一種基于樞紐現象和加權離群分數的離群數據挖掘算法

郭 峰，張繼福

(太原科技大學 計算機科學技術學院，太原 030024)

1 引 言

離群數據是指明顯偏離其他數據，不滿足數據的一般模式或行為，與存在的其他數據不一致的數據，或者明顯偏離其它數據[1]，已經廣泛應用在天文光譜數據分析[2]、災難天氣預報[3,4]、金融[5]、網絡入侵檢測[6]等領域.由于"維度災難"的影響[7,8]，大多數在低維數據空間中表現良好的離群挖掘算法，在高維數據空間中效果變差，其主要原因是在高維數據空間中的數據變得稀疏，任意兩個數據對象之間的距離趨于一致，隱藏了真實離群數據，使每個數據對象都幾乎成為離群數據[9]，因而大多數離群數據挖掘方法無法適用于高維數據集.

k近鄰查詢在離群數據挖掘中有著廣泛的應用，樞紐現象(Hubness)是維度災難中與k近鄰查詢相關的一個概念[10,11].樞紐現象是指在高維數據集中，任意數據對象i出現在其他數據對象k近鄰列表中的次數Nk(i)，其次數分布呈現明顯的右偏態，一些數據對象(antihubs，稱為非樞紐點)很少或者不出現在其他數據對象kNN列表中.隨著數據維度的增大，樞紐現象越來越明顯，且非樞紐點與高維數據集中的離群數據存在密切關聯關系[12].本文針對高維數據集，利用樞紐現象給出了一種基于樞紐現象和加權離群分數的離群數據挖掘算法.該算法首先計算逆k近鄰，得到每個數據對象的離群分數；其次使用每個數據對象與其k近鄰點的距離，對其k近鄰點的離群分數之和進行加權，獲得加權k近鄰分數和作為啟發性條件，并且多次隨機選擇區分度比例計算每個數據對象的區分度，將所得區分度平均值設為區分度閾值，大于區分度閾值則認為所選取區分度比例是滿意值；然后將每個數據對象的離群分數與其加權k近鄰分數和，按區分度比例滿意值求和，得到該對象的離群程度，選取離群程度最大的若干數據對象作為離群數據.最后采用人工數據集和UCI 標準數據集，實驗驗證了該算法的有效性.

2 相關工作

傳統的離群數據挖掘方法，例如基于統計[13]、基于距離[14,15]、基于密度[16,17]、基于子空間[18,19]等，都會受到"維度災難"的影響，在高維數據集中挖掘效果較差.k近鄰查詢是離群數據挖掘中的一種簡單和基本步驟，影響著離群挖掘效果.

k近鄰查詢是指根據相似性度量在數據集中尋找或查詢與給定對象最鄰近的k個數據對象[20]，并廣泛應用在離群數據挖掘中，其典型研究成果為：Ramaswamy等人[14]首先提出基于k近鄰的離群數據檢測算法，計算數據集中每個數據對象與其第k近鄰之間的歐氏距離，距離最大的n個數據對象是離群數據，其缺點是距離相同時的離群數據判斷；Angiulli等人[15]將離群數據認為是與其k近鄰距離之和越大的n個數據對象，并提出HilOut算法，其主要思想是利用空間填充曲線計算近似k近鄰，找到候選離群數據準確計算進行篩選.?stermark[21]提出Fuzzy KNN算法，將模糊knn與遺傳算法結合，在時間序列中進行離群數據挖掘.

逆k近鄰查詢是指給定一個查詢數據對象，根據相似性度量返回一個結果集，該結果集中每一個數據對象都將該查詢數據對象作為其k近鄰[22].在逆k近鄰查詢中，查詢數據對象與數據集中其他數據對象相似性相關，具有低逆k近鄰值的數據對象很少或者不出現在數據集其他數據對象的k近鄰列表中，與離群數據存在關聯關系[12].逆k近鄰查詢廣泛應用在在離群數據挖掘中，典型研究成果為：Hautamaki等人[23]提出了ODIN算法，該算法將任意一個數據對象i出現在其他數據對象k近鄰列表中的次數Nk(i)分數被認為是該數據對象的離群分數，并分析了為何Nk(i)分數能夠構成有意義的離群分數的原因，其缺點是需要人為設定離群分數閾值，不適應于未知數據分布的離群數據挖掘；Lin等人[24]提出了一種ODIN算法的變體，遍歷數據集中所有數據對象，將離群數據認為是Nk(i)=0的數據對象，其缺點是離群挖掘結果受數據分布影響，包含在小簇中的離群數據可能被隱藏.

