中性游走驅(qū)動的進化子空間聚類算法

林鑫濤,何振峰

(福州大學 數(shù)學與計算機科學學院,福州 350108)

1 引 言

聚類是把數(shù)據(jù)對象集劃分為多個數(shù)據(jù)簇,使得處于同一簇中的對象具有高相似性,處于不同簇中的對象具有高相異性的過程,聚類可以幫助人們更好地理解數(shù)據(jù)的內(nèi)在結構,在諸多領域都發(fā)揮著巨大的作用[1].近年來,信息技術的高速發(fā)展使得數(shù)據(jù)呈現(xiàn)出高維化的趨勢,“維度災難[2]”讓傳統(tǒng)聚類算法的聚類效果大打折扣.子空間聚類是進行高維數(shù)據(jù)聚類的有效方法之一,其利用特征選擇的思想從數(shù)據(jù)集所處的特征空間中抽取出一個或多個子空間,并在各個子空間內(nèi)搜索數(shù)據(jù)簇.現(xiàn)有子空間聚類算法雖然在一定程度上解決了“維度災難”的影響,但還存在可使用性差、效率低、可伸縮性差、魯棒性低、啟發(fā)信息不足等諸多問題[3].

Peignier等人于2015年提出進化子空間聚類算法Chamleoclust[4],算法利用可演化的染色體結構來搜索子空間和聚集數(shù)據(jù),將遺傳算法[5]的優(yōu)點融入子空間聚類過程中,取得了很好的效果.Chameleoclust已經(jīng)被運用于化學分子研究、音樂的自動產(chǎn)生等領域[6].但由于啟發(fā)信息不足的原因,其仍然存在搜索效率不高;容易陷入局部最優(yōu)等問題.

傳統(tǒng)進化算法思想源于達爾文的自然選擇學說,將自然選擇對有利突變的固定作為進化的主要驅(qū)動力[7].1968年由木村資生提出的“中性理論(neutral theory)[8]”認為:在生物遺傳進化過程中發(fā)生的大部分突變是對生物體生存既無好處也無壞處的“中性突變(neutral mutations)”,而生物進化的主要驅(qū)動力是中性突變的隨機固定而不是自然選擇引起的有利突變的固定.本文以中性理論的思想為基礎提出一種“中性游走(neutral walks)[9]”驅(qū)動的進化子空間聚類算法.以進化潛力為啟發(fā)信息對染色體進一步評價,并利用中性游走來引導中性突變,在提高算法效率的同時,也能適時地將搜索引導到搜索空間的其它部位,較好地解決了原算法的搜索陷入局部最優(yōu)的問題.

2 研究背景

2.1 子空間聚類簡介

子空間聚類是為解決高維數(shù)據(jù)聚類而產(chǎn)生的一種新的聚類分支,與傳統(tǒng)聚類相比,子空間聚類面臨的主要挑戰(zhàn)是如何有效地搜索一系列子空間并在其中聚類.目前的子空間聚類算法主要有自底向上和自頂向下兩種搜索策略,自底向上的子空間聚類算法從低維子空間開始開始,向上增加子空間的維度,直到遍歷所有可能的子空間,尋找所有可能的簇.自頂向下的子空間聚類算法從數(shù)據(jù)集的全維度數(shù)據(jù)空間開始,遞歸地搜索越來越小的子空間.目前子空間聚類的主要問題有:搜索空間過大導致效率不高;對啟發(fā)信息依賴性很強;魯棒性差;可伸縮性差等[3].

2.2 進化子空間聚類算法Chameleoclust

Chameleoclust算法將進化算法的可操作性、并行性、全局搜索性、魯棒性等優(yōu)點融合到子空間聚類求解過程中,算法染色體結構具有的可變的染色體長度、顯隱性基因等仿生特征給搜索過程帶來了極大的自由度,且算法只有一個與子空間聚類相關的輸入?yún)?shù):數(shù)據(jù)簇數(shù)量上限,這很好地解決了大部分子空間聚類算法對輸入?yún)?shù)的依賴性問題.Chameleoclust過程如圖1所示(詳見文獻[4]).

圖1 Chameleoclust流程圖Fig.1 Flow chart of Chameleoclust

編碼策略:算法采用變長整數(shù)編碼,將簇中心信息編碼成染色體.其染色體Γ由大量基因四元組γ=構成,其中g∈{0,1}決定了γ是否表達;c為簇編號;d為維度編號;m∈{-1000,…,1000}表示貢獻度.每個染色體對應一個由子空間中心點pc(表示數(shù)據(jù)簇和該簇所處的子空間)組成的集合Φ,簇i對應子空間中心點在維度j的值計算過程如公式(1)所示,其中xmax=max(abs(S)),S為數(shù)據(jù)集標準化(x=(x′-μ)/σ)后所有特征值集合.

