一种改进的最大相关最小冗余选择性贝叶斯分类器

D0I:10.13374/.issn1001-053x.2012.01.006 第34卷第1期 北京科技大学学报 Vol.34 No.1 2012年1月 Journal of University of Science and Technology Beijing Jan.2012 一种改进的最大相关最小冗余选择性贝叶斯分类器 马 勇仝瑶瑶☒ 程玉虎 中国矿业大学信息与电气工程学院，徐州221116 区通信作者，E-mail:lextynf@163.com 摘要利用K均值聚类和增量学习算法扩大训练样本规模，提出一种改进的RMR SBC.一方面，利用K均值聚类预测 测试样本的类标签，将已标记的测试样本添加到训练集中，并在属性选择过程中引入一个调节因子以降低K均值聚类误标 记带来的风险。另一方面，从测试样本集中选择有助于提高当前分类器精度的实例，把它加入到训练集中，来增量地修正贝 叶斯分类器的参数.实验结果表明，与mRMR SBC相比，所提方法具有较好的分类效果，适于解决高维且含有较少类标签的 数据集分类问题. 关键词分类器：属性选择：冗余：K均值聚类：增量学习 分类号TP18 An improved maximum relevance and minimum redundancy selective Bayesian classifier MA Yong,TONG Yao-ao,CHENG Yu-hu School of Information and Electrical Engineering,China University of Mining and Technology,Xuzhou 221116,China Comresponding author,E-mail:lextynf@163.com ABSTRACT A kind of improved mRMR SBC was proposed by using K-means clustering and incremental learning algorithms to en- large the scale of training samples.On one hand,the testing samples are labeled using the K-means clustering algorithm and are added to the training set.A regulatory factor is introduced into the process of attribute selection to reduce the risk of mislabel resulting from K- means clustering.On the other hand,some samples that are most helpful for improving the current classification accuracy are selected from the testing set and are added to the training set.Based on the enlarged training set,parameters in the Bayesian classifier are ad- justed incrementally.Experimental results show that compared with mRMR SBC,the proposed Bayesian classifier has better classifica- tion results and is applicable for solving the classification problem for the high-dimensional dataset with little labels. KEY WORDS classifiers:attribute selection:redundancy:K-means clustering:incremental learning 在众多分类方法中，朴素贝叶斯分类器(naive 互信息提供了一种评价两个属性之间相关性的 Bayesian classifier,NBC)具有结构简单、分类准确和 一般方法，计算简单，易于理解.正是凭借这一优 理论基础坚实的优点，在文本分类和信息检索等领 点，学者提出了各种基于互信息的属性选择方法， 域得到了广泛的应用口.在进行分类的过程中， 如Peng等提出的最大相关最小冗余(maximum NBC经常会遇到一些维数较高的数据集，在这些高 relevance and minimum redundancy,mRMR)属性选 维数据集中通常会存在大量的无关和冗余属性，导 择方法.进一步，Peng等将mRMR应用于NBC, 致NBC的分类准确率降低.为此，可以考虑采用一 得到最大相关最小冗余选择性贝叶斯分类器 些属性选择的方法来去除无关、冗余属性，如基于 (mRMR selective Bavesian classifier,mRMR SBC), 距离的方法回、基于一致性的方法和基于互信息 实验结果表明mRMR SBC具有很好的分类效果因， 的方法回 但是，当训练样本的个数较少时，通常难以准确计 收稿日期：201104-22 基金项目：国家自然科学基金资助项目(60804022：60974050：61072094)：教有部新世纪优秀人才支持计划资助项目(NCET-08-0836)

