基于混合遺傳算法的高維離群數據檢測

施冬冬，方星星

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

基于混合遺傳算法的高維離群數據檢測

施冬冬1，方星星2

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

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

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

1　問題描述

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

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

2　高維空間離群數據描述

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

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

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

3.1染色體編碼

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

3.2適應度函數

Sc為稀疏系數即（2）式，適應度與稀疏系數正好相反，適應度越大，子空間中的數據越少.

3.3模擬退火算法

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

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

3.4染色體交叉

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

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

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

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

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

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

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

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

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

3.5染色體變異

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

3.6算法步驟

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

4　實驗結果及分析

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

表1

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

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

表2

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

5　總結

本文在遺傳算法的基礎上結合模擬退火算法的局部搜索能力，有效的避免了遺傳算法容易“早熟”的特點，并且，通過實驗證明新算法的有效性.但是在數據規(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

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