施冬冬，方星星

（1.安徽大學(xué)江淮學(xué)院，安徽　合肥　230039；2.解放軍陸軍軍官學(xué)院，安徽　合肥　230000）

基于混合遺傳算法的高維離群數(shù)據(jù)檢測

施冬冬1，方星星2

（1.安徽大學(xué)江淮學(xué)院，安徽合肥230039；2.解放軍陸軍軍官學(xué)院，安徽合肥230000）

離群點研究在實際應(yīng)用中有著重要的意義，隨著數(shù)據(jù)規(guī)模的不斷擴大，傳統(tǒng)的離群點檢測方法已經(jīng)不適用于高維空間數(shù)據(jù)，本文在遺傳算法的基礎(chǔ)上結(jié)合模擬退火算法，一方面利用遺傳算法對高維數(shù)據(jù)處理有很好的全局搜索能力，一方面利用模擬退火算法的局部搜索能力，最后經(jīng)實驗證明，本文提出的新算法能有效的提高高維空間離群點檢測的效率.

離群點；遺傳算法；模擬退火算法

1　問題描述

離群點檢測是數(shù)據(jù)挖掘的重要內(nèi)容之一.目前離群數(shù)據(jù)檢測的研究十分活躍，已經(jīng)有許多離群數(shù)據(jù)挖掘算法，其主要方法可歸為五類，即基于聚類的方法：通過聚類發(fā)現(xiàn)常規(guī)模式，不屬于任何一個類的數(shù)據(jù)即是離群點；基于統(tǒng)計的方法：離群點是那些偏離正常分布（如正態(tài)分布、Poisson分布等）的數(shù)據(jù)，這類方法需要數(shù)據(jù)服從一定的分布［1］；基于深度的方法：計算d維凸球的不同層，那些位于球最外層的數(shù)據(jù)為離群點，這種方法在大型高維數(shù)據(jù)中的應(yīng)用較為困難；基于距離的方法：給定數(shù)據(jù)集X及距離dmin，對于點p∈X，若至少存在X中的m個數(shù)據(jù)點到點p的距離大于dmin，則稱p為離群點；基于密度的方法：如果一個數(shù)據(jù)點的局部離群因子高于一個閥值則被認為是一個離群點，它用于發(fā)現(xiàn)局部離群點［2］.

目前，低維離群數(shù)據(jù)的檢測算法已較成熟，受“維度災(zāi)”（the curse of dimensionality）的影響，許多傳統(tǒng)的檢測算法運用到高維數(shù)據(jù)上往往失效，但是在實際生產(chǎn)應(yīng)用中，高維數(shù)據(jù)普遍存在，例如，基因表達數(shù)據(jù)、金融數(shù)據(jù)、多媒體數(shù)據(jù)以及文本數(shù)據(jù)等［3］.因此對高維數(shù)據(jù)離群點檢測算法的研究具有非常重要的意義.遺傳算法對高維空間的數(shù)據(jù)處理有很好的全局搜索能力，但是缺點是顯而易見的，局部尋優(yōu)能力差，容易產(chǎn)生“早熟”現(xiàn)象（局部收斂）［4］.模擬退火算法有很強的局部搜索能力，本文在遺傳算法基礎(chǔ)上結(jié)合了模擬退火算法，能使搜索過程避免陷入局部收斂.

2　高維空間離群數(shù)據(jù)描述

我們把一組高維空間數(shù)據(jù)用規(guī)模為n的橫向量集合A表示，每個向量維數(shù)是k，表示成A=｛a1，a2……an｝，其中ai=｛ai1，ai2……ait｝，k維數(shù)據(jù)的每個屬性劃分為f=1/φi等份，φ為第i維被劃分的間隔個數(shù)，設(shè)maxi和mini分別表示數(shù)據(jù)集n在第i維上的最大值和最小值，那么劃分的每個間隔的長度即為：對于一個s維的網(wǎng)格，s＜k，即k維數(shù)據(jù)投影到s個不同的維上.假設(shè)各個分量的取值是獨立的，那么一個點在s維的網(wǎng)格中是否出現(xiàn)可以用Bemoulli隨即變量來描述，約為fS.n為數(shù)據(jù)的總數(shù)，在s維的空間中，期望值為n·fS，標(biāo)準方差為，設(shè)s維網(wǎng)格H中數(shù)據(jù)的實際個數(shù)為n'，那么H的稀疏系數(shù)

如果Sc取負值，即認為H中的數(shù)據(jù)點個數(shù)明顯少于期望值.實際上，大多數(shù)時候數(shù)據(jù)分量的取值并不是統(tǒng)計獨立的，也并不總呈均勻分布.然而，稀疏系數(shù)仍然可以正確衡量空間中數(shù)據(jù)的稀疏程度.我們的目標(biāo)是尋找具有最小稀疏系數(shù)的s維子空間.

3　遺傳算法（GA）及其改進

3.1染色體編碼

染色體的長度為數(shù)據(jù)集的維數(shù).對于一個n維數(shù)據(jù)集，第k（k≤n）個屬性的取值可能為1～φ或者“*”，“*”表示對該屬性的取值不關(guān)心.例如對一個四維數(shù)據(jù)集的二維子空間它的一個可能的二維子空間模式為“*3*9”，這個模式中，第二維和第四維的取值是確定的，而第一維和第三維的取值是不關(guān)心的.

3.2適應(yīng)度函數(shù)

Sc為稀疏系數(shù)即（2）式，適應(yīng)度與稀疏系數(shù)正好相反，適應(yīng)度越大，子空間中的數(shù)據(jù)越少.

3.3模擬退火算法

