数据挖掘-频繁模式.pdf

第七讲 关联规则第七讲 关联规则邓志鸿 北京大学信息科学技术学院2012年3月30日回顾?基本聚类方法?聚类结果展示?层次聚类方法?划分聚类方法?基于密度的聚类方法?性能评估?内在质量指标?外在质量指标回顾?层次聚类方法?特点?生成嵌套聚类的层次结构?最多执行N步（ N是样本数量）?在第t步，由ℜt-1生成ℜt?ℜt-1表示第t-1步生成的聚类结果?ℜt表示第t步生成的聚类结果?主要类型?凝聚聚类算法 (Agglomerative clustering algorithms) ?ℜ0={{x1},…,{xN}}, ℜN-1 ={{x1,…,xN}} and ℜ0∠ … ∠ℜN-1.?分裂聚类算法（Divisive clustering algorithms）?ℜ0={{x1,…,xN}},ℜN-1= {{x1},…,{xN}} and ℜN-1∠ … ∠ℜ0.回顾?划分聚类方法?问题描述?给定对象集合D，聚类数目k和目标函数F划分聚 类算法把D分割成k组，使得目标函数在这样的分割 下达到最优聚类－>极值问题?基本算法?K-means ?Bisecting K-means?Fuzzy C-means?每个样本属于所有聚类，只不过是隶属力度有所不同而已。

