基于最大相關(guān)最小冗余樸素貝葉斯分類器的應(yīng)用*

重慶醫(yī)科大學(xué)公共衛(wèi)生與管理學(xué)院 醫(yī)學(xué)與社會研究中心 健康領(lǐng)域社會風(fēng)險(xiǎn)預(yù)測治理協(xié)同創(chuàng)新中心(400016)

陳江鵬 彭 斌△ 文 雯 曾 慶 唐小靜 胡 珊 文小焱 闕 萍

基于最大相關(guān)最小冗余樸素貝葉斯分類器的應(yīng)用*

重慶醫(yī)科大學(xué)公共衛(wèi)生與管理學(xué)院 醫(yī)學(xué)與社會研究中心 健康領(lǐng)域社會風(fēng)險(xiǎn)預(yù)測治理協(xié)同創(chuàng)新中心(400016)

陳江鵬 彭 斌△文 雯 曾 慶 唐小靜 胡 珊 文小焱 闕 萍

目的 將基于最大相關(guān)最小冗余(maximum relevance minimum redundancy,MRMR)的樸素貝葉斯分類器(naive bayesian classifier,NBC)應(yīng)用于基因表達(dá)數(shù)據(jù)并與經(jīng)典NBC、隨機(jī)森林(random forests,RF)進(jìn)行比較。方法 采用Matlab與R軟件編程，應(yīng)用結(jié)腸癌與肺癌基因表達(dá)數(shù)據(jù)集，分別采用上述三種方法進(jìn)行比較研究，使用10-折交叉驗(yàn)證方法估計(jì)經(jīng)典NBC與RF的分類準(zhǔn)確率。結(jié)果 應(yīng)用MRMR-NBC分析結(jié)腸癌基因表達(dá)數(shù)據(jù)集顯示，采用信息熵(mutual information quotient,MIQ)法，當(dāng)特征m=11時(shí)分類準(zhǔn)確率達(dá)93.55%；而采用信息差(mutual information difference,MID)法時(shí)，當(dāng)m=15時(shí)分類準(zhǔn)確率達(dá)到95.16%。應(yīng)用MRMR-NBC分析肺癌基因表達(dá)數(shù)據(jù)集顯示，采用MIQ法，當(dāng)m=14時(shí)分類準(zhǔn)確率最高達(dá)98.63%，而采用MID法時(shí)當(dāng)m=12時(shí)分類準(zhǔn)確率達(dá)到97.26%。而采用經(jīng)典NBC分析結(jié)腸癌與肺癌基因表達(dá)數(shù)據(jù)時(shí)，分類準(zhǔn)確率分別為66.67%、80.00%；RF在分析結(jié)腸癌與肺癌基因表達(dá)數(shù)據(jù)時(shí)，分類準(zhǔn)確率分別為81.89%、77.62%。結(jié)論 MRMR-NBC能在僅有極少屬性參與分類時(shí)，得到較高的分類準(zhǔn)確率，優(yōu)于經(jīng)典NBC與RF。

最大相關(guān)最小冗余 樸素貝葉斯分類器 隨機(jī)森林 特征選擇

最大相關(guān)最小冗余(maximum relevance minimum redundancy,MRMR)方法自報(bào)道以來，逐漸受到關(guān)注。Hanchuan Peng等[1]人研究發(fā)現(xiàn)基于MRMR的分類器能夠準(zhǔn)備地處理分類問題，尤其是樸素貝葉斯分類器(naive bayesian classifier,NBC)，繼承了準(zhǔn)確、高效、快速的優(yōu)點(diǎn)。

隨機(jī)森林(random forests,RF)是一種集成的機(jī)器學(xué)習(xí)方法，它利用bootstrap重抽樣技術(shù)從原始樣本中抽取多個(gè)樣本進(jìn)行決策樹建模，再組合多顆決策樹的預(yù)測，通過投票得出最后結(jié)果[2]。訓(xùn)練集的隨機(jī)性和節(jié)點(diǎn)候選分割特征集合的隨機(jī)性，保證了RF中決策樹的多樣性。在繼承決策樹優(yōu)點(diǎn)的基礎(chǔ)上，在大數(shù)理論的支撐下，RF有效避免了機(jī)器學(xué)習(xí)領(lǐng)域的“過擬合”現(xiàn)象，這是RF的一個(gè)突出優(yōu)點(diǎn)[3]。此外，RF還具有分類正確率高、運(yùn)行時(shí)間短、對異常值和噪聲具有很好的容忍度等特點(diǎn)。因此，RF是機(jī)器學(xué)習(xí)方法中具有較高準(zhǔn)確率的組合分類器，其分類性能甚至超過了貝葉斯分類方法[4]。