樞紐現象是"維度災難"與逆k近鄰查詢相關的一個概念，并隨著數據維度的增大，樞紐現象越來越明顯.Radovanovic等人[12]首先分析了樞紐現象，并表明在低維和高維數據中，非樞紐點和離群數據均存在關聯關系；隨著空間維度的增大，樞紐現象使數據集產生更顯著的樞紐點和非樞紐點，并據此提出了適用于高維離群檢測的AntiHub算法和AntiHub2算法.AntiHub算法計算數據集中每個數據對象的Nk(i)值，根據Nk(i)值計算離群分數.AntiHub2算法在AntiHub算法的基礎上引入啟發性信息，在計算一個數據對象的離群程度時除了考慮該數據對象的Nk(i)分數還考慮其k近鄰數據對象的Nk分數和，設置step參數進行遍歷，找到最大區分度比例α，將當前數據對象的Nk(i)分數與其k近鄰數據對象的Nk分數和按最大區分度比例α求和，得到離群程度，選取離群程度最大的若干數據對象作為離群數據.

綜上所述，現有的基于逆k近鄰(RkNN)的離群挖掘算法均使用Nk(i)值，對Nk(i)值操作得到離群分數.ODIN算法和AntiHub算法對離群數據和正常數據對象的區分度不高，主要原因是Nk(i)本質上是離散的，較大的k值選擇提高區分度但運算代價昂貴.AntiHub2算法能夠在較小的k值選擇下獲得較高的區分度，其缺點是計算過程中需要設置參數進行遍歷，時間復雜度高，同時也都沒有考慮距離因素.

3 樞紐現在與相關概念

3.1 樞紐現象

樞紐現象(Hubness)是指高維數據空間中，任意數據對象i出現在其他數據對象k近鄰列表中的次數Nk(i)的分布呈現出明顯的右偏態，且右偏程度會隨著數據維度的增加而增大，導致少量的樞紐點(hubs)非常頻繁地出現在數據集其他數據對象的kNN列表中.而另外一些非樞紐點(antihubs)很少或者不出現在數據集其他數據對象的kNN列表中.參照文獻[10]右偏程度的計算公式定義如下；

(1)

其中：μNk和δNk分別表示Nk(i)的均值和標準差.當SNk>0 時，SNk值越大，Nk(i)的右偏程度就越高，數據集的樞紐現象就越明顯.

樞紐現象與"維度災難"相關.當高維數據出現"維度災難"時，任意兩個數據對象之間的距離趨于一致，反映相似性差異的各種距離指標效果變差，大部分數據對象將落在以數據質心為中心的超球體表面上[10].該特征使得顯著低于超球體表面的數據對象更有可能出現在其他數據對象的kNN列表中，即這些數據對象具有更高的Nk(i)值，被稱為樞紐點.與此對應，顯著遠離超球體表面的數據對象很少或者不出現在其他數據對象的kNN列表中，具有較低的Nk(i)值，被稱為非樞紐點.超球體表面附近的數據對象,即"規則"數據對象，傾向于具有接近k的Nk(i)期望.若數據集來自多個分布，那么大部分數據點將落在以相應分布的質心為中心的超球面上.

3.2 相關概念

在文獻[12]中，將給定數據對象i的Nk(i)值歸一化，并計算其離群分數，計算公式定義如下：

(2)

其中：ai為數據對象i的離群分數.當Nk(i)=0時，由公式(2)也可使得數據對象i獲得有意義的離群分數.計算每個數據對象的離群分數，選取離群分數最高的若干個數據對象，并將其視為離群數據.

在文獻[12]中，引入啟發性信息，在計算數據對象i的離群程度時，除了考慮其Nk(i)分數還考慮其k近鄰數據對象的Nk分數和.k近鄰Nk分數和(anni)的計算公式定義如下：

anni=∑j∈NN(k,i)aj

(3)

