購物籃演算法

1. 推薦演算法之模型協同過濾（1）-關聯規則

關聯規則是數據挖掘中的典型問題之一，又被稱為購物籃分析，這是因為傳統的關聯規則案例大多發生在超市中，例如所謂的啤酒與尿布傳說。事實上，「購物籃」這個詞也揭示了關聯規則挖掘的一個重要特點：以交易記錄為研究對象，每一個購物籃（transaction）就是一條記錄。關聯規則希望挖掘的規則就是：哪些商品會經常在同一個購物籃中出現，其中有沒有因果關系。為了描述這種「經常性」及「因果關系」，分析者定義了幾個指標，基於這些指標來篩選關聯規則，從而得到那些不平凡的規律。

（1）計算支持度
支持度計數：一個項集出現在幾個事務當中，它的支持度計數就是幾。例如{Diaper, Beer}出現在事務 002、003和004中，所以它的支持度計數是3
支持度：支持度計數除於總的事務數。例如上例中總的事務數為4，{Diaper, Beer}的支持度計數為3，所以它的支持度是3÷4=75%，說明有75%的人同時買了Diaper和Beer。

（2）計算置信度
置信度：對於規則{Diaper}→{Beer}，{Diaper, Beer}的支持度計數除於{Diaper}的支持度計數，為這個規則的置信度。例如規則{Diaper}→{Beer}的置信度為3÷3=100%。說明買了Diaper的人100%也買了Beer。

一般地，關聯規則被劃分為動態推薦，而協同過濾則更多地被視為靜態推薦。
所謂動態推薦，就是推薦的基礎是且只是當前一次（最近一次）的購買或者點擊。譬如用戶在網站上看了一個啤酒，系統就找到與這個啤酒相關的關聯規則，然後根據這個規則向用戶進行推薦。而靜態推薦則是在對用戶進行了一定分析的基礎上，建立了這個用戶在一定時期內的偏好排序，然後在這段時期內持續地按照這個排序來進行推薦。由此可見，關聯規則與協同過濾的策略思路是完全不同的類型。
事實上，即便在當下很多能夠拿到用戶ID的場景，使用動態的關聯規則推薦仍然是值得考慮的一種方法（尤其是我們經常把很多推薦方法的結果綜合起來做一個混合的推薦），因為這種方法的邏輯思路跟協同過濾有著本質的不同，問題似乎僅僅在於：個人的偏好到底有多穩定，推薦到底是要迎合用戶的長期偏好還是用戶的當下需求。

挖掘關聯規則主要有Apriori演算法和FP-Growth演算法。後者解決了前者由於頻繁的掃描數據集造成的效率低下缺點。以下按照Apriori演算法來講解。

step 1： 掃描數據集生成滿足最小支持度的頻繁項集。
step 2： 計算規則的置信度，返回滿足最小置信度的規則。

如下所示，當用戶購買1商品時推薦2、3商品