文章编号= 1009 -2552 (2018)06 -0115 -06
DOI：10. 13274/j. cnki. hdzj. 2018. 06. 025
y
信息疼甲
基于数据双重优化聚类的协同过滤推荐算法
王艺霏，彭柏
(国网冀北电力有限公司信息通信分公司，北京100053)
摘要：在传统的协同过滤推荐算法使用中，不可避免地遇到数据稀疏性、冷启动和可扩展性 问题。然而个性化推荐系统需要真实大量的流式数据支持，因此需要一类能够有效提高符合现 实用户需求的推荐方法。该类推荐方法必须密切联系用户日常操作行为，采集用户偏好程度等 等。在流式大数据环境下，推荐算法中的用户特征和用户偏好尤为重要。文中提出了一种基于 用户活跃度（CF-act)双重聚类的协同过滤推荐算法，以用户特征和用户偏好为种子数据，对种 子数据采用优化的K-means算法分别聚类生成用户-项目评分表，在聚类中搜索目标用户的最近 邻居为目标用户产生推荐，缩小搜索范围，降低推荐的时间复杂度。最后，文中比较了提出的 推荐算法与传统协同过滤算法的误差率，且验证了推荐系统的运行效率。关键词：协同过滤；双重聚类；优化的K-means算法；扩展性 中图分类号：TP393
Collaborative filtering recommendation algorithm based on double
optimization clustering with data
WANG Yi-fei，PENG Bo
(State Grid Jibei Information & Telecommunication Company，Beijing 100053，China)
文献标识码：A
Abstract ： In the use of traditional collaborative filtering recommendation algorithm，data sparsity，cold start and scalability are unavoidable. However，personalized recommendation system requires a lot of real data support，so a kind of recommendation method can be effectively improved to meet the needs of real users. This kind of recommendation must be closely related to the user’s daily operation behavior，to collect user preference and so on. In the large data environment， the user characteristics and user preferences of the proposed algorithm are particularly important. This paper puts forward a kind of based on user activity ( CF-act ) double clustering collaborative filtering recommendation algorithm， characteristics and user preferences to the user data for seed， the seed data， respectively， the optimization of K-means algorithm clustering generate user-project assessment，in clustering search target user nearest neighbors of target user recommendation，narrow your search，reduce the time complexity of recommendation. Finally， it compares the error rate of proposed algorithm and traditional collaborative filtering algorithm， and verifies the operating efficiency of recommendation system.
Key words： collaborative filtering； double clustering； optimized K-means algorithm； scalability
0引百
信息化技术的飞速发展使互联网进人了大数据
性化推荐系统中应用最广泛的推荐技术就是协同过 滤推荐算法[3]。协同过滤推荐系统根据推荐算法
收稿日期：2017 -10-16
作者简介：王艺霏（1988 -)，女，硕士，高级工程师，研究方向为大
数据处理、数据挖掘、人工智能方向等。
时代[|]。人们能方便地从网络中获取信息,但是大 量的信息导致了信息超载问题，个性化推荐系统[2] 被认为是解决这种问题的最有效的工具之一，在个
—115 —
的不同可以分为两大类:基于内存的协同过滤推荐 算法[4]和基于模型的协同过滤推荐算法[5]，其中基 于内存的协同过滤推荐算法又分为基于用户的协同 过滤推荐算法[6]和基于项目的协同过滤推荐算 法[7]。然而，随着用户数和项目数呈现指数式增长 协同过滤推荐技术遇到了瓶颈，例如评分矩阵越来 越稀疏，可扩展性差，冷启动等问题[8]。在这种情 况下，当计算相似度时误差非常大，寻找的最近邻居 偏差也会比较大，从而推荐质量会变得非常低。
本文提出了基于数据双重优化聚类的协同过滤 推荐算法:对整个用户集，根据用户的特征值进行聚 类，考虑到只根据用户特征进行聚类具有片面性，所 ①Pearson相关相似
计算用户^和用户^之间的Pearson相关系数 定义为：
sim ( u，v) PCCZij。-O2 -O2
(1)
其中，/u〃是指用户u评价过且用户〃也评价过的项 目集合，Q和〜分别指用户u和用户^对项目i的 评分，< 表示用户u的平均评分。
②余弦相似性
余弦相似性是指将用户-项目评分矩阵中的每 以提出了根据用户对项目的评分即用户偏好再进行 聚类，然后对目标用户所在的两个聚类簇取交集，产 生由用户特征和用户偏好优化聚类后的聚类簇，在 对用户进行聚类的过程中采用优化的K-Means算法 聚类，最后在聚类中搜索目标用户的最近邻居为目 标用户产生推荐。
1传统协同过滤推荐算法
个性化推荐系统中最常使用的是协同过滤推荐
算法，它的基本思想是[9]:根据用户-项目评分矩 阵计算用户（或项目）之间的相似度，然后根据相似 度值，寻找最近邻集合，最后为目标用户产生推荐。 基于内存的协同过滤推荐算法的步骤是[1°]:数据收 集与整理，寻找最近邻居，产生推荐。1.1数据收集与整理
首先收集数据，然后对数据进行处理与整理形
成rn x 〃阶的评分矩阵及，m表示参与评分的m个 用户，〃表示评分矩阵中的〃个项目。用户对项目 的喜爱程度用其对项目的评分来表示通常设置为 1分~5分的评分制，评分越高表示喜欢的程度越 高。评分矩阵如图1所示，其中，表示用户^对
项目i的评分。
I'
h…h
Ru...
^2,2
UmRm，l... Rm，n
图
1
用户项目评分矩阵
1.2寻找最近邻
通过计算用户之间的相似性来寻找目标用户的 最近邻居，计算用户之间的相似性是协同过滤推荐 算法的核心，其中应用最广泛最成熟的相似性算法 是:相关相似性[11]、余弦相似性[12]和修正的余弦相 似性[13]。一 116 —
一行作为一个行向量，用两个行向量之间的夹角余 弦来衡量两个用户之间的相似度。二者的夹角越小 相似度越高反之相似度越低。则用户u和用户^之 间的余弦相似度定义为：
sim (u，v) c
I
ruirvi(2)
IluvIluv③修正的余弦相似性
余弦相似性度量方法中没有考虑到不同用户之间的评分风格问题，有的用户习惯性评高分而有的 用户喜欢评低分，为了避免上述现象带来的缺陷，提 出了调整的余弦相似性，去掉了用户的平均评分，则 调整的余弦相似性定义为：
sim ( u，v)
CeosI iG/u ( rui - ru ) ( rvi - rv ) ZiE/u (厂ui -r:)2 (厂Vi -〇2
(3)
1.3产生推荐
获得目标用户的最近邻集合后，就可以预测目 标用户对未评分项目的评分值，然后根据预测的评 分值将评分值最高的前#个项目推荐给目标用户， 其预测评分值的公式定义为：
1 V.,(u) Sim( u，V) *( rvi-r *)
(4)
其中，sim(u，v)表示用户u和用户V之间的相似度， ,(u)表示用户u的最近邻居集合，由用户u的邻居用 户对项目i的评价来预测u对i的评分P( u，i)。
2
基于用户活跃度（CF-act)聚类的协
同过滤推荐算法
2. 1
协同过滤推荐模型基本结构
本文提出的基于用户活跃度（CF-act)聚类的协
同过滤推荐算法，分为离线和在线两部分。离线时， 首先根据用户的活跃度将活跃度高的用户作为初始 聚类中心，采用欧式距离相似性[14]将其余的用户进 行聚类，然后提取聚类用户的用户-评分信息，最后 存储聚类信息。在线时，系统仅查找目标用户所属 的聚类，在所属的聚类中查找最近邻居，为目标用户 产生推荐。由于在线为目标用户产生推荐时只需在 目标用户所在的聚类中产生推荐，这样大大减少了 最近邻居的搜索范围，降低了推荐的响应时间。基 本结构如图2所示。
2所示。
表2 信息表NCUser
用户 ID
12
345
年龄1
4
性别01001
职业1
3
112
11
3
处理数据的算法描述：
在线部分户目登标用陆数据库中提 SIIII取聚类令信息
1产生椎若1
111111
离线部分
原数始据_^基选于取用聚户类活中跃心度 _对
行用聚户类进产生
----^推荐'
聚到类数信据息^服----务器_存中
储 图2推荐模型基本结构
2.2用户特征数据集的收集与处理
用户的特征信息可以根据用户在网站上的注
册信息来获取，本文是从MovieLens数据集中提取 的相关属性（年龄、性别、职业）信息，部分数据如 表1所示，每一列分别表示用户ID，年龄，性别， 职业。
表
1
用户特征信息表CUser
用户ID
年龄
性别
职业
124Mtechnician2
53Fother323Mwriter424Mtechnician5
33
F
other
本文将年龄分为7个阶段分别是18岁以下， 18岁〜24岁，25岁〜34岁，35岁〜44岁，45岁〜 49岁，50岁~ 55岁，56岁以上，将7个年龄段分别用数字〇~6来表示。性别是二元属性（M，F)用0 表示M，1表示F。MovieLens数据集中的职业信息 一共是21种，本文根据《中华人民共和国职业分类 大典》分为的八大类职业[15]，将21种职业归属为四 大类，分别用数字0~3来表示。处理后的数据如表
输人:用户特征信息表CUser
输出:用数字代表的用户特征信息表NCUser
① 从⑶ser表中查询n个用户，记为\"={^，…Un I
② For all ' e U
F〇r( j = 〇;j < 3;j ++ )
分别判断每个^[i]的特征信息
If
'[/•] E {0 -17||18 -24||25 -34||45 -49||50 - 55||56 -1
then int flagfirst: = {0||1||2||3||4||5||6| else if ut [ j + 1] e {M|F | then int flagfirst： = {0|| 1| else if '[) + 2] e {某一职业类| then int flagfirst: = {0||1||2|| 3| end if end if
end
2.3基于用户属性特征和用户偏好的聚类
在本文中，将根据用户的个人特征（年龄、性 别、职业)对用户进行聚类，本文采用的聚类方法是
K-Means算法[16]对用户进行聚类，但是原始的K- Means聚类算法是随机选取初始聚类中心，这样随
机选取的聚类中心往往不具有代表性使得推荐的质 量不仅没有提高反而会降低，所以本文对K-Means 聚类算法进行了优化:选取基于用户特征属性活跃
度（C-act)和用户偏好活跃度（F-act)高的用户作为 初始聚类中心。选取活跃度高的用户作为初始聚类 中心更具有代表性，聚类的结果会更好。
①基于属性活跃度初始聚类中心的选取
本文根据年龄段的划分将用户分为7大簇，所 以将取7个用户作为初始聚类中心。首先根据用户 在特征信息数据集中的活跃度来选取聚类中心。定义1:用户特征属性活跃度（C-act)。用户特 征属性活跃度是指用户在用户属性特征数据集中的
一 117 —
，
活跃度。因为根据年龄段划分的七个类簇，所以年 龄属性的选择是固定的为{〇，1，2,3,4,5,6厂然后 根据年龄段选择性别，例如在年龄段为0时，选取性 别活跃度高的男性或女性，最后根据年龄和活跃度 高的性别属性选取活跃度高的职业属性，依次类推 选取年龄段分别为1，2,3,4,5,6的活跃度高的性别 和职业属性，最后选取的结果如表3所示。
表3
基于用户属性特征活跃度的初始聚类中心
似度，将相似度高的对象分配到初始聚类中心所在 的类中。最后在每个聚类中计算所有对象的均值， 产生一个新的聚类中心，重复计算直到聚类中心不
再发生变化。因为K-Means聚类算法的尺值是预先 给定的，所以如果是随机选取的K个值对于本文的 聚类结果往往不具有代表性，产生的聚类结果不明 显，所以本文提出了优化的初始聚类中心，最终选取 的[个初始聚类中心。聚类算法具体步骤如下： 输人:用户表NCUser、用户特征属性表、聚类数目尺
年龄01性别00职业
33
输出：尺个用户特征属性聚类簇
① 从NCUser表中查询^个用户，记为\"={a，2
013014015
01
6
0
3
② 基于用户偏好活跃度初始聚类中心的选取
定义2:用户偏好活跃度（F-act)。用户偏好活跃度是指根据用户-评分数据集，选取用户评分多 的用户（即用户偏好活跃度）作为初始聚类中心。 根据表2选取的基于属性特征活跃度的初始聚类中 心，选取属于每行聚类中心的用户ID，例如将属于 (0 0 3)的用户ID的集合定为％ = {用户ID}，依 次类推分别获取（1 0 3)，（2 0 1)，（3 0 1)，（4 0 1)，（5 0 1)，（6 0 1)的用户ID集合，最后选择每 个集合里面评分最多的用户作为每个年龄段的聚类 中心，最后选取的聚类中心如图3所示。
original centers:
[880.0
.0^ 0.0, 3.0][393.0, 1.0, 0.0, 3.0][537.0^ l.Bj 0.0^ 1.0][650.0^ 3.0^ 0.0J 1.0][406.0^ 4.0^ Q.Bj 1.0][524.0J 5.0^ 0.0, 1.0][481.0^
6.0, 0.0^ 3.0]
图3
初始聚类中心
③ 基于用户的聚类
本文采用的聚类算法是K-Means聚类算法对用 户进行聚类，K-Means算法是一种通过均值对数据 点进行聚类的算法。K-Means算法通过预先设定的 尺值及每个类别的初始质心对相似的数据点进行划 分。并通过划分后的均值迭代优化获得最优的聚类 结果。其基本思想是:在数据对象为〃的数据集中 随机选取尺个初始聚类中心，然后计算剩余的对象 与初始聚类中心的相似度，这里计算相似度时是将 用户属性信息看作空间向量，采用欧式距离计算相 一 118 —
从2，\".，〜}
② 初始化尺个空聚类，记为4 = U1，…，^}③ 根据选取基于属性特征活跃度（C-act)和偏好活
跃度（F-act)高的用户特征向量作为尺个初始聚类 中心，记作B = A，…人}④ Repeat
For所有的' e \"For所有的e B
计算 '和聚类中心^的相似性hrn( ^次），将相 似度值最大的用户分配到聚类中心所在的聚类中。
For所有的％ e A
For所有的e U
计算用户^对聚类％中所有用户的平均特征 信息值赋值给^
Until聚类中心不再发生变化
⑤ 返回
得到K个聚类簇后，由于只根据用户属性特征 进行聚类，得到的聚类簇具有片面性，并且属性特征 值只采取年龄、性别、职业三个属性，得出的结果具 有不准确性。所以本文提出了对用户进行优化聚 类，再根据用户-项目评分数据采用同样的聚类算 法对用户偏好进行聚类。在对用户偏好进行聚类时 同样采用图3所示的初始聚类中心，不同的是用户 偏好聚类采用的是用户-项目评分表，最后根据目 标用户所在的用户属性特征聚类簇和用户偏好聚类 簇取交集形成最终的聚类簇。
得到最终的聚类簇后，提取目标用户聚类簇中 所有用户对项目的评分，整理成聚类后的用户-项 目评分表，在为目标用户产生推荐时，只在目标用户 所在的聚类中搜索目标用户的最近邻居产生推荐， 这样大大缩小了搜索范围，降低了推荐的时间复 杂度。
3实验结果与分析
本文实验采用的数据集是由美国Minnesota大
学提供的MovieLens数据集，MovieLens数据集是历 史最悠久的推荐系统，是一个非商业性质的、以研究 为目的的实验性站点。MovieLens网站提供了 4种 不同的数量级，分别 MovieLens 100k、MovieLens 1M、
MovieLens 10M 和 MovieLens 20M，本文实验选用的
30、35、40、45、50。实验结果如图4-5所示。
是943个用户对1682部电影的MovieLens 100k数 据集，评分是1
评分制，评分越高表示用户对该
电影的喜爱程度越高，通过这10万条评分记录对比 传统的协同过滤推荐和改进的协同过滤推荐的推荐 质量。该数据集的稀疏度为：
100000
943 x 1682
= 93.7%
⑶
采用5 -折交叉验证的方式将实验数据按4:1 的比例分为训练集和测试集，其中80%的数据集为 训练集，20%作为测试集。
衡量协同过滤推荐质量的指标有:准确率、召回 率、覆盖率、新颖性、惊喜度、平均绝对误差（Mean
Absolute Error，MAE )、均方根误差（Root Mean Squared Error，RMSE )等，MAE是目前在推荐系统评
估推荐质量使用最广泛的评价指标。本文实验所用
的评价指标是平均绝对误差（MAE)，均方根误差 (RMSE)和准确率/召回率，平均绝对误差（MAE)公 式如下：
丽
=1笔I凡ll
(6)
均方根误差误差（RMSE)公式如下：
i (凡1)2
RMSE = 1 = 1
N
(7)
其中，凡表示预测的用户评分集合{^，…， 〜丨，仏表示实际用户评分集合{心，…，3n1。
平均绝对误差值或均方根误差值越小，表示该 推荐算法的质量越高。对用户进行聚类时，聚类数 目的选定是非常关键的，聚类数目过多或者过少都 会影响聚类的结果，这样不仅没有提高反而会降低 推荐质量。本文根据年龄段的划分将数据集分为了 7个类簇，在选取初始聚类中心时是基于用户特征 活跃度和用户偏好活跃度获取的聚类中心，这样选 取的聚类中心更具有代表性，综合考虑了用户属性 特征和用户-项目评分信息对用户进行了优化聚类。本实验中相似度计算采用的是Pearson相关相 似性[17]公式，对于基于用户的推荐算法模型来说，
Pearson相关系数比其他度量用户相似度的方法更
胜一筹，它可以避免评分等级膨胀（grade inflation) 的问题。邻居数目分别选取的是5、10、15、20、25、
图4平均绝对误差比较
由图4显示出取不同邻居数目时，传统的协同 过滤推荐模型与本文提出的模型对MAE的影响情 况。分析得出，本文提出的基于用户优化的优化聚
类推荐模型（DK-CF)计算的平均绝对误差（MAE) 比传统的协同过滤算法（T-CF)和没有进行优化的 聚类的推荐模型（K-CF)的平均绝对误差都要低（例 如当邻居数量为15时，本文提出的模型比传统的协 同过滤推荐模型要低9%左右）。
图5
均方根误差比较
由图5显示出取不同的邻居数目时，传统的协 同过滤推荐模型与本文提出的模型对RMSE的影响 情况。分析得出，本文提出的基于用户特征优化的 优化聚类推荐模型（DK-CF)计算的均方根误差 (RMSE)比传统的协同过滤算法(T-CF)和没有进行 优化的聚类的推荐模型（K-CF)的均方根误差都要 低（例如当邻居数量为20时，本文提出的模型比传 统的协同过滤推荐模型要低7%左右）
本文在对提出的推荐模型与传统模型进行
MAE和RMSE比较的同时，也在准确率和召回率上 进行了比较，实验结果如图6 - 7所示。
由图6和图7可知随着推荐列表的不同变化，
DK-CF模型比T-CF模型的准确率和召回率都有所
提高。
一 119 一
择最近邻，所以这就导致了推荐的不准确性。当新
4
0.110
60.0020
用户到来时，由于还没有对物品的评分，这样就出现 了冷启动问题。所以后续的工作可以根据用户已评 过分的项目来填充数据的稀疏性或将相似度计算进 一步优化缓解数据稀疏性提高推荐质量，可以考虑 将用户的时间属性融人到相似性算法中来解决新用 户的冷启动问题，提高推荐质量。参考文献：
[1] 张浩然，李中良，邹腾飞，等.农业大数据综述[J].计算机科
学，2014,41(S2) :387 -392.
图6
准确率比较
[2] 李霞，李守伟.面向个性化推荐系统的二分网络协同过滤算法
•0.
图7
召回率比较
4结束语
本文主要是融合用户的属性特征信息和用户偏
好信息，提出了将用户进行优化聚类的推荐模型，聚
类采用的是优化的K-means算法，与传统的随机选 取初始聚类中心的K-means聚类算法相比，基于用 户活跃度选取的初始聚类中心聚类的结果更合理。 优化聚类具有融合了用户对项目的评分和用户本身 的属性特征信息的优点，两种信息的聚类结合使得 聚类结果更加准确。本文提出的基于优化聚类的协 同过滤推荐算法在提高了推荐质量的同时，降低了 为目标用户实时推荐的响应时间，缓解了推荐系统 的可扩展性问题。然而，随着大数据时代的到来，用 户数和项目数呈指数式增长，而用户对项目的评分 往往比较少，这就是协同过滤推荐算法的稀疏性问 题，当为目标用户进行推荐时，是根据用户的评分选
一 120 —
研究[J].计算机应用研究，2013，30 (7) : 1946 - 1949.
[3] 孙光福，吴乐，刘淇，等.基于时序行为的协同过滤推荐算法[J].软件学报，2013,24(11):2721 -2733.
[4] 赵琴琴，鲁凯，王斌.SPCF:—种基于内存的传播式协同过滤推荐算法[J].计算机学报，2013，36(3) :671 -676.
[5] 王兴茂，张兴明，邬江兴.基于一跳信任模型的协同过滤推荐算法口].通信学报，2015,36(6):197 -204.
[6] 荣辉桂，火生旭，胡春华，等.基于用户相似度的协同过滤推荐算法[J].通信学报，2014,35(2):16 -24.
[7] 叶锡君，龚玥.基于项目类别的协同过滤推荐算法多样性研究口].计算机工程，2015,41(10):42 -46 +52.
[8] 张付志，刘赛，李忠华，等.融合用户评论和环境信息的协同过滤推荐算法[J].小型微型计算机系统，2014,35(2) :228 -232.[9] 汪静.协同过滤推荐算法研究综述[J].中国新通信，2014,
16(13) :111 -113.
[10] 张学钱，林世平，郭昆.协同过滤推荐算法对比分析与优化应用[J].计算机系统应用，2015,24(5) :100 -105.
[11] 张星煜，张建，辛明军.相似性一局部性方法相关参数分析[J].计算机技术与发展，2014，24(11) :47 - 50.
[12] 刘英伟，秦永彬.基于余弦相似性的m-类分类器设计与算法实现[J].计算机与数字工程，2014,42(3):351 -354.
[13] 任看看，钱雪忠.协同过滤算法中的用户相似性度量方法研究[】].计算机工程，2015,41(8):18 -22,31.
[14] 王燕，安云杰.时间序列相似性度量方法[J].计算机工程与设计，2016,37(9) :2520 -2525.
[15] 谢晶，孙一平，黄梅.活用《职业分类大典》规范设置职业资格清单目录[J].中国人力资源社会保障，2017 (5) : 18 - 19.[16] 贾洪杰，丁世飞，史忠植.求解大规模谱聚类的近似加权核k-
出63耶算法口].软件学报，2015,26(11):2836 -2846.
[17] 范虎，花伟伟.协同过滤推荐算法的研究与改进[J].计算机
技术与发展，2013,23(9):66 -69.
责任编辑：肖滨
因篇幅问题不能全部显示，请点此查看更多更全内容