一種基于遺傳算法的特征選擇和權(quán)重確定方法

(淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000)

特征選擇，是從一個(gè)初始特征集中挑選出一些特征組成最優(yōu)特征子集，依據(jù)這些子集構(gòu)建的分類器能夠使某種評(píng)估標(biāo)準(zhǔn)達(dá)到最優(yōu)，具有較高的預(yù)測(cè)精度.特征選擇可以提高構(gòu)建的分類或回歸模型的泛化能力，降低特征維度的同時(shí)還提高了計(jì)算效率，所以特征選擇方法的研究成為目前模式識(shí)別研究領(lǐng)域中的一個(gè)熱點(diǎn)問題.

本文首先討論了目前常用的一些特征選擇方法，分析了這些方法存在的一些問題，隨后針對(duì)這些問題，本文提出了一種新的基于遺傳算法的特征權(quán)重確定方法.最后我們通過實(shí)驗(yàn)驗(yàn)證了所提算法的效果.

1 特征選擇的相關(guān)工作

特征選擇可以看作是一個(gè)搜索尋優(yōu)的過程.1997年，M.Dash 提出了特征選擇的一般框架，清楚的描述了這個(gè)過程，如圖1所示[1].從圖1中可以看到，特征選擇過程由四步組成:子集產(chǎn)生、子集評(píng)價(jià)、終止和驗(yàn)證方法.第一步為產(chǎn)生子集，即由一部分特征組成的集合，接著對(duì)這個(gè)特征集進(jìn)行評(píng)估，直到停止的條件滿足，選擇的過程才結(jié)束.如果沒有條件未滿足，則重復(fù)前面的工作，直到完成.目前學(xué)者們的研究集中于搜索策略和評(píng)價(jià)標(biāo)準(zhǔn)兩方面.

圖1 一般特征選擇框架圖

特征選擇的任務(wù)，實(shí)際上是將特征的維數(shù)從M 壓縮至對(duì)于描述類別是最有效的m 維，這樣，所有的可能的特征集的組合數(shù)為

選擇哪些特征組成最優(yōu)特征子集需要一個(gè)標(biāo)準(zhǔn)進(jìn)行評(píng)價(jià).這些標(biāo)準(zhǔn)可以分為以下五類:信息相關(guān)的度量、距離相關(guān)的度量、依賴性相關(guān)的度量、一致性相關(guān)的度量和分類錯(cuò)誤相關(guān)的度量等[1].前四類方法根據(jù)數(shù)據(jù)內(nèi)在的特性來對(duì)所選擇的特征子集進(jìn)行評(píng)價(jià)，獨(dú)立于特定的算法，常用于過濾模式(filter method)的方法中;分類錯(cuò)誤率度量標(biāo)準(zhǔn)則經(jīng)常與特定的學(xué)習(xí)算法聯(lián)系，常用于封裝模式(wrapper method)的方法中[2].不同的評(píng)價(jià)標(biāo)準(zhǔn)會(huì)得到不同的特征子集.另外，使用窮舉法，對(duì)所有的可能的特征組合進(jìn)行評(píng)估，計(jì)算量會(huì)非常大，也是不實(shí)際的.所以，尋找一種理想的搜索算法變得非常必要.根據(jù)能否搜索到最優(yōu)組合，搜索算法可以分為最優(yōu)搜索算法、次優(yōu)搜索算法.到目前為止，唯一可以得到最優(yōu)結(jié)果的搜索方法就是分支界定法[3].雖然分支界定法在效率上比窮舉法高，但是對(duì)于高維度特征空間，計(jì)算量還是太大而難以實(shí)現(xiàn).單獨(dú)最優(yōu)特征組合是最簡(jiǎn)單的搜索算法，但是，即使各特征統(tǒng)計(jì)獨(dú)立，組合起來不一定最優(yōu).后來出現(xiàn)的搜索算法有順序前進(jìn)法 (Sequential Forward Selection，SFS)[4]和順序后退法 (Sequential Backward Selection，SBS)[5].SFS 沒有考慮入選特征之間的相關(guān)性，而且不能剔除已入選而品質(zhì)變低劣的特征.而SBS 則無法入選已被剔除而品質(zhì)變優(yōu)良的特征，且由于其是一種自上而下的方法，在高維空間運(yùn)算，計(jì)算量比SFS 大.由于特征選擇實(shí)際上是一個(gè)組合優(yōu)化問題，因此也可以使用解決優(yōu)化問題的方法來解決特征選擇問題，比如基于啟發(fā)式搜索策略的禁忌搜索(Tabu Search，TS)算法[6]，基于隨機(jī)搜索策略的粒子群算法(Particle Swarm Optimization，PSO)[7]、模擬退火算法(Simulated Annealing)[6]和遺傳算法 (genetic algorithm，GA)[8]等.這些方法都是近似方法，在求解時(shí)間和質(zhì)量上都較為理想，被廣泛應(yīng)用.

