陳俊穎，陸慧娟，嚴 珂，葉敏超

(中國計量大學 信息工程學院，浙江 杭州 310018)

ReliefF和APSO混合降維算法研究

陳俊穎，陸慧娟，嚴 珂，葉敏超

(中國計量大學 信息工程學院，浙江 杭州 310018)

降維與分類一直是機器學習的研究熱點，在很多領(lǐng)域有著成功的應用.針對基因數(shù)據(jù)分類存在特征維數(shù)過高、冗余數(shù)據(jù)和高噪聲等問題，現(xiàn)提出一種基于ReliefF和自適應粒子群(APSO)優(yōu)化的混合降維算法.即先通過ReliefF和APSO算法選擇特征子集，然后使用超限學習機作為評價函數(shù)對基因數(shù)據(jù)進行分類，最后通過循環(huán)迭代得到最優(yōu)的分類精度.實驗證明，混合降維算法與已有的算法相比分類精度更高、更穩(wěn)定，它適用于基因表達數(shù)據(jù)降維.

ReliefF算法；APSO算法；降維；基因表達數(shù)據(jù)

隨著生物信息學的發(fā)展，發(fā)現(xiàn)了一種可以對癌癥進行診斷的技術(shù)，定義為DNA微陣列技術(shù)[1-2].在對基因表達數(shù)據(jù)分類的研究中，發(fā)現(xiàn)基因表達數(shù)據(jù)具有維數(shù)高、小樣本和非線性等特點[3]，而如何獲得較高的分類精度、穩(wěn)定的泛化性能、降低時間復雜度，成為當前基因表達數(shù)據(jù)分析的研究重點.對樣本數(shù)據(jù)的篩選、特征選擇、特征提取、分類等都是當今數(shù)據(jù)挖掘和機器學習中的研究熱點.通過對基因表達數(shù)據(jù)的挖掘和學習，人們能夠清楚的了解差異基因的功能和對其進行干預而引起的結(jié)果，并最終將獲得的信息作為診斷和治療的依據(jù).如今對于基因表達數(shù)據(jù)分類[4]，主要體現(xiàn)在降維、分類精度以及分類器的穩(wěn)定性上.

最新的降維方法提出了MRMD(maximum relevance maximum distance),即最大相關(guān)最大距離.MRMD選擇出和類標具有強相關(guān)并且特征之間具有低冗余的特征子集，主要有兩部分組成的：一是特征與數(shù)據(jù)類標之間的相關(guān)性，用Pearson相關(guān)系數(shù)來計算特征和類標之間的相關(guān)性；二是特征之間的冗余性，用三種距離函數(shù)(Euclidean距離、Cosine距離和Tanimoto系數(shù))和的平均值來計算特征之間的冗余性.而本文的ReliefF算法考慮了特征與數(shù)據(jù)類標之間的相關(guān)性.

Relief算法作為一個高效的特征選擇方法，吳艷文[5]等人，分析Relief算法及其在聚類應用中存在的問題，提出了一種基于Relief算法的特征評價函數(shù)，以解決特征權(quán)值取值不當對聚類產(chǎn)生的負面影響.張翔[6]等人為了提高Relief特征加權(quán)的適應性和魯棒性，融合間距最大化和極大熵理論，構(gòu)造了一個結(jié)合極大熵原理的間距最大化目標函數(shù)，提出了一組魯棒的Relief特征加權(quán)算法.吳紅霞[7]等人，提出基于Relief和SVM-RFE的組合式SNP特征選擇方法.Relief雖然應用廣泛，但是只能處理兩類的數(shù)據(jù)，因此1994年Kononeill對其進行了擴展，得到了ReliefF算法.ReliefF算法可以處理多類別問題，能夠處理目標屬性為連續(xù)值的回歸問題.從目前的文獻來看，對ReliefF算法還有很多值得進一步研究的空間.

粒子群算法，也稱粒子群優(yōu)化算法，是近年來由J.Kennedy和R.C.Eberhart等[8]研究開發(fā)的一種新型進化算法.在對生物群體觀察和研究的基礎上，通過群體中每個個體共享群體信息，逐漸完善自身行為軌跡的尋優(yōu)過程，最終得到最優(yōu)解.P Ghamisi[9]等人，通過將遺傳算法(genetic algorithm，GA)和PSO算法進行混合交叉迭代，提出了一種HGAPSO-Selection算法.涂娟娟[10]等人，發(fā)現(xiàn)現(xiàn)有的PSO算法在迭代的過程中粒子群的多樣性會逐漸缺失，提出了一種改進的分期變異PSO算法，早期對粒子群進行變異，后期對個體極值和全局極值進行隨機擾動，優(yōu)化神經(jīng)網(wǎng)絡參數(shù)及結(jié)構(gòu)，始終保持粒子群的多樣性.PSO特征提取算法由于算法簡單、易于實現(xiàn)、參數(shù)少、收斂速度快等優(yōu)點在連續(xù)優(yōu)化問題和離散優(yōu)化問題中都表現(xiàn)出良好的效果，但其在全局搜索時容易陷入局部最優(yōu)解而導致早熟收斂、收斂速度慢等問題.

