数据挖掘概念和技术Chapter6ppt课件

1、数据发掘: 概念和技术 Chapter 6 张晓辉 复旦大学 国际数据库研讨中心第6章：从大数据库中发掘关联规那么n关联规那么发掘n从买卖数据库中发掘一维的布尔形关联规那么n从买卖数据库中发掘多层次关联规那么n在买卖数据库和数据仓库中发掘多维关联规那么n从关联发掘到相关性分析n基于约束的关联发掘n小结什么是关联发掘?n关联规那么发掘：n在买卖数据、关系数据或其他信息载体中，查找存在于工程集合或对象集合之间的频繁方式、关联、相关性、或因果构造。n运用：n购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。n举例： n规那么

2、方式： “Body Head support, confidence.nbuys(x, “diapers) buys(x, “beers) 0.5%, 60%nmajor(x, “CS) takes(x, “DB) grade(x, “A) 1%, 75%关联规那么：根本概念n给定: (1)买卖数据库 (2)每笔买卖是：一个工程列表 (消费者一次购买活动中购买的商品)n查找: 一切描画一个工程集合与其他工程集合相关性的规那么nE.g., 98% of people who purchase tires and auto accessories also get automotive servi

3、ces donen运用n* 护理用品 (商店应该怎样提高护理用品的销售？)n家用电器 * (其他商品的库存有什么影响?)n在产品直销中运用附加邮寄nDetecting “ping-ponging of patients, faulty “collisions规那么度量：支持度与可信度n查找一切的规那么 X & Y Z 具有最小支持度和可信度n支持度, s, 一次买卖中包含X 、 Y 、 Z的能够性n可信度, c, 包含X 、 Y的买卖中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%, 最小可信度为 50%, 那么

4、可得到A C (50%, 66.6%)C A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户关联规那么发掘：道路图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) 1%, 75%n单维 vs. 多维 关联 (例子同上)n单层 vs. 多层 分析n那个种类牌子的啤酒与那个牌子的尿布有关系?n各种扩展n相关性、因果分析n关

5、联并不一定意味着相关或因果n最大方式和闭合相集n添加约束n如, 哪些“小东西的销售促发了“大家伙的买卖？第6章：从大数据库中发掘关联规那么n关联规那么发掘n从买卖数据库中发掘一维的布尔形关联规那么n从买卖数据库中发掘多层次关联规那么n在买卖数据库和数据仓库中发掘多维关联规那么n从关联发掘到相关性分析n基于约束的关联发掘n小结关联规那么发掘一个例子对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的根本思想:频繁项集的任何子集也一定是频繁的交易ID购买商品2000A,B,

6、C1000A,C4000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%最小值尺度 50%最小可信度 50%关键步骤：发掘频繁集n频繁集:是指满足最小支持度的工程集合n频繁集的子集也一定是频繁的n如, 假设AB 是频繁集，那么 A B 也一定是频繁集n从1到kk-频繁集递归查找频繁集n用得到的频繁集生成关联规那么Apriori算法n衔接: 用 Lk-1自衔接得到Ckn修剪: 一个k-项集，假设他的一个k-1项集他的子集 不是频繁的，那他本身也不能够是频繁的。n伪代码:nCk: Candidate itemset of size knLk : frequent item

7、set of size knL1 = frequent items;nfor (k = 1; Lk !=; k+) do beginn Ck+1 = candidates generated from Lk;n for each transaction t in database don increment the count of all candidates in Ck+1 that are contained in tn Lk+1 = candidates in Ck+1 with min_supportn endnreturn k Lk;Apriori算法 例子TID Items100

8、 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 Ditemset sup.1223334153itemset sup.12233353扫描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2扫描 DC3L3itemset2 3 5扫描 Ditemset sup2 3 52如何生成候选集n假定 Lk-1 中的项按顺序陈列n第一步: 自衔接 Lk-1 ninsert into Cknselect p.item1, p.item2, , p.itemk-1, q.itemk-1nf