根據(jù)分類器與評(píng)價(jià)函數(shù)的關(guān)系，特征選擇的模式目前可以分為過濾式、封裝式以及混合(Hybird)模式[2].基于過濾式的方法獨(dú)立于分類器，其方法是使用一定的函數(shù)，對(duì)于候選的部分特征進(jìn)行分類能力的評(píng)估，同時(shí)用某種策略從中選擇最好的一些特征.這種方法實(shí)現(xiàn)簡(jiǎn)單，效率高，但是由于獨(dú)立于分類器，容易和分類器產(chǎn)生偏差.基于封裝式的方法則將分類器封裝于其中，直接以分類的正確率作為特征選擇的目標(biāo)，分類正確率最高的那一部分特征將被作為最后的特征集被選中.在這種方法中，分類學(xué)習(xí)算法就封裝在特征選擇過程里面，分類算法的識(shí)別正確率直接成為了特征子集的評(píng)價(jià)準(zhǔn)則，所以其精度一般較過濾模式方法高，但是每次對(duì)特征子集的評(píng)價(jià)都要計(jì)算分類器的精度，所以其效率不高.目前一些學(xué)者結(jié)合這兩類方法的優(yōu)點(diǎn)，把兩者結(jié)合起來形成了一類混合模式的方法，也取得了較好的效果[9].

遺傳算法由生物進(jìn)化的過程啟發(fā)而產(chǎn)生.生物從最簡(jiǎn)單的低等生物發(fā)展出復(fù)雜的高級(jí)生物，期間經(jīng)歷了漫長(zhǎng)的進(jìn)化，通過遺傳和變異等，按照“物競(jìng)天擇，適者生存”的規(guī)則演變而來.遺傳算法對(duì)求解問題的模型，沒有特別的要求，是一種非數(shù)值優(yōu)化方法，所以適應(yīng)性比較廣泛.其次，在搜索時(shí)，遺傳算法采用群體搜索策略，從一個(gè)群體進(jìn)化到另外一個(gè)群體，提高了效率，且不易陷入局部最優(yōu).這些優(yōu)點(diǎn)，讓遺傳算法被廣泛應(yīng)用于特征選擇中.

2 基于遺傳算法的特征選擇和權(quán)重確定方法

遺傳算法是一種基于封裝模式的特征選擇方法.這種方法把分類器封裝于其中，直接以分類器的精度作為評(píng)價(jià)特征子集的選擇標(biāo)準(zhǔn).由于每次需要計(jì)算分類器精度，所以效率不是很高.另外，也沒有考慮到特征的權(quán)重，事實(shí)上每個(gè)特征對(duì)于分類的貢獻(xiàn)不是同等的.所以，我們提出了一種基于遺傳算法的特征選擇和權(quán)重確定方法.這種方法的過程如下圖2所示.

圖2 基于遺傳算法特征選擇和權(quán)重確定方法示意圖

這種方法主要分為以下兩步進(jìn)行.

第一步:由傳統(tǒng)的GA 算法初選出候選特征集.

