基于人工蜂群智能技術(shù)的屬性異常點(diǎn)檢測*

朱煥雄，劉 波

暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣州 510630

基于人工蜂群智能技術(shù)的屬性異常點(diǎn)檢測*

朱煥雄，劉 波+

暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣州 510630

為了解決數(shù)據(jù)庫屬性異常點(diǎn)檢測方法時間復(fù)雜度大并且查準(zhǔn)率和查全率不高的問題，提出了新的基于人工蜂群優(yōu)化技術(shù)（artificial bee colony，ABC）和O-measure度量（一種評估屬性異常點(diǎn)的度量）相結(jié)合的屬性異常點(diǎn)檢測方法，模擬人工蜂群隨機(jī)搜索較優(yōu)的食物源能力發(fā)現(xiàn)屬性異常點(diǎn)。針對群體智能算法檢測屬性異常點(diǎn)會陷入局部收斂的缺陷，提出使用模擬退火技術(shù)讓人工蜂群跳出局部最優(yōu)解而找到全局最優(yōu)解的算法。該算法通過蜂群在二維數(shù)據(jù)平面上搜索食物源,計算所經(jīng)過路徑上的數(shù)據(jù)項O-measure適應(yīng)度，從中尋找最優(yōu)解（即屬性異常點(diǎn)）。實驗結(jié)果表明，所提算法較之前的算法耗時短，且提高了檢測的準(zhǔn)確率和查全率。

屬性異常點(diǎn)；人工蜂群算法；模擬退火；O-measure

1 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)質(zhì)量問題成為人們?nèi)找骊P(guān)注的重點(diǎn)。數(shù)據(jù)庫中存在異常屬性值就是數(shù)據(jù)質(zhì)量問題之一。異常點(diǎn)[1]是數(shù)據(jù)集中出現(xiàn)與正常的數(shù)據(jù)集中不一致的數(shù)據(jù)，往往是錯誤的數(shù)據(jù)值，會降低數(shù)據(jù)的可用性[2]，對數(shù)據(jù)分析與挖掘產(chǎn)生較大的影響。為此有必要對數(shù)據(jù)異常點(diǎn)進(jìn)行檢測，其對保證數(shù)據(jù)的質(zhì)量具有重要的意義。

異常點(diǎn)（outlier）分為類異常點(diǎn)和屬性異常點(diǎn)[1,3]。類異常是指在具有類別屬性的數(shù)據(jù)集中存在的稀有類對象（元組或記錄等）[1,3]；屬性異常點(diǎn)是指數(shù)據(jù)集記錄中存在錯誤的屬性值或者是偏離正常分布的屬性值[1]，這些錯誤的屬性值通常由人為拼寫錯誤或傳輸過程出錯等引起。

文獻(xiàn)[4]介紹了一些常用的檢測類異常點(diǎn)方法，如基于統(tǒng)計的方法、基于分類的方法、基于聚類的方法等[4]，但是檢測類異常點(diǎn)的方法不能直接用于檢測屬性異常點(diǎn)。因此Koh等人[5]提出采用O-measure、P-measure、Q-measure標(biāo)準(zhǔn)度量來衡量屬性異常點(diǎn)，對產(chǎn)生的數(shù)據(jù)子空間中的每個屬性計算這3個標(biāo)準(zhǔn)度量值，使用OODS（outlier detection from data space）算法對屬性異常點(diǎn)進(jìn)行檢測，由于算法需要產(chǎn)生數(shù)據(jù)子空間，檢測的時間復(fù)雜度相當(dāng)高。文獻(xiàn)[3]將群體智能技術(shù)應(yīng)用在屬性異常點(diǎn)檢測；文獻(xiàn)[6]提出兩個數(shù)據(jù)項集之間相關(guān)可信度度量的概念，并利用該度量檢測離散型屬性孤立點(diǎn)；文獻(xiàn)[7]提出基于函數(shù)依賴的異常點(diǎn)檢測方法；文獻(xiàn)[8]采用FP-growth算法挖掘出非頻繁數(shù)據(jù)項集，結(jié)合異常度量閾值對異常點(diǎn)檢測，但是算法時間復(fù)雜度較高；蔡美等人[9]提出基于蟻群算法的屬性異常點(diǎn)檢測方法，但是容易陷入局部最優(yōu)。

本文在已有的屬性異常點(diǎn)檢測算法基礎(chǔ)上，擬研究新的屬性異常點(diǎn)的檢測方法，主要有以下貢獻(xiàn)：

（1）提出了新的基于人工蜂群算法的屬性異常點(diǎn)檢測算法。具體地講，首先將數(shù)據(jù)集記錄去重，統(tǒng)計相應(yīng)元組在原數(shù)據(jù)集中的頻數(shù)；然后將去重后的數(shù)據(jù)集記錄（不包括頻數(shù)）映射到一個二維的搜索平面，數(shù)據(jù)集的每個數(shù)據(jù)項對應(yīng)到二維平面上的點(diǎn)；隨后充分利用蜂群在二維平面上的局部尋優(yōu)能力和隨機(jī)尋優(yōu)能力尋找最優(yōu)食物源，每次迭代后將較小的屬性O(shè)-measure度量值存儲到異常結(jié)果表中，根據(jù)屬性的O-measure值越小而屬性異常可能性越大的原則[5]，最終發(fā)現(xiàn)屬性異常點(diǎn)。

