《数据挖掘概念和技术Chapter6》由会员分享，可在线阅读，更多相关《数据挖掘概念和技术Chapter6（36页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘概念和技术Chapter6Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第6章：从大数据库中挖掘关联规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关性分析n基于约束的关联挖掘n小结2001-11-62数据挖掘：概念和技术什么是关联挖掘?n关联规则挖掘：n在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。n应用：n购
2、物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。n举例： n规则形式： “Body Head support, confidence”.nbuys(x, “diapers”) buys(x, “beers”) 0.5%, 60%nmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%2001-11-63数据挖掘：概念和技术关联规则：基本概念n给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品)n查找: 所有描述一个项目集合与其他项目集合相关性的规则nE.g., 9
3、8% of people who purchase tires and auto accessories also get automotive services donen应用n* 护理用品 (商店应该怎样提高护理用品的销售？)n家用电器 * (其他商品的库存有什么影响?)n在产品直销中使用附加邮寄nDetecting “ping-pong”ing of patients, faulty “collisions”2001-11-64数据挖掘：概念和技术规则度量：支持度与可信度n查找所有的规则 X & Y Z 具有最小支持度和可信度n支持度, s, 一次交易中包含X 、 Y 、 Z的可能性n可
4、信度, c, 包含X 、 Y的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到nA C (50%, 66.6%)nC A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户2001-11-65数据挖掘：概念和技术关联规则挖掘：路线图n布尔 vs. 定量 关联 (基于 处理数据的类型)nbuys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60%nage(x, “30.39”) income(x, “42.48K”) buys(x, “PC”)
5、 1%, 75%n单维 vs. 多维 关联 (例子同上)n单层 vs. 多层 分析n那个品种牌子的啤酒与那个牌子的尿布有关系?n各种扩展n相关性、因果分析n关联并不一定意味着相关或因果n最大模式和闭合相集n添加约束n如, 哪些“小东西”的销售促发了“大家伙”的买卖？2001-11-66数据挖掘：概念和技术第6章：从大数据库中挖掘关联规则n关联规则挖掘n从交易数据库中挖掘一维的布尔形关联规则n从交易数据库中挖掘多层次关联规则n在交易数据库和数据仓库中挖掘多维关联规则n从关联挖掘到相关性分析n基于约束的关联挖掘n小结2001-11-67数据挖掘：概念和技术关联规则挖掘一个例子对于 A C：supp
6、ort = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的最小值尺度 50%最小可信度 50%2001-11-68数据挖掘：概念和技术关键步骤：挖掘频繁集n频繁集:是指满足最小支持度的项目集合n频繁集的子集也一定是频繁的n如, 如果AB 是频繁集，则 A B 也一定是频繁集n从1到k（k-频繁集）递归查找频繁集n用得到的频繁集生成关联规则2001-11-69数据挖掘：概念和技术Apriori算法n连接: 用 Lk-1自连接得到Ckn修剪: 一个k-项集，如
7、果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。n伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = 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
8、Lk+1 = candidates in Ck+1 with min_support endreturn k Lk;2001-11-610数据挖掘：概念和技术Apriori算法 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D2001-11-611数据挖掘：概念和技术如何生成候选集n假定 Lk-1 中的项按顺序排列n第一步: 自连接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 = 10n用Apriori提高 执行 冰山查询的效率n先计算低维n只有当所有的低维都满足预制时才计算高维2001-11-636数据挖掘：概念和技术
