基于微粒群算法的上下文離群數(shù)據(jù)挖掘算法

王也，張繼福，趙旭俊

(太原科技大學計算機科學與技術學院，太原 030024)

摘要：現(xiàn)有的離群檢測方法大多都忽視離群數(shù)據(jù)的上下文信息，使得離群數(shù)據(jù)難以理解。從離群數(shù)據(jù)的可解釋性角度，采用微粒群算法(PSO)，給出了一種上下文有關的離群數(shù)據(jù)挖掘算法(COM-PSO)。該算法將數(shù)據(jù)屬性作為上文有關信息，且將離群數(shù)據(jù)看作微粒；根據(jù)數(shù)據(jù)對象相對全局數(shù)據(jù)的頻數(shù)，采用帶有變異算子的PSO算法來搜索離群數(shù)據(jù)；最后UCI數(shù)據(jù)，實驗結果驗證了該算法的有效性，并具有效率高、可解釋性強等特點。

關鍵詞：離群數(shù)據(jù)；上下文有關；微粒群；可解釋性；頻數(shù)

收稿日期：2014-11-24

基金項目：山西省青年科學

作者簡介：王也(1991-)，男，主要研究方向為數(shù)據(jù)挖掘及應用、并行計算。

中圖分類號：TP311文獻標志碼：A

離群數(shù)據(jù)(outlier)是顯著不同于其它數(shù)據(jù)，不滿足數(shù)據(jù)的一般行為或模式，與存在的其它數(shù)據(jù)不一致[1]。離群數(shù)據(jù)挖掘有著廣闊的應用前景，如醫(yī)療處理，傳感器/視頻網絡監(jiān)視和入侵等。

目前，離群數(shù)據(jù)挖掘方法主要有：(1)基于統(tǒng)計學的方法[2]，其核心思想是對數(shù)據(jù)的正常性做出假設，假設數(shù)據(jù)集服從某種分布或概率模型，通過不一致檢驗把那些嚴重偏離分布曲線的數(shù)據(jù)對象視為離群數(shù)據(jù)，但問題是：許多情況下，用戶不了解數(shù)據(jù)集的分布，實際數(shù)據(jù)集往往并不符合理想數(shù)學分布。(2)基于距離的方法，該方法的基本思想是對給定的數(shù)據(jù)集，使用距離來量化數(shù)據(jù)對象之間的相似性。遠離其他數(shù)據(jù)對象的數(shù)據(jù)將被視為離群數(shù)據(jù)。該方法的缺陷是：由于數(shù)據(jù)集不同，往往不容易設定距離閾值Dmin.(3)基于密度的方法[3-4]，其核心思想是把數(shù)據(jù)對象周圍的密度與其鄰域周圍的密度進行比較，將密度顯著不同于其鄰域周圍的密度的數(shù)據(jù)對象定義為離群數(shù)據(jù)。該方法的問題在于其計算量非常大。

盡管大量的離群數(shù)據(jù)挖掘方法已經被提出[5-6]，但是對于離群數(shù)據(jù)產生的原因進行分析和解釋的工作相對較少。離群數(shù)據(jù)挖掘算法只是離群數(shù)據(jù)挖掘的第一步，更重要也是更具有挑戰(zhàn)性的是要對離群數(shù)據(jù)產生的來源、含義及特征進行分析。Guanting Tang，Jian Pei等人在2013年SSDBM會議上提出了一個帶有上下文信息的離群數(shù)據(jù)模型[7]，并給出一種上下文有關的離群數(shù)據(jù)挖掘算法，但由于該算法先采用剪枝的方法縮小范圍，再采用枚舉的方法搜索離群數(shù)據(jù)，其挖掘效率低，且該模型缺少離群數(shù)據(jù)與正常數(shù)據(jù)的相似性。本文利用微粒群算法(Particle SwarmOptimization，PSO)具有簡單容易實現(xiàn)，且沒有許多參數(shù)需要調整等優(yōu)勢，采用帶有變異算子的微粒群算法[8-10]來搜索上下文有關離群數(shù)據(jù)，不僅保存了上下文有關的信息，即：離群數(shù)據(jù)的可解釋性信息，同時也提高了離群數(shù)據(jù)挖掘的效率。

