基于聚类的离群点检测

1基于聚类的离群点检测方法RajendraPamula,JatindraKumarDeka,SukumarNandiDepartmentofComputerScienceandEngineeringIndianInstituteofTechnologyGuwahatiGuwahati,Assam,IndiaEmail:r.pamula,jatin,[e-mail]摘要:本论文提出来一个聚类方法用以检测离群点。通过使用k均值聚类算法来从数据集中划分聚类。离聚类中心比较近的点不太可能是离群点，同时我们可以从聚类中去除掉这些点。接下来计算剩下的点和离群点的距离。需要计算的离群点度的降低可能是由于一些点的去除。我们声明离群度最高的点作为离群点。实验数据使用真实数据集，并论证得知，即使所计算的数据比较少，但所提出的方法比现存的方法优越。关键字:离群点；聚类；基于距离；1.引言离群点是和数据集中正常点不一致的数据点。离群点检测在数据清理中有重要的应用，像欺诈检测，入侵检测，营销，传感网络，垃圾邮件检测。在数据点中找出异常点是离群点检测的基础理论。离群点检测暗示对象脱离给定的数据集。离群点的检测已经广泛地在统计领域研究。典型地就是用户需要使用统计分布对数据点建模，同时一个点被划为离群点主要看其和假定模型的关联。这些技术的主要问题是许多情况下用户可能对基础数据分布没有足够的了解。特别是对数据集中的每一对关联对象使用距离函数的基于距离的技术。基于距离的定义描述了一个对数据分析有效的工具。这些定义以计算的方式是有效率的，而在部分已经检测的数据集中基于距离的离群点的得分是单调非递增函数。最近几年已经提出了许多快速检测基于距离的离群点算法。一些算法在CPU消耗上比较有效，而其他一些主要是侧重于I/O消耗。许多方法用来查找偏离其他点的某个点，这意味着这个点是离群点。众所周知，数据集中的离群点是相当少的。因此也没必要为所有点提供这些方法。通过移除可能不是离群点的这些都，我们可以降低计算时间。2我们的工作是使用聚类和距离函数来区别那些不是离群点的点，然后去除这些点。接下来为所有剩余的点预测基于距离的方法，这些方法使用一个参数来区别一个点是不是离群点。我们假设数据集中有n个离群点，然后通过我们的方法得出的前n个点作为离群点。我们使用基于距离的局部离群系数来区别离群点。2.相关工作KnorrandNg是第一个提出基于距离的离群点检测方法。如果数据集中至少有pct部分对象和对象p的距离大于D,则对象p是一个基于距离的关于参数pct和D的离群点即DB（pct,D）离群点。这个定义被广泛接受，因为它归纳了许多统计离群的测试。Ramaswamy等人提出了以上定义的扩展。所有点根据离群度划分。给定两个变量kn和w，如果Dk中比p有更高价值的对象数少于w，则对象p被认为是离群点，其中Dk表示对象p的第k个最近邻的距离。随后，Angiulli和Pizzuti提出了一个通过考虑全部对象领域来决定离群点的方法。所有点的划分是基于第k个最近邻距离的总和，而不是单独考虑第k个最近邻的距离。上述的三个定义是紧密相关的。Breuning等人提出了数据集中用以表示每个对象离群程度的局部离群系数。这是关于离群点离群程度的第一个概念。离群系数局限在仅考虑一个约束领域的每个对象。一个对象的局部离群系数可以通过和它的领域比较其密度。它比基于距离的方法有更强的模型能力，因为它仅仅是基于对象本身的密度。基于密度的方法不能明确地把对象归类为离群点或者非离群点。Zhang等人提出了局部基于距离的离群点检测方法。基于距离的局部离群系数可以确定一个对象偏离其邻域的程度。计算数据集中所有点的基于距离的局部离群系数，其复杂度为2()ON，其中N是数据集中点的个数。聚类方法有许多，像CLARANS,DBSCAN,BIRCH和CURE都能检测离群点。然而，因为聚类方法的主要目的是发现聚类，其发展是为了使聚类最优化，而不是使离群点检测最优化。离群点的定义使用的是主观的被这些算法检测到的聚类。而基于距离的离群点定义则更加客观并且聚类是怎样在输入的数据中被检测出来的显得相对独立。3目前关于离群点的工作主要是仅仅集中在识别方面，在文献11中打算提供有意的知识，它是基于为什么一个待鉴定的离群点是异常的解释。3.背景我们使用基于距离的局部离群系数，它能表示一个点偏离其领域的程度。一个点的LDOF值高就意味着偏离其领域比较多，同时也就意味着可能是离群点。LDOF的计算如下：LDOF中的p，其定义如下：():ppdLDOFpD,','1:(,')(1)ppqqNqqDdistqqkk计算所有点LDOF值计算消耗比较大，但算法的复杂度是2()ON。我们尝试在去除那些可能不是离群点的点时降低计算复杂度。4.基于局部离群点的剪枝这部分主要描述提出的算法，它是LDOF的改进。在文献18中提出的LDOF算法的主要缺点是计算消耗巨大。这是因为数据集DS中的每个点都要计算其LDOF。而我们所关注的仅仅是离群点，它的数量是非常少的，对于所有点LDOF的计算用处较小，可以一起避免。我们使用K均值算法来对数据集进行聚类。一旦聚类形成，则计算每个聚类的半径。去除那些离质心的距离比半径小的点。然后计算每个聚类中未被剪枝点的LDOF值。记录拥有高LDOF值的前n个点作为离群点。A．简述基于剪枝算法的主要思想是首先对数据集进行聚类，然后从聚类中剪去那些可能不是离群点的点。而离群点的数目n可能会很小，这种额外的前序步骤可以帮助去除不是离群点的点。算法1描述了我们查找离群点的方法。我们简要描述一下剪枝算法执行所需要的步骤。(1)产生聚类：首先使用K均值聚类算法对整个数据集聚类，然后计算每个聚类4的半径。（2）剪枝：如果一个聚类包含的点比要求的离群点的数目要少，这个聚类就可以免去剪枝。为每个聚类剪枝：计算聚类中每个点离质心的距离。如果距离比半径小，则去除该点。(3)估算离群点：计算所有聚类中未被剪枝的点的LDOF。则拥有高LDOF值的前n个点作为离群点。K均值算法复杂度为c*it*N，其中c是聚类的数目，it是重复计算的次数，N是数据点的数目。这个算法的总的复杂度是c*it*N+c*np+2(*)wN，其中np表示每个聚类中的点的平均个数，w表示剪枝后剩下的点所占的比率，这个值一般在0.4左右。聚类的数目c依赖与离群点的数目。然而c和it是比较小的，所以总得复杂度要小于2N。算法1离群点检测算法输入：数据集DS，聚类数c，重复次数it，离群点个数n1.使用K均值聚类算法得到聚类,得到Y2.foreachclusterjCYdo3.jRadius←()jradiusC4.endfor5.if|Cj|nthen6.foreachpointpi∈Cjdo7.ifdistance(pi,oj)Radiusjthen8.prune(pi)9.else10.AddpitoU11.endif12.endfor13.else14.foreachpointpi∈Cjdo515.AddpitoU16.endfor17.endif18.foreachpointpi∈Udo19.计算LDOF(pi)20.endfor21.根据LDOF的值对所有点进行排序22.拥有高LDOF值得前n个点作为离群点B.实验结果这一部分，我们比较离群点检测算法PLDOF和LDOF。（1）医学诊断数据集：在现实的数据库中很难找到一个数据集来评估离群点检测算法，因为仅有很少的数据集能正确的认识到哪些对象是真正的行为异常。在这个试验中我们使用医学的数据集WDBC，这个数据集是为了乳房肿块诊断做原子特征提取的。这个数据集包括569个医学诊断记录，每个记录都有32个属性(ID,诊断信息，30个真实的输入特征)。这个诊断是二元的，要么是良性的要么是恶性的。我们认为良性的记录的正常数据。这个实验中，我们用所有的这357个良性诊断记录作为正常对象，然后加入5个恶性诊断记录作为离群点。通过改变邻近的大小k，把真实离群点占隐藏离群点的比率作为检测的精度。实验中，我们逐渐增加k的值，然后计算每个方法的计算精度。图1WDBC数据6为了进一步验证我们的方法，我们重复10次实验，每次离群点的数目不相同。每次独立执行10步，然后计算平均检测精度，k的取值范围从10到50.从图1中我们可以看出精度随前n个点和邻域的大小k变化而变化。正如图1所示，我们的算法比LDOF算法精度高。如果考虑钱20个点，两个算法都能检测到所有的离群点。我们同时也改变邻域大小k来进行实验。可以看到，两个算法在k=30时精度达到了极限。从表1中我们可以看出虽然我们从数据集中剪去了57%的点，但是两个算法的精度还是差不多。由于剪去了57%的点，计算的消耗也大大降低，这也是基于LDOF剪枝方法值得肯定的一面。表1WDBC数据集的剪枝比率（2）酵母数据集：在这个实验中，我们使用酵母数据集，这个数据集曾被用来查找蛋白质集中的地方。数据集包括1484个对象，每个对象有如下属性：名字和其他8个输入特征。我们认为在C-terminus中值为0的目标信号为正常数据，其中POX的值比异常的大2.实验中我们使用整个1474个记录作为正常对象，然后加入10个记录作为离群点。我执行与医学诊断数据集相似类型的实验可以观察到相同的趋势。实验结果如图2和表2.可以看出我们可以从原始数据集中剪去超过60%的点而不丢失离群点。表2酵母数据集的剪枝比率7图2酵母数据5.结论本篇论文我们提出了一个有效的离群点检测方法。首先通过使用每个聚类的半径来判断哪些点可能不是离群点，然后从数据集中移除这些点。由于降低了数据集的大小，时间复杂度得到了降低。同时使用基于距离的局部离群系数来衡量一个对象偏离其邻域的程度。通过剪除一些点使得我们的方法在检测离群点上比现在的方法精度要高。参考文献[1]F.Angiulli,S.Basta,andC.Pizzuti.Distance-baseddetectionandpredictionofoutliers.IEEETransactionsonKnowledgeandDataEngineering,18:145–160,2006.[2]F.AngiulliandC.Pizzuti.Fastoutlierdetectioninhighdimensionalspaces.InPKDD’02:Proceedingsofthe6thEuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscovery,pages15–26,2002.[3]F.AngiulliandC.Pizzuti.Outliermininginlargehighdimensionaldatasets.IEEETransactionsonKnowledgeandDataEngineering,17:203–215,2005.[4]A.Arning,R.Agrawal,andP.Raghavan.Alinearmethodfordeviationdetection8inlargedatabases.pages164–169,1996.[5]M.M.Breunig,H.-P.Kriegel,R.T.Ng,andJ.Sander.Lof:identifyingdensity-basedlocaloutliers.SIGMODRec.,29(2):93–104,2000.[6]M.Ester,H.-P.Kriegel,andX.Xu.Adatabaseinterfaceforclusteringinlargespatialdatabases.InProceedingsof1stInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD-95),1995.[7]A.Ghoting,S.Parthasarathy,andM.Otey.Fastminingo