D0I:10.13374/1.issm100103.2008.08.025 第30卷第8期 北京科技大学学报 Vol.30 No.8 2008年8月 Journal of University of Science and Technology Beijing Aug:2008 基于互信息的多关系朴素贝叶斯分类器 徐光美杨炳儒秦奕青张伟 北京科技大学信息工程学院，北京100083 摘要为进一步提高多关系朴素贝叶斯方法的分类准确率，分析了已有的剪枝方法，并扩展互信息标准到多关系情况下· 基于元组号传播方法和面向元组的统计计数方法，给出了基于扩展互信息标准进行属性选择的方法和步骤，并建立了一种基 于扩展互信息的多关系朴素贝叶斯分类器。标准数据集上的实验显示，基于扩展互信息标准进行属性选择，可以在不增加算 法时间复杂度的前提下，找到与分类属性最相关的属性，并在仅有极少属性参与分类时，得到较高的分类准确率.Mutagenesis 数据集上的实验则显示，这种属性选择可以使多关系问题退化为单关系问题，大大降低了分类代价 关键词朴素贝叶斯：分类器：多关系数据挖掘：归纳逻辑程序设计：互信息 分类号TP391 Multi-relational Nalve Bayesian classifier based on mutual information XU Guangmei,YA NG Bingru,QIN Yiqing,ZHANG Wei School of Information Engineering.University of Science and Technology Beijing.Beijing 100083 ABSTRACI To improve the accuracy of multi-relational Naive Bayesian classifiers.the existing pruning methods were discussed and the attribute filter criterion was upgraded based on mutual information to deal with multi-relational data directly.On the basis of the tuple ID propagation method and counting methods towards tuple.the filter method based on extended mutual information was given. and a multi-relational Naive Bayesian classifier based on mutual information(MI-MRNBC)was implemented.Experimental results show that,in a multi-relational domain,with the help of the attribute filter based on extended mutual information,the classifier can give a better accuracy without the increase of time complexity.In extraordinary instances.the multi-relational classification degener- ates into a single relational one,which extremely decreases the cost of classification. KEY WORDS Naive bayesian:classifier:multi-relational data mining (MRDM):inductive logic programming (ILP):mutual in- formation 随着多关系数据挖掘的兴起，各种各样的多关 Graph NB中使用了一种叫做“Cutting off”的剪枝 系朴素贝叶斯分类器(multi-relational Naive 策略，对表进行剪枝，以提高分类准确率。但是这种 Bayesian classifier,MRNBC)被提出，其中大多数方 方法有很多缺点：第一，对于朴素贝叶斯分类而言， 法基于归纳逻辑程序设计(inductive logic program~ 参与分类的基本单位是属性而不是表，因此直接删 ming,ILP)技术形成，这类方法通常都通过用户定 除弱连接的表是明显不合适的·第二，特征选择有 义的参数和语言偏置控制规则长度，从而降低问题 两种方法一过滤方法(filter)和打包方法(wrap 规模、提高分类准确率，例如：基于ILP一R的多关 per),“Cutting off"剪枝方法是一种打包方法，打包 系朴素贝叶斯分类方法山、1BC2]、1BC2方法[3]、 方法是与分类器绑定的剪枝策略，它选择的是与分 Mr-SBC方法可和nFOIL方法6等；基于Cross- 类器特点相匹配的最好属性，所以理论上能够得到 Mime的元组号传播方法]；基于关系数据库技术 很好的准确率；但打包方法找到的好的属性仅适于 的多关系朴素贝叶斯分类方法一Graph一NB). 当前所用分类器，而且使用打包方法明显需要付出 收稿日期：2007-07-24修回日期：2007-12-17 基金项目：国家自然科学基金资助项目(N。-60675030) 作者简介：徐光美(1977-)，女，博士研究生；杨炳儒(1943一)，男，教授，博士生导师，E mail:bryang--kd@yahoo~com~cm基于互信息的多关系朴素贝叶斯分类器 徐光美 杨炳儒 秦奕青 张 伟 北京科技大学信息工程学院‚北京100083 摘 要 为进一步提高多关系朴素贝叶斯方法的分类准确率‚分析了已有的剪枝方法‚并扩展互信息标准到多关系情况下． 基于元组号传播方法和面向元组的统计计数方法‚给出了基于扩展互信息标准进行属性选择的方法和步骤‚并建立了一种基 于扩展互信息的多关系朴素贝叶斯分类器．标准数据集上的实验显示‚基于扩展互信息标准进行属性选择‚可以在不增加算 法时间复杂度的前提下‚找到与分类属性最相关的属性‚并在仅有极少属性参与分类时‚得到较高的分类准确率．Mutagenesis 数据集上的实验则显示‚这种属性选择可以使多关系问题退化为单关系问题‚大大降低了分类代价． 关键词 朴素贝叶斯；分类器；多关系数据挖掘；归纳逻辑程序设计；互信息 分类号 TP391 Mult-i relational Naïve Bayesian classifier based on mutual information XU Guangmei‚Y A NG Bingru‚QIN Y iqing‚ZHA NG Wei School of Information Engineering‚University of Science and Technology Beijing‚Beijing‚100083 ABSTRACT To improve the accuracy of mult-i relational Naïve Bayesian classifiers‚the existing pruning methods were discussed and the attribute filter criterion was upgraded based on mutual information to deal with mult-i relational data directly．On the basis of the tuple ID propagation method and counting methods towards tuple‚the filter method based on extended mutual information was given‚ and a mult-i relational Naïve Bayesian classifier based on mutual information （MI-MRNBC） was implemented．Experimental results show that‚in a mult-i relational domain‚with the help of the attribute filter based on extended mutual information‚the classifier can give a better accuracy without the increase of time complexity．In extraordinary instances‚the mult-i relational classification degener￾ates into a single relational one‚which extremely decreases the cost of classification． KEY WORDS Naïve bayesian；classifier；mult-i relational data mining （MRDM）；inductive logic programming （ILP）；mutual in￾formation 收稿日期：2007-07-24 修回日期：2007-12-17 基金项目：国家自然科学基金资助项目（No．60675030） 作者简介：徐光美（1977—）‚女‚博士研究生；杨炳儒（1943—）‚男‚教授‚博士生导师‚E-mail：bryang—kd＠yahoo．com．cn 随着多关系数据挖掘的兴起‚各种各样的多关 系 朴 素 贝 叶 斯 分 类 器 （ mult-i relational Naïve Bayesian classifier‚MRNBC）被提出‚其中大多数方 法基于归纳逻辑程序设计（inductive logic program￾ming‚ILP）技术形成．这类方法通常都通过用户定 义的参数和语言偏置控制规则长度‚从而降低问题 规模、提高分类准确率．例如：基于 ILP—R 的多关 系朴素贝叶斯分类方法［1］、1BC ［2］、1BC2方法［3—4］、 Mr—SBC 方法［5］ 和 nFOIL 方法［6］ 等；基于 Cross￾Mine 的元组号传播方法［7—8］；基于关系数据库技术 的多关系朴素贝叶斯分类方法———Graph—NB ［9］． Graph—NB 中使用了一种叫做“Cutting off ”的剪枝 策略‚对表进行剪枝‚以提高分类准确率．但是这种 方法有很多缺点：第一‚对于朴素贝叶斯分类而言‚ 参与分类的基本单位是属性而不是表‚因此直接删 除弱连接的表是明显不合适的．第二‚特征选择有 两种方法———过滤方法（filter）和打包方法（wrap￾per）‚“Cutting off”剪枝方法是一种打包方法．打包 方法是与分类器绑定的剪枝策略‚它选择的是与分 类器特点相匹配的最好属性‚所以理论上能够得到 很好的准确率；但打包方法找到的好的属性仅适于 当前所用分类器‚而且使用打包方法明显需要付出 第30卷 第8期 2008年 8月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．8 Aug．2008 DOI:10．13374／j．issn1001－053x．2008．08．025