离群点挖掘

离群点挖掘（精选7篇）

离群点挖掘 篇1

离群点检测又称异常检测、孤立点检测、偏差检测。Hawkins[1]给出了离群点的本质性定义:离群点是数据集中偏离大部分数据的数据,使人们怀疑这些数据的偏离并非由随机因素产生,而是产生于完全不同的机制。也就是说,离群点是数据集中与其他数据明显不一致的观测值。

离群点检测在传感器网络中有许多重要的应用,例如异常事件检测,动物的行为改变,异常入侵检测等。离群点检测提供了数据可靠性、事件报告和网络安全等功能,在环境监测和濒危物种生活习性监督等领域有着广泛应用。离点群检测是数据挖掘的基本任务之一,与数据挖掘的其他任务一关联规则分析、分类分析、聚类分析等任务相比,离群点检测更加符合数据挖掘的本质。

随着传感器网络技术的发展,WSN中的离群点检测成为近年来研究的热点,出现了很多检测算法。由于网络有限的资源,传感器网络中的数据挖掘技术受到了很多的限制,使得其离群点检测面临严峻的挑战[2],最棘手的问题是如何在能量消耗最小的情况下,提高检测精度。

由于受到网络通信带宽有限、物理设备故障、恶劣环境及外界干扰等因素影响,传感器网络中节点收集的数据往往是不可靠不精确的,数据会出现异常、丢失、不一致等问题。在WSN中,离群点定义为那些明显偏离传感数据正常模式的数据[3]。在WSN中传感器节点用于监测物理世界,因此存在着代表正常行为和状态的传感数据模式。

由于WSN特殊的特点,如资源受限,物理故障,及恶劣的环境影响等,无线传感器网络更容易产生异常值。很多课题研究如何在WSN中识别离群点原因的问题,包括错误检测,事件检测以及入侵检测。这一方向的研究值得深入探讨,以获得对决策有帮助的信息,而不是单纯地将离群点作为错误信息忽略掉。

在许多研究中,为了减少不一致数据也就是离群数据对分析结果的影响,离群点常常被忽略或者作为噪声被处理,然而,“一个人的噪声可能是另一个人的信号”,不加分析地舍弃离群数据,可能导致重要信息的丢失[4]。例如在欺诈检测中,离群数据可能意味着欺诈行为的发生;在环境监测中,离群数据可能预示着灾害天气的到来;在入侵检测中,离群数据可能意味着入侵行为的发生等等,由此可见离群数据检测是数掘挖掘领域的一项关键任务。如果可能,噪音和错误数据应该被忽略或纠正,因为噪音是随机的错误,不会对实际数据分析造成影响。而造成离群的其他原因应该识别出来,因为其中可能隐含研究者感兴趣的关于事件的重要信息。

要将现有的离群点检测技术应用到传感器网络中,存在的主要问题有[5,6,7,8]:

(1)大多数现有工作没有考虑多变量数,假设传感数据是单变量的。然而,有时候单个变量没有出现异常,但多个变量一起考虑时可能就是异常状况。

(2)现有技术考虑邻居节点之间的空间关联,但如何选择合适的邻居范围是一个问题。而考虑数据事件关联性的时候,如何选择滑动窗口的大小也是个问题。

(3)很少区别离群点究竟是事件还是错误。现有方法只是简单将离群点认为是错误。通常认为错误应该被删除,关于隐藏事件的重要的信息有可能丢失。实际上这些技术没有具体描述如何处理识别出来的离群点。

(4)许多技术需要用户定义阈值,但我们往往难以定义一个合适的阈值。此外,如果WSN特征动态变化的话,设置固定的阈值也是不合理的。

(5)这些技术假设传感节点是静止的,没有考虑节点移动性。如果将这些算法应用到动态网络环境中也存在一些问题。

参考文献

[1]Hawkins D.Identification of Outliers[M].London:Chapmanand Hall,1980.

[2]Zhang Y.Meratnia N.,Havinga P.Outlier Detection Techniquesfor Wireless Sensor Network:A Survey[J].IEEE COMMUNICATIONSSURVEYS&TUTORIALS,2010,12(2):1—12

[3]Chandola,V.,Banerjee,A.and Kumar,V.(2007)'Outlier detection:a survey',Technical Report,University of Minnesota.

[4]李建中,李金宝,石胜飞.传感器网络及其数据管理的概念,问题与进展[J].软件学报,2003,14(10):1717-1727.

[5]马祖长,孙怡宁,梅涛.无线传感器网络综述.通信学报,2004,25(4):114—124.

[6]Sinhua A,handrakasan A.Dynamic power management in wire-less sensor network[J].IEEE Design and Test ofComputer,2001,l8(2):62-74.

[7]Akyildiz,I.F.,Su,W.,Sankarasubramaniam,Y.and Cayirci,E.(2002)'Wireless sensor net-works:a survey',Computer Networks,Vol.38,No.4,pp.393-422,March.

[8]Gaber,M.M.(2007),Data Stream Processing in Sensor Networks',Springer.

离群点挖掘 篇2

一、充分利用歌曲，挖掘“兴趣点”

课前一首歌是组织教学的好方法，它能使学生以饱满的精神，为上好一堂课作前奏，所以我在这次活动中以歌曲开头，调节了课堂气氛又缓解了学生的紧张情绪。

二、以身体语言，培养“兴趣点”

教态即教师的身体语言，它是无声的语言，能对教学起到恰到好处的补充配合修饰作用，调动学生的兴趣，比如我在教“bybus””bycar”“bybike““byplane”时，充分运用肢体语言，让学生边说边做，在活动中带动起学生兴趣和积极性，效果比较好。

三、精心组织活动，寻找“兴趣点”

