基于相似传播和情景聚类的网络协同过滤推荐算法研究

曾群　程晓

〔摘要〕互联网时代，个性化推荐系统逐渐被应用到各个不同的领域，随之个性化推荐算法也成为目前研究的热点。然而，传统的推荐算法往往存在着冷启动、数据稀疏等问题。本文在对传统推荐算法研究的基础上，提出了一种基于相似传播和情景聚类的协同过滤推荐算法，根据计算用户间的情景相似度对用户进行聚类，然后根据相似传播原理找出目标用户更多的最近邻居，最后根据预测目标用户对项目的评分进行推荐。借助网上公共数据集在Matlab上实现了该算法并验证了算法的有效性。实验结果表明，本文所提算法的准确性相比传统算法有所提高，同时缓解了传统推荐算法存在的冷启动和数据稀疏性等问题。

〔关键词〕相似传播；情景聚类；协同过滤；推荐算法

DOI：10.3969/j.issn.1008-0821.2016.11.009

〔中图分类号〕G2062〔文献标识码〕A〔文章编号〕1008-0821（2016）11-0050-05

〔Abstract〕In the age of the Internet era，the personalized recommendation system gradually is applied to different fields and recommendation algorithm has become a research hot spot at present.Traditional recommendation algorithm，however，often has some problems，for example a cold start，sparse data.In this paper，on the basis of researches on traditional recommendation algorithm，this paper proposed a collaborative filtering recommendation algorithm based on similarity propagation and context clustering.Computing the similarity between user for user clustering，then the paper found more nearest neighbors of target users，according to the similarity propagation to finally，it recommended projects according to the forecast target users ratings.With the help of online public data，the paper implemented the proposed algorithm and verified the effectiveness of the proposed algorithm on Matlab.experiment showed that the accuracy of the proposed algorithm compared with the traditional algorithm was higher，and the proposed algorithm relieved the problems of traditional recommendation algorithm，such as the cold start and sparse data，etc.

〔Key words〕similarity propagation；context clustering；collaborative filtering；recommendation algorithm

如今，互联网已经成为人们获取信息的重要途径。然而，随着网络上信息量越来越大，信息过载的问题也越来越严重，这对人们在网上快速查找精确信息造成了很大的困难。个性化推荐系统能够根据用户的兴趣偏好、项目、需求甚至通过感知用户的情景来向用户推荐信息，这不仅很好地解决了信息过载的问题，同时还满足了用户的个性化需求。在实际应用方面，亚马逊、当当等大型电商网站都开发出了自己的推荐系统。在学术研究领域，个性化推荐方面的研究也逐渐进入学者的视野并得到关注，例如美国的Grouplens团队、Alexander Tuzhilin教授、Paul Resnick教授等对个性化推荐系统及相关的推荐算法进行了深入的研究[1]。

1问题的提出

协同过滤推荐算法作为目前研究较成熟、应用范围较广的推荐算法已被广泛地运用于互联网各大推荐系统中[2]。然而，传统的协同过滤推荐算法推荐的准确率和推荐效率往往受到多方面的影响，如对于新用户存在的冷启动问题和由于评分矩阵数据稀少导致的数据稀疏问题对推荐算法的质量产生的影响。

本文对传统的推荐算法进行了改进，将相似传播的思想和用户的情景与协同过滤推荐相结合，提出了一种基于相似传播和情景聚类的网络协同过滤推荐算法，在传统协同过滤算法存在的问题得到了较好缓解的同时也提高了推荐算法推荐的准确率。

2相关概念及理论

21情景的定义

情景在不同的领域有不同的定义，心理学、情报学、哲学、组织行为学、教育学、社会学等领域的众多学者都对情景进行了深入的研究和探讨，但关于情景的定义学者们都各执己见，不能达成一致共识，因此情景一直没有统一的定义。Dey等人认为能描述某一实体特征的信息即为情景[3]。虽然这一定义目前被广泛引用，但由于不同领域对情景的理解各不相同，情景的定义一直无法准确给出。大多数学者都认同：情景是和实体是不可分的，情景只有与实体产生联系才具有意义，情景可以将实体的相关信息进行详细的描述。

22聚类的概念

聚类是利用一定的方法将数据集合划分成簇中各成员间相似度较高但簇与簇间各不相同的多个簇的过程。聚类的结果往往随着所使用的聚类方法的改变而改变，使用不同的聚类方法对相同的数据集进行聚类，产生的最终结果也可能不同。划分的过程不是通过人，而是通过聚类算法进行的。

23协同过滤推荐

协同过滤推荐（Collaborative Filtering Recommendation，CFR）是根据用户的兴趣偏好及相关信息找到与用户相似的群体，将该群体感兴趣的内容作为待推荐的内容推荐给用户。协同过滤推荐不需要用户显式查找自己感兴趣的内容或项目，而是根据已有用户对项目的评分来预测计算该用户的评分，进而根据评分高低对用户进行推荐，因此该方法在许多领域得到广泛的应用。

