- 1 -
中国科技论文在线
基于物品属性聚类的融合协同过滤算法
梁佳男，张华**
作者简介：梁佳男（1989-），男，硕士研究生，推荐系统，信息安全
通信联系人：张华（1983-），女，副教授，密码协议、物联网和云计算安全、工业控制系统安全、移动互
联网安全
（北京邮电大学网络与交换国家重点实验室，北京 100876）
5 摘要：随着信息技术的发展，各式各样的推荐系统早已广泛地应用在电子商务、新闻推荐等
领域。协同过滤可以算是推荐系统众多推荐算法中，使用频率最高的一种。但其往往存在数
据稀疏性问题和冷启动等缺点。为了减少推荐系统计算的时间，提高推荐准确率，本文提出
一种基于物品标签聚类和 slope-one 协同过滤的融合推荐算法。在算法中，通过利用用户对
物品的评分行为和物品的属性标签，计算出用户对物品属性的偏好向量。然后利用该向量对10
用户进行聚类，将用户分成多个相似偏好用户组。最后，再使用 slope-one 算法对未评分的
物品进行打分。属性标签的使用，减少了用户特征向量的维度，部分解决了矩阵稀疏的问题，
而通过聚类和 slope-one 算法的融合，在保留了 slope-one 算法计算模型简单优点的同时，
也提高了打分的准确性。最后，通过 MovieLens 上的数据集验证，相比于 slope-one 算法，
该融合算法确实能够提高推荐系统的准确性。 15
关键词：推荐系统；协同过滤；聚类；标签
中图分类号：TP311
Hybrid collaborative filtering algorithm based on Item Tag
clustering 20
LIANG Jianan, ZHANG Hua
(State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and
Telecommunications,Beijing 100876)
Abstract: With the development of information technology, a lot of recommendation systems
have been widely used in e-commerce, news recommendation etc. Collaborative filtering is one of 25
the most important recommendation algorithms among recommendation system. However it's also
suffering some problems such as data sparsity and cold start. In order to reduce computing time
for recommendation and improve the accuracy, a new collaborative filtering recommendation
system combining item-tag clustering and slope-one algorithm is proposed. In this algorithm,
users were clustered according to users' preference on tags of items. Property tags were userd to 30
reduce users' feature vector, which solved data sparsity partially. By combining both clustering
and slope-one algorithm, the recommendation system retained the advantage of slope-one
algorithm while improving accuracy as well. The experiment were applied to MovieLens dataset,
which showed that the accuracy of this combined algorithm is in advance of naïve slope-one.
Key words: Recommendation system; Collaborative filtering; Clustering; Tag 35
0 引言
随着互联网的不断发展，其承载的信息数量也越来越大。过量信息的出现，导致用户无
法能够简单快速的从中获取对自己有效的信息。而且，随着电子商务的发展，在某些场合下，
用户需求往往具有不确定性和模糊性。根据亚马逊网站的统计, 在其网站购物的客户中, 有40
明确购买意向的仅占 16%。如果商家能够从海量的商品中把满足用户模糊需求的商品主动推
荐给用户, 则有望将用户潜在需求转化为实际需求, 不仅能够提高网站的销售量, 还有助于
提高用户对网站的忠诚度和黏性。在此背景下，推荐系统也就应运而生，并在短时间内得到
大量的运用。
- 2 -
中国科技论文在线
到目前为止，对推荐系统的分类还没有一个统一的标准，许多学者从各个角度都推荐系45
统进行了不同的划分。但主流推荐算法一般包括以下几种：1）基于内容的推荐；2）协同过
滤推荐；3）基于知识的推荐；4）融合推荐[1]。其中，协同过滤是最为成熟的一种推荐算法
[2]。主要包括基于用户的协同过滤和基于物品的协同过滤两种推荐方式。然而，随着推荐系
统处理的数据量不断增长，针对协同过滤推荐的问题也不断出现，其中数据稀疏性则是协同
过滤面临的一个最主要的问题。因为在实际的应用中，用户对项目的评分矩阵往往比较稀疏。50
据统计表明，在大型的电子商务网站中，只有不超过 1%的物品是被评过分的[3]。从而导致在
使用其它用户评分数据来对该物品打分时，计算出来的评分精度并不高。随后提出了一系列
的方法来减小数据稀疏性对推荐精度的影响。比如通过填充法来减小矩阵的稀疏性，通过奇
异值分解来减少不太重要的用户和物品，从而降低矩阵的维度。
在本文中，我们提出一种结合物品标签聚类[4]和 slope-one 算法[5]的融合推荐算法。首先55
利用用户对物品的评分行为和物品的属性标签，计算出用户对物品属性的偏好向量。然后利
用该向量对用户进行聚类，将用户分成多个相似偏好用户组。最后再使用 slope-one 算法对
未评分的物品进行打分。最后通过使用 MovieLens 上的数据集验证，表明相比于朴素的
slope-one 算法，该融合算法确实能够提高推荐系统的准确性。
1 聚类分析 60
聚类概述
简单来说，聚类就是分组，它可以把一组物品通过某种方式，分配到各个组里（该组也
可称之为一个簇），使得同一簇里面的各个元素间的相似度最高。即不存在另一簇中的某个
元素 iX 使得，该元素与目标元素 jX 之间的相似度小于目标元素簇里其它元素 jX 和该目标
元素的相似度。在数据挖掘中，聚类方法经常会被用来进行数据的统计分类。同时，在机器65
学习，模式识别，图像分析和信息提取等领域，聚类算法出现的频率也非常的高。
聚类种类
目前，有好多种的聚类算法已经应用在各个领域，我们可以根据不同业务的数据类型，
和具体应用的需求，来选择适合我们的聚类算法。一般而言，聚类算法经常被划分以下三种：
划分法(partitioning methods)：给定一个有 N 个元素的数据集，通过划分构造出 K 组簇70
（K<N）。当此 K 组簇满足每组簇都至少包含一项数据，且每个数据都属于且仅属于一组
簇时，算法结束；
层次法(hierarchical methods):对给定的数据集一直进行层次划分，直到某种条件满足才
会终止。具体又可分为“自底向上”和“自顶向下”两种方案；
基于密度的方法(density-based methods):其与其它方法不同，它不是基于各种距离，而75
是基于密度的，从而克服基于距离算法只能发现“类圆形”的缺点。它的大致思想就是，如
果某一区域中点的密度大于某个阈值，就把它划分到与之相近的簇中。
虽然存在着各种各样的聚类分析算法，但聚类分析从某种程度上来看，只是解决一些问
题的敲门砖，怎样合理地应用聚类分析后的结果，往往才是决定算法性能的关键。
k-means 聚类算法 80
自从 Mac Queen 在 1967 年提出了 k-means 聚类算法，现在 k-means 已成为使用频率最
- 3 -
中国科技论文在线
高的聚类算法。k-means 算法的核心在于找出 K 个簇的中心 1C , 2C ,…, kC 使得该簇中每个点
jx 到该簇中心 iC 的距离小于到它到其它簇中心的距离。该方法首先随意分配 K 个点
（ 1C , 2C ,…, kC ）作为 K 个簇的中心，然后对集合中每个点 ix ，找到离它最近的簇的中心
iC ，并将其分配至第 i 组。这样，当所有点都分配到相应的簇之后，对每个簇中的所有节85
点重新计算出各自的中心，如此迭代计算下去，直到最后所有簇的中心都收敛到某个阈值δ
为止。通常我们都使用欧式距离作为任意两点间距离的度量。
k-means 是一种最优化解决问题的方式，中间结果可能存在一些局部的最小值，但全局
只存在唯一的最小值。聚类过程会沿着距离减小的方向不断前进，直到最后达到收敛条件停
止。但由于 k-means 采用迭代方式来寻找最优解，迭代过程只能保证差值间局部的最优，90
因此，非常容易陷入局部最优的圈套。
2 基于物品标签聚类的融合协同过滤推荐
图 1 为算法的大体流程。在设计的改进算法中，首先，用户根据各自的打分形成用户的
评分矩阵，然后结合物品各自的属性标签，转化成用户对属性的偏好向量。接下来，使用聚
类算法，将用户根据各自的偏好向量，聚合成不同的相似用户集。接着，相同相似用户集中95
的用户依据各自的评分，利用 slope-one 算法，对所有未评分的物品进行打分。通过这种方
式，为所有未评分的物品形成高质量且准确度更高的评分预测。通过使用此改进算法，不仅
解决了评分矩阵稀疏的问题，也一定程度上提高了预测评分的准确率。从某种程度上来看，
该算法可以看作为基于用户和基于物品两种协同过滤算法的综合。对比与其它类似的算法，
它在提高了评分预测准确性的同时，反而使用了更少的评分项来产生出此预测结果，提高了100
算法的计算效率。
图 1 推荐算法流程
Recommendation algorithm processes
聚类 105
在朴素的 slope-one 算法中，预测评分是根据所有用户的评分计算出来的。在所有计算
的评分中，可能一些用户跟当前用户之间相似度不大。但如果你使用了这些相似度不高用户
的评分来给未评分物品打分的话，所预测的评分也就不那么准确了。为了解决这个问题，我
们可以采用 k-means 聚类的方式。
首先，根据用户对物品的历史评分行为，为每个用户构造出用户-物品打分向量。然后，110
结合物品的属性标签，可以得到用户-属性标签的偏好值向量。接着，依据生成的偏好值向
量，采用 k-means 聚类算法可以将用户分成 K 个相似用户集。当然，除了 k-means 聚类算法
以外，还有许多种聚类算法，像是 BIRCH，DBSCAN 等。这里，我们为了简化算法的复杂
度，从而采用了最简单的 k-means 方式进行聚类。
- 4 -
中国科技论文在线
预测评分 115
Slope-one 算法是一种典型的基于物品的协同过滤算法。它的原理非常简单，即通过线
性回归来预测评分。算法使用 (x) x bf 作为其线性回归表达式。参数 b 代表用户在两件
物品上评分的差值。在绝大多数情况下，表达式 (x) x bf 会比线性回归式 (x) x bf a
更快速，更准确，且占用更少的存储。
Slope-one 算法首先会计算目标物品 j 和物品 i 之间的平均差值 ,j idev ，然后计算出用户120
u 对物品 j 的预测评分 (u, j)P 。
计算差值。假定有所有用户的评分向量集 SU，那么平均差值 ,j idev （物品 j 和物品 i 之
间的平均差值）计算公式如下：
, (SU)
, ,
,
,j i
u j u i
j i
u S j i
r r
dev
c
其中，
,
(SU)
j i
S 代表同时包含对物品 i 和物品 j 评分的用户集 SU，
, ,
(S (SU))
j i j i
c card= 表125
示用户集的数量。
预测目标用户的评分。根据之前计算的差值，计算用户 ut 对物品 k 预测评分值 。
物品 k 的预测评分值 可以用以下公式计算：
, , ,
(SU) {j}
,
(SU) {j}
( ) c
(u, j)
j i u i j i
i S
j i
i S
dev r
P
c
?
?
+
=
å
å
其中， (u, j)P 是目标用户 u 对物品 j 的预测评分，
,j i
dev 是上个式子中计算出来的差值，
,j i
c 130
,j i
c 是
,
(SU)
j i
S 中的元素。
产生推荐结果
针对每一个目标用户，计算完所有未评分的物品以后，对所有的评分进行排序，将排名
最高的几件物品推荐给目标用户即可。
3 实验结果及分析 135
数据集
本论文采用明尼苏达大学 GroupLens 研究组公开的 MovieLens 数据集中 100K 大小规模
的数据进行测试，该数据集包括 943 个用户对 1682 部电影产生的 100000 个评分，其中每个
用户至少对 20 部电影进行过评分。
利用的 MovieLens 数据集，按 8:2 的比例划分训练集和测试集，比较新的融合协同过滤140
推荐算法和普通协同过滤推荐算法之间准确度的差异。
测评指标
在测评中，采用均值误差 MAE[6]作为推荐系统质量的度量指标。MAE 是推荐系统中最
直观最常用的测评指标。通过计算 MAE，我们可以避免计算单一用户差值带来的抖动。MAE
计算如下式： 145
- 5 -
中国科技论文在线
1
| p q |
n
i i
iMAE
n
=
-
=
å
实验结果
测试结果分别取聚类 K=5，10，15，20 时，计算其 MAE，并与朴素 slope-one 算法进
行比较。图 2 为算法比较结果。
150
图 2 推荐准确率对比
Recommended accuracy rate comparison
图 2 中，横坐标表示每次实验中，融合算法采用不同的 K，纵坐标表示计算出来的均值
误差 MAE。 155
从上图中可以看出，选择不同的簇大小，可以影响最终计算出来 MAE 的结果。当簇参
数选择比较小的时候，同一簇里拥有过多的数据，从而也引入了许多噪声。而当簇参数选择
比较大的时候，同一簇内的数据就会过少，导致预测的准确度会降低。当我们数据集中，当
K=5 时，可以获得最小的均值误差 MAE，亦即最高的推荐准确率。
4 结论 160
本文介绍了一种结合物品标签聚类和 slope-one 算法的融合推荐算法。相比于朴素的协
同过滤推荐算法，它不仅很好的解决了数据稀疏性的问题，同时通过对 K-means 算法选择
合适的 K 参数，可以有效减少用户对其相关性较小用户群评分的影响，提高预测评分的准
确性，从而提高推荐系统的推荐准确率。但在该推荐算法中，并没有考虑到像是时间戳等一
类的全文信息，相信在未来通过加入诸如时间戳[7]和地理位置[8]等类型的全文信息后，算法165
的推荐准确率还会有不错的提升。
[参考文献] (References)
[1] Chen J, Miller C, Dagher G G. Product recommendation system for small online retailers using association
rules mining[C]. Innovative Design and Manufacturing (ICIDM), Proceedings of the 2014 International
Conference on. IEEE, 2014: 71-77. 170
[2] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the
state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6):
- 6 -
中国科技论文在线
734-749.
[3] Resnick P, Iacovou N, Suchak M, et al. GroupLens: an open architecture for collaborative filtering of
netnews[C]. Proceedings of the 1994 ACM conference on Computer supported cooperative work. ACM, 1994: 175
175-186.
[4] Kumar G, Mehra H, Seth A R, et al. An hybrid clustering algorithm for optimal clusters in Wireless sensor
networks[C]. Electrical, Electronics and Computer Science (SCEECS), 2014 IEEE Students' Conference on. IEEE,
2014: 1-6.
[5] Zhang Z, Tang X, Chen D. Applying User-Favorite-Item-Based Similarity into Slope One Scheme for 180
Collaborative Filtering[C]. Computing and Communication Technologies (WCCCT), 2014 World Congress on.
IEEE, 2014: 5-7.
[6] Herlocker J L, Konstan J A, Terveen L G, et al. Evaluating collaborative filtering recommender systems[J].
ACM Transactions on Information Systems (TOIS), 2004, 22(1): 5-53.
[7] Jiang W, Wu J, Wang G, et al. FluidRating: A Time-Evolving Rating Scheme in Trust-based Recommendation 185
Systems Using Fluid Dynamics[C]. Proc. of the 33rd IEEE International Conference on Computer
Communications (INFOCOM). 2014.
[8] Yawutthi S, Natwichai J. An Efficient Indexing for Top-k Query Answering in Location-Based
Recommendation System[C]. Information Science and Applications (ICISA), 2014 International Conference on.
IEEE, 2014: 1-4. 190
