基于K-均值聚類和泰森多邊形的異常值檢測方法

孫　添，何國良

(電子科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 四川　成都　611731)

?

基于K-均值聚類和泰森多邊形的異常值檢測方法

孫添，何國良

(電子科技大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 四川成都611731)

[摘要]離群點發(fā)現(xiàn)是數(shù)據(jù)挖掘研究的一個重要方面.根據(jù)數(shù)據(jù)流的特點提出一種基于K-均值聚類和泰森多邊形的離群點檢測方法，先用K-均值對數(shù)據(jù)進行處理，生成中間聚類結(jié)果，然后用泰森多邊形方法(VOD)對這些中間結(jié)果進行再次選擇，最后找出可能存在的離群點.

[關(guān)鍵詞]異常值檢測；K-均值聚類；泰森多邊形；數(shù)據(jù)挖掘

數(shù)據(jù)挖掘任務(wù)一般可以分4類：(a)依賴性檢驗；(b)類別鑒定；(c)類別描述；(d)異常檢測.前面3種任務(wù)與數(shù)據(jù)集合大部分對象中的模式有關(guān).絕大多數(shù)的數(shù)據(jù)挖掘比如分類、關(guān)聯(lián)規(guī)則等都是這3類任務(wù)的范疇；但其中的第4類任務(wù)主要是研究數(shù)據(jù)集中的一小部分內(nèi)容，而這一小部分不符合數(shù)據(jù)集的一般模型或規(guī)則，這些數(shù)據(jù)對象叫做異常點.很多挖掘方法將其看成噪聲丟掉，而在另一些應(yīng)用如保險欺詐檢驗中，關(guān)于異常點的檢測在這種情況下就成為相當(dāng)重要的事情.

近年來，一種被稱為數(shù)據(jù)流的新型數(shù)據(jù)形式在相當(dāng)多的領(lǐng)域中出現(xiàn)，如通話記錄等.數(shù)據(jù)流在通常情況下是一個有序的數(shù)據(jù)序列x2,…，xi,…,xn(xi為數(shù)據(jù)點).這些數(shù)據(jù)按i遞增的順序只能訪問少量的幾次甚至一次.

本文提出的異常值檢測方法是一種適應(yīng)流數(shù)據(jù)特點，并且對數(shù)據(jù)分區(qū)是使用K-均值聚類方法來實現(xiàn)的，將在內(nèi)存中保存著每個部分生成的k個聚類點.為了適應(yīng)內(nèi)存容量的限制丟掉了每部分剩余的數(shù)據(jù)點，并且采用一種非參數(shù)方法查找異常用于累積存儲于內(nèi)存中的點上.這樣能降低參數(shù)對異常值檢測的影響，因而能更好地將數(shù)據(jù)中的異常值找出.之前的一些文獻用到聚類算法，在檢測異常值時又引入其他閾值作為判斷的依據(jù)，使得算法對參數(shù)的依賴性很大；而本文對于異常值的判定選取非參數(shù)檢測方法，使得算法只受聚類參數(shù)k的影響，從而使得算法效率更高.

1相關(guān)知識

1.1離群點定義

對離群點的定義不一樣的檢測方法存在一定的差別，但Hawkins給出的形式化定義被研究者廣泛接受并成為研究離群點問題的基礎(chǔ)[1].

如果一個數(shù)據(jù)樣本與其他樣本之間存在足以引起懷疑的差異，則被稱為離群點，Hawkins的定義形象地描述了離群點的特征.

1.2k-means聚類算法

k-means聚類僅僅是諸多劃分聚類方法中的一種.其主要流程為：(1)隨機選擇K個數(shù)據(jù)作為N個文檔初始聚類中心點；(2)對剩余的每個數(shù)據(jù)計算它到初試聚類中心點的距離，并把它歸到最近的聚類中心點；(3)將已經(jīng)得到的各類聚類中心點進行重新計算；(4)重復(fù)(2)、(3)，直到聚類中心點不再變化，然后記最終的聚類中心點為(si,ti).

1.3數(shù)據(jù)流離群點檢測

數(shù)據(jù)流數(shù)據(jù)與傳統(tǒng)的數(shù)據(jù)挖掘?qū)ο笙啾?，?shù)據(jù)流數(shù)據(jù)隨著時間動態(tài)增加，數(shù)據(jù)量不斷增大等.這些特點使得數(shù)據(jù)流異常點檢測的方法需要滿足下面的要求：

