基于人工蜂群智能技術的屬性異常點檢測*

朱煥雄，劉 波

暨南大學 信息科學技術學院，廣州 510630

基于人工蜂群智能技術的屬性異常點檢測*

朱煥雄，劉 波+

暨南大學 信息科學技術學院，廣州 510630

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

屬性異常點；人工蜂群算法；模擬退火；O-measure

1 引言

隨著大數據時代的到來，數據質量問題成為人們日益關注的重點。數據庫中存在異常屬性值就是數據質量問題之一。異常點[1]是數據集中出現與正常的數據集中不一致的數據，往往是錯誤的數據值，會降低數據的可用性[2]，對數據分析與挖掘產生較大的影響。為此有必要對數據異常點進行檢測，其對保證數據的質量具有重要的意義。

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

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

本文在已有的屬性異常點檢測算法基礎上，擬研究新的屬性異常點的檢測方法，主要有以下貢獻：

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

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

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

2 人工蜂群算法及相關概念

2.1 人工蜂群算法

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

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

（2）引領蜂階段。隨機分配引領蜂到蜜源的各個位置進行食物源的搜索，每個引領蜂與一個食物源對應，計算引領蜂所在位置食物源的適應度，引領蜂根據式（1）在鄰域內搜索新的食物源。當引領蜂搜索到更優的食物源時，更新引領蜂的位置，否則食物源未更新次數加1。

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

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

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

（4）偵察蜂階段。當某個食物源未更新的次數達到一定的數量（limit）后，放棄該食物源，食物源所對應的引領蜂變為偵察蜂，然后偵察蜂按照式（3）全局搜索新的未被訪問過的數據空間，尋找新的并且更優的食物源。

（5）記錄本次迭代后的最優解。

（6）繼續執行步驟（2），直到蜂群算法達到收斂狀態或者是達到最大的迭代次數為止。

2.2 O-measure的相關概念

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

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

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

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

Table 1 Dataset example表1 數據集示例

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

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

2.3 模擬退火算法

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

其中，Fc表示當前食物源的適應度；Fne表示新的食物源的適應度；Temp(t)表示當前時刻的溫度值。每次迭代時溫度的更新公式如下：

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

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

3 利用人工蜂群智能屬性異常點的檢測

3.1 基本思路及IABC_Detection算法

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

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

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

IABC_Detection算法步驟如下：

（1）初始化人工蜂群算法的相關參數，如蜂群的數量為SN，引領蜂的數量為SN/2，算法迭代的次數為t，模擬退火的初始溫度等。

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

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

（4）當某個食物源未更新的次數超過limit，則該食物源對應的引領蜂變為偵察蜂，放棄該食物源，偵察蜂進行隨機搜索，全局搜索較優的食物源并且評估它們的適應度。

（5）記錄本次迭代的最優解，模擬退火算法的溫度發生變化。

（6）回到步驟（2），重復執行直到算法收斂或者是算法達到終止條件。

（7）輸出屬性異常點。

IABC_Detection算法實現的具體說明如下：

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

在步驟（2），算法隨機分配引領蜂到二維數據平面上，每個引領蜂的位置可以表示為Lij，Lij也表示元組ti中屬性Aj的屬性值。對每個引領蜂所在的食物源計算適應度（即O-measure），然后在該引領蜂附近按照式（1）搜索更優的食物源，并且計算該食物源的適應度。引領蜂按照模擬退火機制選擇適應度較好的食物源存入異常結果表，異常結果表S的結構定義為四元組(T,A,V,M)。其中T是元組的ID，A是目標屬性的名稱，V是該目標屬性A所對應的值，M是目標屬性A所對應的O-measure值。在異常結果表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）搜索新食物源，并且計算新食物源的適應度，采用模擬退火機制選擇較優的食物源，并且將較優的食物源及其相應的適應度存儲到異常結果表S中。

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

在步驟（5）中，記錄每次迭代的最優解，模擬退火算法的溫度根據式（6）進行相應的變化。

3.2 算法執行的時間復雜度分析

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

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

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

3.3 IABC_Detection算法檢測屬性異常點的效果分析

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

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

隨著數據集的元組數或屬性個數增大，當給定蜂群數量一定時，雖然偵查蜂能進行全局搜索，但蜂群在尋找最優食物源的時候仍然可能會出現搜索不到目標解的情形，算法的查全率會受到一定的影響。IABC_Detection算法采用模擬退火機制，能有效地跳出局部最優解，擴大解的搜索范圍，從中尋找更多全局較優解。

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

蜂群在尋找最優食物源時，都是從一個位置移動到新的位置，因此人工蜂群算法的狀態轉移可以表示為：

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

否則P(X,Y)=0。

因為人工蜂群算法結合模擬退火算法之后，都將會選擇較優的食物源作為解，所以當給定初始的引領蜂的解，并且蜂群內部進行無數次的迭代后，人工蜂群算法的Markov鏈種群系列能以概率1收斂于全局屬性異常點集合M，如式（9）所示：

4 模擬實驗

4.1 實驗環境

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

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

4.2 實驗結果及分析

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

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

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

Fig.4 Comparison of precision ratio圖4 算法的查準率對比圖

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

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

下面給出IABC_Detection算法中參數值對結果的影響：

（1）O-measure閾值的設定。設定閾值α對異常結果集表S進行裁剪，即當屬性的O-measure值大于閾值α時，對結果集表S中相應的數據進行刪除。經過反復實驗發現，當α=0.010時，算法具有較好的查準率，不會影響找到的異常屬性點。

（2）迭代次數t對算法收斂性的影響。初始時，蜂群隨機選擇食物源，算法的查全率不高，但是隨著算法迭代次數增加，當迭代次數增加到2 000次左右時，算法能找到的屬性異常點數量將不再有大的變化，算法趨于收斂狀態，查全率也趨于穩定。迭代次數對算法收斂性的影響實驗結果如圖5所示。

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

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

Fig.6 Recall ratio to different number of employed bees圖6 引領蜂的個數對查全率的影響

（4）參數limit的設置。當尋找到食物源的適應度經過limit次未發生改變時，該食物源將被丟棄，并且該食物源對應的引領蜂變為偵察蜂，偵察蜂重新在全局搜索空間搜索新的食物源。參數limit如果設置得太大，容易陷入局部最優，但limit設置得太小，算法很難收斂。經實驗發現，limit設置在20～30時算法的效果較佳。

4.3 F-score值的比較

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

Table 3 F-score values of related algorithms表3 相關算法的F-score值比較表 %

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

5 結束語

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

[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.

附中文參考文獻：

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

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

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

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

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

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

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

[16]張德富,彭煜,朱文興,等.求解三維裝箱問題的混合模擬退火算法[J].計算機學報,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(國家自然科學基金);the Foundation of Guangzhou Science and Technology Planning Project under Grant No.201604010037(廣州市科技計劃基金).

CNKI網絡優先出版: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—），男，廣東梅州人，暨南大學碩士研究生，主要研究領域為人工智能，數據挖掘等。

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年于中南大學計算機應用專業獲得碩士學位，現為暨南大學教授，主要研究領域為數據挖掘，群體智能，信息集成等。