基于Weighted-slope One的用户聚类推荐算法研究

郑 丹，王名扬，陈广胜

(东北林业大学 信息与计算机工程学院，黑龙江 哈尔滨 150040)

基于Weighted-slope One的用户聚类推荐算法研究

郑 丹，王名扬，陈广胜

(东北林业大学 信息与计算机工程学院，黑龙江 哈尔滨 150040)

针对传统协同过滤推荐算法存在的数据稀疏性以及实时性差的问题，提出一种基于Weighted-slope One的用户聚类推荐算法。该算法首先利用Weighted-slope One算法的思想对初始的用户-评分矩阵进行有效填充，降低数据的稀疏性；然后，结合初始聚类中心优化改进的K-means方法对用户进行聚类，生成相似用户集合，以缩小目标用户搜索最近邻的范围；最后，结合目标用户所属的聚类，利用基于用户的协同过滤算法搜索最近邻居，为目标用户推荐对应的产品。仿真实验结果表明，改进算法可以显著降低数据的稀疏度，同时提升推荐的准确性和实时性。

协同过滤；高维稀疏矩阵；Weighted-slopeOne；K-means；聚类中心

1 概 述

随着信息网络的不断发展，令人眼花缭乱的商品、繁杂且真假难辨的信息都在急剧增长。对于用户来说，想要在这些信息中快速发现、收集和维护自己所需的信息记录需要花费大量的时间和精力，这就是“信息超载”现象。在电子商务领域，通过合理地整合信息对用户实现个性化推荐是解决信息超载问题的一种有效方案。个性化推荐作为一种依靠用户购买记录、用户偏好等为基础来实现推荐目标产品推荐的算法，在电子商务领域有着广泛的应用。在目前的电子商务推荐系统中，协同过滤是使用最广泛、最成功的推荐算法。它通过构建用户-项目的评分矩阵，搜索与目标用户具有相似偏好的邻居用户，根据邻居用户对某项目的评分值来预测目标用户对项目的评分值，从而产生推荐结果[1]。

尽管协同过滤算法在商品的个性化推荐当中取得了巨大的成功，但是，近年来随着电子商务平台上用户以及产品数量的不断增长，数据稀疏性成为限制传统协同过滤算法应用的瓶颈，并由此带来了推荐精度低、实时性差和冷启动等问题[2]。由于用户评分的项目相对于所有项目来说只占到很小的一部分，所以当用户的评分项目之间没有交集的时候，很难判断两个用户之间是否具有相似偏好，从而导致推荐精度的下降。同时，用户、产品数量的激增是用户-项目评分矩阵过大，使搜索目标用户的最近邻居范围变大，推荐实时性受到严重影响。冷启动问题是针对“小白”用户来说的。“小白”用户指的是刚进入电子商务平台的用户，没有任何的评价和购买记录，无法去度量他与其他用户的相似度。冷启动问题实际上是数据稀疏性的一个极端表现[3]。究其本质，形成这两个问题的主要原因还是数据稀疏性问题，因此，有必要对数据稀疏性进行深入研究。

近年来，针对数据稀疏性带来的问题，为了提升推荐效果，学者们将主成分分析、聚类分析、奇异值分解等算法引入到传统的协同过滤推荐算法中，通过降维，缩小目标用户搜索最近邻居的范围，使得推荐的精度和实时性有了明显提升。文献[4]提出使用主成分分析对维数进行约减，然后使用传统的K-means聚类技术对用户进行聚类，生成用户簇类，以缩小目标用户搜索最近邻居的范围，有效缓解了数据稀疏性，提升了推荐质量。文献[5]提出使用奇异值分解算法对用户-项目的评分矩阵进行处理，然后使用协同过滤算法对目标用户产生推荐，有效缓解了数据稀疏性的问题，同时推荐精度也得到了提升。文献[6]提出了一种基于项目聚类的协同过滤算法，通过对各项目进行聚类，在与目标项目最相似的若干个类中搜索最近邻居产生推荐列表。但是，直接使用主成分分析、SVD奇异值分解、聚类分析等来对原始的用户-评分矩阵进行处理的能力是有限的。因为，当用户-评分矩阵数据的稀疏程度很大时，这些方法在第一步进行处理时的效果就不太理想。

