FP Tree算法原理是什么

FP Tree算法原理是什么，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

Apriori算法是挖掘頻繁項(xiàng)集的經(jīng)典算法，需要多次掃描數(shù)據(jù)，I/O是很大的瓶頸。為了解決這個(gè)問(wèn)題，F(xiàn)P Tree算法（也稱FP Growth算法）采用了一些技巧，無(wú)論多少數(shù)據(jù)，只需要掃描兩次數(shù)據(jù)集，因此提高了算法運(yùn)行的效率。下面我們就對(duì)FP Tree算法做一個(gè)總結(jié)。

1. FP Tree數(shù)據(jù)結(jié)構(gòu)

　　　　為了減少I/O次數(shù)，F(xiàn)P Tree算法引入了一些數(shù)據(jù)結(jié)構(gòu)來(lái)臨時(shí)存儲(chǔ)數(shù)據(jù)。這個(gè)數(shù)據(jù)結(jié)構(gòu)包括三部分，如下圖所示：

　　　　第一部分是一個(gè)項(xiàng)頭表。里面記錄了所有的1項(xiàng)頻繁集出現(xiàn)的次數(shù)，按照次數(shù)降序排列。比如上圖中B在所有10組數(shù)據(jù)中出現(xiàn)了8次，因此排在第一位，這部分好理解。第二部分是FP Tree，它將我們的原始數(shù)據(jù)集映射到了內(nèi)存中的一顆FP樹(shù)，這個(gè)FP樹(shù)比較難理解，它是怎么建立的呢？這個(gè)我們后面再講。第三部分是節(jié)點(diǎn)鏈表。所有項(xiàng)頭表里的1項(xiàng)頻繁集都是一個(gè)節(jié)點(diǎn)鏈表的頭，它依次指向FP樹(shù)中該1項(xiàng)頻繁集出現(xiàn)的位置。這樣做主要是方便項(xiàng)頭表和FP Tree之間的聯(lián)系查找和更新，也好理解。

　　　　下面我們講項(xiàng)頭表和FP樹(shù)的建立過(guò)程。

2. 項(xiàng)頭表的建立

　　　　FP樹(shù)的建立需要首先依賴項(xiàng)頭表的建立。首先我們看看怎么建立項(xiàng)頭表。

　　　　我們第一次掃描數(shù)據(jù)，得到所有頻繁一項(xiàng)集的的計(jì)數(shù)。然后刪除支持度低于閾值的項(xiàng)，將1項(xiàng)頻繁集放入項(xiàng)頭表，并按照支持度降序排列。接著第二次也是最后一次掃描數(shù)據(jù)，將讀到的原始數(shù)據(jù)剔除非頻繁1項(xiàng)集，并按照支持度降序排列。

　　　　上面這段話很抽象，我們用下面這個(gè)例子來(lái)具體講解。我們有10條數(shù)據(jù)，首先第一次掃描數(shù)據(jù)并對(duì)1項(xiàng)集計(jì)數(shù)，我們發(fā)現(xiàn)O，I，L，J，P，M, N都只出現(xiàn)一次，支持度低于20%的閾值，因此他們不會(huì)出現(xiàn)在下面的項(xiàng)頭表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列，組成了我們的項(xiàng)頭表。

　　　　接著我們第二次掃描數(shù)據(jù)，對(duì)于每條數(shù)據(jù)剔除非頻繁1項(xiàng)集，并按照支持度降序排列。比如數(shù)據(jù)項(xiàng)ABCEFO，里面O是非頻繁1項(xiàng)集，因此被剔除，只剩下了ABCEF。按照支持度的順序排序，它變成了ACEBF。其他的數(shù)據(jù)項(xiàng)以此類推。為什么要將原始數(shù)據(jù)集里的頻繁1項(xiàng)數(shù)據(jù)項(xiàng)進(jìn)行排序呢？這是為了我們后面的FP樹(shù)的建立時(shí)，可以盡可能的共用祖先節(jié)點(diǎn)。

　　　　通過(guò)兩次掃描，項(xiàng)頭表已經(jīng)建立，排序后的數(shù)據(jù)集也已經(jīng)得到了，下面我們?cè)倏纯丛趺唇P樹(shù)。

3. FP Tree的建立

　　　　有了項(xiàng)頭表和排序后的數(shù)據(jù)集，我們就可以開(kāi)始FP樹(shù)的建立了。開(kāi)始時(shí)FP樹(shù)沒(méi)有數(shù)據(jù)，建立FP樹(shù)時(shí)我們一條條的讀入排序后的數(shù)據(jù)集，插入FP樹(shù)，插入時(shí)按照排序后的順序，插入FP樹(shù)中，排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，而靠后的是子孫節(jié)點(diǎn)。如果有共用的祖先，則對(duì)應(yīng)的公用祖先節(jié)點(diǎn)計(jì)數(shù)加1。插入后，如果有新節(jié)點(diǎn)出現(xiàn)，則項(xiàng)頭表對(duì)應(yīng)的節(jié)點(diǎn)會(huì)通過(guò)節(jié)點(diǎn)鏈表鏈接上新節(jié)點(diǎn)。直到所有的數(shù)據(jù)都插入到FP樹(shù)后，F(xiàn)P樹(shù)的建立完成。

