基于距離的異常點挖掘算法研究

1、基于距離的異常點挖掘算法研究董沛然，王莉*（北京郵電大學(xué) 電子工程學(xué)院，北京 100876）510152025303540摘要：異常點挖掘是一種從數(shù)據(jù)中分析并發(fā)現(xiàn)潛在的反常對象的數(shù)據(jù)挖掘技術(shù)，它在實際生產(chǎn)生活中越來越受到人們的關(guān)注，并逐漸成為計算機(jī)領(lǐng)域的一個研究熱點。本文系統(tǒng)地研究了基于距離的異常點挖掘算法，針對循環(huán)嵌套算法和單元格算法這兩種最常用的基于距離的異常點挖掘算法，對比分析了它們的算法思想和時間復(fù)雜度，并通過海量數(shù)據(jù)進(jìn)行算法仿真，總結(jié)出其各自的優(yōu)缺點及適用場合，為實際應(yīng)用中異常點挖掘算法的選擇提供了參考依據(jù)。關(guān)鍵詞：計算機(jī)軟件與理論；數(shù)據(jù)挖掘；異常點檢測中圖分類號：tp311rese

2、arch in distance-based outliers detection algorithmdong peiran, wang li(school of electronic engineering, beijing university of posts and telecommunications, beijing100876)abstract: outliers detection is a data mining technology to analyze and find potential abnormalphenomena from the data. this tec

3、hnology has attracted increasing attention and it has nowbecome a focus for research in computer field. this paper systematically discusses algorithm ofoutliers detection based on distance, comparing and analyzing the main idea of the algorithm andtime complexity of the two most common outliers dete

4、ction algorithm based ondistancenested-loop algorithm and cell-based algorithm. the paper also summarizesrespectively the various occasions where these two most common outliers detection algorithm canbe used through algorithm simulation of mass data, providing references for the selection ofoutliers

5、 detection algorithm in practical applications.key words: computer software and theory; data mining; outliers detection0 引言在現(xiàn)代工業(yè)生產(chǎn)和經(jīng)濟(jì)活動中，人們越來越關(guān)注數(shù)據(jù)集合中的異常數(shù)據(jù)。異常數(shù)據(jù)是與一般行為或模型不一致的數(shù)據(jù)，它們是數(shù)據(jù)集合中與眾不同的數(shù)據(jù)，這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。異常的成因主要來自于以下幾個方面1：（1）數(shù)據(jù)來源于不同的類；（2）自然變異，即許多數(shù)據(jù)集可以用一個統(tǒng)計分布建模，如用正態(tài)(高斯)分布建模，其中數(shù)據(jù)對象的概率隨到分布中心

6、距離的增加而急劇減少，也就是說，大部分?jǐn)?shù)據(jù)對象靠近中心，數(shù)據(jù)對象顯著地不同于這個中心的似然性很??；（3）數(shù)據(jù)測量和收集的失誤。 異常點挖掘就是發(fā)現(xiàn)與其它大部分對象不同的對象，屬于數(shù)據(jù)挖掘中的一個分支。在欺詐檢測、市場分析、醫(yī)療診斷等領(lǐng)域，異常點挖掘是一項很有意義的研究。因為數(shù)據(jù)集合中數(shù)據(jù)的多樣性和多維性，所以異常點挖掘問題通常比較困難2。常見的異常點挖掘算法包括基于統(tǒng)計模型的方法、基于密度模型的方法、基于偏離模型的方法和基于距離模型的方法3。本文主要討論基于距離模型的異常點挖掘算法，并在數(shù)據(jù)集規(guī)模增大和數(shù)據(jù)分布狀況改變的情況下，對比分析單元格算法和傳統(tǒng)算法的優(yōu)劣。作者簡介：董沛然（1986-）

