Delaunay 三角剖分在離群點(diǎn)檢測(cè)中的應(yīng)用

朱慶生，唐 匯，馮 驥

ZHU Qingsheng,TANG Hui,FENG Ji

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶400044

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

1 引言

離群點(diǎn)檢測(cè)通常是根據(jù)適當(dāng)?shù)脑u(píng)價(jià)標(biāo)準(zhǔn)找出數(shù)據(jù)集中與其他大部分?jǐn)?shù)據(jù)不一樣的數(shù)據(jù)點(diǎn)。而這些數(shù)據(jù)所包含的信息對(duì)于識(shí)別系統(tǒng)中的異常行為非常有用，這種異常的數(shù)據(jù)點(diǎn)則被稱(chēng)為離群點(diǎn)。離群點(diǎn)的檢測(cè)是數(shù)據(jù)挖掘中一個(gè)非常重要的領(lǐng)域，已經(jīng)被廣泛應(yīng)用在通信異常檢測(cè)，新的疾病癥狀發(fā)現(xiàn)，天氣預(yù)測(cè)以及網(wǎng)絡(luò)入侵檢測(cè)等方面[1]。

到目前為止，產(chǎn)生了很多不同的離群挖掘算法。Knorr 和Ng[2]最早提出了一種基于距離的離群點(diǎn)檢測(cè)算法。Ramaswamy 等在此基礎(chǔ)上提出了改進(jìn)的基于距離的K-NN（kth nearest neighbor）[3]算法，該算法先計(jì)算每個(gè)點(diǎn)的到它的第K個(gè)最近鄰居的距離，然后進(jìn)行排序，把其中距離最大的n個(gè)點(diǎn)作為離群點(diǎn)。Angiulli和Pizzuti[4]提出了一種計(jì)算一個(gè)點(diǎn)P的前k個(gè)最近鄰居距離之和的算法，距離和越大則該點(diǎn)為離群點(diǎn)的程度越高。由于基于距離的算法無(wú)法識(shí)別數(shù)據(jù)集中的局部離群點(diǎn)，Breunig 等人提出了一種基于密度的LOF 算法[5]，主要思想是通過(guò)把每個(gè)點(diǎn)的密度和它Mints 鄰域的平均密度比值作為該點(diǎn)的局部離群因子，離群因子的值越大則離群程度越高。在KNN 算法的基礎(chǔ)上同時(shí)發(fā)展出了一類(lèi)基于KNN 圖的算法，如Ville Hautamaki 等人提出的基于KNN 圖的ODIN 算法[6]，它是通過(guò)連接每個(gè)點(diǎn)的K個(gè)最近鄰居形成一個(gè)稀疏的有向的KNN 圖，然后計(jì)算每個(gè)點(diǎn)的入度數(shù)檢測(cè)離群點(diǎn)。

在上述的算法中都存在一個(gè)前提條件，就是需要提供每個(gè)數(shù)據(jù)對(duì)象擁有的鄰居個(gè)數(shù)即參數(shù)k的值，它的選擇通常是依靠用戶的經(jīng)驗(yàn)和大量的實(shí)驗(yàn)決定的，對(duì)于不同的數(shù)據(jù)集，k的取值沒(méi)有可借鑒性。為了解決這個(gè)問(wèn)題，本文使用了空間鄰居的概念，它是直接把每個(gè)數(shù)據(jù)對(duì)象所處的空間上相鄰的點(diǎn)作為鄰居，因而不同于k最近鄰，無(wú)需人工設(shè)置鄰居的個(gè)數(shù)。空間鄰居可以由Delaunay三角剖分算法產(chǎn)生，在Delaunay三角剖分圖中，每個(gè)點(diǎn)與它空間上相鄰的點(diǎn)都存在一條邊相連接，根據(jù)這個(gè)特點(diǎn)，本文提出了一種無(wú)需參數(shù)的基于Delaunay 圖的離群點(diǎn)檢測(cè)算法。

2 Delaunay 三角剖分

