1、費高雷 通信與信息工程學(xué)院 2015年春季,第6章 挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性：基本概念和方法,2,第6章：挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性： 基本概念和方法,基本概念 頻繁項集挖掘方法 那些模式是有趣的：模式評估方法 小結(jié),3,什么是頻繁模式分析?,頻繁模式: 頻繁出現(xiàn)在數(shù)據(jù)集中的模式（如項集、子序列或子結(jié)構(gòu)） 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD會議上提出，稱為頻繁項集和關(guān)聯(lián)規(guī)則挖掘 驅(qū)動:發(fā)現(xiàn)數(shù)據(jù)中的內(nèi)在規(guī)律 超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？ 啤酒和尿布 在買了一臺PC之后下一步會購買? 哪種DNA對這種藥物敏感? 我們?nèi)绾巫詣訉eb文檔

2、進行分類? 更加廣泛的用處 購物籃分析、交叉銷售、直銷 點擊流分析、DNA序列分析等等,什么是頻繁模式分析?,5,頻繁模式挖掘為什么重要?,頻繁模式: 數(shù)據(jù)集內(nèi)在和重要的屬性 許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ) 關(guān)聯(lián), 相關(guān), 和因果分析 序列模式,空間模式（比如子圖） 時空模式分析, 多媒體, 時間序列和流數(shù)據(jù) 分類: discriminative, frequent pattern analysis 聚類分析: 基于頻繁模式的聚類 數(shù)據(jù)倉庫: iceberg cube and cube-gradient 語義數(shù)據(jù)壓縮: fascicles 更廣泛應(yīng)用,6,關(guān)聯(lián)規(guī)則基本模型,設(shè)I=i1, , im為

3、所有項目的集合；D為事務(wù)數(shù)據(jù)庫，事務(wù)T是一個項目子集（TI）。每一個事務(wù)具有唯一的事務(wù)標(biāo)識TID 項集：由項目構(gòu)成的集合，為了方便表述用用A表示 事務(wù)T包含項集A，當(dāng)且僅當(dāng)AT 如果項集A中包含k個項目，則稱其為k項集 支持度：項集A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占D中總事務(wù)的百分比 頻繁項集（或大項集）：項集的支持度超過用戶給定的最小支持度閾值,I=a, b, c, d, e, f,若A=a, c，則A的支撐度為50%,項,屬性,一個事物,數(shù)據(jù)對象,7,關(guān)聯(lián)規(guī)則基本模型,關(guān)聯(lián)規(guī)則是形如XY的邏輯蘊含式，其中XI，YI，且XY= 如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含XY，則稱關(guān)聯(lián)規(guī)則XY的支持度為s

4、% 實際上，支持度是一個概率值，是一個相對計數(shù) support (XY)=P (X Y) 項集的支持度計數(shù)(頻率) support_count 包含項集的事務(wù)數(shù) 若項集X的支持度記為support (X)，規(guī)則的信任度為support (XY)support (X) 是一個條件概率P (Y | X) confidence (XY)=P (Y | X)=support _count(XY)support_count (X),8,頻繁模式和關(guān)聯(lián)規(guī)則,itemset X=x1, , xk 找出滿足最小支持度和置信度的所規(guī)則 X Y 支持度s：事務(wù)包含 XY的概率 置信度c：事務(wù)含X也包含Y的條件概率

5、,令supmin = 50%, confmin = 50% 頻繁模式：A:3, B:3, D:4, E:3, AD:3 關(guān)聯(lián)規(guī)則: A D (60%, 100%) D A (60%, 75%),9,挖掘關(guān)聯(lián)規(guī)則一個例子,規(guī)則 A C： 支持度 = support(AC) = 50% 置信度 = support(AC)/support(A) = 66.6%,最小支持度 50% 最小置信度 50%,挖掘關(guān)聯(lián)規(guī)則(實際例子),11,閉頻繁項集和極大頻繁項集,一個長模式包含子模式的數(shù)目：e.g., a1, , a100 contains (1001) + (1002) + + (110000) = 2

