基于距離的異常點(diǎn)挖掘算法研究

1、基于距離的異常點(diǎn)挖掘算法研究董沛然，王莉*（北京郵電大學(xué) 電子工程學(xué)院，北京 100876）510152025303540摘要：異常點(diǎn)挖掘是一種從數(shù)據(jù)中分析并發(fā)現(xiàn)潛在的反常對象的數(shù)據(jù)挖掘技術(shù)，它在實(shí)際生產(chǎn)生活中越來越受到人們的關(guān)注，并逐漸成為計(jì)算機(jī)領(lǐng)域的一個(gè)研究熱點(diǎn)。本文系統(tǒng)地研究了基于距離的異常點(diǎn)挖掘算法，針對循環(huán)嵌套算法和單元格算法這兩種最常用的基于距離的異常點(diǎn)挖掘算法，對比分析了它們的算法思想和時(shí)間復(fù)雜度，并通過海量數(shù)據(jù)進(jìn)行算法仿真，總結(jié)出其各自的優(yōu)缺點(diǎn)及適用場合，為實(shí)際應(yīng)用中異常點(diǎn)挖掘算法的選擇提供了參考依據(jù)。關(guān)鍵詞：計(jì)算機(jī)軟件與理論；數(shù)據(jù)挖掘；異常點(diǎn)檢測中圖分類號(hào)：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ì)活動(dòng)中，人們越來越關(guān)注數(shù)據(jù)集合中的異常數(shù)據(jù)。異常數(shù)據(jù)是與一般行為或模型不一致的數(shù)據(jù)，它們是數(shù)據(jù)集合中與眾不同的數(shù)據(jù)，這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。異常的成因主要來自于以下幾個(gè)方面1：（1）數(shù)據(jù)來源于不同的類；（2）自然變異，即許多數(shù)據(jù)集可以用一個(gè)統(tǒng)計(jì)分布建模，如用正態(tài)(高斯)分布建模，其中數(shù)據(jù)對象的概率隨到分布中心

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

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

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

9、d，則稱 oq 為 o p 的 d-鄰近點(diǎn)，稱所有 d-鄰近點(diǎn)的集合為點(diǎn) o p 的d-鄰域5。定義 2 對于 a 中的任一點(diǎn) o p ，選取一個(gè)經(jīng)驗(yàn)臨界值 m（視具體情況而定），設(shè)點(diǎn) 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-鄰域中的點(diǎn)的個(gè)數(shù)為 n p 若 n p m，則稱該點(diǎn) o p 為 a 中的異常點(diǎn)5。這里 d 稱為臨界距離，m 稱為臨界鄰居數(shù)目。定義 2 是基于距離的異常點(diǎn)的數(shù)量化定義。7075802

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

11、j 個(gè)維度的平均值為：x j =1 nn i=1那么對第 j 個(gè)維度的 n 個(gè)數(shù)據(jù)點(diǎn)所實(shí)施的中心化變換為：xij = xij - x j ，在所有維度上都實(shí)施上述變換，則每個(gè)維度的均值都為 0，即各個(gè)維度的取值都有相同85的基點(diǎn)。標(biāo)準(zhǔn)化變換的目的是確保個(gè)維度的變化范圍相等。當(dāng)用不同的方法衡量變化范圍時(shí)，就有不同的標(biāo)準(zhǔn)化變換方法7。常用的有：（1）最大最小歸一法將 a 中每個(gè)點(diǎn)的每個(gè)分量都除以相應(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 中每個(gè)點(diǎn)的每個(gè)分量都除以相應(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 個(gè)維度的極差為：1in 1in第 j 個(gè)維度的 n 個(gè)數(shù)據(jù)所實(shí)

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)化變換后，個(gè)變量的基點(diǎn)相同，變化范圍也相同了。步驟二 計(jì)算各點(diǎn)之間的距離計(jì)算 a 中每兩點(diǎn)之間的距離：mi=1步驟三 計(jì)算每個(gè)點(diǎn) d-鄰域內(nèi)點(diǎn)的個(gè)數(shù)對于一個(gè)比較小的正數(shù) d，個(gè)數(shù) n i 。步驟四 判斷每個(gè)點(diǎn)是否為異常點(diǎn)oia ，i=1,2,n，統(tǒng)計(jì) oi 的 d-鄰域之內(nèi)數(shù)據(jù)點(diǎn)的120125給定經(jīng)驗(yàn)臨界值 m，若 n i m，則 c 內(nèi)無異常點(diǎn)，并且 c 的第一層鄰居內(nèi)也無異常點(diǎn)；若 c+c.neigh

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

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

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

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

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

19、紹了基于距離模型的兩種異常點(diǎn)挖掘算法原理，并通過 matlab 仿真對比了兩種算法的時(shí)間復(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)行時(shí)間（秒）8.118.13單元格算法運(yùn)行時(shí)間（秒）3.162.09195200205210實(shí)際應(yīng)用中異常點(diǎn)挖掘算法的選擇提供了參考。參考文獻(xiàn) (references)1 楊宇. 多指標(biāo)綜合評價(jià)中賦權(quán)方法評析j. 統(tǒng)計(jì)與決策，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é)報(bào)（自然科學(xué)），2009，23（2）.4 edw