這一步主要是從原始特征集中選出比較好的一些初始特征集，用于后續(xù)的精選和權(quán)重確定.使用二進(jìn)制位編碼的方法創(chuàng)建一個(gè)二進(jìn)制位串代表一個(gè)染色體C.一個(gè)特征fi使用一個(gè)二進(jìn)制位，也就是一個(gè)基因位gi來表示，則有下面一個(gè)關(guān)于fi和gi函數(shù)關(guān)系:

從式2 中，我們可以看到基因位和特征一一對(duì)應(yīng)，有多少特征就需要有多少基因位來表示.當(dāng)基因取值為1 時(shí)，表明特征被選中，反之則反.第一步流程圖如圖3所示.

第二步:由可以確定權(quán)重的GA 算法在第一階段初選出候選特征集的基礎(chǔ)上，繼續(xù)精簡(jiǎn)特征集，同時(shí)也求得最終入選的特征對(duì)應(yīng)的權(quán)重.可以確定特征權(quán)重的GA 與傳統(tǒng)GA 方法的流程大致相同，我們介紹與GA 中不同的幾個(gè)地方，主要是個(gè)體編碼方式、解碼方式和交叉遺傳操作.

(1)個(gè)體編碼方式

如表1所示，在GA 中，我們用x位二進(jìn)制位表示一個(gè)特征的權(quán)重，這樣，如果由第一階段GA 選出來的候選特征集的位數(shù)為n位，則特征權(quán)重位的位數(shù)為nx，即整個(gè)染色體的長(zhǎng)度.

表1 在確定權(quán)重的GA 算法染色體中個(gè)體的二進(jìn)制位編碼

(2)染色體解碼

因?yàn)榇_定權(quán)重GA 算法中染色體的編碼與傳統(tǒng)GA中不同，相應(yīng)的解碼方式也不同，先將每一個(gè)特征fi對(duì)應(yīng)的二進(jìn)制基因位串轉(zhuǎn)化為一個(gè)十進(jìn)制整數(shù)qi，然后，就可以求得每個(gè)特征的權(quán)重:

圖3 應(yīng)用GA 進(jìn)行候選特征子集選擇流程圖

(3)交叉遺傳操作

由于在第二步的GA 中，基因的編碼方式與傳統(tǒng)GA 不同，我們使用了x位表示一個(gè)權(quán)重位，為了在進(jìn)行交叉操作后，盡量不會(huì)因?yàn)榻徊媸沟靡粋€(gè)特征的權(quán)重被嚴(yán)重改變，我們?cè)谶M(jìn)行交叉操作時(shí)，交叉點(diǎn)選擇為n的整數(shù)位處，也是隨機(jī)選擇，但是不處于這一點(diǎn)時(shí)就重新再選擇，直到滿足這個(gè)條件位置為止，這與在GA 中采用的傳統(tǒng)的方法那樣完全隨機(jī)選擇交叉點(diǎn)不同.

通過上述的兩個(gè)步驟，我們就可以得到一個(gè)精選的特征子集及其對(duì)應(yīng)的權(quán)重.

3 實(shí)驗(yàn)及結(jié)果

為了驗(yàn)證所提算法的效果，開展了以下一系列的實(shí)驗(yàn).

3.1 數(shù)據(jù)來源和實(shí)驗(yàn)方案

