数据挖掘——规则和最近邻分类器

规则和最近邻分类器

基于规则的分类

使用一组 “if…then…”规则进行分类
规则: (Condition)→y

• 其中
  • Condition 是属性测试的合取
  • y 是类标号
• 左部: 规则的前件（或前提）（Rule antecedent）
• 右部: 规则的后件（或结论）（Rule consequent）
• 分类规则的例子:
  • (Blood Type=Warm) $\wedge$ (Lay Eggs=Yes) $\to$ Birds
  • (Taxable Income < 50K) $\wedge$ (Refund=Yes) $\to$ Cheat =No

规则的质量

用覆盖率和准确率度量

1. 规则的覆盖率（Coverage） :满足规则前件的记录所占的比例
2. 规则的准确率（Accuracy） :在满足规则前件的记录中，满足规则后件的记录所占的比例

举例：规则:(Status=Single) → No
Coverage=40%, Accuracy= 50%

规则分类的特征

互斥规则集

1. 每个记录最多被一个规则覆盖
2. 如果规则都是相互独立的，分类器包含互斥规则

如果规则集不是互斥的

• 一个记录可能被多个规则触发
  
• 如何处理?
  • 有序规则集
    • 基于规则的序 vs 基于类的序
  • 无序规则集
    • 在无序规则方案中，允许一条记录触发多条规则，规则被触发时视为对其相应类的一次投票，然后计算不同类的票数（可以使用加权方式）来决定记录的类所属。

有序规则集

根据规则优先权将规则排序定秩（rank）

• 有序规则集又称决策表（decisionlist）

对记录进行分类时

• 由被触发的，具有最高秩的规则确定记录的类标号
• 如果没有规则被触发，则指派到缺省类

穷举规则集

每个记录都至少被一个规则覆盖

如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖

如果规则集是非穷举的，一个记录可能不被任何规则触发

规则定序方案

1. 基于规则的序

   • 根据规则的质量排序：覆盖率(coverage)和准确率(accuracy)

2. 基于类的序

   • 属于同一类的规则放在一起
   • 基于类信息（如类的分布、重要性）对每类规则排序

直接方法：顺序覆盖

基本思想

• 依次对每个类建立一个或多个规则
• 对第i类建立规则
  • 第i类记录为正例，其余为负例
  • 建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例（即构建一个正例的规则）
  • 删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除
    

删除实例

为什么要删除实例？

• 否则, 下一个规则将与前面的规则相同
  （规则可能重复）

为什么删除正实例?

• 防止高估后面规则的准确率
• 确保下一个规则不同

为什么删除负实例?

• 防止过拟合错误训练集
• 防止低估后面规则的准确率

规则增长

两种策略

1. 一般到特殊（通常采用的策略）
   • 从初始规则r: {}→y开始
   • 反复加入合取项，得到更特殊的规则，直到不能再加入
2. 特殊到一般（适用于小样本情况）
   • 随机地选择一个正例作为初始规则
   • 反复删除合取项，得到更一般的规则，直到不能再删除

问题

• 加入/删除合取项有多种选择，如何选择？
• 何时停止加入/删除合取项？$\to$需要评估标准

规则评估

常用的度量

• 准确率
• 似然比
• Laplace
• FOIL信息增益

准确率

$Accuracy=\frac{n_c}{n}$

• n : 被规则覆盖的实例数
• $n_c$: 被规则正确分类的实例数

问题：准确率高的规则可能覆盖率太低
在上面的例子中：
Acc(r1): 90.9%
Acc(r2): 100%

似然比 （越高越好）

k是类别数
$f_i$是被规则覆盖的类i的样本的观测频度
$e_i$是规则作随机猜测的期望频度
$$R=2\sum _{i=1}^k{f}_{i}log(\frac{f_i}{e_i})$$
简单理解就是当前规则分类效果比随机效果越高，说明规则越好

停止条件与规则剪枝

1. 停止条件
   • 计算增益
   • 如果增益不显著, 则丢弃新规则
2. 规则剪枝
   • 类似于决策树后剪枝
   • 降低错误剪枝 :
     • 删除规则中的合取项
     • 比较剪枝前后的错误率
     • 如果降低了错误率，则剪掉该合取项

规则分类的特点

K-最近邻分类算法

急切学习 vs 惰性学习

1. 急切学习（Eager Learner）
   • 两步过程: (1) 归纳 (2) 演绎
2. 惰性学习（Lazy Learner）
   • 把训练数据建模过程推迟到需要对样本分类时
   • 例子
   • Rote-learner（死记硬背）
     • 记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类
   • 最近邻（Nearest neighbor）
     • 使用“最近”的 k 个点 (最近邻) 进行分类

k-最近邻分类算法

1. 令k是最近邻数目，D是训练样例的集合
2. for 每个测试样例 $z=(x^{\prime },y^{\prime })$ do
3. 计算z和每个样例$(x,y)\in D$之间的距离$d(x^{\prime },x)$
4. 选择离z最近的k个训练样例的集合$Dz\in D$
5. $y^{\prime }=argmax\sum _{(x_i,y_i)\in D_z}I(v=y_i)$
6. end for

距离加权表决:
$y^{\prime }=argmax\sum _{(x_i,y_i)\in D_z}I(v=y_i)$

k值的选择

如果 k 太小, 则对噪声点敏感
如果 k 太大, 邻域可能包含很多其他类的点

k-NN的特点

1. 是一种基于实例的学习
   • 需要一个邻近性度量来确定实例间的相似性或距离
2. 不需要建立模型，但分类一个测试样例开销很大
   • 需要计算域所有训练实例之间的距离
3. 基于局部信息进行预测，对噪声非常敏感
4. 最近邻分类器可以生成任意形状的决策边界
   • 决策树和基于规则的分类器通常是直线决策边界
5. 需要适当的邻近性度量和数据预处理
   • 防止邻近性度量被某个属性左右