一种结合用户和项目聚类的协同过滤算法

罗 弦，丁 箐，王 禹

(中国科学技术大学 软件学院，安徽省合肥市 235000)

0 引言

推荐系统是解决“信息超载”现象的最有力的措施[1]。在推荐系统中，系统的推荐策略和工作方式是核心组成部分，它是由推荐算法决定的，因此关于推荐算法的研究成为该领域的焦点。根据使用的数据源和领域知识不同，推荐算法分为基于内容的(Content-Based)、基于人口统计学的(Demographic-Based)、协同过滤(Collaborative Filtering，CF)以及其他推荐方法。

目前研究最深且应用最广的推荐算法是协同过滤算法[2]，其原理依据是“人以群分，物以类聚”。本文研究的是基于内存(Memory-Based)的CF，它无需预先训练模型，是一种启发式的算法。它利用用户和项目的邻居信息计算相似度并预测目标用户对项目的评分[3]，从而获得推荐。

基于用户的推荐[4]和基于项目的推荐[5]是CF的两大思路。基于用户的CF依据其他相似用户的评分为目标用户产生推荐，随着用户数量增大，评分矩阵稀疏和算法复杂度增高是显而易见的问题，且推荐结果的可解释较差。基于项目的CF根据项目之间的相似度来计算预测值，它存在可拓展性差、忽略项目属性等问题。鉴于二者存在的诸如数据稀疏性[6]、冷启动(实际上是数据稀疏的极端表现)[7]、可拓展性[8]等问题，多位研究者提出包括BP神经网络、Naive Bayesian分类方法、基于内容预测的矩阵填充和矩阵降维等方法。同时为了提高协同过滤推荐速度及实时性，多位研究者提出包括K-Means聚类算法、Gibbs Sampling方法等方法。经典的相似度度量方法对数据稀疏性的表现较差，有研究者提出改进的相似度度量策略，比如定义社交网络中用户属性相似和互动相似度，并将两部分线性拟合重新构造总体的相似度。

本文基于上述研究背景，在传统的协同过滤基础上，结合用户聚类和项目聚类，重新构成相似度的度量方法和预测评分的计算方式，提出一种改进的协同过滤算法。

1 传统的协同过滤算法

1.1 问题描述

为简化问题，仅就基于用户的CF来继续以下的讨论。基于项目的CF在原理上与之十分类似，不再赘述。

1.2 最近邻查询

最近邻集合的查询是CF最重要的步骤，相似度的计算方式直接影响最近邻选取的效果和效率。要计算用户对之间的相似度大小，首先得到该用户对共同评价过的所有项目集合，然后根据选取的相似度度量方法计算二者之间的相似度。常用的相似度度量方法有Jaccard系数、Minkowski距离、Cosine相似度、Pearson相关系数[9]等。其中Pearson相关系数对数据作了归一化处理，在实际应用的大多数时候有着更好的表现。用Iij表示i用户和j用户共同评价的所有项目集合，x是属于该集合的一个项目，Sim(i，j)为这两个用户之间的Pearson相关系数，公式如下所示：

(1)

最近邻查询是利用用户对项目的评分信息，计算出需要推荐服务的用户u和别的用户的相似度Sim(u，Ni)，最后得到与u相似度最高的若干用户形成最近邻集合N(u)。最近邻居集合N(u)的选取是下一步预测评分并产生推荐的重要前提，具体方法有阈值法、Top-N法等。

1.3 产生推荐

得到最近邻集合N(u)后，下一步就是计算预测的评分结果，并排序产生推荐列表。通过以下公式来计算出用户u对项目i的预测的评分Pu,i：

(2)

在得到用户对未知项目的预测评分之后进行排序，选取由高到低序数靠前的若干个项目作为推荐内容呈现给目标用户。

2 改进的协同过滤算法

2.1 针对相似度的优化

一首流行歌曲，几乎人人都听过，并且通常做出非个性化的评价。“哈利波特”问题阐明了热门项目对相似度的贡献较小。针对于此，相关文献[10]提出对Pearson相关系数作以下修正:

(3)

其中N(c)表示项目c在用户-项目评分矩阵中被评价的总次数。在实际应用中发现单纯凭借Pearson相关系数并不可以解决数据稀疏带来的一些问题，比如用户之间相关联的项目数量过少(共同评价项目过少)。为了降低这一现象带来的影响，相关文献[11]引入显著性加权因子α，即共同评价的物品数量占各自全部评价数量的比重：

(4)

其中Iu表示用户u评分的全部项目，Iv表示用户v评分的全部项目，Iu,v表示用户u和用户v共同评分的全部项目。从公式中可以清晰地看出用户间的相似度随着共同评价物品数量减少而减少。本文将用户间相似度的计算方法改进为：

Sim′(u,v)=α×Sim(u,v)

(5)

2.2 结合用户聚类和项目聚类的协同过滤

如果用户集合大小为M，项目集合大小为N，传统的协同过滤算法的时间复杂度为O(N*M*M)[12]，伴随项目规模和用户规模的激增，计算开销也随之增高。为了改善算法的性能，提高系统的可拓展性，利用聚类对数据进行预处理是经常采用的策略。

