基于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