基于以上启发，文中提出一种基于Weighted-slopeOne的用户聚类推荐算法。首先借鉴Weighted-slopeOne算法的思想对初始的用户-项目评分矩阵进行填充，使初始的用户-评分矩阵的稀疏性大大降低。其次，对于已经填充的用户-评分矩阵使用一种初始聚类中心优化改进的K-means算法对用户进行聚类，生成相似用户集合。最后，使用协同过滤算法实现对目标用户的推荐。具体推荐过程为：首先判断目标用户所属的簇类，在目标用户所属的相似用户集合内实现推荐。实验仿真结果表明，文中所提出的方法不但有效降低了数据的稀疏性，同时由于是在目标用户所属簇类内为其实现系统过滤推荐，因此可以有效地降低协同过滤搜索目标用户最近邻居的范围；并且由于都是目标用户的相似用户，因此文中提出的算法在降低计算复杂度的同时，还能有效提升推荐系统的实时响应速度。

2 基于Weighted-slope One算法降低用户-评分矩阵的稀疏性

Slope One算法是于2005年由Daniel Lemire教授提出的一个基于项目的推荐算法[7]。算法以f(x)=x+b作为预测器，使用线性回归预测用户对未评分项目的打分，参数b为用户对两个项目评分的平均偏差[8]。Weighted-slopeOne是SlopeOne的一个递进算法，它均衡了每个评分项目对于目标项目的影响。由于Weighted-slopeOne在预测用户对项目的打分值时充分考虑了用户共同评分的差异度以及不同项目被用户同时评论的次数，因此，所得预测的评分与真实的用户评分是比较相近的。但是，文献[9]研究表明SlopeOne在用户-项目评分矩阵比较密集的时候推荐的效果较好，当数据比较稀疏时，其推荐的效果并不好。鉴于此，文中并不直接使用Weighted-slopeOne算法进行推荐，而是借鉴Weighted-slopeOne算法的这种对目标用户打分思想来对初始高维的用户-评分矩阵进行填充，对填充后的矩阵使用初始聚类中心优化的K-means算法进行聚类，生成相似用户集合。当对目标用户进行推荐时，首先确定目标用户所属的簇类，然后在该簇类内搜索目标用户的最近邻居，产生推荐。

使用Weighted-slopeOne对用户u的未评分项目进行填充降低用户-评分矩阵的稀疏性的过程为：首先，寻找用户u和用户v评分过的项目集合Iuv=Iu∩Iv，利用式(1)计算用户u的未评分项目j对于项目i的偏移量devji，根据式(2)得到目标用户对于项目j的评分值。

这是经典的SlopeOne算法计算目标用户对项目评分的方法，但是对项目进行评分的用户数量在最终的预测评分时显然也有影响。因此，使用Weighted-slopeOne算法修正最终目标用户u对于项目的预测评分，即根据式(3)得出目标用户对项目j的最终评分。

(1)

(2)

(3)

其中：ui，uj分别表示用户u对项目i和项目j的评分值；card(i∩j)表示项目i和项目j同时被评分过的用户数目；R(u)表示目标用户u已经评价过的项目的集合；D(j)表示与目标项目j计算得到的平均偏移量devji的集合。

通过使用Weighted-slopeOne算法对初始的用户-评分矩阵进行处理，矩阵中的大部分零元素就会被填充，从而有效降低了整个矩阵的稀疏程度。

3 初始聚类中心优化的K-means算法

K-means算法是一种基于划分的聚类分析方法，由于其理理论可靠、算法实现简单、收敛速度快，并且又容易实现对大规模数据的处理，因此是应用最广泛的聚类算法之一。但是由于传统的聚类算法对聚类中心敏感，随机地选取任意k个点作为初始聚类中心，并迭代地改变中心使聚类准则收敛，经常会导致算法陷入局部最优，产生完全不同的聚类结果。为了避免这种初始聚类中心随机选取带来的聚类结果不稳定性，学者们将数据分布的稠密程度作为指标引入到初始聚类中心的选取上，希望所选取的初始聚类中心能够在一定程度上代表数据本身的分布情况。

文献[10]通过划分高、低密度区域选择高密度区域中具有代表性的数据对象作为初始的聚类中心。文献[11]通过建立数据对象分布的密度集合，计算最近两点的垂直中点方法来确定初始聚类中心，迭代形成最终簇类。通过考察密度特性，这些算法都有效地改善了K-means的稳定性。但算法中还存在着参数选择较为主观的现象，比如对于密度参数θ选得过大，可导致本不属于同一类的样本点被划分到同一类的情况；如果过小，会导致相反的情形，导致噪声数据也被列入候选聚类中心的情况，由此导致聚类性能的下降。