6、100 1 = 1.27*1030 sub-patterns! 解: 引入閉頻繁項集和極大頻繁項集 閉項集：不存在具有相同支持度的真超項集 閉頻繁項集：如果X是頻繁的，且不存在真超項集（super-pattern）Y（X Y），使 X、Y有相同的支持度計數(shù) (proposed by Pasquier, et al. ICDT99) 極大頻繁項集：如果X是頻繁的，并且不存在超項集Y使得X Y，并且Y是頻繁的 (proposed by Bayardo SIGMOD98) 兩者有不同，極大頻繁項集定義中對真超集要松一些,極大頻繁項集,Border,Infrequent Itemsets,Maxima

7、l Itemsets,極大頻繁項集的真超項集不頻繁,閉頻繁項集,最大頻繁項集存在的問題： 最大頻繁項集的子集是頻繁的，但無法推斷出其具體的支持度 閉頻繁項集的集合包含頻繁項集的完整信息（包括支持度） 例子：數(shù)據(jù)庫包含兩個事物，且令最小支持度為1 , 閉頻繁項集 a1, , a100: 1 a1, , a50: 2 最大頻繁項集 a1, , a100: 1 所有頻繁模式 a1: 2, , a1, a2: 2, , a1, a51: 1, , a1, a2, , a100: 1 A big number: 2100 - 1? Why?,閉頻繁項集和極大頻繁項集,Minimum support =

8、2,# Closed = 9 # Maximal = 4,Closed and maximal,Closed but not maximal,閉頻繁項集和極大頻繁項集,16,第6章：挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性： 基本概念和方法,基本概念 頻繁項集挖掘方法 那些模式是有趣的：模式評估方法 小結(jié),17,頻繁項集挖掘方法,Apriori算法: 通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集 提高Apriori算法的效率 挖掘頻繁項集的模式增長方法 是用垂直數(shù)據(jù)格式挖掘頻繁項集 挖掘閉模式和極大模式,18,Apriori算法的步驟,Apriori算法命名源于算法使用了頻繁項集性質(zhì)的先驗（Prior）知識 Apriori

9、算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個步驟： 通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集 利用頻繁項集構(gòu)造出滿足用戶最小信任度的規(guī)則 挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分,19,頻繁項集,為了避免計算所有項集的支持度（實際上頻繁項集只占很少一部分），Apriori算法引入潛在頻繁項集的概念。 若潛在頻繁k項集的集合記為Ck，頻繁k項集的集合記為Lk則兩者之間滿足關(guān)系Lk Ck 構(gòu)成潛在頻繁項集所遵循的原則是“頻繁項集的子集必為頻繁項集”。,20,關(guān)聯(lián)規(guī)則的性質(zhì),性質(zhì)1：頻繁項集的子集必為頻繁項集 性質(zhì)2：非頻繁項集的超集一定是非頻繁的 Ap

10、riori算法運用性質(zhì)1，通過已知的頻繁項集構(gòu)成長度更大的項集，并將其稱為潛在頻繁項集 潛在頻繁k項集的集合Ck 是指由有可能成為頻繁k項集的項集組成的集合 以后只需計算潛在頻繁項集的支持度，而不必計算所有不同項集的支持度，因此在一定程度上減少了計算量,21,Apriori: 一種候選產(chǎn)生-測試方法,頻繁項集的任何子集必須是頻繁的 如果 啤酒, 尿布, 堅果 是頻繁的, 啤酒,尿布也是 每個包含 啤酒,尿布,堅果的事務(wù) 也包含 啤酒,尿布 Apriori 剪枝原則: 如果一個項集不是頻繁的, 將不產(chǎn)生/測試它的超集! 方法: 由長度為k的頻繁項集產(chǎn)生長度為 (k+1) 的候選項集, 并且 根據(jù)

11、 DB測試這些候選 性能研究表明了它的有效性和可伸縮性,22,Apriori 算法 一個例子,數(shù)據(jù)庫 TDB,第1次掃描,C1,L1,L2,C2,C2,第2次掃描,C3,L3,第3次掃描,23,Apriori算法,(1) L1=頻繁1項集; (2) for(k = 2; Lk-1 ; k+) do begin (3) Ck = apriori_gen(Lk-1); /新的潛在頻繁項集 (4) for all transactions t D do begin (5) Ct = subset(Ck, t); /找出t中包含的潛在的頻繁項 (6) for all candidates c Ct d