7、，男，北京郵電大學(xué)電路與系統(tǒng)專業(yè)工學(xué)碩士，主要研究方向為數(shù)據(jù)挖掘、異構(gòu)通信網(wǎng)絡(luò)的融合等通信聯(lián)系人：王莉，女，北京郵電大學(xué)電子工程學(xué)院講師，計算機(jī)和通信領(lǐng)域?qū)＜? e-mail: liwang-1-1 基于距離的異常點挖掘問題模型直觀上，一個異常點是指在一個數(shù)據(jù)集合中這樣的數(shù)據(jù)點：遠(yuǎn)離它的數(shù)據(jù)點較多，至少45要占 p 100%，而接近它的數(shù)據(jù)點較少，至多占(1-p) 100%。這里，稱為臨界鄰居比例4。因此，從本質(zhì)上講，所謂異常點是指相對孤立的數(shù)據(jù)，即在其鄰域內(nèi)數(shù)據(jù)點較少的數(shù)據(jù)點。圖 1 給出了二維數(shù)據(jù)集中異常點的示例（其中 a、b 兩點為異常點）。圖 1二維數(shù)據(jù)集中的異常點50遵循這個直觀描述

8、，下面給出基于距離的異常點的精確定義：設(shè)存在一維點的集合a，a = o1 , o2 , o3 ,.,on ，oi = (xi1 , xi 2 ,.,xim ),i = 1,2,.,n ，其中 oi 為 a 中的數(shù)據(jù)點， xim 為 oi 的第 個分量。定義 a 中任意兩點 o p 、 oq 間的距離為：mi =1556065其中 為任意正整數(shù)。若 =1，則：mi =1此時的距離稱為絕對距離。若 =2，則：mi =1此時的距離稱為歐氏距離。于是引入下面的定義：定義 1 對于 a 中的任一點 o p ，給定一個比較小的正數(shù) d0，若效用點集中的任一點 oq滿足條件： d k (op , oq )

9、d，則稱 oq 為 o p 的 d-鄰近點，稱所有 d-鄰近點的集合為點 o p 的d-鄰域5。定義 2 對于 a 中的任一點 o p ，選取一個經(jīng)驗臨界值 m（視具體情況而定），設(shè)點 o p-2-d k (o p , oq ) = ( x pi - xqi )1 / kkd1 (o p , oq ) = x pi - xqid 2 (o p , oq ) = ( x pi - xqi )1 / 2k的 d-鄰域中的點的個數(shù)為 n p 若 n p m，則稱該點 o p 為 a 中的異常點5。這里 d 稱為臨界距離，m 稱為臨界鄰居數(shù)目。定義 2 是基于距離的異常點的數(shù)量化定義。7075802

10、循環(huán)嵌套算法在傳統(tǒng)的循環(huán)嵌套算法中，需要計算集合 a 中各數(shù)據(jù)點之間的距離，再計算每個點 d-鄰域內(nèi)點的個數(shù)，才能判斷這個點是否為異常點。具體流程包括以下四個步驟：步驟一 數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備階段的任務(wù)是數(shù)據(jù)的中心化和標(biāo)準(zhǔn)化。由于 a 中不同維度 x*i 和 x* j 表示的是數(shù)據(jù)對象的不同屬性，它們往往會使用不同的度量單位，其數(shù)值也可能相差十分懸殊。在這種情況下，變化量大的維度可能會淹沒變化量小的維度，從而使得后者應(yīng)有的作用的不到反映6。為了確保個維度在分析中的地位相同，需要對數(shù)據(jù)進(jìn)行中心化和標(biāo)準(zhǔn)化變換。中心化變換的目的是使各種維度的量值都有相同的基點，通常在原始值上減去相應(yīng)維度的平均值：記第

11、j 個維度的平均值為：x j =1 nn i=1那么對第 j 個維度的 n 個數(shù)據(jù)點所實施的中心化變換為：xij = xij - x j ，在所有維度上都實施上述變換，則每個維度的均值都為 0，即各個維度的取值都有相同85的基點。標(biāo)準(zhǔn)化變換的目的是確保個維度的變化范圍相等。當(dāng)用不同的方法衡量變化范圍時，就有不同的標(biāo)準(zhǔn)化變換方法7。常用的有：（1）最大最小歸一法將 a 中每個點的每個分量都除以相應(yīng)維度上取值的絕對值的最大值。90xij =xijmax xij， i=1,2,n；j=1,2,pi歸一化后數(shù)據(jù)的取值介于-1 到 1 之間。該方法對于具有類均勻分布的數(shù)據(jù)歸一化效果較好。（2）總和標(biāo)準(zhǔn)化

