中性游走驅(qū)動(dòng)的進(jìn)化子空間聚類算法

林鑫濤,何振峰

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福州 350108)

1 引 言

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

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

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

2 研究背景

2.1 子空間聚類簡介

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

2.2 進(jìn)化子空間聚類算法Chameleoclust

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

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

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

(1)

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

(2)

(3)

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

(4)

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

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

Chameleoclust的不足之處:

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

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

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

3.1 中性概念簡介

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

中性突變是用中性近鄰(單輪突變可達(dá)且表現(xiàn)型相同的基因)替換原基因的過程,因此可以使用中性近鄰的進(jìn)化潛力來對中性突變進(jìn)行評價(jià),以解決無法通過表現(xiàn)型變化評價(jià)中性突變的問題.Marie等人指出:潛力大的中性近鄰能夠?qū)?dāng)前搜索引導(dǎo)到搜索空間的其他部位以帶來多樣性[10].

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

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

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

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

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

進(jìn)化潛力定義:

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

圖3 排序策略的改進(jìn)Fig.3 Improvement of sorting strategy

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

(5)

(6)

(7)

中性游走驅(qū)動(dòng)的進(jìn)化子空間聚類:

Begin

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

Step2.中性游走起點(diǎn)Γ0=初代種群中排在最后的個(gè)體;

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

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

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

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

Step8.return Γ0;

End

3.3 算法復(fù)雜度分析

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

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

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

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

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

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

(8)

(9)

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

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

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

表2 實(shí)驗(yàn)結(jié)果對照(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í),超過一定遺傳迭代次數(shù)后,Chameleoclust NW的最佳適應(yīng)值要明顯優(yōu)于Chameleoclust,即前者的搜索效率要明顯高于后者.

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

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

圖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聚類的最佳適應(yīng)值增長情況.可以看出,s取值0.5時(shí)算法的搜索效率要明顯高于取值0.1或0.8時(shí),這說明過度強(qiáng)調(diào)優(yōu)秀個(gè)體的作用(s太小)或過度強(qiáng)調(diào)搜索的全局性(s太大)都會對算法搜索效率產(chǎn)生一定的影響,只有把握好兩者之間的平衡才能較好地發(fā)揮算法的性能.

5 結(jié)束語

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