基于直方圖和FP增長的高維空間離群點挖掘

李龍姣，程國達

(南京財經(jīng)大學信息工程學院，江蘇 南京 210046)

0 引言

一個離群點是這樣一個數(shù)據(jù)，它與數(shù)據(jù)集中其它數(shù)據(jù)偏離如此之多以至于讓人們懷疑它是由另外一種完全不同的機制產(chǎn)生的[1]。離群點檢測是數(shù)據(jù)挖掘的基本任務之一，其目的是消除噪音或發(fā)現(xiàn)潛在的、有用的知識，例如欺詐檢測、入侵檢測、故障檢測、生態(tài)系統(tǒng)失調(diào)檢測等[2]。傳統(tǒng)的離群點檢測方法主要分為5類:(1)基于統(tǒng)計的方法[3];(2)基于深度的方法[4];(3)基于聚類的方法[5];(4)基于密度的方法[6];(5)基于距離的方法[7]。

隨著信息技術(shù)的發(fā)展，現(xiàn)實數(shù)據(jù)集的維數(shù)和數(shù)據(jù)的數(shù)量顯著上升，幾十維甚至上百維的數(shù)據(jù)并不少見。在高維數(shù)據(jù)空間中，數(shù)據(jù)非常稀疏，根據(jù)數(shù)據(jù)的相似性，每個點都可被定義為離群點[8]。如何選擇合理高效的度量方法處理好高維空間數(shù)據(jù)點的稀疏問題，并合理解釋高維空間離群點的物理意義，是高維離群點挖掘方法的目標。

1 現(xiàn)有高維離群點挖掘方法

高維數(shù)據(jù)中的離群點并不是在所有維上都離群，在絕大多數(shù)情況下，離群數(shù)據(jù)往往只在少數(shù)幾個維上出現(xiàn)異常。如果在數(shù)據(jù)的所有維上進行離群點挖掘，不僅有很大的時間復雜度，而且由于平均作用，使得數(shù)據(jù)之間差異變得很小[9]，為了提高挖掘效率，人們提出了投影變換[9-10]和特征選取[11-12]等基于子空間挖掘的方法。

Aggarwal等[9]提出了用遺傳算法來尋找最優(yōu)子空間的投影變換方法，這種方法將空間劃分成等邊的網(wǎng)格空間并計算每個網(wǎng)格的稀疏因子，然后利用遺傳算法來挖掘子空間中的離群點。在這種方法中，計算每個網(wǎng)格的稀疏因子都要掃描整個數(shù)據(jù)集，因此具有很高的計算復雜度。Sanghamitra等[13]提出了一種改進方法，可以大大縮短計算時間。上述兩種方法采用遺傳算法雖然能有效解決數(shù)據(jù)投影問題，但還存在問題。首先，在初始化階段，構(gòu)成染色體的維是隨機選取的，這就給離群點挖掘結(jié)果帶來很大的不確定因素;其次，不同的網(wǎng)格劃分存在困難，不同的劃分會帶來不同的結(jié)果。

Angiulli等[11]提出了 HilOut算法，該方法首先利用Hilbert曲線將高維數(shù)據(jù)映射到一維線性空間，根據(jù)數(shù)據(jù)在一維空間中的前驅(qū)和后繼找出每個數(shù)據(jù)的k個最近鄰，從而計算每個數(shù)據(jù)點的權(quán)值，最后根據(jù)權(quán)值排序找出離群點，避免了復雜的距離計算開銷。雖然Hilbert曲線可以將復雜的高維問題轉(zhuǎn)化為簡單的一維空間計算問題，但是該方法還是有不少缺點。首先，Hilbert曲線也和網(wǎng)格劃分方法一樣，要不斷將每個維2等分，這一點是很難做到的，因為不是每個維的長度都是2的次方;其次，Hilbert曲線雖然能保證一維上相鄰的數(shù)據(jù)點在原高維空間中也相鄰，但是高維空間中相鄰的點用該曲線映射到一維空間中就不一定相鄰了，這就難以保證挖掘結(jié)果的準確性。