Delaunay 三角剖分算法在數(shù)值分析（比如有限元分析）以及圖形學(xué)中是一個(gè)非常重要的理論基礎(chǔ)，可以用來(lái)建立數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)，通過(guò)所建立的連通圖反映數(shù)據(jù)對(duì)象之間的相似性關(guān)系[7]。Delaunay 三角剖分的結(jié)構(gòu)良好，能夠適應(yīng)各種分布密度的數(shù)據(jù)，目前已經(jīng)有了很多成熟的實(shí)現(xiàn)算法。Steven Fortune 提出了一種時(shí)間復(fù)雜度為O(NlogN)的三角網(wǎng)構(gòu)建算法[8]。由于此算法針對(duì)于2 維平面的，并不適合于高維數(shù)據(jù)集，P Cignonit 等人則提出了一種d維空間中的快速的Delaunay 三角網(wǎng)構(gòu)建算法[9]。Delaunay 三角網(wǎng)的應(yīng)用方面也取得了很多成果，如Yi Xiao和Hong Yan[10]實(shí)現(xiàn)了應(yīng)用Delaunay 三角網(wǎng)對(duì)文檔圖像中的文字區(qū)域進(jìn)行提取。Dongquan Liu[11]等人提出了基于Delaunay 三角剖分的邊緣點(diǎn)檢測(cè)算法。Vladimir Estivill-Castro[12]等人利用三角剖分的特性實(shí)現(xiàn)了對(duì)數(shù)據(jù)集的聚類(lèi)。

圖1 delaunay 三角剖分

如圖1 實(shí)線部分形成的圖形為Delaunay 三角剖分，虛線部分為Voronoi 圖（又稱(chēng)泰森多邊形），它們互為對(duì)偶關(guān)系，圖中每個(gè)頂點(diǎn)為泰森多邊形的生長(zhǎng)中心，連接其中相鄰的具有公共邊的泰森多邊形的中心而形成的三角網(wǎng)圖即為Delaunay 三角剖分。在圖中每個(gè)數(shù)據(jù)點(diǎn)和它空間上相鄰的點(diǎn)之間都有邊相連；任意三角形的外接圓不能包含其他數(shù)據(jù)點(diǎn)，如果在d維空間中，則相當(dāng)于每一個(gè)單純形的外接超球面中都不包含其他的點(diǎn)。從三角剖分圖中可以有效地反映數(shù)據(jù)點(diǎn)之間的相似性關(guān)系。

3 基于Delaunay 三角剖分的離群點(diǎn)檢測(cè)算法

本文算法的主要思想是首先建立數(shù)據(jù)集對(duì)應(yīng)的Delaunay 三角剖分，任意數(shù)據(jù)集對(duì)應(yīng)著唯一的Delaunay三角剖分圖[13]，遍歷此圖獲取每個(gè)數(shù)據(jù)對(duì)象直接相連的鄰居，形成每個(gè)點(diǎn)的空間鄰域關(guān)系。然后結(jié)合每個(gè)點(diǎn)偏離它的鄰居點(diǎn)的程度和它所在區(qū)域分布的稀疏程度，提出了一種新的離群因子的定義，離群因子的大小決定了每個(gè)點(diǎn)的離群程度。

假設(shè)數(shù)據(jù)集D={X1，X2，…，Xn}，任意點(diǎn)?p∈D。

定義1Delaunay 三角剖分圖G(V，E)：

圖G(V，E)為通過(guò)Delaunay 三角剖分算法形成的三角圖。

定義2空間鄰居Ne(p)：

在數(shù)據(jù)集D對(duì)應(yīng)的Delaunay 圖中，點(diǎn)p的空間鄰居則為與點(diǎn)p直接相連的點(diǎn)。即Ne中所有的點(diǎn)和點(diǎn)p之間都存在一條邊直接相連。

定義3點(diǎn)p的平均鄰域距離mean(p)：

mean(p)是點(diǎn)p到與它直接相連的鄰居點(diǎn)距離的平均值，可以反映點(diǎn)p附近分布的密度，distance(p，q)是求點(diǎn)p與點(diǎn)q之間的歐式距離。

定義4點(diǎn)p的相對(duì)離群度ROF(p)：

