本章內容
- 發現事務數據中的公共模式
- FP-growth算法
- 發現Twitter源中的共現詞
你用過搜索引擎嗎？輸入一個單詞或者單詞的一部分，搜索引擎就會自動補全查詢詞項。用戶甚至事先都不知道搜索引擎推薦的東西是否存在，反而會去查找推薦詞項。我也有過這樣的經歷，當我輸入以「為什麼」開始的查詢時，有時會出現一些十分滑稽的推薦結果。為了給出這些推薦查詢詞項，搜索引擎公司的研究人員使用了本章將要介紹的一個算法。他們通過查看互聯網上的用詞來找出經常在一塊出現的詞對1。這需要一種高效發現頻繁集的方法。
1. J. Han, J. Pei, Y. Yin, R. Mao, 「Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,」 Data Mining and Knowledge Discovery 8 (2004), 53–87.
本章會在上一章討論話題的基礎上進行擴展，將給出一個非常好的頻繁項集發現算法。該算法稱作FP-growth，它比上一章討論的Apriori算法要快。它基於Apriori構建，但在完成相同任務時採用了一些不同的技術。這裡的任務是將數據集存儲在一個特定的稱作FP樹的結構之後發現頻繁項集或者頻繁項對，即常在一塊出現的元素項的集合FP樹。這種做法使得算法的執行速度要快於Apriori，通常性能要好兩個數量級以上。
上一章我們討論了從數據集中獲取有趣信息的方法，最常用的兩種分別是頻繁項集與關聯規則。第11章中介紹了發現頻繁項集與關鍵規則的算法，本章將繼續關注發現頻繁項集這一任務。我們會深入探索該任務的解決方法，並應用FP-growth算法進行處理，該算法能夠更有效地挖掘數據。這種算法雖然能更為高效地發現頻繁項集，但不能用於發現關聯規則。
FP-growth算法只需要對數據庫進行兩次掃瞄，而Apriori算法對於每個潛在的頻繁項集都會掃瞄數據集判定給定模式是否頻繁，因此FP-growth算法的速度要比Apriori算法快。在小規模數據集上，這不是什麼問題，但當處理更大數據集時，就會產生較大問題。FP-growth只會掃瞄數據集兩次，它發現頻繁項集的基本過程如下：
- 構建FP樹
- 從FP樹中挖掘頻繁項集
下面先討論FP樹的數據結構，然後看一下如何用該結構對數據集編碼。最後，我們會介紹兩個例子：一個是從Twitter文本流中挖掘常用詞，另一個從網民網頁瀏覽行為中挖掘常見模式。