其中：anni為數據對象i的k近鄰Nk分數和，數據對象j為其k近鄰，aj為數據對象j的Nk(j)分數.數據對象i的離群程度計算公式定義如下：

cti=(1-α)·ai+α·anni

(4)

其中：cti為數據對象i的離群程度，ai為其Nk(i)分數，anni為其k近鄰Nk分數和，α為最大區分度比例.計算每個數據對象的離群程度，選取離群程度最大的若干數據對象作為離群數據.

4 距離信息加權與區分度滿意值

4.1 距離信息加權

指根據文獻[15]，離群數據是全體數據對象中與其k近鄰平均距離最大的n個數據對象.現有的基于逆k近鄰的離群挖掘算法都未考慮距離因素，因此引入距離信息作為權值，提高其準確率.k近鄰距離定義為：給定數據對象與其k近鄰數據對象之間歐氏距離的平均值.k近鄰權值定義為：給定數據對象的k近鄰距離與數據集k近鄰距離平均值的比值，其計算公式定義如下：

(5)

其中：wi為數據對象i的k近鄰權值,averDisk(i)為其k近鄰距離，averDisk為數據集k近鄰距離平均值.

根據公式(2)(3)，計算數據對象i的歸一化Nk(i)分數ai和其k近鄰Nk分數和anni.ai值較高的數據對象Nk(i)值較低，較少或者不出現在數據集其他數據的k近鄰列表中，并與離群數據存在關聯關系，因此可以使用ai計算離群分數.因為ai在本質上離散，對離群數據與正常數據區分度低，引入anni作為啟發性條件能夠提高算法區分度.對于給定數據對象i，使用其k距離權值對其k近鄰Nk分數和anni進行加權，得到加權k近鄰Nk分數和(Wanni)，其計算公式定義如下：

Wanni=anni·wi

(6)

其中：Wanni為數據對象i加權k近鄰Nk分數和，anni為其k近鄰Nk分數和，wi為其k近鄰權值.參照文獻[12],離群程度計算公式可重新定義為：

cti=(1-α′)·ai+α′·Wanni

(7)

其中：cti為數據對象i的離群程度，ai為其Nk(i)分數，Wanni為其加權k近鄰Nk分數和，α′為區分度比例滿意值.

當數據對象i為離群數據時，數據對象i的k近鄰距離大于數據集k近鄰距離平均值，其k近鄰權值wi>1，所對應加權k近鄰Nk分數和Wanni大于k近鄰Nk分數和anni.根據公式(4)(7)，對于離群數據，使用加權k近鄰Nk分數和可獲得比文獻[12]高的離群分數，提高正常數據對象和離群數據的區分度.利用信息作對離群分數進行加權還具有以下優點：當數據集不滿足任何特定分布模型時，距離信息仍能有效地發現離群數據；k近鄰查詢，可獲得所有數據對象的k近鄰距離，不需要進行額外計算.

4.2 區分度滿意值

使用區分度閾值分支判斷可以有效減少循環次數，提高算法效率.為適用于數據分布未知的數據集，自動生成區分度閾，根據區分度閾值判斷區分度比例滿意值，并根據公式(7)使用區分度比例滿意值計算離群程度.自動生成區分度閾值用于分支判斷，使用區分度比例滿意解α′計算離群程度的步驟如下：

從α′∈(0,step,2·step，…，1)中多次隨機選取α′，每個α^′值調用局部函數discScore(y,ρ)計算對應區分度，多次實驗所獲得區分度平均值設為區分度閾值Threshold；繼續從α′∈(0,step,2·step，…，1) 中多次隨機選取α′，如果所選取α′對應區分度大于區分度閾值，則認為所選取α′為一個區分度比例滿意值；使用區分度比例滿意值α′計算離群程度.

計算區分度滿意值α′的過程是在所有α取值中隨機選取有限個α′，根據區分度閾值判斷是否為區分度比例滿意值α′.當搜索參數step設置較小時，使用區分度滿意值α′可以減少算法循環次數.在計算區分度比例滿意值α′的過程中，采用隨機抽樣，計算得到的區分度比例滿意值α′具有隨機性，因此m次隨機選擇α′，計算區分度比例直到獲得n個區分度比例滿意值.

5 離群數據挖掘算法描述

