《数据挖掘的概念与技术-北大》课件.ppt

关系数据库 面向对象数据库 文本数据 多媒体数据 异构数据 WWW数据 数据挖掘分类 ——挖掘技术 数据库技术 机器学习技术 统计技术 神经网络技术 可视化技术 …… 数据挖掘原理与方法 关联（Association） 反映一个事件和其他事件之间依赖或关联的知识 如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测 可以用关联规则的形式表示 规则形式： “Body ? Head [support, confidence]”. 举例： contains(T, “computer”) →contains(T, “software”) [support = 1%, confidence = 75%] age(X, “20..29”) ^ income(X, “20..29K”) → buys(X, “PC”) [2%, 60%] 应用： 业务相关性分析、交叉销售、产品目录设计等 关联规则（一） X ? Y 满足X中条件的数据库元组也满足Y中条件 规则兴趣度度量 支持度 置信度 强规则 同时满足最小支持度阈值和最小置信度阈值的规则 关联规则（二） 给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品) 查找: 所有描述一个项目集合与其他项目集合相关性的规则 E.g., 98% of people who purchase tires and auto accessories also get automotive services done 应用 * ? 护理用品 (商店应该怎样提高护理用品的销售？) 家用电器 ? * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄 规则度量：支持度与置信度 查找所有的规则 X Y ? Z 具有最小支持度和可信度 支持度 s, 一次交易中包含{X 、 Y 、 Z}的可能性 置信度 c, 包含{X 、 Y}的交易中也包含Z的条件概率 关联规则挖掘方法 对于 A ? C： support = support({A 、C}) = 50% confidence = support({A 、C})/support({A}) = 66.6% 关键步骤：挖掘频繁集 频繁集:是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 如, 如果{AB} 是频繁集，则 {A} {B} 也一定是频繁集 从1到k（k-频繁集）递归查找频繁集 用得到的频繁集生成关联规则 Apriori算法 连接: 用 Lk-1自连接得到Ck 修剪: 一个k-项集，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。 伪代码: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = {frequent items}; for (k = 1; Lk !=?; k++) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ?k Lk; Apriori算法 — 例子 如何生成候选集 假定 Lk-1 中的项按顺序排列 第一步: 自连接 Lk-1 insert into Ck select p.item1, p.item2, …, p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 第二步: 修剪 forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck 生成候选集的例子 L3={abc, abd, acd, ace, bcd} 自连接 : L3*L3 abc 和 abd 得到 abcd acd 和 ace 得到 acde 修剪: ade 不在 L3中，删除 acde C4={abcd} Apriori 够快了吗? — 性能瓶颈 Apriori算法的核心: 用频繁的(k – 1)-项集