　　　　似乎也很抽象，我們還是用第二節(jié)的例子來(lái)描述。

　　　　首先，我們插入第一條數(shù)據(jù)ACEBF，如下圖所示。此時(shí)FP樹(shù)沒(méi)有節(jié)點(diǎn)，因此ACEBF是一個(gè)獨(dú)立的路徑，所有節(jié)點(diǎn)計(jì)數(shù)為1, 項(xiàng)頭表通過(guò)節(jié)點(diǎn)鏈表鏈接上對(duì)應(yīng)的新增節(jié)點(diǎn)。

　　　　接著我們插入數(shù)據(jù)ACG，如下圖所示。由于ACG和現(xiàn)有的FP樹(shù)可以有共有的祖先節(jié)點(diǎn)序列AC，因此只需要增加一個(gè)新節(jié)點(diǎn)G，將新節(jié)點(diǎn)G的計(jì)數(shù)記為1。同時(shí)A和C的計(jì)數(shù)加1成為2。當(dāng)然，對(duì)應(yīng)的G節(jié)點(diǎn)的節(jié)點(diǎn)鏈表要更新

　　　　同樣的辦法可以更新后面8條數(shù)據(jù)，如下8張圖。由于原理類似，這里就不多文字講解了，大家可以自己去嘗試插入并進(jìn)行理解對(duì)比。相信如果大家自己可以獨(dú)立的插入這10條數(shù)據(jù)，那么FP樹(shù)建立的過(guò)程就沒(méi)有什么難度了。

4. FP Tree的挖掘

　　　　我們辛辛苦苦，終于把FP樹(shù)建立起來(lái)了，那么怎么去挖掘頻繁項(xiàng)集呢？看著這個(gè)FP樹(shù)，似乎還是不知道怎么下手。下面我們講如何從FP樹(shù)里挖掘頻繁項(xiàng)集。得到了FP樹(shù)和項(xiàng)頭表以及節(jié)點(diǎn)鏈表，我們首先要從項(xiàng)頭表的底部項(xiàng)依次向上挖掘。對(duì)于項(xiàng)頭表對(duì)應(yīng)于FP樹(shù)的每一項(xiàng)，我們要找到它的條件模式基。所謂條件模式基是以我們要挖掘的節(jié)點(diǎn)作為葉子節(jié)點(diǎn)所對(duì)應(yīng)的FP子樹(shù)。得到這個(gè)FP子樹(shù)，我們將子樹(shù)中每個(gè)節(jié)點(diǎn)的的計(jì)數(shù)設(shè)置為葉子節(jié)點(diǎn)的計(jì)數(shù)，并刪除計(jì)數(shù)低于支持度的節(jié)點(diǎn)。從這個(gè)條件模式基，我們就可以遞歸挖掘得到頻繁項(xiàng)集了。

　　　　實(shí)在太抽象了，之前我看到這也是一團(tuán)霧水。還是以上面的例子來(lái)講解。我們看看先從最底下的F節(jié)點(diǎn)開(kāi)始，我們先來(lái)尋找F節(jié)點(diǎn)的條件模式基，由于F在FP樹(shù)中只有一個(gè)節(jié)點(diǎn)，因此候選就只有下圖左所示的一條路徑，對(duì)應(yīng){A:8,C:8,E:6,B:2, F:2}。我們接著將所有的祖先節(jié)點(diǎn)計(jì)數(shù)設(shè)置為葉子節(jié)點(diǎn)的計(jì)數(shù)，即FP子樹(shù)變成{A:2,C:2,E:2,B:2, F:2}。一般我們的條件模式基可以不寫(xiě)葉子節(jié)點(diǎn)，因此最終的F的條件模式基如下圖右所示。

　　　　通過(guò)它，我們很容易得到F的頻繁2項(xiàng)集為{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。遞歸合并二項(xiàng)集，得到頻繁三項(xiàng)集為{A:2,C:2,F:2}，{A:2,E:2,F:2},...還有一些頻繁三項(xiàng)集，就不寫(xiě)了。當(dāng)然一直遞歸下去，最大的頻繁項(xiàng)集為頻繁5項(xiàng)集，為{A:2,C:2,E:2,B:2,F:2}

　　　　F挖掘完了，我們開(kāi)始挖掘D節(jié)點(diǎn)。D節(jié)點(diǎn)比F節(jié)點(diǎn)復(fù)雜一些，因?yàn)樗袃蓚€(gè)葉子節(jié)點(diǎn)，因此首先得到的FP子樹(shù)如下圖左。我們接著將所有的祖先節(jié)點(diǎn)計(jì)數(shù)設(shè)置為葉子節(jié)點(diǎn)的計(jì)數(shù)，即變成{A:2, C:2,E:1 G:1,D:1, D:1}此時(shí)E節(jié)點(diǎn)和G節(jié)點(diǎn)由于在條件模式基里面的支持度低于閾值，被我們刪除，最終在去除低支持度節(jié)點(diǎn)并不包括葉子節(jié)點(diǎn)后D的條件模式基為{A:2, C:2}。通過(guò)它，我們很容易得到D的頻繁2項(xiàng)集為{A:2,D:2}, {C:2,D:2}。遞歸合并二項(xiàng)集，得到頻繁三項(xiàng)集為{A:2,C:2,D:2}。D對(duì)應(yīng)的最大的頻繁項(xiàng)集為頻繁3項(xiàng)集。

