基于聚類的離群點(diǎn)檢測(cè)

1、基于聚類的離群點(diǎn)檢測(cè)方法Rajendra Pamula, Jatindra Kumar Deka, Sukumar NandiDepartment of Computer Science and EngineeringIndian Institute of Technology GuwahatiGuwahati, Assam, IndiaEmail: iitg.ac.in摘要:本論文提出來(lái)一個(gè)聚類方法用以檢測(cè)離群點(diǎn)。通過(guò)使用k均值聚類算法來(lái)從數(shù)據(jù)集中劃分聚類。離聚類中心比較近的點(diǎn)不太可能是離群點(diǎn)，同時(shí)我們可以從聚類中去除掉這些點(diǎn)。接下來(lái)計(jì)算剩下的點(diǎn)和離群點(diǎn)的距離。需要計(jì)算的離群點(diǎn)度的降低可能是

2、由于一些點(diǎn)的去除。我們聲明離群度最高的點(diǎn)作為離群點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)使用真實(shí)數(shù)據(jù)集，并論證得知，即使所計(jì)算的數(shù)據(jù)比較少，但所提出的方法比現(xiàn)存的方法優(yōu)越。關(guān)鍵字:離群點(diǎn)；聚類；基于距離；1.引言離群點(diǎn)是和數(shù)據(jù)集中正常點(diǎn)不一致的數(shù)據(jù)點(diǎn)。離群點(diǎn)檢測(cè)在數(shù)據(jù)清理中有重要的應(yīng)用，像欺詐檢測(cè)，入侵檢測(cè)，營(yíng)銷，傳感網(wǎng)絡(luò)，垃圾郵件檢測(cè)。在數(shù)據(jù)點(diǎn)中找出異常點(diǎn)是離群點(diǎn)檢測(cè)的基礎(chǔ)理論。離群點(diǎn)檢測(cè)暗示對(duì)象脫離給定的數(shù)據(jù)集。離群點(diǎn)的檢測(cè)已經(jīng)廣泛地在統(tǒng)計(jì)領(lǐng)域研究。典型地就是用戶需要使用統(tǒng)計(jì)分布對(duì)數(shù)據(jù)點(diǎn)建模，同時(shí)一個(gè)點(diǎn)被劃為離群點(diǎn)主要看其和假定模型的關(guān)聯(lián)。這些技術(shù)的主要問(wèn)題是許多情況下用戶可能對(duì)基礎(chǔ)數(shù)據(jù)分布沒(méi)有足夠的了解。特別是對(duì)數(shù)

3、據(jù)集中的每一對(duì)關(guān)聯(lián)對(duì)象使用距離函數(shù)的基于距離的技術(shù)?；诰嚯x的定義描述了一個(gè)對(duì)數(shù)據(jù)分析有效的工具。這些定義以計(jì)算的方式是有效率的，而在部分已經(jīng)檢測(cè)的數(shù)據(jù)集中基于距離的離群點(diǎn)的得分是單調(diào)非遞增函數(shù)。最近幾年已經(jīng)提出了許多快速檢測(cè)基于距離的離群點(diǎn)算法。一些算法在CPU消耗上比較有效，而其他一些主要是側(cè)重于I/O消耗。許多方法用來(lái)查找偏離其他點(diǎn)的某個(gè)點(diǎn)，這意味著這個(gè)點(diǎn)是離群點(diǎn)。眾所周知，數(shù)據(jù)集中的離群點(diǎn)是相當(dāng)少的。因此也沒(méi)必要為所有點(diǎn)提供這些方法。通過(guò)移除可能不是離群點(diǎn)的這些都，我們可以降低計(jì)算時(shí)間。我們的工作是使用聚類和距離函數(shù)來(lái)區(qū)別那些不是離群點(diǎn)的點(diǎn)，然后去除這些點(diǎn)。接下來(lái)為所有剩余的點(diǎn)預(yù)測(cè)基于