實(shí)驗(yàn)的數(shù)據(jù)來源于南佛羅里達(dá)大學(xué)(University of South Florida)的DDSM (Digital Database for Screening Mammography，DDSM)[10].我們構(gòu)建了一個(gè)基于鉬靶乳腺X 線攝片和多特征最近鄰算法[11]的乳腺腫塊計(jì)算機(jī)輔助診斷系統(tǒng).在訓(xùn)練階段，先建立一個(gè)大規(guī)模參考庫(kù)，主要由含有正常組織的感興趣區(qū)域(Region of Interest，ROI)和含有腫塊的ROI 兩類區(qū)域組成.隨后使用分割算法對(duì)參考庫(kù)中的所有ROI 進(jìn)行可疑腫塊輪廓提取.當(dāng)分割完成后，在分割結(jié)果上應(yīng)用特征提取和計(jì)算方法計(jì)算所有ROI的特征集.這樣就得到了參考ROI 特征數(shù)據(jù)庫(kù).在整個(gè)特征數(shù)據(jù)庫(kù)上，使用特征選擇、權(quán)重確定算法及分類決策算法，并引入已經(jīng)確診的金標(biāo)準(zhǔn)(Truth File)對(duì)上述結(jié)果進(jìn)行判定.分割算法我們使用的是一種基于動(dòng)態(tài)規(guī)劃法的方法[11].在診斷階段，使用基于圖像內(nèi)容檢索 (Computer Aided Diagnose using Content-based Image Retrieval，CBIR CAD)方法，針對(duì)放射科醫(yī)師任意感興趣的區(qū)域去進(jìn)行檢測(cè)，CAD 系統(tǒng)除了返回待查詢的區(qū)域和腫塊的相似度分?jǐn)?shù)和/或腫塊是良性還是惡性的分類分?jǐn)?shù)，還有最相似的K 幅參考感興趣區(qū)域圖像.

3.2 參數(shù)設(shè)置

(1)種群規(guī)模和個(gè)體初始化時(shí)閾值

種群的大小用來控制種群的規(guī)模.顯然，種群規(guī)模越大，相當(dāng)于增大了搜索的群體以及種群多樣性，找到理想解的可能性就越大，但是計(jì)算量肯定會(huì)增大.本文中種群大小設(shè)置為40.

(2)進(jìn)化代數(shù)

進(jìn)化代數(shù)用來控制遺傳算法的結(jié)束時(shí)間.一般來說，代數(shù)越多，越可能找到理想解，但搜索時(shí)間會(huì)增加.在本文中，這個(gè)值設(shè)置為300.

(3)交叉概率

交叉概率用于控制參與交叉的個(gè)體數(shù)量，這個(gè)值不宜過小，也不宜過大.過小的話，則會(huì)使得算法收斂速度過快而陷入局部最優(yōu)，過大則會(huì)使大量?jī)?yōu)秀個(gè)體遭到破壞，而使算法不收斂.在本文中設(shè)置為0.7.

(4)變異概率

變異概率用來控制參與變異的個(gè)體數(shù)量.它的影響主要是在進(jìn)化的后期，和交叉概率的作用類似.在本文中，設(shè)置為0.001.

3.3 實(shí)驗(yàn)結(jié)果

為了測(cè)試和評(píng)估所提出的新特征和新的特征選擇方法的效果，我們對(duì)7種方法進(jìn)行了實(shí)驗(yàn).這些方法中，有使用所有特征且權(quán)重都為1的AF-KNN 方法和GA-KNN 方法以及本文方法.實(shí)驗(yàn)結(jié)果如表2所示，表中K值為KNN 算法所選出的與待測(cè)ROI 最相似的參考ROI的數(shù)目.在本文實(shí)驗(yàn)中，是在遺傳算法的染色體中設(shè)定相應(yīng)的基因位，一起訓(xùn)練出來的.95%置信區(qū)間是本文實(shí)驗(yàn)結(jié)果要求達(dá)到的95%可信度所跨度的范圍.受試者操作特性曲線 (Receiver Operating Characteristic Curve，ROC 曲線)[12]是廣泛采用的評(píng)價(jià)CAD 系統(tǒng)性能的工具，有別于單閾值分析的方法，通過設(shè)置很多閾值進(jìn)行決策，可以獲取到含有多對(duì)靈敏度和假陽(yáng)性率值組成相應(yīng)的二元有序點(diǎn)對(duì)集合，再分別以假陽(yáng)性率、靈敏度值為橫、縱坐標(biāo)，既可以通過二維坐標(biāo)系，在二維空間中描述這些點(diǎn)，連接這些點(diǎn)而成的曲線就是ROC 曲線.Az為ROC 曲線下包絡(luò)的面積，是描述受試者操作特性曲線最重要的指標(biāo)，該值越大，表明系統(tǒng)性能越好.

表2 各種方法的實(shí)驗(yàn)結(jié)果

