Delaunay 三角剖分在离群点检测中的应用

朱庆生，唐 汇，冯 骥

ZHU Qingsheng,TANG Hui,FENG Ji

重庆大学 计算机学院，重庆400044

College of Computer Science,Chongqing University,Chongqing 400044,China

1 引言

离群点检测通常是根据适当的评价标准找出数据集中与其他大部分数据不一样的数据点。而这些数据所包含的信息对于识别系统中的异常行为非常有用，这种异常的数据点则被称为离群点。离群点的检测是数据挖掘中一个非常重要的领域，已经被广泛应用在通信异常检测，新的疾病症状发现，天气预测以及网络入侵检测等方面[1]。

到目前为止，产生了很多不同的离群挖掘算法。Knorr 和Ng[2]最早提出了一种基于距离的离群点检测算法。Ramaswamy 等在此基础上提出了改进的基于距离的K-NN（kth nearest neighbor）[3]算法，该算法先计算每个点的到它的第K个最近邻居的距离，然后进行排序，把其中距离最大的n个点作为离群点。Angiulli和Pizzuti[4]提出了一种计算一个点P的前k个最近邻居距离之和的算法，距离和越大则该点为离群点的程度越高。由于基于距离的算法无法识别数据集中的局部离群点，Breunig 等人提出了一种基于密度的LOF 算法[5]，主要思想是通过把每个点的密度和它Mints 邻域的平均密度比值作为该点的局部离群因子，离群因子的值越大则离群程度越高。在KNN 算法的基础上同时发展出了一类基于KNN 图的算法，如Ville Hautamaki 等人提出的基于KNN 图的ODIN 算法[6]，它是通过连接每个点的K个最近邻居形成一个稀疏的有向的KNN 图，然后计算每个点的入度数检测离群点。

在上述的算法中都存在一个前提条件，就是需要提供每个数据对象拥有的邻居个数即参数k的值，它的选择通常是依靠用户的经验和大量的实验决定的，对于不同的数据集，k的取值没有可借鉴性。为了解决这个问题，本文使用了空间邻居的概念，它是直接把每个数据对象所处的空间上相邻的点作为邻居，因而不同于k最近邻，无需人工设置邻居的个数。空间邻居可以由Delaunay三角剖分算法产生，在Delaunay三角剖分图中，每个点与它空间上相邻的点都存在一条边相连接，根据这个特点，本文提出了一种无需参数的基于Delaunay 图的离群点检测算法。

2 Delaunay 三角剖分

Delaunay 三角剖分算法在数值分析（比如有限元分析）以及图形学中是一个非常重要的理论基础，可以用来建立数据集的拓扑结构，通过所建立的连通图反映数据对象之间的相似性关系[7]。Delaunay 三角剖分的结构良好，能够适应各种分布密度的数据，目前已经有了很多成熟的实现算法。Steven Fortune 提出了一种时间复杂度为O(NlogN)的三角网构建算法[8]。由于此算法针对于2 维平面的，并不适合于高维数据集，P Cignonit 等人则提出了一种d维空间中的快速的Delaunay 三角网构建算法[9]。Delaunay 三角网的应用方面也取得了很多成果，如Yi Xiao和Hong Yan[10]实现了应用Delaunay 三角网对文档图像中的文字区域进行提取。Dongquan Liu[11]等人提出了基于Delaunay 三角剖分的边缘点检测算法。Vladimir Estivill-Castro[12]等人利用三角剖分的特性实现了对数据集的聚类。

图1 delaunay 三角剖分

如图1 实线部分形成的图形为Delaunay 三角剖分，虚线部分为Voronoi 图（又称泰森多边形），它们互为对偶关系，图中每个顶点为泰森多边形的生长中心，连接其中相邻的具有公共边的泰森多边形的中心而形成的三角网图即为Delaunay 三角剖分。在图中每个数据点和它空间上相邻的点之间都有边相连；任意三角形的外接圆不能包含其他数据点，如果在d维空间中，则相当于每一个单纯形的外接超球面中都不包含其他的点。从三角剖分图中可以有效地反映数据点之间的相似性关系。

3 基于Delaunay 三角剖分的离群点检测算法

本文算法的主要思想是首先建立数据集对应的Delaunay 三角剖分，任意数据集对应着唯一的Delaunay三角剖分图[13]，遍历此图获取每个数据对象直接相连的邻居，形成每个点的空间邻域关系。然后结合每个点偏离它的邻居点的程度和它所在区域分布的稀疏程度，提出了一种新的离群因子的定义，离群因子的大小决定了每个点的离群程度。

假设数据集D={X1，X2，…，Xn}，任意点∀p∈D。

定义1Delaunay 三角剖分图G(V，E)：

图G(V，E)为通过Delaunay 三角剖分算法形成的三角图。

定义2空间邻居Ne(p)：

在数据集D对应的Delaunay 图中，点p的空间邻居则为与点p直接相连的点。即Ne中所有的点和点p之间都存在一条边直接相连。

定义3点p的平均邻域距离mean(p)：