　　　　同樣的方法可以得到B的條件模式基如下圖右邊，遞歸挖掘到B的最大頻繁項(xiàng)集為頻繁4項(xiàng)集{A:2, C:2, E:2,B:2}。

　　　　繼續(xù)挖掘G的頻繁項(xiàng)集，挖掘到的G的條件模式基如下圖右邊，遞歸挖掘到G的最大頻繁項(xiàng)集為頻繁4項(xiàng)集{A:5, C:5, E:4,G:4}。

　　　　E的條件模式基如下圖右邊，遞歸挖掘到E的最大頻繁項(xiàng)集為頻繁3項(xiàng)集{A:6, C:6, E:6}。

　　　　C的條件模式基如下圖右邊，遞歸挖掘到C的最大頻繁項(xiàng)集為頻繁2項(xiàng)集{A:8, C:8}。

　　　　至于A，由于它的條件模式基為空，因此可以不用去挖掘了。

　　　　至此我們得到了所有的頻繁項(xiàng)集，如果我們只是要最大的頻繁K項(xiàng)集，從上面的分析可以看到，最大的頻繁項(xiàng)集為5項(xiàng)集。包括{A:2, C:2, E:2,B:2,F:2}。

　　　　通過(guò)上面的流程，相信大家對(duì)FP Tree的挖掘頻繁項(xiàng)集的過(guò)程也很熟悉了。

5. FP Tree算法歸納

　　　　這里我們對(duì)FP Tree算法流程做一個(gè)歸納。FP Tree算法包括三步：

　　　　1）掃描數(shù)據(jù)，得到所有頻繁一項(xiàng)集的的計(jì)數(shù)。然后刪除支持度低于閾值的項(xiàng)，將1項(xiàng)頻繁集放入項(xiàng)頭表，并按照支持度降序排列。

　　　　2）掃描數(shù)據(jù)，將讀到的原始數(shù)據(jù)剔除非頻繁1項(xiàng)集，并按照支持度降序排列。

　　　　3）讀入排序后的數(shù)據(jù)集，插入FP樹(shù)，插入時(shí)按照排序后的順序，插入FP樹(shù)中，排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，而靠后的是子孫節(jié)點(diǎn)。如果有共用的祖先，則對(duì)應(yīng)的公用祖先節(jié)點(diǎn)計(jì)數(shù)加1。插入后，如果有新節(jié)點(diǎn)出現(xiàn)，則項(xiàng)頭表對(duì)應(yīng)的節(jié)點(diǎn)會(huì)通過(guò)節(jié)點(diǎn)鏈表鏈接上新節(jié)點(diǎn)。直到所有的數(shù)據(jù)都插入到FP樹(shù)后，F(xiàn)P樹(shù)的建立完成。

　　　　4）從項(xiàng)頭表的底部項(xiàng)依次向上找到項(xiàng)頭表項(xiàng)對(duì)應(yīng)的條件模式基。從條件模式基遞歸挖掘得到項(xiàng)頭表項(xiàng)項(xiàng)的頻繁項(xiàng)集。

　　　　5）如果不限制頻繁項(xiàng)集的項(xiàng)數(shù)，則返回步驟4所有的頻繁項(xiàng)集，否則只返回滿足項(xiàng)數(shù)要求的頻繁項(xiàng)集。

6. FP tree算法總結(jié)

　　　　FP Tree算法改進(jìn)了Apriori算法的I/O瓶頸，巧妙的利用了樹(shù)結(jié)構(gòu)，這讓我們想起了BIRCH聚類，BIRCH聚類也是巧妙的利用了樹(shù)結(jié)構(gòu)來(lái)提高算法運(yùn)行速度。利用內(nèi)存數(shù)據(jù)結(jié)構(gòu)以空間換時(shí)間是常用的提高算法運(yùn)行時(shí)間瓶頸的辦法。

　　　　在實(shí)踐中，F(xiàn)P Tree算法是可以用于生產(chǎn)環(huán)境的關(guān)聯(lián)算法，而Apriori算法則做為先驅(qū)，起著關(guān)聯(lián)算法指明燈的作用。除了FP Tree，像GSP，CBA之類的算法都是Apriori派系的。

看完上述內(nèi)容，你們掌握FP Tree算法原理是什么的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！