基于K-均值聚类和泰森多边形的异常值检测方法

孙　添，何国良

(电子科技大学数学科学学院， 四川　成都　611731)



基于K-均值聚类和泰森多边形的异常值检测方法

孙添，何国良

(电子科技大学数学科学学院， 四川成都611731)

[摘要]离群点发现是数据挖掘研究的一个重要方面.根据数据流的特点提出一种基于K-均值聚类和泰森多边形的离群点检测方法，先用K-均值对数据进行处理，生成中间聚类结果，然后用泰森多边形方法(VOD)对这些中间结果进行再次选择，最后找出可能存在的离群点.

[关键词]异常值检测；K-均值聚类；泰森多边形；数据挖掘

数据挖掘任务一般可以分4类：(a)依赖性检验；(b)类别鉴定；(c)类别描述；(d)异常检测.前面3种任务与数据集合大部分对象中的模式有关.绝大多数的数据挖掘比如分类、关联规则等都是这3类任务的范畴；但其中的第4类任务主要是研究数据集中的一小部分内容，而这一小部分不符合数据集的一般模型或规则，这些数据对象叫做异常点.很多挖掘方法将其看成噪声丢掉，而在另一些应用如保险欺诈检验中，关于异常点的检测在这种情况下就成为相当重要的事情.

近年来，一种被称为数据流的新型数据形式在相当多的领域中出现，如通话记录等.数据流在通常情况下是一个有序的数据序列x2,…，xi,…,xn(xi为数据点).这些数据按i递增的顺序只能访问少量的几次甚至一次.

本文提出的异常值检测方法是一种适应流数据特点，并且对数据分区是使用K-均值聚类方法来实现的，将在内存中保存着每个部分生成的k个聚类点.为了适应内存容量的限制丢掉了每部分剩余的数据点，并且采用一种非参数方法查找异常用于累积存储于内存中的点上.这样能降低参数对异常值检测的影响，因而能更好地将数据中的异常值找出.之前的一些文献用到聚类算法，在检测异常值时又引入其他阈值作为判断的依据，使得算法对参数的依赖性很大；而本文对于异常值的判定选取非参数检测方法，使得算法只受聚类参数k的影响，从而使得算法效率更高.

1相关知识

1.1离群点定义

对离群点的定义不一样的检测方法存在一定的差别，但Hawkins给出的形式化定义被研究者广泛接受并成为研究离群点问题的基础[1].

如果一个数据样本与其他样本之间存在足以引起怀疑的差异，则被称为离群点，Hawkins的定义形象地描述了离群点的特征.

1.2k-means聚类算法

k-means聚类仅仅是诸多划分聚类方法中的一种.其主要流程为：(1)随机选择K个数据作为N个文档初始聚类中心点；(2)对剩余的每个数据计算它到初试聚类中心点的距离，并把它归到最近的聚类中心点；(3)将已经得到的各类聚类中心点进行重新计算；(4)重复(2)、(3)，直到聚类中心点不再变化，然后记最终的聚类中心点为(si,ti).

1.3数据流离群点检测

数据流数据与传统的数据挖掘对象相比，数据流数据随着时间动态增加，数据量不断增大等.这些特点使得数据流异常点检测的方法需要满足下面的要求：

1)算法可以在小空间上运行

这是数据流挖掘面临的首要困难，主要是由于数据量随时间的不断增加，离群点检测针对所有存储下来的数据来进行是不大现实的，故将有限的存储空间对“无限”的数据流进行处理对于数据流异常值检测算法是可行的.

2)算法只能扫描数据少量几次甚至一次

伴随时间的推移，使用不断添加到数据流的新的数据代替以前存储器中储存的数据，这样就使得算法需要只对数据进行少量几次访问甚至一次.

2离群点检测方法

之前有人提出了一种基于K-均值聚类的流数据离群点发现方法[2].该方法首先在数据流分区接着使用K-均值聚类产生中间聚类结果(均值参考点集)，之后再利用非参数方法对这些参考点找出潜在的离群点.借鉴该种算法，文献[3]提出用K-均值聚类结合凝聚聚类查找离群点方法，一开始将K-均值聚类应用在各时段内的数据流来生成对应的中间均值点集，然后对这些中间均值点应用凝聚聚类进行分析，查找出那些可能存在的异常值.

根据上面两种方法的思路，本文提出基于K-均值聚类并使用VOD离群点检测方法.这个方法的主要步骤是：第一步，将数据流进行分区，然后做K-均值聚类生成相应的聚类中心点集；第二步，利用泰森多边形的方法来对这些中间均值点进行异常值的判断.相对于之前的方法，在查找异常点的过程中不再引入新的参数，使得算法对参数的影响变小.

2.1相关定义

VOD方法的原理

Voronoi图是一种用来描述点集邻近关系的一种数据结构.给定M个点的集合S，点集S的Voronoi图把平面划分成M个区域.一般地，将Voronoi图的点称作Voronoi顶点，线段称作Voronoi边，如图1所示.

图1　Voronoi图

在点S集的Voronoi图中，给定pS ,V(pi)只包含S中的一个点.所以，相对于V(pi)多边形范围内的其他任意一个点来讲，其到pi的距离比到S中其他顶点的距离都要小.也就是,∀j≠i}.其中，dist()是欧氏距离.

Voronoi图上，任意pi的每一个邻近点确定Voronoi多边形V(pi)的一条边；反过来说，可以通过V(pi)的边找出pj的所有邻近点，记为VN(pi).如图1所示，p2的邻近点是p2、p3、p4、p5、p6.

