『啤酒與尿不濕』之關聯規則

02-02

春節先來一篇，祝各位同學猴年快樂啦，希望0基礎同學也能看懂本文。

拿這個例子做本系列的開場也是因為我個人覺得其解釋性強，也非常直觀。在之後掌握了一些更深入的數學工具之後，循序漸進地對一些更複雜的演算法進行學習，就會相對容易不少。

首先當然還是先講一下這個發生在沃爾瑪婦孺皆知的故事吧。

沃爾瑪一家分店的營銷經理對超市的銷售數量進行設定跟蹤，有一次他發現了一個很奇怪的現象：啤酒與尿不濕的銷量在周末總會出現成比例增長。他們立即對這個現象進行了分析和討論，並且派出專門的人員在賣場內進行全天候的觀察。他們發現這些顧客有幾個共同的特點：

一般是周末出現這種情況

購買者以已婚男士為主

他們家中有孩子且不到兩歲，有尿不濕的剛需

他們喜歡看體育比賽節目，並且喜歡邊喝啤酒邊看，顧客有喝啤酒的需求

周末是體育比賽扎堆的日子，所以出現這種關聯銷售多在周末的時候

這位營銷經理從中受到啟發，他對超市的物品擺放進行了調整，將賣場內原來相隔很遠的婦嬰用品區與酒類飲料區的空間距離拉近，減少顧客的行走時間，將啤酒與尿不濕擺放在一起，同時將牛肉乾等一些簡便的下酒食品也擺放在一起，這樣全年下來，營業額增加了幾百萬美元。

我們先不管這個故事的真實性與否，我們關心的是，是否能有一種較為通用的辦法，從一份資料庫中（如銷售記錄）中發現某些特徵（如商品種類）之間的聯繫？這就是本文著重要講的內容——關聯規則演算法。

在講解演算法之前，我們先了解幾個簡單的概念：

事務庫（Transaction Database）：存儲著二維結構的記錄集。定義為：D
就好比一份超市銷售記錄，列是商品ID，行是每個人的購買記錄，每個格子中存的是這個人是否購買了該商品。
事務（Transaction）：在事務庫里的某一筆事務。定義為：T，T ∈ D
舉例來說就是某一位客戶的購買記錄。
支持度（Support）：定義為 S(X) = occur(X) / count(D) = P(X)
比如啤酒的支持度為3%，意思就是在該資料庫中有3%的顧客購買了啤酒。
置信度（Confidence/Strength）：定義為 C(X->Y) = S(X ∪ Y) / S(X) = P(Y|X)
如果C(啤酒->尿布)=40%，意思就是在購買啤酒的顧客中，有40%的人同時也購買了尿布。

好了暫時先介紹這麼幾個概念，那麼假設我們現在有一個支持度閾值和一個置信度閾值，如何才能快速地找到所有滿足閾值條件的規則呢？（規則可以是兩兩關係，也可以是多個特徵之間的關係）

如果你沒有接觸過這一塊內容，並且你是一個勇於認真思考的人，那麼看到這兒你可以先暫時不用往下看了，帶著這個問題可以慢慢思考個一兩天，然後再來看看別人是怎麼解決這個問題的（可以從時空複雜度來下手分析）。

===================== 大家好我叫Apriori分割線 ========================

Apriori演算法是一種挖掘關聯規則的頻繁項集演算法，我們先看下這個單詞的發音和釋義（嚴肅臉）：

apriori 英[e?prɑ??:r?] 美[e?pr??:r?] adj. 先驗的; <拉>由原因推及結果的; 演繹的; 推測的;
example: apriori probability 先驗概率

好些人學完課也不知道這演算法念什麼… 我就想問問你還打算跟面試官愉快地裝逼嗎（誤

Apriori採用的是一種逐層搜索的迭代法來尋找我們最終要的答案，在描述演算法之前還有幾個概念需要先說明：

項集(Items)：同時出現的項的集合。定義為：k-itemset（k項集）
比如{啤酒}、{尿不濕}就是1項集，{啤酒，尿不濕}這樣的組合就是2項集。
候選集（Candidate itemset）：通過向下合併（Join）得出的項集。定義為C[k]
頻繁集（Frequent itemset）：支持度大於等於支持度閾值（Minimum Support/minsup）的項集。表示為L[k]。注意，頻繁集的子集一定是頻繁集。

Apriori核心演算法步驟描述如下：

