劉愛(ài)琴，荀亞玲 (太原科技大學(xué)計(jì)算機(jī)學(xué)院，太原 030024)

離群數(shù)據(jù)挖掘是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支，其目的是找出隱含在海量數(shù)據(jù)中的相對(duì)稀疏而孤立的異常數(shù)據(jù)模式。離群數(shù)據(jù)挖掘有著廣泛的應(yīng)用，例如網(wǎng)絡(luò)非法入侵檢測(cè)及天文學(xué)上新星體發(fā)現(xiàn)等[1]。

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

1 相關(guān)研究

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

假設(shè)數(shù)據(jù)集D=(O，A)，對(duì)象集O={o1，o2，…om}，屬性集A={A1，…Ad}，對(duì)象o∈O關(guān)于屬性Ai的值記為∏Ai(o).

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

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

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

(1)

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

(2)

其中：

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

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

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

本文給出一種基于屬性熵和加權(quán)余弦相似度的離群數(shù)據(jù)挖掘算法LEAWCD.該算法首先根據(jù)局部屬性熵分析每個(gè)對(duì)象各個(gè)屬性在k-鄰域δ內(nèi)的屬性偏離度，并據(jù)此自動(dòng)設(shè)置相應(yīng)的屬性權(quán)向量；然后使用對(duì)高維數(shù)據(jù)更有效的加權(quán)余弦相似度來(lái)度量各對(duì)象的離群程度，從而實(shí)現(xiàn)各對(duì)象在k-鄰域δ內(nèi)的局部離群點(diǎn)檢測(cè)。

2 基于屬性熵和加權(quán)余弦相似度的離群數(shù)據(jù)挖掘算法

2.1 局部加權(quán)離群度量因子的計(jì)算

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

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

(3)

其中：分子 LEAAi(o)為對(duì)象o關(guān)于屬性Ai的局部屬性熵，分母為對(duì)象o的k-鄰域δ內(nèi)所有對(duì)象關(guān)于屬性Ai的局部屬性熵均值。當(dāng)deviateLevel(o，Ai)大于1時(shí)，表明屬性Ai為對(duì)象o在k-鄰域δ內(nèi)的離群屬性，且其值越大，說(shuō)明該屬性離群的程度越高。

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

(4)

而

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

(5)

(6)

參照文獻(xiàn)[6]，對(duì)象的局部加權(quán)離群因子定義如下：

(7)

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

2.2 算法的描述

輸入：數(shù)據(jù)集D，鄰域?qū)ο髷?shù)k，離群點(diǎn)個(gè)數(shù)n.

輸出：離群點(diǎn)集

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

3.依據(jù)局部加權(quán)離群因子ω1KOF采用快速排序法將各對(duì)象按升序排序；

4.輸出前n個(gè)對(duì)象，即為所求離群點(diǎn)集。

3 實(shí)驗(yàn)

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

(1)算法的精確度比較

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

表1 算法的檢測(cè)精確度比較

(2)算法對(duì)數(shù)據(jù)集維度的伸縮性

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

圖1 算法對(duì)數(shù)據(jù)集維數(shù)的伸縮性

4 結(jié)束語(yǔ)

目前的離群數(shù)據(jù)挖掘算法應(yīng)用到高維數(shù)據(jù)時(shí)會(huì)出現(xiàn)“維災(zāi)難”，效率較低。LEAWCD算法通過(guò)屬性偏離度自動(dòng)設(shè)置權(quán)重，并使用對(duì)高維有效的加權(quán)余弦相似度來(lái)度量各對(duì)象的離群程度，實(shí)現(xiàn)了高維離群點(diǎn)檢測(cè)。理論分析和實(shí)驗(yàn)結(jié)果表明，LEAWCD算法在減少用戶依賴(lài)，縮短運(yùn)行時(shí)間，提高檢測(cè)精度上具有較明顯優(yōu)勢(shì)。

參考文獻(xiàn)：

[1] 薛安榮，鞠時(shí)光，何偉華，等.局部離群點(diǎn)挖掘算法研究[J].計(jì)算機(jī)學(xué)報(bào)，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] 張賀，蔡江輝，張繼福.信息熵度量的離群數(shù)據(jù)挖掘算法[J].智能系統(tǒng)學(xué)報(bào)，2010，5(2)：150-157.

[5] 于紹越，商琳.基于信息熵的相對(duì)離群點(diǎn)的檢測(cè)方法：ENBROD[J].南京大學(xué)學(xué)報(bào)，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] 王磊，張繼福.基于屬性相關(guān)分析的離群數(shù)據(jù)并行挖掘算法[J].太原科技大學(xué)學(xué)報(bào)，2011，32(5)：364-368.

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

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