根据Voronoi图的性质，对于点集中S任一个点pi，根据pi的Voronoi多边形V(pi)确定它的邻近点，再计算pi到其所有的邻近点平均距离，记为Vd(pi)，作为pi的近邻分布密度，即：

(1)

Vd(pi)可以很客观地反映点周围pi的分布密度，故对于异常点来说，其邻近点与它的距离比较大，Vd(pi)也就比较大.如果将Vd(pi)按从大到小的顺序排列，那么Vd(pi)较大的点就可能是异常点.

2.2算法思想

以下对本文提出的算法思想进行阐述.首先对数据流进行分区，把顺序的m个数据点来形成一个划分，接着将K-均值聚类应用在每一个划分中的m个数据点上，并把产生的k个聚类中心点保存为ki(si，ti)的数据类型；然后构造k个ki的Voronoi图，计算每一点的V-邻近分布密度Vd(pi)，根据Vd(pi)的大小来判断数据流中的异常值.数据流离群点检测过程一直到某一时刻内的数据已经全部遍历后才会结束.算法流程如下：

图2　算法流程

2.3算法时间复杂性分析

算法的过程是由两部分组成：一是分割数据，分割是将连续的m个数据点看作一个划分，将K-均值聚类应用在每一个划分上的m个数据点所生成的聚类中心点的开销；对k个ki利用VOD方法检测异常值的开销.

在大数据集上应用k-means算法，优点主要表现为算法的可伸缩性比较好，而时间复杂度为O(tkn)，其中t是算法实现时迭代的次数，k是事先限定好的簇的个数，n则是数据集合里面数据点的个数.通常情况下，k≪n和t≪n.由于对每个划分块上的m个数据点进行K-均值聚类，因此这一步的时间消耗复杂度为O(mkn).如果数据点的个数m取值比较小，那么相对应的迭代次数t也会相应比较小.

3实验分析

本节通过实验来分析算法的效率和有效性.使用二维模拟数据集来测试算法对离群点的检测效果，模拟数据如图3所示.生成的方法是在矩形区域内产生1 000个符合N(4.0,1.0)的正态分布的点，然后再产生1 000个均匀分布(x2+y2≤1)的随机点，最后加入10个异常数据点在空白区域.

图3　实验数据集

对算法进行实验，实验结果如表1所示.

表1　实验结果

由图2可知，先采用聚类算法，使得数据量急剧减少，再对生成的数据点进行异常值检测，但由于k值不同，异常点检测方法的效果受到一定影响，检测出来的异常值的数目不同.当k为某一个恰当值时，可以很好地找出全部的异常值.

采用文献[2]提出的方法来查找异常值，查找结果如表2.

表2　对比试验结果

此方法也能找出异常值，但在判定异常值的过程中引入新的阈值，使得算法受到两个参数的影响，而非参数的方法查找异常值所受到的限制更小，查找准确率更高.虽然该算法对异常值的检测与k值有关，主要是K-均值聚类的效果受k的值影响较大.但在异常值检测中，泰森多边形是一种非参数检测，因此本算法只受k值影响.

4结语

K-均值聚类的聚类结果比较不稳定，即使对于同样输入参数聚类结果也可能完全不一样.本文提出一种基于K-均值聚类和泰森多边形的离群点检测查找方法，在K-均值聚类的基础上增加泰森多边形使算法更加稳定.对于点的个数很多的情况，我们第一时间可以排除其为异常值，对其他的点进行异常值检测，提高了效率.理论分析与实验结果表明，算法是有效、可行的.

[参考文献]

[1]HAWKINSD.Identificationofoutliers[M].London：ChapmanandHall, 1980.

[2]倪巍伟，陆介平，陈耿，等.基于均值分区的数据流离群点检测算法[J].计算机研究与发展，2006,43(9)：1639-1643.

[3]曾颖，罗可，邹瑞芝.基于K-均值聚类和凝聚聚类的离群点查找方法[J].计算机工程与应用，2009，45(29)：131-133.

[4]QUJL，QINW，SAIY，FENGYM.Anonparametricoutlierdetectionmethodforfinancialdata[C].Proceedingsofthe16thIEEEInternationalConferenceonManagementScience&Egneering,2009:1442-1447.

[5]黄天强，秦小麟，叶跃飞.基于方形邻域的离群点的查找新方法[J].控制与决策，2006,21(5):541-545.

[6]BREUNINGMM,KREIGELHP,NGRT,etal.LOF：Identifyingdensity-basedlocaloutliers[C].TheACMSIGMOD,Dallas,TX,2000:427-438.

[7]ESTERM,KREIGELHP,SANDERJ,etal.Adensitybasedalgorithmfordiscoveringclustersinlargespatialdatabases[C].ProcofKDD’96,PorlandOR,1996:226-231.

(责任编辑穆刚)

Outliers detection method based onK-means and voronoi diagram

SUN Tian, HE Guoliang

(School of Mathematical Sciences, University of Electronic, Science and Technology, Chengdu Sichuan 611371, China)

Abstract：Outlier discovery is an important aspect of data mining. According to the characteristics of the data stream, based on K-means clustering and outlier detection method Thiessen polygons is proposed, first with K-mean data processing, generation intermediate clustering results, and then using Thiessen polygons method (VOD). These intermediate results were once again selected, and finally the possible outliers were identified.

Key words：outliers detection; K-means clustering; voronoi diagram; data mining

[中图分类号]O651

[文献标志码]A

[文章编号]1673-8004(2016)02-0010-04

[作者简介]孙添(1990—)，女，河北保定人，硕士，主要从事数据分析方面的研究.

[基金项目]国家自然科学基金项目(11371288)；国家留学基金项目.

[收稿日期]2015-06-17