從表2中可以發(fā)現(xiàn)由傳統(tǒng)的GA 方法選出了34個(gè)特征作為候選特征子集，對(duì)63 維特征進(jìn)行了初步降維，然后本文方法在這個(gè)基礎(chǔ)上最終選出了24個(gè)特征，并確定了特征相應(yīng)的權(quán)重.在臨床中，一般認(rèn)為Az值:0.5～0.7之間時(shí)診斷價(jià)值較低，在0.7～0.9之間時(shí)診斷價(jià)值中等，而在0.9 以上時(shí)診斷價(jià)值較高.本文的方法，全特征法以及GA 特征選擇方法得到的Az 下的面 積 分 別為:0.8782 ± 0.0078，0.8632 ±0.0081和0.8478 ±0.0088，從數(shù)據(jù)上看，進(jìn)行GA 特征選擇后，入選特征為34個(gè)，特征維數(shù)明顯降低，而CAD 性能也明顯提高，說明特征選擇對(duì)分類器性能的提高有很重要的作用.而且用本文所提出的方法特征數(shù)進(jìn)一步降為24個(gè)，CAD的性能卻比前面的兩種方法有更大的提升，說明本文所提方法行之有效.

4 結(jié)論

特征選擇是模式識(shí)別中非常關(guān)鍵的一步，挑選出最優(yōu)特征子集的同時(shí)還能降低特征維度，提高計(jì)算效率.很多算法在進(jìn)行特征選擇的時(shí)候沒有考慮到特征的權(quán)重，簡(jiǎn)單的將特征的分類效力同等對(duì)待，這是不合理的.本文提出了一種兩步選擇特征的方案，先用遺傳算法初選出一個(gè)特征子集，在此基礎(chǔ)上再用能夠確定特征的遺傳算法進(jìn)一步精選特征，并確定特征的權(quán)重.實(shí)驗(yàn)結(jié)果顯示，我們的算法取得了較好效果.

[1]Dash M，Liu H.Feature selection for classification[J].Intelligent data analysis，1997，1 (3):131-156.

[2]鄭雅敏.基于遺傳算法的特征選擇方法的改進(jìn)研究[D].重慶:重慶大學(xué)通信工程學(xué)院，2008.

[3]劉亦韜，胡維華.一種處理Top-k 逆向查詢的分支界定算法[J].杭州電子科技大學(xué)學(xué)報(bào)，2014 (6):76-79.

[4]Liu B，Li S，Wang Y，et al.Predicting the protein SUMO modification sites based on Properties Sequential Forward Selection (PSFS)[J].Biochemical and biophysical research communications，2007，358 (1):136-139.

[5]Xue B，Zhang M，Browne W N.Particle swarm optimisation for feature selection in classification:Novel initialisation and updating mechanisms[J].Applied Soft Computing，2014 (18):261-276.

[6]許鵬飛，苗啟廣，李偉生.基于函數(shù)復(fù)雜度的自適應(yīng)模擬退火和禁忌搜索新算法[J].電子學(xué)報(bào)，2012，40(6):1218-1222.

[7]張丹，韓勝菊，李建，等.基于改進(jìn)粒子群算法的BP算法的研究[J].計(jì)算機(jī)仿真，2011，28 (2):147-150.

[8]Handbook of genetic algorithms[M].New York:Van Nostrand Reinhold，1991:20-65.

[9]Fischer U，Hermann K，Baum F.Digital mammography:current state and future aspects[J].European radiology，2006，16 (1):38-44.

[10]Keller J M，Gray M R，Givens J A.A fuzzy k-nearest neighbor algorithm[J].IEEE Transactions on Systems，Man and Cybernetics，1985 (4):580-585.

[11]Song E，Xu S，Xu X，et al.Hybrid segmentation of mass in mammograms using template matching and dynamic programming[J].Academic radiology，2010，17 (11):1414-1424.

[12]Eltonsy N H，Tourassi G D，Elmaghraby A S.A concentric morphology model for the detection of masses in mammography[J].IEEE Transactions on Medical Imaging，2007，26 (6):880-889.