除了上述兩種投影變換方法之外，小波變換也可以用來在子空間上挖掘離群點。它首先通過在數(shù)據(jù)空間強加一個多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后進行變換，在變換后的空間中發(fā)現(xiàn)密集區(qū)域[14]，消除密集區(qū)域后剩下的點就是離群點。Yu等[15]就利用小波變換從原始數(shù)據(jù)中消除了聚類從而得到離群點。當然，該方法也有網(wǎng)格劃分的缺點。

Mohamed 等[16]提出了 PCKA(Projected Clustering based on the K-means Algorithm)特征選取算法。該方法把空間中的維分為兩種，一種是密集維，另一種是稀疏維，離群點就在稀疏維上，而聚類就要在密集維上尋找。PCKA的不足之處就是簡單地把高維空間中的維劃分為密集維和稀疏維，沒有考慮有些維既有聚類數(shù)據(jù)的投影，也有離群數(shù)據(jù)的投影，這部分維在該算法中很可能被誤除從而影響挖掘結(jié)果。

此外，Tan等[17]提出的決策樹歸納方法和許龍飛等[18]提出的粗糙集方法來挖掘離群點，但這些方法存在和文獻[16]一樣的問題。

在本文提出的方法中，計算高維數(shù)據(jù)每一維上的稀疏度，根據(jù)稀疏度形成直方圖，在直方圖上判別該維上離群點;在得到離群點-離群維的對應關(guān)系表后，用FP增長方式對離群點-離群維關(guān)系表進行分析，像挖掘關(guān)聯(lián)規(guī)則一樣，挖掘存在離群點的維之間的關(guān)系，從而解釋離群點不同維之間的關(guān)系。通過對實際數(shù)據(jù)集的實驗，表明本方法是有效和有意義的。

2 原理與算法

2.1 KNN(K-Nearest Neighbors)距離的計算

假設(shè)DB是一個 d維數(shù)據(jù)，A={A1，A2，…，Ad}表示數(shù)據(jù)集的維，X={x1，x2，…，xN}為數(shù)據(jù)集的 N個數(shù)據(jù)點，其中 xi={xi1，xi2，…，xid}，xij(i=1，…，N;j=1，…，d)對應著數(shù)據(jù)點xi在維Aj上的值。數(shù)據(jù)集中任意兩點 xu，xv在維 As上的距離為 ds(xu，xv)=|xus－xvs|，其中1≤u，v≤N，1≤s≤d。

定義1 在d維數(shù)據(jù)集DB中，給定一個參數(shù)k，一個數(shù)據(jù)點的KNN距離是指這個點與其k個最近鄰點的距離之和。

KNN距離顯示出了一個點的離群程度，KNN距離越大，這個點距離它的k個最鄰近點越遠，即它是離群點的可能性越高。

算法1(KNN距離計算)

輸入:DB:數(shù)據(jù)集;k:近鄰數(shù)據(jù)點數(shù)目;Aj:需要計算的維j;N:每一維的數(shù)據(jù)數(shù)目。

輸出:每個數(shù)據(jù)點在Ai上的KNN距離yij(i=1，…，N;j=1，…，d)(規(guī)范化至[0，1])。

步驟1 將DB中Ai對應的N個值存儲到一維數(shù)組 a[N]，b[N];

步驟2 將數(shù)組b中元素升序排列，取每個元素b[i](i=0，…，N-1)的前驅(qū)和后繼元素共2k 個;

步驟3 計算b[i](i=0，…，N-1)與其2k個前驅(qū)后繼的直線距離，并將這2k個距離從小到大排序;

步驟4 從排序的距離中取前k個距離相加即為KNN距離;

步驟5 將Aj上數(shù)值的KNN距離規(guī)范化至[0，1];

步驟6 從數(shù)組a中獲取b中元素在DB中對應的索引號以便將其在Aj上的KNN距離yij保存到相應位置。

2.2 通過直方圖判別離群點