4、距離的方法，這些方法使用一個(gè)參數(shù)來(lái)區(qū)別一個(gè)點(diǎn)是不是離群點(diǎn)。我們假設(shè)數(shù)據(jù)集中有n個(gè)離群點(diǎn)，然后通過(guò)我們的方法得出的前n個(gè)點(diǎn)作為離群點(diǎn)。我們使用基于距離的局部離群系數(shù)來(lái)區(qū)別離群點(diǎn)。2.相關(guān)工作Knorr and Ng是第一個(gè)提出基于距離的離群點(diǎn)檢測(cè)方法。如果數(shù)據(jù)集中至少有pct部分對(duì)象和對(duì)象p的距離大于D,則對(duì)象p是一個(gè)基于距離的關(guān)于參數(shù)pct和D的離群點(diǎn)即DB（pct,D）離群點(diǎn)。這個(gè)定義被廣泛接受，因?yàn)樗鼩w納了許多統(tǒng)計(jì)離群的測(cè)試。Ramaswamy等人提出了以上定義的擴(kuò)展。所有點(diǎn)根據(jù)離群度劃分。給定兩個(gè)變量kn和w，如果Dk中比p有更高價(jià)值的對(duì)象數(shù)少于w，則對(duì)象p被認(rèn)為是離群點(diǎn)，其中Dk表示對(duì)

5、象p的第k個(gè)最近鄰的距離。隨后，Angiulli 和Pizzuti提出了一個(gè)通過(guò)考慮全部對(duì)象領(lǐng)域來(lái)決定離群點(diǎn)的方法。所有點(diǎn)的劃分是基于第k個(gè)最近鄰距離的總和，而不是單獨(dú)考慮第k個(gè)最近鄰的距離。上述的三個(gè)定義是緊密相關(guān)的。Breuning等人提出了數(shù)據(jù)集中用以表示每個(gè)對(duì)象離群程度的局部離群系數(shù)。這是關(guān)于離群點(diǎn)離群程度的第一個(gè)概念。離群系數(shù)局限在僅考慮一個(gè)約束領(lǐng)域的每個(gè)對(duì)象。一個(gè)對(duì)象的局部離群系數(shù)可以通過(guò)和它的領(lǐng)域比較其密度。它比基于距離的方法有更強(qiáng)的模型能力，因?yàn)樗鼉H僅是基于對(duì)象本身的密度?；诿芏鹊姆椒ú荒苊鞔_地把對(duì)象歸類為離群點(diǎn)或者非離群點(diǎn)。Zhang等人提出了局部基于距離的離群點(diǎn)檢測(cè)方法。

6、基于距離的局部離群系數(shù)可以確定一個(gè)對(duì)象偏離其鄰域的程度。計(jì)算數(shù)據(jù)集中所有點(diǎn)的基于距離的局部離群系數(shù)，其復(fù)雜度為，其中N是數(shù)據(jù)集中點(diǎn)的個(gè)數(shù)。聚類方法有許多，像CLARANS,DBSCAN,BIRCH和CURE都能檢測(cè)離群點(diǎn)。然而，因?yàn)榫垲惙椒ǖ闹饕康氖前l(fā)現(xiàn)聚類，其發(fā)展是為了使聚類最優(yōu)化，而不是使離群點(diǎn)檢測(cè)最優(yōu)化。離群點(diǎn)的定義使用的是主觀的被這些算法檢測(cè)到的聚類。而基于距離的離群點(diǎn)定義則更加客觀并且聚類是怎樣在輸入的數(shù)據(jù)中被檢測(cè)出來(lái)的顯得相對(duì)獨(dú)立。目前關(guān)于離群點(diǎn)的工作主要是僅僅集中在識(shí)別方面，在文獻(xiàn)11中打算提供有意的知識(shí)，它是基于為什么一個(gè)待鑒定的離群點(diǎn)是異常的解釋。3.背景我們使用基于距離的