第 34 卷 第 1 期 2012 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 1 Jan． 2012 一种改进的最大相关最小冗余选择性贝叶斯分类器 马 勇 仝瑶瑶 程玉虎 中国矿业大学信息与电气工程学院，徐州 221116 通信作者，E-mail: lcxtynf@ 163. com 摘 要 利用 K 均值聚类和增量学习算法扩大训练样本规模，提出一种改进的 mRMR SBC． 一方面，利用 K 均值聚类预测 测试样本的类标签，将已标记的测试样本添加到训练集中，并在属性选择过程中引入一个调节因子以降低 K 均值聚类误标 记带来的风险． 另一方面，从测试样本集中选择有助于提高当前分类器精度的实例，把它加入到训练集中，来增量地修正贝 叶斯分类器的参数． 实验结果表明，与 mRMR SBC 相比，所提方法具有较好的分类效果，适于解决高维且含有较少类标签的 数据集分类问题． 关键词 分类器; 属性选择; 冗余; K 均值聚类; 增量学习 分类号 TP18 An improved maximum relevance and minimum redundancy selective Bayesian classifier MA Yong，TONG Yao-yao ，CHENG Yu-hu School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou 221116，China Corresponding author，E-mail: lcxtynf@ 163. com ABSTRACT A kind of improved mRMR SBC was proposed by using K-means clustering and incremental learning algorithms to en￾large the scale of training samples． On one hand，the testing samples are labeled using the K-means clustering algorithm and are added to the training set． A regulatory factor is introduced into the process of attribute selection to reduce the risk of mislabel resulting from K￾means clustering． On the other hand，some samples that are most helpful for improving the current classification accuracy are selected from the testing set and are added to the training set． Based on the enlarged training set，parameters in the Bayesian classifier are ad￾justed incrementally． Experimental results show that compared with mRMR SBC，the proposed Bayesian classifier has better classifica￾tion results and is applicable for solving the classification problem for the high-dimensional dataset with little labels． KEY WORDS classifiers; attribute selection; redundancy; K-means clustering; incremental learning 收稿日期: 2011--04--22 基金项目: 国家自然科学基金资助项目( 60804022; 60974050; 61072094) ; 教育部新世纪优秀人才支持计划资助项目( NCET--08--0836) 在众多分类方法中，朴素贝叶斯分类器( naive Bayesian classifier，NBC) 具有结构简单、分类准确和 理论基础坚实的优点，在文本分类和信息检索等领 域得到了广泛的应用［1］． 在进行分类的过程中， NBC 经常会遇到一些维数较高的数据集，在这些高 维数据集中通常会存在大量的无关和冗余属性，导 致 NBC 的分类准确率降低． 为此，可以考虑采用一 些属性选择的方法来去除无关、冗余属性，如基于 距离的方法［2］、基于一致性的方法［3］和基于互信息 的方法［4］． 互信息提供了一种评价两个属性之间相关性的 一般方法，计算简单，易于理解． 正是凭借这一优 点，学者提出了各种基于互信息的属性选择方法， 如 Peng 等提出的最大相关最小冗余 ( maximum relevance and minimum redundancy，mRMR) 属性选 择方法［5］． 进一步，Peng 等将 mRMR 应用于 NBC， 得到最大相关最小冗余选择性贝叶斯分类器 ( mRMR selective Bayesian classifier，mRMR SBC) ， 实验结果表明 mRMR SBC 具有很好的分类效果［5］． 但是，当训练样本的个数较少时，通常难以准确计 DOI:10.13374/j.issn1001-053x.2012.01.006

