FP-Growth演算法.ppt

1、,第 6 章關連分析：基本概念和演算法, 2008 台灣培生教育出版 (Pearson Education Taiwan),基本專有名詞,二元表示方式：購物籃資料可以被表示成二元格式項目集：在關聯分析中，一堆0 或更多項目被稱為一項目集支持個：其代表交易中包含特定項目集之數量,基本專有名詞,關規則：關聯規則為 XY 的表示式，X 和Y 為無交集的項目集，即 。強度由支持度（ support ）和信賴度（confidence）進行測量支持度，信賴度，,關規則探勘(1),給定交易集合T，找尋支持度最小支持度（minsup）且信賴度最小信賴度（minconf）的所有規則。最小支持度和最小信賴度代表的

2、是支持度和信賴度的門檻值以窮舉法（brute-force approach）探勘關聯規則時會計算每一可能規則的支持度和信賴度，初始步驟有助於改善關聯規則探勘演算法的執行，以減少計算支持度和信賴度的需求,關規則探勘(2),關聯規則探勘的演算法將問題切割成二個主要的子工作：高頻項目集的產生（Frequent Itemset Generation），尋找所有滿足最低支持度門檻值的項目集規則產生（Rule Generation），從前一步驟找到的高頻項目集中，萃取所有具有高信賴度的規則，這些規則被稱為強規則（strong rule）,高頻項目集的產生,晶格（lattice）結構可被用來列舉所有可能的項

3、目集合一個項目集 I = a,b,c,d,e 的晶格,Apriori 原則(1),若一項目集是高頻項目集，則他的所有子集合也必定是高頻的,Apriori 原則(2),若a,b是非高頻（infrequent）項目，則a,b的所有超集合也會是非高頻項目,Apriori 演算法中的高頻項目集產生,候選集的產生與刪除(1),候選集產生。這個步驟是以高頻 (k-1)-項目集為基礎，來產生新候選k-項目集。應該要避免產生太多不必要的候選集必須保證候選集合是完整的不應產生同樣的候選集合超過一次以上候選集刪除。這個步驟使用以支持度為基礎之刪除策略來淘汰一些候選k-項目集。,候選集的產生與刪除(2),產生候選集

4、的方法 窮舉法,圖 以窮舉法產生候選3-項目集,候選集的產生與刪除(3),產生候選集的方法 Fk-1 F1 法,圖 藉由合併高頻 (k-1)-項目集與一個高頻項目，以產生與刪除k-項目集。 要注意的是，有些候選集是不必要的，因他們的子集合是非高頻的,候選集的產生與刪除(4),產生候選集的方法 Fk-1 Fk-1 法,圖 藉由合併一對高頻 (k-1)-項目集來產生與刪除候選k-項目集,支持度計算,支持度計算是用來判斷在apriori-gen 函數的候選集刪除步驟中，留下來之每個候選集合的發生頻率,圖 列舉一筆交易t 中包含3 個項目的集合,使用雜湊樹做支持度計算,在支持度計算過程中，每一筆交易包

5、含的項目集合也會被雜湊至適合的桶子中此方式取代交易中每一項目與每一候選集的比較，而只將項目集合與其對應桶子中的候選集合做配對,計算的複雜度,Apriori 演算法的計算複雜度會被下列因素影響：支持門檻值項目的（維）交平均交寬1-高頻項目集的產生候選集產生支持計算,規則產生,規則是從一個高頻項目集產生所有這樣的規則必須滿足最低支持度門檻值以信賴度為基礎之刪除（confidence-based pruning）Apriori 演算法的規則產生,使用信賴度來刪除關聯規則,高頻項目集的精簡表示方式(1),最大高頻項目集：最大高頻項目集可被定義為一個高頻項目集，因它的最近超集合（immediate su

6、persets）沒有一個是高頻。封閉項目集：項目集X 是封閉的，若它的最近超集合與X 完全沒有相同的支持個數。封閉高頻項目集：一項目集為封閉高頻項目集，若它是封閉的且它的支持度大於或等於最小支持度。,高頻項目集的精簡表示方式(2),最大高頻項目集,高頻項目集的精簡表示方式(3),封閉高頻項目集,高頻項目集的精簡表示方式(4),高頻項目集、最大高頻項目集與封閉高頻項目集之間的關係,產生高頻項目集的替代方法,項目集晶格之走訪（traversal）：演繹法（ General-to-Specific）與歸納法（Specific-to-General ）等價別（equivalence class）廣優先

7、（breadth-first）與深優先（depth-first）交資集的表示方式當在計算候選項目集的支持度時，交易資料集的表示方式的選擇會影響I/O 成本,演繹法、歸納法以及雙向搜尋,等價別：字首樹與字尾樹,廣優先與深優先,使用深度優先方法產生候選項目集,水準與垂直的資料格式,FP-Growth 演算法,FP-growth 演算法以不同的方法來發掘高頻項目集不支持在Apriori 範例中的產生與測試（generate-and-test使用一個稱為FP-tree 的壓縮資料結構來對資料集做編碼，並從此結構中直接萃取出高頻項目集,FP-tree 的建構(1),FP-tree 是一種輸入資料的壓縮表

8、示方式,FP-tree 的建構(2),FP-Growth 演算法中的高頻項目集產生(1),FP-growth 為產生高頻項目集的演算法， 在FP-tree 中以由下至上（bottom-up）的方式進行探索,FP-Growth 演算法中的高頻項目集產生(2),FP-Growth 演算法中的高頻項目集產生(3),FP-growth 利用各個擊破（divide-and-conquer）策略將問題切割成多個小的子問題（subproblems），以尋找特定結尾之所有高頻項目集,FP-Growth 演算法中的高頻項目集產生(4),關聯樣式的評估,關聯分析演算法可產生大量可能的樣式（pattern）可透過統

9、計參數來建立透過主觀參數來建立視覺化以模版為基礎之方法（template-based approach）主觀興趣測指標（subjective interestingness measure）,客觀興趣測量(1),客觀測量是一種資料驅動方式（data-driven），以評估關聯樣式的品質，除了指定門檻值來過濾低品質樣式之外，它是領域獨立（domain-independent）並且需要來自使用者最小的輸入支持信賴架構之限制：現有之關聯規則探勘的建構，是依賴支持度和信賴度測量，以減少不感興趣的樣式興趣因素（interest factor）興趣因素的限制,客觀興趣測量(2),相關性分析相關性分析的限制

10、IS 測IS 測的限制其他的客觀興趣測量客觀測量中的一致性,客觀測量的特性(1),反轉特性（inversion property）：反向特性：當交換f11 與f00，和f10 與f01 的高頻個數時，若M 的值維持不變，則客觀測量M 在反向操作下是不變的。null addition 特性若測量值不會因為增加f00 而受影響，且在列聯表中的所有其他高頻個數皆保持一樣，則在null addition 操作下客觀測量M是不變的。,客觀測量的特性(2),尺特性（scaling property）：尺變性（scaling invariance property）：客觀測量M 在行列尺度操作下是不變的若M(T) = M(T)，其中T 是高頻個數（frequent counts）的列聯表 f11; f10; f01; f00 ，T是尺度高頻個數（scaled frequency counts）的列聯表k1k3 f11; k2k3 f10; k11k4 f01; k2k4 f00而k1, k2, k3, k4為正數。,偏態支持度分佈的影響,交叉支持樣式：交叉支持樣式為一項目集X=i1,i2,ik，其支持度比率 是小於使用者指定之門檻值c h,