ROF(p)為點(diǎn)p相對(duì)于它所有鄰居點(diǎn)的離群度的平均值，其中，PROF(p，q)表示點(diǎn)p相對(duì)于點(diǎn)q的離群程度，滿足點(diǎn)q是點(diǎn)p的鄰居點(diǎn)，即q∈Ne(p)。

如圖2 所示，點(diǎn)p5 相對(duì)于點(diǎn)p3 的離群度為p5 到p3 的距離和p3 到它的鄰居點(diǎn)p1，p2，p4 的距離的平均值的比值；p5 的相對(duì)離群度ROF(p)值則為點(diǎn)p5 相對(duì)于p2，p3，p4 的離群度的平均值。從圖中可以看出相對(duì)離群度的定義能夠有效地表示每個(gè)點(diǎn)相對(duì)于它的鄰居點(diǎn)的離群程度。

圖2 相對(duì)離群度描述

定義5點(diǎn)p的離群因子DBOF(p)：

任意點(diǎn)p的離群因子定義為規(guī)范化后的該點(diǎn)的平均鄰域距離和相對(duì)離群度之和。

maxmean，minmean分別為數(shù)據(jù)集中所有點(diǎn)的平均鄰域距離的最大值和最小值，同樣maxROF，minROF分別為相對(duì)離群度的最大值和最小值。由上定義可知，每個(gè)點(diǎn)的離群因子是由它的平均鄰域距離和相對(duì)離群度共同決定的，通常平均鄰域距離越大說(shuō)明該點(diǎn)分布越稀疏，因此為離群點(diǎn)的可能性也就越大。相對(duì)離群度則反映了一個(gè)點(diǎn)偏離它鄰居點(diǎn)的程度，如果一個(gè)點(diǎn)到它的鄰居的距離越大，鄰居點(diǎn)所在區(qū)域分布越密集，則該點(diǎn)的離群因子也就越大，說(shuō)明該點(diǎn)偏離它的鄰居節(jié)點(diǎn)的程度也就越大。因此把這兩個(gè)特征結(jié)合起來(lái)定義可以使離群因子包含的信息更加完備。

圖3 為包含離群點(diǎn)的三角剖分圖，標(biāo)記了幾個(gè)處于不同位置的頂點(diǎn)，由圖中可知點(diǎn)p1為一個(gè)離群點(diǎn)，p1到它的鄰居點(diǎn)p2 的距離很大，點(diǎn)p2 與它鄰居點(diǎn)（p1除外）距離較小，所以p1 相對(duì)于鄰居點(diǎn)p2 的離群度也就很大，由此可知它的相對(duì)離群度較大，并且點(diǎn)p1 的平均鄰域距離也很大，所以點(diǎn)p1 的離群因子DBOF(p1) 較大；圖中點(diǎn)p2 處于中間聚類(lèi)的邊界位置，p3 處于內(nèi)部分布密集的區(qū)域，p4 處于內(nèi)部分布稀疏的區(qū)域。分析它們的離群因子發(fā)現(xiàn)，邊緣點(diǎn)p2 的離群因子小于離群點(diǎn)，大于內(nèi)部點(diǎn)p3，p4；由于點(diǎn)p4 處于分布稀疏的區(qū)域，因此相對(duì)于p3 擁有較大的平均鄰域距離，所以點(diǎn)p4 的離群因子大于p3；點(diǎn)p3 為離群點(diǎn)的可能性則最低。

圖3 包含離群點(diǎn)的Delaunay 三角剖分圖

通過(guò)對(duì)圖3 的分析可以發(fā)現(xiàn)離群因子DBOF 的定義能夠有效地表示每個(gè)點(diǎn)的離群程度，其值越大說(shuō)明該點(diǎn)偏離其鄰居點(diǎn)越遠(yuǎn)，離群程度越高。具體算法如下：

輸入：數(shù)據(jù)集D

輸出：top-n離群點(diǎn)

步驟1使用Delaunay 三角剖分算法建立數(shù)據(jù)集D對(duì)應(yīng)的Delaunay 三角剖分圖G(V，E)。

步驟2遍歷圖G，獲取每個(gè)點(diǎn)的鄰接關(guān)系表。