7、局部離群系數(shù)，它能表示一個(gè)點(diǎn)偏離其領(lǐng)域的程度。一個(gè)點(diǎn)的LDOF值高就意味著偏離其領(lǐng)域比較多，同時(shí)也就意味著可能是離群點(diǎn)。LDOF的計(jì)算如下：LDOF中的p，其定義如下：計(jì)算所有點(diǎn)LDOF值計(jì)算消耗比較大，但算法的復(fù)雜度是。我們嘗試在去除那些可能不是離群點(diǎn)的點(diǎn)時(shí)降低計(jì)算復(fù)雜度。4.基于局部離群點(diǎn)的剪枝這部分主要描述提出的算法，它是LDOF的改進(jìn)。在文獻(xiàn)18中提出的LDOF算法的主要缺點(diǎn)是計(jì)算消耗巨大。這是因?yàn)閿?shù)據(jù)集DS中的每個(gè)點(diǎn)都要計(jì)算其LDOF。而我們所關(guān)注的僅僅是離群點(diǎn)，它的數(shù)量是非常少的，對(duì)于所有點(diǎn)LDOF的計(jì)算用處較小，可以一起避免。我們使用K均值算法來(lái)對(duì)數(shù)據(jù)集進(jìn)行聚類。一旦聚類形成，則

8、計(jì)算每個(gè)聚類的半徑。去除那些離質(zhì)心的距離比半徑小的點(diǎn)。然后計(jì)算每個(gè)聚類中未被剪枝點(diǎn)的LDOF值。記錄擁有高LDOF值的前n個(gè)點(diǎn)作為離群點(diǎn)。A 簡(jiǎn)述基于剪枝算法的主要思想是首先對(duì)數(shù)據(jù)集進(jìn)行聚類，然后從聚類中剪去那些可能不是離群點(diǎn)的點(diǎn)。而離群點(diǎn)的數(shù)目n可能會(huì)很小，這種額外的前序步驟可以幫助去除不是離群點(diǎn)的點(diǎn)。算法1描述了我們查找離群點(diǎn)的方法。我們簡(jiǎn)要描述一下剪枝算法執(zhí)行所需要的步驟。(1)產(chǎn)生聚類：首先使用K均值聚類算法對(duì)整個(gè)數(shù)據(jù)集聚類，然后計(jì)算每個(gè)聚類的半徑。（2）剪枝：如果一個(gè)聚類包含的點(diǎn)比要求的離群點(diǎn)的數(shù)目要少，這個(gè)聚類就可以免去剪枝。為每個(gè)聚類剪枝：計(jì)算聚類中每個(gè)點(diǎn)離質(zhì)心的距離。如果距離比

9、半徑小，則去除該點(diǎn)。(3)估算離群點(diǎn)：計(jì)算所有聚類中未被剪枝的點(diǎn)的LDOF。則擁有高LDOF值的前n個(gè)點(diǎn)作為離群點(diǎn)。K均值算法復(fù)雜度為c*it*N，其中c是聚類的數(shù)目，it是重復(fù)計(jì)算的次數(shù)，N是數(shù)據(jù)點(diǎn)的數(shù)目。這個(gè)算法的總的復(fù)雜度是c*it*N+c*np+，其中np表示每個(gè)聚類中的點(diǎn)的平均個(gè)數(shù)，w表示剪枝后剩下的點(diǎn)所占的比率，這個(gè)值一般在0.4左右。聚類的數(shù)目c依賴與離群點(diǎn)的數(shù)目。然而c和it是比較小的，所以總得復(fù)雜度要小于。算法1 離群點(diǎn)檢測(cè)算法輸入：數(shù)據(jù)集DS，聚類數(shù)c，重復(fù)次數(shù)it，離群點(diǎn)個(gè)數(shù)n1.使用K均值聚類算法得到聚類,得到Y(jié)2.for each cluster do3. 4.end

