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

孫　添，何國良

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

?

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

孫添，何國良

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

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

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

數(shù)據(jù)挖掘任務(wù)一般可以分4類：(a)依賴性檢驗(yàn)；(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ù)對象叫做異常點(diǎn).很多挖掘方法將其看成噪聲丟掉，而在另一些應(yīng)用如保險欺詐檢驗(yàn)中，關(guān)于異常點(diǎn)的檢測在這種情況下就成為相當(dāng)重要的事情.

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

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

1相關(guān)知識

1.1離群點(diǎn)定義

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

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

1.2k-means聚類算法

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

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

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

1)算法可以在小空間上運(yùn)行

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

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

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

2離群點(diǎn)檢測方法

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

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

2.1相關(guān)定義

VOD方法的原理

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

圖1　Voronoi圖

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

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

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

(1)

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

2.2算法思想

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

圖2　算法流程

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

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

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

3實(shí)驗(yàn)分析

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

圖3　實(shí)驗(yàn)數(shù)據(jù)集

對算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示.

表1　實(shí)驗(yàn)結(jié)果

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

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

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

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

4結(jié)語

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

[參考文獻(xiàn)]

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

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

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

[4]QUJL，QINW，SAIY，F(xiàn)ENGYM.Anonparametricoutlierdetectionmethodforfinancialdata[C].Proceedingsofthe16thIEEEInternationalConferenceonManagementScience&Egneering,2009:1442-1447.

[5]黃天強(qiáng)，秦小麟，葉躍飛.基于方形鄰域的離群點(diǎn)的查找新方法[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

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

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

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

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

[收稿日期]2015-06-17