12、o (7) c.count +; (8) end; (9) Lk=c Ck | c.count minsup (10) end; (11) Answer=,24,Apriori的重要細(xì)節(jié),如何產(chǎn)生候選? 步驟 1: Lk的自連接 步驟 2: 剪枝 候選產(chǎn)生的例子 L3=abc, abd, acd, ace, bcd 自連接: L3*L3 abcd：由 abc 和 abd acde：由 acd 和 ace 剪枝: acde 被刪除, 因為 ade 不在 L3 C4=abcd,25,如何產(chǎn)生候選?,假定 Lk-1 中的項集已排序(按字典序排序) 步驟 1: Lk-1自連接 （參考書本p253） i

13、nsert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 Step 2: 剪枝,26,教材161頁 例6.3（支持計數(shù)=2）,27,例子,28,由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則,根據(jù)公式產(chǎn)生關(guān)聯(lián)規(guī)則 對于每個頻繁項集l，產(chǎn)生所有的非空子集頻繁 對于l的每個非空子集s，如果 則輸出規(guī)則”s (l-s)”,29,頻繁模式挖掘的挑戰(zhàn),挑戰(zhàn) 事務(wù)數(shù)據(jù)庫的多遍掃描 數(shù)量巨大的候選

14、 候選支持度計數(shù)繁重的工作量 改進 Apriori: 基本思想 減少事務(wù)數(shù)據(jù)庫的掃描遍數(shù) 壓縮候選數(shù)量 便于候選計數(shù),30,頻繁項集挖掘方法,Apriori算法: 通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集 提高Apriori算法的效率 挖掘頻繁項集的模式增長方法 是用垂直數(shù)據(jù)格式挖掘頻繁項集 挖掘閉模式和極大模式,31,提高Apriori算法的方法,Hash-based itemset counting（散列項集計數(shù)） Transaction reduction（事務(wù)壓縮） Partitioning（劃分） Sampling（采樣）,思路：降低掃描次數(shù)、提高每次掃描的效率,32,劃分: 只掃描數(shù)據(jù)庫兩次,

15、項集在DB中是頻繁的, 它必須至少在DB的一個劃分中頻繁 掃描 1: 劃分?jǐn)?shù)據(jù)庫, 并找出局部頻繁模式 local frequent itemset 掃描 2: 求出全局頻繁模式 A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB95,33,抽樣-頻繁模式,選取原數(shù)據(jù)庫的一個樣本, 使用Apriori 算法在樣本中挖掘頻繁模式 掃描一次數(shù)據(jù)庫, 驗證在樣本中發(fā)現(xiàn)的頻繁模式. 再次掃描數(shù)據(jù)庫, 找出遺漏的頻繁模式

16、犧牲一些精度換取有效性。 H. Toivonen. Sampling large databases for association rules. In VLDB96,34,基于散列的技術(shù),散列項集到對應(yīng)的桶中，一個其hash桶的計數(shù)小于閾值的k-itemset 不可能是頻繁的 J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining association rules. In SIGMOD95,35,動態(tài)集計數(shù): 減少掃描次數(shù),ABCD,ABC,ABD,ACD,BCD,AB,AC,BC,AD,BD,CD

17、,A,B,C,D,Itemset lattice,一旦確定 A 和 D 是頻繁的，立即開始 AD 的計數(shù) 一旦確定 BCD 的兩個長度為2的子集是頻繁的，立即開始BCD 的計數(shù),事務(wù),1-itemsets,2-itemsets,Apriori,1-itemsets,2-items,3-items,DIC,S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD97,36,頻繁項集挖掘方法,Apriori算

18、法: 通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集 提高Apriori算法的效率 挖掘頻繁項集的模式增長方法 是用垂直數(shù)據(jù)格式挖掘頻繁項集 挖掘閉模式和極大模式,37,主要步驟: 利用頻繁k-1項集產(chǎn)生候選的頻繁k項集Ck 掃描數(shù)據(jù)庫確定Ck 中的每一項是否為頻繁k項集 E.g. ,TID Items bought 100 f, a, c, d, g, i, m, p 200 a, b, c, f, l, m, o 300 b, f, h, j, o 400 b, c, k, s, p 500 a, f, c, e, l, p, m, n,Apriori,Apriori iteration C1 f,a,c,

