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