第1期 马勇等：一种改进的最大相关最小冗余选择性贝叶斯分类器 ·27 算互信息以及NBC的概率分布参数园.为此，从扩 4 minR(s)=-1 (5) 展训练样本和增量学习两个方面考虑，提出一种改 进的最大相关最小冗余选择性贝叶斯分类器 式中，x:和x为S中任意两个属性，R为属性间的 (improved mRMR SBC,ImRMR SBC).一方面，结 独立性 合样本信息和部分先验知识，利用K均值聚类为测 mRMR准则表示如下： 试样本添加类别标签，从而扩展训练样本，并在使 maxo (D,R)=D-R. (6) 用mRMR准则进行属性选择的同时加入一个风险 式中，φ用来增量式地选择同类结点相关性较大， 调节因子以降低K均值聚类效果的风险性.另外， 而同其他属性结点相关性较小的属性 考虑到增量学习方式不仅可以利用以前获得的学习 利用mRMR准则进行属性选择，通常采用递 结果，缩短学习时间，还充分利用了样本提供的信 增方式逐步获取，假设己经获得m-1个属性结点， 息).因此，此处利用增量学习获得的新知识来不 则可以通过下式选择第m个属性结点， 断更新NBC的参数，从而提高NBC概率分布参数 的计算准确性 1最大相关最小冗余选择性贝叶斯分类器 (7) mRMR SBC的分类思想是基于mRMR准则选 式中，Sm-1为已经选择好的m-1个属性结点集合 择出相关性大、冗余性小的属性，然后在己选择的 2改进最大相关最小冗余选择性贝叶斯分 属性上构建NBC.NBC的分类过程如下：设C表 类器 示类结点，有q个不同取值c1,…,C4,…c,:Q是训 练数据集；T是测试数据集，t={x,…,x,…x}是 2.1K均值聚类和mRMR准则相结合的属性选择 T中的一个样本实例，也是属性变量X={x,…, 方法 x,x}的具体取值.假设类结点的先验概率为 使用mRMR准则进行属性选择，虽然能够得 p(c),由朴素假设，概率p(tIc.)的计算可以简 到较好的分类效果，但是它忽略了测试样本的作 化为 用，尤其在训练样本较少的情况下，更加需要依赖 测试样本提供的信息进行属性选择.为充分利用样 p(tlc）=p(xi,…,x,…,xlc4)= p(xilc), 本信息，一个有效的方法是扩展训练样本.考虑到 (1) K均值聚类算法具有简单、快速并且能够有效处理 由贝叶斯定理，得到类结点的后验概率为 大规模数据集的优点，此处采用K均值聚类来对测 p(clt)=p(ilep(c) 试样本进行初步的划分，将划分后的测试样本添加 p(t) 1≤k≤q (2) 到训练样本集中，从而达到扩展样本实例的目的. 式中，p(t)对于所有的类为常数，p(c)为类的先验 K均值聚类算法的目的是找到分割点，使每个 概率.于是计算的主要目标是求p(tlc),p(tlck) 聚类的均值同每个样本点的方差最小回.设4= 可由式(1)求出. {μ，…u,…,un}是类别c对应的样本实例均 mRMR准则主要包含两个部分：最大相关准则 值，则：与属于类别c4的样本实例的方差为 和最小冗余准则因.设1，表示通过训练样本集计 J(c)=∑It-4I2, (8) 算得到的互信息，属性与类结点间的互信息为 K均值聚类算法的最终目的是使得所有类的方差和 L(X:C)=∑1(x:C), (3) 最小，即 最大相关准则为 J(c)= ∑∑It-uI2, (9) m D(.c). (4) 台 在利用mRMR SBC对数据集进行分类时，通 式中，x:为属性子集S中某一属性结点，IS1为属性 常会拥有一定数量的已标记训练样本，可以用于确 子集S中属性结点的个数，D为m个属性结点同类 定K均值聚类算法的分类数目和初始中心.K均值 结点间互信息的均值 聚类算法的求解步骤如下： 最小冗余准则为 步骤1令分类数目g与己知训练样本的类别

第 1 期 马 勇等: 一种改进的最大相关最小冗余选择性贝叶斯分类器 算互信息以及 NBC 的概率分布参数［6］． 为此，从扩 展训练样本和增量学习两个方面考虑，提出一种改 进的最大相关最小冗余选择性贝叶斯分类器 ( improved mRMR SBC，ImRMR SBC) ． 一方面，结 合样本信息和部分先验知识，利用 K 均值聚类为测 试样本添加类别标签，从而扩展训练样本，并在使 用 mRMR 准则进行属性选择的同时加入一个风险 调节因子以降低 K 均值聚类效果的风险性． 另外， 考虑到增量学习方式不仅可以利用以前获得的学习 结果，缩短学习时间，还充分利用了样本提供的信 息［7］． 因此，此处利用增量学习获得的新知识来不 断更新 NBC 的参数，从而提高 NBC 概率分布参数 的计算准确性． 1 最大相关最小冗余选择性贝叶斯分类器 mRMR SBC 的分类思想是基于 mRMR 准则选 择出相关性大、冗余性小的属性，然后在已选择的 属性上构建 NBC［8］． NBC 的分类过程如下: 设 C 表 示类结点，有 q 个不同取值 c1，…，ck，…cq ; Q 是训 练数据集; T 是测试数据集，t = { x' 1，…，x' l，…x' n } 是 T 中的一个样本实例，也是属性变量 X = { x1，…， xl，…xn } 的具体取值． 假设类结点的先验概率为 p( ck ) ，由朴素假设，概率 p ( t | ck ) 的计算可以简 化为 p( t |ck ) = p( x' 1，…，x' l，…，x' n |ck ) = ∏ n l = 1 p( x' l |ck ) ， ( 1) 由贝叶斯定理，得到类结点的后验概率为 p( ck | t) = p( t |ck ) p( ck ) p( t) ，1≤k≤q． ( 2) 式中，p( t) 对于所有的类为常数，p( ck ) 为类的先验 概率． 于是计算的主要目标是求 p( t | ck ) ，p( t | ck ) 可由式( 1) 求出． mRMR 准则主要包含两个部分: 最大相关准则 和最小冗余准则［5］． 设 I1 表示通过训练样本集计 算得到的互信息，属性与类结点间的互信息为 I1 ( X; C) = ∑ n l = 1 I1 ( xl ; C) ， ( 3) 最大相关准则为 max D( S，C) = 1 | S | ∑xi∈S I1 ( xi ; C) ． ( 4) 式中，xi 为属性子集 S 中某一属性结点，| S | 为属性 子集 S 中属性结点的个数，D 为 m 个属性结点同类 结点间互信息的均值． 最小冗余准则为 minR( S) = 1 | S | 2 x ∑i ，xj ∈S I1 ( xi，xj ) ． ( 5) 式中，xi 和 xj 为 S 中任意两个属性，R 为属性间的 独立性． mRMR 准则表示如下: maxφ( D，R) = D － R． ( 6) 式中，φ 用来增量式地选择同类结点相关性较大， 而同其他属性结点相关性较小的属性． 利用 mRMR 准则进行属性选择，通常采用递 增方式逐步获取，假设已经获得 m － 1 个属性结点， 则可以通过下式选择第 m 个属性结点， max xj ∈X － Sm [ － 1 I1 ( xj ; C) － 1 m － 1 x ∑i∈Sm－1 I1 ( xj ; xi ] ) ． ( 7) 式中，Sm － 1为已经选择好的 m － 1 个属性结点集合． 2 改进最大相关最小冗余选择性贝叶斯分 类器 2. 1 K均值聚类和 mRMR 准则相结合的属性选择 方法 使用 mRMR 准则进行属性选择，虽然能够得 到较好的分类效果，但是它忽略了测试样本的作 用，尤其在训练样本较少的情况下，更加需要依赖 测试样本提供的信息进行属性选择． 为充分利用样 本信息，一个有效的方法是扩展训练样本． 考虑到 K 均值聚类算法具有简单、快速并且能够有效处理 大规模数据集的优点，此处采用 K 均值聚类来对测 试样本进行初步的划分，将划分后的测试样本添加 到训练样本集中，从而达到扩展样本实例的目的． K 均值聚类算法的目的是找到分割点，使每个 聚类的均值同每个样本点的方差最小［9］． 设 μk = { μk1，…，μkl，…，μkn } 是类别 ck 对应的样本实例均 值，则 μk 与属于类别 ck 的样本实例的方差为 J( ck ) = ∑t∈ck ‖t － μk‖2 ， ( 8) K 均值聚类算法的最终目的是使得所有类的方差和 最小，即 J( c) = ∑ q k = 1 ∑t∈ck ‖t － μk‖2 ， ( 9) 在利用 mRMR SBC 对数据集进行分类时，通 常会拥有一定数量的已标记训练样本，可以用于确 定 K 均值聚类算法的分类数目和初始中心． K 均值 聚类算法的求解步骤如下: 步骤 1 令分类数目 q 与已知训练样本的类别 ·27·

·28* 北京科技大学学报 第34卷 标签数目一致，设置最大迭代次数iter: c=c4八xi≠x: 步骤2从训练样本集Q的每类样本中，随机 T+(x=x1c), 选择一个样本实例作为各类的初始聚类中心： +2X,=1c)++E c'=cxi=xi: 步骤3在第iter次迭代中，对任意一个测试 样本，根据式(8)分别求其与q个中心的方差，将 p (X:=xic), c≠Ck 该样本归到最小方差所在的类； (12) 步骤4利用求均值的方法更新该类的中 式中，专=IX,l+count(c),IX,I为属性X,取值的个 心值： 数，count(c)为含有类别c4的个数. 步骤5对于q个聚类中心，如果利用步骤3、 综上所述，给出基于K均值聚类的增量式 步骤4的迭代法更新后，：值不变，或者迭代次数 mRMR SBC的算法步骤. 达到iter,则迭代结束，否则继续迭代. 步骤1初始化：将属性子集的初始值设为空 使用K均值聚类算法为测试样本添加类标签 集μ，即S←一μ，确定m的取值，设置α的取值 后，存在的主要问题是，K均值聚类得到的结果具 步骤2用K均值聚类算法为测试样本添加类 标签 有一定的风险性，有可能会将一部分测试样本划分 到错误的类别.为此，在计算属性与类别相关性的 步骤3将添加类标签后的测试样本加入到训 时候，添加一个风险调节因子来控制K均值聚类算 练样本中，组成新的训练集Q2· 法错分类带来的风险.改进后的mRMR准则进行 步骤4确定最优属性子集S:确定同类结点相 属性选择的公式为 关性最大的结点为S中的第一属性，使用式(10)依 次选择出剩下的m-1个属性 al (ic）+(1-a)l,(c）- max 步骤5在选择好的属性子集S上，利用Q构 m是46)] 建初始NBC (10) 步骤6使用初始NBC对Q进行分类测试，得 式中：12为在扩展后的训练样本上得到的互信息： 到分类准确率。· a∈D,l]为风险调节因子，α取值较大时，属性与 步骤7增量地学习测试数据集：用初始NBC 类别相关性的计算更多依赖于原训练数据集Q得 为测试样本添加类标签，将添加类标签的样本加入 到的互信息1，反之则表明更多依赖于扩展后的训 Q,根据式(11)和(12)增量地学习NBC参数，然后 练数据集得到的互信息I2· 对Q进行分类测试得分类准确率如果'小于。， 2.2贝叶斯分类器的增量学习 则返回原参数值，否则保留己得到的参数，。= 贝叶斯分类器的增量学习方式是指从测试样本 重复至T为空集 T中选择有助于提高当前分类器精度的实例，把它 步骤8在最终学习好的NBC上，对T进行分 加入到训练集Q中，来增量地修正NBC当前的分 类，得到分类准确率 类参数，直至T中的元素全部加入到训练集中.增 3实验研究 量贝叶斯学习是一个利用样本信息来修正当前信息 的连续动态过程，后验信息必须与先验信息属于同 选取四个具有代表性的UCI标准数据集来测 分布，对类概率和类条件概率采用无信息先验均匀 试贝叶斯分类器的分类性能，它们分别为Seme- 和共轭狄利克雷分布估计0.设测试样本1通过初 tion、Arr、Multiple和Madelon,其中包含二分类和多 始贝叶斯分类器添加类标签得d=(,c),加入 分类，连续数据和离散数据.数据集的概况见表1. 到训练样本Q中，则类概率为 表1数据集概要 8 Table 1 Summary of datasets 8+1P(c), c≠c; 数据集 类别数 属性个数 样本数 p(c)= 属性类型 (11) 1 5pc,)++6' c'= Semetion 10 256 离散 790 Arr 3 279 连续 452 式中，8=1C1+IQ1,1C1为类别的个数，IQ1为训 Multiple 6 649 连续 1000 练样本的大小.类条件概率的增量计算为 Madelon 500 连续 1000 p(X,=x1c4)=

北 京 科 技 大 学 学 报 第 34 卷 标签数目一致，设置最大迭代次数itermax ; 步骤 2 从训练样本集 Q 的每类样本中，随机 选择一个样本实例作为各类的初始聚类中心; 步骤 3 在第 iter 次迭代中，对任意一个测试 样本，根据式( 8) 分别求其与 q 个中心的方差，将 该样本归到最小方差所在的类; 步骤 4 利用求均值的方法更新该类的中 心值; 步骤 5 对于 q 个聚类中心，如果利用步骤 3、 步骤 4 的迭代法更新后，μk 值不变，或者迭代次数 达到itermax，则迭代结束，否则继续迭代． 使用 K 均值聚类算法为测试样本添加类标签 后，存在的主要问题是，K 均值聚类得到的结果具 有一定的风险性，有可能会将一部分测试样本划分 到错误的类别． 为此，在计算属性与类别相关性的 时候，添加一个风险调节因子来控制 K 均值聚类算 法错分类带来的风险． 改进后的 mRMR 准则进行 属性选择的公式为 max xj ∈X － Sm [ － 1 αI1 ( xj ; c) + ( 1 － α) I2 ( xj ; c) － 1 m － 1 x ∑i∈Sm－1 I2 ( xj ; xi ] ) ． ( 10) 式中: I2 为在扩展后的训练样本上得到的互信息; α∈［0，1］为风险调节因子，α 取值较大时，属性与 类别相关性的计算更多依赖于原训练数据集 Q 得 到的互信息 I1，反之则表明更多依赖于扩展后的训 练数据集得到的互信息 I2 ． 2. 2 贝叶斯分类器的增量学习 贝叶斯分类器的增量学习方式是指从测试样本 T 中选择有助于提高当前分类器精度的实例，把它 加入到训练集 Q 中，来增量地修正 NBC 当前的分 类参数，直至 T 中的元素全部加入到训练集中． 增 量贝叶斯学习是一个利用样本信息来修正当前信息 的连续动态过程，后验信息必须与先验信息属于同 分布，对类概率和类条件概率采用无信息先验均匀 和共轭狄利克雷分布估计［10］． 设测试样本 t 通过初 始贝叶斯分类器添加类标签得 d =〈t * ，c * 〉，加入 到训练样本 Q 中，则类概率为 p* ( ck ) = δ δ + 1 p( ck ) ， c * ≠ck ; δ δ + 1 p( ck ) + 1 1 + δ ， c * = c { k ． ( 11) 式中，δ = | C | + | Q |，| C | 为类别的个数，| Q | 为训 练样本的大小． 类条件概率的增量计算为 p* ( Xl = x' l |ck ) = ξ 1 + ξ p( Xl = x' l |ck ) ， c * = ck∧x* l ≠x' l ; ξ 1 + ξ p( Xl = x' l |ck ) + ξ 1 + ξ ， c * = ck∧x* l = x' l ; p( Xl = x' l |ck ) ， c * ≠ck        ． ( 12) 式中，ξ = | Xl | + count( ck ) ，| Xl |为属性 Xl 取值的个 数，count( ck ) 为含有类别 ck 的个数． 综上 所 述，给 出 基 于 K 均值聚类的增量式 mRMR SBC 的算法步骤． 步骤 1 初始化: 将属性子集的初始值设为空 集μ，即 S←μ，确定 m 的取值，设置 α 的取值． 步骤 2 用 K 均值聚类算法为测试样本添加类 标签． 步骤 3 将添加类标签后的测试样本加入到训 练样本中，组成新的训练集 Q2 ． 步骤 4 确定最优属性子集 S: 确定同类结点相 关性最大的结点为 S 中的第一属性，使用式( 10) 依 次选择出剩下的 m － 1 个属性． 步骤 5 在选择好的属性子集 S 上，利用 Q 构 建初始 NBC． 步骤 6 使用初始 NBC 对 Q 进行分类测试，得 到分类准确率 l0. 步骤 7 增量地学习测试数据集: 用初始 NBC 为测试样本添加类标签，将添加类标签的样本加入 Q，根据式( 11) 和( 12) 增量地学习 NBC 参数，然后 对 Q 进行分类测试得分类准确率 l'． 如果 l'小于 l0， 则返回原参数值，否则保留已得到的参数，l0 = l'． 重复至 T 为空集． 步骤 8 在最终学习好的 NBC 上，对 T 进行分 类，得到分类准确率． 3 实验研究 选取四个具有代表性的 UCI 标准数据集来测 试贝叶斯分类器的分类性能，它们分别为 Seme￾tion、Arr、Multiple 和 Madelon，其中包含二分类和多 分类，连续数据和离散数据． 数据集的概况见表 1． 表 1 数据集概要 Table 1 Summary of datasets 数据集 类别数 属性个数 属性类型 样本数 Semetion 10 256 离散 790 Arr 2 279 连续 452 Multiple 10 649 连续 1 000 Madelon 2 500 连续 1 000 ·28·

