基于遺傳算法的高維離群點(diǎn)檢測(cè)算法的改進(jìn).doc

基于遺傳算法的高維離群點(diǎn)檢測(cè)算法的改進(jìn)摘要： 離群點(diǎn)檢測(cè)問(wèn)題在欺詐檢測(cè)，網(wǎng)絡(luò)魯棒性分析，和入侵檢測(cè)等領(lǐng)域上有著重要的應(yīng)用，并且大多數(shù)應(yīng)用在高維數(shù)據(jù)領(lǐng)域中，Aggarwal 和Yu提出的基于子空間投影和遺傳算法（GA）的離群點(diǎn)檢測(cè)方法是處理高維數(shù)據(jù)的一個(gè)有效方法。由于該算法的交叉重組過(guò)程采用貪心策略選擇子串，并且隨著變異概率的改變可能導(dǎo)致發(fā)現(xiàn)不了一些有意義的離群數(shù)據(jù)。本文提出一種改進(jìn)的算法，通過(guò)對(duì)原算法的交叉過(guò)程和變異過(guò)程進(jìn)行適當(dāng)?shù)母倪M(jìn)，提高了檢測(cè)的精度并不受變異概率改變的影響。關(guān)鍵詞：離群點(diǎn)檢測(cè)；高維數(shù)據(jù)；遺傳算法；交叉；變異An improved high-dimensional Outlier detection algorithm Based on genetic algorithmJia ruiyu,Huang yitang,Shidondong（Educational Department Key Laboratory of Intelligent Computing & Signal Processing, Anui University, Hefei, china 230039School of Computer Science and Technology of Anhui University, Hefei 230039 ）Abstract.:The outlier detection problem has important applications in the field of fraud detecti，on, network robustness analysis, and intrusion detection. Most such applications are most important for high-dimensional domains in which the data can contain hundreds of dimensions. Aggarwal and Yus recent projection of space-based and genetic algorithm (GA) of the Outlier Detection of high-dimensional data processing is an effective method, because the algorithm is cross-restructuring process by greedy string of strategic options, and mutation in the course of this mutation probability that the change may not lead to some Outlier. This paper presents an improved method, through the crossover and the variability of due process of improvement, Improve the accuracy of the test and is not subject to mutation probability of impactKey words: outlier detection；high-dimensional data；genetic algorithm；crossover；mutation1. 引言離群數(shù)據(jù)挖掘通?？梢钥醋魅齻€(gè)子問(wèn)題：什么樣的數(shù)據(jù)是異常，即離群點(diǎn)的定義；有效挖掘離群數(shù)據(jù)的方法； 離群點(diǎn)的意義，即離群挖掘結(jié)果的合理解釋。到目前為止，離群點(diǎn)還沒(méi)有一個(gè)被普遍采納的定義，Hawkins 對(duì)離群定義在一定意義上揭示了離群點(diǎn)的本質(zhì)：“離群點(diǎn)與其他點(diǎn)如此不同，以至于讓人懷疑它們是由另外一個(gè)不同的機(jī)制產(chǎn)生的。”現(xiàn)有的離群點(diǎn)的定義大多是在Hawkins定義的基礎(chǔ)上給出的一個(gè)定量化描述。近年來(lái)，研究人員提出了大量的離群檢測(cè)算法，大致可以把它們歸納為以下幾類：基于統(tǒng)計(jì)的方法、基于密度的方法、基于深度的方法、基于距離的方法和基于偏離的方法。在一些實(shí)際的應(yīng)用中常常要面臨這高維的問(wèn)題，高維空間離群檢測(cè)與其他數(shù)據(jù)集的離群檢測(cè)差別甚大的原因主要有兩個(gè)：高維空間數(shù)據(jù)的稀疏性經(jīng)常導(dǎo)致所有記錄在傳統(tǒng)距離的收稿日期:2008基金項(xiàng)目:安徽省高等學(xué)校省級(jí)自然科學(xué)研究項(xiàng)目（kj2008B092）作者簡(jiǎn)介：賈瑞玉（1965-），女，副教授,研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、數(shù)據(jù)挖掘、人工智能;黃義堂（1983-），男，安徽滁州人，碩士研究生，研究方向?yàn)橹悄苘浖?。意義上都有可能是離群點(diǎn)。因此，高維空間中很難找到一個(gè)通用的離群產(chǎn)生機(jī)制；高維空間中的離群檢測(cè)算法的計(jì)算復(fù)雜度通常都比較高，算法的執(zhí)行效率極低。高維空間中的異常檢測(cè)通常采用AggarwalYu提出的高維數(shù)據(jù)異常檢測(cè)方法?；舅枷胧前迅呔S空間投影到子空間，采用演化計(jì)算來(lái)尋找最優(yōu)子空間，降低空間的維數(shù)，然后利用傳統(tǒng)的檢測(cè)算法來(lái)發(fā)現(xiàn)異常。具體實(shí)現(xiàn)時(shí)，高維空間中異常模式的檢測(cè)通常是非常困難的，一個(gè)最簡(jiǎn)單的辦法是考慮數(shù)據(jù)維的所有可能組合，對(duì)所有子空間進(jìn)行異常模式的搜索。這種方法雖然能找出全局最優(yōu)的離群點(diǎn)，然而對(duì)于具有n個(gè)屬性的數(shù)據(jù)集，可能的維數(shù)組合數(shù)為，對(duì)于高維數(shù)據(jù)，這個(gè)數(shù)字將是一個(gè)天文數(shù)字，因此算法的執(zhí)行效率非常差。針對(duì)這一缺陷， AggarwalYu運(yùn)用遺傳算法提出了子空間離群點(diǎn)檢測(cè)方法（簡(jiǎn)記為Gen）優(yōu)化了這個(gè)問(wèn)題的求解，并取得良好效果。但在交叉過(guò)程和變異過(guò)程仍存在缺陷，檢測(cè)的精度不夠高。在此基礎(chǔ)上通過(guò)對(duì)原算法的交叉過(guò)程和變異過(guò)程進(jìn)行適當(dāng)?shù)母倪M(jìn)，提高了檢測(cè)的精度并不受變異概率改變的影響。2. 原算法描述 Gen算法將數(shù)據(jù)的每一維分成個(gè)等深度（equi-depth）區(qū)間，即數(shù)據(jù)映像到一維空間上后，每一區(qū)間包含相等數(shù)量的數(shù)據(jù)點(diǎn)，占總數(shù)據(jù)點(diǎn)的f=1/。在一個(gè)數(shù)據(jù)集k 維子空間中的每一維上各取一個(gè)深度區(qū)間，組成一個(gè)k 維立方體D，引入稀疏系數(shù)S(D)來(lái)表示它的稀疏程度.(D 對(duì)應(yīng)的k 個(gè)屬性及取值相當(dāng)于數(shù)據(jù)集的一個(gè)模式)。，S(D)越小表示D 所包含的數(shù)據(jù)點(diǎn)越少，稀疏系數(shù)很小的D對(duì)應(yīng)的模式即為異常模式。稀疏系數(shù)S(D)的定義如下：其中，n(D)為立方體D 包含的數(shù)據(jù)點(diǎn)的數(shù)目，f = f=1/，N 為數(shù)據(jù)集大小. 為預(yù)期分?jǐn)?shù)，為標(biāo)準(zhǔn)偏差點(diǎn)。Gen算法描述：GA 的操作對(duì)象是字符串，變量與個(gè)體之間的映像要通過(guò)編碼實(shí)現(xiàn)，下面簡(jiǎn)單介紹GA的個(gè)體編碼?？紤]一個(gè)n 維數(shù)據(jù)集，第k（kn）個(gè)屬性的取值可能為1或者“*”，“*”表示對(duì)該屬性的取值不關(guān)心。例如對(duì)一個(gè)四維數(shù)據(jù)集的二維子空間它的一個(gè)可能的二維子空間模式為“*3*9”，這個(gè)模式中，第二維和第四維的取值是確定的，而第一維和第三維的取值是不關(guān)心的。Gen中使用前面討論的稀疏系數(shù)計(jì)算相應(yīng)模式的適應(yīng)度由于本文將在通過(guò)對(duì)交叉操作和變異過(guò)程進(jìn)行改進(jìn)，使得改進(jìn)后的算法能夠比Gen 更為有效，因此著重介紹交叉過(guò)程和變異過(guò)程的實(shí)現(xiàn)。交叉過(guò)程（CrossOver）:常用的交叉方法為兩點(diǎn)交叉，即任選一點(diǎn)作為交叉點(diǎn)并交換這點(diǎn)右邊的部分。例如兩個(gè)字符串3*2*1 和1*33*，若選擇第3位置為交叉點(diǎn)，那么交叉結(jié)果為3*23*和1*3*1。在這個(gè)例子中，父串和子串都是五維數(shù)據(jù)的三維子空間模式。但是，如果交叉發(fā)生在第四點(diǎn)之后，兩個(gè)結(jié)果子串為3*2*和1*331，分別對(duì)應(yīng)著五維數(shù)據(jù)的二維子空間和四維子空間模式。由于異常檢測(cè)過(guò)程中只考慮給定維數(shù)的子空間，所以這種兩點(diǎn)交叉會(huì)產(chǎn)生不合理的結(jié)果。因此Gen中對(duì)交叉方法作了相應(yīng)的修改，來(lái)保證父串和子串都對(duì)應(yīng)相同給定維數(shù)的子空間模式。令k 為指定的子空間維數(shù)，對(duì)于一對(duì)模式階為k 的字符串s1 和s2，指定串中的一個(gè)位置，有以下3 種類型：(1) 在此位置上，兩個(gè)串都是*(2) 在此位置上，兩個(gè)串都不是*(3) 在此位置上，兩個(gè)串中只有一個(gè)是*設(shè)s 為s1 和s2 交叉生成的一個(gè)子串，很明顯在第一類位置上，子串s 也是*。假設(shè)s1 和s2 含k 個(gè)第2 類位置，則s1 和s2 均含有k- k 個(gè)第3 類位置，兩者總共包含2(k- k ) 個(gè)第3 類位置。Gen中字符串s1 和s2 重組過(guò)程（Recombine(s1, s2)）（即s1 和s2 交叉過(guò)程）描述如下： 設(shè)R 為第二類位置的集合（k 個(gè)），Q 為第三類位置的集合，s 為一子串。 枚舉第二類位置的所有可能重組方式（2 k 種），選擇稀疏系數(shù)最小的一種組合方式設(shè)置在s的對(duì)應(yīng)位置上。 反復(fù)選取Q 中第三類位置對(duì)應(yīng)的父串值并設(shè)置在s 的相應(yīng)位置上，使得s 有最小的稀疏系數(shù)，直到s 的k 個(gè)位置都設(shè)置完畢。s 的其它位置設(shè)為*。 令s 為s 的補(bǔ)串，s 的每一位置的取值相對(duì)于s 來(lái)自不同的父串，將s 作為s1 和s2 交叉后的另一個(gè)子串。很顯然，重組后的交叉過(guò)程能夠保證子串s 和s 與父串有相同的維（階）數(shù)。變異過(guò)程（Mutation）Gen算法的變異過(guò)程分兩種情況：(1)設(shè)s為原字符串s的一個(gè)子串，其每一個(gè)位置的取值都為*，Gen將s之外的一個(gè)位置變?yōu)?，同時(shí)我們從1到之間選取一個(gè)值更改s的一個(gè)隨機(jī)位置的屬性值，從而確保子空間的維數(shù)不會(huì)發(fā)生變化。(2)如果變異發(fā)生在不是*的位置上，這個(gè)位置的屬性值就由1到的一個(gè)其他值來(lái)替代。對(duì)于這兩種情況，Gen設(shè)置兩個(gè)變異概率p1和p2。P1對(duì)應(yīng)（1）的情況，p2對(duì)應(yīng)（2）的情況，計(jì)算它們的平均值p=（p1+ p2）/2來(lái)作為Gen的變異概率。3. Gen算法的改進(jìn)在一對(duì)模式階為k 的字符串（k 維模式）s1 和s2 交叉過(guò)程中，其子串形式有種，其中可能包含了一些稀疏系數(shù)很小的子串。Gen認(rèn)為遍歷這些子串耗時(shí)太多，因此，Gen中的重組過(guò)程（Recombine(s1,s2)）只是結(jié)合貪心策略，盡可能獲取比s1 和s2 稀疏系數(shù)小的一個(gè)子串s 即可。顯然，Gen 在交叉過(guò)程中降低了時(shí)間復(fù)雜度，但由于其在Recombine(s1,s2)過(guò)程中只是為了獲取一個(gè)稀疏系數(shù)小的子串s，并沒(méi)有對(duì)s 以外的一些稀疏系數(shù)很小的子串（k 維模式）進(jìn)行判斷處理，最終可能丟失相當(dāng)部分的異常模式，因?yàn)閟 以外的其它子串中很可能存在一些比s 更優(yōu)的子串，同時(shí)這些子串中包含了一些稀疏系數(shù)很小的子串（異常模式）。針對(duì)Recombine(s1,s2)的這一不足，本文通過(guò)保存s 以外的一些較優(yōu)的子串（異常模式）并進(jìn)行判斷處理來(lái)對(duì)Gen進(jìn)行改進(jìn)。預(yù)置參數(shù)MinSC 和異常模式候選集CandSet，在字符串s1和s2 交叉過(guò)程中，對(duì)交叉得到的子串進(jìn)行判斷處理：如果發(fā)現(xiàn)某子串模式的稀疏系數(shù)小于MinSC，將該子串模式保存在CandSet。顯然，參數(shù)MinSC應(yīng)該根據(jù)實(shí)際數(shù)據(jù)集合理設(shè)置，盡量比較小。改進(jìn)后的重組過(guò)程為Recombine-1(s1,s2)： 設(shè)R 為第二類位置的集合（k 個(gè)），Q 為第三類位置的集合，s 為一子串。 枚舉第二類位置的所有可能重組方式（2k種），選擇稀疏系數(shù)最小的一種組合方式設(shè)置在s的對(duì)應(yīng)位置上。 用第三類位置的每一種重組方式來(lái)擴(kuò)展s，如果s 的稀疏系數(shù)MinSC，則s 為異常模式，將其添加至CandSet。最終選擇其中一種重組方式設(shè)置在s 的相應(yīng)位置上，使得s 有最小的稀疏系數(shù)。 令s 為s 的補(bǔ)串， s 的每一位置的取值相對(duì)于s 來(lái)自不同的父串，將s 作為s1 和s2 交叉后的另一個(gè)子串。由于對(duì)交叉過(guò)程中產(chǎn)生的子串進(jìn)行判斷處理，增加了異常模式候選集CandSet，擴(kuò)大的模式多樣性，因此，改進(jìn)后的算法 與Gen相比更有可能收斂到期望的解。在變異過(guò)程（Mutation）中如果p1和p2發(fā)生變化，即變異概率p發(fā)生變化，很可能導(dǎo)致相當(dāng)部分的異常模式發(fā)生變化，按照上述方法增加變異候選集MutationSet，在發(fā)生變異過(guò)后將產(chǎn)生的新的字符串保存在MutationSet中，通過(guò)將變異前后的字符串的稀疏系數(shù)與MinSC進(jìn)行比較。假設(shè)s是s的變異字符串（1）若s的稀疏系數(shù)MinSC且s的稀疏系數(shù)MinSC且s的稀疏系數(shù)MinSC。者將s保留。（2）若s的稀疏系數(shù)MinSC或者s的稀疏系數(shù)MinSC,者將s替換s。通過(guò)上述處理，從而保證查找結(jié)果不會(huì)因p的變化而發(fā)生變化。4. 實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)采用UCI機(jī)器學(xué)習(xí)倉(cāng)庫(kù)的數(shù)據(jù)集。PC 機(jī)的配置：3.0G Intel(R)CPU，DDR512M 內(nèi)存。數(shù)據(jù)集Breastcancer ,Zoo和Machine 的屬性區(qū)間個(gè)數(shù)=2。Gen代表原算法，Gen代表只進(jìn)行交叉過(guò)程改進(jìn)的算法，Gen代表交叉過(guò)程和變異過(guò)程都改進(jìn)的算法。試驗(yàn)結(jié)果見(jiàn)表1和表2：表1 Gen和Gen比較數(shù)據(jù)集Gen（time）Gen（time）Gen（quality）Gen（quality）Breastcancer (14)(m=200, k=4)42s40s-3.54(125),15-3.54(250),20Zoo (18)(m=100,k=4)18s14s-3.00(62),6-3.00(125),9Machine (8)（m=100，k=5）12s9s-3.31(23),12-3.31(96),25表1 中數(shù)據(jù)集Breastcancer， Zoo 和Machine的屬性區(qū)間個(gè)數(shù)=2。結(jié)果分析：以Zoo數(shù)據(jù)集（測(cè)試在其18個(gè)屬性上進(jìn)行）為例。m：最優(yōu)異常模式個(gè)數(shù)，k：子空間維數(shù)，交叉概率和變異概率分別取0.5 和0.05，即搜索最優(yōu)的100個(gè)4維異常模式。Gen耗時(shí)18秒找到100個(gè)4維異常模式，其中包括62個(gè)不同的異常模式，稀疏系數(shù)均值為-3.00，包含這些異常模式的離群點(diǎn)有6個(gè)。Gen耗時(shí)14秒找到100個(gè)4維異常模式，其中包括125（增加CandSet的緣故）個(gè)不同的異常模式，稀疏系數(shù)均值為-3.00，包含這些異常模式的離群點(diǎn)有9個(gè).顯然Gen比Gen的效率更高，原因在與Gen 在交叉過(guò)程中的改進(jìn)能夠找到更多的異常模式，同時(shí)Recombine-1(s1,s2)較Recombine(s1,s2)可能得到更優(yōu)的子串s，使得Gen 中的GA 收斂更快，耗時(shí)更少。表1表明Gen比Gen能發(fā)現(xiàn)更多的異常模式和離群點(diǎn)。表2 Gen和Gen比較數(shù)據(jù)集Gen（quality）Gen（quality）Zoo (18)(m=100,k=4,p=0.05)-3.06(125),9-3.00(127),10Zoo (18)(m=100,k=4,p=0.01)-3.00(121),9-3.00(127),10Zoo (18)(m=100,k=4,p=0.002)-2.99(116),7-3.00(127),10表2中數(shù)據(jù)集Zoo在m、k、交叉概率相等的情況下，對(duì)變異概率分別為0.05、0.01、0.002進(jìn)行比較，發(fā)現(xiàn)在Gen中隨著變異概率的不同，查找的異常模式和離群點(diǎn)的個(gè)數(shù)也不同,而在Gen中者不會(huì)發(fā)生變化，這是因?yàn)樵谧儺愡^(guò)程中增加了一個(gè)變異候選集，通過(guò)再次比較，篩選出一部分發(fā)生變異的字符串，確保變異概率的改變不會(huì)對(duì)