（2）為了避免群體智能算法陷入局部最優(yōu)的情形，本文將模擬退火的機(jī)制引入人工蜂群算法中。雖然文獻(xiàn)[10]也提出使用模擬退火算法改進(jìn)人工蜂群算法，但該算法省去了人工蜂群算法中的偵察蜂階段，在算法執(zhí)行后期全局搜索能力會受到很大的影響，而本文算法在偵察蜂執(zhí)行階段能搜索全局最優(yōu)解。

（3）通過實驗驗證了本文提出的人工蜂群智能算法能縮短屬性異常點(diǎn)的檢測時間，提高算法的查準(zhǔn)率和查全率。對提出的人工蜂群算法在檢測屬性異常點(diǎn)準(zhǔn)確性上進(jìn)行相應(yīng)的效果分析。

2 人工蜂群算法及相關(guān)概念

2.1 人工蜂群算法

人工蜂群算法[11-13]由土耳其學(xué)者Karaboga于2005年提出，它通過模擬蜜蜂采蜜覓食的行為而尋找優(yōu)化問題的解，具有收斂速度快、并行的特征，而且能避免陷入局部最優(yōu)。人工蜂群算法不僅在解決多維函數(shù)優(yōu)化和組合優(yōu)化問題上具有優(yōu)勢[11]，在聚類算法中也有相應(yīng)的應(yīng)用[13]。謝娟等人[14]提出基于近似梯度引導(dǎo)的人工蜂群搜索策略，曹春紅等人[15]提出改進(jìn)的人工蜂群算法，并用于幾何約束問題上。人工蜂群算法中蜜蜂的基本組成主要有：引領(lǐng)蜂、跟隨蜂和偵察蜂[11]。引領(lǐng)蜂的數(shù)量或者跟隨蜂的數(shù)量等于蜂群數(shù)量的一半，也等于食物源的數(shù)量[11]，蜜源的位置表示優(yōu)化問題的可行解。人工蜂群算法求解問題的步驟如下：

（1）初始化人工蜂群算法參數(shù)階段。設(shè)置蜂群的數(shù)量、引領(lǐng)蜂的個數(shù)、最大迭代次數(shù)、limit參數(shù)等。

（2）引領(lǐng)蜂階段。隨機(jī)分配引領(lǐng)蜂到蜜源的各個位置進(jìn)行食物源的搜索，每個引領(lǐng)蜂與一個食物源對應(yīng)，計算引領(lǐng)蜂所在位置食物源的適應(yīng)度，引領(lǐng)蜂根據(jù)式（1）在鄰域內(nèi)搜索新的食物源。當(dāng)引領(lǐng)蜂搜索到更優(yōu)的食物源時，更新引領(lǐng)蜂的位置，否則食物源未更新次數(shù)加1。

其中，j是隨機(jī)選擇的下標(biāo)，j∈(1,2,…,D)，D是維數(shù)，i∈(1,2,…,SN)，k∈(1,2,…,SN)，SN是蜂群的數(shù)量，k表示不同于i的蜜源；α是一個隨機(jī)參數(shù)，α∈[-1,1];NXij表示新的位置；Xij表示原來的位置。

（3）跟隨蜂階段。跟隨蜂根據(jù)式（2）計算得到的選擇概率，選擇一個食物源：

其中，fiti表示蜜蜂的適應(yīng)度值（如O-measure(Ai,t)，見式（4））；N表示食物源的數(shù)量。跟隨蜂被選中后，也是按照式（1）在其附近尋找更優(yōu)的蜜源，然后保存更優(yōu)的食物源。

（4）偵察蜂階段。當(dāng)某個食物源未更新的次數(shù)達(dá)到一定的數(shù)量（limit）后，放棄該食物源，食物源所對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?，然后偵察蜂按照式?）全局搜索新的未被訪問過的數(shù)據(jù)空間，尋找新的并且更優(yōu)的食物源。

（5）記錄本次迭代后的最優(yōu)解。

（6）繼續(xù)執(zhí)行步驟（2），直到蜂群算法達(dá)到收斂狀態(tài)或者是達(dá)到最大的迭代次數(shù)為止。

2.2 O-measure的相關(guān)概念

定義1（支持度）假設(shè)關(guān)系R中有m個屬性A1,A2,…,Am，S是R上包含屬性Au…Av的投影，記作S=πAu…Av(R)。在S中，某個元組s的支持度sup(s)就是該元組s在關(guān)系R上對應(yīng)屬性(Au,…,Av)上具有相同屬性值的元組個數(shù)。