Relief系列算法通過計算權(quán)重來進行特征選擇運行速度快，且不限制數(shù)據(jù)的類型.粒子群算法能夠快速地尋找最優(yōu)的過程，還能對系統(tǒng)的參數(shù)進行優(yōu)化改進.ReliefF是特征選擇算法，需要丟棄一些基因，這樣將會丟失一部分有用的信息，而PSO算法是特征提取算法，會浪費資源在冗余和噪聲基因上.然而，APSO可以提高搜索能力得到更優(yōu)的解決方案，平衡算法的全局與局部搜索能力，從而提高了算法的多樣性與搜索效率[11].

綜上所述，本文提出了一種基于ReliefF和APSO的混合降維算法.

1 ReliefF算法

ReliefF算法的核心思想就是特征和數(shù)據(jù)集類標之間的相關(guān)性.ReliefF算法從訓練集中隨機選擇一個樣本R.先找出與R屬于同一類且離它最近的樣本稱為NearHit，然后再找出與R屬于不同類且離它最近的樣本稱為NearMiss，根據(jù)以下算法得到權(quán)重：

4) 重復以上過程m次，得到每個特征的平均權(quán)重.其計算公式如下：

W(A)=W(A)-diff(A,R,H)/m+

diff(A,R,M)/m.

(1)

其中diff(A,R,H)表示樣本R和它的同類NearHit在特征A上的差.

重復m次以后，每個特征都得到一個平均權(quán)重，平均權(quán)重越大，則代表該特征能更好的區(qū)分不同類別，而平均權(quán)重越小，則代表該特征不能很好的區(qū)分不同類別.ReliefF算法的復雜度隨著樣本抽樣次數(shù)m和原始特征集個數(shù)N的增加而線性增加，所以運行的速度快.Relief系列算法運行速度快，對數(shù)據(jù)類型沒有限制，會給予所有類別相關(guān)性高的特征較高的權(quán)重，所以屬于一種特征權(quán)重算法.

2 APSO算法

粒子群算法，是一種從飛鳥集群捕食行為的研究中發(fā)現(xiàn)的.群體中每個個體共享群體信息，逐漸完善自身行為軌跡的尋優(yōu)過程，最終得到最優(yōu)解.是一種基于迭代的優(yōu)化算法.

PSO算法初始化一群隨機粒子(隨機解).根據(jù)粒子的速度和位置的更新公式，不斷進行迭代尋找個體最優(yōu)解和歷史最優(yōu)解.在每一次的迭代過程中，每個粒子通過跟蹤兩個“極值”(pbest，gbest)來更新自己的位置和速度.

(2)

(3)

其中w為權(quán)值，V是粒子的速度，X是粒子的位置，c1和c2是學習因子，通常取c1=c2=2.粒子群算法的本質(zhì)就是群體共享信息來幫助粒子移動到下一個迭代位置，直至找到最優(yōu)解.個體充分利用自身信息和以及群體共享的信息來調(diào)整自己的位置是粒子群算法的關(guān)鍵所在.

由于PSO算法在處理多極值函數(shù)問題上經(jīng)常出現(xiàn)早熟收斂等問題，為增加粒子跳出局部極值的能力，本文提出APSO算法在速度更新時加入慣性系數(shù)，變化后的公式如下：

(4)

(5)

式(5)中ωmax，ωmin分別為最大、最小慣性系數(shù)，Kmax為最大迭代次數(shù),τ為經(jīng)驗值，一般在[20,55]內(nèi)取值.較大的ω令APSO具有較強的全局搜索能力，ω較小則更傾向于局部搜索.慣性系數(shù)在初期的時候一般較大，隨著算法的迭代次數(shù)增加而逐漸減少.通過改變慣性系數(shù)的大小，達到不同的搜索效果.隨著慣性系數(shù)的逐漸減小，算法也由初期的全局搜索到后期的局部搜索.

