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.