美文网首页
CPAR论文

CPAR论文

作者: heaker | 来源:发表于2018-07-22 16:59 被阅读22次

摘要

-> 传统的分类方法(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:

  1. 根据某支持度、置信度阈生成一些候选规则。
  2. 从中选取一小部分规则,用来形成一个分类器。
  3. 预测时,选取与规则主体匹配的最好规则。(有着最高的置信度)

CMAR:

CMAR生成和评价规则与CBA类似,但使用了一个更高效的结构——FPtree。同时,一个最主要的不同是:在预测时,采用了多重规则(using weighted χ2.)CMAR的准确度更高。

当遇到比较大的数据集时,两种算法的开销都比较大。

3.规则的生成(Step-by-step)

3.1 FOIL算法

一种贪心的算法(分辨正样本和负样本)。基本的思路:不断生成当前最好的规则(通过Gain参数【基于一条规则中新键值对的加入】判断),剔除掉已经包含的正样本,最后所有的规则合成一个集合。

对于多分类问题,解决办法:1 vs rest

image
image

时间复杂度:O(nkm|R|)

缺点:FOIL没有达到很高的准确度,其原因是:生成的规则比较少。

3.2 PRM:Predictive Rule Mining

相比于FOIL中剔除掉已经包含的正样本,PRM采取降低权重的方法(乘以一个因子),以此生成更多的规则,从而提高准确度。同时,通过PNArray来存储一些信息,来减少时间的开销。

PNArray所存储的信息:

  1. 与当前规则r匹配的正样本、负样本数量。
  2. 加入一个新的键值对literal p后,正样本、负样本的数量。
image

时间复杂度: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)(采用拉普拉斯预期误差估计)

image

4.2 分类

选取每个类的最好k条作预测,步骤如下:

  1. 选取该样本所有与主体匹配的规则。
  2. 对于每一个类,选取最好k条。
  3. 比较每个类的平均预测准确度,选择最高的类。

5.参考文献:

CPAR: Classification based on Predictive Association Rules,Xiaoxin Yin

相关文章

  • CPAR论文

    摘要 -> 传统的分类方法(C4.5,FOIL,RIPPER):速度更快,但大多数情况下准确度不高 -> 关联分类...

  • CPAR算法

    CPAR算法 1.关联规则分类的步骤 一般而言,关联规则分类包括以下步骤: 挖掘数据,得到频繁项集。 分析频繁项集...

  • 2018-05-08

    论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文过了!论文...

  • 6.29

    明天继续早起,然后看论文写论文看论文看论文明天继续早起,然后看论文写论文看论文看论文明天继续早起,然后看论文写论文...

  • 论文!论文!

    写论文无疑也是半个折磨,论文里的用语要十分规范,论文中的思路也要特别清晰,语句要一板一眼,不可以用过多的修饰,写论...

  • 论文论文论文!

    生产外包的分类包括OEM、ODM 和 OBM 几种不同的合作模式。其中: OEM(原始设备制造),即原始设备制造商...

  • 推荐系统论文阅读(三十)-微信:深度反馈网络-DFN

    论文: 论文题目:《Deep Feedback Network for Recommendation》 论文地址:...

  • 联系客服

    服务范围:论文写作,职称论文论文发表,论文降重,论文修改,外文翻译等 微信客服: 电...

  • FPN:feature pyramid networks for

    论文:feature pyramid networks for object detection论文链接 论文概述...

  • 推荐系统论文阅读(三)-阿里巴巴个性化重排序算法

    论文原文 论文题目:《Personalized Re-ranking for Recommendation》 论文...

网友评论

      本文标题:CPAR论文

      本文链接:https://www.haomeiwen.com/subject/imtrmftx.html