基于此，文中提出一种基于距离-期望密度参数的聚类中心选择方法。该方法结合每个聚类簇大致期望的样本平均个数来确定密度θ的大小。同时，在满足期望密度的前提下，计算每个密度区域的半径，作为期望密度参数，结合数据样本间的距离，寻找初始的聚类中心。由于对用户聚类依靠的是用户对产品的评分相似性，与密度类似，偏好同一类产品的用户一般会具有相同的喜好，所以将改进的K-means聚类算法直接应用于用户聚类产生相似用户是十分有意义的。

(1)相关定义。

定义1：密度参数。

取空间中的任一数据样本xi，以其为中心，寻找距离xi最近的θ个数据样本，把xi与个样本之间的最大距离称之为样本xi的密度参数，用ε表示。

定义2：期望密度。

Eθ=a*n/k

(4)

其中：n为数据集的样本总数；k为设定的聚类个数；a为期望密度比例系数。

a可以根据经验选取，文中取a=0.6。即，如果某个数据样本被选作聚类中心，则离该对象最近的θ个样本应该占到以该对象为中心所形成的聚类簇覆盖样本的60%。

定义3：平均相异度。

数据样本之间的平均相异度定义为：

(5)

其中：xi、xj为数据集中两个数据样本；t为数据对象xj的个数；d(xi,xj)为数据样本xi与xj间的距离，文中用欧几里得距离公式进行计算：

(6)

(2)改进算法的思想。

聚类中心优化的K-means算法中，选取具有较低期望密度参数且彼此相距最远的k个对象作为初始的聚类中心，这些中心点能够很好地反映数据对象的空间分布特性，同时能保证选出的聚类中心所覆盖的区域样本密度较高。这些都使得算法具有较高的稳定性，同时使得算法能够获得全局最优的聚类效果。

4 基于用户的协同过滤推荐

协同过滤算法是于1992年由Goldberg等学者提出的，该算法是以项目属性或者用户评分相似性作为个性化推荐的基础。协同过滤算法可以分为基于用户的协同过滤和基于项目的协同过滤[12]。基于用户的协同过滤算法实现推荐时基于如下事实：如果用户对一些项目的评分比较相似，就认为他们在其他项目的评分上具有相似关系[13]。

算法的执行流程为：首先，计算目标用户与推荐系统中所有用户的相似性，找到与目标用户最相似的邻居用户集合；其次，根据最近邻居集合中用户对项目的评分去预测目标用户对未评分项目的打分；最后，根据预测的打分情况为目标用户推荐打分值最高的topM个项目[14-15]。

算法执行过程中先明确的几个计算单元如下：

(1)用户相似度计算。

用户之间的相似度是通过用户对项目的历史评分来进行度量的[16]。文中使用余弦相似性来产生用户最近邻居，其公式如下：

(7)

(2)项目评分预测

在预测项目评分时，经常选取前N个与目标用户相似性最大的用户作为目标用户的最近邻居，根据这些邻居用户对目标用户未评分项目的评分情况来预测产生目标用户对其的评分值。假设Nu表示邻居用户的集合，根据式(8)可以计算目标用户对于某项目的预测评分。

(8)

针对预测评分的值给出目标用户的推荐列表。

5 基于Weighted-slope One的用户聚类推荐算法

设用户集合为U={u1,u2,…,um}，使用改进的K-means算法生成的用户集合表示为U'={C1,C2,…,Ck}。其中，k表示生成簇类的个数，Ck表示第k个簇类。基于Weighted-slopeOne的用户聚类推荐算法的具体执行步骤如下：

输入：用户-评分矩阵D，聚类个数k，最近邻居及大小N，推荐列表的个数M；

输出：目标用户的推荐列表以及对应的评分。

Step1：根据Weighted-slopeOne算法利用式(3)对初始的用户-评分矩阵D中的0元素进行填充，生成填充矩阵Dζ；

Step2：利用改进的K-means算法基本思想对Dζ进行处理，生成k个聚类输出，各聚类的中心为ci,i=1,2,…,k；