3传统协同过滤推荐算法

协同过滤推荐的原理是根据用户的兴趣偏好及相关信息找到与用户相似的群体，将该群体感兴趣的内容作为待推荐的内容推荐给用户。其中，基于记忆的协同过滤在实际运用中运用范围较广，它又可以根据被计算相似度的对象的不同分为用户和项目两种类型[4]。

31基于用户的协同过滤

基于用户的协同过滤（User-based CF）推荐算法首先是查找与目标用户相似的群体（即目标用户的最近邻），这一过程通常通过利用系统中已有“用户-项目”评分矩阵中的评分数据来计算用户与用户之间的相似度来完成；然后根据生成的最近邻集合中的用户对项目的评分数据，利用评分预测计算公式来计算得到目标用户对某一项目的预测评分；最后根据预测结果对目标用户进行推荐。整个推荐过程大致可分为目标用户最近邻查找和目标用户对项目的评分预测。余弦相似性、修正的余弦相似性、Tanimoto系数，Pearson相关系数[5]等是在计算相关系数时较常使用的方法。

User-based协同过滤推荐算法在计算用户间的相似度时多是采用Pearson相关系数的计算方法，根据已有用户对项目的评分矩阵进行计算。计算用户u与u′间的相似度，计算公式如下：

sim（u，u′）=∑s∈I（u，u′）（r（u，s）-（u））（r（u′，s）-（u′））∑s∈I（u，u′）（r（u，s）-（u））2（r（u′，s）-（u′））2

其中，r（u，s）代表用户u对项目s的评分，r（u′，s）代表用户u′对项目s的评分；（u）代表用户u对所有项目评分的平均分，（u′）代表用户u′对所有项目评分的平均分；I（u，u′）代表用户u与用户u′都有评分的项目的集合。

通过计算目标用户与非目标用户间的相似度找到与目标用户相似的用户群体，将该群体的集合作为目标用户的最近邻集合D。生成最近邻集合后，将最近邻集合中用户对项目的评分数据代入评分预测公式来对目标用户进行偏好预测。预测目标用户u对某一项目s′的评分时可采用如下公式[6]：

P（u，s′）=∑u′∈D[sim（u，u′）R（u′，s′）]∑u′∈Dsim（u，u′）

其中R（u′，s′）代表用户u的最近邻集合中的用户对项目s′的评分，sim（u，u′）代表用户u与u′的相似度，D为用户u的最近邻集合。

以上公式计算出来的预测结果将作为对目标用户进行推荐的依据。

32基于项目的协同过滤

基于项目的协同过滤（Item-based CF）推荐算法首先是找到与项目相似的项目群，这一过程通常通过利用已有用户对项目的评分数据计算项目与项目之间的相关系数来完成；项目相似群生成后，根据用户对群体中各项目的已有评分数据来计算用户对某一项目的预测评分；最后根据评分计算结果对用户产生相关推荐。计算项目t与t′间的相似度，计算公式如下：

sim（t，t′）=∑u∈u（t，t′）（r（u，t）-（t））（r（u，t′）-（t′））∑u∈u（t，t′）（r（u，t）-（t））2（r（u，t′）-（t′））2

其中，r（u，t）代表用户u对项目t的评分，r（u，t′）代表用户u对项目t′的评分；（t）代表所有用户对项目t评分的平均分，（t′）代表所有用户对项目t′评分的平均分；u（t，t′）代表对项目t与t′都有评分的用户的集合。

根据项目间相关系数的计算生成项目的最近邻集合I，之后根据生成的相似的项目群体来预测用户对项目的评分。如计算用户a对项目i的预测评分，计算公式如下[7]：

P（a，i）=（i）+∑j∈I（i，j）sim（i，j）（r（a，j）-（j））∑j∈I（i，j）sim（i，j）

其中，（i）代表所有用户对项目i评分的平均分，（j）代表所有用户对项目j评分的平均分；sim（i，j）代表项目i与项目j间的相似度；I（i，j）代表项目i的最近邻集合。

计算出预测评分后依据预测结果对用户进行推荐。

然而，对于新用户和评分数据较少的用户，利用传统的协同过滤推荐算法很难对其进行准确的推荐。本文在对传统推荐算法研究的基础上，将相似传播的思想和用户的情景与协同过滤推荐相结合，提出了一种基于相似传播和情景聚类的协同过滤推荐算法，对传统的推荐算法进行改进以解决冷启动及数据稀疏等问题。由于在个性化推荐的过程中充分考虑用户的情景，使得推荐结果更能满足用户个性化的需求，准确率也相对较高。

4基于相似传播和情景聚类的协同过滤推荐算法

