基于类关联规则的分类 Classification Based on Class-Association Rules 赵东垒 符号学习研究组

引言 国际研究现状 基本概念的定义 基于类关联规则的分类(CMAR) 未来工作 参考文献 TD-FP-Growth挖掘类关联规则 规则剪枝 对测试数据分类 未来工作 参考文献

1. 引言 分类问题 关联规则是给定数据集中项之间的有趣联系. 通过分析给定的一个带有类别信息的数据集建立一个分类器. 预测未知类别信息的数据对象. 关联规则是给定数据集中项之间的有趣联系. 基于关联规则的分类, 是利用数据挖掘的方法挖掘数据集中的类关联规则, 然后建立分类器, 并对未知类别数据进行预测. 关联规则中右侧固定为类别的属性 A=a1, B=b2->class1

2. 国际研究现状(1) 1993年Agrawal, Imielinski和Swami [AIS93]提出了关联规则的挖掘, 一个流行的应用领域是购物篮分析. 1994年Agrawal和Srikant [AS94]提出了著名的Apriori算法, 它是一种有效的关联规则挖掘算法, 它探查逐级挖掘Apriori性质: 频繁项集的所有非空子集都应该是频繁的. 在第k次迭代(K>1), 它根据频繁K-项集, 形成频繁(k+1)-项集候选, 并扫描数据库一次, 找出完整的频繁(K+1)-项集L(k+1). 1998年Liu, Hsu和Ma [LHM98]提出了CBA算法, 它采用经典的Apriori算法挖掘训练集, 用满足要求的关联规则来构造分类器, 实验[LHM98]表明, CBA算法比C4.5有较好的测试精度. 1999年Dong, Zhang, Wong 和Li [LDR00]提出了CAEP算法, 使用项集支持度挖掘显露模式来构造分类器, 2000年Li, Dong, 和Rmamohanarao [LDR00]提出了基于跳跃显露模式JEP分类法. 1999年Meretakis和Wuthrich [MW99]将大项集应用于朴素贝叶斯分类, 实验[MW99]表明, 在测试精度上要优于C4.5, CBA和TAN(a Bayesian network extension of Naïve Bayes)

国际研究现状(2) 1999年Wang, Zhou和He [WZH99]提出了基于关联的决策树, 它首先产生满足置信度的所有关联规则, 然后以精度驱使约剪规则. 2000年Han, Pei和Yin [HPY00]提出FP-Growth算法, 它是一种不产候选的挖掘频繁项集方法, 实验[HPY00]表明, FP-Growth算法比Apriori算法获得更好的效率, 是目前最流行的挖掘频繁项集的算法. 2001年Li, Han和Pei [LHP01]提出了CMAR算法, 它是基于扩展FP-Growth算法来有效的挖掘类关联规则, 采用多条匹配的类关联规则来预测新的样例, 实验 [LHP01]表明, CMAR的测试精度优于C4.5和CBA. 2003年Yin和Han [YH03]提出了CPAR算法, 它扩展了FOIL算法, 产生了较小规模的关联规则, 引入了期望精度的方法来评价规则, 预测新的样例. 2005年Wang和Karypis [WK05]提出了HARMONY算法, 它直接产生覆盖样例具有最高置信度的类关联规则, 大大提高剪枝的效率.

3. 基本概念的定义 假设数据对象obj=(a1, a2, … , an), ai∈Ai, 其中Ai称为属性. 设C = {c1, c2, …, cm}. 数据集中的每个数据对象都存在一个类别标示cobj∈C. 对于每个样例, 我们可以看成是一个项Item的集合加上一个类别标识. 在这里项Item是一个属性--值对, 即Item = (Attribute, value). 设 P为一个模式P= Item1 … Itemk, c为类标识, 对于每条规则R: P -> c. 规则的支持度sup(R)和规则的置信度的conf(R)的定义: sup(R)=训练集中匹配模式P, 并且满足类标识为c的样例的个数. conf(R)=规则的支持度与训练集中匹配模式P的样例的个数的比值 conf(R)= sup(R)/sup(P) A:a1