19、d,g,i,m,p,l,o,h,j,k,s,b,e,n L1 f, a, c, m, b, p C2 fa, fc, fm, fp, ac, am, bp L2 fa, fc, fm, ,38,頻繁模式挖掘的瓶頸,多遍數(shù)據(jù)庫掃描是 昂貴的 挖掘長模式需要很多遍掃描, 并產(chǎn)生大量候選 挖掘頻繁模式 i1i2i100 掃描次數(shù): 100 候選個數(shù): (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 ! 瓶頸: 候選產(chǎn)生-測試 能夠避免候選產(chǎn)生嗎?,39,挖掘頻繁模式而不產(chǎn)生候選,使用局部頻繁的項, 由短模式增長產(chǎn)生長模式 “abc” 是頻繁模式 得

20、到包含 “abc”的所有事務(wù): DB|abc “d” 是 DB|abc 中的局部頻繁項 abcd 是頻繁模式,挖掘頻繁模式增長方法（FP-growth）：根據(jù)事物數(shù)據(jù)庫構(gòu)造頻繁模式樹（FP-tree），在頻繁模式樹上挖掘，實質(zhì)是把事物數(shù)據(jù)庫壓縮成FP-tree進行挖掘,40,由事務(wù)數(shù)據(jù)庫構(gòu)造FP-樹,min_support = 3,TID Items bought (ordered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b, m 300 b, f, h,

21、 j, o, w f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p,掃描 DB 一次, 找出頻繁 1項集 （單個項的模式） 按頻率的降序?qū)㈩l繁項排序, 得到 f-list 再次掃描 DB, 構(gòu)造 FP-樹,f-list=f-c-a-b-m-p,41,構(gòu)造FP-tree,Item frequency f 4 c 4 a 3 b 3 m 3 p 3,TID Items bought 100 f, a, c, d, g, i, m, p 200 a, b, c, f, l, m, o 300 b, f, h

22、, j, o 400 b, c, k, s, p 500 a, f, c, e, l, p, m, n,Step 1: 掃描數(shù)據(jù)庫構(gòu)造頻繁1項集L,L,f-list=f-c-a-b-m-p,42,TID Items bought (ordered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b, m 300 b, f, h, j, o f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c,

23、 a, m, p,Step 2: 第二遍掃描數(shù)據(jù)庫，對頻繁項進行排序,構(gòu)造FP-tree,43,f:1,c:1,a:1,m:1,p:1,f, c, a, m, p,f:2,c:2,a:2,b:1,m:1,p:1,m:1,f, c, a, b, m,NOTE: 每一條事物對應(yīng)到FP樹中的一條路徑,構(gòu)造FP-tree,Step 2:構(gòu)造FP樹,44,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,Step 2:構(gòu)造FP樹,f:3,c:2,a:2,b:1,m:1,p:1,m:1,f, b,b:1,c, b, p,c:1,b:1,p:1,f:3,c:2,a:2,

24、b:1,m:1,p:1,m:1,b:1,f, c, a, m, p,Node-Link,構(gòu)造FP-tree,45,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,Header Table Item head f c a b m p,Step 2:最終的FP樹,構(gòu)造FP-tree,46,頻繁模式挖掘步驟,可以按照f-list 將頻繁模式劃分成子集 f-list=f-c-a-b-m-p 包含 p的模式 包含 m 但不包含 p的模式 包含 c 但不包含 a, b, m, p 模式 f 完全性和非冗余性,47,構(gòu)造條件模式基,由長度為1的頻繁模式開始 收集頻繁項

25、 的所有前綴路徑，形成條件模式基,條件模式庫 item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1,48,從條件模式基到條件FP-樹,對于每個條件模式基 累計條件模式基中每個項的計數(shù) 構(gòu)造模式基中頻繁項的FP-樹（條件FP-樹）,m-條件模式基 : fca:2, fcab:1,m-條件FP-樹,m的所有頻繁模式 m, fm, cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,頭表 It

26、em frequency head f 4 c 4 a 3 b 3 m 3 p 3,49,從條件模式基到條件FP-樹,遞歸: 挖掘每個條件 FP-樹,“m”的條件FP-樹 (fca:3),add“a”,add“c”,add“f”,“am”的條件 FP-樹 (fc:3),“cm”的條件 FP-樹 (fa:3),“fm”的條件 FP-樹 (ca:3),“acm”的條件 FP-樹 (f:3),“afm”的條件 FP-樹 (c:3),add“c”,add“f”,51,特殊情況: FP-樹中的單個前綴路徑,假定 (條件) FP-樹 T 具有單個共享的前綴路徑P 挖掘可以分解成兩步 將單個前綴路徑歸約成

27、一個結(jié)點 連接兩部分的挖掘結(jié)果,+,52,使用FP-樹挖掘頻繁模式,基本思想: 頻繁模式增長 通過模式和數(shù)據(jù)庫劃分遞歸地增長頻繁模式 方法 對于每個頻繁項, 構(gòu)造它的條件模式基 然后構(gòu)造它的條件 FP-樹 在新構(gòu)造的條件FP-樹上重復(fù)這一過程 直到結(jié)果條件 FP-樹為空, 或者它只包含一條路徑單個路徑將產(chǎn)生其子路徑的所有組合, 每個子路徑是一個頻繁模式,53,FP-樹結(jié)構(gòu)的優(yōu)點,完全性 保留頻繁模式挖掘的完整信息 不截斷任何事務(wù)的長模式 壓縮性 壓縮無關(guān)信息非頻繁的項被刪除 項按頻率的降序排列: 越是頻繁出現(xiàn), 越可能被共享 絕對不比原來的數(shù)據(jù)庫大 (不計結(jié)點鏈和計數(shù)字段),54,FP-增長

28、vs. Apriori: 隨支持度增長的可伸縮性,Data set T25I20D10K,55,FP-增長 vs. 樹-投影:隨支持度增長的可伸縮性,Data set T25I20D100K,56,為什么FP-增長是贏家?,分治: 根據(jù)已經(jīng)得到的頻繁模式劃分任務(wù)和數(shù)據(jù)庫 導(dǎo)致較小的數(shù)據(jù)庫的聚焦的搜索 其它因素 沒有候選產(chǎn)生, 沒有候選測試 壓縮數(shù)據(jù)庫 : FP-樹結(jié)構(gòu) 不重復(fù)地掃描整個數(shù)據(jù)庫 基本操作局部頻繁項計數(shù)和建立子FP-樹, 沒有模式搜索和匹配,57,有關(guān)的其他方法,挖掘頻繁閉項集合和最大模式 CLOSET (DMKD00) 挖掘序列模式 FreeSpan (KDD00), Prefi

29、xSpan (ICDE01) 頻繁模式的基于限制的挖掘 Convertible constraints (KDD00, ICDE01) 計算具有復(fù)雜度量的冰山數(shù)據(jù)方 H-tree and H-cubing algorithm (SIGMOD01),58,頻繁項集挖掘方法,Apriori算法: 通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集 提高Apriori算法的效率 挖掘頻繁項集的模式增長方法 是用垂直數(shù)據(jù)格式挖掘頻繁項集 挖掘閉模式和極大模式,使用垂直數(shù)據(jù)格式挖掘頻繁項集,使用tid-list, 包含item的事務(wù)的標(biāo)識的集合 M. Zaki et al. New algorithms for fast d

30、iscovery of association rules. In KDD97 掃描一次數(shù)據(jù)集將水平格式數(shù)據(jù)轉(zhuǎn)化為垂直格式 通過頻繁k項集的tid-list的交集，計算對應(yīng)(k+1)項集的tid-list,60,頻繁項集挖掘方法,Apriori算法: 通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集 提高Apriori算法的效率 挖掘頻繁項集的模式增長方法 是用垂直數(shù)據(jù)格式挖掘頻繁項集 挖掘閉模式和極大模式,極大模式,頻繁模式 a1, , a100 包含 (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 頻繁子模式! 最大模式: 頻繁模式, 其真超模式都不是頻繁的 BCDE, ACD 是最大模式 BCD 不是最大模式,min_sup=2,挖掘極大模式,掃描1: 找出頻繁項 A, B, C, D, E 掃描2: 找出以下項集的支持度 AB, AC, AD, AE, ABCDE BC, BD, BE, BCDE CD, CE, DE, CDE 由于 BCDE 是最大模式,