定義2（鄰居）對于元組s=＜au…av＞，設(shè)屬性Av是目標(biāo)屬性，目標(biāo)屬性的鄰居記為N(Av,s)，且有N(Av,s)=＜au…av-1＞，即s中不包含屬性Av的項。

定義3（屬性異常度量O-measure）假設(shè)元組s=＜au…av＞，對目標(biāo)屬性Av的O-measure計算公式為：

一個經(jīng)過處理后的數(shù)據(jù)集（選取國家、州、城市3個維度）示例如表1所示，對原來的數(shù)據(jù)集進(jìn)行相應(yīng)的預(yù)處理操作。首先對數(shù)據(jù)集進(jìn)行去重，所謂去重是將相同的元組當(dāng)作一條記錄，然后統(tǒng)計該元組的頻數(shù)，如果某個元組不存在相同的元組則頻數(shù)為1。

Table 1 Dataset example表1 數(shù)據(jù)集示例

在表1中，令元組s=＜美國,紐約,紐約＞，元組t=＜澳大利亞,維多利亞,紐約＞,由式（4）定義可知：

因為O-measure（城市,t）＜O-measure（城市,s），所以“紐約”在元組t中是屬性異常點(diǎn)的可能性更大，而在元組s中是屬性異常點(diǎn)的可能性較小。

2.3 模擬退火算法

模擬退火算法[16]是一種全局優(yōu)化算法，采用概率機(jī)制來控制解的接受與否，對于好的解，無條件地接受，反之，以一定的概率接受解。應(yīng)用到人工蜂群算法中，蜜蜂將有更大的概率搜索到其他更優(yōu)質(zhì)的食物源，能很好地避免陷入局部最優(yōu)解。模擬退火算法需要設(shè)置一個初溫，算法執(zhí)行后，溫度不斷發(fā)生變化，在變化過程中，新食物源的位置也是按式（1）產(chǎn)生，引領(lǐng)蜂和跟隨蜂在搜索時對較差適應(yīng)度（O-measure值較大）的食物源具有一定的選擇概率，而不采用原始人工蜂群算法的貪心選擇策略，擴(kuò)大食物源的搜索范圍。模擬退火算法滿足式（5）的條件時會選擇較差適應(yīng)度的食物源。

其中，F(xiàn)c表示當(dāng)前食物源的適應(yīng)度；Fne表示新的食物源的適應(yīng)度；Temp(t)表示當(dāng)前時刻的溫度值。每次迭代時溫度的更新公式如下：

其中,?表示改變的因子，一般取?∈(0.9,1.0)；Temp(t)表示當(dāng)前時刻的溫度；Temp(t+1)表示下一時刻的溫度。

本文采取的方法是在引領(lǐng)蜂和跟隨蜂階段能使用模擬退火算法尋找全局較優(yōu)解，而不只是貪婪選擇較優(yōu)的解，并且偵查蜂階段也能夠搜索到全局較優(yōu)解。

3 利用人工蜂群智能屬性異常點(diǎn)的檢測

3.1 基本思路及IABC_Detection算法

為了模擬蜂群在二維平面上搜索最優(yōu)解，將預(yù)處理后關(guān)系型數(shù)據(jù)集中的每個數(shù)據(jù)項對應(yīng)到二維平面圖中的一個結(jié)點(diǎn)，每個結(jié)點(diǎn)由記錄所在維度的編號和屬性所在維度的編號確定。圖1表示表1的數(shù)據(jù)集（國家、州、城市屬性的投影）對應(yīng)的二維平面，平面上的結(jié)點(diǎn)“□”表示數(shù)據(jù)集中的一個屬性值，蜂群可以在該平面圖中搜索和尋找較優(yōu)的食物源時發(fā)現(xiàn)屬性異常點(diǎn)。圖1中的一條路徑展示了蜜蜂尋找較優(yōu)食物源（即屬性異常數(shù)據(jù)）的過程。

Fig.1 Bee's foraging source path圖1 人工蜂群搜索食物源過程

將人工蜂群算法和O-measure度量相結(jié)合的思路如下：首先，將數(shù)據(jù)集對應(yīng)到蜂群可以搜索的二維平面，充分利用蜂群的鄰近搜索和隨機(jī)搜索的覓食能力，在搜索平面中尋找較優(yōu)的食物源，存儲每次迭代后較優(yōu)屬性的O-measure度量值，并將相應(yīng)的計算結(jié)果存入異常結(jié)果表中。接著，根據(jù)屬性的O-measure值的大小找出屬性異常點(diǎn)。為了防止群體智能算法在查找屬性異常點(diǎn)時陷入局部收斂狀態(tài)，再將模擬退火技術(shù)引入到上述思路中，所提出的算法記為IABC_Detection。

IABC_Detection算法步驟如下：

（1）初始化人工蜂群算法的相關(guān)參數(shù)，如蜂群的數(shù)量為SN，引領(lǐng)蜂的數(shù)量為SN/2，算法迭代的次數(shù)為t，模擬退火的初始溫度等。