4. 基于类关联规则的分类(CMAR) 基于类关联规则的分类(CMAR)主要包括四个步骤： 如果是连续的属性值, 需要将其离散化, 或者称数据的预处理. 挖掘所有的满足支持度和置信度的类关联规则. 基于已经产生的关联规则, 通过剪枝建立一个分类器. 利用分类器对未知类别数据进行分类. training set mining 数据预处理 挖掘 类关联规则 pruning results testing set 分类 建立分类器

4.1. 挖掘类关联规则 training data set T 给定数据集T, 首先由T生成FP-Tree. 通过TD-FP-Growth算法挖掘所有的满足支持度和置信度的类关联规则. 通过剪枝策略选取一个规则子集构成分类器. Header Table Header Table training data set T Item count link A:a1 4 A:a2 1 B:b1 B:b2 3 B:b3 C:c1 C:c2 C:c3 D:d1 D:d2 D:d3 Item count link A:a1 4 B:b2 3 C:c1 D:d3 ID A B C D Class 1 a1 b1 c1 d1 2 b2 d2 3 a2 b3 c2 d3 4 c3 5 Minsup=2

4.1.1 FP-Tree构造过程 4 A:a1,B:b2,C:c3,D:d3,C 5 A:a1,B:b2,C:c1,D:d3,C 1 A:a1,B:b1,C:c1,D:d1,A 3 A:a2,B:b3,C:c2,D:d3,A 2 A:a1,B:b2,C:c1,D:d2,B root Header Table Item count link A,a1 4 B,b2 3 C,c1 D,d3 3 A:1,B:1,C:1 4 A:1,B:1,C:2 2 A:1,B:1 1 A:1 1 C:1 A,a1 D,d3 1 A:1 1 B:1 2 B:1,C:1 3 B:1,C:2 C,c1 B,b2 2 B:1,C:1 1 B:1 1 C:1 C,c1 D,d3 1 C:1 Minsup=2 Minconf=50% D,d3 FP-Tree

4.1.2 TD-FP-Growth算法 item count link A,a1 3 B,b1 2 item count link A:a1->C sup(R)=2 conf(R)=50% Sub Header Table of C,c1 Sub Header Table of B,b2 B:b2->C sup(R)=2 conf(R)=66.7% item count link A,a1 3 B,b1 2 A:a1&&B:b2->C sup(R)=2 conf(R)=66.7% item count link A,a1 3 D:d3->C sup(R)=2 conf(R)=66.7% root A:a1&&D:d3->C sup(R)=2 conf(R)=100% Header Table B:b2 &&D:d3-->C sup(R)=2 conf(R)=100% Item count link A,a1 4 B,b2 3 C,c1 D,d3 4 A:1,B:1,C:2 3 A:1,B:1,C:1 3 B:1,C:2 1 C:1 A,a1 D,d3 A:a1&&B:b2&&D:d3->C sup(R)=2 conf(R)=66.7% 1 A:1 C,c1 B,b2 3 B:1,C:2 2 B:1,C:1 2 B:1,C:1 1 C:1 C,c1 D,d3 Minsup=2 Minconf=50% 1 C:1 D,d3 FP-Tree

4.1.3 存储类关联规则 ID Rule Support Confidence 1 abc->A 60 100% 2 abcd->A 70 80% 3 abe->B 4 bcd->C 50% CR-Tree

4.2. 规则剪枝(1) 一般的情况, 产生的类关联规则的数目是非常大的. 为了使后面的分类更加的有效, 剪掉一些规则, 以消除多余的噪声信息. 定义1: 设偏序关系R1 > R2当且仅当 conf(R1) > conf(R2). conf(R1) = conf(R2), sup(R1) > sup(R2). conf(R1) = conf(R2), sup(R1) = sup(R2).R1拥有的属性值对的项数比R2的少. 定义2: R1: P -> c相对于R2: P’-> c’更一般, 当且仅当P是P’的子集. 规则剪枝的步骤如下: 用更一般且有高置信度的规则剪掉那些特殊的低置信度的规则. 如给定规则R1和R2, 当R1比R2更一般且R1>R2, 则用R1剪掉R2. 选择具有正相关的规则. 对于规则R: P -> c计算P与c的χ2相关值. 我们选择χ2相关值超过阈值(3.84)的规则. 基于数据覆盖的剪枝.