Knorr等在文獻[19]中這樣定義離群點:如果數(shù)據(jù)集DB中對象至少有pct部分與對象o的距離大于dmin，則稱對象o是以pct和dmin為參數(shù)的基于距離的離群點。

上述基于距離的離群點定義是全局離群點的定義，除此之外，還有另外的一種離群點，如果一個對象相對于它的局部鄰域，特別是關(guān)于鄰域密度，它是遠離的，那它就是局部離群點[20]。

除了上述定義的全局離群點和局部離群點，本文提出一種隱形離群點。

定義2 數(shù)據(jù)集DB的對象，如果其綜合屬性分析結(jié)果屬于某個聚類C，但是在某些維上卻不屬于任何聚類在這些維上的投影區(qū)域，這種對象為隱形離群點。

隱形離群點一般處于所屬聚類的邊緣，以全局的眼光來看并不離群，使用投影變換或者特征選取方法挖掘離群點時也容易被忽略，本文在數(shù)據(jù)的每一維上進行分析后才能保證將其辨別，并準確判斷其離群維。

如某個數(shù)據(jù)點在任何一維上離群，則把它當作是離群點并記下它離群的維以便后續(xù)分析。根據(jù)直方圖找出全局離群點、局部離群點以及隱形離群點，其中隱形的離群點并不屬于預先設(shè)定的離群點集，但也會隨著離群點一起檢測出，經(jīng)過FP增長分析后方可確定是否離群，這些離群點是很有分析價值的，提取這些隱形離群點和明顯的離群點一起進行后續(xù)的離群屬性關(guān)系分析，將得到很多有用的信息。

KNN 距離規(guī)范至區(qū)間[0，1]，將[0，1]區(qū)間分成s份，每份長度為1/s，然后計算 Ai(i=1，…，d)上屬于每個區(qū)間的數(shù)據(jù)個數(shù)，從而生成KNN直方圖。

假設(shè)離群點在數(shù)據(jù)集中所占比例為α(0＜α≤5%)，數(shù)據(jù)總數(shù)為N，則離群點數(shù)目為αN。在直方圖中，S1，…，Sm為 s個 KNN 距離區(qū)間，|Si|(i=1，…，s)為第i個區(qū)間包含的數(shù)據(jù)點數(shù)目。

定義3 在某一維的KNN直方圖中，將前m(0＜m≤s)個KNN距離區(qū)間所包含的數(shù)據(jù)點數(shù)目相加得直至且≥(1－α/2)N，如果|Sm+1|≤αN，則N，如果|Sm+1|≥αN，則，定義直方圖中右邊β部分的數(shù)據(jù)點為這一維上的全局離群點。

定義3給出了在直方圖中區(qū)分全局離群點的規(guī)則，其中αN為離群點總數(shù)，離群點包含全局離群點、局部離群點和隱形離群點，故定義中將αN/2作為全局離群點的最大值，在直方圖中進行具體的計算后，確定β為判定全局離群點的邊界值，即把直方圖右部β部分數(shù)據(jù)點判定為全局離群點。

定義4 在某一維的KNN直方圖中，從S1至SS取第一個包含數(shù)據(jù)點小于αN的距離區(qū)間Sn(1＜n＜s)，令γ=，則這一維上的局部離群點和隱形離群點存在于γ和β部分數(shù)據(jù)點之間。

定義4給出了局部離群點和隱形離群點在直方圖中存在范圍。由于聚類的密度不同，故不同的聚類包含的數(shù)據(jù)點所處的KNN距離區(qū)間不同，本方法定義處于直方圖左邊γ部分的數(shù)據(jù)點為該維上密度最大聚類中的數(shù)據(jù)點，而Sn為該聚類與其余聚類之間的分隔，γ至β部分數(shù)據(jù)就包含了小密度聚類以及局部離群點和隱形離群點。由于局部離群點存在于不同的聚類之間，隱形離群點處于聚類的邊緣，局部離群點和隱形離群點的KNN距離大于聚類中數(shù)據(jù)點的KNN距離。