10、 for5.if |Cj|n then6. for each point piCj do7. if distance(pi,oj)Radiusj then8. prune(pi)9. else10. Add pi to U11. end if12. end for13.else14. for each point piCj do15. Add pi to U16. end for17.end if 18.for each point piU do19. 計(jì)算 LDOF(pi)20.end for21.根據(jù)LDOF的值對(duì)所有點(diǎn)進(jìn)行排序22.擁有高LDOF值得前n個(gè)點(diǎn)作為離群點(diǎn)B.實(shí)驗(yàn)結(jié)果這一部分

11、，我們比較離群點(diǎn)檢測(cè)算法PLDOF和LDOF。（1）醫(yī)學(xué)診斷數(shù)據(jù)集：在現(xiàn)實(shí)的數(shù)據(jù)庫(kù)中很難找到一個(gè)數(shù)據(jù)集來(lái)評(píng)估離群點(diǎn)檢測(cè)算法，因?yàn)閮H有很少的數(shù)據(jù)集能正確的認(rèn)識(shí)到哪些對(duì)象是真正的行為異常。在這個(gè)試驗(yàn)中我們使用醫(yī)學(xué)的數(shù)據(jù)集WDBC，這個(gè)數(shù)據(jù)集是為了乳房腫塊診斷做原子特征提取的。這個(gè)數(shù)據(jù)集包括569個(gè)醫(yī)學(xué)診斷記錄，每個(gè)記錄都有32個(gè)屬性(ID,診斷信息，30個(gè)真實(shí)的輸入特征)。這個(gè)診斷是二元的，要么是良性的要么是惡性的。我們認(rèn)為良性的記錄的正常數(shù)據(jù)。這個(gè)實(shí)驗(yàn)中，我們用所有的這357個(gè)良性診斷記錄作為正常對(duì)象，然后加入5個(gè)惡性診斷記錄作為離群點(diǎn)。通過(guò)改變鄰近的大小k，把真實(shí)離群點(diǎn)占隱藏離群點(diǎn)的比率作為檢

12、測(cè)的精度。實(shí)驗(yàn)中，我們逐漸增加k的值，然后計(jì)算每個(gè)方法的計(jì)算精度。圖1 WDBC數(shù)據(jù)為了進(jìn)一步驗(yàn)證我們的方法，我們重復(fù)10次實(shí)驗(yàn)，每次離群點(diǎn)的數(shù)目不相同。每次獨(dú)立執(zhí)行10步，然后計(jì)算平均檢測(cè)精度，k的取值范圍從10到50.從圖1中我們可以看出精度隨前n個(gè)點(diǎn)和鄰域的大小k變化而變化。正如圖1所示，我們的算法比LDOF算法精度高。如果考慮錢20個(gè)點(diǎn)，兩個(gè)算法都能檢測(cè)到所有的離群點(diǎn)。我們同時(shí)也改變鄰域大小k來(lái)進(jìn)行實(shí)驗(yàn)?？梢钥吹剑瑑蓚€(gè)算法在k=30時(shí)精度達(dá)到了極限。從表1中我們可以看出雖然我們從數(shù)據(jù)集中剪去了57%的點(diǎn)，但是兩個(gè)算法的精度還是差不多。由于剪去了57%的點(diǎn)，計(jì)算的消耗也大大降低，這也是基

13、于LDOF剪枝方法值得肯定的一面。表1 WDBC數(shù)據(jù)集的剪枝比率（2）酵母數(shù)據(jù)集：在這個(gè)實(shí)驗(yàn)中，我們使用酵母數(shù)據(jù)集，這個(gè)數(shù)據(jù)集曾被用來(lái)查找蛋白質(zhì)集中的地方。數(shù)據(jù)集包括1484個(gè)對(duì)象，每個(gè)對(duì)象有如下屬性：名字和其他8個(gè)輸入特征。我們認(rèn)為在C-terminus中值為0的目標(biāo)信號(hào)為正常數(shù)據(jù)，其中POX的值比異常的大2.實(shí)驗(yàn)中我們使用整個(gè)1474個(gè)記錄作為正常對(duì)象，然后加入10個(gè)記錄作為離群點(diǎn)。我執(zhí)行與醫(yī)學(xué)診斷數(shù)據(jù)集相似類型的實(shí)驗(yàn)可以觀察到相同的趨勢(shì)。實(shí)驗(yàn)結(jié)果如圖2和表2.可以看出我們可以從原始數(shù)據(jù)集中剪去超過(guò)60%的點(diǎn)而不丟失離群點(diǎn)。表2 酵母數(shù)據(jù)集的剪枝比率圖2 酵母數(shù)據(jù)5.結(jié)論本篇論文我們提出了