∑∑ =∈=kicoiicosimF1),(max F回顾?DBSCAN?Density Based Spatial Clustering of Applications with Noise?基于密度定义聚类?称密度相连的最大对象集合为一个聚类?噪声 (NoiseNoise)?称不在任何聚类中的对象为“噪声”边界对象 (border point) ?不是核心对象，但是在某个核心对象的 Eps邻域内课堂练习－1Distance Matrix:全链的聚类过程 注意：用距离度量邻近GAS算法内容? ?简介简介简介简介?基本概念?关联分析基本方法?基本内容?频繁模式挖掘?关联规则生成?多层关联规则?模式评估关联规则? 1993年SIGMOD大会上Agrawal等人首次提出?关联规则挖掘 (association rule mining) ? 目的：发现数据中内在的规律性?人们通常会同时购买什么样的商品？— Beer and diapers??购买微机后，接下来用户通常会有什么购物行为？?哪种DNA对某个新药敏感？? 应用?Basket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis, and DNA sequence analysis.? 核心任务核心任务? 频繁模式频繁模式 (Frequent pattern)? 在数据集（库）中频繁出现的模式（项集 (a set of items)、子序列 (subsequences)、 子结构 (substructures) 等）。

内容?简介? ?基本概念基本概念基本概念基本概念?频繁模式挖掘基本方法?基本内容?频繁模式挖掘?关联规则生成?多层关联规则?模式评估关联规则分析?Association Rule Analysis?给定事务集合，根据某些项的出现来预测其它项的出现Market-Basket transactionsTID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Example of Association Rules{Diaper} → {Beer}, {Milk, Bread} → {Eggs,Coke}, {Beer, Bread} → {Milk},隐含着内在关联，而非偶然现象基本概念?项项 (Item)?最小的处理单位?例如：Bread, Milk?事务事务 (Transaction)?由事务号和项集组成?例如：?事务数据库事务数据库?由多个事务组成由多个事务组成?项集项集 (Itemset)?一个或多个项 (item) 的集?例如：{Milk, Bread, Diaper}?k-项集 (k-itemset)?包含k个项的集合TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 基本概念?包含关系包含关系?令T为一事务，P为一项集。

称T包含P，如果P是T的子集?记T ⊇ P 或 P ⊆ T?支持度计数支持度计数 (Support count)?事务数据库中包含某个项集的事务的个数?例如： σ({Milk, Bread,Diaper}) = 2 ?支持度支持度 (Support)?事务数据库中包含某个项集的事务占事务总数的比例例如： s({Milk, Bread, Diaper}) = 2/5?频繁项集频繁项集 (Frequent Itemset)?令P为任何一个项集，称P为频繁项集，如果P的支持度不小于指 定的最小阈值 (minsupthreshold)TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 基本概念Example: Beer}{}Diaper,Milk{⇒4 . 052 |T|)BeerDiaper,,Milk(===σs67. 032 )Diaper,Milk()BeerDiaper,Milk,(===σσc?关联规则关联规则 (Association Rule)?表达形式：X → Y (s, c)?其中， X 和 Y 都是项集，s是规则的 支持度，c是置信度?例子： {Milk, Diaper} → {Beer} (0.4, 0.67)?规则评估度量指标规则评估度量指标?支持度－Support (s)?同时包含X和Y的事务占事务总数的比 例?置信度－Confidence (c)?在所有包含X的事务中包含Y的事务所 占比例TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 内容?简介?基本概念? ?关联分析基本方法关联分析基本方法关联分析基本方法关联分析基本方法? ?基本内容基本内容基本内容基本内容?频繁模式挖掘?关联规则生成?多层关联规则?模式评估关联规则分析－内容?给定一个事务数据库TD，关联规则挖掘的目标 是要找到所有支持度和置信度都不小于指定阈 值的规则。

支持度 ≥minsupthreshold?置信度 ≥minconfthreshold?穷举法 (Brute-force approach)?列出所有可能的规则?对每条规则计算其支持度和置信度?通过阈值minsup和minconf过滤无效规则可计算性？计算复杂性分析?给定 d 个不同项：?项集数目等于2d?所有可能的关联规则总数等于：1231111+−=⎥⎦⎤ ⎢⎣⎡⎟ ⎠⎞⎜ ⎝⎛−×⎟ ⎠⎞⎜ ⎝⎛=+−=−=∑∑dddkkdjjkdkdR如果如果 d=6 则则 R = 602 关联规则－分析Example of Rules:{Milk,Diaper} → {Beer} (s=0.4, c=0.67) {Milk,Beer} → {Diaper} (s=0.4, c=1.0) {Diaper,Beer} → {Milk} (s=0.4, c=0.67) {Beer} → {Milk,Diaper} (s=0.4, c=0.67) {Diaper} → {Milk,Beer} (s=0.4, c=0.5) {Milk} → {Diaper,Beer} (s=0.4, c=0.5)TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 思考• 所有规则都对应于把同一项集分成两个部分 {Milk, Diaper, Beer}• 源自同一项集的规则有相同的支持度，但是置信度不同•因此，我们可以分别处理对支持度和置信度的要求•X → Y s=s(X∪Y) c= s(X∪Y) / s(X) 关联规则分析?分两步执行： 1. 挖掘频繁项集 － 生成所有支持度≥ minsup的项集2. 构造规则 － 用每个频繁项集生成高置信度的规则 － 对频繁模式的每次分割（一分为二）就形成一条规则， 再判断该规则是否满足最小置信度阈值条件。

但是，挖掘频繁模式仍然是一个“计算昂贵”的 工作{Milk, Diaper, Beer} s=0.4{Milk} s=0.8{Milk} → {Diaper,Beer} s=0.4, c=0.4/0.8=0.5 关联规则分析 的核心内容?简介?基本概念? ?关联分析基本方法关联分析基本方法关联分析基本方法关联分析基本方法?基本内容? ?频繁模式挖掘频繁模式挖掘频繁模式挖掘频繁模式挖掘?关联规则生成?多层关联规则?模式评估频繁模式挖掘－重要性?发现数据集中的有价值的重要性质?是其它数据挖掘任务的基础?关联分析：Association rules analysis → Mining Frequent Itemset?因果分析：causality analysis?序列、结构模式：Sequential, structural (e.g., sub-graph) patterns?时空、多媒体、时间序列、流数据模式分析?分类?聚类?数据仓库?语义数据压缩?推荐系统等其他应用生成频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE给定给定d个项， 有个项， 有 2d个可能 的候选项集个可能 的候选项集生成频繁项集?穷举法 (Brute-force approach) ?网格中每个项集都是候选的频繁项集?通过扫描一次数据库，可以得到每个候选项集的支持度?比较每一条事务和每个候选项集?计算复杂度－O(NMw)?N为事务数目， M = 2d为候选项集， w为一次比较的计算代价TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke NTransactionsList of CandidatesMw生成频繁项集－策略?缩小候选项集的数量 (M)?完全搜索：M=2d?通过裁减技术减少M?缩小比较次数 (NM)?用不同的数据结构来存储后续项集和事务?避免比较每一对候选项集和事务?缩小比较代价 (w)?采用 DHP 和 vertical-based 挖掘技术缩小候选项集?Apriori 性质:?如果一个项集是频繁的，那么它的所有 子集都是频繁的。

也称为反单调性?Apriori 性质成立的原因如下：?任何一个项。