程一艦

數據技術處

? ? ? 我們常說我們生活在信息時代，實際上，我們更多的還是生活在數據時代。因為從過去到現在累積了大量的數據，對數據的挖掘和分析也僅是從最近幾年大數據和人工智能技術的發展而興起。我們對現有數據價值的利用還遠低于數據本身擁有的價值。隨著數據在黨的十九屆四中全會中與勞動、資本、土地、知識、技術、管理等一起被列為生產要素，數據價值的挖掘將會越來越深入。數據挖掘在《Data Mining》一書中的解釋就是從大量數據中挖掘有趣模式和知識的過程。既然未來已來，我們就要順應時代發展，掌握必備技能。

? ? 在前面我們介紹了一種簡單的挖掘商品關聯性算法。今天要介紹的是更高效的FP-Growth算法(FP指的是Frequent Pattern)，它可以用到搜索詞提醒，常用詞，挖掘強關聯性商品，商品推薦等領域上。挖掘商品關聯系或者詞語之間的關聯性，需要做的事是構造各種商品組合然后分析出這種組合是否是高頻率出現。Apriori算法每產生一種組合都要遍歷一次數據庫來判斷當前組合是否是高頻記錄，這個在大量數據面前是很耗時間。

一、原理介紹

與Apriori算法相比，FP-Growth算法更進一步，通過將交易數據巧妙的構建出一顆FP樹，然后在FP樹中遞歸的對頻繁項進行挖掘。FP-Growth算法僅僅需要兩次掃描數據庫，第一次是統計每個商品的頻次，用于剔除不滿足最低支持度的商品，然后排序得到FreqItems。第二次，掃描數據庫構建FP樹。還是以之前Apriori的例子來一步步的詳細分析FP樹的構建，和頻繁項的遞歸挖掘。

首先，找出頻繁1項集，支持度為50%

ID集合{1，2，3，5}，所以在剔除ID=4和6后，對每條訂單的商品序列按照商品出現的頻率進行重新排序，得到如下：

然后，構建FP-Tree

如果我們想獲取誰的頻繁模式，只需要找到該節點并上溯尋找到所有節點即可，舉個例子，找到2的頻繁項集候選集，可以得到兩個個路徑；根據這個FP-Tree，挖掘頻繁模式就是通過遞歸的獲取節點的子樹的過程。子樹構建方式如下：新建一個新的FP樹，然后遍歷樹中所有的待挖掘節點，往上找，直到root節點，然后把當前路徑上的非根節點添加到subTree中，每個節點的頻次為當前遍歷節點的頻次。

我們以2節點為例，找到2節點的路徑{2,1,3}和{2,3}，每個路徑的頻率等于該路徑中2節點的頻率，因此

2-1-3=>3

2-3=>1

然后我們構建新的subTree：

所以根據指出度為50%，我們可以得到{2},{2,3},{2,3,1}都是頻繁模式，例如{2,1,3}總共出現3次，3/5=0.6 = 60% 大于我們要求的支持度50%；{2}和{2,3}都出現4次，其他的依次類推；

二、驗證

我們通過Spark的MLlib中提供的數據挖掘算法FP-Growth來驗證一下我們的結果

通過結果可以看出我們的計算是對的

三、適用場景

除了跟Apriori算法一樣，用來進行一些關聯商品推薦，FP-Tree還可以用于這樣的場景：輸入一個單詞或者單詞的一部分，推斷出你可能要搜索的查詢詞項，比如在百度輸入“xxx大學”開始查詢時，會出現諸如“xxx大學為什么還不放假”之類的推薦結果。

FP-Growth又稱為FP-增長算法，它比Apriori算法要快，它基于Apriori構建，但在完成相同任務時采用了一些不同的技術。不同于Apriori算法的”產生－測試”，這里的任務是將數據集存儲在一個特定的稱做FP樹的結構之后發現頻繁項集或者頻繁項對，即常在一塊出現的元素項的集合FP樹,這種做法是的算法的執行速度要快于Apriori，通常性能要好兩個數量級以上。

四、總結

數據挖掘中關于關聯規則或者頻繁模式挖掘類的算法，也是我們日常生活中經常用到的算法。數據挖掘還有很多有趣的算法，?這些算法能讓我們更好的從數據從挖掘價值信息。同時，大數據平臺也將一如既往的為各種數據挖掘類應用提供算力支持，為我行金融科技發展打造堅持的大數據平臺支撐。

總結

以上是生活随笔為你收集整理的数据挖掘原理与算法_技术分享|大数据挖掘算法之FPGrowth算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。