馮 宇，苑易偉

(1.長安大學 電子與控制工程學院，陜西 西安 710064；2.西安理工大學 自動化與信息工程學院，陜西 西安 710048)

0 引 言

孤立點也被稱作離群點或異常點，是指數據中不符合一般規(guī)律或明顯偏離其他數據的數據。在數據挖掘研究領域，孤立點檢測是一個重要的研究方向，其任務是通過算法尋找與大部分數據有著不同屬性或含義的少量數據[1]。一方面，在數據預處理階段發(fā)現(xiàn)并剔除這些數據，可以降低孤立點對數據挖掘結果的負面影響；另一方面，罕見的數據不一定是無用的數據，可能蘊含更大的研究價值，通過研究這些數據，會發(fā)現(xiàn)一些新的知識[2]。孤立點檢測技術已經廣泛應用于工業(yè)控制、網絡安全、電子商務等各個領域[3-4]。

1 相關研究

孤立點檢測算法大致可以分為四類，分別為基于統(tǒng)計、基于聚類、基于距離和基于密度的算法?；诮y(tǒng)計的孤立點檢測算法需要已知數據集的統(tǒng)計學分布規(guī)律[5-6]，并且應明確孤立點不服從這種分布規(guī)律。然而實際中孤立點的分布規(guī)律往往并不清楚，與此同時，結構復雜的高維數據集會明顯減弱這類算法的效果。基于聚類的孤立點檢測算法是通過聚類分析將數據劃分為若干個簇，并給定閾值，小于設定閾值的簇即視為孤立點[7]。這類算法在聚類過程中就能檢測孤立點，但其檢測的效果與簇形成的質量密切相關[8]?；诰嚯x的孤立點檢測算法需要計算每個對象與其近鄰的距離，并且認為孤立點與其近鄰的距離比正常數據遠。這類算法應用簡單，并且其有效性得到了充分的論證[9]，但如果距離參數選取不合適，算法的效果會變得很不理想[10]?；诿芏鹊墓铝Ⅻc檢測算法根據數據的局部孤立程度來尋找孤立點，該思路更符合孤立點定義，因此基于密度的孤立點檢測算法近年來發(fā)展迅速[11-12]。

2 關鍵技術

文中提出一種基于最小超球面密度的孤立點檢測算法(minimum hyper sphere density，MHSD)，在介紹算法之前，需對相關的定義和概念進行闡述。

2.1 相關定義

定義1：給定正整數n，一個n維球面是n+1維空間中距離某個點為R的所有點的集合。

特別地，一個0維球面是長度為R的線段的兩個端點，一個1維球面是半徑為R的圓，一個2維球面是半徑為R的球體的面。維數大于2的球面稱為超球面。最小球是包含對象p的k近鄰所有超球中半徑R最小的球面，p不一定是球心。

定義2：NNk(p)是對象p的k近鄰序列，RNNk(p)是k近鄰中包含p的所有對象，即反近鄰。

以圖1為例介紹RNNk(p)的構造方法。假設數據集A={p,q1,q2,q3,q4,q5,}，當k=3時，NNk(p)={q1,q2,q3,q4}，NNk(q1)={p,q2,q4}，NNk(q2)={p,q1,q3}，NNk(q3)={q1,q2,q5}，NNk(q4)={p,q1,q2,q5}，NNk(q5)={q1,q2,q3}。則根據定義2，p的RNNk(p)為{q1,q2,q4}，同樣也能得到其他對象的RNNk。顯然，NNk(p)與RNNk(p)不一定相等。

圖1 反近鄰構造方法示意

定義3：對于給定的正整數k，對象p的有效近鄰定義為p的k近鄰對象的k近鄰中包含p的所有對象，即：ENP(p)=NNk(p)∩RNNk(p)，ENP(p)可能為空集。

以圖2為例介紹ENP(p)的構造方法。圖中數據集D={a,b,c,d,e,f,g,h,i,j,k}，當k=4時，d的k近鄰NNk(d)={e,g,h,j}，反近鄰RNNk(d)={e,j}；g的k近鄰NNk(g)={e,f,h,i}，反近鄰RNNk(g)={e,f,h,i,k}。則d和g的有效近鄰分別為ENPk(d)={e,j}和ENPk(g)={e,f,h,i}。

圖2 有效近鄰構造示意

根據上述定義，文中對最小超球面密度的定義為：

定義4：對象p的最小超球面密度是p的有效k近鄰個數與最小超球面半徑R的比值，即

(1)

其中，|ENP(p)|為有效近鄰的個數。

2.2 算法描述

文中算法首先計算所有數據的有效k近鄰,然后根據k近鄰中的數據和對象p的距離從小到大排列，得到對象的最近近鄰序列，通過計算對象p與有效k近鄰中的最小超球面密度差來計算對象p的密度背離程度，最后根據有效k近鄰中的所有數據的密度背離程度計算對象p的孤立程度。算法具體描述如下：

