【文章內(nèi)容簡(jiǎn)介】 PTree 項(xiàng) 條件模式基 條件 FPtree 生成的頻繁模式 I5 {(I2 I1:1),(I2 I1 I3:1)} I2:2,I1:2 I2 I5:2, I1 I5:2, I2 I1 I5:2 I4 {(I2 I1:1),(I2:1)} I2:2 I2 I4:2 I3 {(I2 I1:2,(I2:2),(I1:2)} I2:4,I1:2, I1:2 I2 I3:4, I1 I3:2, I2 I1 I3:2 I1 {(I2:4)} I2:4 I2 I1:4 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 53 挖掘 FPTree Procedure FP_growth(Tree,?) (1) If Tree contains a single path P then (2) for each bination (denote as ?) of the nodes in the path P (3) generate pattern ??? with support = minisup of nodes in ?。 (4) Else for each ai in the header of Tree { (5) generate pattern ?=ai ?? with support =。 (6) construct ?, s conditional pattern base and then ?’conditional FP_tree Tree?。 (7) IF Tree??248。 then (8) call FP_growth(Tree?, ?)。} 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 54 由事務(wù)數(shù)據(jù)庫(kù)構(gòu)建 FP樹(shù) {} 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 frequency head f 4 c 4 a 3 b 3 m 3 p 3 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, 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} 1. 掃描 DB一次 ,找到頻繁 1項(xiàng) (單一項(xiàng)模式 ) 2. 按支持度降序?qū)︻l繁項(xiàng)排序?yàn)? Flist 3. 再次掃描 DB,構(gòu)建 FPtree Flist=fcabmp 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 55 劃分模式和數(shù)據(jù)庫(kù) ? 頻繁模式根據(jù) Flist可以被劃分為若干子集 ? Flist=fcabmp ? 包含 p的模式 ? 包含 m 但包含 p的模式 ? … ? 包含 c 但丌包含 a ,b, m, p的模式 ? 模式 f ? 完整性 和 非冗余性 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 56 從 P的條件數(shù)據(jù)庫(kù)找出包含 P的模式 ? 從 FPtree的索引表的頻繁項(xiàng)開(kāi)始 ? 沿著每個(gè)頻繁項(xiàng) p的鏈接遍歷 FPtree ? 累積項(xiàng) p的所有轉(zhuǎn)換前綴路徑來(lái)形成的 p的條件模式基 條件模式基 項(xiàng) 條件模式基 c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} 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 frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 57 遞歸 : 挖掘每個(gè)條件 FPtree {} f:3 c:3 a:3 m條件 FPtree “am”的條件模式基 : (fc:3) {} f:3 c:3 am條件 FPtree “cm”的條件模式基 : (f:3) {} f:3 cm條件 FPtree “cam”的條件模式基 : (f:3) {} f:3 cam條件 FPtree 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 58 一個(gè)特例 : FPtree中的單一前綴路徑 ? 假定 (條件的 ) FPtree T 有一個(gè)共享的單一前綴路徑 P ? 挖掘可以分為兩部分 ? 將單一前綴路徑約簡(jiǎn)為一個(gè)結(jié)點(diǎn) ? 將兩部分的挖掘結(jié)果串聯(lián) ? a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 + a2:n2 a3:n3 a1:n1 {} r1 = 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 59 通過(guò) DB 投影 (Projection)使 FPgrowth可伸縮 ? FPtree 丌能全放入內(nèi)存 ?—DB 投影 ? 首先將一個(gè)數(shù)據(jù)庫(kù)劃分成一個(gè)由若干投影(Projected)數(shù)據(jù)庫(kù)組成的集合 ? 然后對(duì)每個(gè)投影數(shù)據(jù)庫(kù)構(gòu)建和挖掘 FPtree ? Parallel projection vs. Partition projection 技術(shù) ? Parallel projection is space costly 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 60 Partitionbased Projection ? Parallel projection 需要很多磁盤空間 ? Partition projection 節(jié)省磁盤空間 Tran. DB fcamp fcabm fb cbp fcamp pproj DB fcam cb fcam mproj DB fcab fca fca bproj DB f cb … aproj DB fc … cproj DB f … fproj DB … amproj DB fc fc fc cmproj DB f f f … 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 61 改進(jìn)途徑 ? 使用哈希表存儲(chǔ)候選 k項(xiàng)集的支持度計(jì)數(shù) ? 移除丌包含頻繁項(xiàng)集的事務(wù) ? 對(duì)數(shù)據(jù)采樣 ? 劃分?jǐn)?shù)據(jù) ? 若一個(gè)項(xiàng)集是頻繁的 ,則它必定在某個(gè)數(shù)據(jù)分區(qū)中是頻繁的 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 62 FPtree 結(jié)構(gòu)的優(yōu)點(diǎn) ? 完整性 ? 保持了頻繁項(xiàng)集挖掘的完整信息 ? 沒(méi)有打斷仸何事務(wù)的長(zhǎng)模式 ? 緊密性 ? 減少丌相關(guān)的信息 —丌頻繁的項(xiàng)沒(méi)有了 ? 項(xiàng)按支持度降序排列 : 越頻繁出現(xiàn) ,越可能被共享 ? 決丌會(huì)比原數(shù)據(jù)庫(kù)更大 (丌計(jì)結(jié)點(diǎn)鏈接和計(jì)數(shù)域 ) ? 對(duì) Connect4 數(shù)據(jù)庫(kù) , 壓縮比率可以超過(guò) 100 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 63 內(nèi)容提要 ? 引言 ? Apriori 算法 ? FPgrowth 算法 ? 并行關(guān)聯(lián)規(guī)則挖掘 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 關(guān)聯(lián)規(guī)則改進(jìn) ? 總結(jié) Three parallel algorithms: CD, DD, CaD based on Apriori Discovering frequent itemsets (1) is much more expensive than generating rules (2) Phase 1: Each node generates candidate kitemsets locally from the frequent (k1)itemsets ? how to partition? Phase 2: The match candidates itemsets and transactions collect the local counts ? how to distribute? Phase 3: determine the global counts for itemsets ? how to find? find frequent kitemsets and replicate in all nodes 并行關(guān)聯(lián)規(guī)則挖掘 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 64 kitemset An itemset having k items Lk Set of frequent kitemsets (those with minimum support) Each member of this set has 2 fields: itemset and support count Ck Set of candidate kitemsets (potentially frequent itemsets) Each member of this set has 2 fields: itemset and support count Pi Processor with idi Di The dataset local to the processor Pi D Ri The dataset local to the processor Pi after repartitioning Cik The candidate set maintained with the processor Pi during the kth pass (there are k items in each candidate) 并行關(guān)聯(lián)規(guī)則挖掘 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 65 Objective: minimizing munication Techniques: Straightforward parallelization of Apriori Carry out redundant duplicate putations in parallel to avoid munication Only requires municating count values (no data tuples are exchanged) Processors can scan the local data asynchronously in parallel 計(jì)數(shù)分布 CD 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 66 Algorithm: Pass 1: (1) Each processor Pi generates its local candidate itemset Ci1 depending on the items present in its local data partition Di (2) Develop and Exchange local counts Ci1 (3) Develop global support counts C1 計(jì)數(shù)分布 CD 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 67 Algorithm: Pass k1: (1) Pi generates the plete Ck using the plete Lk1 created at the end of pass (k1). Each processor has the identical Lk1 thus generates identical Ck and puts its count values in a mon order into a count array (2) Pi makes a pass over data partition Di and develop local support counts for candidates in Ck (3) Pi exchanges local Ck counts with all other processors to develop global Ck counts. All processors must synchronize. (4) Pi putes Lk from Ck (5) Pi independently decide to terminate or continue to the next pass 計(jì)數(shù)分布 CD 2020/11/4 史