傳統(tǒng)的遺傳算法在進行選擇、交叉和變異的過程中一般采用輪盤賭的方式，選擇、保留上代最優(yōu)染色體替換下一代最差染色體的方式，但是選擇個體概率和個體適應(yīng)度成正比，導(dǎo)致前期有的個體充斥整個種群，而后期個體之前沒什么差異，會出現(xiàn)“早熟”現(xiàn)象.在這里我們利用模擬退火算法的思想，對個體適應(yīng)度隨時間改變進行進化.公式如下：

這里e為遺傳算法中的世代數(shù)，M為種群數(shù)，φ為改變前的適應(yīng)度，φ'為改變后的適應(yīng)度，T0為設(shè)置好的初始溫度，我們把他設(shè)置為200，N是一個無限接近1的一個小數(shù)可以根據(jù)實際來改變（這里我們設(shè)為0.9999）.這樣我們在每次使用輪盤賭選擇時，可以隨機選擇由公式3得到的適應(yīng)度，從而保證前期適應(yīng)度打的個體會縮小差距，并且避免后期出現(xiàn)個體之前適應(yīng)度差距很小，可以適當(dāng)?shù)姆糯筮m應(yīng)度，確保了改進后的適應(yīng)度能自適應(yīng)的進行伸縮，有效的緩解了之前我們提到的遺傳算法“早熟”現(xiàn)象.

3.4染色體交叉

常用的交叉方法為兩點交叉，即任選一點作為交叉點并交換這點右邊的部分.但是這種兩點交叉有時會產(chǎn)生不合理的結(jié)果.我們對交叉方法作了一定的修改，來保證父串和子串都對應(yīng)相同給定維數(shù)的子空間模式.令k為指定的子空間維數(shù)，對于一對模式階為k的字符串st1和st2，指定串中的一個位置，有以下3種類型：

（1）在此位置上，兩個串都是*

（2）在此位置上，兩個串都不是*

（3）在此位置上，兩個串中只有一個是*

設(shè)st為st1和st2交叉生成的一個子串，很明顯在第一類位置上，子串st也是*.假設(shè)st1和st2含k'個第2類位置，則st1和st2均含有k-k'個第3類位置，兩者總共包含2（k-k'）個第3類位置.字符串st1和st2交叉過程描述如下：

①設(shè)R為第二類位置的集合（k'個），Q為第三類位置的集合，s為一子串.

②枚舉第二類位置的所有可能重組方式（2k'種），選擇稀疏系數(shù)最小的一種組合方式設(shè)置在s的對應(yīng)位置上.

③反復(fù)選取Q中第三類位置對應(yīng)的父串值并設(shè)置在s的相應(yīng)位置上，使得s有最小的稀疏系數(shù)，直到s的k個位置都設(shè)置完畢.s的其它位置設(shè)為*.

④令s'為s的補串，s'的每一位置的取值相對于s來自不同的父串，將s'作為s1和s2交叉后的另一個子串.很顯然，重組后的交叉過程能夠保證子串s和s'與父串有相同的維（階）數(shù).

3.5染色體變異

變異的目的是改善遺傳的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象.這里使用如下變異方法：首先在得到的兩個新個體和上，以概率Pm隨機選擇在st1和st2上的某一維非*屬性qi，i∈［1，k］，然后交換染色體st1和st2在qi屬性上的編碼.

3.6算法步驟

本文的算法步驟的具體流程為：

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

本文在VC6.0開發(fā)環(huán)境下進行驗證，實驗采用UCI機器學(xué)習(xí)倉庫的數(shù)據(jù)集（Breastcancer）.PC機的配置：AMD Athlon（tm）II X2 245，DDR2 2G內(nèi)存.數(shù)據(jù)集包含100000個樣本數(shù)據(jù)，其中150個離群點，交叉概率設(shè)為69%，變異概率為0.1%，初始溫度T0定為200，溫度冷卻系數(shù)α=0.99.我們選取不同規(guī)模的樣本數(shù)據(jù)采用本算法進行比較，如表1所示.

表1

可以發(fā)現(xiàn)隨著數(shù)據(jù)規(guī)模的擴大，正確離群點檢測的概率越高.

為體現(xiàn)出本算法的優(yōu)越性，先將該算法與一般遺傳算法的檢索結(jié)果進行對比，如表2所示：

表2

從表2看出，在相同的情況下，GA'檢測率最高，表明該改進算法具有優(yōu)于一般遺傳算法的性能；GA'平均收斂世代數(shù)明顯大于前者，也說明混合了模擬退火伸縮適應(yīng)度的遺傳算法的確可以有效地緩解“早熟”、過早收斂的現(xiàn)象.

5　總結(jié)

本文在遺傳算法的基礎(chǔ)上結(jié)合模擬退火算法的局部搜索能力，有效的避免了遺傳算法容易“早熟”的特點，并且，通過實驗證明新算法的有效性.但是在數(shù)據(jù)規(guī)模較小的情況小，該算法對離群點檢測的效率還有待提高，這也是以后對該算法進一步改進的地方.

〔1〕Aggarwal C，Yu P.An effective and efficient algorithm for highdimensional outlier detection［J］.The VLDB Journal，2005，14（2）：211-221.

〔2〕Charu C.Aggarwal，Philip S.Yu.Outlier Detection for High Dimensional Data ACM2001.

〔3〕AgrawalR，Gehrke J，Gunopulos D，et a1．Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications［A］．Haas L M，Tiwary A．Proc．ofthe ACM SIGMOD InternationalConferenceonManagement of Data［C］．Seattle：ACM Press，1998．94．105．

〔4〕范明，孟曉峰.Jia Wei HAN and KAMBER M.Data mining concepts and techniques［M］.北京：機械工業(yè)出版社，2007.

O212；TP311.13

A

1673-260X（2016）10-0001-02

2016-06-16

安徽省省級自然科學(xué)研究一般項目（無編號）