基于分化距离的离群点检测算法

实现离群点检测的机器学习算法离群点检测（Outlier detection）是机器学习中的一项重要任务，旨在识别数据集中与其他数据点不太相似或异常的数据点。

离群点也被称为异常值，它们与正常的数据点存在明显的偏离或异常行为。

离群点检测的目标是从大量的数据中准确地识别这些异常值，以便进一步分析和采取相应的措施。

实现离群点检测的机器学习算法有多种，下面将介绍一些常用的方法：1. 统计学方法：这些方法利用统计学原理来识别离群点。

其中一个常用的方法是基于数据的标准差或均值的阈值判断。

如果数据点的值偏离均值或标准差超过一定的阈值，则将其标记为离群点。

这种方法简单易用，但对于复杂的数据分布可能不够准确。

2. 基于距离的方法：这些方法通过计算数据点与最近邻数据点之间的距离来判断是否为离群点。

其中一种常见的方法是K近邻算法，它通过计算每个数据点与其K个最近邻数据点的距离，并将距离较远的点标记为离群点。

还有一种方法是基于密度的离群点检测算法，如LOF（局部离群因子）算法，它衡量数据点周围的局部密度与其邻近数据点的局部密度之比，从而识别离群点。

3. 基于聚类的方法：这些方法将数据点分为不同的聚类，并将边界上的数据点标记为离群点。

其中一个常用的算法是DBSCAN（基于密度的聚类应用噪声）算法，它通过将数据点组织成高密度区域和低密度区域来判断离群点。

也有一些其他的聚类算法可用于离群点检测，如基于谱聚类、层次聚类等。

4. 基于深度学习的方法：近年来，深度学习在离群点检测中的应用日益增多。

深度学习模型可以自动从数据中学习特征，并且对非线性和高维数据具有较好的处理能力。

一些常用的深度学习模型，如自编码器（Autoencoder）和变分自编码器（Variational Autoencoder），可以用于离群点检测。

这些模型可以通过重构误差或潜在空间的分布来判断数据点的异常性。

总结而言，离群点检测是机器学习中的一项重要任务，可以通过多种算法实现。

离群点判断算法
离群点判断算法主要用于检测数据集中与大多数观测值显著不同的异常值。

简要介绍如下：
1. 四分位数法则：基于箱线图原理，若数据点小于下四分位数(Q1)减去1.5倍四分位距(IQR)，或大于上四分位数(Q3)加上1.5倍IQR，则视为离群点。

2. Z-score方法：计算每个数据点与其均值的偏差（即标准分数），若绝对值超过预定阈值（如3），则视为离群点。

3. DBSCAN聚类算法：通过密度连接度识别核心对象和边界对象，不满足邻域密度要求的数据点被视为离群点。

4. LOF(Local Outlier Factor)：比较数据点与周围邻居的局部密度，LOF值过高表示该点可能为离群点。

5. Isolation Forest：利用随机森林构建隔离树，孤立于树结构顶层的数据点更可能是离群点。

这些算法可应用于数据分析、故障检测等多个领域，有助于发现潜在问题或异常现象。

基于深度的离群点检测方法引言：随着大数据时代的到来，数据的规模和复杂性不断增加。

在这些海量数据中，可能存在一些与其他数据明显不同的离群点，它们可能是异常事件、故障、欺诈行为等。

因此，离群点检测成为了数据挖掘和异常检测领域的一个重要任务。

传统的离群点检测方法往往依赖于统计学或距离度量，但随着深度学习的兴起，基于深度的离群点检测方法也得到了广泛关注。

深度学习在离群点检测中的应用：深度学习是一种强大的机器学习技术，能够从数据中学习到更高层次的抽象特征表示。

在离群点检测中，深度学习可以通过学习数据的分布模式来识别离群点。

它不仅可以捕捉到数据的局部特征，还能够学习到数据的全局特征，从而提高离群点检测的准确性。

基于深度的离群点检测方法：基于深度的离群点检测方法主要包括自编码器、生成对抗网络和变分自编码器等。

1. 自编码器（Autoencoder）：自编码器是一种无监督学习方法，通过将输入数据压缩成低维编码再进行解码重建，从而学习到数据的潜在表示。

在离群点检测中，自编码器可以通过对正常数据进行重构来判断新样本是否为离群点。

如果重构误差大于某个阈值，则将其判定为离群点。

2. 生成对抗网络（Generative Adversarial Network，GAN）：生成对抗网络由生成器和判别器组成，通过对抗学习的方式来生成和判别样本。

在离群点检测中，生成器可以学习到正常数据的分布，而判别器则可以判断新样本是否为离群点。

如果生成器无法生成与正常数据相似的样本，判别器就会将其判定为离群点。

3. 变分自编码器（Variational Autoencoder，VAE）：变分自编码器是一种生成模型，通过学习潜在变量的分布来生成新样本。

在离群点检测中，变分自编码器可以通过计算样本的重构误差和潜在变量的分布来判断其是否为离群点。

如果重构误差大且潜在变量的分布与正常数据不一致，则将其判定为离群点。

优势与挑战：基于深度的离群点检测方法相比传统方法具有以下优势：1. 可以学习到更高层次的抽象特征表示，从而提高离群点检测的准确性；2. 不需要依赖于先验知识或特定的距离度量，适用于多种类型的数据；3. 可以处理高维数据和非线性数据。

大规模数据中的离群点检测方法研究一、绪论在大规模数据中，信息的数量很大，而且数据的结构比较复杂。

因此，离群点检测是大规模数据挖掘中常见的问题，而且对于很多领域都有着极其重要的实际应用，例如金融风险管理、健康监测、木材病虫害分析等。

