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

王也，張繼福，趙旭俊

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

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

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

收稿日期：2014-11-24

基金項(xiàng)目：山西省青年科學(xué)

作者簡(jiǎn)介：王也(1991-)，男，主要研究方向?yàn)閿?shù)據(jù)挖掘及應(yīng)用、并行計(jì)算。

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

(1)

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

對(duì)于數(shù)據(jù)集R中的兩個(gè)數(shù)據(jù)對(duì)象g1g2，當(dāng)g1.Ai≠All時(shí)，對(duì)于任意的屬性Ai(1≤ i ≤ n)，都有g(shù)1.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ù)關(guān)系集合cond(r，o)=avs(r)∩avs(o)表明離群數(shù)據(jù)o和參考數(shù)據(jù)r相似關(guān)系，離群數(shù)據(jù)o在一些屬性上與參考數(shù)據(jù)r有著共同的值，如果cond(r，o)，則離群數(shù)據(jù)o和參考數(shù)據(jù)r沒(méi)有共同特征。

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

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

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

設(shè)(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)的上下文有關(guān)信息，具有上下文有關(guān)信息的離群數(shù)據(jù)(r，o)稱之為上下文有關(guān)離群數(shù)據(jù)。對(duì)于數(shù)據(jù)集R中的任意兩個(gè)上下文有關(guān)離群數(shù)據(jù)(r1，o1)和(r2，o2)，如果r1>r2，o2>o2，cov(r1)=cov(r2)，cov(o1)=cov(o2)，那么deg(r1，o1)=deg(r2，o2).由此對(duì)比可以看出，(r2，o2)比(r1，o1)包含更多的屬性，(r2，o2)更適合作為上下文有關(guān)離群數(shù)據(jù)。若上下文有關(guān)離群數(shù)據(jù)(r1，o1)，不存在其他的上下文有關(guān)離群數(shù)據(jù)(r2，o2)，r2

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

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

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

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

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)表示取隨機(jī)數(shù)運(yùn)算:

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

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

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

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

Algorithm COM-PSO

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

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

步驟1：初始化群體位置、速度、適應(yīng)值、Pbest和Gbest，跳轉(zhuǎn)至步驟7；

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)分析

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

表1　ClosedCube算法所用時(shí)間

4.1可理解性

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

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

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

4.2性能分析

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[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ù)挖掘：概念與技術(shù)[M].范明，孟小峰，譯.2版.北京：機(jī)械工業(yè)出版社，2007.

[6]樓巍，曹家麟.面向大數(shù)據(jù)的高維數(shù)據(jù)挖掘技術(shù)研究[D].上海：上海大學(xué)，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ù)立方體技術(shù)研究[J].軟件學(xué)報(bào)，2004，15(6)1165-1171.

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

[10]仇晨曄，方濱興.多目標(biāo)微粒群算法研究及其在交通事故分析中的應(yīng)用[D].北京：北京郵電大學(xué)，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)化問(wèn)題的改進(jìn)微粒群算法[J].太原科技大學(xué)學(xué)報(bào)，2012，33(5)：406-409.

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

[14]譚瑛，高慧敏，曾建潮.求解整數(shù)規(guī)劃問(wèn)題的微粒群算法[J].系統(tǒng)工程理論與實(shí)踐，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