基于屬性熵和加權余弦相似度的離群算法

劉愛琴，荀亞玲 (太原科技大學計算機學院，太原 030024)

離群數據挖掘是數據挖掘領域中的一個重要分支，其目的是找出隱含在海量數據中的相對稀疏而孤立的異常數據模式。離群數據挖掘有著廣泛的應用，例如網絡非法入侵檢測及天文學上新星體發(fā)現等[1]。

目前，很多數據的維數非常高，有的甚至高達上百維，如何提高高維數據離群挖掘的效率是目前研究的一個重點。在高維數據空間中，數據的稀疏性意味著每個點都可以看作離群數據，因此傳統(tǒng)的基于統(tǒng)計的、基于分類的、基于距離以及基于聚類等方法的離群數據挖掘算法不再能有效發(fā)現離群數據[2]。當前用于高維離群檢測的方法有基于信息理論的、基于余弦相似度、基于子空間的、基于基尼指標的、基于屬性相關性分析等算法?；谛畔⒗碚摰碾x群挖掘算法通過分析數據集的信息熵來進行離群挖掘，此類算法基于這樣的假設：離群點增加了數據集的不規(guī)則性。典型的算法有基于信息熵的快速貪婪算法[3]和信息熵度量的離群數據挖掘算法[4]和基于信息熵的相對離群點的檢測方法等[5]。ANNA K使用余弦相似度來度量高維數據中的離群對象，也是一種比較有效的方法[6]。所謂子空間技術是針對全空間而言的。在數據的所有屬性中，選取若干維屬性所組成的數據空間為子空間。離群挖掘即找到容易識別離群點的子空間，子空間技術對高維數據效率很高。AGARWAL C等提出一種基于子空間的離群數據挖掘算法[7]，該算法的基本思想是首先將高維數據投影到低維子空間，然后在子空間中考察數據的行為，并利用遺傳算法搜索稀疏子空間，把稀疏子空間中的數據定義為離群數據，但搜索子空間的進化算法是隨機搜索算法，并不能確保搜索到所有的異常子空間，算法的完備性和準確性無法得到保證。ZHANG J F等利用概念格作為子空間描述工具，提出了一種低維子空間離群數據挖掘方法，并利用概念格和稠密度系數提高了算法的正確性和完備性[8]。王磊等利用屬性相關性分析思想，刪除了高維數據集中的冗余屬性，并結合并行運算及微粒群算法，提高了離群檢測的準確性和效率[9]。石巖等人在屬性相關分析的基礎上，采用基尼指標作為離群度量因子，挖掘出不同離群程度的數據點[10]。

1 相關研究

為了提高高維離群檢測的精度，倪巍偉等人將子空間和信息熵的概念相結合，提出了基于局部信息熵的加權子空間離群點檢測算法(SPOD)[11]。其相關的概念定義如下：

假設數據集D=(O，A)，對象集O={o1，o2，…om}，屬性集A={A1，…Ad}，對象o∈O關于屬性Ai的值記為∏Ai(o).

定義1(對象o的k-距離)。存在對象p∈O，使得至少有k個對象p′∈O滿足dist(o,p′)≤dist(o,p′)，并且最多有k-1個對象p′∈O滿足dist(o,p′)

定義2(對象o的k-鄰域)。對象o的k-鄰域是其鄰居對象的集合，即:

δ=Nk(o)={q∈O|dist(o,q)≤k-dist(o)}

(1)

定義3(局部屬性熵)。對o∈O，Ai∈A,對象o關于屬性Ai的局部信息熵定義為：

(2)

其中：

dmax=max{dist(∏Ai(o),∏Ai(q))|q∈Nk(o)}

dmin=min{dist(∏Ai(o),∏Ai(q))|q∈Nk(o)}

SPOD算法是一種檢測精度較高的離群挖掘算法，但存在以下不足：(1)依據局部屬性熵而設置的屬性權重為一固定值，并不能反映屬性本身的離群程度，且需要人為設置；(2)需兩次計算每個對象的k-鄰域。首次計算各對象的k-鄰域δ其目的是最終確定每個對象各個屬性在該鄰域δ內的權重參數ω.其后將會根據權重ω再次計算每個對象的k-鄰域δ′，并計算加權密度等，檢測基于鄰域δ′的局部離群點。計算鄰域是SPOD算法中最耗時的一個步驟，其時間復雜度為：O(d×m2).兩次計算鄰域直接造成算法運行時間變長，運算效率降低。此外，k-鄰域δ′及加權密度等相關量的計算是基于權重參數ω進行的，而權重ω是根據另一不同的鄰域k-鄰域δ內的離群屬性而設置的，因此鄰域δ′及其相關量的計算理論上并不是完全必要和合理的。

本文給出一種基于屬性熵和加權余弦相似度的離群數據挖掘算法LEAWCD.該算法首先根據局部屬性熵分析每個對象各個屬性在k-鄰域δ內的屬性偏離度，并據此自動設置相應的屬性權向量；然后使用對高維數據更有效的加權余弦相似度來度量各對象的離群程度，從而實現各對象在k-鄰域δ內的局部離群點檢測。

2 基于屬性熵和加權余弦相似度的離群數據挖掘算法

2.1 局部加權離群度量因子的計算

在SPOD算法中，若對象o關于屬性Ai的局部屬性熵大于其k-鄰域δ內各對象關于Ai的屬性熵均值，則將屬性Ai視為對象o在k-鄰域δ內的離群屬性。文中引入屬性偏離度來進一步判斷和衡量屬性離群的程度。

