杨大鑫，王荣波，黄孝喜，谌志群

(杭州电子科技大学 计算机学院，浙江 杭州 310018)

0 引 言

随着互联网和电子商务的飞速发展，在大量的商品信息面前，用户或消费者往往很难发现最需要或最合适的商品。在信息爆炸的时代，如何解决信息超载的问题，受到了越来越多的关注，并提出了多种推荐算法，主要包括基于规则的推荐算法[1]、基于模型的推荐算法[2]和协同过滤推荐算法[3]等。虽然协同过滤推荐算法在现实中有很多的应用[4-8]，但是它在处理大数据时会存在稀疏性和扩展性等问题，导致推荐效果不理想。对研究人员有很大的挑战。其中，文献[9]提出了一种通过矩阵聚类的协作过滤算法，利用矩阵聚类算法对用户评分数据进行聚类，然后对聚类后的子矩阵进行协作过滤，提高了算法的推荐精度。文献[10]利用BP神经网络来预测用户对项目的评分，减小了数据集的稀疏性，提高了推荐系统的推荐质量。但是训练BP神经网络模型需要额外的时间花销。文献[11]利用奇异值对高维数据矩阵进行降维，使得评分矩阵变得密集，以此来减小数据矩阵的稀疏性。但是奇异值分解之后会导致数据丢失，在高维数据矩阵中，降维效果不是很理想。文献[12]对用户和项目两个维度进行联合聚类，通过对聚类信息的平滑处理和对用户未评分项目的预测，在数据稀疏的问题上进行改进，从而提高了推荐的质量。

针对传统的协同过滤推荐算法在处理大数据时存在的稀疏性、扩展性等问题，文中提出了一种基于最小方差的K-means用户聚类推荐算法。首先利用Weighted Slope One算法对数据矩阵中的未评分项进行预测，减小其稀疏性；然后通过基于最小方差的K-means算法对填充后的评分数据进行聚类，减少用户最近邻搜索空间，提高算法的扩展性；最后在目标用户所在的类中利用传统的基于用户的协同过滤进行推荐，生成最终的推荐结果。并通过与其他算法的对比验证该算法。

1 相关背景知识

1.1 用户相似性计算

基于用户的协同过滤推荐算法通过用户对项目的历史评分来度量用户之间的相似度。其中，计算用户相似度的方法有如下几种：皮尔逊(Pearson)相关系数法、余弦向量法和修正的余弦向量法等。文中采用余弦向量法来产生用户最近邻居，公式如下：

(1)

1.2 项目评分预测

利用式(1)的相似性计算可以得到目标用户u的最近邻居。设目标用户u的最近邻居的集合为Nu，则可以从目标用户u对最近邻居集合项目的评分中得到其对项目i的预测评分，公式如下：

(2)

1.3 基于Weighted Slope One算法降低数据稀疏性

初始数据矩阵中的0元素经过Weighted Slope One算法处理后可以降低其稀疏性。因为在推荐系统的应用过程中，用户对项目的评分数通常会大于2，所以为了平衡各个评分项目对于目标项目的影响，需要用到Weighted Slope One算法[13]，它是Slope One算法[14]的一个递进算法。

首先，定义一个数据矩阵R，Ru,i为用户u对项目Itemi的评分；Iu为用户u所有评分的项目；Ui为对项目Itemi进行评分的用户集合；Uij=Ui∩Uj为对Itemi和Itemj两个项目都评过分的用户集合；Numij为集合中元素的数目。

项目Itemi和Itemj之间评分的偏差可以由式(3)得到：

(3)

最后，得到目标用户user对项目Itemi的预测评分：

(4)

1.4 K-means算法

设待聚类的数据集为X={xi|xi∈RP,i=1,2,…,n}。K个聚类中心分别为M1，M2，…，Mk，于是用wj(j=1,2,…,k)表示聚类的k个类别。

定义1：两个数据对象间的欧氏距离为：

(5)

定义2：同类别中数据对象的算术平均为：

(6)

定义3：聚类准则函数为：

(7)

在传统K-means算法中，初始簇心的选择是随机的，通过相似度计算，把数据集中的数据样本与最近的初始中心归为一类，不断重复这一过程，直到各个初始中心在某个精度范围内不变。具体算法步骤如下：

