1、Principles and Applications of Business IntelligenceChap 3 ： 关联分析 1Introduction to商务智能方法与应用第3章 关联分析Chapter 3: Association AnalysisPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 22关联关联若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则是寻找在同一个事件中出现的不同项的相关性，比如在一次购买活动中所买不同商品的相关性。关联分析即利用关联规则进行数据挖掘。关联规则是形式
2、如下的一种规则，“在购买计算机的顾客中，有30的人也同时购买了打印机”。从大量的商务事务记录中发现潜在的关联关系，可以帮助人们作出正确的商务决策。Principles and Applications of Business IntelligenceChap 3 ： 关联分析 33购物篮分析购物篮分析此类关联分析在零售业，如超市等得到广泛应用，企业可以获得注入产品间的关联，或者产品类别和购买这些类别的产品的顾客的统计信息之间的关联规则。-关联分析又称购物篮分析，在销售配货、商店商品的陈列设计、超市购物路线设计、产品定价和促销等方面得到广泛应用。Principles and Applicatio
3、ns of Business IntelligenceChap 3 ： 关联分析 44什么是关联挖掘什么是关联挖掘? ?关联规则挖掘：-在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联结构。应用：-购物篮分析、交叉销售、产品目录设计、 聚集和分类等。举例： -规则形式： “Body Head support, confidence”.-buys(x, “diapers”) buys(x, “beers”) 0.5%, 60%-major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%Principles and
4、Applications of Business IntelligenceChap 3 ： 关联分析 5主要内容 3.1 频繁模式与关联规则 3.2 频繁项集的典型挖掘方法 3.3 关联规则的生成方法 3.4 关联规则的其他类型 3.5 关联规则的兴趣度的其他度量Principles and Applications of Business IntelligenceChap 3 ： 关联分析 63.1 频繁模式与关联规则从交易数据库、关系数据库以及其他的数据集中发现项或对象的频繁模式（frequent patterns）、关联（ associations）的过程buys(x, “diapers
5、”) buys(x, “beers”) 0.5%, 60% Rao, Srikumar S. “Diaper-beer Syndrome,” Forbes, April 6, 1998. pp. 128130outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyes交易号交易号（TID）商品（商品（Items）1beer, diaper, nuts2beer, biscuit,
6、 diaper3bread, butter, cheese4beer, cheese, diaper, nuts5beer, butter, cheese, nutsPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 7交易数据库Transaction ID Items Bought2000A,B,C1000A,C4000A,D5000B,E,F I=A,B,C,D,E,F 2项集：vTransactional database u 每个交易：由顾客一次购买的商品（items）组成uI=i1, i2, , imu项
7、集(Itemset): x=ij1,ij2,ijp， ijiIu每个项集包含的项的个数，称为项集的长度，一个长度为k的项集又称为k项集。Principles and Applications of Business IntelligenceChap 3 ： 关联分析 8支持度（Support） 交易包含项集X的概率E.g. X=A , Y=A,B=ABv若support(X) =minsup ，则X称为频繁项集(frequent itemset)，也可以说X是频繁的.n设minsup = 50%A:3, B:3, D:4, E:3, AD:3TIDItems bought10A, B, D20
8、A, C, D30A, D, E40B, E, F50B, C, D, E, Fcount()support()100%|XXDPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 9闭合频繁项集 一个频繁项集X被称为闭合频繁项集（closed frequent itemset）当且仅当不存在任一个项集Y满足XY 且support(Y)=support(X)。闭合频繁项集X被称为是闭合的。 例如：- A是频繁的，但不是闭合的，因为support(AD)=support(A)，且A ADTIDItems bought1
9、0A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, FPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 10关联规则 给定两个项集X 和Y，关联规则是形如XY 的蕴含式- XI 称为规则的前件， YI 称为规则的后件，XY= 规则XY的支持度(support)support(XY）=support(XY) 规则XY的置信度(confidence)support()confidence()100%support()XYXYXPrinciples and Applicat
10、ions of Business IntelligenceChap 3 ： 关联分析 11Support and confidenceTransaction-idItems bought10A, B, D20A, C, D30A, E40B, E, F50B, C, D, E, F 关联规则：X Y support( X Y ) =support(X Y)=|TXY| / nE.g: X=A Y=Csupport(A C )=support(AC)=0.2X=A,D=AD Y=Csupport(AD C )=support=(ADC)=0.2Principles and Application
11、s of Business IntelligenceChap 3 ： 关联分析 12Support and confidenceTIDItems bought10A, B, D20A, C, D30A, E40B, E, F50B, C, D, E, F 置信度（confidence ）Confidence(X Y )=|TXY| / |TX|=sup(XY) / sup(X)A C (20%, 33%)AD C (20%, 50%)买尿片的买尿片的交易交易同时买啤酒和同时买啤酒和尿片的交易尿片的交易买啤酒的交易买啤酒的交易Principles and Applications of Busi
12、ness IntelligenceChap 3 ： 关联分析 13关联规则的挖掘 给定如下阈值- minimum support : minsup- Minimum confidence : minconf 发现所有形如X Y 的关联规则，满足- Support(X Y ) minsup- Confidence(X Y) minconfPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 143.2 频繁项集的典型挖掘方法 3.2.1 逐层发现算法AprioriApriori (Agrawal & SrikantVL
13、DB94) 3.2.2 无候选集发现算法FP-growth- Freq. pattern growth (FPgrowthHan, Pei & Yin SIGMOD00) 其他方法：其他方法：- Vertical data format approach (CharmZaki & Hsiao SDM02)- High dimensional dataset: TD-close (Liu, Han, et al. ICDE06)- Principles and Applications of Business IntelligenceChap 3 ： 关联分析 153.2.1 逐层发现算法Apr
14、iori 主要步骤1. k=12. 统计每个k项候选集的支持度，找出频繁的k项集：Lk3. 利用频繁的k项集生成k+1项候选集(Candidate itemset )：Ck+14. k=k+1; 转至步骤2Principles and Applications of Business IntelligenceChap 3 ： 关联分析 16示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B
15、3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2minsup = 2/4Principles and Applications of Business IntelligenceChap 3 ： 关联分析 17如何生成候选项集？ 性质1： 给定最小支持度阈值minsup，一个频繁项集的所有非空子集都是频繁的。- if beer, diaper is frequent, s
16、o is beer and diaper- If beer is not frequent, beer, diaper is not frequent Apriori 剪裁规则: 若存在某些项集是不频繁的，则这些项集的任何超集都是不频繁的，因而无须生成和测试。Principles and Applications of Business IntelligenceChap 3 ： 关联分析 1818 项集格项集格 上图是i1, i2, i3, i4的项集格（lattice），这种结构能枚举所有可能的项集。假设i2, i3, i4是频繁项集，那么它的所有子集i2，i3，i4，i2, i3，i2,i
17、4和i3, i4都是频繁的。反之，如i1, i2是非频繁的，它的所有超集i1, i2, i3，i1, i2, i4和i1, i2, i3, i4都是非频繁的。Principles and Applications of Business IntelligenceChap 3 ： 关联分析 19如何生成候选项集？ 假设每个Lk 中的项集的项都是按顺序排列的 步骤1: 两两组合 Lk 中项集生成 Ck+1 步骤2: 裁剪（pruning）Principles and Applications of Business IntelligenceChap 3 ： 关联分析 20如何生成候选项集？ 假设项
18、集的项按字母序排列： beer bread butter cheese diaper nutsPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 21如何生成候选项集？ 步骤1 a b c d a b c e 设p 和q 是Lk 中的两个项集, 满足时生成(k+1) 项集：p.item1=q.item1, , p.itemk-1=q.itemk-1, p.itemk q.itemkp.item1p.item2p.itemk-1p.itemkq.item1q.item2q.itemk-1q.itemkp.item1p
19、.item2p.itemk-1p.itemkq.itemkPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 22如何生成候选项集？步骤1 字母序：abcde L3=abc, abd, acd, ace, bcd- abcd from abc and abd- acde from acd and ace C4=abcd，acdeL3item1item2item3abcabdacdacebcdPrinciples and Applications of Business IntelligenceChap 3 ： 关联
20、分析 23如何生成候选项集？步骤2 删除那些包含非频繁k项集的(k+1) 项集E.g：L3=abc, abd, acd, ace, bcd， C4=abcd，acde 由于cde 不频繁，所以acde不可能频繁 C4=abcdPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 24Database TDB1st scanC1C2C22nd scanL33rd scanC3L1L2TidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3Items
21、etsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2Supmin = 2Principles and Applications of Business IntelligenceChap 3 ： 关联分析 2525Apriori Apriori 性能瓶颈性能瓶颈 Apriori算法的核心:- 用频繁的(k 1)-项集生成候选的频繁 k-项集- 用数据库扫描和模
22、式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成- 巨大的候选集:- 多次扫描数据库： 如果最长的模式是n的话，则需要 n +1次数据库扫描FPFP增长算法增长算法 与Apriori算法不同，频繁模式增长（frequent pattern growth）算法，简称FP增长算法使用一种称为FP树的数据结构，并且采用分而治之的策略，无需产生候选频繁项集就能得到全部的频繁项集。Principles and Applications of Business IntelligenceChap 3 ： 关联分析 263.2.2 无候选集发现算法FP-growth FPgrowthHan, P
23、ei & Yin SIGMOD00 采用一种树的数据结构（FP-tree）来实现频繁项集的发现，不需要先生成候选项集 FP-tree的特点- 完整性保留了用于挖掘频繁项集的所有信息- 紧凑性减少了与频繁项集挖掘无关的信息，F-list: 高频项更多机会被不同交易共享永远小于原来的交易数据库TIDItems bought 100f, a, c, d, g, i, m, p200a, b, c, f, l, m, o300 b, f, h, j, o, w400 b, c, k, s, p500 a, f, c, e, l, p, m, n Principles and Applications
24、of Business IntelligenceChap 3 ： 关联分析 27算法： FP-growthHeader TableItem frequency head f4c4a3b3m3p3minsup = 3/51. 扫描交易数据库，找出所有频繁单项2. 按照支持度降序排列所有频繁单项，得到f-list3. 扫描交易数据库，构建FP-tree T4. 调用mineTree(T, f-list=f-c-a-b-m-pf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1FP-treeTID (ordered) frequent items100 f, c, a, m, p200
25、 f, c, a, b, m300 f, b400 c, b, p500 f, c, a, m, p Principles and Applications of Business IntelligenceChap 3 ： 关联分析 28频繁项集的分割 频繁项集的集合可以分为若干个不相交的子集 例如：F-list=f-c-a-b-m-p- 所有包含p的项集- 含有m不包含p的项集- - 含有c 不含a, b, m, p的项集- 项fPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 29生成条件模式库(condit
26、ional pattern base) 从头表(header table)开始 通过指针链遍历 FP-tree 找到所有包含某项如p的分支 合并相同前缀路径，构成 p 条件模式库Conditional pattern basesitemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3FP-tree: T100 f, c, a, m, p200f, c,
27、 a, b, m300f, b400c, b, p500f, c, a, m, pPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 30mineTree(T, X)c:3Header TableItem frequency head c3Tpfcam: 2cb: 1以p为例：X=; 生成并输出频繁项集Xp=p, support=3 生成p的条件模式库 统计单项频率：c:3, f:2, a:2, m:2, b:1 为 条件模式库构建FP-tree: Tp X=p,调用mineTree(Tp, X)Principle
28、s and Applications of Business IntelligenceChap 3 ： 关联分析 33挖掘高维度数据集中的频繁项集Carpenter (Pan, et al. KDD03)- Mine data sets with small rows but numerous columns- Construct a bottom-up row-enumeration tree for efficient miningTD-close (Liu, Han, et al. ICDE06)- Mine data sets with small rows but numerous
29、columns- Construct a Top-down row-enumeration tree for efficient miningPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 34Mining Frequent Patterns from Very High Dimensional Data: A Top-Down Row Enumeration Approach Hongyan LiuTsinghua UniversityJiawei Han, Dong Xin, Zheng ShaoUnive
30、rsity of Illinois at Urbana-ChampaignPrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 35行枚举方法riABCD1a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d25a2b2c2d31/19/2022Minsup=2 Table T Transposed Tableitemsetrowseta11, 2, 3a24, 5b11, 2, 3, 4c11, 3c22, 4, 5d22, 3, 4Principles and Applications of Bu
31、siness IntelligenceChap 3 ： 关联分析 361/19/2022自上而下的挖掘策略1a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d25a2b2c2d313a1b1c124b1c2d225c234b1d245a2c2351514b123a1b1d2245c2234b1d2134b1124b1123a1b113512514523534512a1b11245134523451234b11235Minsup=312345Principles and Applications of Business IntelligenceChap 3 ： 关联分析 371
32、/19/2022自上而下、分而治之的递归挖掘345134523451234545a2c2245c214512455a2b2c2d325c2351513512523512351a1b1c1d12a1b1c2d23a1b1c1d24a2b1c2d213a1b1c124b1c2d234b1d214b123a1b1d2234b1d2134b1124b1123a1b112a1b11234b1Without 5With 5w/o 4With 45w/o 3With 345w/o 2With 2345w/o 1Divide-and-conquerPrinciples and Applications of
33、Business IntelligenceChap 3 ： 关联分析 383.3 关联规则的生成方法Principles and Applications of Business IntelligenceChap 3 ： 关联分析 39生成关联规则minconfslsuplsupsslconfidence-)()() )( ( 为每个频繁项集l, 生成非空子集s; 若满足 则输出规则：(l-s) s e.g： l=ABCD, s = D , (l-s)= ABC confidence(ABC D)=support(ABCD)/support(ABC)(Y)()|P() (XsupportXsu
34、pportXYYXconfidencePrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 40生成关联规则 minconf=80%vFor BCE：Confidence(BE C)80% Confidence(CE B)80% Confidence(B CE) 80% Confidence(E BC) 80% Confidence(C BE) 80% L1L2L3Principles and Applications of Business IntelligenceChap 3 ： 关联分析 41生成关联规则 mi
35、nconf=80%vFor BCE：Confidence(BE C)80% Confidence(CE B)80%v confidence(C BE): 80%L1L2L3Principles and Applications of Business IntelligenceChap 3 ： 关联分析 42生成关联规则For BCE， Confidence(BE C) 66.7%.play basketball not eat cereal 20%, 33.3% 更准确Principles and Applications of Business IntelligenceChap 3 ： 关联
36、分析 78信息管理学院相关分析强关联规则不一定是有趣的 分析购买计算机游戏和录像事务。在分析的 10 000个事务中，假设发现关联规则的数据挖掘程序在该数据上运行，使用最小支持度30%，最小置信度60%Principles and Applications of Business IntelligenceChap 3 ： 关联分析 79信息管理学院强关联规则不一定是有趣的对以下关联规则求支持度与置信度：buys（X，“computer games”） buys（X，“videos”） support=40%，confidence=66% 该规则为强关联规则，满足最小支持度和最小置信度阈值。 然
37、而，购买录像的可能性是75%，比66%大，所以计算机游戏和录像是负相关的，买其中一种实际上减少了买另一种的可能性相关分析Principles and Applications of Business IntelligenceChap 3 ： 关联分析 80信息管理学院相关分析由关联分析到相关分析 例如，P(game)=0.6， P(video)=0.75， P(game，video)=0.4，则 P(game，video)/（P(game) P(video)） =0.4/(0.60.75)=0.89 所以， game和video之间存在负相关)()()(,BPAPBAPcorrBAPrinci
38、ples and Applications of Business IntelligenceChap 3 ： 关联分析 81信息管理学院相关分析由关联分析到相关分析 值公式： 其中oij为联合事件观测频度eij为联合事件期望频度2211=crijijijijoee-ijijcount Aacount BbeN2Principles and Applications of Business IntelligenceChap 3 ： 关联分析 82信息管理学院由关联分析到相关分析222222-4000-45003500-3000=+450030002000-1500500-1000+=555.61
39、5001000观测值 期望值期望值2Principles and Applications of Business IntelligenceChap 3 ： 关联分析 83相关性度量 支持度、置信度之外 AB (support, confidence, correlation) 相关性度量- lift, cosine, 2, all_conf, coherencePrinciples and Applications of Business IntelligenceChap 3 ： 关联分析 84相关性度量：Lift Lift(增益,提升度)()()()() =( ) ( )( )( )(AB
40、)(BA)( )(A)lift ABlift BAP ABsup ABP A P Bsup A sup Bconfconfsup Bsup1: positively correlated=1: independent 1.正相关 222222000-15001000-1500500-10001500-1000=+=833.31500150010001000Principles and Applications of Business IntelligenceChap 3 ： 关联分析 99信息管理学院2Principles and Applications of Business IntelligenceChap 3 ： 关联分析 100
