论文阅读笔记 The Wisdom of the Few

<阅读笔记>

参与了dantezhao的一个论文阅读计划 paper-notes

将阅读成果分享到博客

最近邻协同过滤做用户推荐，
一种传统的方法是，将近邻算法应用于用户打分数据并得出结果；
另一种非传统的方法是，基于一个独立数据集的专家打分数据

本文介绍了非传统的方法，在专家数据的基础上，使用最近邻协同过滤生成推荐

这种方法在文中也被称为少数智慧方法(The Wisdom of the Few approach)

该方法主要用于解决冷启动问题

带着问题阅读：
1. what: 最近邻协同过滤和专家数据的概念  
2. why: 为什么使用专家数据代替传统的用户数据  
3. how: 如何用这种方式实现用户推荐

0. 摘要

最近邻系统过滤做用户推荐的缺点：
a) 数据稀疏和噪音
b) 冷启动问题
c) 可扩展性

传统最近邻协同过滤基于用户打分数据(user-rating data)

新方法则基于独立数据集的专家近邻(expert neighbors)数据

新方法既能克服传统方法的缺点，又能保证相对的精确性

本文从Netflix的数据集爬取专家评分作为基础数据，从预测准确性和推荐精准度两方面来分析结果

最后本文还会给出一个用户使用报告，评估用本文方法生成的推荐

1. 导言

协同过滤和最近邻算法

协同过滤(Collaborative filtering, CF)是构建用户推荐系统的主流方法

CF算法基于其他相似用户的打分，向特定用户推荐产品

最近邻算法(The Nearest Neighbor algorithm)就是为每个用户找出一批相似的用户，通过相似用户的资料做出推荐

然而，再做出推荐之前，找出相似用户面临如下问题：
a) 数据稀疏性和噪声
b) 计算成本高

数据来源

本文探索如何从特定群体（专家群体expert)的专业评分来预测大众行为

新近的研究发现，基于反馈(feedback-based)的CF算法有相当一部分误差(error)来自于用户反馈的噪声

所以本文使用了掺杂较少噪声的专家数据源来做推荐

本文关于专家(expert)的定义：
在某个特定群体中，对产品的评估(打分)有见解、质量稳定、可信度高的一批人

研究目标

本文的研究目的不是提高协同过滤算法的准确性(accuracy)

本文主要关注如下几点：
a) 如何从一个小群体用户推测大范围用户的行为

b) 发掘从一个独立不相关的数据集生成推荐的潜在效果

c) 分析专业评分者能否为普通用户提供良好的预测

d) 论述本文使用的方法能否解决传统CF算法的缺陷

本文贡献

1) 收集并比较了两个数据集的特点：Netflix用户的电影评分数据集vs.网络搜集的150个专业影评人影评数据

2) 设计了一套基于专家意见预测个人评分的方法

3) 从两方面评估使用专家意见来预测用户选择的效果：
    a) 预测准确性
    b) 推荐列表精确度

2. 从网络挖掘专家打分数据

获取数据

作者在第一个段落简单说明了获取专家打分数据有两种途径：
a) 从可靠数据源获取原始评测数据，使用模型推算出打分
b) 从网络爬取线程的数据

本文的专家影评数据爬取自烂番茄网站

这些专家数据可以匹配到Netflix影库（17770部影片）中的8000部

虽然舍弃了很多数据，但是50%（8000比17770粗略地视为50%）左右的Netflix影片数据已经足够用于计算

为了更为精确，本文为专家设定了一个最少观影量ρ=250，又从1750位专家中筛选出169位作为最终的专家数据集

极少的数据量印证了本文所用新方法的潜力

2.1 数据集分析，用户和专家

打分数量和数据稀疏性（Figure 2a, 2b）

用户数据来自Netflix，专家数据来自烂番茄(Rotten Tomatoes)

1) 数据稀疏性
    a) 用户数据的稀疏性系数约为0.01，表明用户矩阵中只有1%的位置有非零值
    
    b) 专家数据的稀疏性系数约为0.07

2) Figure 2b: 每个用户/每个专家的打分数据累积分布函数(CDF of ratings per user and expert)
    
    a) 平均每个Netflix用户为少于100部电影打分，其中只有10%的用户为超过400部电影打分
    
    b) 平均每个专家为400多部电影打分，其中10%的专家为1000部以上的电影打分

