基于最大相關最小冗余樸素貝葉斯分類器的應用*

重慶醫科大學公共衛生與管理學院 醫學與社會研究中心 健康領域社會風險預測治理協同創新中心(400016)

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

基于最大相關最小冗余樸素貝葉斯分類器的應用*

重慶醫科大學公共衛生與管理學院 醫學與社會研究中心 健康領域社會風險預測治理協同創新中心(400016)

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

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

最大相關最小冗余 樸素貝葉斯分類器 隨機森林 特征選擇

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

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

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

最大相關最小冗余法簡介

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

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

最大相關和最小冗余的測度指標分別定義為：

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

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

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

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

通過啟發式算法優化搜索實現特征子集選擇：

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

方 法

1.數據來源

為了探討上述方法在進行分類特征基因選取時的優劣，挑選結腸癌[5]與肺癌[6]基因表達數據集進行比較研究。

2.數據預處理

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

3.分析方法

(1)樸素貝葉斯分類器

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

式中，X是與c無關的規范化常數。

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

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

(3)隨機森林

采用R軟件(R 3.1.0，http://www.r-project.org)編程，由“randomForest”包完成。由包內函數的默認參數構建RF，10次10-折交叉驗證評價RF對數據集的分類準確性。

4.評價指標

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

算法準確率定義為：

其中，TP，TN，FP，FN分別為分類正確的陽性樣本數，分類正確的陰性樣本數，分類錯誤的陽性樣本數和分類錯誤的陰性樣本數。

采用增量特征選擇(incremental feature selection,IFS)方法判斷最優特征個數。

結 果

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

采用經典樸素貝葉斯方法分析基因表達數據時，分類準確率均較低(結腸癌數據集為66.67%；肺癌數據集為80.00%)，MRMR-NBC明顯優于NBC。隨機森林在分析基因表達數據時，與NBC大致相當，其分類準確率不及MRMR-NBC(結腸癌數據集為81.89%；肺癌數據集為77.62%)。

討 論

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

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

[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]武曉巖，李康.基因表達數據判別分析的隨機森林方法.中國衛生統計，2006，23(6)：491-494.

[3]劉孝良.基于半監督學習的隨機森林算法研究與應用.山東：中國海洋大學，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.

(責任編輯：郭海強)

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

國家自然科學基金(81373103)；重慶市科委基礎與前沿研究計劃項目(cstc2013jcyjA10009)

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