定義5 取直方圖左邊γ部分數(shù)據(jù)所在KNN區(qū)間包含的平均數(shù)據(jù)點數(shù)目為c，即c=|Si|/(n－1)，將εc(0＜ε≤1)作為聚類包含數(shù)據(jù)點數(shù)目的最小值。

定義6 在某一維的直方圖中，對于[γ，β]部分數(shù)據(jù)所在的KNN距離區(qū)間，如果連續(xù)3個區(qū)間內(nèi)數(shù)據(jù)點的數(shù)目之和小于εc，則這些區(qū)間內(nèi)的數(shù)據(jù)點為這一維上的局部離群點或者隱形離群點。

定義5和定義6給出了在直方圖中判別局部離群點和隱形離群點的規(guī)則。實驗表明，處于直方圖中[γ，β]部分數(shù)據(jù)中的聚類，其包含數(shù)據(jù)點的KNN距離最多分布與3個連續(xù)的區(qū)間，故如果連續(xù)3個連續(xù)區(qū)間的數(shù)據(jù)數(shù)目之和小于εc，則這些區(qū)間內(nèi)的數(shù)據(jù)就是疑似局部離群點或者隱形離群點。

算法2 (根據(jù)KNN直方圖判別離群點)

輸入:d維數(shù)據(jù)集DB;每一維數(shù)據(jù)在s個KNN距離區(qū)間內(nèi)的數(shù)據(jù)點數(shù)目;離群點在數(shù)據(jù)集中所占比例α，數(shù)據(jù)總數(shù) N，ε(0 ＜ ε≤1))。

輸出:每一維上的全局離群點所在距離區(qū)間集合outlier_Interval以及局部離群點和隱形離群點所在的距離區(qū)間集合local_Interval。

方法:對每一維數(shù)據(jù)Ai(i≤i≤d)。

(1)全局離群點判別。

(2)確定γ。

(3)確定局部離群點。

2.3 離群點-離群維關(guān)系表

找出數(shù)據(jù)集中的離群點只是本文的目的之一，更為重要的目的是分析存在離群點的屬性之間的關(guān)系，為此首先要生成離群點-離群維關(guān)系表。

算法3 (離群點-離群維關(guān)系表生成)

輸入:d維數(shù)據(jù)集DB;每一維上的全局離群點以及局部離群點和隱形離群點所在的距離區(qū)間集合。

輸出:每個離群點的離群屬性集;將維Ai對應的數(shù)據(jù)存入一維數(shù)組pointValue[N];將維Ai數(shù)據(jù)對應的KNN距離值存入一維數(shù)組pointWeight[N];所有的離群點在pointValue的對應的索引號存入一位數(shù)組 Outlier[N]。

方法:

在數(shù)組pointWeight中找到屬于這些KNN距離區(qū)間的KNN距離并把這些距離對應的索引號存入一位數(shù)組pointIndex

for j=0 to pointIndex.Count do

if(Outlier中存在 pointIndex[j])

取得pointIndex[j]在Outlier中的索引號index;

將這一維的維數(shù)i加入pointIndex[j]對應的數(shù)組Att[index];

else

將 pointIndex[j]加入 Outlier

將這一維的位數(shù) i加入 pointIndex[j]對應的數(shù)組 Att[Outlier.Count-1];

end for

end for

2.4 離群維的頻繁項集分析

頻繁地同時出現(xiàn)離群屬性組合就是頻繁項集，這些離群維之間必然存在某些關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)這些規(guī)則可以發(fā)現(xiàn)離群點的離群原因，從而解釋離群點的物理意義。為了避免產(chǎn)生大量候選項集合重復掃描數(shù)據(jù)庫，本文選擇頻繁模式增長(Frequent-Pattern Growth，F(xiàn)P增長)[14]方法對離群屬性集進行頻繁項集挖掘，找出頻繁出現(xiàn)的離群屬性組合。

3 實驗結(jié)果與結(jié)論