3) Figure 2a: 每部影片的打分数据累积分布函数(CDF of ratings per movie)
    
    a) 平均每部影片有1000个Netflix用户打分
    
    b) 平均每部影片有100个专家打分

总结：专家矩阵比用户矩阵稀疏性更弱，分布更为均匀

平均打分分布（Figure 3a, 3b）

1) Figure 3a：基于影片的平均分数分布情况
    
    a) Netflix影库中每部电影平均得分为0.55(3.2星)，10%的影片分数在0.45(2.8星)或更少
    
    b) 专家数据集的影片平均得分为0.6(3.5星)，有10%的影片分数低于0.4(2星)，另有10%的影片分数高于0.8(0.8~1之间)


2) Figure 3b描绘了基于用户/专家的平均打分分布情况
    
    a) Netflix用户评分正态分布在0.7(0.4星)左右
    
    b) 专家评分的正态分布在0.6(3.5星)左右


3) 由图所得结论
    
    a) 基于影片(per movice)的专家评分，差异性大于基于用户(per user)的专家评分
      原因可能是专家有更强的评分意识，无论电影是否喜欢都会去观看并打分
      普通用户倾向于观看受好评的影片
    
    b) 大部分的高分电影专家都会打高分，说明专家对优秀电影的看法较为一致

打分的标准差（Figure 4a, 4b）

1) Figure 4a: 基于影片的标准差分布(std per movie)
    
    a) Netflix库内影片得分的标准差在0.25(1星)左右，差异性比较小
    
    b) 专家库内影片得分的标准差在0.15左右，差异性稍大


2) Figure 4: 基于影片的标准差分布(std per user)
    
    a) 基于Netflix用户的标准差大约为0.25，差异性大于基于影片的标准差
    
    b) 基于专家用户的标准差大约为0.2，差异性较小

总结

上述数据分析展现了普通用户和专家的异同：

1) 专家数据稀疏性更比普通用户小

2) 专家为大部分的电影打分，而不是只评受欢迎的影片

3) 对于优秀的电影，专家和大众看法一致

4) 基于电影的标准差，专家和普通用户一样偏低，说明专家和普通用户观点趋于一致

5) 基于专家的标准差比基于普通用户的标准差低，说明专家个人平均打分相差不大

3. 专家最近邻

这一段主要解释了最近邻方法的使用和公式的构成

方法介绍：协同过滤通常会使用KNN(k-NearestNeighbor)算法

    a) 基于k个最近邻，计算出用户-物品预测值

    b) k近邻可以是用户的最近邻也可以是物品的最近邻

    c) 本文选取基于用户的最近邻，正好适合专家数据

计算步骤拆解

1) 首先，计算出用户-物品的分数矩阵

2) 接着，计算所有用户的相似度
2.1) 选用一个余弦相似度(variation of the cosine similarity)的变体  

2.2) 该余弦相似度包含一个校正系数(adjusting factor)  

2.3) 这个校正系数含有与两类用户都相关的物品的数量

与传统CF计算的不同

a) 只选用专家数据预测用户打分  

b) 生成一个相似度矩阵，将每个用户和专家数据集进行比较  

c) 选用与普通用户的相似度超过δ(Delta)的专家，用于预测用户对特定物品的打分

选用固定阈值(fixed threshold) δ 遇到的问题和解决方法

a) 有可能只找到非常少的近邻

b) 即便找到了近邻，这个近邻也有可能没为当前物品打分

c) 为了解决上述两个问题，方法中引入一个置信阈值τ(Tau)

d) τ用来限定专家所拥有的最少近邻数，而且这些近邻必须为当前物品打过分

下一段落预告

下一段落主要介绍 δ 和 τ 两个参数的相互作用

这两个参数的最优设置取决于数据集和实现方法的设计

为了与传统的CF方法作比较，本文采用基于相同阈值的最近邻方法

4. 结果解释


基于前述数据，为了验证169个专家预测10000个Netflix用户的效果如何

设计了两套实验：

1) 衡量预测推荐的平均误差(mean error)和覆盖率

2) 衡量推荐列表的精准度(precision)

4.1 推荐误差

拆分数据集

为了评估专家打分的预测潜力，我们用随机抽样将用户数据集分成两部分
a) 80%的训练数据集
b) 20%的测试数据集

最终使用k折叠交叉验证的平均结果，k值为5(5-fold cross validation)