mean(p)是点p到与它直接相连的邻居点距离的平均值，可以反映点p附近分布的密度，distance(p，q)是求点p与点q之间的欧式距离。

定义4点p的相对离群度ROF(p)：

ROF(p)为点p相对于它所有邻居点的离群度的平均值，其中，PROF(p，q)表示点p相对于点q的离群程度，满足点q是点p的邻居点，即q∈Ne(p)。

如图2 所示，点p5 相对于点p3 的离群度为p5 到p3 的距离和p3 到它的邻居点p1，p2，p4 的距离的平均值的比值；p5 的相对离群度ROF(p)值则为点p5 相对于p2，p3，p4 的离群度的平均值。从图中可以看出相对离群度的定义能够有效地表示每个点相对于它的邻居点的离群程度。

图2 相对离群度描述

定义5点p的离群因子DBOF(p)：

任意点p的离群因子定义为规范化后的该点的平均邻域距离和相对离群度之和。

maxmean，minmean分别为数据集中所有点的平均邻域距离的最大值和最小值，同样maxROF，minROF分别为相对离群度的最大值和最小值。由上定义可知，每个点的离群因子是由它的平均邻域距离和相对离群度共同决定的，通常平均邻域距离越大说明该点分布越稀疏，因此为离群点的可能性也就越大。相对离群度则反映了一个点偏离它邻居点的程度，如果一个点到它的邻居的距离越大，邻居点所在区域分布越密集，则该点的离群因子也就越大，说明该点偏离它的邻居节点的程度也就越大。因此把这两个特征结合起来定义可以使离群因子包含的信息更加完备。

图3 为包含离群点的三角剖分图，标记了几个处于不同位置的顶点，由图中可知点p1为一个离群点，p1到它的邻居点p2 的距离很大，点p2 与它邻居点（p1除外）距离较小，所以p1 相对于邻居点p2 的离群度也就很大，由此可知它的相对离群度较大，并且点p1 的平均邻域距离也很大，所以点p1 的离群因子DBOF(p1) 较大；图中点p2 处于中间聚类的边界位置，p3 处于内部分布密集的区域，p4 处于内部分布稀疏的区域。分析它们的离群因子发现，边缘点p2 的离群因子小于离群点，大于内部点p3，p4；由于点p4 处于分布稀疏的区域，因此相对于p3 拥有较大的平均邻域距离，所以点p4 的离群因子大于p3；点p3 为离群点的可能性则最低。

图3 包含离群点的Delaunay 三角剖分图

通过对图3 的分析可以发现离群因子DBOF 的定义能够有效地表示每个点的离群程度，其值越大说明该点偏离其邻居点越远，离群程度越高。具体算法如下：

输入：数据集D

输出：top-n离群点

步骤1使用Delaunay 三角剖分算法建立数据集D对应的Delaunay 三角剖分图G(V，E)。

步骤2遍历图G，获取每个点的邻接关系表。

步骤3从数据集中任意取一个未访问的点p，获取它的邻居点集合Ne(p)，并标记此点为已访问。

步骤4计算点p到Ne(p)中所有点的距离的平均值mean(p)。

步骤5依次计算点p相对Ne(p)中每个点q的离群度PROF(p，q)，然后取它们的平均值得到点p的相对离群因子ROF(p)。

步骤6重复步骤3 到步骤5 直到数据集中所有的点都访问完毕，执行下一步。

步骤7遍历数据集，计算每个点平均邻域距离mean 和相对离群度ROF 的最大最小值。

步骤8根据定义5，按最小-最大规范化原则处理所有点p∈D的平均邻域距离mean(p) 和相对离群度ROF(p)，然后把规范化后的值求和作为该点的离群因子DBOF(p)。

步骤9按DBOF 的值降序排列，输出离群因子最大的前n个离群点。

4 时间复杂度分析

生成Delaunay 三角剖分图算法时间复杂度最坏的情况下为O(N2)，目前已有很多改进的算法可以把时间复杂度优化到O(N×lgN)，其中N为数据集的大小；算法中计算所有点的平均邻域距离的时间复杂度O(k×N)其中k值为每个点的空间邻居数目，在Delaunay 三角剖分图中该值通常为一个较小的常数。计算所有点的相对离群度时间复杂度为O(k×N)，根据已知条件计算所有点的相对离群度需要的时间复杂度为O(N)。因此本文算法总的时间复杂度为O(N×lgN)+O(k×N)+O(k×N)+O(N)。

5 实验

为了验证算法的准确性，分别以合成数据和真实数据集作为实验数据，同时选择了传统的基于距离的KNN 算法，基于密度的LOF 算法，和Ke Zhang[14]等人提出的一种新的基于密度的LDOF 算法进行了对比实验。该算法的实验环境为：I3 2.4 GHz CPU，内存为2 GB，操作系统为Windows XP，算法的编写使用Matlab。

由于LOF 算法的检测结果依赖于设置合适参数MinPts，KNN 算法依赖于参数K的设置，不同的参数值会对算法结果产生较大影响，本文的结果则是选取的多次实验得出最好的值。