Step3：通过式(6)计算目标用户与聚类中心ci的距离，将目标用户分配到距离最小的聚类Ci(i=1,2,…,k)中；

Step4：在目标用户所属的簇类中，根据式(7)计算目标用户与其他用户的相似性，搜索出相似性最大的前N个用户作为目标用户的最近邻居集合，记为Nu；

Step5：利用式(8)计算各个项目的预测评分，列出topM个预测得分最大的项目推荐给目标用户。

6 仿真实验与结果分析

6.1 数据集

仿真实验中，选取了MovieLens站点的电影数据集作为实验数据。数据集中包含了943个用户1 682部电影共10 000条评价得分，其中每个用户至少对20部电影进行了评分，评分值为1～5之间的整数。评分值越大说明用户对该项目的偏好性越强，0值表示用户未对该电影进行评分。

6.2 评测指标

在推荐算法中经常使用平均绝对误差(MAE)来衡量推荐结果的好坏。MAE是通过计算预测的用户评分与实际的用户评分之间的偏差来度量预测的准确性[12]。假设目标用户对项目的实际评分为{pi|i=1,2,…,n},其中n表示项目的总个数，使用推荐算法预测得到的目标用户对项目的评分为 {qi|i=1,2,…,n},那么MAE的计算公式为：

(9)

从式(9)可以看出，MAE值越小说明推荐结果的准确性越高。

6.3 仿真结果分析

为保证所选取的相似用户集合最为合理，首先针对用户簇类个数进行系统过滤算法的实现，计算其对应的MAE值，以选择最合理的用户簇类个数来对目标用户产生最终的推荐结果。

图1就是在不同的聚类个数下MAE的变化情况。

图1 不同聚类数目下的MAE值

由图1可以看出，随着聚类个数的增加，MAE的值先降后升，这说明在用户数固定的情况下，需要找到一个最优的聚类数目能够使推荐的MAE值达到最小。从图1中观察可知，当聚类个数为11时，MAE的值最低，显然对于文中所选取的数据集而言，令k=11是最合理的聚类个数。

在确定了最优的聚类个数后，将文中所提出的基于Weighted-slopeOne算法与传统的协同过滤算法、基于K-means用户聚类的协同过滤算法进行了比较。最近邻居的个数从5增至50，间隔为5。实验对比结果如图2所示。

图2 推荐结果的MAE值比较

根据图2，随着目标用户最近邻居个数的不断增加，三种算法的MAE值呈明显的下降趋势。这说明随着最近邻居个数的不断增加，可以有效提升推荐结果的准确率。但从MAE下降的速率来看，当最近邻居的个数上升到某个个数之后，MAE下降的速率越来越慢，最后趋近于平滑。这说明最近邻居的个数并不是越多越好，而是随着最近邻居数目的增多，其为MAE减小所做的贡献越来越小。在实际应用中，当考虑推荐系统实时性、存储、计算的复杂度时，合理选择最近邻居的个数对于推荐精度和维护成本都至关重要。

除此之外，在不同的最近邻居数目下对比三种算法可得，文中提出的算法较其他算法均有最小的MAE值，传统的协同过滤算法的推荐效果最不理想，添加了用户聚类的推荐效果次之。但是由于数据稀疏性和初始聚类中心随机选取可能带来的不稳定聚类结果，基于K-means的协同过滤推荐的精度也不高。而文中提出的算法无论是对数据稀疏性还是聚类结果都进行了对应的处理，可以确保在数据稀疏性降低的同时有稳定的聚类结果。显然，通过文中填充高维稀疏矩阵，实现用户聚类，为目标用户在聚类内给出推荐结果的方法不但有效降低了数据的稀疏性，同时在聚类内搜索目标用户的最近邻居缩小了搜索范围，加快了推荐算法的响应速度，推荐MAE值得到了提升。

7 结束语

文中分析陈述了协同过滤推荐算法所存在的问题以及学者为提升推荐准确率所做的研究工作。在此基础上提出了一种基于Weighted-slopeOne的用户聚类推荐算法。通过借鉴Weighted-slopeOne进行评分预测的思想对初始的用户-项目矩阵中的0元素进行填充，降低数据稀疏性，使用改进的K-means聚类算法对用户进行聚类，在簇类内查找目标用户的最近邻居最终给出预测评分以及推荐结果。仿真实验证明，文中提出的算法可以有效地提升推荐的准确性，同时由于其缩小了搜索最近邻居的空间，推荐算法的实时性也得到了提升。