(1)

適應值函數(shù):算法的適應值函數(shù)如公式(2)所示,其中Spc表示所有分配到簇c的數(shù)據(jù);ε(x,pc)表示數(shù)據(jù)x(經(jīng)過標準化后)與簇c的不匹配程度(基于曼哈頓距離dD,計算過程如公式(3)),當ε(x,pc)的值最小時數(shù)據(jù)x被分配到簇c,其中‖表示空間的維數(shù),D表示全維度空間,DDpc表示Dpc的補空間,O為0向量.

(2)

(3)

選擇:在新種群的產(chǎn)生階段,將排在最后的個體作為精英直接保留到新種群中后(elitist selection),再通過選擇變異產(chǎn)生N-1個新個體.選擇父代時,個體α被選擇概率pα(公式(4),s為選擇壓力參數(shù))根據(jù)其在種群中的排位rα∈{1,…,N}呈指數(shù)級增長.因此排序策略是十分重要的,Chameleoclust采用基于單一適應值的簡單排序(從小到大),由于在實際搜索過程中每一代種群中都有大量適應值相同的個體,這種簡單排序顯然無法提供足夠的啟發(fā)信息.

(4)

變異:算法有兩種突變形式:染色體重排(包含子段刪除、移位、復制,如圖2所示)、點突變(隨機替換任意位置四元組中的元件值),其中子段刪除與子段復制是變長突變,子段移位和點突變是定長突變.這些靈活的突變形式為算法的搜索過程帶來了極大的自由度.

圖2 三種染色體重排策略Fig.2 Three chromosome rearrangement strategies

Chameleoclust的不足之處:

簡單排序策略使得算法無法對適應值相同但染色體不同的個體進行優(yōu)劣評價,因此缺乏足夠的啟發(fā)信息來引導搜索,這也使得在擁有極大自由度的情況下,算法搜索空間過大以及容易陷入局部最優(yōu)等問題進一步加劇.因此算法的搜索效率不高,且搜索過程中容易出現(xiàn)連續(xù)多輪遺傳迭代聚類質(zhì)量沒有提高的局面.

3 中性游走驅(qū)動的Chameleoclust算法

與自然選擇理論不同,中性理論從分子層面闡述生物遺傳進化的原因.因此以中性理論視角出發(fā)能夠從染色體層面對Chameleoclust存在的問題進行合理的解釋,并更容易找出合適的解決方案.

3.1 中性概念簡介

生物體的基因型(編碼形式)與表現(xiàn)型(具體作用)之間存在多對一的映射關系,即生物的遺傳編碼存在著大量冗余(中性冗余).中性冗余的存在使得一些基因型的變化并不會造成表現(xiàn)型的改變(中性突變).中性突變作為生物遺傳進化過程中占比最高的突變類型,對生物遺傳材料中發(fā)生的有害突變起到了緩沖作用的同時;也讓生物體有了能應對不斷變化的環(huán)境的能力,對生物遺傳進化起著積極作用.

中性突變是用中性近鄰(單輪突變可達且表現(xiàn)型相同的基因)替換原基因的過程,因此可以使用中性近鄰的進化潛力來對中性突變進行評價,以解決無法通過表現(xiàn)型變化評價中性突變的問題.Marie等人指出:潛力大的中性近鄰能夠?qū)斍八阉饕龑У剿阉骺臻g的其他部位以帶來多樣性[10].

中性突變將具有相同表現(xiàn)型的基因相連接組成了中性網(wǎng)絡.中性游走[9]通常被用來探索中性網(wǎng)絡,其一般步驟如下:1.選取初始起點;2.找出當前起點的所有中性近鄰;3.從中性近鄰中選出與起點相比有距離增長(游走的步長)的個體替換原起點;4.重復2～3步直到游走結束.2.中的步長概念依具體問題而定,在啟發(fā)信息充足的情況下,可以在中性游走時控制步長來對進化搜索過程進行引導.

