机器学习之手把手实现，第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现...
https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on2-fp-growth/index.html?ca=drs-
本文將介紹機器學習領域經典的 FP-growth（Frequent Pattern Growth）模型，它是目前業界經典的頻繁項集和關聯規則挖掘的算法。相比于 Apriori 模型，FP-growth 模型只需要掃描數據庫兩次，極大得減少了數據讀取次數并顯著得提升了算法效率。您將看到 FP-growth 的原理介紹、FP-growth 實現步驟和詳解、FP-growth 實現代碼以及用 FP-growth 解決實際的頻繁項集和關聯規則挖掘問題。通過閱讀本文，您會對 FP-growth 的原理了如指掌，并可以自己開發出 FP-growth 的實現代碼。
從啤酒和尿布引出的頻繁項集
在機器學習系列文章的第一篇中，主要介紹了支持向量機 SVM 模型的原理和實現。在文章一開始，筆者提到機器學習主要分為四大類，分別是分類，聚類，回歸和關聯分析。第一篇中的 SVM 就屬于分類。那么下面筆者開始介紹關聯分析。關聯分析分為頻繁項集挖掘和關聯規則挖掘。
生活中的數據本身包含著各種規律，機器學習模型可以從數據中挖掘出這些規律，啤酒與尿布就是一個典型的例子。有研究發現，在超市的訂單記錄中，啤酒和尿布總是頻繁共同出現在同一條訂單記錄里。換句話說，買尿布的人，往往會順手買啤酒。這就引出了本文的主題之一，即頻繁項集。頻繁項集是在數據庫中大量頻繁出現的數據集合。那么發現這些頻繁項集有什么意義呢？
主流的頻繁項集挖掘算法有 Apriori 和 FP-growth。其中 Apriori 算法需要多次掃描數據庫，這就使得該算法本身不適合大數據量。FP-growth，即 Frequent Pattern Growth，它通過構建 FP 樹(即 Frequent Pattern Tree)這樣的數據結構，巧妙得將數據存儲在 FP 樹中，只需要在構建 FP 樹時掃描數據庫兩次，后續處理就不需要再訪問數據庫了。這種特性使得 FP-growth 算法比 Apriori 算法速度快。FP 樹是一種前綴樹，由頻繁項的前綴構成，具體細節會在頻繁項集挖掘原理一節介紹。挖掘出頻繁項集后，可以從頻繁項集中進一步挖掘關聯規則。
關聯規則簡介
關聯規則是在頻繁項集的基礎上得到的。關聯規則指由集合 A，可以在某置信度下推出集合 B。通俗來說，就是如果 A 發生了，那么 B 也很有可能會發生。舉個例子，有關聯規則如：{'雞蛋', '面包'} -> {'牛奶'}，該規則的置信度是 0.9，意味著在所有買了雞蛋和面包的客戶中，有 90%的客戶還買了牛奶。關聯規則可以用來發現很多有趣的規律。這其中需要先闡明兩個概念：支持度和置信度。
支持度 Support
支持度指某頻繁項集在整個數據集中的比例。假設數據集有 10 條記錄，包含{'雞蛋', '面包'}的有 5 條記錄，那么{'雞蛋', '面包'}的支持度就是 5/10 = 0.5。
置信度 Confidence
置信度是針對某個關聯規則定義的。有關聯規則如{'雞蛋', '面包'} -> {'牛奶'}，它的置信度計算公式為{'雞蛋', '面包', '牛奶'}的支持度/{'雞蛋', '面包'}的支持度。假設{'雞蛋', '面包', '牛奶'}的支持度為 0.45，{'雞蛋', '面包'}的支持度為 0.5，則{'雞蛋', '面包'} -> {'牛奶'}的置信度為 0.45 / 0.5 = 0.9。
關聯規則用于發現 if -> then 這樣的規則，并可以給出這條規則的可信度（即置信度）。現實場景中可以用來發現很多規律，下面舉個例子。在信息安全領域，需要根據已有流量數據制定規則，來判斷是否觸發安全報警。如規則{'數據包大'，'多個 ip 地址同時發送數據'} -> {'異常'}，該規則的置信度為 0.85。這條規則表示，當流量數據包大，并有多個 ip 地址同時向目標 ip 發送數據時，則有 85%的概率存在異常，需要觸發報警。
頻繁項集挖掘原理
頻繁項集挖掘分為構建 FP 樹，和從 FP 樹中挖掘頻繁項集兩步。本節用如下表所示的數據集作為例子展開，該示例數據集共四條數據。
表 1. 示例數據集
| a,b,c |
| c,d,b,a |
| d,e,a |
| b,a |
構建 FP 樹
構建 FP 樹時，首先統計數據集中各個元素出現的頻數，將頻數小于最小支持度的元素刪除，然后將數據集中的各條記錄按出現頻數排序，剩下的這些元素稱為頻繁項；接著，用更新后的數據集中的每條記錄構建 FP 樹，同時更新頭指針表。頭指針表包含所有頻繁項及它們的頻數，還有每個頻繁項指向下一個相同元素的指針，該指針主要在挖掘 FP 樹時使用。下面用上文提到的數據集展開說明，假設最小支持度為 2。
首先，統計數據集中各元素出現的次數，得 a 出現 4 次, b 出現 3 次, c 出現 2 次, d 出現 2 次, e 出現 1 次。
接著，將出現次數小于最小支持度 2 的元素（即 e）在數據集中刪除，并將數據集按出現次數由高到低排序，得表 2。
表 2. 更新后的數據集
| a,b,c |
| a,b,c,d |
| a,d |
| a,b |
然后，用更新后的數據集中的記錄創建 FP 樹，并同時更新頭指針表。創建 FP 樹時，當待添加的記錄與 FP 樹中的路徑相同，則只需更新元素對應的頻數；如果待添加的記錄與 FP 樹存在不一致，則在不一致的地方分叉，創建新的結點。如圖 1-4 所示。注意，FP 樹的根節點是 null。
圖 1. 向 FP 樹添加第一條記錄{a,b,c}
圖 2. 向 FP 樹添加第二條記錄{a,b,c,d}
圖 3. 向 FP 樹添加第三條記錄{a,d}
圖 4. 向 FP 樹添加第四條記錄{a,b}
挖掘頻繁項集
得到 FP 樹后，需要對每一個頻繁項，逐個挖掘頻繁項集。具體過程為：首先獲得頻繁項的前綴路徑，然后將前綴路徑作為新的數據集，以此構建前綴路徑的條件 FP 樹。然后對條件 FP 樹中的每個頻繁項，獲得前綴路徑并以此構建新的條件 FP 樹。不斷迭代，直到條件 FP 樹中只包含一個頻繁項為止。下面以元素 c 為例，從上文圖 4 創建好的 FP 樹中挖掘頻繁項集。
首先，獲得以 c 元素的前綴路徑{a:2,b:2}，注意此處 a 和 b 的頻數為 2 是因為 c 的頻數為 2，所以與 c 共同出現的 a 和 b 的頻數就都為 2。
接著，創建條件 FP 樹，具體的創建過程和上一節創建 FP 樹的過程一樣，如圖 5 所示。
圖 5. c 元素的前綴路徑構成的條件 FP 樹
注意此時頭指針表中包含兩個元素，所以對每個元素，需要獲得前綴路徑，并將前綴路徑創建成條件 FP 樹，直到條件 FP 樹中只包含一個元素時返回。
再加上{c}本身就是頻繁項集，所以 c 對應的頻繁項集有：{c} {c,a} {c,b} {c,b,a}。
圖 6. b 元素的前綴路徑構成的條件 FP 樹
將其他元素 a,b,d 同樣按照上述對 c 的操作，得到表 3 所示頻繁項集。
表 3. 元素 a,b,c,d 對應的頻繁項集
| a | {a} |
| b | {b} {b,a} |
| c | {c} {c,a} {c,b} {c,b,a} |
| d | ze8trgl8bvbq {d,a} |
關聯規則挖掘原理
關聯規則挖掘首先需要對上文得到的頻繁項集構建所有可能的規則，然后對每條規則逐個計算置信度，輸出置信度大于最小置信度的所有規則。以頻繁項集{a,b,c}為例，構建所有可能的規則：{b,c} -> {a}, {a,c} -> {b},{a,b} -> {c},{c} -> {a,b},{b} -> {a,c},{a} -> {b,c}。對每條規則計算置信度后，輸出滿足要求的規則即可。
實現步驟: 自己動手實現 FP-growth
以上都為理論部分，下面開始介紹如何自己動手實現代碼。
首先，需要創建一個樹形的數據結構，叫做 FP 樹。如清單 1 所示，該樹結構包含結點名稱 nodeName，結點元素出現頻數 count，父節點 nodeParent，指向下一個相同元素的指針 nextSimilarItem，子節點集合 children。
清單 1. FP 樹結構
| 1 2 3 4 5 6 7 | class TreeNode: ????def __init__(self, nodeName, count, nodeParent): ????????self.nodeName = nodeName ????????self.count = count ????????self.nodeParent = nodeParent ????????self.nextSimilarItem = None ????????self.children = {} |
接著，用第一步構造出的數據結構來創建 FP 樹。如清單 2 所示，代碼主要分為兩層。第一層，掃描數據庫，統計出各個元素的出現頻數；第二層，掃描數據庫，對每一條數據記錄，將數據記錄中不包含在頻繁元素中的元素刪除，然后將數據記錄中的元素按出現頻數排序。將數據記錄逐條插入 FP 樹中，不斷更新 FP 樹，更新的過程會在清單 3 中介紹。
清單 2. 創建 FP 樹
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def createFPTree(frozenDataSet, minSupport): ????#scan dataset at the first time, filter out items which are less than minSupport ????headPointTable = {} ????for items in frozenDataSet: ????????for item in items: ????????????headPointTable[item] = headPointTable.get(item, 0) + frozenDataSet[items] ????headPointTable = {k:v for k,v in headPointTable.items() if v >= minSupport} ????frequentItems = set(headPointTable.keys()) ????if len(frequentItems) == 0: return None, None ????for k in headPointTable: ????????headPointTable[k] = [headPointTable[k], None] ????fptree = TreeNode("null", 1, None) ????#scan dataset at the second time, filter out items for each record ????for items,count in frozenDataSet.items(): ????????frequentItemsInRecord = {} ????????for item in items: ????????????if item in frequentItems: ????????????????frequentItemsInRecord[item] = headPointTable[item][0] ????????if len(frequentItemsInRecord) > 0: ????????????orderedFrequentItems = [v[0] for v in sorted(frequentItemsInRecord.items(), key=lambda v:v[1], reverse = True)] ????????????updateFPTree(fptree, orderedFrequentItems, headPointTable, count) ????return fptree, headPointTable |
清單 3 主要用來更新 FP 樹，這里用到了遞歸的技巧。每次遞歸迭代中，處理數據記錄中的第一個元素處理，如果該元素是 fptree 節點的子節點，則只增加該子節點的 count 樹，否則，需要新創建一個 TreeNode 節點，然后將其賦給 fptree 節點的子節點，并更新頭指針表關于下一個相同元素指針的信息。迭代的停止條件是當前迭代的數據記錄長度小于等于 1。
清單 3. 更新 FP 樹
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def updateFPTree(fptree, orderedFrequentItems, headPointTable, count): ????#handle the first item ????if orderedFrequentItems[0] in fptree.children: ????????fptree.children[orderedFrequentItems[0]].increaseC(count) ????else: ????????fptree.children[orderedFrequentItems[0]] = TreeNode(orderedFrequentItems[0], count, fptree) ????????#update headPointTable ????????if headPointTable[orderedFrequentItems[0]][1] == None: ????????????headPointTable[orderedFrequentItems[0]][1] = fptree.children[orderedFrequentItems[0]] ????????else: ????????????updateHeadPointTable(headPointTable[orderedFrequentItems[0]][1], fptree.children[orderedFrequentItems[0]]) ????#handle other items except the first item ????if(len(orderedFrequentItems) > 1): ????????updateFPTree(fptree.children[orderedFrequentItems[0]], orderedFrequentItems[1::], headPointTable, count) |
清單 4 開始挖掘頻繁項集，這里也是遞歸迭代的思路。對于頭指針表中的每一個元素，首先獲取該元素結尾的所有前綴路徑，然后將所有前綴路徑作為新的數據集傳入 createFPTree 函數中以創建條件 FP 樹。然后對條件 FP 樹對應的頭指針表中的每一個元素，開始獲取前綴路徑，并創建新的條件 FP 樹。這兩步不斷重復，直到條件 FP 樹中只有一個元素為止。
清單 4. 挖掘頻繁項集
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def mineFPTree(headPointTable, prefix, frequentPatterns, minSupport): ????#for each item in headPointTable, find conditional prefix path, create conditional fptree, then iterate until there is only one element in conditional fptree ????headPointItems = [v[0] for v in sorted(headPointTable.items(), key = lambda v:v[1][0])] ????if(len(headPointItems) == 0): return ????for headPointItem in headPointItems: ????????newPrefix = prefix.copy() ????????newPrefix.add(headPointItem) ????????support = headPointTable[headPointItem][0] ????????frequentPatterns[frozenset(newPrefix)] = support ????????prefixPath = getPrefixPath(headPointTable, headPointItem) ????????if(prefixPath != {}): ????????????conditionalFPtree, conditionalHeadPointTable = createFPTree(prefixPath, minSupport) ????????????if conditionalHeadPointTable != None: ????????????????mineFPTree(conditionalHeadPointTable, newPrefix, frequentPatterns, minSupport) |
清單 5 展示了獲取前綴路徑的步驟。對于每一個相同元素，通過父節點指針不斷向上遍歷，所得的路徑就是該元素的前綴路徑。
清單 5. 獲取前綴路徑
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | def getPrefixPath(headPointTable, headPointItem): ????prefixPath = {} ????beginNode = headPointTable[headPointItem][1] ????prefixs = ascendTree(beginNode) ????if((prefixs != [])): ????????prefixPath[frozenset(prefixs)] = beginNode.count ????while(beginNode.nextSimilarItem != None): ????????beginNode = beginNode.nextSimilarItem ????????prefixs = ascendTree(beginNode) ????????if (prefixs != []): ????????????prefixPath[frozenset(prefixs)] = beginNode.count ????return prefixPath |
清單 6 展示了挖掘關聯規則的代碼，這里也用到了遞歸迭代的技巧。對于每一個頻繁項集，構造所有可能的關聯規則，然后對每一個關聯規則計算置信度，輸出置信度大于閾值的關聯規則。
清單 6. 挖掘關聯規則
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def rulesGenerator(frequentPatterns, minConf, rules): ????for frequentset in frequentPatterns: ????????if(len(frequentset) > 1): ????????????getRules(frequentset,frequentset, rules, frequentPatterns, minConf) def getRules(frequentset,currentset, rules, frequentPatterns, minConf): ????for frequentElem in currentset: ????????subSet = removeStr(currentset, frequentElem) ????????confidence = frequentPatterns[frequentset] / frequentPatterns[subSet] ????????if (confidence >= minConf): ????????????flag = False ????????????for rule in rules: ????????????????if(rule[0] == subSet and rule[1] == frequentset - subSet): ????????????????????flag = True ????????????if(flag == False): ????????????????rules.append((subSet, frequentset - subSet, confidence)) ????????????if(len(subSet) >= 2): ????????????????getRules(frequentset, subSet, rules, frequentPatterns, minConf) |
代碼下載 (code downloads)
本文所有 FP-growth 實現代碼可在文末下載。
本文數據集簡介
圖 7. 數據集樣例
數據集是購物車數據。每一條代表了一條購物車信息。目的是要挖掘出在購物車中頻繁共同出現的集合，并根據此頻繁項集挖掘出關聯規則。關聯規則暗示頻繁項集之間存在的關系，如購買了面包的人，有很高的可能性會同時購買牛奶。
應用示例: 應用實現的 FP-growth 解決實際問題
清單 7. 用 FP-growth 解決實際問題
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | if __name__=='__main__': ????print("fptree:") ????dataSet = loadDataSet() ????frozenDataSet = transfer2FrozenDataSet(dataSet) ????minSupport = 3 ????fptree, headPointTable = createFPTree(frozenDataSet, minSupport) ????fptree.disp() ????frequentPatterns = {} ????prefix = set([]) ????mineFPTree(headPointTable, prefix, frequentPatterns, minSupport) ????print("frequent patterns:") ????print(frequentPatterns) ????minConf = 0.6 ????rules = [] ????rulesGenerator(frequentPatterns, minConf, rules) ????print("association rules:") ????print(rules) |
清單 5 中的代碼首先加載數據集，然后通過調用前面實現的 FP-growth 代碼，先是構造 FP 樹，接著從 FP 樹中挖掘頻繁項集，最后從頻繁項集中產生關聯規則，并輸出置信度。
表 4. 頻繁項集的結果示例
| {'gloves'} | 0.5 |
| {'shoes', 'socks'} | 0.5 |
| {'milk', 'eggs', 'bread'} | 0.5 |
| {'bread'} | 0.5 |
| {'milk', 'bread'} | 0.5 |
| {'gloves', 'socks'} | 0.5 |
| {'shoes'} | 0.5 |
| {'eggs', 'bread'} | 0.5 |
| {'eggs'} | 0.5 |
| {'milk'} | 0.67 |
| {'socks'} | 0.67 |
| {'milk', 'eggs'} | 0.5 |
從表 4 中可以看出，鞋子與襪子，牛奶與面包，面包與雞蛋，牛奶與雞蛋，手套與襪子，牛奶、雞蛋與面包等項在數據集中共同出現得很頻繁。
表 5. 關聯規則的結果示例
| {'socks' }-> {'shoes'} | 0.75 |
| {'shoes'} -> {'socks'} | 1.0 |
| {'eggs', 'bread'} -> {'milk'} | 1.0 |
| {'bread'} -> {'milk', 'eggs'} | 1.0 |
| {'eggs'} -> {'milk', 'bread'} | 1.0 |
| {'milk', 'bread'} -> {'eggs'} | 1.0 |
| {'milk'} -> {'eggs', 'bread'} | 0.75 |
| {'milk', 'eggs'} -> {'bread'} | 1.0 |
| {'bread'} -> {'milk'} | 1.0 |
| {'milk'} -> {'bread'} | 0.75 |
| {'socks'} -> {'gloves'} | 0.75 |
| {'gloves'} -> {'socks'} | 1.0 |
| {'bread'} -> {'eggs'} | 1.0 |
| {'eggs'} -> {'bread'} | 1.0 |
| {'eggs'} -> {'milk'} | 1.0 |
| {'milk'} -> {'eggs'} | 0.75 |
從表 5 中可以看出某人購買了鞋子，極有可能會同時購買襪子；某人購買了雞蛋與面包，極有可能會購買牛奶；某人購買了手套，極有可能會購買襪子。但是需注意，關聯規則反過來不一定同樣成立，拿第一條和第二條結果為例，由鞋子推出襪子的置信度是 1.0，但是反過來，由襪子推出鞋子的置信度只有 0.75，而并不是 1.0。
總結
本文首先介紹了頻繁項集和關聯規則在現實場景中的應用，接著介紹了頻繁項集和關聯規則挖掘的原理，然后通過代碼樣例，介紹了在自己動手實現 FP-growth 模型時的思路。最后，用購物車數據展示了如何應用 FP-growth 解決實際問題。需要注意的是，FP-growth 算法本身對于海量數據仍然會很慢，雖然其只需要掃描數據庫兩次，但是對于海量數據在內存中建立一份統一的 FP 樹結構是不大現實的。這就需要考慮采用并行計算的思路來并發實現 FP-growth，利用多臺電腦并行執行 FP-growth，從而加速運算。并行 FP-growth 的具體實現方法可以參考文獻 2 所列的論文。由于篇幅有限，這部分內容不在本次內容中展開，預計后期會對這部分內容進行專門介紹。
參考資源
本文用到的參考文獻如下：
- 參考 Peter Harrington 著《機器學習實戰》，了解 FP-growth 模型。
- Zhang D, Zhang D, Zhang D, et al. Pfp: parallel fp-growth for query recommendation[C]// ACM Conference on Recommender Systems. ACM, 2008:107-114.
轉載于:https://www.cnblogs.com/davidwang456/articles/8926985.html
總結
以上是生活随笔為你收集整理的机器学习之手把手实现，第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 机器学习之手把手实现第1部分:支持向量机
- 下一篇： 机器学习系列之手把手教你实现一个 nai