1離群數(shù)據(jù)與上下文信息

設數(shù)據(jù)集R中有M個數(shù)據(jù)對象，數(shù)據(jù)屬性的維數(shù)為N，數(shù)據(jù)對象為g(A1，A2，…，An)，其中Ai作為維屬性，A1，A2，…，An是數(shù)據(jù)對象g的屬性值，表示為g.Ai，若屬性值為空，則表示為all.參照文獻[7]，相關概念描述如下：

(1)

在公式(1)中，deg(r，o)衡量了數(shù)據(jù)對象o的離群程度，deg(r，o)越大，數(shù)據(jù)對象o相對r的離群程度也就越大。

對于數(shù)據(jù)集R中的兩個數(shù)據(jù)對象g1g2，當g1.Ai≠All時，對于任意的屬性Ai(1≤ i ≤ n)，都有g1.Ai=g2.Ai，則稱g1是g2的祖先，g2是g1的后代。表示為g1

離群數(shù)據(jù)的上下文信息包含：(1)離群數(shù)據(jù)的參考數(shù)據(jù)(r，o)；(2)離群屬性out(r，o)；(3)離群數(shù)據(jù)數(shù)目；(4)離群程度deg(r，o).參考數(shù)據(jù)r表明離群數(shù)據(jù)o相比于哪些正常數(shù)據(jù)是離群的。離群屬性out(r，o)=space(r)-space(cond(r，o))表明相比參考數(shù)據(jù)，離群數(shù)據(jù)在哪些屬性上離群。共同屬性值集也稱離群數(shù)據(jù)與參考數(shù)據(jù)關系集合cond(r，o)=avs(r)∩avs(o)表明離群數(shù)據(jù)o和參考數(shù)據(jù)r相似關系，離群數(shù)據(jù)o在一些屬性上與參考數(shù)據(jù)r有著共同的值，如果cond(r，o)，則離群數(shù)據(jù)o和參考數(shù)據(jù)r沒有共同特征。

2利用微粒群算法搜索上下文有關離群數(shù)據(jù)

2.1上下文有關離群數(shù)據(jù)

上下文信息是離群數(shù)據(jù)的組成部分之一，能夠對離群數(shù)據(jù)的含義做出很好的解釋，例如：“在X學校計算機專業(yè)學生中，未參加數(shù)據(jù)結構課程的3名學生相對于參加數(shù)據(jù)結構課程的128名學生就是離群數(shù)據(jù)?！?，在該離群數(shù)據(jù)中，上下文信息包括：1)參考數(shù)據(jù)：參加數(shù)據(jù)結構課程的128名計算機專業(yè)學生；2)離群屬性：未參加數(shù)據(jù)結構課程；3)離群數(shù)據(jù)數(shù)目：3；4)離群數(shù)據(jù)與參考數(shù)據(jù)的關系：均為計算機專業(yè)的學生；5)離群程度：128/3.由此可以看出，上下文信息很好的解釋了該離群數(shù)據(jù)：相對于參加數(shù)據(jù)結構的128名計算機專業(yè)學生(參考數(shù)據(jù))，未參加數(shù)據(jù)結構課程的3名計算機專業(yè)學生(離群數(shù)據(jù))在未參加數(shù)據(jù)結構課程的屬性(離群屬性)上，出現(xiàn)了異常，同時，他們都是計算機專業(yè)的學生(離群數(shù)據(jù)與參考數(shù)據(jù)的關系)。由此可見，離群數(shù)據(jù)的上下文有關信息，有效地解釋了離群數(shù)據(jù)，對于離群數(shù)據(jù)的理解具有較大幫助。

