数据挖掘2015必威体育精装版精品课程完整课件(第5讲)---关联规则挖掘的其它问题PPT.ppt

关联规则挖掘的其它问题 主要内容 基于多最小支持度的关联规则 关联规则的评价 支持度的分布 大多数数据集中支持度的分布都不平衡 一个零售数据集中支持度的分布 支持度的分布 如何合理设置最小支持度阈值minsup? minsup过高, 可能会丢失稀有的、令人感兴趣的项目 (如，贵重商品或耐用品)。 minsup过低, 则计算开销过大，结果项集过多。 使用单一的最小支持度效果不佳。 多最小支持度模型 每个项目都有一个最小支持度(Minimum Item Supports, MIS) 。 通过为不同的项目提供不同的MIS值，用户可以表达对不同规则的不同支持度的需求。 多最小支持度举例 MIS(Milk)=5%, MIS(Coke) = 3%,MIS(Broccoli)=0.1%, MIS(Salmon)=0.5% MIS({Milk, Broccoli}) = min (MIS(Milk), MIS(Broccoli)) = 0.1% 支持度不再满足反单调性 假设: Support(Milk, Coke) = 1.5% 且 Support(Milk, Coke, Broccoli) = 0.5% {Milk,Coke} 不频繁，但 {Milk,Coke,Broccoli} 频繁 MSapriori算法 按支持度升序排列项目 e.g.: MIS(1) = 10% MIS(2) = 20%  MIS(3) = 5% MIS(4) = 6% 顺序: 3, 4, 1, 2 对Apriori进行修改: L1 : 1-频繁项集（支持度 ? minMIS(i)） F1 : {i | sup(i) ? MIS(i)} C2 : 2-候选项集从F1，而不是L1中连接得到 举例 假设数据集包含100条事务，第一次扫描数据库得到如下项目的支持度: {3}.count = 6, {4}.count = 3, {1}.count = 9, {2}.count = 25. 则L1= {3, 1, 2}, and F1 = {3, 2} 由于4.count /n MIS(3) (= 5%)，故L1 中不包含4。 由于1.count /n MIS(1) (= 10%)，故F1中不包含1。 MIS(1) = 10% MIS(2) = 20%  MIS(3) = 5% MIS(4) = 6% 多最小支持度—Apriori性质 A Item MIS(I) Sup(I) A 0.10% 0.25% B 0.20% 0.26% C 0.30% 0.39% D 0.50% 0.05% E 3% 4.20% B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 多最小支持度—Apriori性质 A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE Item MIS(I) Sup(I) A 0.10% 0.25% B 0.20% 0.26% C 0.30% 0.39% D 0.50% 0.05% E 3% 4.20% 主要内容 基于多最小支持度的关联规则 关联规则的评价 挖掘各种关联规则 支持度-置信度框架的局限性 支持度的缺点在于许多潜在有意义的模式由于包含支持度小的项而被删去。 置信度的缺陷在于忽略了规则后件中项集的支持度。如咖啡和茶的问题。 置信度和支持度的失效 Example(Aggarwal Yu, PODS98) 5000名学生中 3000 打蓝球 3750吃稻米 2000 既打篮球又吃稻米 打篮球 ? 吃稻米 [40%, 66.7%] 被误导了， 因为吃稻米的学生总数为 75% ，高于 66.7%. 打篮球 ? 不吃稻米 [20%, 33.3%] 则更为精确, 尽管其支持度和置信度更低 感兴趣度的应用 Interestingness Measures Lift作为相关度量 称规则A－B的提升度 大于1，A和B正相关，A的出现意味着B的出现 等于1，A和B独立 小于1，A和B负相关，A的出现以往着B的减少 感兴趣度的类型很多 针对不同的应用，不同感兴趣度的效果不一样 兴趣度的度量列表 合适的感兴趣度 Piatetsky-Shapiro: 一个合适的感兴趣度应具备3个特性: 若A和B是统计独立的，则M(A,B) = 0 当P(A)和