基于规则的二次学习分类方法

李莎莎

【摘  要】多数基于规则的分类方法对训练集学习一次，产生的规则数量较少，在预测未知实例时容易出现不匹配规则的情况，影响分类准确率。文中提出一种基于规则的二次学习方法RCDI（Rule-based classification with double induction），选取长度为1和2的频繁项建立候选集，频繁项包含正项以及负项。在候选集上搜索全局以及条件库最优值来产生规则，增大搜索空间。当测试出现规则不匹配或冲突的情况，则针对符合测试实例特征实例进行二次规则提取。实验表明，该算法不仅可行，而且提高了分类准确率。

【关键词】数据挖掘;分类;规则提取;二次学习

1 引言

分类是数据挖掘中重要的任务之一。传统的基于规则的分类算法通常重复搜索当前一个最优值或多个最优值来产生规则，并移除训练集中被这些规则覆盖的例子，例如 FOIL[1]，CPAR[2] 和 CMER[3]等。这些分类方法选取生成规则的最优值时候选集中值数量少，搜索范围较小，导致产生的分类规则较少，在测试未知实例时极易出现规则不匹配的情况，在某些训练集上的分类准确率不高。Liu等提出了关联分类方法来产生关联规则[4]。大多数关联分类算法主要基于正关联模式来产生分类规则，如XTY的形式。如果是负相关则产生形如XT﹁Y 或者 ﹁X TY的负关联，﹁X代表不取x值。研究表明负关联模式也包含了非常有价值的信息，能更大范围的增大候选集的搜索空间，因而利用负关联模式进行分类同样具有十分重要的意义。 年，Liudgren等提出了二次学习方法，该方法在解决规则冲突方面有着明显的效果，但采用对冲突规则覆盖实例进行二次学习，无法解决无匹配规则的测试情况。

针对以上问题，文中提出一种新算法：基于规则的二次学习分类算法RCDI（Rule-based classification with double induction）。RCDI候选集的产生采用频繁模式，候选集包括满足支持度和置信度、长度为1的正项和负项，以及长度为2的频繁项，增大了对训练集的搜索空间。在规则产生时，充分考虑候选集上全局以及条件库最优值。规则产生过程中保留高置信度的中间规则。当测试未知实例出现规则不匹配或冲突的情况，根据测试实例的属性值在训练集上的覆盖实例组成新训练集，进行二次规则提取，二次提取规则与之前保留的高置信度规则结合，预测待分类实例类别。新训练集符合待测实例的特征，很好的解决待测实例的规则不匹配问题。通过在10个UCI数据上测试结果表明，RCDI不仅可行，而且取得了很高的分类准确率。

本文的安排如下：第2节，我们介绍RCDI，并且讨论怎样用 RCDI对新实例进行分类。实验结果在第3节进行报告。最终在第4节对我们的工作进行总结。

2 基于规则的二次学习方法

在本节，我们介绍基于规则的二次学习方法RCDI（Rule-based classification with double induction）生成的详细步骤。

2.1 RCDI规则生成

假设 为一系列元组。每个元组 有m个属性 。令 作为类标 ，并且 由 种样本组成。一条规则 包含多个样本 和一个类标 ，形式为 。从一个分类器中提取的规则组成了一个规则集。如果一个元组 满足一条规则中 的形式，那么 被规则 匹配， 预测 属于类别 。当一组属性值 所在的元组个数与训练集 的元组个数相等，则称 被属性值 覆盖。

RCDI首先选择训练集中的单个类别作为正类P，其余类别作为负类N。正类候选集生成时考虑训练集中属性值的正项和负项。度量单个属性值 以及 在每个类别中的增益值、相关度、支持度以及置信度。当满足支持度，置信度为100%时加入规则集;若满足给定支持度和置信度时，相关度大于1保留为频繁集 ，并在频繁集 中按照增益值由大至小进行排序，选择增益大于0的值作为正类的种子集。使用Apriori 算法，满足支持度、置信度和相关度要求生成频繁集 。候选集包含长度为1和2的频繁项集 、 。