定義4(對象o的局部屬性偏離度)。對象o關于屬性Ai的局部屬性偏離度定義為：

(3)

其中：分子 LEAAi(o)為對象o關于屬性Ai的局部屬性熵，分母為對象o的k-鄰域δ內所有對象關于屬性Ai的局部屬性熵均值。當deviateLevel(o，Ai)大于1時，表明屬性Ai為對象o在k-鄰域δ內的離群屬性，且其值越大，說明該屬性離群的程度越高。

在文獻[11]中，將不同屬性分別賦以不同的權值。對于離群屬性設置為一固定的權重λ(λ>1)，而非離群屬性權重設為1.由于權重λ的值需要人為設置，因此挖掘結果易受人為因素影響，且固定的權重值無法精確反映屬性離群的程度。本文使用屬性權向量對不同屬性的權重進行定義。

(4)

而

其中，當deviateLevel(o，Ai)>1時，根據屬性偏離度的定義，屬性Ai為離群屬性。此時權重參數不再需要人工設置，而是設定為該屬性的屬性偏離度，以直接反映該離群屬性的離群程度。deviateLevel(o，Ai)≤1時，屬性Ai為非離群屬性，仍保持權值1不變。

(5)

(6)

參照文獻[6]，對象的局部加權離群因子定義如下：

(7)

ω1KOF用于度量對象的局部離群程度，計算所有對象的ω1KOF，并按升序排列，離群因子最小的n個對象就是所求的局部離群點。

2.2 算法的描述

輸入：數據集D，鄰域對象數k，離群點個數n.

輸出：離群點集

2.運用式(6)，計算每個對象在其k-鄰域δ內的加權中值向量，并用式(7)確定每個對象的局部加權離群因子ω1KOF；

3.依據局部加權離群因子ω1KOF采用快速排序法將各對象按升序排序；

4.輸出前n個對象，即為所求離群點集。

3 實驗

在PentiumIII-1.0G CPU，256M內存，Windows XP操作系統(tǒng)，DBMS為ORACLE9i環(huán)境下，用Visual C++6.0實現了SPOD和LEAWCD算法。實驗中采用國家天文臺提供的晚型星、高紅移類星體以及類星體三個天體光譜數據集。

(1)算法的精確度比較

為了驗證LEAWCD算法的正確性，選取SPOD[11]算法作為比較算法。其中，這三個數據集的維數為44維，兩種算法需共同設置的參數為鄰域中點數目k=7；另外，SPOD算法還需設置離群屬性權重λ=1.5.

表1 算法的檢測精確度比較

(2)算法對數據集維度的伸縮性

為了測試算法對數據集維度的伸縮性，在高紅移類星體光譜數據中分別取維數為10、20、30、40維對SPOD和LEAWCD算法的運算效率進行比較。實驗中，除維數外，其余參數的設置與測試算法精確度的實驗相同。由圖可知，在不同維度下，LEAWCD算法的運行時間基本上為SPOD算法的一半。這是因為對于這兩個算法，計算鄰域都是最耗時的步驟，其復雜度為O(d×m2).在SPOD算法中，需要兩次計算k-鄰域，而在本文算法中，僅需計算一次k-鄰域，因此本文LEAWCD算法其運行時間大約為SPOD算法的一半。

圖1 算法對數據集維數的伸縮性

4 結束語

目前的離群數據挖掘算法應用到高維數據時會出現“維災難”，效率較低。LEAWCD算法通過屬性偏離度自動設置權重，并使用對高維有效的加權余弦相似度來度量各對象的離群程度，實現了高維離群點檢測。理論分析和實驗結果表明，LEAWCD算法在減少用戶依賴，縮短運行時間，提高檢測精度上具有較明顯優(yōu)勢。

參考文獻：

[1] 薛安榮，鞠時光，何偉華，等.局部離群點挖掘算法研究[J].計算機學報，2007，30(8)：1-9.

[2] ARINDAM B，VIPIN K.Anomaly detection：a survey[J].ACM Computing Surveys (CSUR)，2009，41(3)：1-58.

[3] HE Z Y，XU X F，DENG S H.A fast greedy algorithm for outlier mining[C]∥Proceedings of PAKDD′2006(LNAD918).Singapore：NTU，2006：567-576.

[4] 張賀，蔡江輝，張繼福.信息熵度量的離群數據挖掘算法[J].智能系統(tǒng)學報，2010，5(2)：150-157.

[5] 于紹越，商琳.基于信息熵的相對離群點的檢測方法：ENBROD[J].南京大學學報，2008，44(2)：212-218.

[6] ANNA K.A fast outlier detection strategy for distributed high-dimensional data sets with mixed attributes[J].Data Mining and Knowledge Discovery，2010(20)：259-289.

[7] AGARWAL C，YU P S.An effective and efficient algorithm for high-dimensional outlier detection[J].The International Journal on Very Large Data Bases，2005，14(2)：211-221.

[8] ZHANG J F，JIANG Y Y，CHANG KAI H，et al.A concept lattice based outlier mining method in low dimensional subspaces[J].Pattern Recognition Letters，2009，30 (15)：1434-1439.

[9] 王磊，張繼福.基于屬性相關分析的離群數據并行挖掘算法[J].太原科技大學學報，2011，32(5)：364-368.

[10] 石巖，劉愛琴，張繼福.一種基于基尼指標的高維數據離群挖掘算法[J].太原科技大學學報，2013，34(3)：161-165.

[11] 倪巍偉，陳耿，陸介平，等.基于局部信息熵的加權子空間離群點檢測算法[J].計算機研究與發(fā)展，2008，45(7)：1189-1192.