41算法思路

基于聚类的协同过滤推荐算法是根据一定的聚类算法利用已有的“用户-项目”评分矩阵将用户分成多个不同的簇，通过计算用户与各簇的距离来找到与目标用户距离最小的簇作为目标用户的相似用户群体，最后将目标用户相似群体中的用户对某一项目的加权平均分作为目标用户对该项目的评分，以此方式来预测目标用户对项目的偏好程度，然后对用户进行推荐。

然而对于新用户，由于缺少相关信息，在查找用户最近邻时可能会出现很大的误差，最终影响推荐的准确性。情景能很好地描述用户的特征，对个性化推荐有着至关重要的影响。

本文将用户的情景因素引入到个性化推荐中，充分考虑情景对推荐效果的影响，对原有的基于聚类的协同过滤推荐算法在相似度计算公式和用户评分预测公式进行改进，提出了一种基于相似传播和情景聚类的协同过滤推荐算法。该算法根据用户的情景对用户进行聚类，同时引入相似度传播的思想，能够很好地缓解以前算法存在的数据稀疏性问题。

相似传播，就是根据每个用户或项目的最近邻找出最近邻的最近邻，这样能寻找出与目标用户相似的更多的邻居，提高推荐结果的准确性。例如，若用户u的最近邻为u1，而u1的最近邻为u、u2和u3，则在预测用户u对某一项目的评分时，可以根据一定的算法利用用户u1、u2和u3的评分预测用户u的评分，最终进行推荐。

在推荐系统中利用情景对推荐信息进行过滤的时间并非是固定的，根据利用情景的先后，可将情景感知推荐系统分为情景预过滤、后过滤与建模3种不同的形式[8]。情景预过滤是在推荐过程中首先根据用户的情景剔除部分不匹配数据，生成与用户情景相关的评分数据集，之后根据推荐算法对数据集进行用户评分预测，最终将与用户情景匹配的结果推荐给用户。本文所提算法工作流程图如图1所示：

42算法

本文所提算法大致可分为以下3个步骤：

421聚类

本文根据用户情景的不同将用户进行聚类。首先确定出k个聚类中心，然后计算不同情景间的相似度，依此将用户分成k个簇，使得每个簇中的用户有相似的情景。由于情景的属性是混合型的，在计算情景间相似度前需对用户的情景进行抽象描述。本文通过采用余弦相似性计算用户情景的相似性对用户进行聚类。将用户的情景定义为C，计算情景C1与情景C2间的相似性的计算方式如下：

sim（C1，C2）=C1·C2C1C2

通过计算情景间的相似性，将情景相似度高的用户聚类在一起，生成情景最近邻集合M。

422最近邻集合的生成

计算目标用户到通过情景聚类得到的各簇之间的距离，找到与目标用户距离最近的簇，并计算目标用户与簇中各用户间的相似度。本文在传统的计算用户相似度的基础上引入用户的情景因素，对传统的相似度计算方法进行改进，提出了基于情景的用户相似度的计算，如计算目标用户u与用户u′间的相似度，计算方法如下：

sim（u，u′）=∑j∈I（u，u′，c）（r（u，c，j）-（u，c））（r（u′，c，j）-（u′，c））∑j∈I（u，u′，c）（r（u，c，j）-（u，c））2（r（u′，c，j）-（u′，c））2

其中，r（u，c，j）代表用户u在情景c下对项目j的评分，r（u′，c，j）代表用户u′在情景c下对项目j的评分；（u，c）代表用户u在情景c下对所有项目评分的平均分，（u′，c）代表用户u′在情景c下对所有项目评分的平均分；I（u，u′，c）代表用户u与用户u′在情景c下有共同评分的项目的集合。

根据以上公式计算出目标用户与簇中各用户的相关系数，将与目标用户相似度较高的用户放入同一集合中，生成目标用户的最近邻集合N。

在计算项目与项目间的相似度时，本文在基于项目的协同过滤经典算法Slope One算法[9]中引入用户的情景，形成“用户-情景-项目”模型，在计算项目间相似度时将情景因素对用户对项目评分的影响考虑在内，提出基于情景的项目相似度计算方法，计算项目t与项目t′的相似度的计算方法如下：

sim（t，t′）=1-∑u∈U（c，t，t′）[r（u，c，t）-r（u，c，t′）]U（c，t，t′）Pm

其中r（u，c，t）代表用户u在情景c下对项目t的评分，r（u，c，t′）代表用户u在情景c下对项目t′的评分；U（c，t，t′）代表在情景c下对项目t与t′均有评分的用户数，U（c，t，t′）代表在情景c下对项目t与项目t′均有评分的用户的集合，Pm表示满分评分。

通过计算项目间的相关性生成项目的相似项目群作为项目的最近邻集合A。

423推荐的生成