1)算法可以在小空間上運行

這是數(shù)據(jù)流挖掘面臨的首要困難，主要是由于數(shù)據(jù)量隨時間的不斷增加，離群點檢測針對所有存儲下來的數(shù)據(jù)來進行是不大現(xiàn)實的，故將有限的存儲空間對“無限”的數(shù)據(jù)流進行處理對于數(shù)據(jù)流異常值檢測算法是可行的.

2)算法只能掃描數(shù)據(jù)少量幾次甚至一次

伴隨時間的推移，使用不斷添加到數(shù)據(jù)流的新的數(shù)據(jù)代替以前存儲器中儲存的數(shù)據(jù)，這樣就使得算法需要只對數(shù)據(jù)進行少量幾次訪問甚至一次.

2離群點檢測方法

之前有人提出了一種基于K-均值聚類的流數(shù)據(jù)離群點發(fā)現(xiàn)方法[2].該方法首先在數(shù)據(jù)流分區(qū)接著使用K-均值聚類產(chǎn)生中間聚類結(jié)果(均值參考點集)，之后再利用非參數(shù)方法對這些參考點找出潛在的離群點.借鑒該種算法，文獻[3]提出用K-均值聚類結(jié)合凝聚聚類查找離群點方法，一開始將K-均值聚類應(yīng)用在各時段內(nèi)的數(shù)據(jù)流來生成對應(yīng)的中間均值點集，然后對這些中間均值點應(yīng)用凝聚聚類進行分析，查找出那些可能存在的異常值.

根據(jù)上面兩種方法的思路，本文提出基于K-均值聚類并使用VOD離群點檢測方法.這個方法的主要步驟是：第一步，將數(shù)據(jù)流進行分區(qū)，然后做K-均值聚類生成相應(yīng)的聚類中心點集；第二步，利用泰森多邊形的方法來對這些中間均值點進行異常值的判斷.相對于之前的方法，在查找異常點的過程中不再引入新的參數(shù)，使得算法對參數(shù)的影響變小.

2.1相關(guān)定義

VOD方法的原理

Voronoi圖是一種用來描述點集鄰近關(guān)系的一種數(shù)據(jù)結(jié)構(gòu).給定M個點的集合S，點集S的Voronoi圖把平面劃分成M個區(qū)域.一般地，將Voronoi圖的點稱作Voronoi頂點，線段稱作Voronoi邊，如圖1所示.

圖1　Voronoi圖

在點S集的Voronoi圖中，給定pS ,V(pi)只包含S中的一個點.所以，相對于V(pi)多邊形范圍內(nèi)的其他任意一個點來講，其到pi的距離比到S中其他頂點的距離都要小.也就是,?j≠i}.其中，dist()是歐氏距離.

Voronoi圖上，任意pi的每一個鄰近點確定Voronoi多邊形V(pi)的一條邊；反過來說，可以通過V(pi)的邊找出pj的所有鄰近點，記為VN(pi).如圖1所示，p2的鄰近點是p2、p3、p4、p5、p6.

根據(jù)Voronoi圖的性質(zhì)，對于點集中S任一個點pi，根據(jù)pi的Voronoi多邊形V(pi)確定它的鄰近點，再計算pi到其所有的鄰近點平均距離，記為Vd(pi)，作為pi的近鄰分布密度，即：

(1)

Vd(pi)可以很客觀地反映點周圍pi的分布密度，故對于異常點來說，其鄰近點與它的距離比較大，Vd(pi)也就比較大.如果將Vd(pi)按從大到小的順序排列，那么Vd(pi)較大的點就可能是異常點.

2.2算法思想

以下對本文提出的算法思想進行闡述.首先對數(shù)據(jù)流進行分區(qū)，把順序的m個數(shù)據(jù)點來形成一個劃分，接著將K-均值聚類應(yīng)用在每一個劃分中的m個數(shù)據(jù)點上，并把產(chǎn)生的k個聚類中心點保存為ki(si，ti)的數(shù)據(jù)類型；然后構(gòu)造k個ki的Voronoi圖，計算每一點的V-鄰近分布密度Vd(pi)，根據(jù)Vd(pi)的大小來判斷數(shù)據(jù)流中的異常值.數(shù)據(jù)流離群點檢測過程一直到某一時刻內(nèi)的數(shù)據(jù)已經(jīng)全部遍歷后才會結(jié)束.算法流程如下：