(1)在包含N个样本的X中随机选择k个样本数据作为初始簇心Mi(i=1,2,…,k)；

(2)利用式(5)，计算X中各个样本数据p到Mi的距离d(p,Mi)；

(3)找到每个样本数据p的最小的d(p,Mi)，把p加入到与Mi相同的簇中；

(4)完成所有样本的遍历之后，通过式(6)重新计算Mi的值，作为新的簇心；

(5)重复步骤2～4，直到目标准则函数E取值不再变化。

2 基于最小方差优化K-means初始簇心

在众多聚类算法中，K-means算法十分典型，虽然实现起来简单方便，但也有一些弊端。首先，K值是根据人的经验随机确定的，具有一定的盲目性，如果不了解要聚类的数据，那么给出合理的K值就会非常困难；其次，对初始簇心的选择也是随机的，不同的簇心会导致不同的聚类效果，如果选择了孤立点，则聚类结果会有很大的差异。

针对K-means算法存在的缺陷，许多研究者对其进行了优化[15-17]。文中则对初始聚类中心基于最小方差进行优化[18]，在不同范围内选择K个方差最小的样本作为初始簇心。根据方差的定义，一个样本的方差越小，它附近的数据分布就会越密集，使得簇心的选取就会越客观，聚类结果越准确。具体选取步骤如下：

定义4：样本xi到所有样本距离的平均值为：

(8)

定义5：样本xi的方差为：

(9)

定义6：数据集样本的平均距离为：

(10)

(2)利用式(10)计算出X中各个样本之间距离的平均值cmean；

(3)在以cmean为半径的圆之外寻找另一个方差最小的样本，把它作为第二个簇心，添加到集合C中；

(4)重复上一步，在剩余的样本中不断寻找，找到K个簇心之后，算法结束。

通过上述步骤选取到的中心点紧密度极高，可以较好地反映样本的分布情况，具有一定的客观性，聚类结果更加稳定、可靠。

3 基于最小方差的K-means用户聚类推荐算法

该算法中每条数据主要由用户、项目、评分3部分组成。设目标用户为u，用户集合为U={u1,u2,…,um}，基于最小方差优化后的K-means算法生成的用户集合表示为U={C1,C2,…,Ck}。其中，k为生成的簇类个数，Ck表示第k个簇类。基于最小方差的K-means用户聚类推荐算法的描述步骤如下：

输入：用户-项目数据矩阵Rm×n，聚类个数k；

输出：N个推荐项目。

Step3：利用式(5)计算u与k个簇心之间的相似度，然后把u加入到与其最相似的类中；

Step4：利用式(1)计算u与同类中其他用户的相似性，得到其最近邻居集Nuj(j=1,2,…,m)；

Step5：得到最近邻居集之后，可以根据它们对项目的评分，利用式(2)求得u对待推荐项目的预测分，从高到低排序之后，把前N个项目推荐给u。

4 实 验

4.1 数据集与评测标准

采用MovieLens数据集对算法的性能进行测试。数据集中包括943个用户对1 682部电影的10万多条评分，评分为1～5之间的整数。评分值越大说明用户对这部电影越喜欢，0表示用户没有对该电影进行评分。根据实验需要，将其中的80%作为训练集，其余20%作为测试集。

平均绝对偏差(Mean Absolute Error，MAE)是一种常用的推荐质量度量方法，通过计算预测评分与实际真实评分之间的偏差来度量预测的准确性。MAE越小，推荐精度越高。MAE的计算公式如下：

(11)

其中，pi表示用户预测的评分；qi表示对应的实际评分。

4.2 实验结果与分析

实验首先对初始数据中的0元素进行有效消除，然后采用基于最小方差的K-means算法对处理后的数据进行聚类，最后在目标用户所在类中用传统的协同过滤算法输出最终的推荐结果。通过实验对传统的协同过滤算法、简单K-means用户聚类推荐算法和文中算法进行了对比。设定用户聚类数为14，最近邻居的个数从5增加到50，间隔为5。实验结果如图1所示。

