(完整word版)离群点检测(基于距离)实验报告

编号南京航空航天大学毕业设计题目基于无线传感网络的离群点检测的研究及实现学生姓名学号学院计算机科学与技术学院专业计算机科学与技术专业班级指导教师二〇一三年六月南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：基于无线传感网络的离群点检测的研究及实现）是本人在导师的指导下独立进行研究所取得的成果。

尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。

作者签名：年月日（学号）：基于无线传感网络的离群点检测的研究及实现摘要无线传感器网络（Wireless Sensor Network，WSN）的迅猛发展推动了人类生活和社会发展的进步，在家庭、商业、医学、工业以及军事领域等都有广泛的应用。

然而，无线传感器网络自身条件的局限性以及分布环境等条件因素的影响，导致传感器网络的感知数据样本存在丢失、错误等问题，这些问题的存在影响了无线传感器网络的应用，至今如何很好地解决这一问题仍是人们亟待解决的问题。

无线传感器网络中的数据异常检测问题严重影响了数据质量和数据的整体分析。

本文针对这个问题给出了解决方法，并通过实验进行了验证。

主要工作如下：支持向量机（Support Vector Machine, SVM）技术解决无线传感器网络中的数据异常问题，虽然可以避免维数灾难的问题，但是对于大规模感知数据时，SVM技术的映射过程开销很大。

针对这个问题，本文提出KNN-SVM算法，该算法先利用KNN算法对感知数据样本进行裁剪，去掉大部分的正常数据，然后对剩下的小部分数据样本进行异常检测，从而可以减少开销；关键词：无线传感器网络，异常点检测，支持向量机，KNN-VSMResearch and implementation of outlier detection based on wireless sensor networksAbstractRapid development of wireless sensor network (WSN) impelled the human life and social progress.WSN has a wide range of applications in family, business, medical, industrial, military fields and so on. However, the limitations of WSN and the distribution of environment result in missing, error and other problems of data samples in WSN, which affect the application of WSN. So how to solve this problem is still the key problem.The problem of outlier detection affects data quality and data integrity analysis.This paper gives a solution to this problem and validated by experiment.The main work is as follows: Support Vector Machine (SVM) technology can solve abnormal data in WSN and can avoid the dimension disaster problem, but for large scale data, SVM technology mapping process is costly. Aiming at this problem, this thesis puts forward KNN-SVM method which uses KNN method to cut data samples and get rid of most of the normal data, and then detect anomaly in the remaining data samples. KNN-SVM can reduce the overhead effectively.Key Words：WSN; data anomaly detection; SVM;KNN-SVM目录摘要 (i)Abstract (ii)第一章引言............................................................ - 1 -1.1 研究背景.......................................................... - 1 -1.1.1 无线传感器网络基本概念....................................... - 1 -1.1.2 无线传感器网络特点........................................... - 2 -1.2 数据挖掘的研究现状................................................. - 4 -1.2.1 国外的研究现状............................................... - 4 -1.2.2 国内的研究现状............................................... - 4 -1.3 本文主要工作....................................................... - 5 -1.4 论文组织结构....................................................... - 5 - 第二章相关理论及技术介绍................................................. - 7 -2.1 离群点检测技术..................................................... - 7 -2.1.1 离群点检测的定义............................................. - 7 -2.1.2 离群点的检测方法............................................. - 7 -2.1.3 离群点检测技术的应用和存在的问题............................. - 9 -2.2. 支持向量机技术................................................... - 10 -2.2.1 支持向量机的背景知识........................................ - 10 -2.2.2 支持向量机技术介绍.......................................... - 11 - 第三章基于无线传感网络的离群点检测的KNN-SVM算法........................ - 14 -3.1 KNN算法.......................................................... - 14 -3.1.1 KNN算法介绍................................................. - 14 -3.1.2 KNN算法描述................................................. - 15 -3.2 KNN-SVM异常检测算法介绍.......................................... - 17 -3.2.1 KNN-SVM算法原理............................................. - 17 -3.2.2 KNN-SVM算法优化问题......................................... - 20 -3.2.3 KNN-SVM算法描述............................................. - 22 - 第四章基于无线传感网络的离群点检测的KNN-SVM算法实现.................... - 25 -4.1 概要设计和需求分析................................................ - 25 -4.2 KNN-SVM算法的实现................................................ - 26 -4.3 数据分析和实验测试................................................ - 35 -4.3.1实验数据来源................................................. - 35 -4.3.2 实验结果和分析.............................................. - 37 - 第五章总结.............................................................. - 39 - 参考文献.............................................................. - 40 - 致谢................................................................ - 42 -第一章引言1.1 研究背景随着时代的进步，人们对科技的认知能力不断提升，对科技的永无止境的探索，在当今人们对科学的探索水平也在快速增长。