离群点检测是数据挖掘中的一项基本任务，其目的是识别出与大多数数据点不同的数据样本。

离群点通常被称为异常值或噪声点，而离群点检测的目标是识别和排除这些点，以便进一步分析数据。

本文将介绍几种大规模数据中的离群点检测方法。

二、离群点检测方法1. 基于统计方法的离群点检测方法统计方法是最早也是最基本的离群点检测方法之一。

这些方法通常涉及到基本的假设检验、最小二乘法以及高斯混合模型等。

其中，基于高斯混合模型的离群点检测方法是常用的统计学方法之一，其思想是将数据集分解为多个高斯分布，使得每个高斯分布含有一个或多个类似的数据集。

采用 EM 算法对高斯分布进行参数估计，最后根据估计的结果确定离群点。

2. 基于距离的离群点检测方法基于距离的离群点检测方法是一种常用的基于相似性的技术。

本质上，该技术通过将点与它们的相邻点进行比较来评估它们是否为离群点。

最常用的基于距离的离群点检测方法是基于 k 邻居算法的检测方法。

该算法基于距离度量，利用查询点周围 k 个邻居的距离计算离群得分。

具体而言，它利用距离计算，将于邻居间存在较大距离的数据点标识为离群点。

3. 基于密度的离群点检测方法基于密度的离群点检测方法是另一种常见的方法。

该方法通过计算一个点周围的点的密度来确定该点是否为离群点。

最常用的基于密度的离群点检测方法是LOF算法。

该算法基于距离和密度的概念，因此它结合了基于距离和基于密度的技术。

具体而言，LOF算法会计算每个点相对于周围邻居的局部密度，并将其用于计算该点的离群得分。

4. 基于子空间的离群点检测方法随着高维数据的产生，传统的距离和密度的离群点检测方法已经不能很好地应对高维数据的需求。

基于边界和距离的离群点检测江 峰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期江峰:基于边界和距离的离群点检测。

一种改进的基于距离的离群挖掘算法离群点是数据分析中非常重要的一个概念，它是指数据集中与其他数据不同或异常的数据点。

通常情况下，离群点可能代表数据错误、异常事件或互动行为。

因此，人们需要通过一些离群挖掘算法来识别这些离群点。

在离群挖掘算法中，常用的方法包括基于统计学的方法、基于聚类的方法、基于距离的方法等。

其中，基于距离的离群挖掘算法是非常常用的方法之一。

这种方法基于异常值点与其他数据点之间的距离来检测离群点。

然而，作为一种传统的离群挖掘方法，基于距离的算法在实际应用中还存在一些问题。

比如说，当数据点分布不均、噪音不规整、维度过高时，这种算法容易失效或者误判。

那么我们要如何解决这些问题呢？最近，一种改进的基于距离的离群挖掘算法被提出，它可以有效解决传统算法的问题。

这个算法的核心思想是基于数据点在某个距离内的密度来评估离群点。

当某个数据点周围的密度非常低时，这个数据点就很可能是离群点。

为了实现这个算法，我们需要依次进行三个步骤。

第一步，我们需要定义数据点邻域的距离阈值T。

这个值决定了我们将考虑哪些距离内的数据点。

第二步，我们需要计算每个数据点周围的密度并与其他数据点进行比较。

第三步，我们根据分数来判断哪个数据点是离群点。

通过这种改进的基于距离的算法，我们可以大大提高离群点的检测效率和准确性。

这个算法在金融、网络安全、医疗等领域中都有很好的应用前景，具有很好的实际意义和指导意义。

总之，离群挖掘是数据分析中的重要问题之一，基于距离的算法是非常常用的方法之一。

但是，传统算法在某些情况下容易失效或者误判，因此我们需要不断改进算法来适应新的数据分布。

改进的基于距离的离群挖掘算法便是一个很好的例子，它直接从数据的密度出发，给出了更加全面、可靠的离群点检测方法，具有重要意义！。

基于距离的离群点检测算法08计算机二班侯宇铭张国勇易小倩一、概述：这个算法是一个基于距离的异常点检测算法，算法以欧式距离为衡量标准，整个算法分三个部分。

第四部分的改进是用了类似密度检测的思想，比较了之前步骤选出的怀疑离群点的三近邻，经过C++语言的实现，效果还不错。

但是程序稍有漏洞，因此没有在这里体现。

但是第四阶段算法的思想已经附在算法描述后面。

本文档附上测试的数据集的arff格式，excel格式，以及txt供程序使用的格式。

三种格式的数据都是一样的。

数据分布如下：附上算法涉及的变量名称对应表：二、算法描述：（这里以数据集为两个相对集中的数据簇和若干离群点为例进行说明）第一部分：找出两个质心Step1: 遍历数据，将数据存入数组dot中该数据设为二维数据，有x,y两个属性。

Step2:设定遍历时的第一个和第二个数据为初始质心。

设定两个变量longest_distance分别记录两个初始簇的最长的距离，设置dotcore1变量记录第一个簇的质心，dotcore2变量记录第二个簇的质心。

Step3:循环：当一个新的点p进入程序时，首先比较点p分别到点dotcore1的距离和到dotcore2的距离，选择距离较小的质心（这里假设选择了dotcore1），记该距离为distancep。

比较distancep和第一个簇（因为选择了dotcore1）的longest_distance。

若distancep<longest_distance，开始下一次循环。

若distancep>longest_distance，则使点p成为新的质心coredot1。

这样循环下去，就可以找到两个簇的最终质心。

算法流程图：进入阶段2图.1 阶段1第二部分：将所有的点归簇，并筛选一部分点Step4: 开始第二次点的扫描：当一个新的点p进入程序时，首先比较点p分别到点dotcore1的距离和到dotcore2的距离，选择距离较小的质心。