基于聚类的协同过滤算法的研究

杨文娟 金子馨

摘要：作为推荐系统中被普遍使用的算法之一，各大电商网站都会利用协同过滤算法来进行相应物品的推荐。对协同过滤算法来说，推荐精度和时间效率两个方面具有重要的研究价值。因此，如何结合这两方面的优势，从而能设计一种时间效率较高，并且推荐精度很好的协同过滤推荐算法是一个很好的研究方向。为了应对大数据时代的信息量过大的问题，聚类算法与协同过滤算法的结合屡见不鲜。基于此，本文主要就各种聚类算法之间的不同，对聚类算法与协同过滤算法的不同结合方式进行了深入的讨论，并就此进行了实验对比分析。

关键词：推荐系统；协同过滤；聚类；矩阵分解

中图分类号：TP393 文献标志码：A 文章编号：1009-3044（2018）16-0185-04

The Research on Collaborative Filtering Algorithm Based on Clustering

YANG Wen-juan， JIN Zi-xin

（School of Computer and Information， Hefei University of Technology， Hefei 230009， China）

Abstract： Collaborative Filtering （CF） is a popular way to build recommender systems and has been widely deployed by many e-commerce websites. For collaborative filtering algorithms， there are two parallel research directions on it， one is to improve the prediction accuracy of collaborative filtering algorithms， and others focus on reducing time cost of collaborative filtering algorithms. Nevertheless， the problem of how to combine the complementary advantages of these two directions， and design a collaborative filtering algorithm that is both effective and efficient remains pretty much open. In order to cope with the large amount of information in the era of big data， the combination of clustering algorithms and collaborative filtering algorithms is common. Based on this， the paper mainly discusses the different combinations of clustering algorithms and collaborative filtering algorithms. ， and conducted an experimental comparative analysis on this.

Key words： recommender systems； clustering； collaborative filtering algorithm； matrix factorization

互联网的快速发展为信息时代的不同类型的用户需求带来了大量的信息。然而，它也带来了一个新的问题，即信息过载问题。该问题给用户选择个人所需信息带来困难，相应地降低了信息的利用率。为了解决这个问题，推荐系统应运而生[1，2]。

协同过滤算法是目前推荐系统领域许多电子商务网站使用最广泛的算法之一[1，2，3]。该算法是利用与目标用户“品味”相类似的用户，推荐这些用户喜欢的物品给目标用户。协同过滤算法主要包括：基于邻居的协同过滤[3]和基于模型的协同过滤算法[4，5，8]。基于邻居的协同过滤时间复杂度低，但是对稀疏性和冷启动问题较敏感。基于模型的协同过滤算法能很好地解决这两个问题，并且能得到很好的推荐精度，但是在时间效率方面仍有待提高。

因此，为了解决上述时间效率方面的问题，许多研究人员将聚类方法加入推荐系统中[6，7]。聚类算法可以将原有的用户-项目评分矩阵聚类为多个子矩阵，由于每个子矩阵的属性，这个子矩阵中的用户和项目是具有强连接性质的。然后，将传统的协同过滤算法应用到这些小矩阵的评分预测阶段中。该方式不仅可以很好地解决时间效率问题，并且还能保证不错的推荐精度。

因而，本文主要针对不同聚类算法与协同过滤算法的结合，在推荐精度方面进行了实验对比分析。并且通过实验得出结论，聚类算法与协同过滤算法的结合有助于提高推荐系统的实时性，对于在线系统来说是很有优势的。

1相关工作

基于模型的协同过滤算法具有较好的推荐性能，比较典型的有概率矩阵分解模型（PMF）[8]。为了进一步提高效率，研究人员开发了许多其他算法。例如，NHPMF [5]算法比PMF显著提高了推荐的准确性。即便如此，数据量呈指数形式的增长仍然让基于模型的协同过滤算法“不堪重负”。因而，聚类算法应用于协同过滤算法[6，16]成为一种有效解决方式。聚类的有效性主要体现在：通过聚类生成的类别的规模减小，聚类还可以减少评分的稀疏性。

起初，许多学者只考虑了将聚类应用于项目[6，9]或用户[10]以提高时间效率。但是，这些方法只考虑矩阵信息的一个维度而丢失另一维度信息。为了解决這个问题，有学者提出了基于联合聚类的协同过滤算法[7]。与传统的聚类方法相比，联合聚类可以有效地找到用户-项目评分矩阵的隐藏聚类结构，同时对上述两个维度进行聚类。联合聚类算法将原始矩阵聚类成几个小类别，每个小类别内部密切相关。根据这种密切关系，评分预测阶段可以获得较少的计算量和较高的精度。

此前，文献[11]提出了一种基于信息论的联合聚类算法。后来，Agarwal [12]开发了一种利用广义线性模型来平滑误差函数的方法。随后，研究人员提出了如何设置聚类类别数的参考标准[13]。但所有这些方法都是硬聚类[14]，即每个用户、项目和评分只属于一个单一的聚类类别。因此，有学者提出采用模糊聚类[15，17，18]来放宽对类别归属的限制。