設(r，o)為離群數(shù)據(jù)，其參考數(shù)據(jù)為r，離群屬性為out(r，o)，共同屬性值集為cond(r，o)，離群程度系數(shù)為deg(r，o)，則稱r、deg(r，o)、out(r，o)和cond(r，o)為(r，o)的上下文有關信息，具有上下文有關信息的離群數(shù)據(jù)(r，o)稱之為上下文有關離群數(shù)據(jù)。對于數(shù)據(jù)集R中的任意兩個上下文有關離群數(shù)據(jù)(r1，o1)和(r2，o2)，如果r1>r2，o2>o2，cov(r1)=cov(r2)，cov(o1)=cov(o2)，那么deg(r1，o1)=deg(r2，o2).由此對比可以看出，(r2，o2)比(r1，o1)包含更多的屬性，(r2，o2)更適合作為上下文有關離群數(shù)據(jù)。若上下文有關離群數(shù)據(jù)(r1，o1)，不存在其他的上下文有關離群數(shù)據(jù)(r2，o2)，r2

2.2利用微粒群算法搜索上下文有關離群數(shù)據(jù)

微粒群算法(Particle Swarm Optimization，PSO)是Kennedy和Eberhart受到鳥類群體行為的啟發(fā)而提出的。該算法采用“群體”探索問題的空間[9，13]，每個粒子按照一定的自適應速度在空間隨機搜索，同時，每一粒子記憶自己所在空間的最優(yōu)解，并以一定的加速度向自己所經歷最好位置和群體中所有個體所經歷的最好位置飛行。由于PSO算法具有實現(xiàn)容易、精度高，局部和全局搜索能力強等優(yōu)點，從而對解決復雜環(huán)境中的優(yōu)化問題非常有效[10-11]。

搜索上下文有關離群數(shù)據(jù)是根據(jù)參考數(shù)據(jù)與離群數(shù)據(jù)在數(shù)據(jù)集中出現(xiàn)頻數(shù)之比為基礎，通過計算參考數(shù)據(jù)(cov(r))與離群數(shù)據(jù)(cov(o))的頻數(shù)之比，根據(jù)與給定的離群程度系數(shù)閾值△的關系來判斷是否是離群數(shù)據(jù)。根據(jù)這一模型，將數(shù)據(jù)集中的任意兩條數(shù)據(jù)看作為數(shù)據(jù)空間中的微粒i(r，o).兩條數(shù)據(jù)對象分別定義為參考數(shù)據(jù)和離群數(shù)據(jù)，同時他們的屬性值和標識符代表微粒的位置。數(shù)據(jù)對象每一次迭代的變化定義為微粒位置變化的速度。因此，微粒的位置可描述為：Xi(r，o)=(r，(Xr1，Xr2，…，Xrn)o，(Xo1，Xo2，…，Xon))，其中r，o為數(shù)據(jù)對象的標識符，Xr1，Xr2，…，Xrn，Xo1，Xo2，…，Xon為微粒i(r，o)中數(shù)據(jù)對象r，o屬性值。由于微粒的位置由標識符r，o來確定，微粒位置的變化也就意味著標識符r，o的變化，因此微粒位置變化的速度，定義為：Vi(r，o)=(r，(Vr1，Vr2，…，Vrn)o，(Vo1，Vo2，…，Von))，VirVio分別對應為數(shù)據(jù)對象r，o的速度。由于把離群程度系數(shù)deg(r，o)大于閾值△的數(shù)據(jù)對象作為搜索結果，因此，把離群程度公式(1)定義為目標適應值函數(shù)。

根據(jù)數(shù)據(jù)對象的標識符r，o及其屬性值是用整數(shù)表示的，則可采用整數(shù)規(guī)劃問題的微粒群算法[14]。位置和速度的數(shù)值運算與整數(shù)的運算相同，相應計算公式如下：

vin(t+1)=wvin(t)+c1r1[pij(t)-xin(t)]+

c2r2[pgn(t)-xin(t)]

(2)