找出所有頻繁1項集的集合，該集合記作L[1]，令k=1；
連接步：在L[k]的基礎上，通過向下合併得到候選k+1項集，記作C[k+1]；
剪枝步：在C[k+1]中，任一項集的所有非空子集也必須是頻繁的，剔除不符合的，得到L[k+1]；
令k=k+1，重複2->3，直到不能生成更大的頻繁集為止。

看起來似乎有點抽象，我還是以舉例子來說明上述演算法流程，然後你會發現簡單得不能更簡單：

我們先虛構一份春節結束後顧客在某超市購物的消費清單：

我們先定義一個支持度閾值為30%，如果低於這個閾值的項集就會被剔除。那麼我們先通過這個顧客的購物清單來計算『C1候選集』：

方法很簡單，就是統計每個商品出現的頻率而已，然後我們將大於支持度閾值30%的『1項集』挑選出來成為『L1頻繁集』（上圖黃色高亮部分即為L1）。

然後我們通過『L1頻繁集』來構造『C2候選集』，『C2候選集』即是『L1頻繁集』中的『1項集』倆倆組合產生的，如下所示：

在C2中找出所有滿足閾值條件的『2項集』，只有{巧克力，岡本}這麼唯一一組『2項集』，那麼演算法就到此結束了。

如果每個步驟不去掉非頻繁項目集，則其掃描過程的樹形結構如下，每個數字可以理解為是某一種商品：

在其中某個過程中，可能出現非頻繁的項目集，將其去掉（用陰影表示）為：

雖然筆者不知道岡本為何物，但是也該知道在春節結束、情人節前的時刻，該把巧克力和岡本擺在一起促銷更為合適。這就是大數據帶給你神奇的地方，儘管你不懂銷售，不懂大眾購物心理，但是你能拿出一個結果來，並輔以數據支撐。

===================== 產品經理看到這兒就夠啦 ========================

回到演算法本身，很容易就能發現這個演算法的瓶頸在於當事務庫變得十分龐大的時候，每次計算候選集會帶來很大的時間開銷，如果不加以優化，那麼每次都得遍歷每條事務中的每一個節點上的數據才能完成支持度計算這步操作。好了，那麼問題就是如何針對關聯規則挖掘來做優化呢？

這是一個比較有意思的問題，因為學術界和工業界在這個問題上往往會選擇兩種截然不同的策略。

對於學術派來說，優化時間複雜度是第一要事，所以FP-Growth演算法應運而生，發明者採用了一種分治策略將提供頻繁項集的事務庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留了項集關聯信息。如果有比較紮實數據結構基礎的話，你很快就會發現它就是一棵長得比較另類的前綴樹，由頻繁項頭表和項前綴樹構成，每一條路徑表示了一組可行解。通過不斷迭代FP-Tree即可找到所有頻繁項集。

FP-Growth是一種比Apriori更高效的頻繁項挖掘方法，它只需要掃描項目表2次。其中第1次掃描獲得當個項目的頻率，去掉不符合支持度要求的項，並對剩下的項排序。第2遍掃描是建立一顆FP-Tree(frequent-patten tree)。接下來的工作就是在FP-Tree上進行挖掘。

舉個栗子：

它所對應的FP-Tree如下：

然後從頻率最小的單項P開始，找出P的條件模式基，用構造FP-Tree同樣的方法來構造P的條件模式基的FP-Tree，在這棵樹上找出包含P的頻繁項集。

依次從m, b, a, c, f的條件模式基上挖掘頻繁項集，有些項需要遞歸的去挖掘，比較麻煩，比如m節點，具體的過程可以參考博客：Frequent Pattern 挖掘之二(FP Growth演算法)，裡面講得很詳細。

是不是立馬有一種高大上的感覺？像是回到了當年ACM競賽刷題的世界裡。不過工業派表示FP-Growth演算法實現起來比較麻煩，如果這棵樹龐大到無法自由地塞入內存時可能還得建磁碟索引，所以容錯率相對較低，一旦出了問題得同時考慮數據、演算法和存儲實現…… 於是簡單粗暴地為每個項集建索引（行列轉換）和一些分散式及並行計算的技巧受到了工業界的青睞，比較流行的做法有計數分發（Count Distribution）演算法、數據分發（Data Distribution）演算法和候選分發（Candidate Distribute）演算法，各位同學有興趣的話可以通過關鍵詞自行翻閱相關文獻，就不再在這裡展開啦。