基于用户的推荐
算法
为一个用户(u)进行推荐的过程:
for (用户u尚未表达偏好的) 每个物品 i
for (对i有偏好的) 每个其他用户v
计算u和v之间的相似度 s
按权重为s,将v对i的偏好并入平均值
return 值最该的物品(按加权平均排序)
外层循环把每个已知物品作为候选的推荐项,内层循环中逐个查看对候选物品做过评价的其他用户,并记下他们对物品的偏好值,最终,将这些值的加权平均作为目标用户对该物品偏好值的预测.每个偏好值的权重取决于该用户与目标用户之间的相似度.与目标用户约相似,它的偏好值所占权重越大.
但是每个物品都检查速度很慢,实际应用中,通常会计算出一个最相似用户的邻域,然后仅考虑这些用户评价过的物品:
for 每个其他用户 w
计算用户u和用户w的相似度
按相似度排序后,将位置靠前的用户作为邻域n
for (n中的用户有偏好,而u中的用户无偏好的) 每个物品 i // 即候选物品,排除掉非相似用户的物品,用户看过的物品
for (n中用户对i有偏好的) 每个其他用户 v
计算用户u和用户v的相似度 s
按权重s,将v对i的偏好并入平均值
这一过程与前面的主要区别是首先确定相似的用户,再考虑这些相似的用户对什么物品感兴趣,这些物品就称为了推荐的候选项,后续的过程是一样的.这就是标准的基于用户的推荐算法,也是在Mahout中的实现方式.
基于GenericUserBasedRecommender实现算法
DataModel model = new FileDataModel(new File(basePath + "Chapter02/intro.csv"));
UserSimilarity similarity = new PearsonCorrelationSimilarity(model);
UserNeighborhood neighborhood = new NearestNUserNeighborhood(2, similarity, model);
Recommender recommender = new GenericUserBasedRecommender(model, neighborhood, similarity);
UserSimilarity封装了用户相似性的概念,UserNeighborhood封装了最相似用户组的概念.他们是标准的基于用户推荐算法的必要组件.
相似性度量
基于皮尔逊相关系数的相似度
皮尔逊相关系数是一个介于-1和1之间的数,它度量两个一一对应的数列之间的线性相关程度.也就是说,它表示两个数列中对应数字一起增大或减小的可能性.它度量数字一起按比例改变的倾向性,也就是说两个数列中的数字存在一个大致的线性关系.当相关性强时趋于1,弱时趋于0,而负相关的情况下–一个序列的值高而另一个序列的值低,相关值趋于-1.
在推荐中,它用于度量两个用户针对同一个物品的偏好值变化趋势的一致性,都偏高或偏低.取值 -1 到 1.
存在的问题:
- 它并没有考虑两个用户同时给出偏好值的物品数目,如果连个人看过200部共同的电影,即便偶尔评分不一致,也要比两个只看过两部共同电影的人更为相似.
- 如果两个用户的交集仅包含一个物品,则无法进行计算.比如两个用户共同只对一部电影进行了评分.但同时如果两个用户只有一个电影的交集时,也可能不会有太多的相似.
- 如果一个序列中出现偏好值相同的情况,相关系数是未定义的.比如用户对所有电影的评分都是3.0.
可以通过加权来解决上面的问题.即物品数目,考虑的信息越多,所得的相关结果就约可靠.
在基于较多物品计算相关系数时,使相关值向1偏移,使负相关向-1偏移.或者,基于较少的物品进行计算时,可以让相关值向偏好值的均值偏移.Mahout给出了对应的实现.
Mahout中的实现为PearsonCorrelationSimilarity.
根据欧氏距离定义相似度
这一实现基于用户的距离,可以将用户想象成多维空间中的点(维数等于总的物品数),偏好值是坐标.这中相似性度量计算两个用户之间的欧氏距离d.
这个值并不能代表用户相似度,因为值越大表示距离越远,也就是说两个用户越不相似.实际用去 1/(1 + d) 作为相似度.取值0到1.
这种方式可以计算出任何用户之间的相似度,比如连个用户之间的交集物品只有一个,但是根据一件物品计算得到的相似度并不可靠.
Mahout中的实现为EuclideanDistanceSimiliarity.
采用余弦相似性度量
也是将用户偏好值视为空间中的点,并基于此进行相似性度量.
需要将用户偏好值视为n维空间中的点,假设有两条从原点(0,0,…0)出发,分别到这两个点的射线.如果两个用户相似,则他们的打分也相似,也就是说他们的空间位置是很接近的.这样一来,至少这两条射线的方向不会相差太多,两条射线之间的夹角会比较小.反之夹角会比较大.
余弦取值范围-1 到 1之间,小的夹角余弦接近1,大的夹角余弦接近-1.
Mahout中的实现为CosineMeasureSimiliarity.其与皮尔逊相似度的数学推理一致,因此采用同样的实现PearsonCorrelationSimilarity.
采用斯皮尔曼相关系数基于相对排名定义相似度
是皮尔逊相关系数的一个变体,并非基于原始的偏好值,而是基于偏好值的相对排名进行计算.
对于一个用户来说,他们偏好值最低的物品的偏好值被改为1,偏好值次低的物品的偏好值被改为2,以此类推.类似于你对电影进行打分,给最不喜欢的电影一颗星,次不喜欢的电影两颗星.然后在变换后的偏好值上进行皮尔逊相关系数计算.
它保留了偏好值最基本的东西,他们的次序,但是丢掉了用户对不同物品喜好程度的具体差异.介于保留原始偏好值和将他们完全抛弃之间.
取值为 -1 到 1.
Mahout中的实现为SpearmanCorrelationSimiliarity.计算量很大,学术价值大于实用价值.
忽略偏好值基于股本系数计算相似度(Jaccard)
不管一个用户对一个物品的偏好值高低,只关心是否表达过偏好.由两个用户共同表达过偏好的物品数目除以至少一个用户表达过偏好的物品数据而得.
即上图中交集部分除以并集得到的值.当两个用户的偏好集合完全重合时,结果为1,没有任何共同点时,结果为0.取值 0 到1.
当且仅当偏好值为布尔值或根本没有偏好值时才需要用到这一度量方法.或者偏好值中有很多噪音.
Mahout中的实现为TanimotoCofficientSimiliarity.
基于对数似然比更好的计算相似度
它试图反映两个用户由于机缘巧合发生重叠的不可能性.就是说,两个不相似的用户毫无疑问会共同评价一些电影,但是两个相似用户之间的重叠不太可能是出于巧合.
Mahout中的实现为LogLikeLihoodSimiliarity.取值为0到1.
基于物品的推荐
算法
for (用户u尚未表达偏好的) 每个物品 i
for (用户u表达过偏好的) 没个物品 j
计算i和j之间的相似度 s
按权重为s,将u对j的偏好并入平均值
return 值最高的物品 (按加权平均排序)
其实现方式与基于用户的推荐类似.
Slope-one算法
算法
任务两个物品的偏好值之间存在某种线性关系,所以通过某个线性关系函数,例如 Y = mX + b,由物品X的偏好值估计出物品Y的偏好值.Slope-one进一步做了简化,m=1,即斜率为1,只需要确定b = Y - X, 即物品两两之间偏好值的(平均)差异.
算法需要一个重要的预处理步骤,即完成所有物品对之间偏好值的差异:
for 每个物品 i
for 每个其他物品 j
for 对i和j均由偏好的每个用户u
将物品对(i和j)间的偏好值差异加入u的偏好
在此基础上,实现完整算法:
for 用户u未表达偏好的每个物品 i
for 用户u表达过偏好的每个物品 j
找到i和j之间平均的偏好值差异
添加该差异到u对j的偏好值
添加至其平均值
return 值最高的物品 (按平均差异排序)
该算法占用大量的内存,可以将物品之间的差异值转化为离线计算,通过分布式计算以提高速度.
实验性质的算法
基于奇异值分解的推荐算法(SVD)
基于线性插值物品的推荐算法(Knn)
基于聚类的推荐算法
基于模型的推荐算法
缓存封装机制
CachingUserSimiliarity是UserSimiliarity的一种实现,它封装了另一个UserSimilartity的实现并缓存其结果.它利用另一个实现进行计算,并将计算的结果进行缓存.然后当需要提供一个已经计算过的用户间相似度时,它就可以直接返回,而不需要该实现重新计算.
UserSimilarity similarity = new CachingUserSimilarity(
new SpearmanCorrelationSimiliartity(model), model);