圖2　算法流程

2.3算法時間復(fù)雜性分析

算法的過程是由兩部分組成：一是分割數(shù)據(jù)，分割是將連續(xù)的m個數(shù)據(jù)點看作一個劃分，將K-均值聚類應(yīng)用在每一個劃分上的m個數(shù)據(jù)點所生成的聚類中心點的開銷；對k個ki利用VOD方法檢測異常值的開銷.

在大數(shù)據(jù)集上應(yīng)用k-means算法，優(yōu)點主要表現(xiàn)為算法的可伸縮性比較好，而時間復(fù)雜度為O(tkn)，其中t是算法實現(xiàn)時迭代的次數(shù)，k是事先限定好的簇的個數(shù)，n則是數(shù)據(jù)集合里面數(shù)據(jù)點的個數(shù).通常情況下，k?n和t?n.由于對每個劃分塊上的m個數(shù)據(jù)點進行K-均值聚類，因此這一步的時間消耗復(fù)雜度為O(mkn).如果數(shù)據(jù)點的個數(shù)m取值比較小，那么相對應(yīng)的迭代次數(shù)t也會相應(yīng)比較小.

3實驗分析

本節(jié)通過實驗來分析算法的效率和有效性.使用二維模擬數(shù)據(jù)集來測試算法對離群點的檢測效果，模擬數(shù)據(jù)如圖3所示.生成的方法是在矩形區(qū)域內(nèi)產(chǎn)生1 000個符合N(4.0,1.0)的正態(tài)分布的點，然后再產(chǎn)生1 000個均勻分布(x2+y2≤1)的隨機點，最后加入10個異常數(shù)據(jù)點在空白區(qū)域.

圖3　實驗數(shù)據(jù)集

對算法進行實驗，實驗結(jié)果如表1所示.

表1　實驗結(jié)果

由圖2可知，先采用聚類算法，使得數(shù)據(jù)量急劇減少，再對生成的數(shù)據(jù)點進行異常值檢測，但由于k值不同，異常點檢測方法的效果受到一定影響，檢測出來的異常值的數(shù)目不同.當(dāng)k為某一個恰當(dāng)值時，可以很好地找出全部的異常值.

采用文獻[2]提出的方法來查找異常值，查找結(jié)果如表2.

表2　對比試驗結(jié)果

此方法也能找出異常值，但在判定異常值的過程中引入新的閾值，使得算法受到兩個參數(shù)的影響，而非參數(shù)的方法查找異常值所受到的限制更小，查找準(zhǔn)確率更高.雖然該算法對異常值的檢測與k值有關(guān)，主要是K-均值聚類的效果受k的值影響較大.但在異常值檢測中，泰森多邊形是一種非參數(shù)檢測，因此本算法只受k值影響.

4結(jié)語

K-均值聚類的聚類結(jié)果比較不穩(wěn)定，即使對于同樣輸入?yún)?shù)聚類結(jié)果也可能完全不一樣.本文提出一種基于K-均值聚類和泰森多邊形的離群點檢測查找方法，在K-均值聚類的基礎(chǔ)上增加泰森多邊形使算法更加穩(wěn)定.對于點的個數(shù)很多的情況，我們第一時間可以排除其為異常值，對其他的點進行異常值檢測，提高了效率.理論分析與實驗結(jié)果表明，算法是有效、可行的.

[參考文獻]

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

[2]倪巍偉，陸介平，陳耿，等.基于均值分區(qū)的數(shù)據(jù)流離群點檢測算法[J].計算機研究與發(fā)展，2006,43(9)：1639-1643.

[3]曾穎，羅可，鄒瑞芝.基于K-均值聚類和凝聚聚類的離群點查找方法[J].計算機工程與應(yīng)用，2009，45(29)：131-133.

[4]QUJL，QINW，SAIY，F(xiàn)ENGYM.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.

(責(zé)任編輯穆剛)

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

[文獻標(biāo)志碼]A

[文章編號]1673-8004(2016)02-0010-04

[作者簡介]孫添(1990—)，女，河北保定人，碩士，主要從事數(shù)據(jù)分析方面的研究.

[基金項目]國家自然科學(xué)基金項目(11371288)；國家留學(xué)基金項目.

[收稿日期]2015-06-17