第1期 马勇等：一种改进的最大相关最小冗余选择性贝叶斯分类器 ·29 首先分析ImRMR SBC中系数a对分类结果 SBC,如数据集Ar和Multiple,表明K均值聚类 的影响.实验过程中，两种分类器的参数设置情 算法有可能将部分测试样本错误划分并将其添加 况为：属性个数m=15,K均值聚类算法的最大迭 到训练样本集中，此时的“噪声数据”将导致分类 代次数iter=l5.将各数据集的样本集合均平分 准确率下降.为改善ImRMR SBC的分类性能，此 成5份，每次取样本集的15作为训练样本，剩 时需要更多地依赖于原始训练数据集提供的较为 下的作为测试样本.将传统的mRMR SBC和本文 准确的信息，即将风险调节因子α设置得大一些 提出的ImRMR SBC两种分类器分别用于求解表1 由图1(b)和(c)可以看出，分别在a为0.8和 中数据集的分类问题，每个数据集上均独立运行 O.5时，ImRMR SBC在数据集Ar和Multiple上获 五次，取其平均值，图1给出了各数据集的分类 得最高分类准确率.对于数据集Semetion和Made- 准确率与系数α之间的关系曲线.由图可以看出， lon来说，利用K均值聚类算法扩展得到的训练样 利用mRMR SBC得到的各数据集的分类准确率不 本相对准确，有助于互信息以及概率分布参数的 受α的影响，在图中表示为一条水平直线.当a= 计算，此时可将风险调节因子α设置得小一些（均 O时，若ImRMR SBC的分类准确率低于mRMR 为0.3) 60 a 6 59 -+-ImRMR SBC 74 +-·mRMR SBC 58 57 68 ImRMR SBC --→-nRMR SBC 64 550 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 08 1.0 88 51.5 c 87 51.0 86 --ImRMR SBC ---mRMR SBC ImRMR SBC 49.5 -。·mRMR SBC 3 82 49.0 0.2 0.40.60.8 48.5 1.0 0 0.2 0.40.60.8 1.0 图1分类准确率与系数a的关系曲线.(a)Semetion数据集：(b)Ar数据集：(c)Multiple数据集(d)Madelon数据集 Fig.1 Relationship curves between classification accuracy and coefficient a:(a)Semetion dataset:(b)Arr dataset:(c)Multiple dataset:(d) Madelon dataset 由图1的分析结果可知，当属性个数为15，且 数及样本设置情况同上，将两种贝叶斯分类器用于 a分别为0.3、0.8、0.5和0.3时，mRMR SBC在四 对表1中的四个数据集进行分类，结果如表2和3 个数据集上的分类准确率明显高于mRMR SBC.为 所示.由表可以看出，不论设定属性选择的个数是 测试mRMR SBC的分类结果稳定性，固定a的取 多少，ImRMR SBC的分类准确率均明显高于 值，属性个数分别取5、10、15、20、25和30，其余参 mRMR SBC,具有较好的算法稳定性. 表2 mRMR SBC的分类准确率 Table 2 Classification accuracy of mRMR SBC % 属性个数 数据集 均值 5 10 15 20 25 30 Semetion 44.652 52.848 56.392 57.405 58.797 60.443 55.090 Arr 69.439 71.480 69.379 69.703 68.049 67.329 69.230 Multiple 65.325 78.600 83.100 82.725 82.275 81.075 78.850 Madelon 48.975 49.125 48.925 48.225 48.800 48.800 48.808