xin(t+1)=xin(t)+vin(t+1)

(3)

其中：rand(i)表示取隨機數(shù)運算:

其中pi(r，o)表示微粒i(r，o)所經歷過的離群程度最大數(shù)據(jù)對象，pg(r，o)表示所有微粒中離群程度最大數(shù)據(jù)對象。

3基于PSO的上下文有關離群數(shù)據(jù)挖掘算法

由于每一個封閉的上下文有關離群數(shù)據(jù)中的參考數(shù)據(jù)和離群數(shù)據(jù)必須是封閉的，所以，對于給定的數(shù)據(jù)集R，采用ClosedCube算法找出所有的封閉數(shù)據(jù)[8]。

根據(jù)以上所述，基于微粒群算法的上下文有關離群數(shù)據(jù)挖掘算法(Contextual Outlier Mining-Particle Swarm Optimization，COM-PSO)步驟如下：

Algorithm COM-PSO

輸入：數(shù)據(jù)集R，離群程度閾值Δ

輸出：上下文有關離群數(shù)據(jù)

步驟1：初始化群體位置、速度、適應值、Pbest和Gbest，跳轉至步驟7；

步驟2：按公式(2)(3)計算位置和速度；

步驟3：生成隨機數(shù)r3，若r3

步驟4：根據(jù)公式(1)計算適應值；

步驟5：若存在某個微粒的適應值優(yōu)于該微粒經歷的最好位置Pbest，則用該微粒位置替換Pbest，反之Pbest保持不變；

步驟6：若存在某個微粒的適應值優(yōu)于全局最好位置Gbest，則用該微粒位置替換Gbest，反之Gbest保持不變；

步驟7：若全局最優(yōu)Gbest大于離群程度閾值Δ，則輸出Gbest離群數(shù)據(jù)及離群程度系數(shù)deg(r，o)，并重新初始化。

步驟8：若小于預定進化次數(shù)，則返回步驟2.

將輸出的Gbest中的兩條數(shù)據(jù)，作為參考數(shù)據(jù)和離群數(shù)據(jù)。Gbest的值作為離群程度系數(shù)。由此，可以更好的分析的上下文有關離群數(shù)據(jù)。

4實驗分析

在Intel CoreTMi7-820M CPU，8G內存，Windows 8.1操作系統(tǒng)，用Microsoft Visual Studio 2013實現(xiàn)了COM-PSO和COD算法。采用UCI數(shù)據(jù)庫中Solar-flare和Hayes-roth數(shù)據(jù)集，作為實驗數(shù)據(jù)集。表1為尋找封閉數(shù)據(jù)時的一些統(tǒng)計數(shù)據(jù)。

表1　ClosedCube算法所用時間

4.1可理解性

在Hayes-roth數(shù)據(jù)集中，含有160條數(shù)據(jù)，每一條數(shù)據(jù)代表一個人的若干信息，包含5維屬性。分別為姓名，愛好，年齡，教育水平，婚姻狀況。首先，由于姓名和愛好是隨機產生，在分析中我們將其忽略，姓名處理為標識符，愛好用All代替。年齡將其處理為{30，40，50}，教育水平取值處理為{初中，高中，大專，本科}，婚姻狀況取值處理為{單身，已婚，離異，喪偶}。在離群程度閾值Δ=5的情況下，COM-PSO算法挖掘結果如表2所示，其中：“*”代表All.

表2　上下文有關離群數(shù)據(jù)

從表2中我們可以看到，上下文離群數(shù)據(jù)o1=(*，*，高中，離異)包含以下上下文信息：參考數(shù)據(jù)r1{*，*，高中，單身}，離群屬性out(r1，o1)={婚姻狀況}，離群數(shù)據(jù)與參考數(shù)據(jù)關系集cond(r1，o1)={高中}，離群數(shù)目6和離群程度deg(r1，o1)=5.7.根據(jù)上下文信息，可以很好的理解離群數(shù)據(jù)o1：在教育水平為高中的群體中，6個婚姻狀況為離異的人相比34個婚姻狀況為單身的人是離群的，離群程度為5.7.同理，上下文有關離群數(shù)據(jù)o5也可以解釋為：在30歲的群體中，4個喪偶的人相對于34個已婚的人是離群的，離群程度為8.5.