Aggarwal[9]認為評價一個離群點檢測方法的好壞，可以通過在給定的數(shù)據(jù)集上來運行該方法，并且計算在由該方法所找出的離群點中，真正的離群點所占據(jù)的比例，比例越高，則表明該方法的性能越好。本文使用兩個數(shù)據(jù)集對所提出的方法進行測試分析，并分別用該評價方法對實驗結(jié)果進行評價。

數(shù)據(jù)1 使用UCI網(wǎng)站的Abalone數(shù)據(jù)，該數(shù)據(jù)包含4177個數(shù)據(jù)，每個數(shù)據(jù)有9個屬性，分別為性別、長度、直徑、高度、全重、肉重、可食部分重量、殼重和年輪數(shù)。本文將該數(shù)據(jù)集中年輪數(shù)為10圈的成年雄性鮑魚以及幼齡鮑魚數(shù)據(jù)取出作為測試數(shù)據(jù)集，即數(shù)據(jù)包含兩個類，一類是成年雄性鮑魚，另一類維幼齡鮑魚，其中幼齡鮑魚數(shù)據(jù)即為離群點。根據(jù)找出的離群點數(shù)據(jù)來分析區(qū)分相同年輪數(shù)的鮑魚中成年雄性和幼仔鮑魚的屬性。

本實驗設(shè) s=25，α =4‰，ε =0.6，通過對數(shù)據(jù)第二維至第八維(第一維是預測維，第九維年輪數(shù)都為10，故不用計算KNN距離)KNN距離的計算，得到KNN直方圖，以長度屬性為例，如圖1所示。

圖1 長度屬性KNN直方圖

通過直方圖以及算法分析得到每個離群點以及離群維的對應關(guān)系表，如表1所示。

表1 離群點以及離群維的對應關(guān)系表

對該離群點-離群維關(guān)系對應表進行FP分析以發(fā)現(xiàn)離群維之間的關(guān)系如表2所示。

表2 Abalone數(shù)據(jù)結(jié)果分析表

其中屬性2為長度，屬性3為直徑，屬性5為毛重，屬性8為殼重，經(jīng)查詢可得索引號為295-297的離群點為幼齡鮑魚，其離群屬性主要為長度和直徑，由此可知相同年輪的成年鮑魚和幼齡鮑魚仔長度和直徑上相差較大;其它離群數(shù)據(jù)點為相同年輪數(shù)的成年雄性鮑魚中的離群鮑魚，它們主要的離群屬性為毛重和殼重，由此可知這些離群的成年鮑魚是因為“體重超標”才被“孤立”。

實驗結(jié)果評價如表3所示。

表3 Abalone數(shù)據(jù)實驗結(jié)果評價表

數(shù)據(jù)2 使用UCI網(wǎng)站的SPECTF Heart Data Set，該數(shù)據(jù)包含265個數(shù)據(jù)，45個維，每個數(shù)據(jù)描述一個病人的心臟診斷數(shù)據(jù)，其中第一維是綜合診斷結(jié)果，由一個二進制數(shù)0或者1表示，其中0表示不正常，1表示正常，即本數(shù)據(jù)集包含兩個類，一類數(shù)據(jù)為“心臟正?！?，另一類為“心臟不正?！?，數(shù)據(jù)中不正常數(shù)據(jù)即為離群點。實驗找出這些離群點并分析病人的哪些屬性不正常則可判定心臟不正常。

本實驗設(shè) s=25，α=2%，ε=0.6，以第 26維KNN直方圖為例，如圖2所示。

圖2 第26維KNN直方圖

通過直方圖以及算法分析得到每個離群點以及離群維的對應關(guān)系表，如表4所示。

表4 離群點-離群維對應關(guān)系表

對該離群點-離群維關(guān)系對應表進行FP分析以發(fā)現(xiàn)離群維之間的關(guān)系如表5所示。

表5 SPECTF Heart Data Set數(shù)據(jù)實驗結(jié)果分析表