目前，尚未見文獻(xiàn)報(bào)道MRMR-NBC與RF在分類中的性能比較。因此，本文采用基于MRMR的信息差(mutual information difference,MID)與信息熵(mutual information quotient,MIQ)法構(gòu)建NBC，采用常用數(shù)據(jù)集將其與經(jīng)典NBC、RF進(jìn)行比較，為實(shí)際科研工作中分類問題的方法選擇提供建議。

最大相關(guān)最小冗余法簡介

MRMR是以非線性相關(guān)關(guān)系作為特征的相關(guān)性度量因子。對基于互信息的特征選擇算法和NBC，一般需對數(shù)據(jù)集進(jìn)行離散化，因此本文僅使用離散化數(shù)據(jù)構(gòu)造分類器。

給定兩個(gè)隨機(jī)變量x和y，它們的概率密度分別為p(x)和p(y)，聯(lián)合概率分布為p(x,y)，則x和y的互信息可定義為：

最大相關(guān)和最小冗余的測度指標(biāo)分別定義為：

式中，S和|S|分別為特征子集及其包含的特征數(shù)目；c為目標(biāo)類別；I(xi;c)為特征i和目標(biāo)類別c之間的互信息；I(xi;xj)為特征i和特征j之間的互信息；D特征集S中各特征xi與類別c之間的均值，表示特征集與相應(yīng)類別的相關(guān)性；R為S中特征間互信息的大小，表示特征之間的冗余性。

特征選擇的目標(biāo)是期望所選特征子集的分類性能最高，同時(shí)特征維數(shù)盡量少，這就要求特征子集與類別間相關(guān)性最大，特征之間冗余性最小。綜合考慮上述兩個(gè)測度指標(biāo)，得到MRMR的MID和MIQ準(zhǔn)則如下：

maxΦ1(D,R),Φ1=D-R

maxΦ2(D,R),Φ2=D/R

通過啟發(fā)式算法優(yōu)化搜索實(shí)現(xiàn)特征子集選擇：

式中，xj∈XF-Sm-1,XF為原始特征集。這兩種優(yōu)化條件所表示的最大相關(guān)最小冗余即分別為MID和MIQ型的特征選擇算法。

方 法

1.數(shù)據(jù)來源

為了探討上述方法在進(jìn)行分類特征基因選取時(shí)的優(yōu)劣，挑選結(jié)腸癌[5]與肺癌[6]基因表達(dá)數(shù)據(jù)集進(jìn)行比較研究。

2.數(shù)據(jù)預(yù)處理

對基于互信息的特征選擇方法和NBC，一般需對數(shù)據(jù)集進(jìn)行離散化；而RF對數(shù)據(jù)集數(shù)據(jù)屬性要求較低，對于連續(xù)型和離散型數(shù)據(jù)都能在訓(xùn)練后得到較好的分類模型。使用均值μ與標(biāo)準(zhǔn)差σ進(jìn)行數(shù)據(jù)離散化處理：若表達(dá)值大于μ+σ/2則賦值為1，若表達(dá)值小于μ-σ/2則賦值為-1，若表達(dá)值介于上述兩者之間則賦值為0。

3.分析方法

(1)樸素貝葉斯分類器

P(c|X)=P(c|x1,x2,…,xn)=

式中，X是與c無關(guān)的規(guī)范化常數(shù)。

(2)基于最大相關(guān)最小冗余的樸素貝葉斯分類器