4.2性能分析

在Solar-flare數(shù)據(jù)集中，含有7 770條數(shù)據(jù)，每條數(shù)據(jù)表示在拍攝的功能有源區(qū)，包含13維屬性。分別為光斑種類，最大光斑尺寸，光斑分布，光斑狀態(tài)，光斑是否演化，24 h內光斑活躍狀態(tài)，歷史狀態(tài)，歷史上是否是復雜，區(qū)域，最大光斑區(qū)域，C級耀斑產量數(shù)，M級耀斑產量數(shù)，X級耀斑產量數(shù)。

設群體規(guī)模N=80，參數(shù)c1=c2=0.5，w=0.8，變異概率mp=0.4，將預設進化代數(shù)作為算法終止條件，實驗結果如下所示。

由圖1可以看出，COM-PSO算法隨著迭代次數(shù)的增加，其挖掘精度也在增加，特別是當?shù)螖?shù)超過7200代時，COM-PSO算法的精度達96%以上，其原因是COM-PSO 算法開始時，在給定一個非常大的Vmax(速度極大值)條件下，則能到達數(shù)據(jù)集中任何地點，但不能在一次迭代之內找到離群程度最高的數(shù)據(jù)對象；在迭代次數(shù)足夠的情況下，則可能達到任何數(shù)據(jù)對象的位置，而且一旦搜索到大于離群程度系數(shù)閾值的離群數(shù)據(jù)，便重新初始化種群位置，避免了種群凝聚。圖2表明，隨著數(shù)據(jù)集的增大，在迭代次數(shù)一定時，COM-PSO算法的精度下降，其主要原因是隨著數(shù)據(jù)規(guī)模變大，所包含的離群數(shù)據(jù)個數(shù)可能增加，同時由于迭代次數(shù)不變，所搜索到離群數(shù)據(jù)數(shù)目大致相同，因此可能導致挖掘精度降低。

圖1　不同迭代次數(shù)的精度

圖2　不同數(shù)據(jù)集的精度(△=10，次數(shù)=5 600 )

由圖3、4可知，隨著數(shù)據(jù)集和迭代次數(shù)的增長，COM-PSO算法挖掘耗時也在增加，其主要原因是數(shù)據(jù)集增長導致每次迭代計算數(shù)據(jù)對象頻數(shù)的時間增多，從而總體時間增大，而迭代次數(shù)的增多也就意味著計算數(shù)據(jù)對象頻數(shù)的次數(shù)增多，耗時也增大。

圖3　不同迭代次數(shù)的效率

圖4　不同數(shù)據(jù)集的效率(△=10,次數(shù)=5 600)

由圖5可看出，當數(shù)據(jù)集M和迭代次數(shù)不變時，離群程度閾值Δ對COM-PSO算法的挖掘效率影響較小，其主要原因是由于離群程度系數(shù)閾值在COM-PSO算法中，僅僅作為是否為離群數(shù)據(jù)的判斷條件，而離群程度系數(shù)閾值在COD算法中，不僅作為離群數(shù)據(jù)的判斷條件，而且還在剪枝步驟中，作為剪枝判斷條件的一部分，從而導致COD算法效率受離群程度系數(shù)閾值影響較大。在離群程度閾值較小(Δ<25)時，COM-PSO算法的挖掘效率比COD算法效率高，其主要原因是COM-PSO算法在搜索迭代過程中，由于Vmax，每一次的迭代都是合理的，而在COD算法中，當離群程度系數(shù)閾值較小時，剪枝效率低，從而使得挖掘效率較低。

圖5　不同程度系數(shù)的效率 ，次數(shù)=5 600)

5結束語

