《推薦系統：技術、評估及高效算法》一2.5 關聯規則挖掘

本節書摘來自華章出版社《推薦系統：技術、評估及高效算法》一書中的第2章，第2.5節，作者 [ 美］弗朗西斯科·裡奇（francesco ricci）利奧·羅卡奇（lior rokach）布拉哈·夏皮拉（bracha shapira）保羅 b.坎特（paul b.kantor），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

關聯規則挖掘關注于規則的發現，其他能夠根據事務中出現其他物品來預測出現某個物品。兩個物品被發現相關隻意味着共同出現，但是沒有因果關系。注意不要将這種技術與在2.3.3節中提到的基于規則的分類混淆。

我們定義物品集為一個或多個物品的集合（例如，（牛奶，啤酒，尿布））。k-物品集是包含k個物品的集合。給定物品的頻繁度稱為支援量（比如，（牛奶，啤酒，尿布）=131）。并且物品集的支援度是包含它的事務的比例(例如，（牛奶，啤酒，尿布）=0.12)。頻繁物品集是支援度大于或等于最小支援度門檻值的物品集。關聯規則是公式xy的表達式，其中x和y是物品集。（例如，牛奶，尿布啤酒）。在這個案例中，關聯規則的支援度是同時擁有x和y的事務的比例。另一方面，規則的置信度是y中的物品有多經常出現在包含x的事務中。

給定一組事務集合t，關聯規則挖掘的目标是發現具有支援度大于等于最小支援度門檻值以及置信度大于等于最小置信度門檻值的所有規則。暴力法将會列出所有可能的關聯規則，為每一個規則計算支援度和置信度，然後删除不滿足兩個條件的規則。但是，這樣的計算開銷太大。是以，我們采用兩步方法：1)産生了所有支援度大于等于最小支援度的物品集（頻繁項集生成）；2)從每一頻繁物品集中産生高置信規則（規則産生）。

有幾個技術來優化頻繁物品集的産生。在一個廣泛的意義上，它們可以分成：嘗試最小化候選集數量（m），降低事務量（n），降低比較量數量（nm）。但是最常用的方法是使用先驗規則來降低候選數量。這個原則表明如果物品集是頻繁的，那麼所有的子集也是頻繁的。支援度的衡量标準已經驗證了這一點，因為一個物品集的支援度永遠不會超過其子集的支援度。apriori算法是這個規則實際的實作。

給定一個頻繁集l，産生規則時的目的是發現所有滿足最小的置信度需求的非空子集。如果l=k，那麼有2k2條候選關聯規則。是以，在生成頻繁物品集時，需要找到高效的方法來生成規則。對于apriori算法，我們能通過合并規則結果中共用相同字首的兩個規則來産生候選規則。

關聯規則在發現模式和推動個性化市場營銷方面的顯著效果聞名已久［2］。但是，盡管這些方法和推薦系統的目标之間有明顯的關聯，但是它們還是沒有成為主流。主要原因是這種方法類似于基于物品的cf但缺少靈活性，因為它需要事務這個明确的概念——事件共同出現在某個給定的會話中。在第3章中我們将舉一些有意義的例子，其中一些表明關聯規則仍有潛力。

mobasher等［53］提出一種基于關聯規則的個性化網頁系統。他們的系統基于使用者的導航模式，從共同出現的浏覽頁面來識别關聯規則。他們在精确度和覆寫率名額方面優于基于knn的推薦系統。smyth等［68］提出給推薦系統使用關聯規則的兩種不同的研究案例。在第一種案例中，為了生成較好的物品物品相似度名額，他們從使用者屬性中使用先驗算法來抽離物品關聯規則。在第二種案例中，他們應用關聯規則到會話推薦中。這裡的目标是發現共同發生的評論，比如，使用者通過一個推薦物品的特定特征表明偏好。lin等［49］提出一種新的關聯規則挖掘算法，為了獲得一個合适的有意義規則數量，在挖掘期間調整規則的最小支援度，是以解決了先前像apriori這樣算法的某些缺陷。他們挖掘在使用者之間和物品之間的關聯規則。測量出的精确度優于基于相關度推薦的報告值，并且接近于更精巧的方法，如svd和ann的結合。

最後，如在2.3.2節中提到的那樣，cho等［18］在一個網頁商店推薦系統中結合了決策樹和關聯規則挖掘。在他們的系統，關聯規則的導入是為了連結相關的物品集。然後通過連接配接使用者偏好和關聯規則來計算得出推薦結果。他們在不同的事務集中尋找關聯規則，如商品，購物車，點選率。他們用啟發式學習給每一個事務集中規則附權重重。例如，商品關聯規則權重大于點選關聯規則。