12、將 a 中每個點的每個分量都除以相應(yīng)維度上的取值之和。95xij =xijni =1ij， i=1,2,n這種標(biāo)準(zhǔn)化方法所得的新數(shù)據(jù)集滿足：ni=1ij= 1 ，（3）均值標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化-3- xij ， x xxij =xij - m js j， i=1,2,n，100其中 m j ，s j 分別為第 j 列全部數(shù)據(jù)的均值和標(biāo)準(zhǔn)差。采用這種方法所得標(biāo)準(zhǔn)化后的數(shù)據(jù)滿足：m j =1 nn i =1n i=11均值標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化方法特別適用于符合正態(tài)分布的數(shù)據(jù)，處理后的絕大多數(shù)數(shù)據(jù)值將位于-1 到 1 之間。105（4）極差標(biāo)準(zhǔn)化第 j 個維度的極差為：1in 1in第 j 個維度的 n 個數(shù)據(jù)所實

13、施的極差標(biāo)準(zhǔn)化為：xij =xij - x jr j， i=1,2,n110115經(jīng)過這種標(biāo)準(zhǔn)化所得的新數(shù)據(jù)集在各分量上的極大值為 1，極小值為 0，其余的數(shù)值均在 0 與 1 之間。經(jīng)過標(biāo)準(zhǔn)化變換后，個變量的基點相同，變化范圍也相同了。步驟二 計算各點之間的距離計算 a 中每兩點之間的距離：mi=1步驟三 計算每個點 d-鄰域內(nèi)點的個數(shù)對于一個比較小的正數(shù) d，個數(shù) n i 。步驟四 判斷每個點是否為異常點oia ，i=1,2,n，統(tǒng)計 oi 的 d-鄰域之內(nèi)數(shù)據(jù)點的120125給定經(jīng)驗臨界值 m，若 n i m，則 c 內(nèi)無異常點，并且 c 的第一層鄰居內(nèi)也無異常點；若 c+c.neigh

14、bor1m，則 c 中無異常點；若 c+c.neighbor1+c.neighbor2m，則 c 中的所有點均為異常點。步驟三對于步驟二中未能判斷出其內(nèi)部是否為異常點的單元格 ，依次判斷其內(nèi)部每個點145驟二的多次篩選可知， 和 .neighbor2 的數(shù)目都比較小，所以需要計算的點間距離實際上很少，不會增加很多時間復(fù)雜度。150對于 k 維數(shù)據(jù)空間，只需調(diào)整二層鄰居單元格的變長為d2 k，其它處理方法與二維相同9。4 仿真分析下面分別考察在數(shù)據(jù)集的規(guī)模增大和數(shù)據(jù)分布狀況改變時，單元格算法和傳統(tǒng)算法在時間復(fù)雜度上的變化。155用 matlab 實現(xiàn)循環(huán)嵌套算法和單元格算法，輸入不同的數(shù)據(jù)集，運(yùn)

15、用循環(huán)嵌套算法和單元格算法分別進(jìn)行異常點挖掘，觀察兩種算法的運(yùn)行時間。-5-是否為異常點。在這一步，對于 內(nèi)的每個點 o ，都需要判斷它周圍 d-鄰域內(nèi)有多少個點。不過，由于 o 到 和 的第一層鄰居內(nèi)各點的距離都小于 d，而到 的第二層鄰居以外各點的距離都大于 d，因此這里只需要計算 o 到 的第二層鄰居內(nèi)各點的距離。而且，由算法步4.1數(shù)據(jù)集規(guī)模對兩種算法性能的影響數(shù)據(jù)集規(guī)模包含兩個方面：數(shù)據(jù)集中數(shù)據(jù)點的個數(shù)（行數(shù)）和屬性個數(shù)（列數(shù)）。下面分別討論：160屬性個數(shù)不變，數(shù)據(jù)點的個數(shù)增多測試數(shù)據(jù)：取均值為 50，標(biāo)準(zhǔn)差為 10 的正態(tài)分布數(shù)據(jù)集，屬性個數(shù)固定為 2。仿真結(jié)果如表 5.1：表