綜上所述，引入距離信息對離群分數加權提高離群數據與正常數據的區分度,提高離群數據挖掘效果；使用區分度滿意值分支判斷減少循環次數，提高了離群數據挖掘效率.利用距離信息和區分度比例滿意值，計算離群程度的基本步驟：首先對數據集中的每個數據對象進行逆k近鄰查詢，得到每個數據對象出現在其他數據對象k近鄰列表中的次數Nk，根據公式(2)、(3)計算數據對象i的Nk(i)分數與其k近鄰Nk分數和；其次使用每個數據對象的k近鄰權值對其k近鄰Nk分數和加權，得到加權k近鄰Nk分數和；然后多次隨機選擇α′值計算其區分度，將所得區分度平均值設為區分度閾值，大于區分度閾值則認為所選取α′是滿意值；最后使用公式(7)計算每個數據對象的離群程度，選取離群程度最高的若干個數據對象，并將其視為離群數據.其算法描述如下：

算法：WAntiHub(Weighted Anti-Hubness for Unsupervised Distance-Based Outlier Detection)

輸入：數據集D中每個數據的k近鄰；采樣比例ρ∈(0,1]；搜索參數step∈(0,1]

輸出：離群數據

1)n=數據集D的數據個數；

2)for(i=0;i

3) 根據公式(2)計算數據對象i的歸一化Nk(i)分數ai；

4) 使用ai，根據公式(3)計算數據對象i的k近鄰Nk分數和anni；

5) 根據公式(5)計算數據對象i的k近鄰權值wi；

6) 使用wi和anni，根據公式(6)計算數據對象i的加權加權k近鄰Nk分數和Wanni；

7)end for；

8)α從(0,step,2·step，…，1)中隨機取值，得到α1…αm；

9)for(j=0;j

10) for(i=0;i

11) 根據公式(7)，使用α1…αm計算數據對象i的離群程度cti；

12) end for；

13) cdiscj=discScore(cti, ρ)；//調用局部函數計算α1…αm對應區分度

14)end for；

15)Threshold=(∑1jcdiscj)/m ； //計算區分度閾值Threshold

16)α′從(0,step,2·step，…，1)中隨機取值，得到α1′…αq′；

17)for(j=0;j

18) for(i=0;i

19) 根據公式(7)使用α′計算數據對象i的離群程度cti；

20) end for；

21) cdisc=discScore(cti, ρ)；//調用局部函數計算α′對應區分度

22) if cdisc> Threshold；//根據閾值判斷區分度比例滿意值α′

23) 記錄所對應的區分度比例滿意值α′；

24) if 已經保存了s個α′；

25) end if；

26)end for；

28)for(i=0;i

29) 根據公式(7)使用區分度比例滿意值α^′計算離群程度

30)end for；

31)End WAntiHub

算法步驟說明：

1)局部函數：discScore(y,ρ)：對于y∈Rn和ρ∈(0,1]，根據采樣比例找到y中值最小的「nρ?個值，進行去重操作，將非重元素個數除以「nρ?作為輸出.

2)在上述算法中2)-7)計算數據集中每個數據對象Nk(i)歸一化分數ai，使用k近鄰權值對其k近鄰Nk分數和進行加權，得到加權k近鄰分數和Wanni.8)-15)多次隨機選擇α值計算區分度閾值Threshold.16)-27)多次隨機選擇α′，使用區分度閾值判斷，獲得區分度比例滿意值α′.28)-30)使用區分度比例滿意值α′計算每個數據對象的離群程度，選取離群程度最高的若干個數據對象，并將其視為離群數據.

算法復雜性分析：

6 實驗結果及分析

實驗環境：Inter Core(TM) i7-6700HQ CPU 16GB內存，windows 10操作系統，eclipse作為開發平臺，采用Java語言實現了WAntiHub算法和AntiHub2算法[12].實驗數據包括人工數據集和UCI數據集.

6.1 人工數據集

人工數據采用隨機生成正態數據，并將數據集中的1%元素乘以1.5倍作為離群數據.

1)近鄰數k

圖1 近鄰數k對算法的影響Fig.1 Influence of the neighbor number k on the algorithm

