加權關聯(lián)規(guī)則挖掘
在 R 語言中的 arules 包有該算法的實現(xiàn)，故花時間研究了一下該算法的原理和產生的背景试幽。關于什么是關聯(lián)規(guī)則挖掘算法的可以看我的上一篇簡書螟凭。
為什么要加權
加權的原因是因為在現(xiàn)實生活中，事物都是有重要程度之分的峡蟋。
譬如說晶通，在超市的購物記錄中璃氢，每條記錄和每個商品都會對應著相應的利潤，如果我們給記錄和商品按照利潤高低添加權重后就可能可以挖掘到更加多利潤高并且頻繁出現(xiàn)的規(guī)則狮辽。
基于這個思想一也，有學者就提出了加權關聯(lián)規(guī)則挖掘算法。
HITS 算法
加權關聯(lián)規(guī)則挖掘算法是在基于 HITS 算法思想上提出的喉脖。HITS 算法是鏈接分析中非骋叮基礎且重要的算法，被很多搜索引擎所使用动看。
Hub 頁面（樞紐頁面）：指的是包含了很多指向高質量“Authority”頁面鏈接的網(wǎng)頁尊剔，比如 hao123 首頁可以認為是一個典型的高質量“Hub”網(wǎng)頁爪幻。
Authority 頁面（權威頁面）：是指與某個領域或者某個話題相關的高質量網(wǎng)頁菱皆，比如搜索引擎領域，Google 和百度首頁即該領域的高質量網(wǎng)頁挨稿，比如視頻領域仇轻，優(yōu)酷和土豆首頁即該領域的高質量網(wǎng)頁。
HITS 算法的思想基于如下兩個假設：
假設1：一個好的“Authority”頁面會被很多好的“Hub”頁面指向
假設2：一個好的“Hub”頁面會指向很多好的“Authority”頁面
假設每個頁面都有對應的 Hub 值和 Authority 值奶甘，并且初始值都為 1 篷店。可利用上面提到的兩個基本假設，以及相互增強關系等原則進行多輪迭代計算疲陕，每輪迭代計算更新每個頁面的兩個權值(值 +1 或其他策略)方淤，直到權值穩(wěn)定不再發(fā)生明顯的變化為止。更多關于 HITS 算法的細節(jié)可以查看尾部的參考文獻蹄殃。
加權關聯(lián)規(guī)則挖掘
在知道了 HITS 算法的思想后携茂。同樣的，我們也可以做出如下假設：
假設1：一個高質量的事務應該包含很多高質量的項诅岩。
假設2：一個高質量的項應該被很多高質量的事務所包含讳苦。
所以基于假設，論文 [1] 就提出了一種新的度量方式吩谦，稱之為 w-support鸳谜。
給定一個事務數(shù)據(jù)庫。我們可以繪制出其對應的二部圖（bipartite graph）
在這里式廷，我們將事務作為 Hub咐扭，而將項集作為 Auth，并且初始值都為 1（實際使用中是根據(jù)項的重要程度調整 Auth 的值）滑废，以下面的公式計算和調整 Hub 和 Auth 的值和計算項集對應的 w-support
公式中草描，T 表示事務，D 表示數(shù)據(jù)庫策严。計算完后穗慕，我們可以得下表的結果
拿表中 {C} 做為個例子，w-support 的值是如下進行計算的
從表中我們可以觀察兩件有意思的事情妻导。第一逛绵，最大的 hub 值的事務并不是具備 item 數(shù)目最多的。還有就是支持度高的 item 并不一定擁有最大的 w-support倔韭。 原因是因為 w-support 度量考慮的是二部圖中事務與 item 之間的相互貢獻度术浪，而不是單純的依靠 item 在事務中出現(xiàn)的頻數(shù)。而事務的重要性是由 item 重要性決定的寿酌，而不依靠 item 數(shù)量的多少胰苏。
同樣的，我們也可以使用 w-support 度量計算關聯(lián)規(guī)則的支持度和置信度醇疼。計算的公式如下：
與傳統(tǒng)關聯(lián)規(guī)則挖掘類似硕并，加權關聯(lián)規(guī)則挖掘算法的步驟一般也被劃分為兩步
- 利用最小支持度從數(shù)據(jù)庫中找到頻繁項集。
- 利用最小置信度從頻繁項集中找到關聯(lián)規(guī)則秧荆。
在論文中倔毙，作者還做了兩個有趣的實驗來驗證他 w-support 度量的有效性。
第一個實驗是使用加權關聯(lián)規(guī)則算法從 Netflix 的數(shù)據(jù)集中找出最受歡迎的 10 部電影乙濒。他們的做法是將電影做為一個項（Authority）陕赃，每個用戶對相應的電影打分做為事務（Hub），而且假設流行度和用戶的正面的評價有關，和具體的評分多少是無關的么库。
除此傻丝，作者按照評分用戶的活躍度賦予不同的權重，他們認為活躍的用戶更加具有權威性（此處想起水軍）诉儒，也即活躍用戶具有更高的權重桑滩，最后他們與 support 度量的對比圖如下所示
從對比圖中我們可以看到钢拧，兩個最流行的電影列表排序存在明顯的差異岖是，其中值得注意的是用戶的是 The Sixth Sense 在第一個列表中并沒有出現(xiàn)，然而因為多數(shù)的活躍的用戶對該電影給出了正面評價了碰凶，所以出現(xiàn)在列表中了缭受。
另外一個實驗是選出最好的 10 部電影胁澳，與上面稍微有點不同的是，這里的事務都是 5 分評價的而且結果是和 IDMB 的評分列表相對比的米者。得出的實驗結果如下圖所示：
可以看到使用 w-support 度量的列表與 IDMB 最大的不同前三位都被指環(huán)王所包攬了韭畸。另外兩部指環(huán)王的排名的提升是受排名第一的 Lord of the Rings: The Two Towers 的影響。由前面所提到的假設我們可知蔓搞，導致這個結果的原因是因為給排在第一名的電影評五分的用戶的權重的提升胰丁，導致他在評價其他電影的時候，會順帶提高其他電影的 w-support 值喂分，從而最終提升了一部分電影的排名锦庸。
總結
該算法適合稀疏的數(shù)據(jù)，因為計算 w-support 不是單純的依賴頻數(shù)蒲祈。