[1] 王桂芬.电子商务个性化推荐系统中协同过滤算法的研究与应用[D].南昌:南昌大学,2012.

[2] 李 华,张 宇,孙俊华.基于用户模糊聚类的协同过滤推荐研究[J].计算机科学,2012,39(12):83-86.

[3] 孙小华.协同过滤系统的稀疏性与冷启动问题的研究[D].杭州:浙江大学,2005.

[4] 郁 雪,李敏强.一种结合有效降维和K-means聚类的协同过滤推荐模型[J].计算机应用研究,2009,26(10):3718-3720.

[5]VozalisMG,MargaritisKG.ApplyingSVDonitem-basedfiltering[C]//Procof5thinternationalconferenceonintelligentsystemsdesignandapplications.[s.l.]:IEEE,2005:464-469.

[6] 邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推荐算法[J].小型微型计算机系统,2004,25(9):1665-1670.

[7] 李朝阳.基于SlopeOne算法的协作过滤个性化推荐系统设计与实现[D].武汉:华中科技大学,2010.

[8] 王 毅.基于Hadoop的SlopeOne及其改进算法实现[D].成都:西南交通大学,2011.

[9] 董 丽,邢春晓,王克宏.基于不同数据集的协作过滤算法评测[J].清华大学学报：自然科学版,2009,49(4):590-594.

[10] 袁 方,周志勇,宋 鑫.初始聚类中心优化的k-means算法[J].计算机工程,2007,33(3):65-66.

[11] 周炜奔,石跃祥.基于密度的K-means聚类中心选取的优化算法[J].计算机应用研究,2012,29(5):1726-1728.

[12] 马宏伟,张光卫,李 鹏.协同过滤推荐算法综述[J].小型微型计算机系统,2009,30(7):1282-1288.

[13] 李 涛,王建东,叶飞跃,等.一种基于用户聚类的协同过滤推荐算法[J].系统工程与电子技术,2007,29(7):1178-1182.

[14] 李晓艳,张子刚,张逸石.集成k-means聚类和有监督特征选择的混合式协同过滤推荐[J].管理学报,2013,10(9):1362-1367.

[15] 张海燕,丁 峰,姜丽红.基于模糊聚类的协同过滤推荐方法[J].计算机仿真,2005,22(8):144-147.

[16] 贺银慧,陈端兵,陈 勇,等.一种结合共同邻居和用户评分信息的相似度算法[J].计算机科学,2010,37(9):184-186.

Research on User Clustering Recommendation Algorithm Based on Weighted-slope One

ZHENG Dan,WANG Ming-yang,CHEN Guang-sheng

(College of Information and Computer Engineering,Northeast Forestry University,Harbin 150040,China)

Aiming at the problems of data sparseness and the poor real-time performance of traditional collaborative filtering recommendation algorithm,a new user clustering recommendation algorithm based on Weighted-slope One algorithm is proposed.Firstly,the zero items in user-item matrix are filled by Weighted-slope One algorithm.This operation can effectively reduce the data sparseness.Secondly,the users are clustered by the optimizedK-meansalgorithm.Thisoperationcaneffectivelyfindthenearestneighborofthetargetuser.Finally,thecorrespondingproductsarerecommendedtothetargetusersaccordingtotheirnearestneighborswhicharefoundbytheusers’collaborativefilteringrecommendationalgorithm.Experimentalresultsshowthattheimprovedalgorithmcansignificantlyreducethedatasparseness,andimprovetherealtimeperformanceandtheaccuracyofrecommendation.

collaborative filtering;high-dimensional sparse matrix;Weighted-slope One；K-means;clusteringcenter

2015-07-14

2015-10-20

时间：2016-03-22

中央高校基本科研业务费专项资金项目(2572014DB05)；中国博士后科学基金面上基金(2012M520711)；国家自然科学基金资助项目(71473034)

郑 丹(1991-)，女，硕士，研究方向为数据挖掘；王名扬，博士，副教授，研究方向为数据挖掘、社交网络挖掘；陈广胜，教授，研究方向为生物质材料材质预测、新型复合材料智能化检测、技术创新方法推广应用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1521.068.html

TP

A

1673-629X(2016)04-0051-05

10.3969/j.issn.1673-629X.2016.04.011