免规则采集器列表算法(基于规则的分类器特点：规则集的表达能力是什么？)

　　免规则采集器列表算法(基于规则的分类器特点：规则集的表达能力是什么？)

　　基于规则的分类器

　　基于规则的分类器是一种使用一组“如果...则...”规则对记录进行分类的技术。规则学习算法使用一种称为规则和规则的启发式方法。此过程涉及确定覆盖训练数据中案例子集的规则，然后将该分区与其余数据分开。随着规则的添加，更多的数据子集被分离，直到整个数据集被覆盖并且不再有任何案例。

　　**和规则与决策树的分而治之差别很小，决策树的每个决策节点都会受到过去决策历史的影响，规则学习中没有这样的谱系。随着规则的添加，更多的数据子集被分离，直到覆盖整个数据集并且不再保留任何案例。模型的规则用析取范式 R = (r1 ∨ r2 ∨ ••• ∨ rk) 表示，其中 R 称为规则集，ri 是分类规则或析取项。每个分类规则可以用以下形式表示：

　　ri: (条件 i)→yi

　　规则的左侧成为规则的前件或前提。它是属性测试的结合：

　　条件 i=(A1 op v1)∧(A1 op v1)∧•••∧(A1 op v1)

　　其中 (Aj, vj) ​​是属性值对，op 是比较运算符，取自集合 {=, ≠, ﹤, ﹥, ≦, ≧}。每个属性测试 (Aj op vj) ​​称为合取。规则的右侧称为规则后件，收录预测的类 yi。如果规则 r 的前件与记录 x 的属性匹配，则称 r 覆盖 x。当 r 覆盖给定记录时，r 被称为被解雇或解雇。

　　基于规则的分类器具有以下特点：规则集的表达能力几乎等同于决策树，并且与决策树一样，可以用互斥和穷举的规则集来表示。基于规则的分类器和决策树分类器都对属性空间进行线性分区，并将类分配给每个分区。基于规则的分类器通常用于生成与决策树分类器相当的可解释性描述模型。

　　如何构建基于规则的分类器（以RIPPER算法为例）

　　为了构建基于规则的分类器，需要提取一组规则来识别数据集的属性和类标签之间的关键连接。一般采用直接法直接从数据中提取分类规则，直接法将属性空间划分为更小的子空间，使得属于一个子空间的所有记录都可以使用分类规则进行分类。

　　规则增长：

　　目标是提取一个分类规则，该规则涵盖训练集中的大量正例，而没有或只有少量负例。然而，由于搜索空间的指数大小，找到最优规则的计算成本很高。通过以贪婪的方式增长规则来解决指数搜索问题。它产生一个初始规则 r 并不断改进它，直到满足某个终止条件。然后修剪该规则以改善其泛化错误。

　　RIPPER 算法使用从一般到特殊的策略进行规则增长。在从一般到特殊的策略中，首先建立一个初始规则 r:{}→y，其中左侧为空集，右侧收录目标类。该规则的质量很差，因为它涵盖了训练集中的所有示例。然后添加新的连词以提高规则的质量，直到满足终止条件（例如，添加的连词不能再提高规则的质量）。

　　对于二分类问题，RIPPER 算法选择多数类作为默认类，并学习预测少数类的规则。对于多类问题，首先按频率对类进行排序，令 (y1,y2,…,yc) 为排序后的类，其中 y1 是最不频繁的类，yc 是最频繁的类。在第一次迭代中，将属于 y1 的示例标记为正例，而将其他类的示例标记为负例，并使用顺序覆盖算法生成区分正例和负例的规则。接下来，RIPPER 提取将 y2 与其他类区分开来的规则。重复这个过程，直到类 yc 仍然存在，此时 yc 是默认类。充分体现了**和规则的思想。

　　由于规则以贪婪的方式增长，上述方法可能会产生次优规则。为了避免这个问题，可以使用束搜索。该算法维护了 k 个最佳候选规则，每个规则都通过在其先行词中添加或删除连词来增长**。评估候选规则的质量并为下一次迭代选择 k 个最佳候选。

　　连词加减法规则：

　　在规则的增长过程中，需要一个评估指标来确定应该添加（或删除）哪些连词。准确性是一个显而易见的选择，因为它明确给出了被规则正确分类的训练示例的比例。FOIL 信息增益：规则的支持计数对应于它所涵盖的正例数。假设规则 r : A→+ 覆盖 p0 个正例和 n0 个负例。增加了一个新的连词 B，扩展规则 r' : A∧B→+ 涵盖了 p1 个正例和 n1 个负例。根据以上信息，扩展规则的FOIL信息增益定义为：

　　由于该指标与 p1 和 p1/p1+n1 成正比，因此它更喜欢选择那些支持数高且准确度高的规则。RIPPER 算法使用 FOIL 信息增益来选择最佳连接添加到规则前件。当规则开始涵盖反例时，停止添加连词。

　　定期修剪：

　　新规则根据它们在确认集上的表现进行修剪。计算以下度量以确定规则是否需要修剪：(pn)/(p+n)，其中 p 和 n 分别是规则覆盖的验证集中的正例和负例的数量，相对于验证集上规则的准确性，度量是单调的。如果修剪后度量增加，则删除连接。修剪从最后添加的连词开始。例如，给定规则 ABCD→y，RIPPER 算法首先检查是否应该修剪 D，然后检查 CD、BCD 等。虽然原创规则只覆盖正例，但修剪后的规则可能会覆盖训练集中的一些负例。

　　RIPPER算法的原理很简单：一般可以理解为一个三步的过程：增长、剪枝、优化，增长过程使用**和规则技术贪婪地给规则添加条件，直到规则完全可以划分数据子集或不使用任何属性进行分割。与决策树类似，信息增益准则可用于确定下一次拆分的属性，当添加特定规则且熵值不再降低时，需要立即对规则进行剪枝。重复步骤 1 和 2，直到达到停止标准，然后使用各种启发式方法优化整个规则集。