（2）引領(lǐng)蜂被隨機(jī)分配到二維數(shù)據(jù)平面，然后對每個位置的引領(lǐng)蜂計算它們的適應(yīng)度（O-measure值），按照模擬退火機(jī)制選擇適應(yīng)度較好的食物源，更新異常結(jié)果表S或者保存適應(yīng)度較好的屬性值到異常結(jié)果表S。

（3）跟隨蜂在跟隨蜂附近搜索也是按照模擬退火機(jī)制選擇適應(yīng)值較好的食物源。

（4）當(dāng)某個食物源未更新的次數(shù)超過limit，則該食物源對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?，放棄該食物源，偵察蜂進(jìn)行隨機(jī)搜索，全局搜索較優(yōu)的食物源并且評估它們的適應(yīng)度。

（5）記錄本次迭代的最優(yōu)解，模擬退火算法的溫度發(fā)生變化。

（6）回到步驟（2），重復(fù)執(zhí)行直到算法收斂或者是算法達(dá)到終止條件。

（7）輸出屬性異常點(diǎn)。

IABC_Detection算法實現(xiàn)的具體說明如下：

在步驟（1）中，初始化參數(shù)，如人工蜂群的數(shù)量SN，引領(lǐng)蜂的數(shù)量、跟隨蜂的數(shù)量SN/2，算法迭代的次數(shù)t，模擬退火的初始溫度（一般取1 000）；還有l(wèi)imit參數(shù)，算法執(zhí)行時若食物源的適應(yīng)度經(jīng)過limit次都沒更新，則該食物源被放棄，且該引領(lǐng)蜂轉(zhuǎn)化為偵察蜂，偵察蜂重新在二維平面進(jìn)行搜索。此外，引領(lǐng)蜂的數(shù)目或跟隨蜂的數(shù)目與最優(yōu)食物源的數(shù)目相等。

在步驟（2），算法隨機(jī)分配引領(lǐng)蜂到二維數(shù)據(jù)平面上，每個引領(lǐng)蜂的位置可以表示為Lij，Lij也表示元組ti中屬性Aj的屬性值。對每個引領(lǐng)蜂所在的食物源計算適應(yīng)度（即O-measure），然后在該引領(lǐng)蜂附近按照式（1）搜索更優(yōu)的食物源，并且計算該食物源的適應(yīng)度。引領(lǐng)蜂按照模擬退火機(jī)制選擇適應(yīng)度較好的食物源存入異常結(jié)果表，異常結(jié)果表S的結(jié)構(gòu)定義為四元組(T,A,V,M)。其中T是元組的ID，A是目標(biāo)屬性的名稱，V是該目標(biāo)屬性A所對應(yīng)的值，M是目標(biāo)屬性A所對應(yīng)的O-measure值。在異常結(jié)果表S中搜索是否存在元組s，使得元組s滿足N(Ak,s[T])=N(Ak,t),s[A]=Ak,s[V]≠t[Ak]。假如存在這樣的元組s并且有O-measure(Ak,t)＜s[M]，則更新元組s，其中s[V]=t[Ak],s[M]=O-measure(Ak,t),s[T]=t；否則將四元組(t,Ak,t[Ak],O-measure(Ak,t))插入到表S中。

在步驟（3）中，跟隨蜂按照式（1）搜索新食物源，并且計算新食物源的適應(yīng)度，采用模擬退火機(jī)制選擇較優(yōu)的食物源，并且將較優(yōu)的食物源及其相應(yīng)的適應(yīng)度存儲到異常結(jié)果表S中。

在步驟（4）中，偵察蜂按照式（3）選擇蜜源的位置，然后在整個搜索空間進(jìn)行新的食物源搜索，繼續(xù)計算這些蜂所對應(yīng)食物源的適應(yīng)度，記錄本次迭代后得到最優(yōu)的食物源以及相應(yīng)的適應(yīng)度。

在步驟（5）中，記錄每次迭代的最優(yōu)解，模擬退火算法的溫度根據(jù)式（6）進(jìn)行相應(yīng)的變化。

3.2 算法執(zhí)行的時間復(fù)雜度分析

假定數(shù)據(jù)集元組的個數(shù)為n，選擇的屬性個數(shù)是k，總的蜂群個數(shù)為a，偵察蜂的個數(shù)為g，較優(yōu)食物源的個數(shù)為m，迭代次數(shù)為t，算法執(zhí)行的時間復(fù)雜度分析過程如表2所示。

Table 2 Time complexity analysis of algorithm表2 算法時間復(fù)雜度計算

由表2的時間復(fù)雜度計算可以知道，算法總的時間復(fù)雜度為O(mat)，全搜索算法需要雙重循環(huán)遍歷數(shù)據(jù)集，因此算法的時間復(fù)雜度為O(kn2)，對于大規(guī)模數(shù)據(jù)集，kn2?mat，從而本文算法時間復(fù)雜度比全搜索算法的時間復(fù)雜度低。

3.3 IABC_Detection算法檢測屬性異常點(diǎn)的效果分析

