關聯規則挖掘：FP-Growth算法

jopen 8年前發布 | 9K 次閱讀 Java開發

FP-Growth算法不同于Apriori算法的“產生-測試”模型，而是使用一種稱作FP樹的緊湊數據結構組織數據，并直接從該結構中提取頻繁項集。

FP-Growth算法步驟：

1）導出頻繁一項集。

數據庫的第一次掃描與Apriori相同，它導出頻繁1項集的集合和支持度計數。頻繁項的集合按支持度計數的遞減序排列。結果列表記作L。

2）構造FP樹

然后，FP樹的構造如下。首先，創建樹的根節點，用“null”標記。第二次掃描數據庫D。每個事務中的項按L中的次序處理（即按支持度計數遞減序）并對每個事務創建一個分枝。一般地，當為一個事務考慮增加分枝時，沿著共同前綴上的每個節點的計數增加1，為在前綴后的項創建節點和鏈接。

為方便樹遍歷，創建一個項頭表，使每項通過一個節點鏈指向它在樹中的位置。這樣，數據庫頻繁模式的挖掘問題就轉換成挖掘FP樹問題。

3）挖掘FP樹

FP樹的挖掘過程如下。由每個長度為1的頻繁模式（初始后綴模式）開始，構造它的條件模式基（一個“子數據庫”，由FP樹中與后綴模式一起出現的前綴路徑集組成），然后，構造它的條件FP樹，并遞歸地對該樹進行挖掘。模式增長通過后綴模式與條件FP樹產生的頻繁模式連接實現。

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！