虽然基于模型的协同过滤算法可以获得高精度，但时间效率不高。聚类算法可以加速处理大规模数据集的过程，但是会牺牲推荐的准确性。本文主要就不同聚类算法之间的差异，进行实验对比分析。

2方法

假设我们想把用户-项目评分矩阵聚类成K个类别。Agglomerative Clustering是一种自底向上的层次聚类方法，它是根据指定的相似度或者距离来进行类别的划分的。主要按如下步骤进行：

1）将每个用户（项目）当作一个类别；

2）重复：每一轮合并指定距离最小的类别；

3）直到聚类的类别数等于K。

Spectral Clustering是一种使用很广泛的聚类算法，该算法主要思想是将所有数据看作空间中的点，这些点通过边来连接。每条边上面有权重，权重的大小根据距离的远近来决定，距离越近，权重越大，距离越远，权重越小。通过对这一整个图来进行划分，切图后，不同图中的权值低，而同一图中的权值较大。

Affinity Propagation聚类算法简称AP算法，基本思想是将所有数据点看作网络中的节点，通过这些边来传递消息，从而计算出聚类中心。吸引度和归属度是该聚类方法中的两种消息。AP聚类算法根据每个节点的吸引度和归属度的更新来产生高质量的聚类中心，同时将其他的不相似点聚类到别的类别中，从而完成整个聚类算法。

联合聚类（Co-Clustering）将分别对所有的用户、项目和评分进行聚类，并为它们分配概率，即每个聚类一个概率。然后，联合聚类将这些获得的软分配结合起来，以改善下一轮聚类。上述过程将会重复，直到收敛。假设将用户、项目和评分分配给类别[k]的概率为[p（k|ui，vj，rij）]。根据联合聚类思想，我们可以将其表述为：

[p（k|ui，vj，rij）=AB] （1）

[A=p（k|ui）+a×p（k|vj）+b ×p（rij|k）+c] （2）

[B=k′=1Kp（k′|ui）+a×p（k′|vj）+b ×p（rij|k′）+c] （3）

其中，[k′]表示[K]个聚类中的某一个聚类，且[k′∈1，2，...，k，...K]；[a]，[b]，[c]是为了防止分母为零而设置的超参数，可根据具体环境设定，这里我们统一指定为1.0E-7。

当上述这些聚类过程通过迭代方法收敛时，每个类别中的元素都互为邻居，构成邻居集合。同时，由于上述联合聚类是软聚类，即一个用户（项目）可能属于几个类别。我们简单地将用户（项目）分配给具有最大概率的类别。然后，将用户-项目评分矩阵划分为K个类别，以便并行地评分预测在每个类别中进行计算。

通过聚类挖掘用户与项目之间的相互影响关系，在评分预测阶段，以聚类[k]为例。如图1所示，[xk]表示该类别中用户的数量，[yk]表示该类别中项目的数量。该模型确保用户的行为与它的邻居集合相类似，并且项目与其邻居集合相似。提出的用户[ui]与项目[vj]的特征向量方程如下：

[Qki=e∈Cksui，ue×Qki+?Qk ?Qk?N（0，σ2QJ） ] （4）

[Lkj=p∈Ckzvj，vp×Lkj+?Lk ?Lk?N（0，σ2LJ）] （5）

从上面的两个公式可以看出，每个用户（项目）的潜在特征向量由两个项组成。第一项是用户（项目）邻居的加权平均值，[s]代表用户和用户之间的相似度，[z]表示项目与项目之间的相似度。第二项是通过方差[σ2Q]和[σ2L]来控制的用户和项目之间的差异项。据此，计算出类别[Ck]的先验分布如下：

[p（Rk|Qk，Lk，σ2）=i=1xkj=1yk[N（rkij|QkiTLkj，σ2）]ωij] （6）

其中，[ωij]为指标函数，如果用户[ui]评价了项目[vj]，则指标函数[ωij]等于1，否则等于0；建立如下误差平方和目标函数：

[Ek=12i=1xkj=1ykωij（rkij-QkiTLkj）2 +12λQi=1xkQki-e∈Cksui，ue×QkeF +12λLj=1ykLkj-p∈Ckzvj，vp×LkpF ] （7）

在上面的等式中，[λQ=σ2σ2Q]，[λL=σ2σ2L]。顯然该目标函数由三部分组成。首先是实际评分与预测评分之间的关系；接下来的两项是通过参数[λQ]和[λL]来进行平滑处理的邻居信息。[λQ]控制用户邻居信息的影响程度；[λL]控制项目邻居的影响程度。为了达到方程（7）的最小值，对每个用户和项目使用随机梯度下降法，从而得到最优值。

3.1 实验数据集

Movielens是最悠久的推荐系统之一，同时也是一个以研究为目的的非商业性质的实验性站点，主要就是向用户推荐他们可能感兴趣的电影。MovieLens数据集包含的影片种类和数量繁多，用户的数量更是惊人，是各大学者实验过程中的首选。为了最大化利用有效信息进行推荐，实验数据集包含了评分信息，标签信息以及其他一些潜在信息。为此，本文选用了推荐系统中常用的Movielens 10M数据集。本文选取的数据集包含了71567位用户对10681部电影的10000054个评分记录（0.5～5），其中还包含95580个标签。

