趙向兵

（1.太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，山西太原 030024；2.山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西大同 037009）

一種改進的基于加權(quán)屬性的SLOF離群點挖掘算法

趙向兵1，2

（1.太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，山西太原 030024；2.山西大同大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，山西大同 037009）

SLOF算法采用了空間對象的空間屬性和空間關(guān)系確定空間鄰域，并結(jié)合非空間屬性的權(quán)值來計算對象在其鄰域內(nèi)的離群度，但在計算屬性權(quán)值時，仍然由鄰域?qū)＜覜Q定，存在人為因素。文中采用計算每個對象的每個非空間屬性的去一劃分信息熵增量，并通過這個值來反映各個屬性對對象離群的貢獻程度，給出一種改進的SLOF算法。實驗結(jié)果表明，算法具有計算效率高和對用戶依賴性小的優(yōu)點。

高維數(shù)據(jù)；信息熵；息熵增量；屬性權(quán)值；偏離因子

離群點檢測是數(shù)據(jù)挖掘的重要分支之一，其目的是在大量的、復(fù)雜的數(shù)據(jù)集合中消除噪音數(shù)據(jù)或發(fā)現(xiàn)有意義的知識。Hawkins對離群點的定義抓住了概念的精髓：“一個離群點是一個觀察點，它偏離其它觀察點如此之大以至引起懷疑是由不同機制生成的”［1］。典型的應(yīng)用領(lǐng)域包括在電子商務(wù)的犯罪行為探測、網(wǎng)絡(luò)入侵檢測分析。

離群點查找的算法很多，大體上可分為：基于分布的、基于深度的、基于距離的、基于密度的和基于聚類的［2］。近年，Shekhar，Lu和Zhang學(xué)者最先提出二分算法［3］，該算法將空間屬性與非空間屬性區(qū)分開，并用對象與其鄰域的非空間屬性的比值或差值，來表示對象與其鄰域的偏差，簡稱為SLZ算法。SLZ算法沒有能夠解決空間數(shù)據(jù)的異質(zhì)性問題，因而，檢測的結(jié)果主要是全局離群點。Cbawla和Sun學(xué)者同時考慮了空間數(shù)據(jù)的異質(zhì)性和自相關(guān)性，入波動參數(shù)β，且用β和對象與其鄰域的歐拉距離的乘積表示空間局部離群度SLOM［4］。但由于對稱分布狀況決定β，若其在波動幅度較小或空間鄰居較少的情況下，很難準確的表現(xiàn)波動情況，因而出現(xiàn)漏檢和誤檢現(xiàn)象。為此，薛安榮等人提出了一種SLOF算法［5］，該算法用計算鄰域距離的方法解決空間自相關(guān)性問題，用計算空間局部離群系數(shù)的方法來解決空間異質(zhì)性問題，用對象的鄰域距離與鄰域中對象的平均鄰域距離之比表示對象的空間局部離群程度。但此算法在屬性權(quán)值的確定上，仍然由鄰域?qū)＜覜Q定，存在人為因素。

本文針對SLOF算法中屬性權(quán)值確定方面存在的問題，給出了一種SLOF改進型算法，該算法采用計算每個對象的每個非空間屬性的去一劃分信息熵增量，來確定屬性權(quán)值，從而消除人為因素，并使算法的用戶依賴度進一步減少。

1 基本概念和定義

1.1 信息熵

信息熵是信息論中信息和隨機變量的不確定性的一種度量［6］。設(shè)X是一個隨機變量，其取值集合為S（X），p（x）表示X的概率函數(shù)，則X的信息熵定義為：

說明隨機變量的不確定性越大，信息熵就越大；信息熵值越小，不確定性越小。

1.2 去一劃分信息熵增量

設(shè)D是對象集合，D的一個子集是S，并且｜S｜＞1，設(shè)q是S中的一個對象。則S被對象Q劃分為S-｛q｝和｛q｝兩個部分，記為=｛C1，C2｝，得到。則E（S）-E（）為子集S去一劃分信息熵增量，記為Δ（q，s），S明確的情況下，在下文中簡記為Δ（q）。