人工蜂群算法具有全局尋優(yōu)能力，并且收斂速度相對較快[17]。設(shè)IABC_Detection算法全局搜索尋找優(yōu)質(zhì)食物源后找到的解有N個，其中屬性異常點(diǎn)的個數(shù)為n，非屬性異常點(diǎn)的個數(shù)為N-n。在原始的人工蜂群算法中，蜂群按照貪婪擇優(yōu)的方法選擇食物源[17]，如果新食物源的適應(yīng)度優(yōu)于舊食物源的適應(yīng)度，新的食物源代替舊的食物源；否則保留舊的食物源，當(dāng)食物源的適應(yīng)度經(jīng)過limit次都沒改進(jìn)時，該食物源將被丟棄。人工蜂群算法每一次迭代后將產(chǎn)生局部最優(yōu)解，當(dāng)算法執(zhí)行結(jié)束時，在找到的N個食物源中，屬性異常點(diǎn)的個數(shù)n會大于非屬性異常點(diǎn)的個數(shù)，因此找到屬性異常點(diǎn)的概率(n/N)大于找到非屬性異常點(diǎn)的概率(N-n)/N，IABC_Detection算法查準(zhǔn)率較高。

引入模擬退火的IABC_Detection算法能找到屬性異常點(diǎn)的概率同樣較高，即使算法開始時，蜂群會有較大的幾率選擇差的食物源，但算法總的目標(biāo)是貪心選擇適應(yīng)度好的食物源作為目標(biāo)解。

隨著數(shù)據(jù)集的元組數(shù)或?qū)傩詡€數(shù)增大，當(dāng)給定蜂群數(shù)量一定時，雖然偵查蜂能進(jìn)行全局搜索，但蜂群在尋找最優(yōu)食物源的時候仍然可能會出現(xiàn)搜索不到目標(biāo)解的情形，算法的查全率會受到一定的影響。IABC_Detection算法采用模擬退火機(jī)制，能有效地跳出局部最優(yōu)解，擴(kuò)大解的搜索范圍，從中尋找更多全局較優(yōu)解。

設(shè)蜂群總數(shù)為SN，X(0)表示算法運(yùn)行時的初始解集（每個解集X含有SN/2個解，這也是造成蜂群的數(shù)目會影響查全率的因素），X(n)表示迭代第n次蜂群求得的解集，f表示適應(yīng)度，T表示蜂群從當(dāng)前解狀態(tài)移動到下一個解狀態(tài)。

蜂群在尋找最優(yōu)食物源時，都是從一個位置移動到新的位置，因此人工蜂群算法的狀態(tài)轉(zhuǎn)移可以表示為：

又新的解集X(n+1)僅與X(n)有關(guān)，{X(n),n∈N+}是有限齊次Markov鏈，由此得出蜂群移動時概率計算如下所示：

否則P(X,Y)=0。

因為人工蜂群算法結(jié)合模擬退火算法之后，都將會選擇較優(yōu)的食物源作為解，所以當(dāng)給定初始的引領(lǐng)蜂的解，并且蜂群內(nèi)部進(jìn)行無數(shù)次的迭代后，人工蜂群算法的Markov鏈種群系列能以概率1收斂于全局屬性異常點(diǎn)集合M，如式（9）所示：

4 模擬實驗

4.1 實驗環(huán)境

算法模擬平臺為計算機(jī)Intel?CoreTMi5-3210 CPU@2.50 GHz，內(nèi)存2 GB，Windows7 OS，編程語言Java，集成開發(fā)環(huán)境為eclipse-jee-neon-R-win32。實驗以文獻(xiàn)[9]所采用的worldclock數(shù)據(jù)集（http://www.timeanddate.com/worldclock/）的模式為基準(zhǔn)，隨機(jī)產(chǎn)生10、30、50、70萬條數(shù)據(jù)記錄，每1萬條記錄有一個屬性錯誤值。worldclock數(shù)據(jù)集的屬性包括國家、州、城市、所在時區(qū)、夏至?xí)r北京時差、與北京時差。

為了測試IABC_Detection的有效性，將其與全搜索方法（Full_search）、基于非頻繁數(shù)據(jù)項集的異常點(diǎn)檢測方法[8]（Associating detection）、基于ACO算法的屬性異常點(diǎn)檢測方法[9]（Ant_Omeasure）在相同的數(shù)據(jù)集條件下進(jìn)行對比實驗。Full_search方法對數(shù)據(jù)集中每條記錄的每個屬性計算O-measure值，采用IABC_Detection算法的步驟（2）中更新異常表的規(guī)則更新異常結(jié)果表S，然后排序篩選出O-measure值小的屬性值作為屬性異常點(diǎn)。在IABC_Detection算法實驗中，一些參數(shù)經(jīng)過測試調(diào)整后獲得最優(yōu)結(jié)果，如蜂群的數(shù)量設(shè)置為20～200，迭代次數(shù)t為2 000～2 500次，參數(shù)limit設(shè)置為20～30，O-measure閾值為0.010。

