第12章 使用FP-growth算法來高效發(fā)現(xiàn)頻繁項集(代碼)
-
FP
-
優(yōu)點
因為 FP-growth 算法只需要對數(shù)據(jù)集遍歷兩次足淆，所以速度更快尝胆。
FP樹將集合按照支持度降序排序丧裁，不同路徑如果有相同前綴路徑共用存儲空間，使得數(shù)據(jù)得到了壓縮含衔。
不需要生成候選集煎娇。
比Apriori更快。
-
缺點
FP-Tree第二次遍歷會存儲很多中間過程的值抱慌，會占用很多內存逊桦。
構建FP-Tree是比較昂貴的。
-
適用數(shù)據(jù)類型
- 標稱型數(shù)據(jù)(離散型數(shù)據(jù))抑进。
FP-Tree算法全稱是FrequentPattern Tree算法强经，就是頻繁模式樹算法，他與Apriori算法一樣也是用來挖掘頻繁項集的寺渗，不過不同的是匿情，F(xiàn)P-Tree算法是Apriori算法的優(yōu)化處理兰迫，他解決了Apriori算法在過程中會產生大量的候選集的問題，而FP-Tree算法則是發(fā)現(xiàn)頻繁模式而不產生候選集炬称。但是頻繁模式挖掘出來后汁果，產生關聯(lián)規(guī)則的步驟還是和Apriori是一樣的。
-
創(chuàng)建FP樹步驟
創(chuàng)建根節(jié)點玲躯，用NULL標記据德。
統(tǒng)計所有的事務數(shù)據(jù)，統(tǒng)計事務中各個類型項的總支持度(在下面的例子中就是各個商品ID的總個數(shù))
依次讀取每條事務跷车，比如T1棘利， 1， 2朽缴， 5善玫，因為按照總支持度計數(shù)數(shù)量降序排列，輸入的數(shù)據(jù)順序就是2密强， 1茅郎， 5，然后掛到根節(jié)點上或渤。
-依次讀取后面的事務系冗，并以同樣的方式加入的FP樹中，順著根節(jié)點路徑添加薪鹦，并更新節(jié)點上的支持度計數(shù)毕谴。
-
-
Fp樹的數(shù)據(jù)挖掘
由長度為1 的頻繁模式開始，構造他的條件模式基（一個“子數(shù)據(jù)庫”距芬，由FP樹中與后綴模式一起出現(xiàn)的前綴路徑集組成）。
構造該初始后綴模式的條件FP樹循帐，并遞歸的在該樹上實現(xiàn)挖掘框仔。模式增長通過后綴模式與條件FP樹產生的頻繁模式連接實現(xiàn)。
-
Fp樹性質
(結點鏈性質)對于任何頻繁項ia拄养，從FP-tree的頭表對應ia項的頭指針(headof node_link)開始离斩，通過遍歷ia的結點鏈(node_link)可以挖掘出所有包含ia的頻繁模式。
(前綴路徑性質)為了計算以ia為后綴的頻繁模式瘪匿，僅僅需要在FP-tree中計算ia結點的前綴路徑跛梗，并且前綴路徑中每個結點的頻繁計數(shù)等于ia結點的頻繁計數(shù)。
(分段增長)設α為事務數(shù)據(jù)庫D中的一個項集棋弥，B是α的條件模式基核偿，而β是B中的一個項集，那么在D中α∪β的支持度等于B中β的支持度顽染。
(模式增長)設項α為事務數(shù)據(jù)D中的一個項集漾岳，B是α的條件模式基轰绵，13而β是B中的一個項集，那么α∪β為頻繁項集的充分必要條件是β也為頻繁項集尼荆。
(單路徑頻繁項集產生)如果FP-treeT包含一條單路徑P左腔，那么T包含的所有頻繁項集的集合可以通過枚舉路徑P中結點的所有可能組合得到，其支持度計數(shù)為組合中結點的支持度計數(shù)的最小值捅儒。
給定一個事務數(shù)據(jù)庫D,最小支持度閾值minσ和頻繁項頭表=<……>nLi,i,,i12液样。挖掘頻繁閉項集的問題可以分解為n個子問題：第j(1≤j≤n)個子問題是找到所有包含ijn+1?但不包含i(n1jkn)k+?<≤的頻繁閉項集。
可以看出巧还，后挖掘到的頻繁閉項集不可能包含先前找到的頻繁閉項集鞭莽，但是它可能被已有的一個頻繁閉項集所包含，因此在挖掘過程中要對新挖掘的候選頻繁閉項集進行檢驗狞悲。如果剛得到的候選頻繁閉項集X不是已有的一個頻繁閉項集的子集或者兩者的支持度不同撮抓，那么就說X通過了FCI超集檢測，是一個頻繁閉項集摇锋。如果X是一個頻繁閉項集丹拯，那么在X的條件模式基中不存在任何一個項i出現(xiàn)在每一個事務中。
如果Y是一個最大項集合(Y滿足：出現(xiàn)在X的條件模式基的每一個事務中荸恕，但Y的直接超集不滿足這一性質)乖酬，并且X∪Y通過了FCI超集檢測，那么X∪Y是一個頻繁閉項集融求。
-
單路徑候選頻繁閉項集：設i是X的條件模式基中的一個頻繁項目咬像，如果X的條件模式樹中只有一個結點N標記為i，并且N的所有祖先結點只有一個子女生宛，N若滿足下列三個條件之一：
N沒有子女县昂。
N有兩個以上的子女。
-
N有一個子女陷舅，它的支持度計數(shù)小于N的倒彰。
那么單路徑候選頻繁閉項集就是X∪Z，Z包含N和N的祖先(除根結點)莱睁。如果條件模式X的條件FP-tree存在單路徑待讳，在單路徑中提取候選頻繁閉項集的個數(shù)為單路徑中具有不等的頻度個數(shù)。
對單路徑候選頻繁閉項集Y仰剿，如果Y通過了FCI超集檢測创淡，則Y是一個頻繁閉項集。
X和Y是兩個頻繁項集且具有相同的支持度南吮。如果X?Y且Y是閉項集琳彩，那么不存在只包含X不包含Y?X的頻繁閉項集。
-
小節(jié)
FP算法是一種用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式有效的辦法
FP樹構建完成之后，可以通過查找元素項的條件基于及構建條件FP樹來發(fā)現(xiàn)頻繁項集
該過程不斷以更多元素作為條件重復執(zhí)行汁针，直到FP樹中只包含了一個元素為止