步驟3從數(shù)據(jù)集中任意取一個(gè)未訪問(wèn)的點(diǎn)p，獲取它的鄰居點(diǎn)集合Ne(p)，并標(biāo)記此點(diǎn)為已訪問(wèn)。

步驟4計(jì)算點(diǎn)p到Ne(p)中所有點(diǎn)的距離的平均值mean(p)。

步驟5依次計(jì)算點(diǎn)p相對(duì)Ne(p)中每個(gè)點(diǎn)q的離群度PROF(p，q)，然后取它們的平均值得到點(diǎn)p的相對(duì)離群因子ROF(p)。

步驟6重復(fù)步驟3 到步驟5 直到數(shù)據(jù)集中所有的點(diǎn)都訪問(wèn)完畢，執(zhí)行下一步。

步驟7遍歷數(shù)據(jù)集，計(jì)算每個(gè)點(diǎn)平均鄰域距離mean 和相對(duì)離群度ROF 的最大最小值。

步驟8根據(jù)定義5，按最小-最大規(guī)范化原則處理所有點(diǎn)p∈D的平均鄰域距離mean(p) 和相對(duì)離群度ROF(p)，然后把規(guī)范化后的值求和作為該點(diǎn)的離群因子DBOF(p)。

步驟9按DBOF 的值降序排列，輸出離群因子最大的前n個(gè)離群點(diǎn)。

4 時(shí)間復(fù)雜度分析

生成Delaunay 三角剖分圖算法時(shí)間復(fù)雜度最壞的情況下為O(N2)，目前已有很多改進(jìn)的算法可以把時(shí)間復(fù)雜度優(yōu)化到O(N×lgN)，其中N為數(shù)據(jù)集的大?。凰惴ㄖ杏?jì)算所有點(diǎn)的平均鄰域距離的時(shí)間復(fù)雜度O(k×N)其中k值為每個(gè)點(diǎn)的空間鄰居數(shù)目，在Delaunay 三角剖分圖中該值通常為一個(gè)較小的常數(shù)。計(jì)算所有點(diǎn)的相對(duì)離群度時(shí)間復(fù)雜度為O(k×N)，根據(jù)已知條件計(jì)算所有點(diǎn)的相對(duì)離群度需要的時(shí)間復(fù)雜度為O(N)。因此本文算法總的時(shí)間復(fù)雜度為O(N×lgN)+O(k×N)+O(k×N)+O(N)。

5 實(shí)驗(yàn)

為了驗(yàn)證算法的準(zhǔn)確性，分別以合成數(shù)據(jù)和真實(shí)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，同時(shí)選擇了傳統(tǒng)的基于距離的KNN 算法，基于密度的LOF 算法，和Ke Zhang[14]等人提出的一種新的基于密度的LDOF 算法進(jìn)行了對(duì)比實(shí)驗(yàn)。該算法的實(shí)驗(yàn)環(huán)境為：I3 2.4 GHz CPU，內(nèi)存為2 GB，操作系統(tǒng)為Windows XP，算法的編寫(xiě)使用Matlab。

由于LOF 算法的檢測(cè)結(jié)果依賴(lài)于設(shè)置合適參數(shù)MinPts，KNN 算法依賴(lài)于參數(shù)K的設(shè)置，不同的參數(shù)值會(huì)對(duì)算法結(jié)果產(chǎn)生較大影響，本文的結(jié)果則是選取的多次實(shí)驗(yàn)得出最好的值。

圖4 為本文算法在人工數(shù)據(jù)集上對(duì)應(yīng)的檢測(cè)結(jié)果，圖中有3 個(gè)聚類(lèi)，構(gòu)造了9 個(gè)處于不同位置的離群點(diǎn)，本文算法與KNN，LOF 和LDOF 算法一樣能夠準(zhǔn)確地識(shí)別圖中的離群點(diǎn)。

圖4 人工數(shù)據(jù)集

為了測(cè)試算法在真實(shí)數(shù)據(jù)集上的準(zhǔn)確度，從UCI 標(biāo)準(zhǔn)數(shù)據(jù)集中選取了Iris Plants 數(shù)據(jù)集，wine 數(shù)據(jù)集，以及breast-cancer數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。

