陳俊穎，陸慧娟，嚴(yán) 珂，葉敏超

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

ReliefF和APSO混合降維算法研究

陳俊穎，陸慧娟，嚴(yán) 珂，葉敏超

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

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

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

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

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

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

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

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

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

1 ReliefF算法

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

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

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

diff(A,R,M)/m.

(1)

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

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

2 APSO算法

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

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

(2)

(3)

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

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

(4)

(5)

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

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

首先隨機(jī)產(chǎn)生一個(gè)含有N個(gè)粒子的粒子群，然后使用ELM分類器作為評(píng)價(jià)函數(shù)，得到適應(yīng)度后進(jìn)行ReliefF-APSO混合降維處理，不斷迭代最終得到特征子集和最優(yōu)的分類精度.本文將其應(yīng)用于基因數(shù)據(jù)分類中，通過與其他特征選擇方法進(jìn)行對(duì)比，驗(yàn)證該方法的有效性.圖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ù)集，在訓(xùn)練前，對(duì)數(shù)據(jù)進(jìn)行0均值歸一化處理.

Step 2：使用公式(1)進(jìn)行ReliefF算法特征提取，取權(quán)值相對(duì)較大的前k個(gè)特征作為APSO的訓(xùn)練集和測(cè)試集.實(shí)驗(yàn)中k取100.

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

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

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

Step 6：計(jì)算每個(gè)粒子的適應(yīng)度值.

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

4.2 預(yù)處理(歸一化)

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

(6)

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

4.3 實(shí)驗(yàn)分析

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

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

5 結(jié) 語(yǔ)

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

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

[5] 吳艷文,胡學(xué)鋼,陳效軍.基于Relief算法的特征學(xué)習(xí)聚類[J].合肥學(xué)院學(xué)報(bào)(自然科學(xué)版),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].計(jì)算機(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].計(jì)算機(jī)應(yīng)用研究,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)絡(luò)算法的研究及其應(yīng)用[D]. 鎮(zhèn)江: 江蘇大學(xué),2013. TU J J. Research on Learning Algorithm of Neural Network Optimized with PSO and its Application[D]. Zhenjiang: Jiangsu University,2013.

[11] 陳曉青,陸慧娟,鄭文斌,等. 自適應(yīng)混沌粒子群算法對(duì)極限學(xué)習(xí)機(jī)參數(shù)的優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用,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 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

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

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

TP391

A