基于边界和距离的离群点检测江 峰1,杜军威1,眭跃飞2,曹存根2(1.青岛科技大学信息与科学技术学院,山东青岛266061;2.中国科学院计算技术研究所,北京100080)摘 要: 近年来,离群点检测已经引起人们的广泛关注.离群点检测在网络入侵检测、信用卡欺诈、电子商务犯罪、医疗诊断以及反恐等诸多领域都具有十分重要的作用.离群点检测的目的是为了发现数据集中的一小部分对象,与数据集中其余的大部分对象相比,这一小部分对象有着特殊的行为或者具有反常的属性.针对现有的离群点检测方法不能有效处理不确定与不完整数据的问题,本文将粗糙集中边界的概念与Knorr 等所提出的基于距离的离群点检测方法结合在一起,在粗糙集的框架中提出一种新的离群点定义与检测方法.针对于该方法,我们设计出相应的离群点检测算法BDOD,并且通过在临床诊断数据集上所进行的实验,验证了算法BDOD 的有效性.实验结果表明本文的方法为处理离群点检测中的不确定与不完整数据问题提供了一条新的途径.关键词: 数据挖掘;离群点检测;粗糙集;不确定与不完整数据中图分类号: TP274 文献标识码: A 文章编号: 0372-2112(2010)03-0700-06Outlier Detection Based on Bounda ry and D istanceJI ANG Feng 1,DU Jun -wei 1,SUI Yue -fei 2,CAO Cun -gen 2(1.Colle ge o f Information and Science Technology,Qingdao U niversity o f Sc ienc e and Technology,Qingdao,Shandong 266061,China;2.Institute o f Computing Technology ,Chinese Acade my o f Sciences,Bei jing 100080,China )Abstract: In recent years,outlier detection has gained considerable interest.T he identification of outliers is important for many applications such as intrusion detection,credit card fraud,criminal activities in electronic commerce,medical diagno sis and an -t-i terrorism,etc.The ai m of outlier detection is to find small groups of objects who behave in an unexpected w ay or have abnormal properties when compared with the rest large amo u nt of data.Since the existing methods for outlier detection cannot deal with uncer -tain and incomplete data.In this paper,we propose a new method for outlier definition and detection,which exploits the basic notion )boundary of rough sets and Knorr .s method abou t distance -based o u tliers.We also give an algorithm BDOD to find such outliers w ithin the framework of rough set theory.The effectiveness of our algorithm is demonstrated on publicly clinical diagno sis data sets.O u r method gives a new approach to the treatment of u ncertain and incomplete data in outlier detection.Key words: data mining;outlier detection;rough sets;uncertain and incomplete data1 引言离群数据是数据集中偏离大部分数据的数据,它们的表现与大多数常规对象有着明显的差异,以至于让人怀疑它们可能是由另外一种完全不同的机制所产生的[1].离群数据并不等同于错误数据,离群数据中可能蕴含着极为重要的信息,例如在信用卡欺诈检测、网络入侵检测、疾病诊断、通信欺诈分析、故障检测、灾害预测、恐怖活动防范等诸多领域中,离群点都是数据分析的主要对象[2,3].在所有的科学研究领域中,离群数据都可能给予我们新的视角,从而导致新的理论和新的应用的不断出现.因此,对离群数据进行分析与研究具有十分重要的理论意义和实际应用价值.目前,对离群点的检测和分析已经发展成为数据挖掘中一项重要而又有趣的研究任务[3].离群点检测最早出现在统计学领域[5].后来,Knorr 等将其引入到数据挖掘领域[2,18,19,21].现有的离群点检测方法主要有五类[4]:(1)基于统计的方法[5];(2)基于深度的方法[6];(3)基于聚类的方法[7];(4)基于密度的方法[8];(5)基于距离的方法[2,18,19,21].经过分析,我们发现这些方法基本上都是采用确定性的方式来表示和处理数据的,并没有考虑数据的不确定与不完整性问题.而我们的现实生活中又存在着大量不确定与不完整数据.对于这种类型的数据,现有的离群点检测方法还无法处理.因此,我们迫切需要一种能够处理不确定与不完整数据的离群点检测方法.收稿日期:2008-12-22;修回日期:2009-03-23基金项目:国家自然科学基金(No.60802042,60674004,60641010,60573063,60573064);国家863高技术研究发展计划(No.2007A A01Z325);青岛科技大学引进人才启动基金(No.200702583)第3期2010年3月电 子 学 报ACTA ELECTRONICA SINICA Vol.38 No.3Mar. 2010针对上述问题,在前期研究工作中,本文作者深入研究了如何利用粗糙集来进行离群点检测的问题,并提出了若干基于粗糙集的离群点检测方法[9~11].在文献[9]中,基于粗糙集边界的概念,我们提出了一种基于边界的离群点检测方法.另外,在论文[11]中,我们将基于距离的离群点检测方法引入到粗糙集中,并提出了两种针对分类型属性的距离度量,用于计算对象之间的距离.本文将在前期工作基础上,进一步把基于边界的与基于距离的离群点检测方法结合在一起,在粗糙集的框架中提出一种基于边界和距离的离群点检测方法.自1982年Pawla k提出粗糙集理论以来[16],粗糙集作为处理不确定与不完整数据的重要工具,受到广泛关注.经过二十余年的发展,粗糙集已成为数据挖掘、机器学习等领域的重要方法,其中数据约简是其最主要的贡献之一[22].但是,目前在粗糙集理论中对于离群点检测的研究还没有引起足够的重视,类似的研究还很少见.因此,本文利用粗糙集理论来研究离群点检测,选题具有较强的创新性.由于我们的现实世界中存在着大量不确定与不完整数据,离群点检测不可避免地会遇到不确定与不完整数据的处理问题,因此,本文的研究不仅可以为离群点检测中的不确定与不完整数据的处理提供一种新的解决办法,而且还可以拓宽粗糙集理论在数据挖掘等领域的应用范围,为粗糙集理论开辟一个新的应用空间.2粗糙集理论的基本知识粗糙集理论采用基于信息表的知识表示形式,信息表是粗糙集理论表示和处理知识的基本工具.信息表通常被定义成一个四元组IS=(U,A,V,f),其中U 和A分别代表对象集合与属性集合;V是所有属性论域的并集;f是一个信息函数,使得对任意a I A和x I U, f(x,a)I V[16].给定一个信息表IS=(U,A,V,f),对任意的属性子集B A A,我们都可以确定论域U上的一个不可区分关系IND(B)={(x,y)I U@U:P a I B(f(x,a)=f (y,a))}[16].关系IND(B)将论域U划分成多个等价类,所有这些等价类就构成U的一个划分,记为U/ I ND(B).对任意对象x I U,本文将使用[x]B来表示在关系IND(B)下包含对象x的等价类[16,20].定义1给定一个信息表IS=(U,A,V,f),对于任意B A A和X A U,X的B-上近似和B-下近似分别被定义为:X B=G{[x]B I U/IND(B):[x]B H X Xª};X B=G{[x]B I U/IND(B):[x]B A X}.另外,BNB(X)=X B-X B被称为集合X的B-边界.我们可以将X的边界看成是在现有的知识条件下,无法对其进行确定分类的那些元素所组成的集合.边界是某种意义上论域U中的不确定域.因此,相对于U中的其它对象而言,边界中的元素是一类特殊的对象,这些元素既不能确定地属于X,也不能确定地不属于X[16,20].既然相对于U中其它对象而言,边界中的元素是一类特殊的对象,而我们在进行离群点检测时,正好需要在给定数据集中寻找一小部分行为比较特殊或者具有反常属性的对象.因此,本文在讨论离群点检测时,将考虑使用集合边界所蕴含的信息来进行离群点检测[9].3基于边界和距离的离群点本文将针对信息表来设计基于边界和距离的离群点检测方法,该方法的主要思想可以描述如下:给定一个信息表IS=(U,A,V,f)和任意X A U(X Xª).对于任意B A A,首先,根据关系I ND(B)将集合X分成三个部分:异常边界EB(X)、B-主边界PB B(X)和B-下近似XB.然后,针对任意x I X,分别计算x与EB(X)、PB B(X)以及X B中每个对象之间的距离.最后,根据所求得的距离值,就可以判断x是否是一个离群点.虽然上述方法也是通过计算对象x与X中所有对象的距离来判定x是否为离群点.但是,与基于距离的离群点检测不同的是[2,18,19],我们在寻找X中的离群点时,首先将X分成三个部分,然后对来自这三个不同部分的对象采取不同的方式进行处理.具体来说,对于异常边界中的对象,我们认为这些对象是离群点的可能性最大.因此,如果异常边界中存在越多的对象与x 的距离较近,则x越有可能是离群点.而对于下近似中的对象,我们认为这些对象是离群点的可能性最小.因此,如果下近似中存在越多的对象与x的距离较远,则x越有可能是离群点.另外,对于主边界中的对象,我们认为这些对象是离群点的可能性居中.因此,如果主边界中存在越多的对象与x保持适当的距离,则x越有可能是离群点.总之,在给定的知识条件下,如果对象x 总是与异常边界中的对象靠得很近,而与下近似中的对象离得很远,并且与主边界中的对象保持适当的距离,则我们认为x是X中的一个基于边界和距离的离群点.在传统的基于距离的离群点检测方法中,给定数据集X和x I X,只要X中的大部分(超过一定比例)的对象与x的距离较远(大于给定的阈值),就认为x是一个离群点[2,18,19].虽然这种方法比较简单,但它却忽略了X中对象之间的差异.如果我们在检测离群点时,采用同一种方式来处理X中的所有对象,不加以区分,701第3期江峰:基于边界和距离的离群点检测明显这是不合理的,并且最终将导致检测结果存在着偏差.因此,本文所提出的基于边界和距离的离群点检测方法是对传统的基于距离方法的一种改进.定义2(内边界) 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,我们将集合X 的B -内边界定义为:IB B (X )=G {x I X:[x ]B ¾X }命题1 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,令IB B (X )和X B 分别为X 的B -内边界和B -下近似,则IB B (X)=X -X B .证明 由于X B =G {x I X :[x ]B A X},IB B (X )=G {x I X :[x ]B ¾X},并且对于任意x I X,[x ]B A X 或者[x]B ¾X.因此,x I X B 或者x I IB B (X ),即x I IB B (X )G X B ,所以X A IB B (X )G X B .另外,由内边界和下近似的定义可知,X B A X 且IB B (X)A X ,因此IB B (X )G X B A X.这样,我们就有得到IB B (X )G X B =X.另外,不存在一个对象x I X ,使得[x ]B A X 且[x ]B ¾X ,即不存在一个对象x I X 使得x I X B 且x I IB B (X).因此,IB B (X)H X B =ª.由IB B (X )G X B =X 和IB B (X )H X B =ª,我们可以得到IB B (X )=X -X B .根据上述命题,对于任意的X A U 和B A A ,我们都可以把X 分成两个部分:B -内边界和B -下近似.此外,我们还可以进一步把X 的B -内边界分成两个部分:异常边界和主边界.定义3(异常边界) 给定一个信息表IS =(U,A,V,f ),其中A ={a 1,a 2,,,a m }.对于任意X A U(X X ª)和任意a i I A,令IB {a i }(X )为X 的{a i }-内边界,1[i [m.我们将集合X 在信息表IS 中的异常边界定义为:EB(X )=H mi =1IB {a i }(X )定义4(主边界) 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,令IB B (X)和EB(X)分别为X 的B -内边界和异常边界.我们将集合X 的B -主边界定义为:PB B (X )=IB B (X)-EB(X )定义5(偏离因子) 给定一个信息表IS =(U,A ,V,f )和任意的X A U (X X ª).对于任意B A A 和x I X ,我们将对象x相对于集合X 的B -偏离因子定义为:DF BX (x )={y I EB(X):d(x ,y )[d 1}+{y I PB B (X):d(x ,y )\d 2}+{y I X B :d(x ,y )\d 3}X其中d(x ,y)为在某个给定的距离度量下对象x 与y 间的距离[2,3].另外,d 1、d 2和d 3是三个给定的距离阈值.对象x 的偏离因子DF BX (x )体现了x 在现有知识条件下,是一个离群点的可能性.为了刻画数据集中每个对象的离群程度,本文将在偏离因子的基础上引入一个多重离群因子(Multiple Outlier Factor,MOF )的概念,用来表征信息表中每个对象的离群程度[8,10,11].定义6(多重离群因子) 给定一个信息表IS =(U,A ,V,f ),其中A ={a 1,a 2,,,a m }.对于任意X A U (X X ª)和任意x I X ,我们将对象x 相对于集合X 的多重离群因子MO F X (x)定义为:MOF X (x )=E mj =1DF {a j}X (x )@W {a j }X (x )|A |其中,DF {a j }X (x )为对象x 相对于X 的{a j }-偏离因子;W {a j }X :X y [0,1)是一个权重函数,使得对任意x I X ,W {a j }X (x )=1-[x ]a j H XX为x 的权重,1[j [m.|M |表示集合M 的势.定义7(基于边界和距离的离群点)给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).令L 为一个给定的阈值,对于任意x I X,如果MOF X (x )>L ,则x 被称为X 中的一个基于边界和距离的离群点,其中MOF X (x )为对象x 相对于集合X 的多重离群因子.4 基于边界和距离的离群点检测算法BDOD算法1 BDOD输入 信息表IS =(U,A ,V,f )和X A U,其中|U |=n,A ={a 1,a 2,,,a m },|X |=n X .阈值L 、d 1、d 2和d 3输出 X 中所有离群点的集合O(1)对于A 中的每一个属性a i ,1[i [m,循环执行如下操作:( ) 根据U 中对象在属性a i 上的取值,按照值域上的一个给定次序(例如字典序),对U 中的所有对象进行排序[17];( )求出划分U/I ND({a i });( )计算X 的{a i }-内边界和{a i }-下近似.(2)计算X 的异常边界.(3)对于任意1[i [m,计算X 的{a i }-主边界.(4)对于X 中的每个对象x ,循环执行如下操作:( )对于任意y I X ,计算对象x 与y 之间的距离d(x ,y );( )对于任意1[i [m,计算x 相对于X 的{a i }-偏离因子和{a i }-权重;( )计算对象x 相对于X 的多重离群因子MOF X (x);( )如果MOF X (x )>L ,则令O =O G {x }.(5)算法结束,返回离群点集合O.在算法1中,我们采用了一种预先对U 中对象进702电 子 学 报2010年行排序,然后再计算划分U/IND(B)的方法[17],这样可以有效降低计算划分的复杂度.在最坏的情况下,算法1的时间复杂度为O((m@n2X)+(m@n log n)),空间复杂度为O(m@n),其中m,n和n X分别为集合A, U与X的势.5实验结果为了验证BDOD算法的有效性,我们将通过实验来比较BDOD算法、基于边界的离群点检测方法[9]和基于距离的离群点检测方法[11]各自的性能.在实验中,对于BDOD算法,我们将采用/基于粗糙集的覆盖度量0作为距离度量[11].另外,我们将d1、d2和d3这三个距离阈值分别设置为:d1=|A|/3,d2=|A|/2,d3=0.9@|A|,其中|A|代表属性集A的势.对于基于边界的离群点检测方法和基于距离的离群点检测方法,具体的实验细节请参考文献[10].实验中所采用的数据集有2个:Lymphography(淋巴系统造影术)数据集和Wisc onsin Breast Cancer(威斯康星乳腺癌)数据集[15].在这两个数据集上,我们将采用Ag-garwal等所提出的评价指标体系来评测每类离群点检测方法的性能,该评价体系是目前最常用的一类离群点检测方法评价体系[12,14].给定一个数据集以及数据集中每个对象所属的类,Aggarwal认为要评价一个离群点检测方法的好坏,可以通过在给定的数据集上来运行该方法,并且计算在由该方法所找出的离群点中,真正的离群点所占据的比例.比例越高,则表明该方法的性能越好[12].5.1Lymphography数据集Lymphography数据集中包含148个对象和19个属性[15].所有的对象被分成四个类:/nor mal find0、/me tas-tases0、/malign ly mph0和/fibrosis0.我们将/normal find0和/malign lymph0看作稀有类(注:属于稀有类的对象都是离群点).在实验中,Lymphography数据集中的所有数据都被导入到信息表ISL=(U,A,V,f)中.我们分别在U的两个子集X1和X2中检测离群点,其中:(1)X1={x I U:f (x,dislocation)=1};(2)X2={x I U:f(x,early-up-take)=1D f(x,bl-a ff ere)=1}.具体的实验结果如下面的表1所示.表1信息表ISL 中关于X1和X2的实验结果X1:|X1|=50,|R X1|=4X2:|X2|=90,|R X2|=5离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD DIS BOU离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD D IS BOU2%(1)1(25%)1(25%)1(25%)2%(2)2(40%)2(40%)2(40%) 4%(2)2(50%)2(50%)2(50%)4%(4)4(80%)3(60%)3(60%) 6%(3)3(75%)3(75%)2(50%)5%(5)4(80%)4(80%)3(60%) 8%(4)4(100%)3(75%)2(50%)8%(7)5(100%)4(80%)3(60%) 10%(5)4(100%)3(75%)2(50%)14%(13)5(100%)5(100%)3(60%) 12%(6)4(100%)4(100%)2(50%)66%(59)5(100%)5(100%)4(80%) 32%(16)4(100%)4(100%)3(75%)70%(63)5(100%)5(100%)5(100%) 40%(20)4(100%)4(100%)4(100%)在表1中,/BDOD0、/DIS0和/BOU0分别代表BDOD算法、基于距离的和基于边界的离群点检测方法.|Xj|和|RXj|分别表示集合X j中的元素个数以及X j中的离群点个数,1[j[2.对于Xj中的每个对象x,我们分别利用这三种离群点检测方法来计算x的离群程度值.然后根据每种方法所计算出的Xj中对象的离群程度值,由高到低对Xj中对象进行排序.因此,在表1中/离群程度值前k%的对象(对象个数)0是指在采用某种离群点检测方法来计算X j中对象的离群程度值之后,离群程度值排在前k%的对象以及这些对象的个数.而/属于稀有类的对象个数0则是指在由该方法所检测出的离群程度值排在前k%的对象中,属于稀有类的对象个数./覆盖率0是指这些属于稀有类的对象占Xj中所有离群点的比例,1[j[2[10,11,14].从表1中我们可以看出,对于Lymphography数据集,BDOD算法的性能明显要好于基于距离的方法和基于边界的方法,其中基于边界的方法的性能最差.5.2Breast C ancer数据集Breast Cancer数据集中包含699个对象和9个连续型属性.所有对象被分成两类:/malignant0和/be-nign0[15].为了形成一个极不均匀的分布,我们从该数据集中移去一些属于/malignant0类的对象[13].最终的数据集包括483个对象,其中39个对象属于/malignant0类, 444个属于/benign0类.另外,数据集中的9个连续型属性被分别转换成分类型属性X[13-14].703第3期江峰:基于边界和距离的离群点检测X最终的数据集可以从如下网站获取:http://researc h.c mis.csiro.au/rohanb/outliers/breas-t cancer/在最终所获得的Breast Cancer数据集中,我们将/malignant0类看作稀有类.另外,我们将数据集中的数据都导入到信息表ISW=(U c,A c,V c,f c)中[10,11].我们分别在U c的两个子集X c1和X c2中检测离群点,其中: (1)X c1={x I U c:f c(x,Clump-thickness)=5};(2)X c2={x I U c:f c(x,Mitoses)=1}.具体的实验结果如表2所示.从表2中我们可以看出,对于Breast Cancer数据集中,BDOD算法的性能也明显要好于基于距离的方法和基于边界的方法.因此,这同样证明了我们的方法的有效性.表2信息表IS W中关于X c1和X c2的实验结果X c1:|X c1|=87,|R X c1|=4X c2:|X c2|=454,|R X c2|=23离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD DIS BOU离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD D IS BOU2%(2)2(50%)2(50%)2(50%)1%(5)4(17%)4(17%)4(17%) 3%(3)3(75%)2(50%)3(75%)2%(9)8(35%)6(26%)7(30%) 5%(4)3(75%)3(75%)3(75%)3%(14)11(48%)10(43%)11(48%) 6%(5)4(100%)3(75%)3(75%)4%(18)14(61%)12(52%)13(56%) 7%(6)4(100%)4(100%)3(75%)5%(23)18(78%)15(65%)18(78%) 8%(7)4(100%)4(100%)4(100%)6%(27)20(87%)18(78%)20(87%)7%(32)23(100%)23(100%)21(91%)10%(45)23(100%)23(100%)22(96%)12%(54)23(100%)23(100%)23(100%)6结论针对当前的离群点检测方法无法处理不确定与不完整数据的问题,本文将基于粗糙集边界的离群点检测方法与传统的基于距离的离群点检测方法结合在一起,充分发挥这两类方法各自的特点,提出了一种基于边界和距离的离群点检测方法.该方法利用粗糙集在处理不确定与不完整数据方面的优势,可以从不确定与不完整的数据中高效地检测出离群点.针对该方法,我们在粗糙集的信息表中设计出相应的离群点检测算法BDOD,并且通过实验表明,基于边界和距离的方法比基于边界的方法以及基于距离的方法具有更好的性能.由于利用粗糙集的方法进行离群点检测的研究还很少见,本文的工作不仅使得离群点检测可以处理不确定与不完整的数据,而且还扩展了粗糙集在数据挖掘等领域的应用范围,为粗糙集理论开辟了一个新的应用空间.在下一步的工作中,我们打算将本文所提出的离群点检测方法应用于网络入侵检测,用来解决现有的入侵检测系统中所普遍存在的检测准确率低、误警率高的问题[23].参考文献:[1]D Hawkins,Identifications of Outliers[M].London:Chapmanand Hall,1980.[2]E Knorr,R Ng.Algori thms for mining dis tance-based outliers inlarge datasets[A].In Proc of the24th VLD B Conf[C].New Y ork:Morgan Kaufmann,1998.392-403.[3]J W Han,M D amber.Data M ining:Concepts and Techno logies[M].San Francisco:Morgan Kaufmann,2001.[4]L Kovacs,D Vass,A Vidacs.Improving quality of service pa-rameter prediction with preliminary outlier detection and elim-i nation[A].Proc of the2nd Int Workshop on Inter-Domain Per-formance and Si mulation[C].Budapest,2004.194-199. [5]P J Rouss eeuw,A M L eroy.Robus t Regression and O u tlier De-tection[M].New York:John Wiley&Sons,1987.[6]T Johnson,I Kwok,R T Ng.Fast compu tation of2-dimensionaldepth conto u r s[A].In Proc of the4th Int Conf on Knowledge Discovery and Data M ining[C].New Y ork:AAAI Press, 1998.224-228.[7]A K Jain,M N Murty,P J Flynn.Data clustering:a review[J].ACM Computing Su rveys,1999,31(3):264-323.[8]M M Breunig,H-P Kriegel,R T Ng,J Sander.LOF:identifyingdensity-based local o u tliers[A].In Proc of the2000ACM SIG-MOD Int Conf on M anagement of Data[C].Dallas:ACM Press,2000.93-104.[9]F Jiang,Y F Sui,C G Cao.Outlier detection using rough settheory[A].In Proc of the10th Int Conf on Ro ugh Sets,Fuzzy Sets,Data Mining,and Granular Computing[C].Canada: Springer-V erlag,2005.79-87.[10]F Jiang,Y F Sui,C G Cao.A rough set approach to o u tlierdetection[J].International Jo u rnal of General Sy s tems,2008, 37(5):519-536.[11]F Jiang,Y F Sui,C G Cao.Some issues about outlier detectionin rough set theory[J].Expert Systems with Applications, 2009,36(3):4680-4687.[12]C C A ggarwal,P S Y u.Outlier detection for high dimensionaldata[A].In Proc of the2001ACM SIGMOD Int Conf on M anagement of Data[C].California:ACM Press,2001.37-704电子学报2010年46.[13]S Harkins,HXHe,G J Williams,R A Baxter.Outlier detectionusing replicator neural networks[A].In Proc of the4th Int Conf on Data Warehousing and Knowledge Discovery[C].France:Springer-Verlag,2002.170-180.[14]Z Y He,S C Deng,XF Xu.An optimization model for outlierdetection in categorical data[A].In Int Conf on Intelligent Compu ting[C].China:Springer-V erlag,2005.400-409. [15]S D Bay.The UCI KDD repository[D B].http://kdd.ics.,1999.[16]Z Pawlak,Rough Sets.Theoretical Aspects of Reas oning aboutData[M].Dordrecht:Klu wer,1991.[17]S H Nguyen,H S Nguyen.Some efficient algorithms for roughset methods[A].In Proc of the6th Int Conf on Information Processi ng and Management of U ncertainty[C].Spain: Springer-V erlag,1996.1451-1456.[18]L Z Wang,L K Z ou.Research on algorithms for mining dis-tance-based outliers[J].Chinese Jo u rnal of Electronics,Be-ijing,14(3),2005.485-490.[19]E Knorr,R Ng,V T ucakov.D istance-based outliers:algo-ri thms and applications[J].VL DB Journal,2000,8(3-4):237-253.[20]刘清.Rough集及Rough推理[M].北京:科学出版社,2001.Q Liu.Rough Sets and Rough Reasoning[M].Beijing:Sc-ience Press,2001.(in Chinese)[21]黄毅群,卢正鼎,胡和平,李瑞轩.分布式异常检测中隐私保持问题研究[J].电子学报,2006,34(5):796-799.Y Q Huang,Z D Lu,H P Hu,RXLi.Privacy preserving outl-ier detection[J].Acta Electronica Sinica,2006,34(5):796-799.(i n Chinese)[22]邓大勇,黄厚宽,李向军.不一致决策系统中约简之间的比较[J].电子学报,2007,35(2):252-255.D Y Deng,H K Huang,X J parison of various typesof reductions in i nconsistent systems[J].Acta Electronica Sinica,2007,35(2):252-255.(in Chinese)[23]陶新民,陈万海,郭黎利.一种新的基于模糊聚类和免疫原理的入侵检测模型[J].电子学报,2006,34(7):1329-1332.X M T ao,W H Chen,L L G uo.A novel model of IDS based on fuzzy cluster and immune principle[J].Acta Electronica Sinica2006,34(7):1329-1332.(in Chinese)作者简介:江峰男,1978年生,博士、副教授.2007年毕业于中科院计算所.主要研究方向有粗糙集理论、人工智能.现主持国家自然科学基金项目1项.近年来,发表论文10多篇,其中SCI收录6篇.E-mail:jiangkong@眭跃飞男,1963年生,中科院计算所研究员,博士生导师,中国计算机学会高级会员.主要研究方向为人工智能、数理逻辑、大规模知识处理的理论基础.曹存根男,1964年出生,中科院计算所研究员,博士生导师,入选中科院百人计划.主要研究方向为人工智能、知识工程、大规模知识获取与知识处理、情感计算等.705第3期江峰:基于边界和距离的离群点检测。

离群点检测（异常检测）是找出其行为不同于预期对象的过程，这种对象称为离群点或异常。

离群点和噪声有区别，噪声是观测变量的随机误差和方差，而离群点的产生机制和其他数据的产生机制就有根本的区别。

全局离群点：通过找到其中一种合适的偏离度量方式，将离群点检测划为不同的类别；全局离群点是情景离群点的特例，因为考虑整个数据集为一个情境。

情境离群点：又称为条件离群点，即在特定条件下它可能是离群点，但是在其他条件下可能又是合理的点。

比如夏天的28℃和冬天的28℃等。

集体离群点：个体数据可能不是离群点，但是这些对象作为整体显著偏移整个数据集就成为了集体离群点。

离群点检测目前遇到的挑战•正常数据和离群点的有效建模本身就是个挑战；•离群点检测高度依赖于应用类型使得不可能开发出通用的离群点检测方法，比如针对性的相似性、距离度量机制等；•数据质量实际上往往很差，噪声充斥在数据中，影响离群点和正常点之间的差别，缺失的数据也可能“掩盖”住离群点，影响检测到有效性；•检测离群点的方法需要可解释性；离群点检测方法1. 监督方法训练可识别离群点的分类器；但是监督方法检测离群点目前遇到几个困难：1.两个类别（正常和离群）的数据量很不平衡，缺乏足够的离群点样本可能会限制所构建分类器的能力；2.许多应用中，捕获尽可能多的离群点（灵敏度和召回率）比把正常对象误当做离群点更重要。

由于与其他样本相比离群点很稀少，所以离群点检测的监督方法必须注意如何训练和如何解释分类率。

One-class model，一分类模型考虑到数据集严重不平衡的问题，构建一个仅描述正常类的分类器，不属于正常类的任何样本都被视为离群点。

比如SVM决策边界以外的都可以视为离群点。

2.无监督方法正常对象在其中一种程度上是“聚类”的，正常对象之间具有高度的相似性，但是离群点将远离正常对象的组群。

但是遇到前文所述的集体离群点时，正常数据是发散的，而离群点反而是聚类的，这种情形下更适合监督方法进行检测。

1。

4 数据仓库和数据库有何不同?有哪些相似之处？答：区别:数据仓库是面向主题的，集成的,不易更改且随时间变化的数据集合，用来支持管理人员的决策,数据库由一组内部相关的数据和一组管理和存取数据的软件程序组成，是面向操作型的数据库，是组成数据仓库的源数据.它用表组织数据，采用ER数据模型。

相似:它们都为数据挖掘提供了源数据，都是数据的组合.1。

3 定义下列数据挖掘功能：特征化、区分、关联和相关分析、预测聚类和演变分析。

使用你熟悉的现实生活的数据库,给出每种数据挖掘功能的例子。

答：特征化是一个目标类数据的一般特性或特性的汇总。

例如，学生的特征可被提出，形成所有大学的计算机科学专业一年级学生的轮廓，这些特征包括作为一种高的年级平均成绩（GPA:Grade point aversge）的信息,还有所修的课程的最大数量。

区分是将目标类数据对象的一般特性与一个或多个对比类对象的一般特性进行比较。

例如，具有高GPA 的学生的一般特性可被用来与具有低GPA 的一般特性比较.最终的描述可能是学生的一个一般可比较的轮廓，就像具有高GPA 的学生的75％是四年级计算机科学专业的学生,而具有低GPA 的学生的65%不是。

关联是指发现关联规则，这些规则表示一起频繁发生在给定数据集的特征值的条件.例如,一个数据挖掘系统可能发现的关联规则为：major(X，“computing science”) ⇒owns(X，“personal computer”)［support=12%, confidence=98％] 其中，X 是一个表示学生的变量。

这个规则指出正在学习的学生，12％(支持度）主修计算机科学并且拥有一台个人计算机。

这个组一个学生拥有一台个人电脑的概率是98%（置信度，或确定度)。

分类与预测不同，因为前者的作用是构造一系列能描述和区分数据类型或概念的模型(或功能），而后者是建立一个模型去预测缺失的或无效的、并且通常是数字的数据值.它们的相似性是他们都是预测的工具：分类被用作预测目标数据的类的标签，而预测典型的应用是预测缺失的数字型数据的值.聚类分析的数据对象不考虑已知的类标号。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从题目编号中选择一项填写）： A题目：数学建模竞赛参赛队员：姓名专业班级所在学院电话（手机）是否报名全国竞赛A题：离群点的判定摘要离群点是指数据中，远离数值的一般水平的极端大值和极端小值，也称之为歧异值，有时也称其为野值，其对后续的数据处理有很大的影响；本文研究的目的是拟建立适当的数学模型，评判出一组数据中的离群点，并对出现的离群点进行处理。

对于问题一的第一小问，本文拟将一维数据分成确定数据和不确定数据两类，对于确定数据建立残差绝对值模型发现离群点，当残差绝对值y(n)>y1-a(n)时，残差绝对值对应的Xi即为离群点；对于不确定数据，建立可能世界模型确定数据的邻居对象，在传统确定性数据判定方法的基础上，离群点的概率还需要满足所给出的概率阀值；同时满足两个条件即为离群点。

对于问题一的第二小问，本文拟采用aggarwal等所提出的评价指标体系评价残差绝对值模型判定离群点的有效性，计算真正的离群点数占该方法所找出的离群点的比例，比例越大残差绝对值模型判定离群点的有效性越好。

对于问题二，对离群点的处理本文拟分为标准偏差预知和标准偏差未知两类，对于标准偏差预知，本文拟采用统计量T=(X-X)/σ，T值大于舍弃界限中相应置信度下的临界值则舍弃否则保留；对于标准偏差未知，本文分别采用拉依达准则、狄克松法、肖维特法、格鲁布斯法、学生化残差绝对值法对离散点进行处理，更科学决定离散点的舍与留。