假设用户u的用户最近邻集合表示为N，情景c的情景最近邻集合表示为M，项目t的项目最近邻集合表示为A，则用户u在情景c下对项目t的预测评分Gu，c，t可通过目标用户u的用户最近邻集合N中的用户在情景c下对项目t的评分，目标用户u在情景c的情景最近邻集合M下对项目t的评分，以及目标用户u在情景c下对项目t的项目最近邻集合A中项目的评分求得。用户u在情景c下对项目t的预测评分计算方法如下：

Gu，c，t=13k1∑u′∈Nsim（u，u′）[R（u′，c，t）-（u′，c）]+（u，c）+k2∑c′∈Msim（c，c′）[R（u，c′，t）-（c′，t）]+12[（c，t）+（u，c）]+k3∑t′∈Asim（t，t′）[R（u，c，t′）-（c，t′）]+（c，t）

其中k1=1∑u′∈Nsim（u，u′），k2=1∑c′∈Msim（c，c′），k3=1∑t′∈Asim（t，t′）。R（u′，c，t）代表用户u′在情景c下对项目t的评分，R（u，c′，t）代表用户u在情景c′下对t的评分，R（u，c，t′）代表用户u在情景c下对项目t′的评分；（u′，c）代表用户u′在情景c下对所有项目评分的平均分，（c′，t）代表所有用户在情景c′下对项目t评分的平均分，（c，t′）代表所有用户在情景c下对项目t′评分的平均分；（u，c）代表用户u在情景c下对所有项目评分的平均分，（c，t）代表所有用户在情景c下对项目t的评分的平均分。

43实验和结论

为了验证本算法的有效性，笔者利用Matlab进行了验证。本文用来验证的数据集来自Grouplens提供的公开数据集，该数据集中包含了用户的情景信息、用户对电影的评分（1～5分之间）。笔者通过对公开数据集中数据的处理，从原始数据集中选出评分较多的用户，其中包括1 000名用户在不同情景下对3 000部电影做出的160 000条评分作为验证数据，其中用来训练的数据占70%，用来测试的数据占30%，实验对预测分数达45分以上的电影向用户做推荐。

在仿真过程中，通过计算不同算法（含本文算法与传统算法）间的平均绝对误差（MAE，Mean Absolute Error）来加以证明本文算法的有效性。设预测评分集合为P={p1，p2，p3，…，pi，…，pn}，实际评分集合为Q={q1，q2，q3，…，qi，qn}，则平均绝对误差的计算公式如下：

MAE=∑ni=1pi-qin

所得结果如图2所示。由图中可看出在最近邻数目相同时，本文算法的MAE值明显小于Slope One算法和传统的协同过滤推荐算法，本文所提算法推荐的准确率与以上两种算法相比相对较高。

5结语

本文在对用户进行推荐时充分考虑用户的情景因素对推荐结果的影响，根据情景间的差异将用户进行聚类，且在计算用户和项目相似度以及用户对项目的预测评分时也将情景的影响考虑在内，最终实现对用户的项目推荐，仿真实验证明了本文所提算法是有效且可行的。由于在推荐过程中不仅考虑用户的情景因素对用户偏好的影响，同时引入相似传播的思想使得目标用户能找到更多的邻居，这样很好地缓解了传统算法中一直存在的冷启动问题，而且进一步提高了推荐算法的准确率。但由于在根据用户情景对用户进行聚类时需反复迭代，计算所花时间较长，造成整个推荐过程所花时间相对较长，因此未来的研究希望能图2不同算法的MAE值比较

在提高推荐效率上有所突破。

参考文献

[1]冯鹏程.基于情境感知的个性化推荐算法的研究[D].上海：东华大学，2014.

[2]邓晓懿，金淳，韩庆平，等.基于情境聚类和用户评级的协同过滤推荐模型[J].系统工程理论与实践，2013，（11）：2945-2953.

[3]詹丽华，李育嫦，潘瑞冰.基于情景感知的移动搜索的演变和实现[J].图书馆理论与实践，2015，（11）：102-105.

[4]奉国和，梁晓婷.协同过滤推荐研究综述[J].图书情报工作，2011，16：126-130.

[5]邱均平，张聪.高校图书馆馆藏资源协同推荐系统研究[J].图书情报工作，2013，22：132-137.

[6]罗文.协同过滤推荐算法综述[J].科技传播，2015，（7）：115，196.

[7]董坤.基于协同过滤算法的高校图书馆图书推荐系统研究[J].现代图书情报技术，2011，（11）：44-47.

[8]申艳光，郭高尚，吴晶晶.结合情景和协同过滤的移动推荐算法[J].科学技术与工程，2014，（8）：49-52，64.

[9]王毅，楼恒越.一种改进的Slope One协同过滤算法[J].计算机科学，2011，（S1）：192-194.

（本文责任编辑：郭沫含）