采用Matlab編程，其中最大相關(guān)最小冗余特征選擇算法Matlab程序可由Peng Lab主頁獲取(http://penglab.janelia.org/proj/mRMR/#matlab)，它根據(jù)特征與目標(biāo)類別的相關(guān)性進(jìn)行排序，同時(shí)將特征間的冗余性考慮在內(nèi)，達(dá)到相關(guān)與冗余的平衡，最終得到特征的重要性排序。本研究使用不同的特征組合構(gòu)建一系列的NBC。例如，僅使用重要性排序第一位的特征構(gòu)建第一個(gè)NBC；使用重要性排序前兩位的特征構(gòu)建第二個(gè)NBC，以此類推。在上述兩個(gè)數(shù)據(jù)集中，分別選取排序前200位的特征構(gòu)建NBC。

(3)隨機(jī)森林

采用R軟件(R 3.1.0，http://www.r-project.org)編程，由“randomForest”包完成。由包內(nèi)函數(shù)的默認(rèn)參數(shù)構(gòu)建RF，10次10-折交叉驗(yàn)證評價(jià)RF對數(shù)據(jù)集的分類準(zhǔn)確性。

4.評價(jià)指標(biāo)

本文通過使用MRMR方法對每個(gè)數(shù)據(jù)集前200個(gè)特征構(gòu)建NBC，使用采用10折交叉驗(yàn)證估計(jì)此200個(gè)特征組合的分類準(zhǔn)確率。達(dá)到最高分類準(zhǔn)確率時(shí)，包含最少的特征數(shù)目的特征組合為最優(yōu)特征組合。采用10次10折交叉驗(yàn)證(10-fold cross-validation)估計(jì)NBC與RF的算法準(zhǔn)確率。10折交叉驗(yàn)證步驟如下：將數(shù)據(jù)集分為10份，輪流將其中九份作為訓(xùn)練集，另一份作為測試集，進(jìn)行試驗(yàn)；每次試驗(yàn)得到相應(yīng)準(zhǔn)確率，將10次試驗(yàn)結(jié)果正確率的平均值作為對算法準(zhǔn)確率的估計(jì)。此過程循環(huán)10次，即進(jìn)行10次10折交叉驗(yàn)證，求其均值作為算法準(zhǔn)確率的估計(jì)。

算法準(zhǔn)確率定義為：

其中，TP，TN，F(xiàn)P，F(xiàn)N分別為分類正確的陽性樣本數(shù)，分類正確的陰性樣本數(shù)，分類錯(cuò)誤的陽性樣本數(shù)和分類錯(cuò)誤的陰性樣本數(shù)。

采用增量特征選擇(incremental feature selection,IFS)方法判斷最優(yōu)特征個(gè)數(shù)。

結(jié) 果

從圖1、2中可以看出MRMR-NBC僅使用極少的屬性參與分類就能得到非常好的分類效果，且隨著納入分析的特征增多分類效果逐漸趨于穩(wěn)定。應(yīng)用MRMR-NBC分析結(jié)腸癌基因表達(dá)數(shù)據(jù)集顯示，采用MIQ法，當(dāng)特征m=11時(shí)分類準(zhǔn)確率最高達(dá)93.55%，m=1時(shí)分類準(zhǔn)確率已達(dá)到83.87%；而采用MID法時(shí)，當(dāng)m=15時(shí)分類準(zhǔn)確率達(dá)到95.16%，m=1時(shí)分類準(zhǔn)確率也達(dá)到83.87%。應(yīng)用MRMR-NBC分析肺癌基因表達(dá)數(shù)據(jù)集顯示，采用MIQ法，當(dāng)m=14時(shí)分類準(zhǔn)確率最高達(dá)98.63%，而采用MID法時(shí)當(dāng)m=12時(shí)分類準(zhǔn)確率達(dá)到97.26%。

采用經(jīng)典樸素貝葉斯方法分析基因表達(dá)數(shù)據(jù)時(shí)，分類準(zhǔn)確率均較低(結(jié)腸癌數(shù)據(jù)集為66.67%；肺癌數(shù)據(jù)集為80.00%)，MRMR-NBC明顯優(yōu)于NBC。隨機(jī)森林在分析基因表達(dá)數(shù)據(jù)時(shí)，與NBC大致相當(dāng)，其分類準(zhǔn)確率不及MRMR-NBC(結(jié)腸癌數(shù)據(jù)集為81.89%；肺癌數(shù)據(jù)集為77.62%)。

討 論

本文介紹了MRMR-NBC方法，并采用經(jīng)典NBC和RF方法與之對比。研究結(jié)果顯示，在經(jīng)典NBC和RF分類準(zhǔn)確性較差的情況下，在經(jīng)過MRMR特征選擇后僅需少量的特征即能使NBC達(dá)到較高的分類準(zhǔn)確率，并隨著納入分析的特征數(shù)目逐漸增多分類準(zhǔn)確率趨于穩(wěn)定。

盡管MRMR特征選擇方法已表現(xiàn)出較好的分類特征選取性能，但仍有改進(jìn)空間。如：對基于MRMR的分類器，需對數(shù)據(jù)集進(jìn)行離散化，而離散化會丟失數(shù)據(jù)原始信息；若不離散化，一般采用Parzen窗口進(jìn)行概率密度估計(jì)，而該方法計(jì)算時(shí)間及復(fù)雜度均較高。針對傳統(tǒng)信息熵進(jìn)行特征選擇時(shí)需要離散化的特點(diǎn)，可引入鄰域信息熵等，使其能夠很好的處理基因表達(dá)數(shù)據(jù)。又如，可嘗試放棄貝葉斯獨(dú)立性假設(shè)，通過構(gòu)建更復(fù)雜的貝葉斯網(wǎng)絡(luò)來提高分類精度等。

[1]Peng H,Long F,Ding C.Feature selection based on mutual information criteria of max-dependency,max-relevance and min-redundancy.IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(8):1226-1238.

[2]武曉巖，李康.基因表達(dá)數(shù)據(jù)判別分析的隨機(jī)森林方法.中國衛(wèi)生統(tǒng)計(jì)，2006，23(6)：491-494.

[3]劉孝良.基于半監(jiān)督學(xué)習(xí)的隨機(jī)森林算法研究與應(yīng)用.山東：中國海洋大學(xué)，2013.

[4]Caruana R,Niculescu-Mizil A.An empirical comparison of supervised learning algorithms.Proceedings of the 23rd international conference on Machine learning,2006.

[5]Alon U,Barkai N,Notterman DA,et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays.Proc Natl AcadSci U S A,1999,96(12):6745-6750.

[6]Garber ME,Troyanskaya OG,Schluens K,et al.Diversity of gene expression in adenocarcinoma of the lung.Proc Natl AcadSci U S A.2001,98(24):13784-13789.

(責(zé)任編輯：郭海強(qiáng))

Application of Naive Bayesian Classifier Based on Maximum Relevance Minimum Redundancy Method

Chen Jiangpeng,Peng Bin,Wen Wen,et al.

(School of Public Health and Management/Medical and Social Research Center/the Innovation Center for Social Risk Governance in Health,Chongqing Medical University (400016),Chongqing)

Objective To apply Naive Bayesian classifier with Maximum Relevance Minimum Redundancy(MRMR) feature selection methods into gene expression data,and to compare it with Naive Bayesian classifier(NBC) and Random Forests(RF).Methods The three methods were applied to classify the colon and lung genes by Matlab and R software. 10-fold cross-validation was used to estimate the classification accuracy.Results When applying MRMR-NBC method to classify the colon genes,the classification accuracy reached 93.55% with features with mutual information quotient(MIQ),95.16% with with mutual information difference(MID). When applying MRMR-NBC method to classify the lung genes,the classification accuracy reached 98.63% with with MIQ,97.26% with with MID. When applying NBC to classify both of the colon and lung genes,the classification accuracy reached 66.67% and 80.00%; when applying Random Forests to classify both of the colon and lung genes,the classification accuracy reached 81.89% and 77.62%.Conclusion The classification accuracy of MRMR-NBC can reach higher than NBC and RF with fewer features.

Maximum relevance minimum redundancy; Naive Bayesian classifier; Random forests; Feature selection

國家自然科學(xué)基金(81373103)；重慶市科委基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2013jcyjA10009)

△通信作者：彭斌，E-mail：pengbin@cqmu.edu.cn