可以看出Δ（q）表示S被劃分為C?的前后信息熵的變化。從統(tǒng)計角度看，離群點挖掘的關(guān)鍵是檢測出在全局中占百分比小的數(shù)據(jù)對象，因為在子集S中Δ（q）值大的對象正是占百分比小的對象，這些對象更有可能是離群對象。也就是說離群點是指數(shù)據(jù)集合中一旦離群點被刪除，整個數(shù)據(jù)集的“混亂”或“不確定性”就明顯減少的數(shù)據(jù)點。對于對象集合中的某個對象來說，這個對象的每一個非空間屬性對這個對象的離群貢獻度的大小，就是看一下這個對象每一個非空間屬性值在它所對應(yīng)的非空間屬性值集合中的去一劃信息熵增量值的大小，即Δ（q）。所以我們用這個Δ（q）要表示非空間屬性的權(quán)值。

1.3 相關(guān)概念

空間鄰居：對象d的空間鄰居是指與對象d在指定條件c下，存在空間鄰接關(guān)系σc的對象。即?d∈D，?p∈D｛d｝，使得s（p）σcs（d）為真，則對象P是對象d的空間鄰居［5］。

空間鄰域：對象d的空間鄰域N（d）是指對象d的所有空間鄰居的集合，即

?d∈D，N（d）=｛p｜s（p）σcs（d）=ture，p∈D｛d｝｝

加權(quán)距離：在對象集D=｛d1，d2，…，dn｝，對象di，dj∈D，di和dj的M-維非空間屬性是f（di）和f（dj），則數(shù)據(jù)對象di，dj之間的M-維非空間屬性加權(quán)距離

其中：wk是第k維的權(quán)值，且0≥wk≥1（這里是對wk做了歸一化處理），這個距離表示了兩個對象間的偏差。

平均距離：對象d的平均距離是指對象d與其空間鄰域中所有對象的加權(quán)距離的平均值，即

平均距離表示對象與其鄰域非空間屬性上的偏差，偏差大的離群度就越高。

對象領(lǐng)域密度

空間局部離群度：空間對象d所有鄰居的鄰域密度平均值與d的鄰域密度的比值得到d的空間鄰域偏離因子，即：

KSLOF（d）反映對象d的非空間屬性偏離它周邊鄰居的程度。

2 用去一劃分信息熵差量確定非空間屬性的權(quán)重

在計算對象間非空間屬性距離的時候，不同屬性對分析目標的貢獻程度不同，可用熵權(quán)作為非空間屬性重要程度的度量。倪巍偉等對屬性權(quán)值的確定提出了離群屬性子集的概念，用局部信息熵描述數(shù)據(jù)點及其鄰域近數(shù)據(jù)點在屬性上投影的分布情況計算離群屬性的參考值，組成離群屬性子空間，屬于此空間的屬性賦以大于1的λ值，不屬于此空間的屬性賦1。這樣同樣沒有對屬性的權(quán)值做具體的量化，難于區(qū)分λ的具體值，且計算時比較復(fù)雜，也比較抽象。而SLOF算法對屬性權(quán)值確定的方法主要是對非空間屬性做規(guī)則化處理。根據(jù)分析需要，給不同貢獻度的屬性分配不同的權(quán)值，貢獻度大的權(quán)值大，反之則小，權(quán)值一般由鄰域?qū)＜覜Q定。所以這種方法，沒有對每個屬性的貢獻度做具體量化，且很難解釋，計算的數(shù)值有人為化因素，很難對分析數(shù)據(jù)做推廣。而去一劃分信息熵增量很好的解決了以上問題，方法如下：

設(shè)對象集合D=｛d1，d2，…，dn｝，由n個對象組成，對象d∈D的空間屬性函數(shù)s（d），非空間屬性函數(shù)是f（d），f（d）的維度是m維，m維非空間屬性f（d）表示為（f（d1），f（d2），…，f（dm））