16、1數(shù)據(jù)點個數(shù)增加情況下的算法運(yùn)行時間165算法運(yùn)行時間隨著點數(shù)增大而變化的情況如圖 3 所示：圖 3數(shù)據(jù)點個數(shù)的增加對算法運(yùn)行時間的影響可以看出，單元格算法的時間復(fù)雜度低于循環(huán)嵌套算法，并且隨點數(shù)增大的趨勢也低于循環(huán)嵌套算法。170（2）數(shù)據(jù)點的個數(shù)不變，屬性個數(shù)增多：測試數(shù)據(jù)：取均值為 500，標(biāo)準(zhǔn)差為 10 的正態(tài)分布數(shù)據(jù)集，固定數(shù)據(jù)點的個數(shù)為 800。測試結(jié)果如表 5.2 所示：表 2數(shù)據(jù)點個數(shù)增加情況下的算法運(yùn)行時間-6-數(shù)據(jù)點個數(shù)10002000300040005000600070008000900010000循環(huán)嵌套算法運(yùn)行時間(秒)0.351.312.868.788.1111.6

17、715.7321.3026.3032.57單元格算法運(yùn)行時間(秒)0.070.230.470.771.651.722.742.934.324.97數(shù)據(jù)集維數(shù)12345循環(huán)嵌套算法運(yùn)行時間(秒)0.140.240.150.120.19單元格算法運(yùn)行時間(秒)0.030.150.320.370.43175算法運(yùn)行時間隨著屬性個數(shù)增大而變化的情況如圖 4 所示：圖 4數(shù)據(jù)集維數(shù)的增加對算法運(yùn)行時間的影響可以看出，單元格算法的運(yùn)行時間隨著維數(shù)增大而增大的趨勢比較快，這是因為維數(shù)越大，劃分出的單元格就越多，算法時間也越長。1804.2數(shù)據(jù)集分布對兩種算法性能的影響下面研究數(shù)據(jù)分布不同時，兩種算法的比較。

18、用 matlab 生成兩份一維，含有 5000 個數(shù)據(jù)點的數(shù)據(jù)集，第一個數(shù)據(jù)集服從均值為 50、標(biāo)準(zhǔn)差為 20 的正態(tài)分布；第二份數(shù)據(jù)集服從均值為 50、標(biāo)準(zhǔn)差為 3 的正態(tài)分布。對兩個數(shù)據(jù)集分別執(zhí)行兩種挖掘算法，其運(yùn)行時間見表 3：185表 3不同數(shù)據(jù)集分布下算法的運(yùn)行時間可見標(biāo)準(zhǔn)差的不同對循環(huán)嵌套算法運(yùn)行時間幾乎沒有影響，而對單元格算法影響很大。這是因為當(dāng)標(biāo)準(zhǔn)差很小時，數(shù)據(jù)較為集中，這時有更多的數(shù)據(jù)點排除了異常點的可能而不用計算它與周邊點的距離，因而算法效率較高。因此，在實際應(yīng)用中，對于分布比較集中的數(shù)據(jù)集，應(yīng)首選單元格算法；而對于分布較190為分散的數(shù)據(jù)集，應(yīng)首選循環(huán)嵌套算法?？偨Y(jié)本文介

19、紹了基于距離模型的兩種異常點挖掘算法原理，并通過 matlab 仿真對比了兩種算法的時間復(fù)雜度，指出循環(huán)嵌套算法適用于數(shù)據(jù)集維數(shù)較大，且分布的標(biāo)準(zhǔn)差較大的場合，而單元格算法適用于數(shù)據(jù)集對象數(shù)目較多，且分布的標(biāo)準(zhǔn)差較小的場合。本文的分析為-7-數(shù)據(jù)集數(shù)據(jù)集一數(shù)據(jù)集二循環(huán)嵌套算法運(yùn)行時間（秒）8.118.13單元格算法運(yùn)行時間（秒）3.162.09195200205210實際應(yīng)用中異常點挖掘算法的選擇提供了參考。參考文獻(xiàn) (references)1 楊宇. 多指標(biāo)綜合評價中賦權(quán)方法評析j. 統(tǒng)計與決策，2006，217(7)：17 一 19.2 breiman l，friedman j h，olshen r a. classification and regression treesm. new york：chapman & hall，1984.3 王元明，熊偉. 異常數(shù)據(jù)的檢測方法n. 重慶工學(xué)院學(xué)報（自然科學(xué)），2009，23（2）.4 edw