apriori算法-广东工业大学精品课程.ppt

* * 基本概念和路线图 有效的和可伸缩的频繁项集挖掘方法 挖掘各种类型的关联规则 基于约束的关联挖掘 非二元属性的关联规则挖掘规则产生 关联规则的评估 序列模式 内容提要 协同计算与知识工程 * * 兴趣度度量 客观度量 两个流行的度量方法: 支持度和置信度 仅由最小支持度和最小信任度来衡量关联规则是不够的,由此也会产生包含大量冗余的和虚假的规则. 协同计算与知识工程 例1： 在5000个学生中 3000个打篮球 3750个喝麦片粥 2000个学生既打篮球又喝麦片粥 然而，打篮球 = 喝麦片粥 [40%, 66.7%]是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高 打篮球 = 不喝麦片粥 [20%, 33.3%]这个规则远比上面那个要精确，尽管支持度和置信度都要低的多 需要注意:并不是所有的强关联规则都是有用的或者有意义的。 * * 协同计算与知识工程 * * 如前面所知：支持度和置信度不足以过虑掉无趣规 则。为了处理这个问题，可以使用相关度量来扩充 关联规则的支持度-置信度框架，这导致如下形式 的相关规则： A ? B [support, confidence, correlation] 也就是说，相关规则不仅用支持度和置信度度量， 而且还用项集A和B之间的相关度量 协同计算与知识工程 兴趣度度量 * * 一种简单的相关度量: 兴趣度(相关,提升) 考虑P(A) 和P(B) lift(A,B)＝1，表明A与B无关， lift(A,B) 1表明A与B正相关， lift(A,B) 1表明A与B负相关，如果是负相关，则该规则为冗余规则。前面的例题中： A（打篮球）?B（吃谷类食品） P(A?B)＝2000/5000=0.4 P(A)=3000/5000=0.6 P(B)＝3750/5000=0.75 Lift(A,B)=0.4/(.6*.75)=0.891 所以是负相关，该关联规则冗余 协同计算与知识工程 * * 例：假定我们对分析涉及购买计算机和录象的事务感兴趣。设game表示包含计算机游戏的事务，而video表示包含录象的事务，在所分析的10000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录象，而4000个事务同时包含计算机游戏和录象。假定发现关联规则的数据挖掘程序对该数据运行，使用最小支持度30％，最小置信度60％。将发现下面的关联规则： Buy(Xgames ,”computer ”)?buy(X, “videos”) [support=40%,confidence=66%] 该规则是强关联规则，因为它的支持度和置信度大于最小支持度和最小置信度。但它是否是一个冗余规则。 协同计算与知识工程 关联规则评估 * * 设 表示不包含计算机游戏的事务， 表示不包含录象的事务。事务可以汇总在一个相依表中，如下表所示。 购买计算机游戏的概率P（{game})=0.6 购买录象的概率P（{video})=0.75 购买两者的概率P（{game,video})=0.4 Lift(game,video)=0.4/(0.75*0.60)=0.891 所以是负相关，该规则是冗余规则 game 行汇总 video 4000 3500 7500 2000 500 2500 列汇总 6000 4000 10000 协同计算与知识工程 关联规则评估 * 除了提升度外，还有其他的相关度的度量： 兴趣因子 相关系数 余弦 * 协同计算与知识工程 相关度的度量 * 辛普森悖论 规则{性别=男}→{录取=是}的置信度是209/304=68.8% 规则{性别=女}→{录取=是}的置信度是143/253=56.5% 这说明男生更有可能被录取。 性别 录取 总数 是 否 男 女 209 143 95 110 304 253 总数 352 205 557 辛普森悖论：对数据集按照某个变量进行分组后，之前对整个数据集分析得到的关联规则可能并不适用于分组。 * 协同计算与知识工程 * 辛普森悖论 对于法学院： confidence({性别=男}→{录取=是}) == 15.1% confidence({性别=女}→{录取=是}) == 33.6% 对于商学院： confidence({性别=男}→{录取=是}) == 80.1% confidence({性别=女}→{录取=是}) == 91.1% 置信度表明，对于每一个学院，女生更有可能录取，这与先前由包含两个学院的数据得到的结论恰好相反。 进行关联分析时，有的时候需要对数据进行适当的分组，才