按照定性和定量結(jié)合的原則得對象非空間屬性矩陣：

rij表示第i個對象在j-屬性上的值。且可以得出：f（dj）=rij（i=1，…，n，j=j）。

設(shè)p是m個對象中的第j個對象，所以p對象可以包含矩中m個值且每個值分別對應(yīng)對象的m個屬性值。接著我們可以分別計算這m個屬性值在它所對應(yīng)的屬性取值集合中計算去一劃分信息熵增量，分別記為Δ（p1），…，Δ（pm）。

對于p，在m維非空間屬性中，第j維屬性的權(quán)值記為wj，且wj=Δ（pj），（j∈m）。

根據(jù)去一劃信息熵增量的意義可知，對于對象p來說，在每個屬性上Δ（q）值越大，對象p的離群度就越大，它所對應(yīng)的屬性的離群度就越大，它的屬性權(quán)值就越大。進而根據(jù)屬性權(quán)值確定不同屬性對分析目標的貢獻程度。

3 改進的SLOF離群點檢測算法

根據(jù)上述分析，采用計算每個對象的每個非空間屬性的去一劃分信息熵增量，來確定屬性權(quán)值，從而有效地消除人為因素。其算法描述如下：

輸入：對象集D=｛d1，d2，…，dn｝（對象di的空間屬性函數(shù)s（di），非空間屬性函數(shù)是f（di），σc表示在指定條件c下的空間鄰接關(guān)系，m維非空間屬性f（di）表示為（f（dj1），f（dj2），…，f（djm）））。

輸出：離群度最大的前q個對象

Step1：從集合D中取一對象d，從D中尋找與d存在空間關(guān)系σc的所有鄰居，并確定對象d的鄰域N（d）；

Step2：利用（1）式和（6）式分別計算對象d在非空間屬性（f（d1），f（d2），…，f（dm））中各個屬性的去一劃分信息增量值，分別記為Δ（p1），…，Δ（pm）。從而確定對象d的非空間屬性的權(quán)值分別為wj，且wj=Δ（pj），（j到m）；

Step3：把wj代入（2）式計算加權(quán)距離，并利用（3）式計算對象d與空間鄰域中所有對象的加權(quán)距離的平均值；

Step4：利用（4）式和（5）式計算對象d的空間局部鄰域偏離因子KSNOF；

Step5：計算集合D中其它每個對象的空間鄰域偏離因子KSNOF；

Step6：把所對象的空間鄰域偏離因子KSNOF按降序排列；

Step7：輸出前q個對象，前q個對象就是空間離群點。

分析上述算法，該算法的復(fù)雜度為：O（n（klogsn+km+log2n））（k為對象的鄰居數(shù)），而LOF等算法確定鄰域卻采用的是全部屬性，其復(fù)雜度為O（kn2），所以采用此算法離群點檢測效率比較高。

4 實驗

試驗環(huán)境：CoreT7500 2.2G CPU，2G內(nèi)存，操作系統(tǒng)為Windows 2000，數(shù)據(jù)庫為SQL，并采用VC++編寫了上述算法。采用某省旅游景點情況統(tǒng)計數(shù)據(jù)，以200個旅游景點為研究對象，數(shù)據(jù)中既有空間屬性又有非空間屬性。對于各個景點，與它相鄰的景點可以組成其鄰域。選擇5個非空間屬性：tourists，greenrate，complaints，facilitation，satisfaction。通過20個景點評價對象計算得這五個非空間屬性權(quán)值p=｛0.18，0.20，0.15，0.19，0.33｝。實驗結(jié)果表明，這種算法檢測出的5個離群點確實是鄰域離群點，見表1。

表1 SLOF算法挖掘的5個離群點