第 1 期 马 勇等: 一种改进的最大相关最小冗余选择性贝叶斯分类器 首先分析 ImRMR SBC 中系数 α 对分类结果 的影响． 实验过程中，两种分类器的参数设置情 况为: 属性个数 m = 15，K 均值聚类算法的最大迭 代次数itermax = 15. 将各数据集的样本集合均平分 成 5 份，每次取样本集的 1 /5 作为训练样本，剩 下的作为测试样本． 将传统的 mRMR SBC 和本文 提出的 ImRMR SBC 两种分类器分别用于求解表 1 中数据集的分类问题，每个数据集上均独立运行 五次，取其平均值，图 1 给出了各数据集的分类 准确率与系数 α 之间的关系曲线． 由图可以看出， 利用 mRMR SBC 得到的各数据集的分类准确率不 受 α 的影响，在图中表示为一条水平直线． 当 α = 0 时，若 ImRMR SBC 的分类准确率低于 mRMR SBC，如数据集 Arr 和 Multiple，表明 K 均值聚类 算法有可能将部分测试样本错误划分并将其添加 到训练样本集中，此时的“噪声数据”将导致分类 准确率下降． 为改善 ImRMR SBC 的分类性能，此 时需要更多地依赖于原始训练数据集提供的较为 准确的信息，即将风险调节因子 α 设置得大一些． 由图 1 ( b) 和( c) 可 以 看 出，分 别 在 α 为 0. 8 和 0. 5 时，ImRMR SBC 在数据集 Arr 和 Multiple 上获 得最高分类准确率． 对于数据集 Semetion 和 Made￾lon 来说，利用 K 均值聚类算法扩展得到的训练样 本相对准确，有助于互信息以及概率分布参数的 计算，此时可将风险调节因子 α 设置得小一些( 均 为 0. 3) ． 图 1 分类准确率与系数 α 的关系曲线． ( a) Semetion 数据集; ( b) Arr 数据集; ( c) Multiple 数据集 ( d) Madelon 数据集 Fig． 1 Relationship curves between classification accuracy and coefficient α: ( a) Semetion dataset; ( b) Arr dataset; ( c) Multiple dataset; ( d) Madelon dataset 由图 1 的分析结果可知，当属性个数为 15，且 α 分别为 0. 3、0. 8、0. 5 和 0. 3 时，ImRMR SBC 在四 个数据集上的分类准确率明显高于 mRMR SBC． 为 测试 ImRMR SBC 的分类结果稳定性，固定 α 的取 值，属性个数分别取 5、10、15、20、25 和 30，其余参 数及样本设置情况同上，将两种贝叶斯分类器用于 对表 1 中的四个数据集进行分类，结果如表 2 和 3 所示． 由表可以看出，不论设定属性选择的个数是 多 少，ImRMR SBC 的分类准确率均明显高于 mRMR SBC，具有较好的算法稳定性． 表 2 mRMR SBC 的分类准确率 Table 2 Classification accuracy of mRMR SBC % 数据集 属性个数 5 10 15 20 25 30 均值 Semetion 44. 652 52. 848 56. 392 57. 405 58. 797 60. 443 55. 090 Arr 69. 439 71. 480 69. 379 69. 703 68. 049 67. 329 69. 230 Multiple 65. 325 78. 600 83. 100 82. 725 82. 275 81. 075 78. 850 Madelon 48. 975 49. 125 48. 925 48. 225 48. 800 48. 800 48. 808 ·29·

