《基于聚类的离群点检测》由会员分享，可在线阅读，更多相关《基于聚类的离群点检测（9页珍藏版）》请在金锄头文库上搜索。
1、1基于聚类的离群点检测方法Rajendra Pamula, Jatindra Kumar Deka, Sukumar Nandi Department of Computer Science and Engineering Indian Institute of Technology Guwahati Guwahati, Assam, IndiaEmail: iitg.ac.in摘要摘要:本论文提出来一个聚类方法用以检测离群点。通过使用 k 均值聚类算法来从数据集中划分聚类。离聚类中心比较近的点不太可能是离群点，同时我们可以从聚类中去除掉这些点。接下来计算剩下的点和离群点的距离。需要计算的离群
2、点度的降低可能是由于一些点的去除。我们声明离群度最高的点作为离群点。实验数据使用真实数据集，并论证得知，即使所计算的数据比较少，但所提出的方法比现存的方法优越。关键字关键字:离群点；聚类；基于距离；1.引言引言离群点是和数据集中正常点不一致的数据点。离群点检测在数据清理中有重要的应用，像欺诈检测，入侵检测，营销，传感网络，垃圾邮件检测。在数据点中找出异常点是离群点检测的基础理论。离群点检测暗示对象脱离给定的数据集。离群点的检测已经广泛地在统计领域研究。典型地就是用户需要使用统计分布对数据点建模，同时一个点被划为离群点主要看其和假定模型的关联。这些技术的主要问题是许多情况下用户可能对基础数据分布
3、没有足够的了解。特别是对数据集中的每一对关联对象使用距离函数的基于距离的技术。基于距离的定义描述了一个对数据分析有效的工具。这些定义以计算的方式是有效率的，而在部分已经检测的数据集中基于距离的离群点的得分是单调非递增函数。最近几年已经提出了许多快速检测基于距离的离群点算法。一些算法在CPU 消耗上比较有效，而其他一些主要是侧重于 I/O 消耗。许多方法用来查找偏离其他点的某个点，这意味着这个点是离群点。众所周知，数据集中的离群点是相当少的。因此也没必要为所有点提供这些方法。通过移除可能不是离群点的这些都，我们可以降低计算时间。2我们的工作是使用聚类和距离函数来区别那些不是离群点的点，然后去除这
4、些点。接下来为所有剩余的点预测基于距离的方法，这些方法使用一个参数来区别一个点是不是离群点。我们假设数据集中有 n 个离群点，然后通过我们的方法得出的前 n 个点作为离群点。我们使用基于距离的局部离群系数来区别离群点。2.2.相关工作相关工作Knorr and Ng 是第一个提出基于距离的离群点检测方法。如果数据集中至少有 pct 部分对象和对象 p 的距离大于 D,则对象 p 是一个基于距离的关于参数pct 和 D 的离群点即 DB（pct,D）离群点。这个定义被广泛接受，因为它归纳了许多统计离群的测试。Ramaswamy 等人提出了以上定义的扩展。所有点根据离群度划分。给定两个变量 kn
5、和 w，如果 Dk 中比 p 有更高价值的对象数少于 w，则对象 p 被认为是离群点，其中 Dk 表示对象 p 的第 k 个最近邻的距离。随后，Angiulli 和 Pizzuti 提出了一个通过考虑全部对象领域来决定离群点的方法。所有点的划分是基于第 k 个最近邻距离的总和，而不是单独考虑第 k个最近邻的距离。上述的三个定义是紧密相关的。Breuning 等人提出了数据集中用以表示每个对象离群程度的局部离群系数。这是关于离群点离群程度的第一个概念。离群系数局限在仅考虑一个约束领域的每个对象。一个对象的局部离群系数可以通过和它的领域比较其密度。它比基于距离的方法有更强的模型能力，因为它仅仅是基
6、于对象本身的密度。基于密度的方法不能明确地把对象归类为离群点或者非离群点。Zhang 等人提出了局部基于距离的离群点检测方法。基于距离的局部离群系数可以确定一个对象偏离其邻域的程度。计算数据集中所有点的基于距离的局部离群系数，其复杂度为，其中 N 是数据集中点的个数。2()O N聚类方法有许多，像 CLARANS,DBSCAN,BIRCH 和 CURE 都能检测离群点。然而，因为聚类方法的主要目的是发现聚类，其发展是为了使聚类最优化，而不是使离群点检测最优化。离群点的定义使用的是主观的被这些算法检测到的聚类。而基于距离的离群点定义则更加客观并且聚类是怎样在输入的数据中被检测出来的显得相对独立。
7、3目前关于离群点的工作主要是仅仅集中在识别方面，在文献 11 中打算提供有意的知识，它是基于为什么一个待鉴定的离群点是异常的解释。3.3.背景背景我们使用基于距离的局部离群系数，它能表示一个点偏离其领域的程度。一个点的 LDOF 值高就意味着偏离其领域比较多，同时也就意味着可能是离群点。LDOF 的计算如下：LDOF 中的 p，其定义如下：( ):ppdLDOF pD, ,1:( , )(1)pp q qNq qDdist q qk k计算所有点 LDOF 值计算消耗比较大，但算法的复杂度是。我们尝试2()O N在去除那些可能不是离群点的点时降低计算复杂度。4.4.基于局部离群点的剪枝基于局部
8、离群点的剪枝这部分主要描述提出的算法，它是 LDOF 的改进。在文献 18 中提出的 LDOF算法的主要缺点是计算消耗巨大。这是因为数据集 DS 中的每个点都要计算其LDOF。而我们所关注的仅仅是离群点，它的数量是非常少的，对于所有点 LDOF的计算用处较小，可以一起避免。我们使用 K 均值算法来对数据集进行聚类。一旦聚类形成，则计算每个聚类的半径。去除那些离质心的距离比半径小的点。然后计算每个聚类中未被剪枝点的 LDOF 值。记录拥有高 LDOF 值的前 n 个点作为离群点。A 简述基于剪枝算法的主要思想是首先对数据集进行聚类，然后从聚类中剪去那些可能不是离群点的点。而离群点的数目 n 可能
9、会很小，这种额外的前序步骤可以帮助去除不是离群点的点。算法 1 描述了我们查找离群点的方法。我们简要描述一下剪枝算法执行所需要的步骤。(1)产生聚类：首先使用 K 均值聚类算法对整个数据集聚类，然后计算每个聚类4的半径。（2）剪枝：如果一个聚类包含的点比要求的离群点的数目要少，这个聚类就可以免去剪枝。为每个聚类剪枝：计算聚类中每个点离质心的距离。如果距离比半径小，则去除该点。(3)估算离群点：计算所有聚类中未被剪枝的点的 LDOF。则拥有高 LDOF 值的前n 个点作为离群点。K 均值算法复杂度为 c*it*N，其中 c 是聚类的数目，it 是重复计算的次数，N 是数据点的数目。这个算法的总的
10、复杂度是 c*it*N+c*np+，其中 np2( *)w N表示每个聚类中的点的平均个数，w 表示剪枝后剩下的点所占的比率，这个值一般在 0.4 左右。聚类的数目 c 依赖与离群点的数目。然而 c 和 it 是比较小的，所以总得复杂度要小于。2N算法 1 离群点检测算法输入：数据集 DS，聚类数 c，重复次数 it，离群点个数 n1.使用 K 均值聚类算法得到聚类,得到 Y2.for each cluster dojCY3. jRadius()jradius C4.end for5.if |Cj|n then6. for each point piCj do7. if distance(pi
11、,oj)Radiusj then8. prune(pi)9. else10. Add pi to U11. end if12. end for13.else14. for each point piCj do515. Add pi to U16. end for17.end if 18.for each point piU do19. 计算 LDOF(pi)20.end for21.根据 LDOF 的值对所有点进行排序22.拥有高 LDOF 值得前 n 个点作为离群点B.实验结果这一部分，我们比较离群点检测算法 PLDOF 和 LDOF。（1）医学诊断数据集：在现实的数据库中很难找到一个数据集
12、来评估离群点检测算法，因为仅有很少的数据集能正确的认识到哪些对象是真正的行为异常。在这个试验中我们使用医学的数据集 WDBC，这个数据集是为了乳房肿块诊断做原子特征提取的。这个数据集包括 569 个医学诊断记录，每个记录都有 32 个属性(ID,诊断信息，30 个真实的输入特征)。这个诊断是二元的，要么是良性的要么是恶性的。我们认为良性的记录的正常数据。这个实验中，我们用所有的这 357 个良性诊断记录作为正常对象，然后加入 5 个恶性诊断记录作为离群点。通过改变邻近的大小 k，把真实离群点占隐藏离群点的比率作为检测的精度。实验中，我们逐渐增加 k 的值，然后计算每个方法的计算精度。图 1 W
13、DBC 数据6为了进一步验证我们的方法，我们重复 10 次实验，每次离群点的数目不相同。每次独立执行 10 步，然后计算平均检测精度，k 的取值范围从 10 到 50.从图 1 中我们可以看出精度随前 n 个点和邻域的大小 k 变化而变化。正如图 1 所示，我们的算法比 LDOF 算法精度高。如果考虑钱 20 个点，两个算法都能检测到所有的离群点。我们同时也改变邻域大小 k 来进行实验。可以看到，两个算法在 k=30 时精度达到了极限。从表 1 中我们可以看出虽然我们从数据集中剪去了 57%的点，但是两个算法的精度还是差不多。由于剪去了 57%的点，计算的消耗也大大降低，这也是基于 LDOF
14、剪枝方法值得肯定的一面。表 1 WDBC 数据集的剪枝比率（2）酵母数据集：在这个实验中，我们使用酵母数据集，这个数据集曾被用来查找蛋白质集中的地方。数据集包括 1484 个对象，每个对象有如下属性：名字和其他 8 个输入特征。我们认为在 C-terminus 中值为 0 的目标信号为正常数据，其中 POX 的值比异常的大 2.实验中我们使用整个 1474 个记录作为正常对象，然后加入 10 个记录作为离群点。我执行与医学诊断数据集相似类型的实验可以观察到相同的趋势。实验结果如图 2 和表 2.可以看出我们可以从原始数据集中剪去超过 60%的点而不丢失离群点。表 2 酵母数据集的剪枝比率7图
15、2 酵母数据5.5.结论结论本篇论文我们提出了一个有效的离群点检测方法。首先通过使用每个聚类的半径来判断哪些点可能不是离群点，然后从数据集中移除这些点。由于降低了数据集的大小，时间复杂度得到了降低。同时使用基于距离的局部离群系数来衡量一个对象偏离其邻域的程度。通过剪除一些点使得我们的方法在检测离群点上比现在的方法精度要高。参考文献参考文献1 F. Angiulli, S. Basta, and C. Pizzuti. Distance-based detection and prediction of outliers. IEEE Transactions on Knowledge and D
16、ata Engineering, 18:145160, 2006.2 F. Angiulli and C. Pizzuti. Fast outlier detection in high dimensional spaces. In PKDD 02: Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, pages 1526, 2002.3 F. Angiulli and C. Pizzuti. Outlier mining in large highdimensional data sets. IEEE Transactions on Knowledge and Data Engineeri