中性相關理論一直是進化計算領域的研究熱點[11,12],研究者們在進化算法中加入中性元素來解決各類優(yōu)化問題:Marmion等人利用含有中性冗余的進化算法解決流水作業(yè)調(diào)度問題,并利用中性游走主動地對搜索進行引導[13].Vassilev等人在數(shù)字電路進化算法中,以中性突變作為主要驅(qū)動力來演化[14].大量實驗表明:中性的存在能為進化系統(tǒng)帶來以下好處:(1)能夠?qū)τ泻ν蛔冞M行限制,使得即使在高突變率下種群依然可以保持健康;(2)能在一定程度上避免搜索過程中出現(xiàn)過早聚合的問題;(3)能夠提高搜索可靠性.

3.2 中性游走驅(qū)動的Chameleoclust算法

由于隱性基因等因素的影響,Chameleoclust編碼結構存在大量中性冗余,遺傳過程中發(fā)生的絕大部分突變都是對當前適應值(表現(xiàn)型)沒有直接影響的中性突變,再加上其選擇機制的影響,新種群個體大多是原種群中排位靠后個體的中性近鄰,這導致同一代種群中存在大量適應值相同的個體.但Chameleoclust無法對適應值相同的個體進行優(yōu)劣評價,因此啟發(fā)信息不足,無法對中性突變進行正確的引導,從而引發(fā)算法搜索效率不高且極易陷入局部最優(yōu)等問題.

為解決上述問題,我們以對中性突變的引導為搜索過程的重心,提出中性游走驅(qū)動的Chameleoclust算法(簡稱Chameleoclust NW).算法以進化潛力為啟發(fā)信息,并結合中性游走對排序策略進行改進(見圖3),使得在適應值相同時,進化潛力越高的個體被選擇成為父代的概率越大.

進化潛力定義:

由中性近鄰的潛力特性(3.1部分)可知,潛力大的個體能將當前搜索引導到遠離當前搜索空間的部位以帶來更多的多樣性,因此使用父代染色體到子代染色體的變化量來衡量一個染色體的進化潛力,由于表現(xiàn)型無法體現(xiàn)這種變化,因此在定義進化潛力函數(shù)時主要考慮的是突變可能對基因型所帶來的改變.

圖3 排序策略的改進Fig.3 Improvement of sorting strategy

與算法用子空間中心點集合Φ來表示染色體的表現(xiàn)型相對應,提出“潛在子空間中心點集合”Φ′來表示染色體的基因型.與子空間中心點集合不同的是,在構建潛在子空間中心點集合時同時考慮了染色體中顯性基因和隱性基因的影響,因此Φ′代表了Γ可能對應的所有數(shù)據(jù)簇(包含現(xiàn)有的和潛在的),而對于其中任一數(shù)據(jù)簇,潛在子空間中心點表示其可能產(chǎn)生的子空間(包含現(xiàn)有的和潛在的維度)以及其對應的潛在的中心點值.簇i所對應潛在子空間中心點在維度j的值計算過程如公式(5)所示.

(5)

(6)

(7)

中性游走驅(qū)動的進化子空間聚類:

Begin

Step1.初始化(圖1:1.初始化);

Step2.中性游走起點Γ0=初代種群中排在最后的個體;

Step3.產(chǎn)生新一代種群(圖1:2.新種群的產(chǎn)生);

Step4.將新種群按適應值(公式(2))排序(圖1:3.排序);

Step6.Γ0=新種群中排在最后的個體;

Step7.判斷預設遺傳代數(shù)是否結束,若未結束則跳回Step 3;

Step8.return Γ0;

End

3.3 算法復雜度分析

算法涉及到的主要參數(shù)為:T表示總遺傳迭代次數(shù),N表示種群中的個體數(shù),C表示設定的簇數(shù)量上限,D表示數(shù)據(jù)的維度,R表示數(shù)據(jù)對象的數(shù)量.

算法過程中占據(jù)主要時間開銷的步驟包括:適應值計算(公式(2));進化潛力計算(公式(6));排序(Step 4～5).在一輪迭代中,計算適應值過程中的時間復雜度為O(NCRD);計算進化潛力過程中的時間復雜度為O(NC2D);排序時采用快速排序策略,因此時間復雜度為O(Nlog2N).將上述過程的時間復雜度結合可得到算法一輪迭代的時間復雜度O(NCRD+NC2D+Nlog2N).由于log2N<

可以看出,雖然Chameleoclust NW比Chameleoclust多了計算和比較進化潛力的時間開銷,但是兩者的時間復雜度相同,都為O(TNCRD).

4 實驗分析

實驗環(huán)境及數(shù)據(jù)集:本文在5組UCI數(shù)據(jù)集上進行對照試驗,表1給出這些數(shù)據(jù)集的信息.實驗算法采用R語言編寫,運行在一臺配置Intel(R)Core(TM)i7 CPU 3.40GHz,RAM 8GB的計算機上,操作系統(tǒng)是Windows7.