·30 北京科技大学学报 第34卷 表3 ImRMR SBC的分类准确率 Table 3 Classification accuracy of ImRMR SBC 属性个数 数据集 均值 5 10 15 20 25 30 Semetion 47.532 58.228 60.003 61.994 62.342 64.019 59.020 Arr 72.328 75.758 75.767 76.130 76.812 77.090 75.648 Multiple 65.700 80.450 87.100 88.175 88.800 89.825 83.342 Madelon 50.850 51.900 51.400 51.425 49.325 49.575 50.746 duction /Proceedings of the 11th Pacific-sia Conference on Ad- 4结论 rances in Knowledge Discovery and Data Mining.Berlin,2007:96 对含有较少类别标签的高维数据集进行属性选 4]Brown G.A new perspective for information theoretic feature selec- tion//Proceedings of the 12th International Conference on Artifi- 择和分类时，利用mRMR SBC方法选取的属性以 cial Intelligence and Statistics.San Francisco,2009:49 及NBC的概率分布参数都不够准确，从而导致贝 5]Peng H C.Long F H,Ding C.Feature selection based on mutual 叶斯分类器的分类准确率下降.为充分利用测试样 information:criteria of max-dependency,max-relevance,and min- 本蕴涵的知识，提高互信息和NBC参数计算的准 redundancy.IEEE Trans Pattern Anal Mach Intell,2005,27(8): 确性，从属性选择和NBC构建分析两方面出发，提 1226 出了一种基于K均值聚类和增量学习思想的选择 [6]Francois D,Wertz V,Verleysen M.The permutation test for fea- ture selection by mutual information /Proceedings of European 性贝叶斯分类器.通过扩展训练数据集，选择出相 Symposium on Artificial Neural Netucorks.Bruges,2006:239 关性大、冗余性小的属性，增量地学习NBC的概率 7] Thibault G,Aussem A,Bonnevay S,et al.Incremental Bayesian 分布参数，提高分类器的分类准确率.实验验证了 network learning for scalable feature selection /Proceedings of the 这种方法的有效性. Sth International Symposium on Intelligent Data Analysis.Berlin, 2009:202 参考文献 [8]Friedman N.Geiger D,Goldszmidt M.Bayesian network classifi- [1]Di Nunzio G M.Using scatterplots to understand and improve cr.Mach Learn,1997,29(2/3):131 probabilistic models for text categorization and retrieval.Int Ap- 9]Jain A K.Data clustering:50 years beyond k-means.Pattern proximate Reasoning,2009,50(7):945 Recognit Lett,2010,31 (8)651 2] Robnik-Sikonja M.Kononenko I.Theoretical and empirical analy- [10]Gu P,Zhu QS,Zheng C.A multiview approach to semi-super- sis of ReliefF and RReliefF.J Mach Learn,2003,53(1/2):23 vised document classification with incremental naive bayes.Com- B]Hu Q H,Zhao H,Xie Z X,et al.Consistency based attribute re- put Math Appl,2009,57(6):1030

