使用遺傳算法的間接特征向量選取方法

李志偉

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

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

1.簡(jiǎn)介

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

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

2.遺傳算法

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

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

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

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

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

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

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

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

（1）在V中提取訓(xùn)練數(shù)據(jù)對(duì)應(yīng)的那部分特征向量，并使用V ∈R 標(biāo)記，tn為訓(xùn)練數(shù)據(jù)的個(gè)數(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ì)算出種群對(duì)應(yīng)的適應(yīng)度f（a （k））（1≤i≤m）。

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

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

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

遺傳算法GA中所用的符號(hào)表示如下：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）。因此，文中整個(gè)的GA時(shí)間復(fù)雜度為Ga（O（ps+ps×Proc？搖m+ps×Proc？搖c）+O（ps×log ps））。

4.結(jié)論

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