3 基于ReliefF和APSO的混合降維算法

首先隨機產(chǎn)生一個含有N個粒子的粒子群，然后使用ELM分類器作為評價函數(shù)，得到適應度后進行ReliefF-APSO混合降維處理，不斷迭代最終得到特征子集和最優(yōu)的分類精度.本文將其應用于基因數(shù)據(jù)分類中，通過與其他特征選擇方法進行對比，驗證該方法的有效性.圖1是ReliefF和APSO混合降維算法的框架圖.

圖1 ReliefF和APSO混合降維算法框架圖Figure 1 Frame chart of the hybrid dimensionality reduction algorithm base on ReliefF and APSO

ReliefF和APSO混合降維算法步驟如下：

Step 1：給定數(shù)據(jù)集，在訓練前，對數(shù)據(jù)進行0均值歸一化處理.

Step 2：使用公式(1)進行ReliefF算法特征提取，取權(quán)值相對較大的前k個特征作為APSO的訓練集和測試集.實驗中k取100.

Step 3：建立基于APSO的極限學習機神經(jīng)網(wǎng)絡拓撲結(jié)構(gòu)，設置隱層神經(jīng)元數(shù)目，選擇sigmoid作為激活函數(shù).

Step 4：產(chǎn)生種群，設置粒子數(shù)N，每個粒子設置為[-1,1]范圍內(nèi)的隨機數(shù)向量，設置神經(jīng)元個數(shù)及隱層節(jié)點數(shù).實驗中N取20個.

Step 5：初始化APSO的速度與位置變量，設置種群的個體最優(yōu)位置、群體最優(yōu)位置.

Step 6：計算每個粒子的適應度值.

Step 7：根據(jù)式(4)、(5)更新自適應粒子群的位置和速度.

Step 8：判斷是否達到最大迭代次數(shù)，若達到，則停止迭代，否則轉(zhuǎn)step6，繼續(xù)迭代.

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集

使用的數(shù)據(jù)集是UCI上的基因數(shù)據(jù)集，如表1.

表1 數(shù)據(jù)集樣本數(shù)

4.2 預處理(歸一化)

因為不同的數(shù)據(jù)在不同維度上數(shù)據(jù)的數(shù)量級相差過大的話，數(shù)值大的數(shù)的變化會忽略掉數(shù)值小的數(shù)的變化.其次是歸一化之后收斂速度快.在分類算法中，需要使用距離來度量相似性的時候，使用0均值標準化會更好.0均值歸一化是將原始數(shù)據(jù)集歸一化為均值為0、方差為1的數(shù)據(jù)集，歸一化公式如下：

(6)

其中μ，σ2分別為原始數(shù)據(jù)集的均值和方差.

4.3 實驗分析

使用ReliefF和APSO混合降維算法對樣本數(shù)據(jù)進行分類，通過與單一的APSO、單一的ReliefF、GA算法比較分類精度來評價本文降維方法的優(yōu)劣.ReliefF和APSO混合降維算法簡稱為ReliefF-APSO算法.在Breast，Colon和Leukemia 3個基因表達數(shù)據(jù)集上進行實驗，得到的分類精度如表2，圖2～4.

表2 不同基因表達數(shù)據(jù)集下各算法的分類精度

圖2 Breast數(shù)據(jù)集下各算法分類精度Figure 2 Classification accuracy on Breast dataset

圖3 Colon數(shù)據(jù)集下各算法分類精度Figure 3 Classification accuracy on Colon dataset

由圖2、圖3、圖4可知，在基因數(shù)據(jù)集上，單一的ReliefF算法隨著迭代次數(shù)增加，分類精度一直處于上下波動的狀態(tài)，極不穩(wěn)定.而用ReliefF-APSO、APSO、GA算法使用ELM算法進行分類，算法的分類精度不再上下波動.并且隨著迭代次數(shù)增加，算法的分類精度穩(wěn)步上升.本文提出的ReliefF-APSO算法在Breast、Colon、Leukemia數(shù)據(jù)集上都體現(xiàn)了良好的分類精度，且具有良好的穩(wěn)定性.這說明ReliefF-APSO算法是一種有效的降維算法.

5 結(jié) 語

采用ReliefF-APSO算法，先通過ReliefF算法進行特征選擇，選取含有信息更多的特征，然后利用APSO再進行特征提取.本算法能夠快速的縮小全局搜索范圍，具有平衡了算法的全局與局部搜索能力，同時提高了算法的多樣性與搜索效率，減小了算法陷入局部最優(yōu)的可能.通過與已有類似算法在不同數(shù)據(jù)集上進行分類對比實驗，表明本文提出的方法具有更好的分類性能，在基因數(shù)據(jù)降維等領(lǐng)域有較好的應用前景，可以做進一步深入研究.