北 京 科 技 大 学 学 报 第 34 卷 表 3 ImRMR SBC 的分类准确率 Table 3 Classification accuracy of ImRMR SBC % 数据集 属性个数 5 10 15 20 25 30 均值 Semetion 47. 532 58. 228 60. 003 61. 994 62. 342 64. 019 59. 020 Arr 72. 328 75. 758 75. 767 76. 130 76. 812 77. 090 75. 648 Multiple 65. 700 80. 450 87. 100 88. 175 88. 800 89. 825 83. 342 Madelon 50. 850 51. 900 51. 400 51. 425 49. 325 49. 575 50. 746 4 结论 对含有较少类别标签的高维数据集进行属性选 择和分类时，利用 mRMR SBC 方法选取的属性以 及 NBC 的概率分布参数都不够准确，从而导致贝 叶斯分类器的分类准确率下降． 为充分利用测试样 本蕴涵的知识，提高互信息和 NBC 参数计算的准 确性，从属性选择和 NBC 构建分析两方面出发，提 出了一种基于 K 均值聚类和增量学习思想的选择 性贝叶斯分类器． 通过扩展训练数据集，选择出相 关性大、冗余性小的属性，增量地学习 NBC 的概率 分布参数，提高分类器的分类准确率． 实验验证了 这种方法的有效性． 参 考 文 献 ［1］ Di Nunzio G M． Using scatterplots to understand and improve probabilistic models for text categorization and retrieval． Int J Ap￾proximate Reasoning，2009，50( 7) : 945 ［2］ Robnik-ikonja M，Kononenko I． Theoretical and empirical analy￾sis of ReliefF and RReliefF． J Mach Learn，2003，53( 1 /2) : 23 ［3］ Hu Q H，Zhao H，Xie Z X，et al． Consistency based attribute re￾duction / / Proceedings of the 11th Pacific-Asia Conference on Ad￾vances in Knowledge Discovery and Data Mining． Berlin，2007: 96 ［4］ Brown G． A new perspective for information theoretic feature selec￾tion / / Proceedings of the 12th International Conference on Artifi￾cial Intelligence and Statistics． San Francisco，2009: 49 ［5］ Peng H C，Long F H，Ding C． Feature selection based on mutual information: criteria of max-dependency，max-relevance，and min￾redundancy． IEEE Trans Pattern Anal Mach Intell，2005，27( 8) : 1226 ［6］ Francois D，Wertz V，Verleysen M． The permutation test for fea￾ture selection by mutual information / / Proceedings of European Symposium on Artificial Neural Networks． Bruges，2006: 239 ［7］ Thibault G，Aussem A，Bonnevay S，et al． Incremental Bayesian network learning for scalable feature selection / / Proceedings of the 8th International Symposium on Intelligent Data Analysis． Berlin， 2009: 202 ［8］ Friedman N，Geiger D，Goldszmidt M． Bayesian network classifi￾er． Mach Learn，1997，29( 2 /3) : 131 ［9］ Jain A K． Data clustering: 50 years beyond k-means． Pattern Recognit Lett，2010，31( 8) : 651 ［10］ Gu P，Zhu Q S，Zheng C． A multi-view approach to semi-super￾vised document classification with incremental nave bayes． Com￾put Math Appl，2009，57( 6) : 1030 ·30·