传统的英语教学，往往很注意课堂纪律，课堂上静静地听老师讲，然后跟老师读，这样容易使学生失去“兴趣点”。学生好玩好动是天性，因此我们可以通过游戏活动，让他们寻找学习的“兴趣点”。比如：我在授 “Let`sgotothe…”“Ok/Allright/Great”“Buthow?”“By…”这组句型时，采用游戏邀请朋友出去玩的接龙形式，使他们的身心达到完全投入，加速了他们撑握句型的速度，并且使枯燥机械的句型操练变生动活泼趣味无穷……

离群点挖掘 篇3

在产品的使用中质量问题一直是人们关注的焦点, 自20世纪90年代开始, 人们又把质量提升到了一个前所未有的高度来对待, 企业只有在生产的同时不断提高产品的质量, 才能在激烈的竞争中保持不败之地, 保证企业迅速地发展和提高。因此对工件表面离群数据的挖掘, 以及工件表面的缺陷再造, 就显得尤为重要。在国外自20世纪60~70年代就已经开始了工件表面缺陷自动检测系统的研究, 现在某些技术, 如超声波检测技术、激光扫描技术、磁记忆检测技术、涡流检测技术、光电检测技术等已相当成熟。以上有几种世界上较为典型的离群数据采集的检测技术, 这些技术在各自专用的领域都已成型, 并且相当成熟。它们都具有各自的长处, 使它们能够在自己的位置发挥最大的作用。

1 国外典型离群数据采集

比利时一家名为Porldela Praye的工厂运用机器视觉方法, 对钢板因轧制或电镀时所产生的工件表面缺陷进行监视, 钢板的行进速度为7 m/s, 可检测直径或宽度为1~1.5 mm的表面缺陷, 在行进钢板的每一面, 装有2台摄像机和1支宽2 m的照明灯。4幅图像传送到图像处理系统中进行分析, 实时图像可以按照灰度图像或者二值图像的形式来显示, 可指出表面缺陷是否具有周期性出现以及周期可能会是多少 (m) , 缺陷距离头部和边缘位置, 自动在每一板卷的末尾处标识出结果。这种检测机器组成较为简便, 而且实用。它可以快速而且较为准确地检测出工件表面的缺陷并分析出缺陷的一些特性, 从而发现工件是否有加工工序或者机床磨损等原因造成的周期性缺陷。但是它还有一些不足之处, 光源的强弱和光的折射及反射等光学条件有可能会使图像处理系统分析时产生误差, 从而影响到最终结果。

挪威Ynve Strom所提出的用来检测连铸坯表面质量的方法, 是将连铸坯通过一个高频线圈, 使连铸坯表面有感应电流通过, 在钢的热力学和电气性能、感应线圈的参数和连铸坯速度等不变的情况下, 在钢坯表面的缺陷位置, 感应电流的流通路径会增长, 所以在表面单位的长度上将会产生较大的功耗, 造成该部位的温度上升;在钢坯的四周装上4个红外线扫描器用来探测表面温度的分布情况, 从而确定缺陷的形状和位置。此方法可以准确地检测到细微变化, 使得钢坯表面的缺陷可以精确地显现出来, 防止一些光学的反射和折射造成的差异。但是这种方法有些缺点, 必须要保持匀速条件而且感应线圈必须均匀产生稳定的感应电流, 否则将会引起钢坯表面温度变化使红外扫描出现误测。并且这个方法所需要的装置相对较为复杂而且不适合快速检测。

英国的Smanvis装置, 可监视热轧、冷轧、镀锌和彩色板带材, 并且可对缺陷分类。此系统可以对缺陷的类型、数量以及位置、板卷的宽度和长度进行储存。当探测到缺陷时, 图像就会因自动触发而“冻结”起来, 还能对需要的部位加以放大, 方便仔细观察。该装置对工件缺陷的检测详细精确, 可以实时观察缺陷的具体状况, 对缺陷做出详细而正确的判断。而且该装置还可以存储缺陷的一些详细信息, 能够供人分析造成缺陷的原因和概率。

2 国内典型离群数据采集

在国内, 华北电力大学的魏钰对基于图像轮廓特征的机械零件识别进行了研究, 把图像进行减弱噪音的预处理, 然后将图像二值化。再利用图像边缘检测和轮廓提算法, 得到图像中目标物体的轮廓链码, 并且他首次提出了标记轮廓曲线变化的特征。这种基于图像轮廓特征的机械零件识别, 可以经过图像采集后对图像轮廓分析, 获得轮廓链码后除去离群的数据后便可得到标准的轮廓曲线, 标记轮廓曲线的变化特征后将能确定该机械零件。但是这种方法要对零件进行预处理, 这对检测流程和检测速度都有或多或少的影响, 不太适合流水线式的检测。

天津大学的丁金明研究了关于金属镀层工件表面缺陷自动检测系统, 初步设计出了金属镀层的工件表面缺陷的面阵CCD自动监测系统。

3 离群数据发展方向

以上的不同检测方法也证明了离群数据可以帮助我们更好地发现产品缺陷, 并且可以省去人工检测, 还可以避免人工检测中由于检测者的个人原因造成的各种误差和遗漏。不过目前的检测和分析技术还有局限性, 都只能应用于自己特定的生产线上, 难以通用, 所以将会造成不同技术中有不同的缺点。还有一点是离群数据采集时的通病, 即如何界定离群点, 以什么值作为区分离群点的标准。这些还需要一些人工的设定, 系统不能通过智能自行制定。我们应该更深入地探寻这些问题, 从而制造出可以代替人工并且优于人工的检测方法, 使产品的质量问题不再成为难以攻克的堡垒。各种不同的离群数据采集和对离群数据的分析应用正在不断被挖掘, 这将使我们对产品质量检测更加智能、准确、细致。我们也将不断地研究更新, 将离群数据的挖掘和分析技术不断推进。

摘要：工件表面离群数据的挖掘是一种通过现代科学技术方法对工件表面进行扫描取点, 并在获取的点群中找出离群的缺陷点, 然后对这些有质量缺陷的离群点进行修复, 以达到合格的质量标准。在该挖掘过程中, 尚有一些问题有待解决, 例如:如何判断什么样的点是离群点, 选出离群点的标准是什么等。且不同的扫描方法和不同的检测技术都有着不一样的效果, 这些都要通过实践不断地改进。

关键词：工件表面,缺陷,再造离群数据,采集,自动检测系统

参考文献

[1]黄洪宇, 林田祥, 陈崇成, 等.离群数据挖掘综述[J].计算机应用研究, 2006 (8) :8-13.

[2]夏火松, 蔡淑琴.基于分形的市场营销离群数据挖掘模型[J].计算机工程与应用, 2006, 2 (12) :24-26.

[3]聂建辉, 胡英, 马孜.散乱点云离群点的分类识别算法[J].计算机辅助设计与图形学学报, 2001, 23 (9) :1526-1532.

离群点挖掘 篇4

1离群点检测算法

1.1基于统计学的方法[3,4]

统计学方法又分为参数方法和非参数方法。参数方法假定正常数据的分布符合一个统计模型, 而离群点就是不遵循分布模型的点;非参数方法对数据作较少的假设, 常见的有使用直方图的方法和基于核密度估计[5]的方法。统计学方法的检测结果在统计上是无可非议的, 但检测的结果往往难以理解, 而且即使是非参数方法也需要用户提供参数, 例如用直方图进行离群点检测时, 箱的宽度的选择对检测的结果将产生很大的影响。

1.2基于邻近性的方法[6,7]

基于邻近性的方法比较直观易懂, 离群点就是远离其他点的点。基于距离的方法就是给定一个邻域半径, 如果某点邻域范围之内的点的数量如果小于某个阈值, 那么该点就被视为离群点, 邻域半径和相应的阈值将直接影响检测的结果。针对基于距离的检测只适用于全局离群点的检测的不足, 提出了基于密度的方法, 基于密度的检测方法将离群点定义为密度明显小于其邻域密度的点, 最经典的基于密度的方法就是LOF算法[6], 后续又提出了许多对LOF算法的改进和变种[8—10]。

1.3基于分类的方法[11]

分类离群点检测算法主要是针对有标号训练集的, 通过对标记训练集的学习, 可以得到分类模型, 基于分类模型就可以区分出正常数据点和离群点, 检测效果依赖于分类模型的质量。

1.4基于聚类的方法[12]

基于聚类的方法就是在聚类的基础上, 将不属于任何簇的以及小簇归为离群点的检测算法, 优点是可以实现无监督学习, 缺点是高度依赖于所选择的聚类算法。

本文主要关注基于邻近性的方法。基于邻近性的离群点检测, 都要进行数据点之间距离的计算, 常见的距离计算方法有欧氏距离、马氏距离、闵可夫斯基距离等, 这些距离都是综合考虑数据在各个维度上的差异, 但并没有考虑各个维度具体的影响有多大。针对不同属性对数据的局部离群因子的贡献的不同, 提出了一种计算距离时的加权策略。加权策略对数值属性和标称属性分别考虑, 数值属性在规范化的基础上根据标准差的不同, 赋予不同的权值, 而标称属性则通过信息熵来进行加权, 当数据既包含数值属性又包含标称属性时, 为此提供了了一种综合加权策略。在加权距离的基础上, 运用LOF算法的思想, 提高了离群点的检测精度, 通过实验进行了证明。

2 LOF算法

局部离群点因子 (local outlier factor, LOF) 算法[6]由Breunig等人于2000年提出, 主要思想是为每个数据点定义一个直观的局部离群点因子, 通过比较LOF值的大小, 就可以知道数据点的离群程度。LOF由数据点周围的密度与其邻域周围的密度的比值来体现, 考虑了数据分布的局部特性, 在实际的离群点检测中体现了良好的性能。

定义1k-距离邻域设D为数据集, 数据点的k-距离邻域包含到o的距离不大于distk (o) 的数据点的集合, 记作Nk (o) ,

dist (o, o') 为o和o'之间的距离, distk (o) 是数据点o的k-距离, 即o与其第k个最近邻之间的距离, distk (o) 满足以下性质:

为了克服某些离o特别近的点对o的局部密度的影响, 定义了可达距离的概念, 在计算o的局部密度时用可达距离代替实际距离可以起到光滑的效果。

定义2可达距离数据点o与o'之间的可达距离reachdistk (o←o') 为

reachdistk (o←o') =max{distk (o) , dist (o, o') }可达距离通常不对称, 即

reachdistk (o←o') ≠reachdistk (o'←o) 。

定义3局部可达密度数据点o的局部可达密度ldrk (o) 为

定义4局部离群因子数据点o的局部可达密度LOFk (o) 为

LOF算法就是根据给定的k值, 计算所有数据点的LOFk (o) , LOFk (o) 较大的点就是离群点。

3距离加权策略

从上述描述可以看出, 数据点的离群因子主要由两个因素决定, 一是k值的选取, 二是距离的度量, k值的选取通常取决于具体的应用环境, 本文主要探究距离的度量, 研究具体每个维度对两个对象的差异起到了多大的影响, 为每个维度赋予相应的权值。

3.1标称属性加权策略

x= (x1, x2, …, xm) , y= (y1, y2, …, ym) 为m维数据集D中的两个数据点, attr为属性集, attr中所有的属性都是标称属性, 那么可以定义x和y之间的距离d (x, y) 为:, wi为权重, qi为x和y在第i维的差异, 。wi的确定需要注意, 现在常见的做法是将每个属性同等看待, 这样显然是不科学的, 因为每个维度对于两点之间实际距离的贡献是不同的。

根据属性在所有数据点上的取值情况, 计算属性的信息熵, 熵的计算方法如下:

设属性A有n个取值, dom (A) ={A1, A2, …, An}, p (Ai) 表示取第i个值的概率, 属性A的信息熵信息熵反映了数据分布的混乱程度, 熵越大, 数据的分布越不规律。文献[8]指出从信息熵角度考虑, 离群点的存在使得数据集的不确定性增强, 而离群点所表现出的不确定性正是通过其在某些属性上的取值分布造成的。熵值较大的属性有可能正是由于离群点在该属性上引起的混乱造成的, 应该特别关注, 因此, 在计算距离时应该突出熵值较大的属性上的差异, 也就是赋予其较大的权值, 由此可以对wi进行量化, 。后续的实验证明了为每个属性赋予wi的权重提高了LOF算法离群点检测的准确率。

3.2数值属性加权策略

对于数值属性, 为了排除量纲的影响, 必须先进行数据的规范化。数据规范化的方法主要包括最小-最大规范化、z分数规范化以及小数定标规范化, 最小-最大规范化易受离群点的影响而使数据失真, 因此选用z分数规范化方法。属性A的取值vi经标准化处理以后变为vi', , μA为属性A取值的均值, 为了增强鲁棒性, sA取A的均值绝对偏差, 即

x= (x1, x2, …, xm) , y= (y1, y2, …, ym) 为m维数据集D中的两个数据点, attr为属性集, attr中所有的属性都是数值属性, 那么可以定义x和y之间的距离d (x, y) 为:, wi为权重, 继续使用标称属性加权的思路, 对于分布比较混乱的属性应重点关注, 但连续属性需要离散化才能求熵, 为此, 引入另外一种数据分布离散程度的度量指标—标准差。属性A的标准差, 在σA的基础上得到

3.3混合属性加权策略

在现实世界中, 许多数据集都是既包含标称属性, 又包含数值属性, 因此混合属性条件下的离群点检测研究也是非常重要的。对混合属性数据集的距离度量是在分别处理标称属性和数值属性的基础上综合加权。

设D为m+n维混合属性数据集, c Attr为标称属性的集合, ‖c Attr‖=m, n Attr为数值属性的集合, ‖n Attr‖=n, Entropies={e1, e2, …, em}为c Attr中属性的信息熵的集合, Deviations={d1, d2, …, dn}为n Attr中属性标准差的集合。根据上述假设, 给出数据集D上各属性的权重

使用此权重计算两数据点x和y的距离, , qi的计算方法同3.1节。

4算法复杂度分析

提出的加权策略比LOF需要额外的计算开销, 计算权值需要对数据集进行一次扫描, 增加的时间复杂度为o (N) , N为数据集的规模, 而LOF本来的复杂度为o (N2) , 所以用提出加权策略的时间复杂度为o (N) +o (N2) ≈o (N2) , 因此因加权引起的时间开销增加是可以接受的, 不会影响算法整体的复杂度。

5实验分析

为验证所提加权策略的有效性, 仿真实验分三步进行, 第一步在标称属性数据集上验证基于信息熵加权的有效性, 第二步在数值属性数据集上检验基于标准差加权的有效性, 第三步在混合属性数据集上研究综合加权的有效性。

5.1实验1

本实验在UCI Mushroom数据集上验证基于信息熵加权的有效性。Mushroom数据集共包含8 124条记录, 22个标称属性, 1个类别属性用来标记Mushroom是否有毒。本实验随机选取1 000条有毒Mushroom记录作为正常数据, 10条可食用Mushroom作为离群点, 分别用经典LOF算法以及本文提出的基于加权距离的LOF (以下简称WLOF) 算法进行离群点检测, 实验结果如图2所示。

5.2实验2

本实验在UCI Ecoli数据集上验证基于标准差加权的有效性。Ecoli数据集共包含336条记录, 7个数值属性, 1个类别属性。本文选取标号为“cp”的143条记录作为正常数据, 标号为“om L”、“im L”和“im S”的共9条记录作为离群点, 分别用LOF和WLOF进行检测, 为了说明数据规范化的必要性, 还是用未规范化的数据进行了检测, 用ULOF标记, 实验结果如图3所示。

5.3实验3

本实验选取UCI Statlog (Heart) 数据集来验证综合加权算法的有效性。Statlog数据集共包含270条记录, 6个数值属性, 7个标称属性, 1个类别属性。本实验选取标号为“1”的150条数据作为正常数据, 标号为“2”的10条数据作为离群点, 分别用LOF和WLOF进行检测, 实验结果如图4所示。

5.4实验分析

上述三个实验分别用标称属性数据集、数值属性数据集和混合属性数据集验证了所提的加权策略, 从结果的对比可以看出本文加权策略的有效性。实验1中k取任何值时WLOF的检测准确率都要大于或等于LOF, 因为对不同属性的加权可以使离群点的离群特性更加明显;实验2中虽然三种方法随着k的增长, 效果趋于相同, 但在k比较小时WLOF的效果还是要明显好于LOF和ULOF, ULOF的效果较差的原因是由于数据没有进行规范化, 这样在计算距离时可能会发生取值较大的属性覆盖了取值较小的属性之间的偏差;实验3在k=15和k=17时LOF的准确率高于WLOF;但随着k的增长, WLOF的检测准确率明显高于LOF。

6结束语

离群点检测过程需要用到数据点之间的距离度量, 本文提出了一种距离度量时的属性加权策略, 通过加权突出不同属性对数据点之间距离的贡献的不同, 使离群点与正常数据之间的区别更加显著, 仿真实验验证了加权策略的有效性。

参考文献

[1] Hawkins D.Identification of outliers.London:Chapman&Hall, 1980

[2] Han Jiawei, Kamber M, Pei Jian.Data Mining:Concepts and Techniques (third edition) .范明, 孟小峰, 译.北京:机械工业出版社, 2012:351—375Han Jiawei, Kamber M, Pei Juan Data Mininy:Concepts and Techniques (third edition) .Fan Ming, Meny Xiaofeng, transtated.Beijing:China Machine Press, 2012:351—375

[3] Rousseeuw P J, Hubert M.Robust statistics for outlier detection.Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery, 2011;1 (1) :73—79

[4] Eskin E.Anomaly detection over noisy data using learned probability distributions.Proceedings of the Int.Conf on Machine Learning, Stanford University, 2000:255—262

[5] Latecki L J, Lazarevic A, Pokrajac D.Outlier detection with kernel density functions.MLDM, 2007;4571:61—75

[6] Breunig M M, Kriegel H P, Ng R, et al.LOF:identifying densitybased local outliers.ACM SIGMOD Int Conf Management of Data, 2000:93—104

[7] Jin W, Tung A K H, Han J, et al.Ranking outliers using symmetric neighborhood relationship.Knowledge Discovery and Data Mining (PAKDD'06) , Singapore, 2006:577—593

[8] 胡彩平, 秦小麟.一种基于密度的局部离群点检测算法DLOF.计算机研究与发展, 2010;47 (12) :2110—2116Hu C P, Qin X L.A Density-based local outlier detecting algorithm.Journal of Computer Research and Development, 2010;47 (12) :2110—2116

[9] 王敬华, 赵新想, 张国燕, 等.NLOF:一种新的基于密度的局部离群点检测算法.计算机科学, 2013;40 (8) :181—185Wang J H, Zhao X X, Zhang G Y, et al.NLOF:a new density-based local outlier detecting algorithm.Computer Science, 2013;40 (8) :181 —185

[10] Ke Zhang, Hutter M, Jin Huidong.A new local distance-based outlier detection approach for scattered real-world data.Advances in Knowledge Discovery and Data Mining, 2009; (5476) :813—822

[11] Babu S, Widom J.Continuous queries over data streams.SIGMOD Record, 2001; (30) :109—120

基于熵距离的离群点检测及其应用 篇5

离群点检测问题是数据挖掘技术的重要研究领域之一,被广泛应用于网络入侵抵御和信用卡恶意透支检测等风险控制领域。与关联规则发现和分类与聚类分析等数据挖掘任务所关注的数据对象不同,离群点检测的任务是从大量复杂的数据集中发现存在于小部分异常数据中新颖的、与常规数据模式显著不同的新数据模式。例如,在学生评教工作,评教效果不仅仅依赖于学生的评教水平,更依赖于学生对教师的态度。如果学生存在偏见,必然会扭曲评教结果,因而会出现故意抬高或压低评分现象,从而出现评教的离群数据。在学生评教过程中,应该找出这些离群数据并加以清除,以提高学生评教数据的正确性。因此,对于离群点检测方法的研究具有重要意义。

1 相关工作

离群点检测技术由于其独特的知识发现功能而得到较深入的研究,目前已经存在许多离群数据点的检测方法[1,2,3,4,5],这些方法可以分为3类:

① 基于统计的离群数据点检测。该方法是假设数据集合满足一个已知的分布或者概论模型,采用不一致性来检测离群点。

② 基于距离的离群数据点检测。该方法认为,如果一个点与数据集中大多数点之间的距离都大于某个阈值,它就是一个离群点。如在某个数据集合S中至少有P部分数据与数据Q的距离大于某个值d时,则认为数据Q是一个离群点。该方法不足之处是比较难确定基准值和距离,因而也常常对数据判断失误。

③ 基于偏离的离群数据点检测。该方法是根据数据集的主要特征来判断离群点,如果某个数据点偏离了这个数据特征,则认为是离群点。该方法思路不错,但对于数据集的特征很难把握,因而常常出现对数据的误判。

一个离群数据点检测方法选择是否合理取决于要处理的数据特征,学生评教的噪声数据比正常数据值可能偏高,也可能偏低,一般来说偏高的噪声数据与真实数据距离要小于偏低噪声数据与真实数据的距离,这样,基于距离的离群数据点检测不能有效地检测出这些噪声数据。引入数据的熵值,提出一个基于熵值距离的离群数据点检测方法,仿真实验表明,该方法能有效地检测出学生评教中的噪声数据。

离群点检测算法可以描述为:计算数据集D中每个数据点的离群因子Da,将其按从大到小降序排列,离群因子最高的前n个点就是所求的离群点,即Top(n)离群点。要得到Top(n)离群点,需要计算每个点的离群因子Da(e),相应地需要计算每个点与数据集中其它点之间的距离以搜索该点的k个最近邻,导致o(N2)的时间复杂度。因此提高算法效率的关键在于减少k近邻搜索时数据点之间距离计算的次数。

依据上述分析提出的离群点检测算法分为2个阶段:第1阶段对数据集进行聚类,采用启发式规则估计每个簇包含离群点的可能性,按可能性从大到小进行排序;第2阶段在聚类的结果上采用熵值距离实现离群点检测,并通过2个剪枝规则进行高效剪枝,提高了算法的效率。

1.1 数据集的聚类

这一阶段的目的是对数据集进行快速的大致聚类,不寻求最优聚类效果,算法的效率是关键因素。这里采用层次聚类和k-means混合的层次k-means算法。算法整体上是自顶向下的分裂层次聚类,在每一层次簇的分裂过程中,采用k-means算法将选定的簇划分为2个子簇(k取值为2)。具体算法为:

步骤1:首先从数据集中随机选取2个点,每个点作为一个簇的初始均值或中心。对于剩余的每一个数据点,根据其与各个簇均值的距离,将其指派到最近的簇,然后重新计算每个簇的均值。这个过程不断重复,直到簇中心不再发生变化,这样就将数据集分解成2个簇,加入簇表中。

步骤2:从簇表中选出一个包含成员个数最多的簇C,利用k-means方法二分簇C为C1和C2;

步骤3:将C1和C2加入簇表中;

步骤4:重复步骤2和步骤3,直到簇表中簇的个数达到指定的个数NC为止。以N表示数据集大小,则分裂停止时的簇个数NC通过式(1)指定:

NC=max(2,N/100)。 (1)

对于得到的簇集合SC={C1,C2,…,CNc},用$\left|\mathit{S}{}_C\right|$表示簇中元素的个数。簇在特征空间中的尺寸,用簇半径RC来表示。簇半径是簇的中心到该簇中最远的点之间的距离。基于聚类的离群点检测算法通常将小簇指定为离群簇,直观的想法是离群点极可能包含在元素个数少的簇中;另一方面,尺寸大的簇有可能密度较低,导致其中元素的k邻域较为稀疏,包含离群点的可能性较大。将这2个因素综合起来,则一个簇包含离群点的可能性大小P可以表示为:

${\rm P}=\frac{R{}_C}{\left|\mathit{S}{}_C\right|}$。 (2)

对于后续的基于熵值距离的离群点检测,如果先取P值最大簇中的点计算离群因子,就会使得剪枝阈值T快速增大,提高剪枝效率。因此,这一阶段应用如下的启发式规则:聚类算法将数据集划分为NC个簇后,按P值从大到小进行排序。假设排序后的结果为P(C1)≥P(C2)≥……≥P(CNC),排序后的簇传递给第2阶段。

1.2 基于熵值距离的离群点检测方法

在得到数据集的分簇结果之后,下面基于熵值距离来进行离群点的检测,考虑到在搜索每个数据的k个最近邻的过程中,如果能尽可能早地确定其为非离群点,就可以立即中断最近邻搜索,节省距离计算。因此定义了2条剪枝规则来实现对正常数据的高效剪枝,减少k近邻搜索时距离计算的次数。下面给出了信息熵、剪枝规则的定义,提出了改进的离群点检测算法。

1.2.1 信息熵与剪枝规则

熵常常用来表示一个系统的有序程度[8]。一个系统的熵值越小,表示它所处的状态越是有序,系统的熵值越大,则表明系统所处的状态越是无序。学生评教数据如果出现噪声数据越多,那么表示这些数据越无序,系统的熵值就越大。反之,如果噪声数据越少,则表示数据越有序,系统的熵值就越小。采用信息熵来判断噪声数据是基于这样的假设:学生评教的正常数据对某个教师的评价结果是一致的。如果这些数据一致性较好,说明学生评教数据中噪声数据较少,熵值就越大,如果数据的一致性差,则说明噪声数据较多,熵值就越小。因此可以通过求信息熵值来判断噪声数据。

定义1,熵:如果系统可能处于多个不同的状态,每种状态出现的概率为pi(i=1,2,…,m),则系统的熵为:

${\rm H}=-k{\displaystyle \sum _{i=1}^{m}p}{}_i\ln p{}_i$。 (3)

式中,k为系数,为保证Hj的值在0和1之间,可以取:$k=\frac{1}{\text{l}\text{n}n}$。

式(3)中定义的熵具有如下的性质:

① 非负性。熵大于或者等于零(规定:pi=0,则pilnpi定义为0)。

② 可加性。熵具有概率性质,系统的熵等于各个状态的熵之和。

③ 对称性。系统的熵与其状态出现概率的排列次序无关。

④ 极值性。当系统的状态概率为等概率时,即当所有的pi(i=1,2,…,m)都相等时,熵值达到最大。当且仅当pi(i=1,2,…,m)中的一个等于1时,熵为零。

⑤ 加法性。2个独立的系统,复合起来的熵等于2个系统的熵值之和。

定义2,剪枝规则1:如果Da(e)≤T,点e被修剪而无需进行k近邻搜索。

定义3,剪枝规则2:对e进行k近邻搜索过程中,假设取q与e计算距离以检查是否为近邻,又假设q已经计算过Da(q)值,则可以利用Da(q)和三角不等式计算Da(e)的上界。如果该上界值小于T,则对象e被修剪而无需进行k近邻搜索。限于篇幅,规则2的推导过程在此略去。

1.2.2 基于熵值距离的离群点检测算法

存在噪声数据的熵值与不存在噪声数据的熵值不同。因而可以通过比较不同数据集熵值的距离来检测噪声数据。假设排序后的某一簇C1种的数据集为D=(a1,a2,…an),其熵值为H(D),去掉数据a1后的数据集表示为D1,去掉数据aj后的数据集表示为Dj,数据集Dj的熵值表示为H(Dj)。那么去掉某个数据后2个熵值之间的距离可以定义为:

$d=\left|{\rm H}(\mathit{D})-{\rm H}(\mathit{D}{}_j)\right|(\max -\min )$。 (4)

式中,max为数据集中的最大值;min为数据集中的最小值。

离群数据点检测算法计算除去每一个数据后数据集的熵值,并计算其值与整个数据集熵值的距离,再根据偏离程度判断评教数据是否为噪声数据。算法步骤如下:

输入:排序后的簇集合SC,最近邻个数k;

输出:离群点集合;

步骤1:初始化,剪枝阈值T设为0,离群点集合为空集;

步骤2:检测P值较大的簇,对于SC中的P(C1)对应的数据集D中的数据点,计算每个数据点的熵值距离

For每个数据点j

计算除去该数据点后数据集的熵值H(Dj)

数据点j的熵值距离为:

$d=\left|{\rm H}(\mathit{D})-{\rm H}(\mathit{D}{}_j)\right|(\max -\min )$

End for

步骤3:如果d大于阈值W,则输出离群点;

步骤4:迭代执行,当阈值T增大到某一规定值时,则采用剪枝规则1和规则2来中断搜索过程。

2 仿真实验与分析

通过实验对算法的效率进行测试分析。实验平台为P4 1.8 GHz的CPU,1 G内存的计算机,操作系统为Windows XP。为了检验基于熵值距离的离群数据点检测效果,随机产生600份对某教师的评教数据,选取该教师的评价分数为0.85,学生评教数据的正常值在(0.85-0.05,0.85+0.03)之间随机生成,偏见评教数据在这个数据范围之外随机选取。比较采用基于熵值距离的离群数据点检测方法和没有采取数据过滤方法的效果比较图如图1所示。

从图1中可用看到,当学生中不存在偏见时,二者的评估结果准确率一样,都是1;当带有偏见数据的比例达到10%时,无数据过滤方式统计数据的准确度明显降低,只有约90%的准确度,而采用偏见数据过滤方法的评教结果的准确度达到98%。随着评教偏见数据比例增加,没有数据过滤方式的评教效果显著下降,完全失去评教意义;而采用偏见数据过滤方法的评教效果下降缓慢。总之,该方法是有效的,能够达到较好的检测效果。

3 结束语

提出了一种改进的离群点检测算法,该算法能够很好地应用到对学生评教数据的处理中,能够有效地检测出评教数据中的异常,提高评教工作的效率和意义。下一步工作是基于局部信息熵的思想来设计更加高效的离群数据检测算法,提高算法的普适性。

参考文献

[1]ANGIULLI F,PIZZUTI C.Outlier Mining in Large High-di-mensional Data Sets[J].IEEE Transactions on Knowledgeand Data Engineering,2005,17(2):203-215.

[2]陈光平,叶东毅.一种改进的离群点检测方法[J].福州大学学报(自然科学版),2007,35(3):376-380.

[3]倪巍伟,陈耿,陆介平,等.基于局部信息熵的加权子空间离群点检测算法[J].计算机研究与发展,2008,45(7):1 189-1 192.

[4]孙金花,胡健,李向阳.基于分形理论的离群点检测[J].计算机工程,2011,37(3):33-35.

[5]杨宜东,孙志挥,朱玉金,等.基于动态网格的数据流离群点快速检测算法[J].软件学报,2006,17(8):1 798-1 803.

离群点挖掘 篇6

关键词：数据挖掘,离群数据,单元格,属性权重,粗糙集

0 引 言

“一个离群点是一个观察点,它偏离其它观察点如此之大以至引起怀疑是由不同机制生成的”[1,14]。离群点检测是数据挖掘的基本任务之一[14],其主要目的是消除数据中的噪音或发现其潜在的、有意义的知识,在电信和信用卡欺诈的侦查、网络入侵检测、气象预报、电子商务和金融服务中的欺诈监测等领域中被广泛应用。现有的离群点检测算法主要分为以下几类:

1) 基于统计分布的方法[2,8] 基于分布的方法是比较常见的,其假设所给定的数据集满足的分布是已知的,即数据集满足某个分布或者概率模型,然后再根据分布模型对数据集中的每个数据采用不一致性检验来确定离群点。它的缺点比较明显,主要有:大多数分布模型只能对单变量分布进行测试,不适用于多维的数据空间;在对数据集进行检测前需要知道数据集的分布模型,对于分布未知的数据集往往需要进行耗时的测试来决定其分布模型,这种情况下代价太大,而且也不一定获得满意的结果。

2) 基于深度的方法[9] 基于深度的方法是给每个数据对象分配一个深度值,将数据对象按分配的深度值映射到二维空间的相应层上,处在浅层上的数据对象比深层上的更有可能是离群点[9,13]。这个算法对四维以下的数据比较有效,对四维和超过四维的数据,处理效率相对比较低。

3) 基于距离的方法[2,12] 基于距离的离群点概念是由Knorr和Ng提出的。如果数据集合D中对象至少有pct部分与对象O的距离大于dmin,则称对象O是pct和为dmin参数的基于距离的离群点,即DB(pct,dmin)离群点[2]。该算法的时间复杂度为O(dn2),其中d为数据的维数,n为数据集中数据对象的总个数。但是该算法对于高维数据空间的稀疏问题没有进行根本解决,并且用户需要设置参数pct和dmin的值。

4) 基于密度的方法[2,11] 基于密度的离群点定义是在距离的基础上建立起来的,将点之间的距离和给定范围内点的个数这两个参数结合起来得到“密度”的概念[7]。其他的方法对离群点的定义都是二值的(具有0、1属性),即:要么是离群点,要么不是离群点,不存在中间状态。该算法提出了局部离群点和基于密度的离群点定义,专门引入了一个度量单位局部离群因子(LOF)来表征一个对象的局部离散的程度。基于密度的离群点检测对于密度不同的区域也能很好地处理。但是仍然有O(δn2)的时间复杂度,其中δ为邻居数,n为数据点总数,并且参数选择比较困难。

5) 基于聚类的方法[10] 该方法先对数据集聚类,然后剩下的数据点就是离群点。该方法可以充分利用聚类现有的研究成果。因为通常簇和离群点的定义是互补的,所以该方法能同时发现簇和离群点。但是该方法仍有其局限性:因为该方法的主要目标是发现簇,所以对离群点的挖掘效率较低;算法针对性强,不同的算法可能采用了不同的方法;依赖数据集中簇的个数和数据中离群点的存在性。

6) 基于偏差的方法[2,15] 基于偏差的离群点挖掘不使用统计检验或基于距离的度量来识别异常对象,而是通过检测一组对象的主要特征来识别离群点。不符合这种描述的数据对象被认为是离群点。它分为顺序异常技术和OLAP数据立方体技术两种方法。

文献[3]中的FORMAUC算法基于网格和密度两种思想,虽然能有效提高算法效率和准确度,但是没有考虑属性之间的重要性的差别。本文吸取了文献[3]的单元格和文献[4]的属性权重的思想,提出了一种新的基于单元格的算法。

1 算法介绍

1.1 基本概念

定义1 将一个m维的空间S划分成m面体,第i维被划分成Si段,每段长为Li,那么,该空间就被划分为S1×S2×…×Sm个区域,这样的每个区域称为单元,记为U=(u1,u2,…,um),1≤ui≤Si。

定义2 在m维的空间S中有一点d=(di,d2,…,dm),若点d属于单元u,p=(p1,p2,…,pm)当且仅当(pi-1)×Li<pi×Li,(1≤i≤m)。记为d∈u。单元u内数据的集合记为S(u),u内数据的个数称为单元的密度,记为|S(u)|。

定义3 若一单元u的密度超过某一给定的阈值Minpts,即|S(u)|≥Minpts成立时,则单元u是密集单元,记为UD,反之单元u为稀疏单元,记为US。

定义4 若单元 U1.p=(p11,p12,…,p1m) ,U2.p=(p21,p22,…,p2m)

满足下式:

$\{\begin{array}{l}p{}_{1i}-p{}_{2i}\in \{-1,0,1\}\\ {\displaystyle \sum _{i=1}^m|}p{}_{1i}-p{}_{2i}|>0\end{array}i=1,2,\cdots ,m$

则称U1、U2互为邻居。

1.2 算法思路

将单元定义为一个三元组U[P,D,S],其中:P=(p1,p2,…,pm)描述了单位的位置;D描述了单元的密度,也就是单元内数据的个数;S是单元内的数据集。

本文算法思想如下:

1) 数据预处理

① 对整个论域[4]进行信息粒度化;

② 用粗糙集理论[4,5,6]进行降维得到约简的属性集合core(A);

③ 确定数据集中每个属性的最终权重wi;

④ 计算每个属性对应的单元的边长Li。

2) 粗选

① 将每个单元的密度D初始为零,S置为空,然后将数据集的数据映射到单元内,f(d(d1,d2,…,dm))→U,该函数映射定义为:

$\{\begin{array}{l}U.p{}_i=\left[\frac{d{}_j}{L{}_j}\right]+1\\ U.D=U.D+1\\ U.S=U.S+\{d\}\end{array}$

其中:1≤i≤Si,1≤j≤m。

② 处理每个单元:若U.D≥Minpts,那么单元内的数据不是离群数据;否则,将单元内的数据暂时标记为离群数据。

3) 精选

这一步主要针对粗选过程中暂时标为离群数据的稀疏单元,处理方法如下:

① 若稀疏单元U的邻居都是空单元,那么该稀疏单元内的数据为离群数据。

② 若稀疏单元U存在非空邻居单元,对于稀疏单元里的数据d来说,从该单元及邻居里查找满足如下条件的数据d:

|dj-d′j|≤Lj 1≤j≤m

由这些数据组成的集合为Set,再从该集合里查找满足下列条件的最大子集合Set:

|Set′[p].di-Set′[q].di|≤Li ∀i∈[1,m]

若Set中数据点的个数大于或等于Minpts,则数据点d就不是离群数据,因为满足上述条件,说明存在一个覆盖数据点d的密集单元。否则,d就是离群数据。

1.3 权重wi的确定

为了减小误差,采取客观权重和主观权重相结合的策略:

wi=pi×u+qi×(1-u)

其中pi是每个属性的客观权重,qi是每个属性的主观权重,u为偏好系数,一般0.5<u<1.0。

客观权重pi的求法如下:

Oi=SGFcore(A)(ai) ai∈core(A)[4]

$p{}_i=\frac{{\rm O}{}_i}{{\displaystyle \sum _{j=1}^m{\rm O}}{}_j}m$为core(A)的维度

qi一般由领域内的专家提供。

1.4 单元格边长Li的确定

基本思想是以最接近平均权重的一维作标准,计算单元格各维对应的边长。

定义平均权重:

$\overline{w}=\frac{{\displaystyle \sum _{i=1}^{m}w}{}_i}{m}m$为core(A)的维度

定义离差:

$\overline{p{}_i}=w{}_i-\overline{w}$

取离差最小的一维作为基准,假如是第j维,L是FORMAUC的参数取值,此时各维对应的边长可通过下式进行计算:

$L{}_j=L\times \frac{w{}_j}{w{}_i}(1\le i\le m)$ (1)

2 算法分析

2.1 效率分析

该算法由于通过粗糙集理论对数据进行降维处理,因而比FORMAUC算法多进行一次扫描。设数据集中数据量为N,稀疏单元的个数为s,稀疏单元的邻居个数为n,稀疏单元内的数据个数为c,则该算法的时间复杂度为:O(2N+s×n×c×log(s×n×c))。本算法与FORMAUC算法复杂度相当,但对于高维数据,尤其是高维稀疏数据,因为进行了降维,所以比FORMAUC算法运行效率高。

2.2 质量分析

数据的各个属性对于具体的聚类分析的重要程度是不一样的,所以需要区别对待这些属性。FORMAUC算法并没有考虑属性的重要程度的差异,而是将它们平等对待,因此将单元格的各边划为等长。本文的改进算法对单元格的划分是依据属性的重要性划分的,属性越重要,相应地该维的边长越长。

如图1,用FORMAUC算法对下列数据集进行离群点挖掘,此时,L取10,Minpts取4,共挖掘出3个离群点。但是如果y维的属性相对重要,此时赋予y维较高的权重,假设经过计算得,Lx=10,Ly=15,如图2,本文算法共挖掘出1个离群点,图1中的另外两个离群点不作离群点处理,所以准确度有了很大提高。

3 实验分析

实验中算法采用C++语言编写,机器配置为Intel T5250 1.50GHz、1G内存,Windows XP系统。实验对FOMAUC和本文的改进算法进行了比较。

测试数据集采用KDD-CUP98数据集,该数据集记录的是慈善捐赠的信息,共有95412条记录,每条记录有481维。

3.1 挖掘速度比较

在实验中,FORMAUC算法中取Minpts=4,L=4;为了与FORMAUC算法具有可比性,在本文算法中,取Minpts=4,L=4,Li根据式(1)确定。为直观清晰起见,运行时间取整。如表1和表2所示,在维数较低(2维和10维)的情况下,本文算法不如FORMAUC运行效率高;随着维度的增加,本文算法运行效率高于FORMAUC算法。之所以有这样的结果是因为本文算法预先进行了降维,需要对数据集多扫描一遍,所以在低维度的情况下,降维的优势没有表现出来,随着维度的增加,降维的效果逐渐显现出来。实验数据证明本文算法对于高维数据有更好的延展性。

3.2 挖掘质量比较

在这个比较实验中,数据量取3000,其他参数与3.1节实验相同,然后在不同维度下进行了准确度的比较。由图3可知,随着维度的增加,FORMAUC准确度随着降低,而本文算法准确度始终高于FORMAUC算法,准确度虽然有所降低,但是曲线比较平缓。这同样说明本文算法对高维数据有更好的延展性。

4 结 语

本文提出了一种基于单元格的离群点挖掘算法。实验结果表明,本文算法通过模糊集的降维和对单元格边长的加权处理,能有效改进算法的运行效率和运行质量,对高维数据有更好的延展性。但是算法仍然需要用户设置参数L和Minpts。下一步的研究方向为:拟采用参数自适应的方法自动确定Li和Minpts的大小,以避免人机交互的过程,使算法的可操作性、可使用性更强。

离群点挖掘 篇7

离群点检测是数据挖掘技术的重要研究领域之一,用来发现数据集中明显偏离于其他数据、不满足数据的一般行为或模式的数据[1]。这些数据对象叫做离群点,也叫做孤立点。离群点检测算法分为基于统计、深度、聚类、距离和密度的方法[2]。其中,基于距离的方法由于算法思想直观,易于实现而得到了广泛的研究和应用。

基于距离的方法大致分为嵌套循环的算法、基于索引的算法和基于单元的算法。但这些方法在处理大规模数据集时都存在性能上的不足。嵌套循环算法通过循环扫描数据集为各样本寻找近邻,复杂度为O(N2×d)(其中N为数据集中对象个数,d为数据的维数)[3]。基于索引的算法通过建立多维索引结构为各样本寻找近邻,最坏情况下的复杂度为O(N2×d)。但在大数据集上建立索引的开销很大,而且随着维数的增大,索引的性能急剧下降,性能不如简单的顺序扫描[4]。基于单元的算法的复杂度与N呈线性关系,但与d呈指数关系,因此很难处理高维数据。

利用嵌套循环算法对维数不敏感,针对其在大数据集上效率低下的问题,本文提出基于聚类和距离的混合离群检测算法(Clustering and Distance-based Outlier Detection,CDOD)。算法首先对数据集进行聚类,将得到的簇按照包含离群点的可能性大小排序,然后对排序后的簇中的数据进行基于距离的离群点检测。实验结果验证了算法的可行性和有效性。

1 相关概念与定义

对于d维空间中的数据点p=(p1,p2,…,pd)和q=(q1,q2,…,qd),通常采用欧式距离度量它们之间的相似性。

Ramaswamy用点p和它的第k个最近邻的距离来度量p的离群程度,记为Dk(p)[5]。Angiulli用权重wk(p)表示对象p与其k个最近邻居的距离之和[6]。显然wk(p)比Dk(p)更精确地度量了p的邻域的稀疏程度。本文在wk(p)的基础之上定义了度量数据点离群程度的离群因子。

定义1(点p的离群因子)对于数据集D,给定参数k和p∈D,则点p的离群因子定义为p与其k个最近邻对象的平均距离:

其中,k NN(p)表示p在D中的k个最近邻元素的集合。Da(p)越大,表示p越远离k-邻域内的近邻,成为离群点的可能性越大。

离群点检测算法可以描述为:计算数据集D中每个数据点的离群因子Da,将其按从大到小降序排列,离群因子最高的前n个点就是所求的离群点,即Top-n离群点。

要得到Top-n离群点,需要计算每个点的离群因子Da(p),相应地需要计算每个点与数据集中其它点之间的距离以搜索该点的k个最近邻,导致O(N2)的时间复杂度。因此提高算法效率的关键在于减少k近邻搜索时数据点之间距离计算的次数。

减少距离计算的主要思想是:对于占数据集绝大多数的正常数据,在搜索每个数据的k个最近邻的过程中,如果能尽可能早地确定其为非离群点,就可以立即中断最近邻搜索,节省距离计算。这一过程称为近似最近邻搜索。其实现方法是:取当前已得到的n个离群点中的Da值的最小值作为剪枝阈值,记为Omin。该值随着已检查数据集的增大而单调递增。而根据点p当前的k个最近邻计算得到的Da(p)值随着新的近邻点的发现而单调递减。因此如果当前的Da(p)

2 CDOD算法

CDOD算法综合了基于聚类和基于距离的方法的特点,并使用一个启发式规则和两个剪枝规则来提高算法的效率。该算法第一阶段对数据集进行聚类,然后采用启发式规则估计每个簇包含离群点的可能性,按可能性从大到小进行排序。第二阶段在聚类的结果上采用嵌套循环算法实现离群点检测,并通过两个剪枝规则进行高效剪枝,提高了算法的效率。

1)第一阶段

这一阶段的目的是对数据集进行快速的大致聚类,不寻求最优聚类效果,算法的效率是关键因素。

本文采用层次聚类和k-means混合的层次k-means算法。该算法整体上是自顶向下的分裂层次聚类,在每一层次的簇的分裂过程中,采用k-means算法将选定的簇划分为2个子簇(k取值为2)。其具体算法为:

(1)首先从数据集中随机选取2个点,每个点作为一个簇的初始均值或中心。对于剩余的每一个数据点,根据其与各个簇均值的距离,将其指派到最近的簇。然后重新计算每个簇的均值。这个过程不断重复,直到簇中心不再发生变化,这样就将数据集分解成2个簇,加入簇表中;

(2)从簇表中选出一个包含成员个数最多的簇C;

(3)利用k-means方法二分簇C为C1和C2;

(4)将C1和C2加入簇表中;

(5)重复步骤(2)~(4),直到簇表中簇的个数达到指定的个数Nc为止。以N表示数据集大小,则分裂停止时的簇个数Nc通过以下经验公式指定:

对于得到的簇集合LC={C1,C2,…,CNc},用|Ci|表示簇中元素的个数。簇在特征空间中的尺寸,用簇半径RCi大致表示。簇半径是簇的中心到该簇中最远的点之间的距离。基于聚类的离群点检测算法通常将小簇(即|Ci|小的簇)指定为离群簇[7],直观的想法是离群点极可能包含在元素个数少的簇中。另一方面,尺寸大的簇有可能密度较低,导致其中元素的k-邻域较为稀疏,包含离群点的可能性较大。将这两个因素综合起来,用一个指标来估计一个簇包含离群点的可能性大小(Outlying Degree of a Cluster),表示为ODC=RCi/|Ci|。

对于后续的基于距离的离群点检测,如果先取ODC值最大的簇中的点计算离群因子,就会使得剪枝阈值Omin快速增大,提高剪枝效率。因此,这一阶段应用如下的启发式规则:聚类算法将数据集划分为Nc个簇后,按ODC值从大到小进行排序。假设排序后的结果为ODC(C1)≥ODC(C2)≥…≥ODC(CNc),排序后的簇传递给第二阶段。

2)第二阶段

这一阶段改进了传统的嵌套循环算法,在其基础之上增加了两个剪枝规则[8]。

规则1:如果Da(p)

规则2:对p进行k近邻搜索过程中,假设取q与p计算距离以检查是否为近邻,又假设q已经计算过Da(q)值,则可以利用Da(q)和三角不等式计算Da(p)的上界。如果该上界值小于Omin,则对象p被修剪而无需进行k近邻搜索。

规则2推导如下:假设已计算对象q的离群因子Da(q)。对p进行k近邻搜索时,取q与p计算距离以检查是否为近邻。点p,q和q的k个最近邻之间形成k个三角形。根据三角不等式有:

(4)式两边同除k,得到:

q的k个最近邻不一定是p的k个最近邻,因此有:

根据式(5)和(6)得到:

这样就得到Da(p)值的上界。如果该上界小于剪枝阈值Omin,即式(8)成立,说明p不可能是离群点而无需再进k近邻搜索。

按第一阶段的启发式规则排序后的簇传递给这一阶段。嵌套循环算法依次从C1到CNc检测离群点。因为首先检测ODC值大的簇中的点,导致剪枝阈值Omin迅速增大,因此对于占数据集绝大多数的正常数据,就会因为剪枝规则1和2的作用,不必精确获得对象的k个最近邻,就可以确定其为非离群点而中断k近邻搜索,减少对象间距离计算的次数。阈值Omin增大越快,内循环k近邻搜索时的剪枝效率越高。

算法1改进的嵌套循环离群点检测算法

输入:排序后的簇集合LC,最近邻个数k,离群点个数n

输出:离群点集合Outliers

(1)初始化剪枝阈值Omin←0,Outliers←

(2)for each C in LC

(3)for each p in C

(4)p的最近邻集合NN(p)←

(5)for each C in LC

(6)for each q in C,q≠p

(7)if dist(p,q)

(8)goto(3)

(10)if|NN(p)|

(11)NN(p)=Neighbors(p,NN(p)∪q,k)

(13)if|NN(p)|=k and Da(p)

(14)goto(3)

(16)end for

(17)end for

(18)Outliers=Top Outliers(Outliers∪p,n)

(19)Omin=Min(Da(s)for all s in Outliers)

(20)end for

(21)end for

其中,函数Maxdist(x,S)返回x与集合S中的对象之间的最大距离。函数Neighbors(x,S,k)返回集合S中关于x的k个最近邻。函数Top Outliers(S,n)返回集合S中Da值最大的前n个对象。

3 算法分析与实验结果

3.1 算法复杂度分析

k-means算法的时间复杂度为O(Nkt),其中N是数据的总数,k是簇的个数,t是迭代次数,通常有k,t≪N,因此算法的效率很高。CDOD算法第一阶段的层次k-means算法的步骤(1)~(4)实质是k值为2的k-means算法。在决定将数据划分到某个簇时,只需要与2个均值点计算距离。在步骤(5)中迭代调用前面的步骤(2)~(4)直到簇分解到指定个数为止,时间复杂度是O(NNct)。因此第一阶段具有线性的时间复杂度。

在第二阶段,对于占数据集绝大多数的正常数据,在搜索对象的k个最近邻时,通过高效的剪枝而尽可能早地中断最近邻搜索,大大减少了对象间距离计算的次数,因此第二阶段具有近似线性的时间复杂度O(N×d)。综合离群检测的两个阶段,CDOD算法的时间复杂度与数据集大小成近似线性关系。

3.2 实验结果

通过实验对算法的效率进行测试分析。实验平台为P4 1.8GHz的CPU,1G内存的计算机,操作系统为Windows XP。实验数据集取自UCI KDD Archive的KDD Cup 1999数据集[9]。该数据集采用1998 DARPA入侵检测数据集来构造连接记录和提取特征。每个连接共有42个变量,其中8个是离散型变量,其余是连续型数字变量。从全部变量中选取了20个连续型变量,并对数据记录进行了归一化处理。为了测试算法对数据集大小的伸缩性,取离群点个数n=30,最近邻个数k分别为5和10,数据集记录个数从100K增加到700K,执行CDOD算法和嵌套循环算法所花费的时间对比如图1和图2所示。

实验结果说明了CDOD算法在执行效率上优于传统的嵌套循环算法,并且随着数据集的增大,挖掘性能更优。

4 结束语

本文研究了大规模数据集上的离群检测问题,提出了CDOD算法。算法综合了基于聚类和基于距离的方法的特点。第一阶段采用层次聚类和k-means的混合聚类算法对数据集进行大致聚类,并用一个启发式规则估计每个簇包含离群点的可能性,按可能性从大到小进行排序。这一方法使得第二阶段进行离群检测时剪枝阈值可以快速增大,提高剪枝效率。第二阶段在嵌套循环算法的基础上增加了两个剪枝规则,可以有效地减少对象间距离计算的次数,实现近似线性的时间复杂度。理论分析与实验结果都表明了算法的可行性和效率。

摘要：针对已有的基于距离的离群点检测算法在大数据集上扩展性差的问题,提出了基于聚类和距离混合的大数据集离群检测算法。算法第一阶段采用层次聚类和k-means混合的层次k-means算法对数据进行聚类,并按照一个启发式规则对其进行排序。第二阶段在聚类的结果上采用嵌套循环算法进行离群检测,并通过两个剪枝规则进行高效剪枝,减少了离群检测时数据点之间距离计算的次数。理论分析和实验结果证明了算法的可行性和效率。

关键词：离群点,聚类,嵌套循环,k近邻搜索

参考文献

[1]Han JW,Kamber M.范明,孟小峰,译.数据挖掘概念与技术[M].北京:机械工业出版社,2004.

[2]陆声链,林士敏.基于距离的孤立点检测研究[J].计算机工程与应用,2004,40(33):73-75.

[3]Knorr EM,Ng RT.Algorithms for mining distance-based outliers in large datasets[C]//Proc.of the 24th VLDB Conference.New York,USA:ACM Press,1998.

[4]Weber R,Schek H-J,Blott S.A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces[C]//Proc.of the 24th VLDB Conference.New York,USA:ACM Press,1998.

[5]Ramaswamy S,Rastogi R,Shim K.Efficient algorithms for mining outliers from large data sets[C]//Proc.of the 2000 ACM SIGMOD Int’l Conf.on Management of Data.New York,2000.

[6]Angiulli F,Pizzuti C.Outlier mining in large high-dimensional data sets[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(2):203–215.

[7]Jiang MF,Tseng SS,Su CM.Two-phase clustering process for outlier detection[J].Pattern Recognition Letters,2001,22(6-7):691-700.

[8]Vu NH,Gopalkrishnan V.Efficient pruning schemes for distance-based outlier detection[C].Proc.of the European Conference on Machine Learning and Knowledge Discovery in Databases.2009:160-175.