李志偉

摘 要： 遺傳算法目前在特征向量選取中扮演著重要角色。由于其具有并行、自適應(yīng)強(qiáng)等諸多優(yōu)點(diǎn)，廣泛受到多個領(lǐng)域的關(guān)注。本文首先對遺傳算法、譜聚類等基礎(chǔ)知識進(jìn)行概述，其次介紹遺傳算法的三個重要過程遺傳、變異及交叉算子。最后給出遺傳算法進(jìn)行特征選擇的步驟。為研究譜聚類算法中，使用遺傳算法進(jìn)行特征選擇提供學(xué)習(xí)參考。

關(guān)鍵詞： 譜聚類 特征向量選擇 遺傳算法

1.簡介

目前特征選擇方法有很多，如模擬退火算法、遺傳算法等。其中，遺傳算法作為一種組合的優(yōu)化算法，不是對單個特征進(jìn)行優(yōu)劣劃分，而是對一個可能特征子集進(jìn)行考核評價，能夠保證所選特征子集的組合達(dá)到最優(yōu)，省去各特征之間的相關(guān)性這一繁瑣工作；另外，遺傳算法具有并行性、自適應(yīng)性、領(lǐng)域無關(guān)性等諸多特點(diǎn)，能夠很好地處理高維的特征集。故而遺傳算法可有效應(yīng)用于特征選擇中，在很多領(lǐng)域都得到成功應(yīng)用。

譜聚類中前K個最大的特征向量并不總能檢測得出真實(shí)的模式識別問題的數(shù)據(jù)結(jié)構(gòu)。所以，特征向量的選取變得很有必要。特征向量選取方式有許多種，如基于熵排列的方法、使用遺傳算法的特征向量選取方法和多套特征向量選取方法等。而特征向量排列列表中有兩種選擇策略。一是在排列列表中直接選取前K個特征向量，且這K個特征向量是譜聚類中最重要的特征向量。第二種特征向量選取策略是在排列列表中的前Km（Km>K）的特征向量中尋找合適的特征向量組合。通過這種策略得到的特征向量組合能夠反映出原始數(shù)據(jù)的結(jié)構(gòu)，能得到令人滿意的聚類結(jié)果。研究特征向量的選擇對譜聚類很有必要。我們應(yīng)該根據(jù)特征向量提供的信息量的多少估計(jì)其對聚類的重要性，并選擇合適的特征向量組合進(jìn)行譜聚類。

2.遺傳算法

遺傳算法GA作為一種實(shí)用的最佳選擇方法，是一種魯棒性搜索方法。不需要知道很多信息就可以在大空間和難以理解的空間中實(shí)現(xiàn)有效搜索。在每一代中，三個最基本操作即繁殖復(fù)制、交叉和變異，它們在保證個體數(shù)目不變的情況下生成一個新的群體。

GA算法的搜索空間為V 子集中的所有列。在編碼設(shè)計(jì)中，每個顏色提代表一個特征向量組合。一個染色體是一個包含Km個基因的位串。串中的每個基因只包含0和1。若第j位為1，則第j個特征向量被選中。否則，對應(yīng)特征向量被忽略。另外，繁殖、交叉和變異算子按如下分別被定義如下：

繁殖：該算子基于適者生存的原則。設(shè)種群A={a ，a ，…，a }，每個個體都有自己的最大適應(yīng)度f（a ），且在新的代數(shù)中均有自己大量的復(fù)制i（k）。例如，在輪盤賭選擇法中，具有高適應(yīng)度值的第i個個體被賦予一個對應(yīng)比例的很高的繁殖概率。一旦一個個體再次重現(xiàn)，則在下代中，就得到了一個新種群（k）={i（k），i=1，2，…，m}。

交叉算子：在交叉算子中，個體之間通過概率決策交換信息。多點(diǎn)交叉是一種常用的交叉方法，為最佳個體提供了多個雜交幾率。對于多點(diǎn)交叉，隨機(jī)選取一個尚未復(fù)制的p交叉位置，并按降序排列。一串連續(xù)的交叉點(diǎn)之間的基因在雙親之間交換以生成兩個新的后代。

