理解机器学习：规则发现的方法 - 顺序覆盖、单一规则构建与剪枝技巧优化

1. 序贯覆盖

回归： 分类：

聚类：

逻辑规则：

读作：若（文字1且文字2且...），则目标概念成立

规则集：充分性与必要性；冲突消解：顺序规则、缺省规则、元规则

eg：

命题逻辑 → 命题规则

原子命题：????,????,????,…A,B,C,…；逻辑连词：↔,→,←,⋀,⋁,¬…↔,→,←,⋀,⋁,¬…

一阶逻辑 →一阶规则

常量：????,????,????,…,1,2,3,…；变量：????,????,????,…A,B,C,…

（n元）谓词/函数： p/n, f/n；项：常量|变量|函数/谓词（项1，项2，…）

原子公式：函数/谓词（项1，项2，…）父亲（X,Y），自然数（39），偶数（后继（1）），…

逻辑连词：↔,→,←,⋀,⋁,¬…；逻辑量词：∀，∃

序贯覆盖：在训练集上每学到一条规则，就将改规则覆盖的样例去除，然后以剩下的样例组成训练

集重复上述过程（ 分治策略）。

 

2. 单条规则学习

目标：寻找一组最优的逻辑文字来构成规则体。本质：搜索问题；搜索空间大，易造成组合爆炸。

方法：自顶向下：一般到特殊（ 泛化）；自底向上：特殊到一般（ 特化）

自顶向下策略：一般到特殊（特化）

 

自底向上策略：特殊到一般（泛化）

规则评判：增加/删除哪一个候选文字；准确率；信息熵增益（率）；基尼系数 ……

规避局部最优：集束搜索：每次保留最优的多个候选规则 ……

3. 剪枝优化

贪心算法导致的非最优的算法：

预剪枝：似然率统计量：

后剪枝：剪错剪枝（REP）：穷举所有可能的剪枝操作（删除文字、删除规则），复杂度非常高，

用验证集反复剪枝直到精确率无法提高。

二者结合：IREP：每生成一条新规则即对进行REP剪枝

IREP*：是对IREP的优化

RIPPER：

 IREP*生成规则集，选取其规则，找到其覆盖的样例，重新生成规则，特化原规则在泛化，把原规

则和新规则放入规则集中进行评价，留下最好的，反复优化直到无法进步。

RIPPER将所有规则放在一起优化，通过全局的考虑来缓解序贯覆盖的局部性。