候选集中每个项集的规则生成时挑选每个项集所在条件库中的最优属性值。项集的条件库是指训练集中包含该项集的所有样本。每个项集 递归选择条件库中信息增益的最大值 ，并找出条件库中存在的、种子集中信息增益最大值 ， 连接 与 生成pattern X。若pattern X的置信度为100%，则加入规则集;当置信度不足100%，但比 的置信度有提升，则X保留继续生成规则;若置信度没有提升，则抛弃这条pattern。在规则的生成过程中，保留置信度较高但不足100%的pattern作为备选规则。当一组规则生成后，对正例被规则覆盖的实例进行删除，若正例中还有实例，则重复规则提取过程。RCDI规则的生成规则如算法1所示。

2.2 分类

当测试未知实例时，RCDI首先度量每个规则的质量Laplace[2]，在每个类别中找出能匹配的规则集，并按照每条规则的 值由大至小进行排序，选取前3条，并计算在这个类别中的平均 值。具有最大平均 值的类别作为最终预测类别。

在测试时，若出现在每个类别都无规则匹配的情况，则要针对该实例进行二次学习。根据测试实例中包含的属性值 ，在训练集中找出包含 中任一属性值的样本，组成小训练集 。在小训练集中同样运用2.1中所介绍的方法进行提取规则，记为 。联合 与 共同对未知实例进行测试，测试时按照规则在训练集上的置信度和支持度由大至小进行排序，选取具有最大置信度和最大支持度的规则对未知实例进行预测。

3 实验

我们在10个 UCI数据集上进行实验，每种数据的特点如表1所示。

Att代表每個训练集的属性个数，Cla代表训练集的类别个数，Ins表明每个训练集所包含的实例数目。每个数据集上的测试采用10-折交叉验证方法。产生候选集时设置支持度为0.1，置信度为10%。在规则提取的过程中当置信度满足60%，则保留为中间规则。

在表1，我们给出了CBA、CMAR、CPAR 和 RCDI的分类准确率，最后一行给出了每个算法的平均准确率。RCDI的候选集搜索范围广，并选取候选集中每个值条件库中的最优种子来连接规则，结合了关联规则和基于规则分类的优点。并且RCDI采用二次学习的方式，在规则不匹配和遇到冲突的情况下，根据未知实例特征所覆盖的训练集进行规则的再次提取。从表 可以看出，RCDI的分类准确率不仅高于CBA算法，并且能取得比CMAR和CPAR更高的分类准确率。

通过以上的实验结果，我们可以得出：1）RCDI分类器将关联规则与基于规则相结合的分类算法是十分必要的。2）RCDI采用二次学习的方式，不仅可行，而且可以获得很高的分类准确率。

4 总结

准确率是衡量一个分类器好坏与否的重要指标。传统的分类算法在预测实例时产生规则不匹配或规则冲突时没有良好的解決方案。文中提出了一种基于规则的二次学习方法RCDI，选取满足支持度和置信度、长度为 和 的频繁项建立候选集，频繁项包含正项以及负项，增大搜索空间。在候选集上搜索全局以及条件库最优值来产生规则。当测试出现规则不匹配或冲突的情况，则针对符合测试实例特征实例进行二次规则提取。在大量数据上的实验表明，该算法不仅可行，而且提高了分类准确率。

参考文献：

[1]John Ross Quinlan，R.Mike Cameron-Jones.FOIL：A midtern report.In Proc.1993 European Conf.Machine Learning，Vienna，Austria，1993，pp：3-20.

[2]Xiaoxin Yin，Jiawei Han.CPAR：Classification based on Predictive Association Rules.Data Mining，The 2003 SIAM（Society for Industrial and Applied Mathematics）International Conference on，May.2003.

[3]Xuejun Wang，Zhongmei Zhou，Guiying Pan.CMER：Classification Based On Multiple Excellent Rules.Journal of Theoretical and Applied Information Technology，2013，pp.661-665.

[4]Wenmin Li，Jiawei Han，Jian Pei.CMAR：Accurate and efficent classification based on multiple class-assocation rules.In ICDM01，2011，pp.369-376.

（作者单位：安徽广播电视大学）