[1] BRAZMA A, VILO J. Gene expression data analysis [J]. Microbes & Infection,2000,480(1):17-24.

[2] SHERLOCK G. Analysis of large-scale gene expression data [J]. Current Opinion in Immunology,2000,12(2):201-205.

[3] HELLER M J. DNA Microarray Technology: Devices, Systems, and Applications [J]. Annual Review of Biomedical Engineering,2002,4(1):129-153.

[4] 陸慧娟.基于基因表達數(shù)據(jù)的腫瘤分類算法研究[D].徐州:中國礦業(yè)大學,2012. LU H J. A Study of Tumor Classification Algorithms Using Gene Expression Data[D]. Xuzhou: China University of Mining and Technology,2012

[5] 吳艷文,胡學鋼,陳效軍.基于Relief算法的特征學習聚類[J].合肥學院學報(自然科學版),2008,18(2):45-48. WU Y W, Hu X, CHEN X J. Feature learning clustering based on Relief algorithm[J]. Journal of Hefei University(Natural Science Edition),2008,18(2):45-48.

[6] 張翔,鄧趙紅,王士同,等.極大熵Relief特征加權(quán)[J].計算機研究與發(fā)展,2011,48(6):1038-1048. ZHANG X, DENG Z H,WANG S T, et al. Maximum entropy Relief feature weighting[J]. Journal of Computer Research and Development,2011,48(6):1038-1048.

[7] 吳紅霞,吳悅,劉宗田,等.基于Relief和SVM-RFE的組合式SNP特征選擇[J].計算機應用研究,2012,29(6):2074-2077. WU H X, WU Y, LIU Z T, et al. Combined SNP feature selection based on relief and SVM-RFE[J]. Application Research of Computers,2012,29(6):2074-2077.

[8] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE,1995:1942-1948.

[9] GHAMISI P, BENEDIKTSSON J A. Feature selection based on hybridization of genetic algorithm and particle swarm optimization [J]. IEEE Geoscience & Remote Sensing Letters,2015,12(2):309-313.

[10] 涂娟娟. PSO優(yōu)化神經(jīng)網(wǎng)絡算法的研究及其應用[D]. 鎮(zhèn)江: 江蘇大學,2013. TU J J. Research on Learning Algorithm of Neural Network Optimized with PSO and its Application[D]. Zhenjiang: Jiangsu University,2013.

[11] 陳曉青,陸慧娟,鄭文斌,等. 自適應混沌粒子群算法對極限學習機參數(shù)的優(yōu)化[J]. 計算機應用,2016,36(11):3123-3126. CHEN X Q, LU H J, ZHENG W B, et al. Optimization of extreme learning machine parameters by adaptive chaotic particle swarm optimization algorithm[J]. Journal of Computer Applications,2016,36(11):3123-3126.

A hybrid dimension reduction algorithm on ReliefF and APSO

CHEN Junying, LU Huijuan, YAN Ke, YE Minchao

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

Dimensionality reduction and classification are two hot topics in the field of machine learning.We proposed a hybrid feature selection algorithm combining ReliefF and adaptive particle swarm optimization (APSO) for gene data classification, solving the problems of high dimension, redundancy as well as noise. The algorithm extracted the feature subsets by using ReliefF and APSO. The extreme learning machine was used as the evaluation function to classify the gene expression data. The optimized classification accuracy was obtained by recursive substitutions. Experiments show that the proposed hybrid dimensionality reduction algorithm contributes to higher classification accuracy and is more stable than existing algorithms. Consequently, it is an appropriate method for the dimensionality reduction of gene expression data.

ReleifF algorithm; APSO algorithm; dimensionality reduction; gene expression data

2096-2835(2017)02-0214-05

10.3969/j.issn.2096-2835.2017.02.013

2017-03-17 《中國計量大學學報》網(wǎng)址：zgjl.cbpt.cnki.net

國家自然科學基金資助項目(No. 61272315，61602431)， 浙江省科技廳國際合作專項(No.2017C34003).

陳俊穎(1992-)，男，浙江省杭州人，碩士研究生，主要研究方向為機器學習．E-mail:1820574626@qq.com 通信聯(lián)系人：陸慧娟，女，教授．E-mail：hjlu@cjlu.edu.cn

TP391

A