《五课挖掘频繁项集的压缩表示》由会员分享，可在线阅读，更多相关《五课挖掘频繁项集的压缩表示（31页珍藏版）》请在金锄头文库上搜索。
1、第五课第五课挖掘频繁项集的压缩表示挖掘频繁项集的压缩表示数据挖掘数据挖掘技术技术2011图灵奖得主图灵奖得主Judea Pearln1937-n加州大学洛杉矶分校（UCLA）的计算机科学教授n将贝叶斯网络和概率方法引入人工智能的先驱之一n数学化因果模型的先驱之一niPhone的Siri语音识别nGoogle的无人驾驶汽车关联规则挖掘存在的问题关联规则挖掘存在的问题n在实际的关联规则挖掘中，得到的频繁项集的数量过于庞大，如挖掘 i1i2i100 n挖掘少量有代表性的项集:n可以满足问题的需要n或其它项集的信息可由这些项集导出主要内容主要内容n最大频繁项集最大频繁项集n频繁闭项集频繁闭项集最大频繁
2、项集BorderInfrequent ItemsetsMaximal Itemsetsn频繁项集n所有超集均不再频繁集合枚举树集合枚举树集合枚举树:A称为头，可能的扩展称为头，可能的扩展: t(A) = B,C,D,E可能的扩展可能的扩展: t(ABC) = D,EMaxMiner的思想nR. Bayardo. Efficiently mining long patterns from databases. SIGMOD98n每次产生集合枚举树的一层，如果可能就进行剪枝。 (ABCD)A (BCD)B (CD)C (D)D ()AB (CD)AC (D) AD ()BC (D)BD ()CD
3、()ABC (C)ABCD ()ABD () ACD ()BCD ()MaxMiner算法n生成第一个结点 N= , 其中 h(N)=且t(N)=A,B,C,D.n对N进行扩展, n若h(N)t(N)是频繁的, 则停止对N进行扩展.n若对it(N), h(N)i不频繁, 则在扩展N之前，从t(N)中删除i.n使用全局剪枝策略 (ABCD)全局剪枝n一旦确定了一个最大频繁项集，则删去所有h(N)t(N)为其子集的结点. (ABCD)A (BCD)B (CD)C (D)D ()AB (CD)AC (D) AD ()BC (D)BD ()CD ()ABC (C)ABCD ()ABD () ACD (
4、)BCD ()ExampleTidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDEF0A2B2C3D3E2F1Min_sup=2Max patterns:A (BCDE)B (CDE) C (DE)E ()D (E)ExampleTidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDE1AB1AC2AD2AE1Min_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()Max patterns:No
5、de AExampleTidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyBCDE2BCBDBEMin_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()Max patterns:BCDENode BExampleTidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyACD2Min_sup=2A (BCDE)B (CDE) C (DE)E ()D (E)AC (D) AD ()Max patterns:BCDEA
6、CDNode AC主要内容主要内容n最大频繁项集最大频繁项集n频繁闭项集频繁闭项集频繁闭项集频繁闭项集nI是频繁项集是频繁项集n不存在与不存在与I支持度相等的支持度相等的I的超集。的超集。最大频繁项集最大频繁项集 vs 频繁闭项集频繁闭项集Minimum support = 2# Closed = 9# Maximal = 4Closed and maximalClosed but not maximal最大频繁项集最大频繁项集 vs 频繁闭项集频繁闭项集基本概念基本概念nPasquier N, Bastide Y, Taouil R et al. Discovering Frequent C
7、losed Itemsets for Association Rules. ICDT99.n公共项集映射,f(T)=iI|t T, it -f(12)=f(1)f(2)=ACD BCE=Cn支持集, g(I)=tTDB | i I, it -g(AE)=g(A) g(E)=135 2345=35n项集C是一个闭项集,当且仅当h(C)=f(g(C)=C -f(g(AC)=f(135)=AC,故AC是闭项集n项集g称为闭项集C的生成子,当且仅当h(g)=C,且不存在 sg,使得h(s)=C. 5B 4C 4E 4A 3BC 3AE 2BE 4CE 3AC 3AB 2BCE 3ACE 2ABE 2A
8、BC 2ABCE 2闭项集与生成子n1-频繁项集作为1-生成子G1nfor(k=1; Gk; k+)连接Gk生成(k+1)-候选生成子CG(k+1);用min_sup剪枝；用生成子的性质剪枝； 得到G(k+1)；nFCk=h(Gk) ；A-CLOSE算法例子CLOSET算法基本性质nJ. Pei, et al. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets. DMKD00.Header tablenullc:4e:3f:3a:1d:1d:1a:1f:1a:1e:1基于基于FP-树挖掘频繁闭项集树挖掘频繁闭项
9、集挖掘包含d的闭项集TDBcefadeacefcfadceff_list:TDB|d (d:2)cefacfaF.C.I.: cfad:2TDB|a (a:3)cefecfF.C.I.: a:3TDB|ea (ea:2)cF.C.I.: ea:2TDB|f (f:4)ce:3cF.C.I.: cf:4, cef:3TDB|e (e:4)c:3F.C.I.: e:4局部频繁项目: c, f, a每个包含d的事务都包含c, f和a挖掘包含a但不含d的闭项集TDBcefadeacefcfadceff_list:TDB|d (d:2)cefacfaF.C.I.: cfad:2TDB|a (a:3)ce
10、fecfF.C.I.: a:3TDB|ea (ea:2)cF.C.I.: ea:2TDB|f (f:4)ce:3cF.C.I.: cf:4, cef:3TDB|e (e:4)c:3F.C.I.: e:4w包含fa, 但不包含dw包含ea, 但不包含d和fw包含ca, 但不包含d, e和fsup(fa)=sup(ca)=sup(cfad),所有包含fa或ca的闭项集都包含d挖掘包含f, 但不含a和d的闭项集TDBcefadeacefcfadceff_list:TDB|d (d:2)cefacfaF.C.I.: cfad:2TDB|a (a:3)cefecfF.C.I.: a:3TDB|ea (e
11、a:2)cF.C.I.: ea:2TDB|f (f:4)ce:3cF.C.I.: cf:4, cef:3TDB|e (e:4)c:3F.C.I.: e:4挖掘包含e, 但不含f,a和d的闭项集TDBcefadeacefcfadceff_list:TDB|d (d:2)cefacfaF.C.I.: cfad:2TDB|a (a:3)cefecfF.C.I.: a:3TDB|ea (ea:2)cF.C.I.: ea:2TDB|f (f:4)ce:3cF.C.I.: cf:4, cef:3TDB|e (e:4)c:3F.C.I.: e:4挖掘只包含c的闭项集nsup(c)=sup(cf), c不是闭
12、项集。n全体闭项集 acdf:2, a:3, ae:2, cf:4, cef:3, e:4CHARM算法nZaki MJ, Hsiao CJ. CHARM: An Efficient Algorithm for Closed Itemset Mining. SDM02 n使用数据库的垂直表示n同时搜索项集与事务id集合 Itemset-Tidset搜索树CHARM性质n设Xg(X)和Yg(Y)为两个itemset-tidset对，则： 若g(X)=g(Y),则h(X)=h(Y)=h(XY) 若g(X)g(Y),则h(X)h(Y),但h(X)=h(XY) 例子min_sup=3sup(DT)min_sup，删去删去D(2456)T(1356)A(1345)W(12345)C(123456)DT(56)DA(45)sup(DA)min_sup，删去删去DW(245)g(D)g(W), 新增DWg (D )g (C ), 用DC 取代DDC(2456)DWC(245)g (T ) g (A ), 新增TATA(135)g (T ) g (W ), 新增TWTW(135)TC(1356)TAC(135) TWC(135)g (T ) g (C )，用TC代替T。g (TAC) = g (TWC)，找出TAWC，删除TAC 和TWCTAWC(135)