經(jīng)數(shù)據(jù)分析，實驗結(jié)果中索引號174-177對應的數(shù)據(jù)為心臟不正常的病人數(shù)據(jù)，主要在F7R、F16R、F16S、F17R、F17S以及F22R屬性出現(xiàn)異常從而被診斷為心臟病;其余數(shù)據(jù)顯示出這些病人雖在某些指標上數(shù)據(jù)異常，但是對心臟健康影響不大，其中F3R、F11R、F10R、F13R以及F2S屬性上出現(xiàn)問題的較多。

實驗結(jié)果評價表如表6所示。

表6 SPECTF Heart Data Set數(shù)據(jù)實驗結(jié)果評價表

4 結(jié)束語

實驗表明，本文提出的離群點挖掘方法能有效地挖掘出數(shù)據(jù)集中的稀有類即離群點，并且除了全局離群點之外，也能找出隱形離群點，用FP增長算法對離群點的離群維進行分析，得出離群維之間的關(guān)聯(lián)規(guī)則，從而合理地解釋了離群點的物理意義;實驗結(jié)果的準確度分析說明挖掘結(jié)果準確有效，本方法具有很好的應用價值。

[1]Hawkins D.Identifications of Outliers[M].London:Chapmanand Hall，1980.

[2]薛安榮，姚琳，鞠時光，等.離群點挖掘方法綜述[J].計算機科學，2008，35(11):13-18，27.

[3]Rousseeuw P J，Leroy A M.Robust Regression and Outlier Detection[M].New York:John Wiley＆Sons，1987.

[4]Johnson T，Kwok I，Ng R T.Fast computation of 2-dimensional depth contours[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining.New York:AAAI Press，1998:224-228.

[5]Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering:A review[J].ACM Computing Surveys，1999，31(3):264-323.

[6]Breunig M M，Kriegel H P，Ng R T，et al.LOF:Identif-ying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.Dallas:ACM Press，2000:93-104.

[7]Knorr E，Ng R.Algorithms for mining distance based outliers in large datasets[C]//Proceedings of the 24th VLDB Conference.New York:Morgan Kaufmann，1998:392-403.

[8]Beyer K，Goldstein J，Ramakrishnan R.When is nearest neighbours meaningful?[C]//Proceedings of the 7th International Conference on Data Theory.1999:217-235.

[9]Aggarwal C C，Yu P.Outlier detection for high dimensional data[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.Santa Barbara，2001:37-47.

[10]Aggarwal C C.Redesigning distance functions and distance based applications for high dimensional data[J].SIGMOD Record Date，2001，30(1):13-18.

[11]Angiulli F，Pizzuti C.Outlier mining in large high-dimensional data sets[J].IEEE Trans.Knowledge and Data Eng.，2005，17(2):203-215.

[12]Angiulli F，Basta S，Pizzuti C.Distance based detection and prediction of outlier[J].IEEE Trans.Knowledge and Data Eng.，2006，18(2):145-160.

[13]Sanghamitra B，Santanu S.A genetic approach for efficientoutlier detection in projected space[J].Pattern Recognition，2008，41(4):1338-1349.

[14]Jiawei Han，Micheline Kamber.Data Mining:Concepts and Techniques，Second Edition[M].Beijing:China Machine Press，2009.

[15]Yu Dantong，Gholamhosein S，Zhang Aidong.FindOut:Finding outliers in very large data sets[J].Knowledge and Information Systems，2002，4(4):387-412.

[16]Mohamed Bouguessa，Shengrui Wang.Mining projected clusters in high-dimensional spaces[J].IEEE Trans.Knowledge and Data Eng.，2009，21(4)507-522.

[17]Tan Pangning，Michael S，Vipin K.Introduction to Data Mining[M].New York:Addison Wesley，2006.

[18]許龍飛，熊君麗.基于粗糙集的高維空間離群點發(fā)現(xiàn)算法研究[J].計算機工程與應用，2004，40(7):58-60.

[19]Knorr E M，Ng RT.Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the 24th International Conference on Very Large Bases.New York，NY，1998.

[20]Markus MBreunig，Hans-Peter Kriegel.LOF:Identifying density-based local outliers[C]//Proceedings of ACM SIGMOD 2000 International Conference on Management of Data.Dalles，TX，2000:93-104.