规则剪枝(2) 当一条规则插入到CR-tree中的时候, 检索CR-tree看是否有规则用剪枝1约束能被剪掉或者能剪掉其它的规则. 对于规则R: P -> c计算P与c的χ2相关值. 选择χ2值大于阈值(3.84)且正相关的规则. 在类关联规则将要插入到CR-Tree时测试. f11>e11 c ┐c total P f11 f12 f11+f12 ┐P f21 f22 f21+f22 f11+ f21 f12+ f22 f11+f12+f21+f22 c ┐c total P e11 e12 e11+e12 ┐P e21 e22 e21+e22 e11+ e21 e12+ e22 e11+e12+e21+e22

规则剪枝(3) Algorithm1: Select rules based on database coverage Input: a set of rules and a coverage threshold δ Output : a subset of rules for classification 1. sort rules in the rank descending order; 2. for each data object in the training data set{ 3. cover-count = 0; 4. }//for 5. while both the training data set and rule ser are not empty{ 6. for each rule R in rank descending order{ 7. find all data objects matching rule R.; 8. If R can correctly classify at least one object{ 9. select R and increase the cover-count of those objects matching R by 1; 10. if its cover-count passes coverage thresholdδ{ 11. remove the data object; 12. }//if 13. }//if 14. }//for 15. }//while

4.3. 对测试数据分类 对于给定的任意一个样例, 找到匹配该样例的一个规则子集, 按规则的分类信息分成组, 同组的有相同的分类信息. 当所有的规则都属于同一组的时候, 得到的分类结果就是该组的类别. 当所有的规则不属于同一类别的时候, 计算各组的 权值,即 , 样例的类别与该值最大的那组的类别一致. T是训练集所含样例的个数

4.3.1. 匹配样例规则子集的选择 Algorithm2: Multiple-rule selection Input: A selected rule set generated by Algorithm 1, and a new tuple Output: A multiple-rule set 1. for each rule r in the selected rule set in sorted order { 2. If r matches the new tuple 3. If (the size of multiple-rule set < Coverage Threshold ) or (the confidence of the top rule in multiple-rule set minus r’s confidence < Confidence Difference Threshold ) { 4. Insert r into the multiple-rule set 5. }//if 6. }//if 7. }//for

5. 未来的工作 将pruning the specialized rules with lower ranks, 集成到挖掘过程里, 不产生由它将要被剪掉的规则或只产生部分, 这样会大大的加快算法的时间效率. 在未知样例预测时, 对所选规则的评价, 我们可以探索新的标准. 如熵等. 剪枝策略的研究, 考虑C4.5的剪枝策略能不能在这里适用. 对算法中的参数敏感性分析.

参考文献(部分) [LHP01] W. Li, J. Han, J. Pei, “CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules”, In ICDM’01, San Jose CA, pp.369-376, 2001. [LHM98] B. Liu, W. Hsu, Y. Ma, “Fast algorithms for mining association rules”, In KDD’98, New York, pp.80−86, 1998. [AS94] R. Agrawal, R. Srikant, “Integrating classification and association rule mining”, In VLDB’94, Santiago Chile, pp.487−499, 1994. [HPY00] J. Han, J. Pei , Y. Yin, “Mining frequent patterns without candidate generation”, In SIGMOD’00, Dallas, pp.1−12, 2000. [WTH02] K. Wang, L. Tang, J. Han, "Top Down FP-Growth for Association Rule Mining", In PAKDD'02, Taipei, pp.334-340, May 3-8 2002. [MW99] D. Meretakis, B. Wuthrich, "Extending Naïve Bayes Classifiers Using Long Itemsets", In KDD‘99, San Diego CA, pp. 165-174, Aug 1999. [WK05] J. Wang, G. Karypis, “HARMONY: Efficiently Mining the Best Rules for Classication”, In SDM’05, California USA, pp. xx-xx, April 2005 .

Think you ! Question?