将基于k均值的聚类算法[13]应用到协同过滤中算法中。首先对用户-项目评分矩阵进行聚类分析，距离函数采用余弦相似性，将用户集合划分为p个簇，将项目集合划分为q个簇。又将目标用户划分到与其聚类质心最近的一个簇，然后在该簇中进行最近邻查询并预测评分。前文已经提到基于用户的CF和基于项目的CF各有各自的片面性和局限性，在预测未评分的时候如果只是基于用户的预测方法或者基于项目的预测方法，都将会忽略其他有用的信息，所以采用以下公式对二者进行聚类分析后的结合：

Pu,i=mPu(u,i)+nPi(u,i)

(6)

(7)

(8)

从公式(7)和(8)中注意到m+n=1。也就是说，在改进的算法中，用户维度和项目维度的预测评分的贡献度是由目标用户和项目与各自的聚类质心的余弦相似性得到的。

2.3 改进后算法的描述

首先使用k均值聚类算法，距离函数采用余弦相似性，对用户和项目进行两个维度的聚类分析。这一步骤可以离线进行，对于用户数量和项目数量变化稳定的系统大大降低了计算复杂度、节省了时间。

然后针对目标用户和项目划分到距离聚类质心最近的簇。其中计算Pu(u,i)采用针对流行项目、共同评分过少而优化的相似度计算方法计算相似度，在簇类选取top-K个最近邻；计算Pi(u,i)则使用传统的Pearson相关系数在项目所属簇类中取top-K个最近邻。

最后使用公式(7)和公式(8)对二者按照参数m和n进行配比，产生最终预测评分Pu,i，选取评分最高的若干项产生推荐。具体的流程图如图1所示。

图1 改进后算法的流程示意

3 实验

3.1 数据集

为评估改进后的协同过滤算法实验效果，本文使用MovieLens数据集中的第二个版本中的数据(ml-1M)，包括了6 040个用户对3 900部电影的1 000 209个评分记录。其中评分在1～5分之间。对其中部分数据进行预处理后的评分密度为8.2%，稀疏度为91.8%，可以看出评分矩阵相当稀疏。

3.2 实验度量标准

评分预测系统一般采用平均绝对误差MAE[14]或是均方根误差RMSE来评估算法的预测准确度。本文选择MAE作为评估改进后算法的推荐精度的衡量指标。公式如下：

(9)

3.3 实验方案和结果

本文通过三个实验方案验证改进后的结合用户聚类和项目聚类的协同过滤算法的可行性。

实验一：固定用户聚类数目p=10，不同项目聚类数目q下的MAE的变化值。q从4到20，步长为4。为控制变量，将用户和项目最近邻查询步骤中的k都设为20。实验结果如图2所示。

图2 实验一的实验结果折线图

实验二：固定项目聚类数目q=10，不同用户聚类数目p下的MAE的变化值。p从4到20，步长为4。为控制变量，将用户和项目最近邻查询步骤中的k都设为20。实验结果如图3所示。

图3 实验二的实验结果折线图

实验一和二说明聚类数目会影响预测评分的准确性。聚类数目过大时，相似对象之间的相似成分所致的影响降低，簇信息过于个性化；聚类数目过小时，不相似对象之间的相似成分所致的影响降低，簇信息过于大众化。取适中的聚类数目才会有较好的预测准确度。

实验三：固定用户聚类数目p=10和项目聚类数目q=10，不同最近邻k的选择下传统协同过滤和本文提出的算法的MAE值比较。实验结果如图4所示。

图4 实验三的实验结果对比折线图

由实验三可见采用改进后的基于聚类的协同过滤算法对比传统的协同过滤算法有着较高的预测准确度。

4 结束语

本文首先讨论了协同过滤的算法在实践过程中遇到的问题，面对诸如数据稀疏性和可拓展性等情况，传统的协同过滤算法并没有展示出上佳的表现。针对于此提出一种改良的协同过滤算法。新算法在相似度计算和预测评分计算上利用了聚类分析结果，结合用户聚类和项目聚类减小了最近邻查询空间，降低用户相似度和项目相似度单方面造成的误差。并通过实验，在MovieLens数据集上验证该算法相较于传统的协同过滤算法在预测准确度上的优越性。

虽然本文对传统协同过滤算法进行了一定程度的改良和优化，但是仍然存在一些亟待解决的问题，比如数据来源单一化，本文仅涉及用户评分和物品属性信息，像用户人口统计学信息、社交网络信息、隐性和显性的知识等，均可以加入算法中；由于时间和实验条件的限制，本文仅仅采用单一的离线的数据集进行离线预测，读者可以利用其他数据集验证本算法的鲁棒性，并且具体的评价指标也不单是预测准确度中的MAE，还有惊喜度、信任度、多样性、满意度等评价准则都未进行针对性评测；本文是基于内存的算法，利用用户和物品的最近邻信息获得推荐，还有一类基于模型的算法，这一类算法可以使用机器学习中的分类、聚类、半监督学习、神经网络等方法利用已有的信息训练出一个预测模型，然后调整参数至收敛。使用预测模型获得推荐结果也有很大的研究空间。