表1 為實(shí)驗(yàn)數(shù)據(jù)集的基本屬性，由于它們都是用于分類(lèi)的數(shù)據(jù)集，并不包含離群點(diǎn)，為了適用于本文算法，分別對(duì)每個(gè)數(shù)據(jù)集做了預(yù)處理，移除數(shù)據(jù)集中的某個(gè)分類(lèi)，并從中取出部分?jǐn)?shù)據(jù)點(diǎn)作為離群點(diǎn)插入新的數(shù)據(jù)集中。wine 數(shù)據(jù)集包含了3 個(gè)分類(lèi)，把其中分類(lèi)3 中的數(shù)據(jù)移除，并從中選取9 條記錄作為離群點(diǎn)插入數(shù)據(jù)集中；Iris Plants 包含了同樣3 個(gè)分類(lèi)Setosa，Versicolour，Virginica，共150條數(shù)據(jù)。把其中的Setosa類(lèi)別中的數(shù)據(jù)減少至9 條作為離群點(diǎn)。breast-cancer 數(shù)據(jù)由10 個(gè)屬性組成，包含了699 條診斷記錄，分為Benign 和Malignant 2 個(gè)類(lèi)別，把其中Malignant 類(lèi)數(shù)據(jù)減少至39 條作為離群數(shù)據(jù)。

表1 不同數(shù)據(jù)集信息

為了評(píng)估算法的結(jié)果，引入了離群誤差率檢測(cè)指標(biāo)[15]（Outlier Error Rate，OER）。

其中SO表示算法輸出的離群點(diǎn)的個(gè)數(shù)，RSO表示算法所檢測(cè)出的正確的離群點(diǎn)的個(gè)數(shù)，DO表示數(shù)據(jù)集的個(gè)數(shù)。

圖5 （a）wine數(shù)據(jù)集

圖5 （b）iris數(shù)據(jù)集

圖5 （c）breast-cancer數(shù)據(jù)集

在圖中，離群點(diǎn)檢測(cè)的誤差率都是隨輸出離群點(diǎn)個(gè)數(shù)的增加而表現(xiàn)出上升的趨勢(shì)，通過(guò)實(shí)驗(yàn)對(duì)比后，發(fā)現(xiàn)本文算法在給出3 個(gè)真實(shí)數(shù)據(jù)集上的檢測(cè)誤差率總體上都要低于KNN、LOF 和LDOF 算法，說(shuō)明在離群點(diǎn)檢測(cè)準(zhǔn)確度上是要高于其他算法的。同時(shí)由于KNN 和LOF 算法檢測(cè)結(jié)果是在設(shè)置不同參數(shù)經(jīng)過(guò)多次實(shí)驗(yàn)后取得的，而本文算法則無(wú)需參數(shù)并且具有良好的檢測(cè)效果。從上述結(jié)論可以得出本文算法是明顯優(yōu)于其他算法的。

6 結(jié)束語(yǔ)

Delaunay 三角剖分圖在圖形學(xué)中已經(jīng)有了很多成熟的應(yīng)用，但是在離群點(diǎn)檢測(cè)方面的應(yīng)用成果還比較少，本文利用Delaunay 三角剖分形成的空間鄰居性質(zhì)提出了一種新的離群點(diǎn)檢測(cè)算法，并在實(shí)驗(yàn)中取得了良好的檢測(cè)效果，有效地減少了參數(shù)對(duì)于離群點(diǎn)檢測(cè)結(jié)果的影響。由于本文算法的效率依賴(lài)于Delaunay 三角剖分算法，因此選擇一個(gè)高效的Delaunay 三角剖分算法會(huì)有利于本文算法性能的提升。

[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，F(xiàn)ranti P.Outlier detection using k-nearest neighbour graph[C]//Proceedings of the 17th International Conference on Pattern Recognition.IEEE，2004，3：430-433.

[7] 邱保志，許敏.無(wú)參數(shù)聚類(lèi)邊界檢測(cè)算法的研究[J].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，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在離群數(shù)據(jù)挖掘中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（7）：128-130.