變異：當(dāng)?shù)趇個個體的第j個位置被選中，變異算子僅將狀態(tài)從0變?yōu)?或者相反改變。當(dāng)具有一個很高變異概率的遺傳算法GA退化到一個隨機(jī)搜索時，變異應(yīng)當(dāng)是一個非常低的概率算子。

3.使用遺產(chǎn)算法的間接特征向量選取

輸入：取自原始數(shù)據(jù)集X={x ，x ，…，x }的訓(xùn)練集合；所有特征向量的排列列表的前Km個特征向量組成的矩陣V∈R 。

輸出：最佳的特征向量組合ec

（1）在V中提取訓(xùn)練數(shù)據(jù)對應(yīng)的那部分特征向量，并使用V ∈R 標(biāo)記，tn為訓(xùn)練數(shù)據(jù)的個數(shù)。

（2）產(chǎn)生隨機(jī)種群A（0）={a （0），a （0），…，a （0）}，并設(shè)置迭代次數(shù)k=0。

（3）只使用V 中a （k）的特征向量構(gòu)造出矩陣U ∈R 。使用式（6）計(jì)算出種群對應(yīng)的適應(yīng)度f（a （k））（1≤i≤m）。

（4）直到一個滿足一個合適的迭代次數(shù)時終止。當(dāng)滿足當(dāng)前的種群被認(rèn)為是最佳種群，則轉(zhuǎn)入步驟（6）。否則執(zhí)行下一步。

（5）再繁殖復(fù)制，交叉和變異產(chǎn)生新的染色體，k=k+1，轉(zhuǎn)入步驟（3）執(zhí)行。

（6）從最佳種群中選擇最好的個體，并將得到的高適應(yīng)度值作為最佳的特征向量組合ec 。

遺傳算法GA中所用的符號表示如下：Ga為GA的最大迭代次數(shù)，ps為種群大小，Prob？搖m和Prob？搖c分別為變異概率和交叉概率。該算法的計(jì)算復(fù)雜度主要包括編碼、繁殖復(fù)制、交叉、變異和適應(yīng)度計(jì)算。在GA的每次迭代，繁殖復(fù)制、交叉和變異的復(fù)雜度分別為O（ps）、O（ps×Proc？搖m）和O（ps×Proc？搖c）。我們使用2路歸并排序作為適應(yīng)度排序的算法，它的復(fù)雜度是O（ps×log ps）。因此，文中整個的GA時間復(fù)雜度為Ga（O（ps+ps×Proc？搖m+ps×Proc？搖c）+O（ps×log ps））。

4.結(jié)論

本文介紹了一種使用遺傳算法進(jìn)行特征向量選取的方法。首先對遺傳算法及譜聚類基礎(chǔ)知識進(jìn)行簡要介紹。而后對遺傳算法的三個主要過程進(jìn)行描述，包括遺傳、交叉及變異。第三部分對使用遺傳算法進(jìn)行特征向量選取進(jìn)行介紹，并分析算法執(zhí)行的時空復(fù)雜度。遺傳算法改善了傳統(tǒng)方法對大規(guī)模復(fù)雜數(shù)據(jù)進(jìn)行特征選取的局限性。但由于遺傳算法中群體的大小、交叉、變異概率均是實(shí)驗(yàn)參數(shù)，很難確定，加上獲得的結(jié)果不一定是最優(yōu)解，因此遺傳算法用于特征選擇有待改進(jìn)。最后遺傳算法作為一種組合優(yōu)化方法，為解決實(shí)際問題提供了不少幫助，該算法勢必在未來發(fā)揮更為重要的價值，應(yīng)用前景將更廣闊。

參考文獻(xiàn)：

[1]Zhao F，Jiao L C，Liu H Q，et al.Spectral clustering with eigenvector selection based on entropy ranking[J].Neurocomputing，2010，73（10）：1704-1717.