4.2 實驗結(jié)果及分析

每種算法對數(shù)據(jù)集執(zhí)行50次后取平均值作為有效數(shù)據(jù)，結(jié)果如圖2、圖3、圖4所示。算法所使用的查準(zhǔn)率和查全率計算公式如式（10）和式（11）所示：

Fig.2 Execution time of different algorithms圖2 算法的執(zhí)行時間對比圖

Fig.3 Comparison of recall ratio圖3 算法的查全率對比圖

Fig.4 Comparison of precision ratio圖4 算法的查準(zhǔn)率對比圖

圖2是不同算法的執(zhí)行時間對比圖，結(jié)果表明Full_search算法要耗費(fèi)的時間最多，IABC_Detection算法消耗的時間最少。采用Full_search方法計算屬性O(shè)-measure值時，時間主要耗費(fèi)在計算大量正常屬性的O-measure值，而且隨著數(shù)據(jù)集增多，全搜索算法尋找屬性異常點(diǎn)所需要的時間也將顯著增加。而IABC_Detection算法能充分利用蜂群的智能行為，在尋找最優(yōu)食物源的過程中計算屬性的O-measure值，算法在每一次迭代執(zhí)行后記錄找到的最優(yōu)解，然后將較好的適應(yīng)度值存入結(jié)果集表中，進(jìn)而找到屬性異常點(diǎn)，可以減少對正常屬性計算O-measure值的時間。Associating detection算法進(jìn)行檢測需要遍歷所有的數(shù)據(jù)值，因此耗費(fèi)的時間多。Ant_Omeasure在數(shù)據(jù)量大時檢測時間多于IABC_Detection算法，主要是人工蜂群算法能避免陷入局部最優(yōu)，收斂速度會比蟻群算法快，同時也能保證查全率。

圖3、圖4分別給出了幾個算法分別在同樣的數(shù)據(jù)集下運(yùn)行得到的查全率和查準(zhǔn)率。實驗結(jié)果表明，采用全搜索算法，在數(shù)據(jù)集大時雖能找出屬性異常點(diǎn)，但在數(shù)據(jù)量小時會將許多正確的屬性值誤判成異常屬性；而且全搜索算法對每條記錄的每個屬性計算O-measure值，會出現(xiàn)很多屬性的O-measure值等于2，導(dǎo)致將很多正常的屬性值誤判成異常屬性，造成全搜索算法查準(zhǔn)率和查全率不高。IABC_Detection算法的查全率和查準(zhǔn)率雖沒達(dá)到100%，但I(xiàn)ABC_Detection算法能充分利用蜂群的智能行為尋找最優(yōu)食物源的過程尋找屬性異常點(diǎn)，提高了屬性異常點(diǎn)檢測的查全率和查準(zhǔn)率；由于蜂群算法采用的是群體智能的思想，算法執(zhí)行搜索時具有一定的啟發(fā)性，但也有可能會陷入局部收斂狀態(tài)，因此也會出現(xiàn)搜索不到屬性異常點(diǎn)的情形。而Associating detection算法采用基于非頻繁項集異常度量的方法沒有O-measure度量值準(zhǔn)確，IABC_Detection算法的查全率高于Ant_Omeasure的查全率，是由于IABC_Detection算法能夠防止陷入局部收斂，尋找更多的全局較優(yōu)解。

下面給出IABC_Detection算法中參數(shù)值對結(jié)果的影響：

（1）O-measure閾值的設(shè)定。設(shè)定閾值α對異常結(jié)果集表S進(jìn)行裁剪，即當(dāng)屬性的O-measure值大于閾值α?xí)r，對結(jié)果集表S中相應(yīng)的數(shù)據(jù)進(jìn)行刪除。經(jīng)過反復(fù)實驗發(fā)現(xiàn)，當(dāng)α=0.010時，算法具有較好的查準(zhǔn)率，不會影響找到的異常屬性點(diǎn)。

（2）迭代次數(shù)t對算法收斂性的影響。初始時，蜂群隨機(jī)選擇食物源，算法的查全率不高，但是隨著算法迭代次數(shù)增加，當(dāng)?shù)螖?shù)增加到2 000次左右時，算法能找到的屬性異常點(diǎn)數(shù)量將不再有大的變化，算法趨于收斂狀態(tài)，查全率也趨于穩(wěn)定。迭代次數(shù)對算法收斂性的影響實驗結(jié)果如圖5所示。

（3）引領(lǐng)蜂的數(shù)量對屬性異常點(diǎn)查全率的影響。因為引領(lǐng)蜂的數(shù)量等于蜂群數(shù)量的一半，所以算法初始時蜂群數(shù)量設(shè)置得少，引領(lǐng)蜂的數(shù)量就少，最終能檢測到的屬性異常點(diǎn)就較少。但是當(dāng)引領(lǐng)蜂的數(shù)量接近實際屬性異常點(diǎn)個數(shù)時，算法趨于收斂狀態(tài)。即使引領(lǐng)蜂的數(shù)量繼續(xù)增加，算法檢測到屬性異常點(diǎn)的個數(shù)也不會增多，可以使用此特點(diǎn)判斷屬性異常點(diǎn)的個數(shù)。引領(lǐng)蜂的數(shù)量對屬性異常點(diǎn)查全率的影響實驗結(jié)果如圖6所示。