14、一個(gè)有效的離群點(diǎn)檢測(cè)方法。首先通過(guò)使用每個(gè)聚類的半徑來(lái)判斷哪些點(diǎn)可能不是離群點(diǎn)，然后從數(shù)據(jù)集中移除這些點(diǎn)。由于降低了數(shù)據(jù)集的大小，時(shí)間復(fù)雜度得到了降低。同時(shí)使用基于距離的局部離群系數(shù)來(lái)衡量一個(gè)對(duì)象偏離其鄰域的程度。通過(guò)剪除一些點(diǎn)使得我們的方法在檢測(cè)離群點(diǎn)上比現(xiàn)在的方法精度要高。參考文獻(xiàn)1 F. Angiulli, S. Basta, and C. Pizzuti. Distance-based detection and prediction of outliers. IEEE Transactions on Knowledge and Data Engineering, 18:145160,

15、 2006.2 F. Angiulli and C. Pizzuti. Fast outlier detection in high dimensional spaces. In PKDD 02: Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, pages 1526, 2002.3 F. Angiulli and C. Pizzuti. Outlier mining in large highdimensional data sets. IEEE T

16、ransactions on Knowledge and Data Engineering, 17:203215, 2005.4 A. Arning, R. Agrawal, and P. Raghavan. A linear method for deviation detection in large databases. pages 164169,1996.5 M. M. Breunig, H.-P. Kriegel, R. T. Ng, and J. Sander.Lof: identifying density-based local outliers. SIGMOD Rec.,29

17、(2):93104, 2000.6 M. Ester, H.-P. Kriegel, and X. Xu. A database interface for clustering in large spatial databases. In Proceedings of 1stInternational Conference on Knowledge Discovery and DataMining (KDD-95), 1995.7 A. Ghoting, S. Parthasarathy, and M. Otey. Fast mining of distance-based outliers

18、 in high-dimensional datasets. Data Mining and Knowledge Discovery, 16(3):349364, June 2008.8 S. Guha, R. Rastogi, and K. Shim. CURE: An efficient clustering algorithm for large databases. SIGMOD Rec.,27(2):7384, 1998.9 W. Jin, A. K. H. Tung, and J. Han. Mining top-n local outliers in large database

19、s. In KDD 01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 293298, 2001.10 E. M. Knorr and R. T. Ng. Algorithms for mining distancebased outliers in large datasets. In Proc. 24th Int. Conf. Very Large Data Bases, VLDB, pages 392403, 199

20、8.11 E. M. Knorr and R. T. Ng. Finding intensional knowledge of distance-based outliers. In VLDB 99: Proceedings of the 25th International Conference on Very Large Data Bases, pages211222, 1999.12 E. M. Knorr, R. T. Ng, and V. Tucakov. Distance-based outliers: algorithms and applications. The VLDB J

21、ournal, 8(3-4):237253, 2000.13 R. T. Ng and J. Han. Efficient and effective clustering methods for spatial data mining. pages 144155, 1994.14 S. Papadimitriou, H. Kitagawa, P. Gibbons, and C. Faloutsos.Loci: fast outlier detection using the local correlation integral.In Data Engineering, 2003. Proceedings. 19th International Conference on Data Engineering, pages 315326, March 2003.15 S. Ramaswamy,