摘要
-> 传统的分类方法（C4.5，FOIL，RIPPER)：速度更快，但大多数情况下准确度不高
-> 关联分类（更高的分类精度），然而也存在着两个问题：
- 会生成大量的关联规则（高额的时间开销）
- 基于置信度的规则评估，可能会导致过拟合
-> CPAR：结合了以上两种的优势
- 采用贪心算法从训练数据中直接生成规则
- 相比于传统的分类方法，CPAR生成和测试更多的规则。（防漏掉一些重要的规则）
- 为避免过拟合，CPAR使用 预期精度 来评估每条规则，并在预测中使用最佳k条规则。
1.介绍
近年来，出现了一种新的方法——关联分类，整合了关联挖掘算法和分类。它使用了关联规则挖掘算法（eg：Apriori、FP growth）来生成关联规则的完整集。然后选择出一个高质量规则的小集合，用这一个集合来预测。这种方法已被具体的实例证明：比传统的分类方法（C4.5）有着更高的准确度。
然而，关联分类在挖掘阶段生成的规则较多、挑选出高质量的规则开销较大，导致起效率上存在一定的劣势。
基于此，我们推出CPAR算法。CPAR算法继承了FOIL在规则生成方面的基本思想、整合了关联分类在预测规则分析方面的特性。
相比于关联分类，CPAR有以下优势：
- 直接从数据集中，生成更小的高质量预测规则集。
- 为避免生成冗余的规则，CPAR生成新规则时会考虑已经生成的规则集合。
- 预测时，CPAR使用与该预测样本匹配的最好k条规则。
同时，CPAR采用了以下的措施来提高准确度和效率：
- 在规则生成中，使用得到动态规划来避免重复的计算。
- 生成规则时，所有close-to-the-best键值对都将被选中。（之前只选最好的一个）
2.基于规则的分类
2.1 一些基本的定义：
Each tuple t in T(a set) follows the scheme (A1, A2, . . . , Ak).Ak is the k-th attribute.
A literal p = an attribute and a value, such as p = (Ai, v).
The form of a rule: p1 ∧ p2 ∧ · · · ∧ pl → c. c is the class label.
注: If a rule contains zero literal, its body is satisfied by any tuple.
2.2 两个重要的分类器：CBA、CMAR
CBA：
- 根据某支持度、置信度阈生成一些候选规则。
- 从中选取一小部分规则，用来形成一个分类器。
- 预测时，选取与规则主体匹配的最好规则。（有着最高的置信度）
CMAR：
CMAR生成和评价规则与CBA类似,但使用了一个更高效的结构——FPtree。同时，一个最主要的不同是：在预测时，采用了多重规则（using weighted χ2.）CMAR的准确度更高。
当遇到比较大的数据集时，两种算法的开销都比较大。
3.规则的生成(Step-by-step)
3.1 FOIL算法
一种贪心的算法（分辨正样本和负样本）。基本的思路：不断生成当前最好的规则（通过Gain参数【基于一条规则中新键值对的加入】判断），剔除掉已经包含的正样本，最后所有的规则合成一个集合。
对于多分类问题，解决办法：1 vs rest
时间复杂度：O(nkm|R|)
缺点：FOIL没有达到很高的准确度，其原因是：生成的规则比较少。
3.2 PRM：Predictive Rule Mining
相比于FOIL中剔除掉已经包含的正样本，PRM采取降低权重的方法（乘以一个因子），以此生成更多的规则，从而提高准确度。同时，通过PNArray来存储一些信息，来减少时间的开销。
PNArray所存储的信息：
- 与当前规则r匹配的正样本、负样本数量。
- 加入一个新的键值对literal p后，正样本、负样本的数量。
时间复杂度：O(nk|R|)，效率较高但准确度还是较低（相比于关联分类）。
3.3 CPAR的规则生成
生成规则时，所有close-to-the-best键值对都将被选中。同时，采用DFS来生成规则，一个示例如下图：
[图片上传失败...(image-d04dc5-1532249941409)]
时间复杂度：O(nk|R|)
4.使用规则进行预测
4.1 规则评估
预测准确度：Prob(t ∈ c|t satisfies r's body)(采用拉普拉斯预期误差估计)
4.2 分类
选取每个类的最好k条作预测，步骤如下：
- 选取该样本所有与主体匹配的规则。
- 对于每一个类，选取最好k条。
- 比较每个类的平均预测准确度，选择最高的类。
5.参考文献：
CPAR: Classification based on Predictive Association Rules，Xiaoxin Yin