為了進一步考察算法的性能，用LCK算法和SLZ算法與該算法進行比較，如圖1所示可知，該算法傾向于挖掘鄰域離群點，而SLZ算法和LCK算法偏向挖掘全局離群點，采用改進型SLOF算法的檢測精度較高，并且準確給出了其它離群數(shù)據(jù)對象的離群順序。也證明了改進型SLOF算法結(jié)果的得出是充分的考慮了空間數(shù)據(jù)的相關(guān)性和異質(zhì)性的結(jié)果，而SLZ算法和LCK算法都造成了局部離群點的漏選。從時間執(zhí)行上來看，由于空間屬性確定鄰域最費時間，這三種算法采用相同的數(shù)據(jù)和算法，因而確定鄰域的執(zhí)行時間一樣，比較總執(zhí)行時間應(yīng)在同一數(shù)量級上，執(zhí)行時間分別為SLOF：3.5s，SLZ：3.8s，LCK：4.1s。如果再把數(shù)據(jù)對象和維數(shù)做人工擴充，隨著對象和非空間屬性維數(shù)的增加，SLZ算法和LCK算法執(zhí)行效率會下降，執(zhí)行時間也會增加，但改進型SLOF算法卻有著很好的伸縮性，執(zhí)行時間增加幅度小于SLZ算法和LCK算法，因而它有著更好的性能。

圖1 檢測結(jié)果比較

5 結(jié)語

該算法充分考慮了空間數(shù)據(jù)的特點，根據(jù)空間關(guān)系確定空間鄰域，減少了用戶指定參數(shù)，特別是在非空間屬性的處理上，通過計算每個屬性去一劃分信息熵增量來確定屬性權(quán)值。進而確定非空間屬性的離群程度。此算法是對SLOF算法的改進，且易于解釋，去除人為因素的干擾。實驗表明，該算法在減少用戶依賴度、提高檢測精度上具有明顯的優(yōu)勢。

［1］Hawkms D.Identification of Outliers［M］.London：Chapman and Hall，1980.

［2］Han Jiawei，Kamber Micheline.Datamining：concepts and techniques［M］.San Francisco：Morgan Kaufmann Publishers，2001.

［3］Gulukota K，Sidney J，Sette A，et a1.Two complementary methods for predicting peptides binding major histocompatibility complex molecules［J］.Journal of Molecular Biology，1997，26：1258-1267.

［4］Brusic V，George R，Margo H，et a1.Prediction of MHC class II-binding peptides using an evolutionary algorithm and artificial neural network［J］.Bioinformatics，1998，14：121-130.

［5］薛安榮，鞠時光，何偉華，等.局部離群點挖掘算法研究［J］.計算機學(xué)報.2007，30（8）：1457-1458.

［6］Claude E S.A mathematical theory of communication［J］.Bell System Techical Journal，1948（27）：623-656.

〔編輯 高?！?/p>

SLOF based on Weighted Attribute of the Improved Algorithm for Outliermining

ZHAO Xiang-bing1，2
（1.School of Computer Science and Technology，Taiyuan University of Science＆Technology，Taiyuan Shanxi，030024； 2.School of Mathematics and Computer Science，Shanxi Datong University，Datong Shanxi，037009）

SLOF algorithm uses spatial properties and spatial relationships of spatial objects to determine spatial neighborhood and combined with the weight of non-spatial attributes to calculate the object＇s outlier in its neighborhood.However，the attribute weights are still determined by the neighborhood experts in the calculation，there are human factors.For each object，calculating leave-one division information entropy increment of each non-spatial attribute is introduced in this article when determining the right value of non-spatial attribute.This value can reflect the contribution of stray objects by the various attributes and furthermore an improved SLOF algorithm is given.Experimental results show that the algorithm has high computational efficiency and the advantage of less dependence on the user.

high dimensional data；entropy；entropy increment；attribute weights；deviation factor

O211.7

A

1674-0874（2011）03-0011-03

2011-02-06

趙向兵（1978-），男，山西大同人，在讀碩士，助教，研究方向：數(shù)據(jù)挖掘。