大多數(shù)傳統(tǒng)的離群挖掘算法缺少對離群數(shù)據(jù)的解釋，使得離群數(shù)據(jù)難以理解。將數(shù)據(jù)屬性作為上文有關信息，并采用微粒群算法(PSO)，給出了一種上下文有關的離群數(shù)據(jù)挖掘算法，從而有效地提高離群數(shù)據(jù)的可解釋性。

參考文獻：

[1]KNNOR E，NG R.Algorithms for mining distance-based outliers in large datasets[C]∥Proc Of the 24thVLDB Conference.New York，USA：Morgan Kaufmann，1998：392-403.

[2]BARNETT V，LEWIS T.Outliers in statistical data[M].New York，USA：John Wiley &Sons，1994.

[3]SARAWAGI S，AGRNWAL K，MEGIDDO N.Discovery-driven exploration of olap data cubes[C]∥Valencia：Proc of IntConf Extending Database Technology (EDBT’98).LNCS 1377，Springer-Verlag，1998：168-182.

[4]BREUNIG M，KRIEGEL H P，NG R，et al.LOF：Identifying density-based local outlier[C]∥Zytkow J M Rauch.Proc of the 3rd European Conference on Principles and Practice of knowledge Discovery in Databases.LNCS 1704，Prague，Czech：Springer，1999：262-270.

[5]HAN J W，KAMBER M.數(shù)據(jù)挖掘：概念與技術[M].范明，孟小峰，譯.2版.北京：機械工業(yè)出版社，2007.

[6]樓巍，曹家麟.面向大數(shù)據(jù)的高維數(shù)據(jù)挖掘技術研究[D].上海：上海大學，2013.9.

[7]GUANTING TANG，JIAN PEI.Mining multidimensional contextual outliers from categorical relational data[C]∥Scientific and Statistical Database Management’13，July 29 - 31 2013，Baltimore，MD，USA.

[8]李盛恩，王珊.封閉數(shù)據(jù)立方體技術研究[J].軟件學報，2004，15(6)1165-1171.

[9]葛凌云，張繼福，蔡江輝.基于微粒群算法和子空間的離群數(shù)據(jù)挖掘算法研究[J].系統(tǒng)仿真學報，2009，21(7)：1897-1903.

[10]仇晨曄，方濱興.多目標微粒群算法研究及其在交通事故分析中的應用[D].北京：北京郵電大學，2013.

[11]J KENNEDY，R EBERHART.Particle swarm optimization[C]∥Proceedingsof IEEE International Conference on Neural networks，NJ，WAAustralia.USA：IEEE Service Center，1995，IV：1942-1948.

[12]屈向紅，郭靖，夏桂梅，等.求解約束優(yōu)化問題的改進微粒群算法[J].太原科技大學學報，2012，33(5)：406-409.

[13]孫超利，譚英，潘正祥，等.一種求解約束優(yōu)化問題的微粒群算法[J].2010，31(6)，453-457.

[14]譚瑛，高慧敏，曾建潮.求解整數(shù)規(guī)劃問題的微粒群算法[J].系統(tǒng)工程理論與實踐，2004，24(5)：126-129.

Contextual Outlier Mining Algorithm Based on Particle Swarm Optimization

WANG Ye，ZHANG Ji-fu，ZHAO Xu-jun

(School of Computer Science and Technology，Taiyuan University of Science and Technology，

Taiyuan 030024，China)

Abstract：Most methods of outlier mining focus on outlier data objects and give little or no attention to contextual information.To enhance the interpretability of outliers，a contextual outlier mining algorithm (COM-PSO)was proposed by using particle swarm optimization.The attributes of data were considered as contextual information of outliers，and outliers were considered as particle swarm.Contextual outliers were searched with mutational PSO algorithm according to the frequency of data object relative to global data set.At last，the experiment results verified the effectiveness of the algorithm by using UCI machine learning repository.

Key words：outliers，context，particle swarm optimization，interpretability，frequency