3.2 评价标准

本文采用均方根误差（RMSE）作为评价标准[19]。文中RMSE通过计算预测评分与实际评分间的偏差来判断预测准确度。RMSE能够很好地反映出测量的精度，因而广泛用于推荐系统中。具体地，RMSE越小，表示评分预测准确度越高。假设算法对[N]部电影预测的评分向量表示为[{p1，...，pN}]，对应实际评分向量为[{r1，...，rN}]，则该算法的RMSE表示为：

[RMSE=i=1N（pi-ri）2N] （8）

3.3实验结果和分析

本小节的运行时间是聚类过后，在预测阶段的一次迭代所消耗的时间。通过运行的时间比较可以得到结论，Spectral Clustering算法的运行时间相对较长，这是因为该算法聚类的结果不佳，导致在评分预测阶段的寻找邻居过程耽误较多时间，因而导致时间消耗相对较多。Affinity Propagation算法不需要指定类别数，自适应得到聚类类别，用户与项目类别数不一致，并不能得到各自不相关的类别，因而并行处理不适用，时间效率较低。实验结果表明，Co-Clustering算法的時间效率最高。

4总结

在本文中，我们主要针对目前出现的信息量呈指数式增长的问题，分析比较了不同聚类算法应用于协同过滤算法的效果，并主要从时间效率和推荐精度两方面进行了实验对比分析。MovieLens数据集的实验结果分析表明，联合聚类算法和一般的聚类算法

比较而言，更能发现评分矩阵中隐藏的结构，进而在评分预测阶段得到更高的推荐精度。

参考文献：

[1] Adomavicius G ，Tuzhilin A. Toward the Next Generation of Recommender Systems： A Survey of the State-of-the-Art and Possible Extensions. IEEE TKDE， pages 734-749， 2005.

[2] Linden G， Smith B and York J. Amazon.com Recommendations： Item-to-Item Collaborative Filtering. IEEE Internet Computing， pages 76-80， 2003.

[3] Sarwar B， Karypis G and Konstan J， et al. Item-based collaborative filtering recommendation algorithms. WWW， pages 285-295， 2001.

[4] Koren Y， Bell R and Volinsky C. Matrix Factorization Techniques for Recommender Systems. Computer， pages 30-37， 2009.

[5] Wu L， Chen E and Liu Q， et al. Leveraging tagging for neighborhood-aware probabilistic matrix factorization. CIKM， pages 1854-1858， 2012.

[6] Najafabadi M K， Mahrin M N and Chuprat S， et al. Improving the accuracy of collaborative filtering recommendations using clustering and association rules mining on implicit data. Computers in Human Behavior， pages 113-128， 2017.

[7] Wu Y， Liu X and Xie M， et al. Improving Collaborative Filtering via Scalable User-Item Co-Clustering. WSDM， pages 73-82， 2016.

[8] Mnih A and Salakhutdinov R R. Probabilistic Matrix Factorization. NIPS， pages 1257-1264， 2007.

[9] Wang Z， Wang X and Qian H. Item Type Based Collaborative Algorithm. CSO， pages 387-390， 2010.

[10] Shi X Y， Ye H W and Gong S J. A Personalized Recommender Integrating Item-Based and User-Based Collaborative Filtering. ISBIM， pages 264-267， 2008.

[11] Dhillon I S， Mallela S and Modha D S. Information-theoretic co-clustering. KDD， pages 89-98， 2003.

[12] Agarwal D and Merugu S. Predictive discrete latent factor models for large scale dyadic data. SIGKDD， pages 26-35， 2007.

[13] Xiao-Guang L I， Ge Y U， Wang D L， et al. Latent Concept Extraction and Text Clustering Based on Information Theory*： Latent Concept Extraction and Text Clustering Based on Information Theory[J]. Journal of Software， 2008， 19（9）：2276-2284.

[14] Geiger B C and Amjad R A. Hard Clusters Maximize Mutual Information， 2016.

[15] Hu L and Chan K C C. Fuzzy Clustering in a Complex Network Based on Content Relevance and Link Structures. TFS， pages 456-470， 2016.

[16] Hu W U， Wang Y J and Wang Z， et al. Two-Phase Collaborative Filtering Algorithm Based on Co-Clustering. JSW， pages 1042-1054， 2010.

[27] Mei J P， Wang Y and Chen L， et al. Large scale document categorization with fuzzy clustering. TFS， pages 1， 2016.

[18] Bu J， Shen X and Xu B， et al. Improving Collaborative Recommendation via User-Item Subgroups. TKDE， pages 2363-2375， 2016.

[19] Chai T and Draxler R R. Root mean square error （RMSE） or mean absolute error （MAE）？ - Arguments against avoiding RMSE in the literature. GMD， pages 1525-1534， 2014.