多维关联规则算法.ppt

2003年4月21日星期一 3月24日 CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules —— CMAR: 基于多维类关联规则的精确有效分类算法 主讲人： 邓绪斌 分类器构造方法 决策树、规则学习、朴素贝叶斯… 缺点：一次考虑一个属性，效率难以提高； 过分适合数据，需要有效的剪枝方法； 多维类关联规则的方法：CBA、CAEP、ADT、CMAR 特点：同时考虑所有属性，在训练样本上挖掘频繁属性集和类标签之间的强关联规则用于以后的分类；（带类分布的FP-树） 问题： 如何有效地存取规则？ （CR-树） 规则如何有效地剪枝？ 给定训练样本，经常会产生很多规则；一些规则会被其它规则所蕴涵，需要剪去，如何确定规则间的蕴涵关系？（规则比较：属性集、置信度、支持度、相关度。） 当对一个新元组进行分类时，如何选择最有效的规则？ 和新元组匹配的规则可能有很多条，如何评判其好坏？(带权 统计) 关联规则分类方法描述 数据对象： obj=(a1,…,an),符合模式(A1,…An); Ai-属性：连续(数值)的或分类的，通过下列方法统一起来： 连续属性值按区间离散化，映射到连续正整数集合{0,1,2,…}。 分类属性值按给定排序方法排序(如：字典序)，映射到连续正整数集合{0,1,2,…}。 类标签集：C={c1,…,cm}; C为固定集合。 训练数据集T: T是训练数据对象集{objk}和类标签集C的笛卡儿积的子集: T {objk}×C 分类器 : 是对象集{objk}到C的函数: : {objk} ? C 给定一个数据对象obj,函数 返回obj的类标签: 。 关联规则分类方法描述 模式： 是属性-值对的集合，满足: 一个数据对象obj和模式 匹配， 给定训练数据集T，可算出形如： 的分类规则，P为模式，c为类标签。 T中和P匹配且有类标签c的数据对象总数，称为规则R的支持：sup(R);和P匹配的对象数称P的支持：sup(P); R的置信度: conf(R)=sup(R)/sup(P)。 CMAR算法轮廓 分两阶段： 根据训练样本T产生分类关联规则集并存储： 产生分类关联规则集； 规则存储； 规则剪枝。 取出分类关联规则对新数据对象进行分类。 取出和新数据对象匹配的规则(可能有多条)； 当多条规则的分类结果不同时，选择合适的规则； 用选定规则对新数据对象进行分类。 产生分类关联规则集-带类分布的FP-树 扫描T一遍，找出至少出现给定支持阈值次的属性-值对集合：F={ Ai , aij }。(F={aij })。 按支持计数对F降序排序； 再次扫描T，建带类分布的FP-树： for T中每个记录t do 按F中的顺序将t的在F中出现的属性-值对插入FP-树；最后插入的属性-值对将t的类标号(当t来自条件模式基时为类分布)同时插入(累加结点的相应类分布计数器)；(每个结点初始化时类分布计数器全0) 在FP-树上自底向上递归地产生频繁模式。 输出的是频繁模式及其类分布计数； 处理完一个属性-值对后，其有关结点的类分布要合并到父结点。 产生分类关联规则集-带类分布的FP-树 最小支持：2; a1?b2?c1?d3 输出模式：d3(C:2,A:1) 条件模式基：a1b2c1(C:1) a1b2(C:1) 条件FP-树：a1b2(C:1)c1(C:1) 但c1为非频繁分布，合并到父结点： 条件FP-树：a1b2(C:2) 该条件FP-树含单枝,且分布集中于叶结点，仅产生频繁模式：a1b2d3(C:2); 至此d3处理完成，将d3有关结点的分布合并到相应父结点; c1(A:1,B:1,C:1)不满足最小支持，将c1有关结点的分布合并到相应父结点; FP-树：a1(A:1)b2(B:1,C:2) 该FP-树含单枝，但分布不集中，产生： a1b2(B:1,C:2)；合并分布，有： FP-树：a1(A:1,B:1,C:2)。输出模式： a1(A:1,B:1,C:2)；规则产生结束。 规则存储-CR树 规则剪枝 为删除冗余或噪声信息,规则需剪枝。 规则