平均绝对误差(MAE, mean average error)和覆盖率(coverage)

1) 专家选择(Critics&apos; Choice)  
用所有专家比上每个给定物品，得出一个平均值
这个平均值作为最差结果衡量基线(worst-case baseline measure)
可以看成一种非个性化的专家选择推荐(Critics&apos; Choice)
专家选择推荐的平均绝对误差是0.885，覆盖率是全覆盖(100%)

2) 专家协同过滤(Expert-CF)
同样使用专家数据，将置信阈值τ设为10，最小相似度δ设为0.01
这种情况下平均绝对误差为0.781，覆盖率为97.7%

3) 标准近邻协同过滤(Standard neighbor-CF)  
忽略专家数据集，仅使用Netflix用户，置信阈值τ取值10，最小相似度δ取值0.01
得到平均绝对误差0.704，覆盖率92.9%

对比专家选择的平均值，专家协同过滤(Expert-CF)在准确度方面有显著提升

将覆盖率考虑进来，置信阈值τ和最小相似度δ两个参数的设置只带来了很小的损失

6. 论述

6.1 本文论述涉及的几个点

本文介绍了一种基于少数专家评分为大众用户生成预测的推荐系统

数据来源于网络上的专家影评

本文采用的专家评测体系与可信度(trust)相关
在可信度敏感的推荐系统中，近邻的影响力可以通过他们对现有用户是否可靠来权衡

基于专家数据的近邻协同过滤在预测准确性方面并没有比原始的方法更优越

6.2 专家数据如何解决传统方法的缺陷

1. 数据稀疏(Data Sparsity)

从上下文看，本文所说的数据稀疏是指用户的打分比较分散

在标准的协同推荐系统中，用户打分数据的稀疏导致了数据不一致性和噪声

专家打分往往会涵盖大部分的评测对象，解决了数据稀疏问题

1. 噪声和恶意打分(Noise and Malicious Ratings)

普通用户打分会因为草率或恶意操作带来数据噪声，影响预测质量

专家的评分质量稳定(consistent)，打分时有较强的主观意识，因而减少了数据噪声

同时，专家数据集更为可控和稳定，可以规避恶意评测和用户注入攻击的问题

1. 冷启动问题(Cold Start)

冷启动是指评分系统中新增的评测对象因缺少评分数据而无法被推荐的问题

新加入系统的用户也面临冷启动的问题

专家在得知新评测对象的时候往往会立即打分，从而减弱了冷启动问题

专家打分的数据集具备较少的稀疏性和噪声，也能够改善冷启动问题

1. 可扩展性(Scalability)

计算N个用户和M个评测对象的矩阵，复杂度是O(N²M)

每当新的评测对象加入系统时，都需要更新矩阵

CF算法的可扩展性受到了算法复杂度的限制

虽然k-means聚类等方法可以用来应对可扩展性问题，但是可扩展性仍然是CF算法的主要研究议题

基于专家数据的方法，因为数据集小，对数据量的扩充并不敏感，也就没有显著的可扩展性问题

1. 隐私(privacy)

为了维护和更新相似矩阵，系统必须传输所有用户评分到某个中央节点用于统一计算

专家数据集容量非常小，传输方便，在客户端本地即可实现运算

7. 结论

方法的使用

本文所述的"少数人智慧"的方法，基于外部独立的数据源中少量的专家打分，对大众用户打分进行预测

基于专家数据的方法与传统CF方法具有可比性

当前方法使用169个专家打分数据来预测Netflix电影打分数据，在平均误差上与传统方法相当

同时该方法也在top-N推荐设置里进行了验证

用户调研显示，在冷启动场景中，新方法比传统的近邻协同过滤更好

新方法在一定程度上解决了传统方法的几个缺陷：
a) 数据稀疏 
b) 可扩展性 
c) 用户反馈中的噪声 
d) 隐私 
e) 冷启动

改进和发展

1) 本文论述了专家协同过滤算法在特定领域的应用，在拥有专家打分体系的其他领域也可以采用

2) 外部专家数据可以和传统CF算法相结合，以改善整体的准确性

3) 本文仅限于基于用户的近邻协同过滤算法，但是其他形式的协同过滤算法也可以使用专家数据这种方式，例如：
    a) 基于物品/评测对象(item-based)的算法
    b) 基于模型(model-based)的算法