第8期 徐光美等：基于互信息的多关系朴素贝叶斯分类器 .965 的平均结果 可以达到最高为84.1%；而使用所有属性参与分类 由于计算互信息值不需要额外的统计计数，因 时，即m为7时分类准确率为78.1%.而且基于扩 此训练阶段仅需要增加对属性的一次快速排序时间 展的互信息标准找到的与分类属性最相关的前三个 就可以找到所需要的m个属性，这不会增加算法运 属性是lumo”、logD”、“ind”,而这三个属性都是目 行的时间复杂度（进行属性选择和不进行属性选择 标表中属性，这意味着不需要进行复杂的多关系连 算法时间复杂度都为O(max(nr·nra),其中T为 接操作，只用目标表中属性分类就可以得到最好的 数据集中的任一表，T。为表T在R中的直接前驱， 分类结果，因此多关系分类退化为单关系分类问题， nr为T中元组数目，nr为Tg中元组数目)，而且 这大大降低了分类的时空代价，一定程度上也提高 当这m个属性之外的属性存在缺失值时丝毫不会 了分类器的容噪能力， 影响分类性能，所以MI一MRNBC算法具有高效性 100 和较高的容错性， 901 ·-MI-MRNBC ·-S-MRNBC 2实验 80 本文使用多关系领域常用的标准数据集： 70 PKDD CUP 1999的金融数据集和Mutagenesis数据 60 集实验，本文实验中各表权值”都默认为1. 1234567891011 属性数 (1)金融数据集，便于比较，根据文献[9]对金 融数据集进行修改，为比较基于互信息的多关系属 图3 Mutagenesis数据集上的分类准确率比较 性选择方法的有效性，本文也实现了一个随机选择 Fig.3 Accuracy on Mutagenesis database 属性进行多关系朴素贝叶斯分类的算法 S-MRNBC.图2是MI一IRNBC和S一IRNBC的 3结论 分类准确率比较（取10次交叉验证的平均结果）· 基于元组号传播方法，本文给出了基于互信息 100 的多关系属性选择方法，并在此基础上形成了基于 ◆-MI-MRNBC 90 S-MRNBC 互信息的多关系朴素贝叶斯分类器(MI一ARNBC), 实验显示使用基于互信息的属性剪枝方法可以在几 乎不增加计算时间基础上，找到与分类属性最相关 70 的属性，并在仅用极少的属性参与分类情况下，得到 601 较高的分类准确率。 11 16212631 属性数 MI一RNBC中根据传播的类标签的数目和类 别进行统计计数，计数并没有考虑传播的元组号可 图2金融数据集上的分类准确率比较 能重复的问题，将来的工作可以考虑引入合适的聚 Fig.2 Accuracy on financial database 合函数，在考虑传播的类标签个数的同时也考虑元 组号是否重复，对于一个表中元组与其他表中多个 从图2可以看出，MI一MRNBC仅使用极少的 元组相连接的情况，可以引入合适的概率分布函数 的属性（当m为6时分类准确率最高为85%）参与 定义多个元组的联合概率，改变现在的多关系朴素 分类就可以得到良好的分类效果，并且当属性个数 贝叶斯计算公式 在1~17之间变化时都比使用所有的属性参与分类 的分类效果更好（所有属性参与分类时，准确率为 参考文献 79.25%) [1]Pompe U.Kononenko 1.Naive Bayesian classifier within ILP-R// (2)Mutagenesis数据集.使用回归友好的 Proceedings of the 5th International Workshop on Inductive Log- Mut agenesis数据集的所有属性参与实验，图3是 ie Programming.Belgie:Katholieke Universiteit Leuven.1995: MI一RNBC和S-MRNBC的分类准确率比较， 417 从图3可以看出：MI一MRNBC仅使用极少的 [2]Peter A.Nicolas L.IBC:a first-order Bayesian classifier//Pro- ceedings of the 9th International Workshop on Inductive Logic 属性就可以得到良好的分类效果，其中当m为3时 Programming.Berlin:Springer-Verlag.1999.1634:92 分类准确率最高为88.9%，m为1时分类准确率就 [3]Nicolas L,Peter A.1BC2:a true first-order Bayesian classifier//的平均结果． 由于计算互信息值不需要额外的统计计数‚因 此训练阶段仅需要增加对属性的一次快速排序时间 就可以找到所需要的 m 个属性‚这不会增加算法运 行的时间复杂度（进行属性选择和不进行属性选择 算法时间复杂度都为 O（max（ nT·nTq））‚其中 T 为 数据集中的任一表‚Tq 为表 T 在 R 中的直接前驱‚ nT 为 T 中元组数目‚nTq为 Tq 中元组数目）‚而且 当这 m 个属性之外的属性存在缺失值时丝毫不会 影响分类性能‚所以 MI—MRNBC 算法具有高效性 和较高的容错性． 2 实验 本文使 用 多 关 系 领 域 常 用 的 标 准 数 据 集： PKDD CUP1999的金融数据集和 Mutagenesis 数据 集实验．本文实验中各表权值 w 都默认为1． （1） 金融数据集．便于比较‚根据文献［9］对金 融数据集进行修改．为比较基于互信息的多关系属 性选择方法的有效性‚本文也实现了一个随机选择 属 性 进 行 多 关 系 朴 素 贝 叶 斯 分 类 的 算 法 S—MRNBC．图2是 MI—MRNBC 和 S—MRNBC 的 分类准确率比较（取10次交叉验证的平均结果）． 图2 金融数据集上的分类准确率比较 Fig．2 Accuracy on financial database 从图2可以看出‚MI—MRNBC 仅使用极少的 的属性（当 m 为6时分类准确率最高为85％）参与 分类就可以得到良好的分类效果‚并且当属性个数 在1～17之间变化时都比使用所有的属性参与分类 的分类效果更好（所有属性参与分类时‚准确率为 79∙25％）． （2） Mutagenesis 数 据 集．使 用 回 归 友 好 的 Mutagenesis数据集的所有属性参与实验．图3是 MI—MRNBC和S—MRNBC的分类准确率比较． 从图3可以看出：MI—MRNBC 仅使用极少的 属性就可以得到良好的分类效果‚其中当 m 为3时 分类准确率最高为88∙9％‚m 为1时分类准确率就 可以达到最高为84∙1％；而使用所有属性参与分类 时‚即 m 为7时分类准确率为78∙1％．而且基于扩 展的互信息标准找到的与分类属性最相关的前三个 属性是“lumo”、“logp”、“indl”‚而这三个属性都是目 标表中属性‚这意味着不需要进行复杂的多关系连 接操作‚只用目标表中属性分类就可以得到最好的 分类结果‚因此多关系分类退化为单关系分类问题‚ 这大大降低了分类的时空代价‚一定程度上也提高 了分类器的容噪能力． 图3 Mutagenesis 数据集上的分类准确率比较 Fig．3 Accuracy on Mutagenesis database 3 结论 基于元组号传播方法‚本文给出了基于互信息 的多关系属性选择方法‚并在此基础上形成了基于 互信息的多关系朴素贝叶斯分类器（MI—MRNBC）． 实验显示使用基于互信息的属性剪枝方法可以在几 乎不增加计算时间基础上‚找到与分类属性最相关 的属性‚并在仅用极少的属性参与分类情况下‚得到 较高的分类准确率． MI—MRNBC 中根据传播的类标签的数目和类 别进行统计计数‚计数并没有考虑传播的元组号可 能重复的问题‚将来的工作可以考虑引入合适的聚 合函数‚在考虑传播的类标签个数的同时也考虑元 组号是否重复．对于一个表中元组与其他表中多个 元组相连接的情况‚可以引入合适的概率分布函数 定义多个元组的联合概率‚改变现在的多关系朴素 贝叶斯计算公式． 参 考 文 献 ［1］ Pompe U‚Kononenko I．Naïve Bayesian classifier within ILP-R∥ Proceedings of the5th International Workshop on Inductive Log￾ic Programming．Belgie：Katholieke Universiteit Leuven‚1995： 417 ［2］ Peter A‚Nicolas L．1BC：a first-order Bayesian classifier∥ Pro￾ceedings of the 9th International Workshop on Inductive Logic Programming．Berlin：Springer-Verlag‚1999‚1634：92 ［3］ Nicolas L‚Peter A．1BC2：a true first-order Bayesian classifier∥ 第8期 徐光美等： 基于互信息的多关系朴素贝叶斯分类器 ·965·