图4 为本文算法在人工数据集上对应的检测结果，图中有3 个聚类，构造了9 个处于不同位置的离群点，本文算法与KNN，LOF 和LDOF 算法一样能够准确地识别图中的离群点。

图4 人工数据集

为了测试算法在真实数据集上的准确度，从UCI 标准数据集中选取了Iris Plants 数据集，wine 数据集，以及breast-cancer数据集作为实验数据。

表1 为实验数据集的基本属性，由于它们都是用于分类的数据集，并不包含离群点，为了适用于本文算法，分别对每个数据集做了预处理，移除数据集中的某个分类，并从中取出部分数据点作为离群点插入新的数据集中。wine 数据集包含了3 个分类，把其中分类3 中的数据移除，并从中选取9 条记录作为离群点插入数据集中；Iris Plants 包含了同样3 个分类Setosa，Versicolour，Virginica，共150条数据。把其中的Setosa类别中的数据减少至9 条作为离群点。breast-cancer 数据由10 个属性组成，包含了699 条诊断记录，分为Benign 和Malignant 2 个类别，把其中Malignant 类数据减少至39 条作为离群数据。

表1 不同数据集信息

为了评估算法的结果，引入了离群误差率检测指标[15]（Outlier Error Rate，OER）。

其中SO表示算法输出的离群点的个数，RSO表示算法所检测出的正确的离群点的个数，DO表示数据集的个数。

图5 （a）wine数据集

图5 （b）iris数据集

图5 （c）breast-cancer数据集

在图中，离群点检测的误差率都是随输出离群点个数的增加而表现出上升的趋势，通过实验对比后，发现本文算法在给出3 个真实数据集上的检测误差率总体上都要低于KNN、LOF 和LDOF 算法，说明在离群点检测准确度上是要高于其他算法的。同时由于KNN 和LOF 算法检测结果是在设置不同参数经过多次实验后取得的，而本文算法则无需参数并且具有良好的检测效果。从上述结论可以得出本文算法是明显优于其他算法的。

6 结束语

Delaunay 三角剖分图在图形学中已经有了很多成熟的应用，但是在离群点检测方面的应用成果还比较少，本文利用Delaunay 三角剖分形成的空间邻居性质提出了一种新的离群点检测算法，并在实验中取得了良好的检测效果，有效地减少了参数对于离群点检测结果的影响。由于本文算法的效率依赖于Delaunay 三角剖分算法，因此选择一个高效的Delaunay 三角剖分算法会有利于本文算法性能的提升。

[1] Gogoi P，Borah B，Bhattacharyya D K，et al.Outlier Identification using symmetric neighborhoods[J].Procedia Technology，2012，6：239-246.

[2] Knnor E，Ng R.Algorithms for mining distance-based outliers in large datasets[C]//Proc of the 24th VLDB Conference.NewYork，USA：Morgan Kaufmann，1998：392-403.

[3] Ramaswamy S，Rastogi R，Shim K.Efficient algorithms for mining outliers from large data sets[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2000：427-438.

[4] Angiulli F，Pizzuti C.Fast outlier detection in high dimensional spaces[M]//Principles of Data Mining and Knowledge Discovery.Berlin Heidelberg：Springer，2002：15-27.

[5] Breunig M M，Kriegel H P，Ng R T，et al.LOF：identifying density-based local outliers[J].ACM Sigmod Record，2000，29（2）：93-104.

[6] Hautamaki V，Karkkainen I，Franti P.Outlier detection using k-nearest neighbour graph[C]//Proceedings of the 17th International Conference on Pattern Recognition.IEEE，2004，3：430-433.

[7] 邱保志，许敏.无参数聚类边界检测算法的研究[J].计算机工程，2011，37（15）.

[8] Fortune S.A sweepline algorithm for Voronoi diagrams[J].Algorithmica，1987，2（1/4）：153-174.

[9] Cignoni P，Montani C，Scopigno R.DeWall：A fast divide and conquer Delaunay triangulation algorithm in [J].Computer-Aided Design，1998，30（5）：333-341.

[10] Xiao Y，Yan H.Text region extraction in a document image based on the Delaunay tessellation[J].Pattern Recognition，2003，36（3）：799-809.

[11] Liu D，Nosovskiy G V，Sourina O.Effective clustering and boundary detection algorithm based on Delaunay triangulation[J].Pattern Recognition Letters，2008，29（9）：1261-1273.

[12] Estivill-Castro V，Lee I.AMOEBA：Hierarchical clustering based on spatial proximity using Delaunay diagram[C]//Proceedings of the 9th International Symposium on Spatial Data Handling.Beijing，China.2000.

[13] 丁永祥，夏巨谌.任意多边形的Delaunay 三角剖分[J].计算机学报，1994，17（4）：270-275.

[14] Zhang K，Hutter M，Jin H.A new local distance-based outlier detection approach for scattered real-world data[M]//Advances in Knowledge Discovery and Data Mining.Berlin Heidelberg：Springer，2009：813-822.

[15] 朱庆生，钟洵，杨鹏.NJW在离群数据挖掘中的应用研究[J].计算机工程与应用，2010，46（7）：128-130.