一種基于遺傳算法的特征選擇和權重確定方法

(淮北師范大學 計算機科學與技術學院，安徽 淮北 235000)

特征選擇，是從一個初始特征集中挑選出一些特征組成最優特征子集，依據這些子集構建的分類器能夠使某種評估標準達到最優，具有較高的預測精度.特征選擇可以提高構建的分類或回歸模型的泛化能力，降低特征維度的同時還提高了計算效率，所以特征選擇方法的研究成為目前模式識別研究領域中的一個熱點問題.

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

1 特征選擇的相關工作

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

圖1 一般特征選擇框架圖

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

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

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

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

2 基于遺傳算法的特征選擇和權重確定方法

遺傳算法是一種基于封裝模式的特征選擇方法.這種方法把分類器封裝于其中，直接以分類器的精度作為評價特征子集的選擇標準.由于每次需要計算分類器精度，所以效率不是很高.另外，也沒有考慮到特征的權重，事實上每個特征對于分類的貢獻不是同等的.所以，我們提出了一種基于遺傳算法的特征選擇和權重確定方法.這種方法的過程如下圖2所示.

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

這種方法主要分為以下兩步進行.

第一步:由傳統的GA 算法初選出候選特征集.

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

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

第二步:由可以確定權重的GA 算法在第一階段初選出候選特征集的基礎上，繼續精簡特征集，同時也求得最終入選的特征對應的權重.可以確定特征權重的GA 與傳統GA 方法的流程大致相同，我們介紹與GA 中不同的幾個地方，主要是個體編碼方式、解碼方式和交叉遺傳操作.

(1)個體編碼方式

如表1所示，在GA 中，我們用x位二進制位表示一個特征的權重，這樣，如果由第一階段GA 選出來的候選特征集的位數為n位，則特征權重位的位數為nx，即整個染色體的長度.

表1 在確定權重的GA 算法染色體中個體的二進制位編碼

(2)染色體解碼

因為確定權重GA 算法中染色體的編碼與傳統GA中不同，相應的解碼方式也不同，先將每一個特征fi對應的二進制基因位串轉化為一個十進制整數qi，然后，就可以求得每個特征的權重:

圖3 應用GA 進行候選特征子集選擇流程圖

(3)交叉遺傳操作

由于在第二步的GA 中，基因的編碼方式與傳統GA 不同，我們使用了x位表示一個權重位，為了在進行交叉操作后，盡量不會因為交叉使得一個特征的權重被嚴重改變，我們在進行交叉操作時，交叉點選擇為n的整數位處，也是隨機選擇，但是不處于這一點時就重新再選擇，直到滿足這個條件位置為止，這與在GA 中采用的傳統的方法那樣完全隨機選擇交叉點不同.

通過上述的兩個步驟，我們就可以得到一個精選的特征子集及其對應的權重.

3 實驗及結果

為了驗證所提算法的效果，開展了以下一系列的實驗.

3.1 數據來源和實驗方案

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

3.2 參數設置

(1)種群規模和個體初始化時閾值

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

(2)進化代數

進化代數用來控制遺傳算法的結束時間.一般來說，代數越多，越可能找到理想解，但搜索時間會增加.在本文中，這個值設置為300.

(3)交叉概率

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

(4)變異概率

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

3.3 實驗結果

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

表2 各種方法的實驗結果

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

4 結論

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

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

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

[3]劉亦韜，胡維華.一種處理Top-k 逆向查詢的分支界定算法[J].杭州電子科技大學學報，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]許鵬飛，苗啟廣，李偉生.基于函數復雜度的自適應模擬退火和禁忌搜索新算法[J].電子學報，2012，40(6):1218-1222.

[7]張丹，韓勝菊，李建，等.基于改進粒子群算法的BP算法的研究[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.