Apriori原理:如果某個項集是頻繁的，那麼它的所有子集都是頻繁的。
Apriori算法：
Apriori算法是有缺點的
缺點是：1.需要多次掃描資料庫 2.産生大量的候選頻繁集 3.時間和空間複雜度高。
從算法第3步可以看出，候選頻繁項集不一定是原始資料集中某一項的子集，即：x為頻繁項，y為頻繁項，{x，y}可以組成一個候選頻繁項集，但是原始資料集中不一定存在{x，y}的組合。這使得Apriori算法有大量時間浪費在無效的集合上。
FP樹增長算法是一種挖掘頻繁項集的算法。Apriori算法雖然簡單易實作，效果也不錯，但是需要頻繁地掃描資料集，IO費用很大。FP樹增長算法有效地解決了這一問題，其通過兩次掃描資料集建構FP樹，然後通過FP樹挖掘頻繁項集。
背景知識
1.什麼是項和項集?
比如我們在購物的時候，購物車内的每一件商品成為一項，若幹個項的集合成為項集。例如{啤酒，尿布}成為一個二進制項集。
2.什麼是支援度?
支援度是在所有的項集中{X,Y}出現的可能性。
例如：購買商品的資料是(表示4條購物資訊)：
①{啤酒，尿布,娃哈哈}
②{啤酒，友善面}
③{尿布,奶粉}
④{啤酒，尿布,洗髮乳}
在這組資料中,{啤酒，尿布}出現的可能性就是這裡面資料的機率。{啤酒，尿布}的支援度是2/4=50%.
{尿布,奶粉}的支援度是1/4=25%
3.什麼是頻繁項集?
我們首先設定一個最小門檻值A，支援度大于A的項集就是頻繁項集，小于A的項集被剔除。
比如 我們設定門檻值為30%,在上面的例子中{啤酒，尿布}就是頻繁項集，{尿布,奶粉}就要被剔除。
問題：如何求出頻繁項集?
首先構造FP樹
然後通過FP樹可以求出頻繁項集
FP算法
FP增長算法需要根據資料集生成FP樹，步驟如下：
步驟一：統計每個元素出現次數，保留頻繁元素（假設次數>3），按照元素出 現次數降序排序。
其中h,j,p,w,v,u,n,o,q,p,e,m的次數是小于等于3的.是以把它們去掉，然後把其他的字母按照次數從大到小排列。
步驟二：建構FP樹
通過上面的序列按照每一行進入樹根初始化樹葉。如果沒有相同的字母就重新建立葉子節點，每個葉子節點有字母其次數。
如圖所示
先插入(z,r)，再插入(z,x,y,s,t),再插入(z)，如圖
最後插完的結果是：
步驟三：FP樹中找到元素的字首路徑
以r為例，r的字首路徑為：以根結點為起點，結點r為終點的所有路徑。
先找到FP樹中所有“r”結點，然後從每一個“r”結點向根結點方向查找，找到的所有路徑就是“r”的字首路徑
然而，找到所有“r”結點，需要周遊整棵FP樹，這使得算法的時間複雜度會很高。
為了友善查找，可以用連結清單來加快尋找的字首路徑。
将FP樹中所有相同的結點用連結清單連接配接，可以将查找結點的時間複雜度從O(n)降到常數級。
通過上面的操作就得到了如下所示的資訊。
步驟四:根據字首路徑構造條件FP樹
t的條件FP樹如下：
t字首路徑中的頻繁元素包括{z：3，x：3，y：3}，這個數字表示對應的元素在原始資料集中和t一起出現的次數，如{z，t}出現3次，{x，t}出現3次，{y，t}出現3次。顯然，這些項集都是頻繁項集。
很容易發現，t的字首路徑也是一個資料集，生成t條件FP樹的過程，跟前面生成FP樹的過程相同，我們也可以在t的條件FP樹基礎上構造x的條件FP樹，對應的就是{t，x}的條件FP樹。
顯然，這是個遞歸的過程。
步驟5:遞歸構造下一層條件FP樹，直至條件FP樹為空.
總結：