由圖1(b)表明隨著k值的增大，WAntiHub算法耗時呈現線性增長.主要原因是Wantihub算法和Antihub2算法都使用(加權)k近鄰Nk分數和，k值越大，計算(加權)k近鄰Nk分數和的數據也隨之增多.對所有的k值，WantiHub算法的效率高于AntiHub2算法，主要原因是WAntiHub算法使用區分度比例滿意值α′代替最大區分度比例α用于計算離群程度，分支判斷減少了循環次數.

2)數據量

圖2是采用100維數據的實驗結果，由圖2(a)表明隨著數據量的增大，WAntiHub算法的準確度基本不變，AntiHub2算法的準確度有緩慢的提高.主要原因是數據量的增加使數據更加聚集，樞紐現象程度加深，非樞紐點更加顯著.對所有數據量，WAntiHub算法的準確度高于AntiHub2算法.

圖2 數據量對算法的影響Fig.2 Influence of the amount on the algorithm

由圖2(b)表明隨著數據量的增大，WantiHub算法耗時呈指數型增長.主要原因是WantiHub算法的時間復雜度為O(n2·t).對所有的數據量，WAntiHub算法的效率高于AntiHub2算法.

3)屬性維度

圖3是采用10000條數據，k=100的實驗結果.由圖3(a)表明隨著屬性維度的增大，WAntiHub2算法和AntiHub2算法的準確率提升.主要原因是數據屬性維度增大使樞紐現象程度加深，非樞紐點更加顯著.AntiHub2算法對準確率的提升高于WAntiHub算法，其主要原因是屬性維度增大使數據集中任意兩個數據對象之間的距離趨于一致，使基于距離信息加權的效果變差.對所有的屬性維度，WantiHub算法的準確率高于AntiHub2算法.

圖3 屬性維度對算法的影響Fig.3 Influence of the dimension on the algorithm

由圖3(b)表明對所有的屬性維度，WatiHub算法運算時間基本一致.主要原因是WantiHub算法使用k近鄰查詢結果作為輸入數據，對屬性維度不同的數據集，其k近鄰查詢結果所包含的數據量基本一致.對所有的維度，WAntiHub算法的效率高于AntiHub2算法.

4)采樣比例ρ

圖4是采用10000條100維數據,k=100的實驗結果.由圖4(a)表明采樣比例ρ對WAntiHub算法精確度影響較小.且對所有的ρ值，WAntiHub算法的準確率高于AntiHub2算法.

圖4 采樣比例ρ對算法的影響Fig.4 Influence of the sampling ratio on the algorithm

6.2 UCI數據集

使用UCI數據集Yeast，HTRU2，Ionosphere，ESRDS驗證算法準確率和效率，所有UCI數據都轉化為標準分數.

表1 UCI數據集信息Table 1 UCI dataset information

圖5 UCI數據集對算準確率的影響Fig.5 Influence of algorithm accuracy on the UCI dataset

由圖5表明在所有UCI數據集上，WAntiHub算法的準確率高于AntiHub2算法，WAntiHub算法對低維數據集Yeast、HTRU_2和中維數據集HTRU_2準確率提高較多，對高維數據集ESRDS準確度提升較小.主要原因是隨著屬性維度的增大，使用距離信息加權的效果變差.

由圖6(a)表明，WantiHub算法對Yeast和Ionosphere數據集效率提升較大，主要原因是Yeast和Ionosphere數據集數據量較小，遍歷找到最大區分度比例α占總運算時間比例大，使用區分度閾值分支判斷有效減少循環次數.圖6(b)顯示對HTRU_2和ESRDS數據集，效率提升較小.主要原因是數據集數據量較大，計算每個數據對象的Nk(i)值占總運算時間比例大.在所有UCI數據集上，WAntiHub算法效率提高.

7 結束語

針對高維數據中維度災難導致離群數據挖掘效果變差，利用逆k近鄰中出現的樞紐現象，給出了一種基于樞紐現象和加權離群分數的離群數據挖掘算法WAntiHub.該算法引入距離信息對離群分數加權，提高離群數據挖掘效果；使用區分度滿意值分支判斷減少循環次數，提高了離群數據挖掘效率.使用人工數據和 UCI 數據集，實驗驗證了該算法的有效性.為適應海量數據的需求，WAntiHub算法的并行化將是下一步的研究工作.

圖6 UCI數據集對算法效率的影響Fig.6 Influence of algorithm efficiency on the UCI dataset