Fig.5 Recall ratio to different number of iterations圖5 迭代次數(shù)對查全率的影響

Fig.6 Recall ratio to different number of employed bees圖6 引領(lǐng)蜂的個數(shù)對查全率的影響

（4）參數(shù)limit的設(shè)置。當(dāng)尋找到食物源的適應(yīng)度經(jīng)過limit次未發(fā)生改變時，該食物源將被丟棄，并且該食物源對應(yīng)的引領(lǐng)蜂變?yōu)閭刹旆?，偵察蜂重新在全局搜索空間搜索新的食物源。參數(shù)limit如果設(shè)置得太大，容易陷入局部最優(yōu)，但limit設(shè)置得太小，算法很難收斂。經(jīng)實驗發(fā)現(xiàn)，limit設(shè)置在20～30時算法的效果較佳。

4.3 F-score值的比較

為了將本文算法與其他文獻(xiàn)對屬性異常點(diǎn)的性能評估方法一致，使用F-score度量（見式（12））對數(shù)據(jù)異常點(diǎn)的檢測效率進(jìn)行評估。分別將本文算法與Full_search、Ant_Omeasure、Associating detection采取同樣的數(shù)據(jù)集進(jìn)行實驗并計算相應(yīng)的F-score值。表3顯示了這些算法對worldclock數(shù)據(jù)集檢測屬性異常點(diǎn)得到的平均F-score值，由此表的結(jié)果可得出，本文采用改進(jìn)的人工蜂群屬性異常點(diǎn)檢測算法效果最好，在數(shù)據(jù)集大的時候IABC_Detection的檢測能避免陷入局部最優(yōu)解，找到的屬性異常點(diǎn)將會更多。

Table 3 F-score values of related algorithms表3 相關(guān)算法的F-score值比較表 %

總之，實驗結(jié)果表明本文提出的人工蜂群算法結(jié)合O-measure度量的方法對于屬性異常點(diǎn)的檢測耗時少，并且提高了查準(zhǔn)率和查全率。

5 結(jié)束語

本文使用蜂群算法對屬性異常點(diǎn)進(jìn)行檢測，利用O-measure度量評估異常屬性值，將數(shù)據(jù)集對應(yīng)到二維平面，讓引領(lǐng)蜂、觀察蜂和偵察蜂通過群體智能在二維平面中搜索尋找最優(yōu)解。針對群體智能算法會陷入局部較優(yōu)解的情況，將模擬退火機(jī)制引入其中，使算法跳出局部最優(yōu)解狀態(tài)，找出全局最優(yōu)解。下一步將研究如何采用并行計算技術(shù)讓蜂群對海量高維的數(shù)據(jù)集尋找屬性異常點(diǎn)。

[1]Wu Xindong.Class noise vs attribute noise:their impacts,detection and cleansing[C]//LNCS 4426:Proceedings of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,Nanjing,China,May 22-25,2007.Berlin,Heidelberg:Springer,2007:7-8.

[2]Li Jianzhong,Liu Xuanmin,An important aspect of big data:data usability[J].Journal of Computer Research and Development,2013,50(6):1147-1162.

[3]Liu Bo,Cai Mei,Yu Jiazong.Swarm intelligence and its application in abnormal data detection[J].Informatica,2015,39(1):63-69.

[4]Han Jiawei,Micheline K.Data mining concepts and techniques[M].3rd ed.Fan Ming,Meng Xiaofeng,trans.Beijing:Machinery Industry Press,2012.

[5]Koh J L Y,Lee M L,Hsu W,et al.Correlation-based detection of attribute outliers[C]//LNCS 4443:Proceedings of the 12th International Conference on Database Systems for Advanced Applications,Bangkok,Thailand,Apr 9-12,2007.Berlin,Heidelberg:Springer,2007:164-175.

[6]Liu Bo,Pan Jiuhui.Study of abnormal data detecting method using attribute correlation analysis[J].Systems Engineering and Electronics,2011,33(1):202-207.

[7]Chiang F,Miller R J.Discovering data quality rules[J].Proceedings of the VLDB Endowment,2008,1(1):1166-1177.

[8]Kao L J,Huang Y P,Sandnes F E.Associating absent frequent itemsets with infrequent items to identify abnormal transactions[J].Applied Intelligence,2015,42(4):694-706.

[9]Cai Mei,Liu Bo.Abnormal data detection method based on ant colony algorithm[J].Computer Engineering,2016,42(8):166-169.

[10]Yang Qun,Cao Xiangyu,Gao Jun.Array synthesis on the basis of an improved artificial bee colony algorithm[J].Journal of Microwaves,2014,30(S1):37-40.

