加权关联规则挖掘
在 R 语言中的 arules 包有该算法的实现，故花时间研究了一下该算法的原理和产生的背景。关于什么是关联规则挖掘算法的可以看我的上一篇简书。
为什么要加权
加权的原因是因为在现实生活中，事物都是有重要程度之分的。
譬如说，在超市的购物记录中，每条记录和每个商品都会对应着相应的利润，如果我们给记录和商品按照利润高低添加权重后就可能可以挖掘到更加多利润高并且频繁出现的规则。
基于这个思想，有学者就提出了加权关联规则挖掘算法。
HITS 算法
加权关联规则挖掘算法是在基于 HITS 算法思想上提出的。HITS 算法是链接分析中非常基础且重要的算法，被很多搜索引擎所使用。
Hub 页面（枢纽页面）：指的是包含了很多指向高质量“Authority”页面链接的网页，比如 hao123 首页可以认为是一个典型的高质量“Hub”网页。
Authority 页面（权威页面）：是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google 和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。
HITS 算法的思想基于如下两个假设：
假设1：一个好的“Authority”页面会被很多好的“Hub”页面指向
假设2：一个好的“Hub”页面会指向很多好的“Authority”页面
假设每个页面都有对应的 Hub 值和 Authority 值，并且初始值都为 1 。可利用上面提到的两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值(值 +1 或其他策略)，直到权值稳定不再发生明显的变化为止。更多关于 HITS 算法的细节可以查看尾部的参考文献。
加权关联规则挖掘
在知道了 HITS 算法的思想后。同样的，我们也可以做出如下假设：
假设1：一个高质量的事务应该包含很多高质量的项。
假设2：一个高质量的项应该被很多高质量的事务所包含。
所以基于假设，论文 [1] 就提出了一种新的度量方式，称之为 w-support。
给定一个事务数据库。我们可以绘制出其对应的二部图（bipartite graph）
二部图（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 度量计算关联规则的支持度和置信度。计算的公式如下：
与传统关联规则挖掘类似，加权关联规则挖掘算法的步骤一般也被划分为两步
- 利用最小支持度从数据库中找到频繁项集。
- 利用最小置信度从频繁项集中找到关联规则。
在论文中，作者还做了两个有趣的实验来验证他 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 不是单纯的依赖频数。
网友评论