基于最大相关最小冗余朴素贝叶斯分类器的应用*

重庆医科大学公共卫生与管理学院 医学与社会研究中心 健康领域社会风险预测治理协同创新中心(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