[11]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Erciyes University,2005.

[12]Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[13]Karaboga D,Ozturk C.A novel clustering approach:artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2011,11(1):652-657.

[14]Xie Juan,Su Shoubao,Wang Jiwen.Search strategy of artificial bee colony algorithm guided by approximate gradient[J].Journal of Frontiers of Computer Science and Technology,2016,10(12):1773-1782.

[15]Cao Chunhong,Xu Guangxing.Geometric constraint solving based on improved artificial bee colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2015,9(9):1122-1131.

[16]Zhang Defu,Peng Yu,Zhu Wenxing,et al.A hybrid simulated annealing algorithm for solving three dimensional packing problem[J].Journal of Computer Science,2009,32(11):2147-2156.

[17]Ning Aiping,Zhang Xueying.Convergence analysis of artificial bee colony algorithm[J].Control and Decision,2013,28(10):1554-1558.

附中文參考文獻(xiàn)：

[2]李建中,劉顯敏.大數(shù)據(jù)的一個重要方面:數(shù)據(jù)可用性[J].計算機(jī)研究與發(fā)展,2013,50(6):1147-1162.

[4]Han Jiawei,Micheline K.數(shù)據(jù)挖掘概念與技術(shù)[M].3版.范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2012.

[6]劉波,潘久輝.采用屬性相關(guān)分析的異常數(shù)據(jù)檢測方法[J].系統(tǒng)工程與電子技術(shù),2011,33(1):202-207.

[9]蔡美,劉波.基于蟻群算法的異常數(shù)據(jù)檢測方法[J].計算機(jī)工程,2016,42(8):166-169.

[10]楊群,曹祥玉,高軍,等.基于改進(jìn)的人工蜂群算法的陣列綜合研究[J].微波學(xué)報,2014,30(S1):37-40.

[14]謝娟,蘇守寶,汪繼文.近似梯度引導(dǎo)的人工蜂群搜索策略[J].計算機(jī)科學(xué)與探索,2016,10(12):1773-1782.

[15]曹春紅,許光星.基于改進(jìn)人工蜂群算法的幾何約束求解[J].計算機(jī)科學(xué)與探索,2015,9(9):1122-1131.

[16]張德富,彭煜,朱文興,等.求解三維裝箱問題的混合模擬退火算法[J].計算機(jī)學(xué)報,2009,32(11):2147-2156.

[17]寧愛平,張雪英.人工蜂群算法的收斂性分析[J].控制與決策,2013,28(10):1554-1558.

Outlier Detection Based onArtificial Bee Colony Intelligent Technology*

ZHU Huanxiong,LIU Bo+

College of Information Science and Technology,Jinan University,Guangzhou 510630,China

2017-03,Accepted 2017-06.

In order to solve the problems of high time complexity,low accuracy and low recall in detecting anomaly database attributes,this paper proposes a new method based on ABC(artificial bee colony)and the O-measure metric(i.e.,a kind of attribute outlier evaluation metric)to find out the attribute outliers,which simulates the bee colony behavior of searching for high quality food sources.In view of the local convergence of swarm intelligence algorithm to detect the attribute outliers,this paper presents the approach of finding the global optimal solution by using the simulated annealing technique,making the bee swarm jump out of the local optimal solution.The proposed algorithm calculates the O-measure of each attribute that the bees have walked,and then from the O-measure value result sets,chooses the best food sources(i.e.,the attribute outliers).In comparison with other algorithms,the experimental results show that the proposed algorithm needs less time,and improves the detection precision and recall.

attribute outlier;artificial bee colony algorithm;simulated annealing;O-measure

+Corresponding author:E-mail:ddxllb@163.com

10.3778/j.issn.1673-9418.1703042

*The National Natural Science Foundation of China under Grant No.U1431227(國家自然科學(xué)基金);the Foundation of Guangzhou Science and Technology Planning Project under Grant No.201604010037(廣州市科技計劃基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-06-22,http://kns.cnki.net/kcms/detail/11.5602.TP.20170622.1702.002.html

ZHU Huanxiong,LIU Bo.Outlier detection based on artificial bee colony intelligent technology.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1984-1992.

A

TP18

ZHU Huanxiong was born in 1991.He is an M.S.candidate at Jinan University.His research interests include artificial intelligence and data mining,etc.

朱煥雄（1991—），男，廣東梅州人，暨南大學(xué)碩士研究生，主要研究領(lǐng)域為人工智能，數(shù)據(jù)挖掘等。

LIU Bo was born in 1965.She received the M.S.degree in computer application from Central South University in 1991.Now she is a professor at Jinan University.Her research interests include data mining,swarm intelligence and information integration,etc.

劉波（1965—），女，廣東陽江人，1991年于中南大學(xué)計算機(jī)應(yīng)用專業(yè)獲得碩士學(xué)位，現(xiàn)為暨南大學(xué)教授，主要研究領(lǐng)域為數(shù)據(jù)挖掘，群體智能，信息集成等。