步驟1：計算每兩個數據間的距離，并找到所有數據的k近鄰。

步驟2：構建每個數據的近鄰序列NNS。

設NNS(p)的初始值是{p}，每次迭代把NNk(p)中距離p最小的對象加入到NNS(p)中，當NNk(p)中所有對象都加入到NNS(p)時，迭代結束。

步驟3：根據定義4計算所有數據的最小超球面密度。

步驟4：計算每兩個數據的最小超球面密度差：

Δspden(x,y)=|spden(x)-spden(y)|

(2)

且Δspden(x,y)=Δspden(y,x)。

步驟5：根據最小超球面密度差，計算對象的最近近鄰序列的密度背離程度(NDD)。

(3)

其中，r=|NNk(p)|。

步驟6：計算每個數據的孤立程度。

(4)

該值越小，說明p的孤立程度越低；該值越大，說明p越有可能是孤立點。根據設定的閾值便可檢測出孤立點。

3 實驗結果與分析

3.1 檢測人工數據集的孤立點

人工二維數據集如圖3所示，數據集包含1 700個正常數據和7個孤立點。這1 700個正常數據分為一個由200個服從高斯分布的數據組成的低密度簇C1和三個由500個服從高斯分布的數據組成的高密度簇C2，C3和C4。7個孤立點的編號分別o1,o2,…,o7。

使用三種經典的孤立點檢測算法與文中提出的MHSD方法進行檢測結果比較，三種方法分別為局部離群因子算法(local outlier factor，LOF)、離群影響因子算法(influenced outlierness，INFLO)和密度相似鄰域離群因子算法(density similarity neighbor based outlier factor，DSNOF)[13-15]，各方法檢測結果中孤立程度最高的7個點如表1所示?？梢钥闯?，INFLO無法檢測出o1、o5、o6和o7，DSNOF無法檢測出o4，LOF和MHSD均可檢測出7個孤立點，MHSD每個孤立點的孤立程度比LOF更大，說明MHSD的檢測效果最理想。

圖3 人工數據集示意

表1 人工數據集孤立點檢測結果

3.2 算法性能評估

引入precision(Pr)，recall(Re)和rank power(RP)三個參數評估算法的性能[16]。Pr表示算法檢測出的孤立點的孤立程度在孤立程度最大的m個數據中的比例，Re表示算法在檢測出的孤立程度最大的m個數據中孤立點個數占孤立點總數的比例，RP表示算法檢測出的n個孤立點在孤立程度最大的m個數據中所占的位置參數。三個參數的值越大，表明算法性能越好。

數據集1選用經典的皮馬印第安人糖尿病數據集[17]，該數據集分為兩類，第一類包含500個數據，第二類包含268個數據。將第一類數據隨機刪除488個，得到一個隨機分布的簇，作為此實驗中的孤立點[18]。為了比較在不同參數選擇下不同算法的效果，將近鄰個數k選為數據的維數、數據量的5%和10%，即k的值選擇為8、14和28。各個算法的性能評估結果如表2～表4所示，其中Nrc為算法檢測出的孤立點個數。

表2 k=8時的算法性能評估結果

續(xù)表2

表3 k=14時的算法性能評估結果

表4 k=28時的算法性能評估結果

當k=8時，在前10個孤立程度最大的數據中，只有MHSD能發(fā)現(xiàn)一個孤立點。隨著m的增大，MHSD能夠檢測出的孤立點個數迅速增多，當m=90時，所有孤立點全被檢測出來。此時LOF、INFLO和DSNOF分別檢測出4、4、3個孤立點，MHSD的性能最好。當k=14時和k=28時，有類似的結果。真實數據集算法性能評估結果表明，MHSD算法隨著k值的增大效果變好，并且優(yōu)于LOF、INFLO和DSNOF。

數據集2選用本課題組在生物信息實驗中實際測量的小鼠心臟竇房結場電位信號數據集，將在常溫環(huán)境下(22±2℃)測量到的230個數據作為正常數據，從低溫環(huán)境下(5±2℃)測量到的數據中取出10個作為孤立點，數據維度為30，取k=30。各個算法的性能評估結果如表5所示，MHSD的性能最優(yōu)。

表5 使用生物信息數據集的算法性能評估結果

4 結束語

文中提出了一種基于最小超球面密度的孤立點檢測算法，該算法通過找出對象數據的近鄰序列，利用最小超球面密度差計算近鄰序列密度背離程度，進而計算每個數據的孤立程度。使用人工數據集和真實數據集的檢測結果表明，MHSD可以檢測孤立點，且與經典的LOF、INFLO和DSNOF三種算法相比，MHSD的性能最優(yōu)。