数据挖掘 - 基于规则的分类

IF-THEN 规则

基于规则的分类器使用一组 IF-THEN 规则进行分类。我们可以用以下形式表达规则：

让我们考虑规则 R1：

R1: IF age = youth AND student = yes 
   THEN buy_computer = yes

要点：

• 规则的 IF 部分称为规则前件或前提条件。

• 规则的 THEN 部分称为规则后件。

• 前件部分的条件包含一个或多个属性测试，这些测试通过逻辑 AND 连接。

• 后件部分包含类预测。

注意：我们也可以将规则 R1 写成如下形式：

R1: (age = youth) ^ (student = yes))(buys computer = yes)

如果给定元组的条件为真，则前件满足。

规则提取

在这里，我们将学习如何通过从决策树中提取 IF-THEN 规则来构建基于规则的分类器。

要点：

要从决策树中提取规则：

• 为从根节点到叶节点的每条路径创建一个规则。

• 要形成规则前件，每个分割标准都通过逻辑 AND 连接。

• 叶节点包含类预测，形成规则后件。

使用顺序覆盖算法进行规则归纳

顺序覆盖算法可用于从训练数据中提取 IF-THEN 规则。我们不需要首先生成决策树。在这个算法中，给定类的每个规则都覆盖该类的许多元组。

一些顺序覆盖算法包括 AQ、CN2 和 RIPPER。根据通用策略，规则一次学习一个。每次学习规则时，都会删除该规则覆盖的元组，并对其余元组继续该过程。这是因为决策树中到每个叶节点的路径都对应于一个规则。

注意：决策树归纳可以被认为是同时学习一组规则。

以下是顺序学习算法，其中规则一次学习一个类。当从类 Ci 中学习规则时，我们希望该规则仅覆盖来自类 C 的所有元组，而不覆盖来自任何其他类的任何元组。

Algorithm: Sequential Covering

Input: 
D, a data set class-labeled tuples,
Att_vals, the set of all attributes and their possible values.

Output:  A Set of IF-THEN rules.
Method:
Rule_set={ }; // initial set of rules learned is empty

for each class c do
   
   repeat
      Rule = Learn_One_Rule(D, Att_valls, c);
      remove tuples covered by Rule form D;
   until termination condition;
   
   Rule_set=Rule_set+Rule; // add a new rule to rule-set
end for
return Rule_Set;

规则剪枝

规则剪枝的原因如下：

• 质量评估是在原始训练数据集上进行的。规则在训练数据上可能表现良好，但在后续数据上表现不佳。这就是为什么需要规则剪枝。

• 通过删除合取来剪枝规则。如果规则 R 的剪枝版本比在独立元组集上评估的质量更高，则对规则 R 进行剪枝。

FOIL 是一种简单有效的规则剪枝方法。对于给定的规则 R：

其中 pos 和 neg 分别是 R 覆盖的正元组和负元组的数量。

注意：此值会随着 R 在剪枝集上的准确性而增加。因此，如果 R 的剪枝版本的 FOIL_Prune 值更高，则我们剪枝 R。