由图1可知，三种算法的MAE值都会随着目标用户最近邻个数的增加而降低，说明推荐的准确率可以随着目标用户的最近邻居数的增加而得到有效提高。而文中算法在不同邻居个数下的MAE值都是最低的，由此可见，与传统协同推荐算法和简单用户聚类推荐算法相比，文中算法具有更好的推荐效果。

图1 实验结果对比

在进行传统的推荐之前，文中算法由于对初始数据进行了填充，并且对用户数据基于最小方差进行了聚类，使得用户最近邻搜索空间更具客观性，选取到的最近邻居更加准确。实验结果表明，相比于传统的协同过滤推荐算法，文中算法的准确度更高。

5 结束语

从数据稀疏性和算法扩展性两方面进行改进，文中提出了一种基于最小方差的K-means用户聚类推荐算法。一方面，利用Weighted Slope One算法对初始数据矩阵进行填充，降低其稀疏性；另一方面，采用基于最小方差的K-means算法对填充后的数据进行聚类，提高算法的扩展性。实验结果表明，文中算法在一定程度上改善了数据稀疏性和算法扩展性，提高了算法的推荐质量。

[1] 陈华月,余 刚,朱征宇.基于加权关联规则的用户关注项目推荐算法[J].计算机工程,2006,32(6):86-88.

[2] 伍杰华,朱岸青,蔡雪莲,等.基于隐朴素贝叶斯模型的社会关系推荐[J].计算机应用研究,2014,31(5):1381-1384.

[3] SCHAFER J B,DAN F,JON H,et al.Collaborative filtering recommender systems[C]//The adaptive web:methods and strategies of web personalization,lecture notes in computer science.Berlin:Springer-Verlag,2007:291-324.

[4] 游 文,叶水生.电子商务推荐系统中的协同过滤推荐[J].计算机技术与发展,2006,16(9):70-72.

[5] 曹一鸣.基于协同过滤的个性化新闻推荐系统的研究与实现[D].北京:北京邮电大学,2013.

[6] KONSTAN J,MILLER B,MALTZ D,et al.GroupLens:applying collaborative filtering to usenet news[J].Communications of the ACM,1997,40(3):77-87.

[7] PARK S T,PENNOCK D M.Applying collaborative filtering techniques to movie search for better ranking and browsing[C]//Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining.New York:ACM,2007:550-559.

[8] 孟 佩,曹 菡,师 军.基于Softmax回归模型的协同过滤算法研究与应用[J].计算机技术与发展,2016,26(12):153-155.

[9] 高凤荣,邢春晓,杜小勇,等.基于矩阵聚类的协作过滤算法[J].华中科技大学学报:自然科学版,2005,33:257-260.

[10] 张 锋,常会友.使用BP神经网络缓解协同过滤推荐算法的稀疏性问题[J].计算机研究与发展,2006,43(4):667-672.

[11] VOZALIS M G,MARGARITIS K G.Applying SVD on item-based filtering[C]//Proceedings of 5th international conference on intelligent systems design and applications.[s.l.]:IEEE,2005:464-469.

[12] 韦素云,肖静静,业 宁.基于联合聚类平滑的协同过滤算法[J].计算机研究与发展,2013,50(S):163-169.

[13] 郑 丹,王名扬,陈广胜.基于Weighted-slope One的用户聚类推荐算法研究[J].计算机技术与发展,2016,26(4):51-55.

[14] LEMIRE D,MACLACHLAN A.Slope one predictors for online rating-based collaborative filtering[C]//SIAM data mining.California:SIAM,2005:21-23.

[15] ERISOGLU M,CALIS N,SAKALLIOGLU S.A new algorithm for initial cluster centers in k-means algorithm[J].Pattern Recognition Letters,2011,32(14):1701-1705.

[16] 汪 中,刘贵全,陈恩红.一种优化初始中心点的K-means算法[J].模式识别与人工智能,2009,22(2):299-304.

[17] 杨善林,李永森,胡笑旋,等.K-means算法中的k值优化问题研究[J].系统工程理论与实践,2006,26(2):97-101.

[18] 谢娟英,王艳娥.最小方差优化初始聚类中心的K-means算法[J].计算机工程,2014,40(8):205-211.