評價指標:采用熵指標[15](Entropy)進行算法的性能分析,其計算過程如公式(8)所示.其中H表示數(shù)據(jù)集的類標簽數(shù),C表示生成的簇數(shù)量,Spc表示簇c中的數(shù)據(jù)對象,E(c)表示單個簇c的熵值,其計算過程如公式(9)所示,其中p(h|c)表示簇c中數(shù)據(jù)類標簽為h的概率.熵指標的取值范圍為[0,1],數(shù)值越大,表明算法聚類性能越優(yōu)越.

(8)

(9)

表1 UCI數(shù)據(jù)集
Table 1 UCI datasets

數(shù)據(jù)集維數(shù)類數(shù)數(shù)據(jù)量Breast332198Liver62345Shape179160Glass96214Diabetes82768

實驗對比:分別對各個數(shù)據(jù)集執(zhí)行10次Chameleoclust和Chameleoclust NW,實驗參數(shù)設置如下:種群規(guī)模N=100,初代種群染色體長度(四元組個數(shù))設為100,其中顯性基因與隱形基因的比例設為1∶2,突變率um=0.005,選擇壓力參數(shù)s=0.5,遺傳迭代次數(shù)T=5000,數(shù)據(jù)簇數(shù)量上限cmax=100.表2給出了10次實驗得到的平均值(最優(yōu)值)結果對照.圖4給出在聚類數(shù)據(jù)集breast時相同代數(shù)Chameleoclust和Chameleoclust NW最佳適應值增長情況.

表2 實驗結果對照(Entropy)
Table 2 Comparison of results(Entropy)

數(shù)據(jù)集ChameleoclustChameleoclust NWbreast0.40069(0.41815)0.43344(0.45321)Liver0.22495(0.25447)0.24968(0.27445)Shape0.84699(0.87568)0.85008(0.87946)Glass0.60447(0.61149)0.64986(0.65809)diabetes0.33086(0.35844)0.33177(0.36743)

由表2的數(shù)據(jù)對照可以看出,無論是平均值還是最優(yōu)值,Chameleoclust NW的效果都優(yōu)于Chameleoclust.由圖4可看出,在聚類數(shù)據(jù)集breast時,超過一定遺傳迭代次數(shù)后,Chameleoclust NW的最佳適應值要明顯優(yōu)于Chameleoclust,即前者的搜索效率要明顯高于后者.

圖4 兩種算法取得的最優(yōu)適應值(breast)Fig.4 Best fitnesses achieved by two algorithms(breast)

參數(shù)s對算法的影響:選擇壓力參數(shù)s∈[0,1)的值直接影響了個體成為父代概率(公式(4)).圖5給出了不同s值下的選擇概率分布情況.可以看出,s的值越小,被選擇的機會就越集中在排位靠后的優(yōu)秀個體上;s的值越大,被選擇的機會就分配得越平均,可加強搜索的全局性.

圖5 不同s值下的選擇概率分布對比Fig.5 Comparison of selection probability distributions with different s-values

圖6 參數(shù)s對算法性能的影響(breast)Fig.6 Influence of parameters s on the algorithm′s performance(breast)

圖6給出了在不同的s值情況下使用Chameleoclust NW算法對數(shù)據(jù)集breast聚類的最佳適應值增長情況.可以看出,s取值0.5時算法的搜索效率要明顯高于取值0.1或0.8時,這說明過度強調(diào)優(yōu)秀個體的作用(s太小)或過度強調(diào)搜索的全局性(s太大)都會對算法搜索效率產(chǎn)生一定的影響,只有把握好兩者之間的平衡才能較好地發(fā)揮算法的性能.

5 結束語

本文將中性理論的思想與Chameleoclust算法的框架相結合,提出一種中性游走驅(qū)動的進化子空間聚類算法.該算法以進化潛力為啟發(fā)信息,對算法的排序策略進行改進,并以精英個體的進化潛力為步長進行主動的中性游走,以此來對遺傳進化過程中的主要角色中性突變進行主動引導,為搜索帶來多樣性的同時,提高了算法的搜索效率,也進一步避免了搜索陷入局部最優(yōu)的情況.本文的后續(xù)工作包括:進一步探索進化策略相關參數(shù)對搜索穩(wěn)定性的影響;嘗試加入交叉變異算子來加強染色體個體之間的信息交流.