在 R 語言中的 arules 包有該算法的實現，故花時間研究了一下該算法的原理和産生的背景。關于什麼是關聯規則挖掘算法的可以看我的

加權的原因是因為在現實生活中，事物都是有重要程度之分的。

譬如說，在超市的購物記錄中，每條記錄和每個商品都會對應着相應的利潤，如果我們給記錄和商品按照利潤高低添加權重後就可能可以挖掘到更加多利潤高并且頻繁出現的規則。

基于這個思想，有學者就提出了加權關聯規則挖掘算法。

HITS 算法

加權關聯規則挖掘算法是在基于 HITS 算法思想上提出的。HITS 算法是鍊接分析中非常基礎且重要的算法，被很多搜索引擎所使用。

Hub 頁面（樞紐頁面）：指的是包含了很多指向高質量“Authority”頁面鍊接的網頁，比如 hao123 首頁可以認為是一個典型的高質量“Hub”網頁。

Authority 頁面（權威頁面）：是指與某個領域或者某個話題相關的高質量網頁，比如搜索引擎領域，Google 和百度首頁即該領域的高質量網頁，比如視頻領域，優酷和土豆首頁即該領域的高質量網頁。

二部圖（bipartite graph）

在這裡，我們将事務作為 Hub，而将項集作為 Auth，并且初始值都為 1（實際使用中是根據項的重要程度調整 Auth 的值），以下面的公式計算和調整 Hub 和 Auth 的值和計算項集對應的 w-support

公式中，T 表示事務，D 表示數據庫。計算完後，我們可以得下表的結果

拿表中 {C} 做為個例子，w-support 的值是如下進行計算的

從表中我們可以觀察兩件有意思的事情。第一，最大的 hub 值的事務并不是具備 item 數目最多的。還有就是支持度高的 item 并不一定擁有最大的 w-support。 原因是因為 w-support 度量考慮的是二部圖中事務與 item 之間的相互貢獻度，而不是單純的依靠 item 在事務中出現的頻數。而事務的重要性是由 item 重要性決定的，而不依靠 item 數量的多少。

同樣的，我們也可以使用 w-support 度量計算關聯規則的支持度和置信度。計算的公式如下：

與傳統關聯規則挖掘類似，加權關聯規則挖掘算法的步驟一般也被劃分為兩步

1. 利用最小支持度從數據庫中找到頻繁項集。
2. 利用最小置信度從頻繁項集中找到關聯規則。

在論文中，作者還做了兩個有趣的實驗來驗證他 w-support 度量的有效性。

第一個實驗是使用加權關聯規則算法從 Netflix 的數據集中找出最受歡迎的 10 部電影。他們的做法是将電影做為一個項（Authority），每個用戶對相應的電影打分做為事務（Hub），而且假設流行度和用戶的正面的評價有關，和具體的評分多少是無關的。

除此，作者按照評分用戶的活躍度賦予不同的權重，他們認為活躍的用戶更加具有權威性（此處想起水軍），也即活躍用戶具有更高的權重，最後他們與 support 度量的對比圖如下所示

從對比圖中我們可以看到，兩個最流行的電影列表排序存在明顯的差異，其中值得注意的是用戶的是 The Sixth Sense 在第一個列表中并沒有出現，然而因為多數的活躍的用戶對該電影給出了正面評價了，所以出現在列表中了。

另外一個實驗是選出最好的 10 部電影，與上面稍微有點不同的是，這裡的事務都是 5 分評價的而且結果是和 IDMB 的評分列表相對比的。得出的實驗結果如下圖所示：

可以看到使用 w-support 度量的列表與 IDMB 最大的不同前三位都被指環王所包攬了。另外兩部指環王的排名的提升是受排名第一的 Lord of the Rings: The Two Towers 的影響。由前面所提到的假設我們可知，導緻這個結果的原因是因為給排在第一名的電影評五分的用戶的權重的提升，導緻他在評價其他電影的時候，會順帶提高其他電影的 w-support 值，從而最終提升了一部分電影的排名。

總結

該算法适合稀疏的數據，因為計算 w-support 不是單純的依賴頻數。

End

作者：曾梓華

來源：簡書

内容觀點不代表本站立場，如若轉載請聯系專欄作者。