融合巴氏系数的用户聚类Slope One算法

王万良，屠海龙，朱炎亮，赵燕伟，鲍 毅

1(浙江工业大学 计算机科学与技术学院，杭州 310023) 2(杭州赫智电子科技有限公司，杭州 310026)

1 引 言

随着互联网的普及和电子商务的快速发展，用户和产品数量呈指数式增长，信息过载问题愈发严重.在大数据的背景下，信息的冗余使得搜索技术已经无法完全满足用户的个性化需求，推荐算法应运而生，如今推荐算法被广泛运用于电子商务、在线广告、社交媒体等各个领域[1].协同过滤算法是目前应用最广泛的个性化推荐算法之一[2].协同过滤的基本思想为：通过用户对于项目的历史评分矩阵，在两个维度上计算邻近关系进行预测计算，如在用户维度找到与目标用户历史评分行为最相似的邻居用户，根据邻居用户的历史评分高低产生推荐项目.

随着推荐场景中用户和项目的数目不断增大，推荐算法的输入评分矩阵增大，但是由于用户能够接触到的项目有限以及大多用户没有对项目进行评分的习惯等原因，用户对于项目的评分数量很少，导致了推荐系统中的评分数据稀疏性问题[3].针对稀疏性问题通常可使用降维和填充的方法解决.Pirasteh等通过运用用户和项目的内容信息对评分数据进行填充[4].邓爱林等利用项目聚类后进行协同过滤推荐，降低了矩阵维度[5].Wang 等首先对用户已经评分的数据进行聚类，然后结合Slope One算法来对未评分数据进行预测填充[6].另外，许多学者提出基于降维技术的稀疏性问题解决方法，如PCA[7]、SVD[8]、非负矩阵分解[9，10].

以上算法在一定程度上缓解了数据稀疏性的问题，但是算法的计算复杂度较高，在数据庞大和更新速度较快的情况下，不能很好地解决实时推荐的问题.在实时性问题的解决方面，Lemire等人提出了Slope One算法[11]，该算法易于实现和维护，准确度较高，在实时推荐上具有较大优势.但是，Slope One算法没有考虑项目之间和用户之间的差异.贺怀清等人利用资源分配的思想度量用户之间的相似度[12]，但该模型没有考虑项目之间的差异对预测结果的影响，并且用户相似度计算方法存在不对称情况.张玉连等人则利用机器学习的方法衡量项目之间的相似度[13]，该方法将基于模型的方法结合Slope One，利用梯度下降计算项目之间相似度，动态调节评分.但该方法求解过程需要多次迭代计算，计算复杂度较高.基于以上分析，本文希望在保持Slope One算法较低计算复杂度的情况下，提高其准确度，提出一种融合巴氏系数的用户聚类Slope One推荐算法(BCUC Slope One Algorithm).巴氏系数在稀疏数据下既能保证良好计算效果，并且计算简单，故引入其作为项目相似度计算方法，能够在数据稀疏条件下将项目差异考虑到模型中，算法还在用户聚类时充分分析了用户评分习惯对准确度的影响.算法基本思想如下：

1)Slope One算法对用户评分数据采用了一致性的分析，影响推荐准确度，提出一种改进的Slope One算法；

2)在用户维度，通过分析用户评分习惯，对用户评分数据进行预处理，消除评分奇异性对推荐预测的影响，再对用户进行聚类降低用户维度上的差异；

3)在项目维度，Slope One算法对系统中的所有项目采用一致性的权重对待，通过加入一种在数据稀疏条件下的相似度计算方法—巴氏系数，考虑项目之间的差异，提高推荐准确度.

2 相关工作

2.1 问题描述

推荐算法输入数据为用户(观众)对项目(电影)的确切的反馈评分数据，与观看记录、查询记录等隐式数据不同的是，评分数据直接表达了用户对项目的喜爱程度.定义用一个矩阵R(m×n)表示用户的反馈评分，m为用户的个数，n表示项目的个数.Ru，i表示用户u对项目i的评分.Ru，i∈[1，2，3，4，5]，数值越大表示用户对项目的评分越高，对项目的喜爱程度越大.用户评分矩阵如表1所示.

表1 评分矩阵Table 1 Rating matrix

图1 Slope One基本模型Fig.1 Slope One model

该矩阵通常为一个稀疏矩阵，矩阵中用户对项目没有作出评分的位置用0表示.推荐算法的本质就是补全该评分矩阵，预测目标用户对其未评分的项目的可能评分，将预测值最高的项目推荐给目标用户.

2.2 Slope One算法

Slope One推荐算法是一种基于项目的协同过滤算法，本质上是一个一元的线性预测模型[11]，f(x)表示目标用户对项目的预测评分，x表示目标用户对项目的评分，b为评分偏差.基本模型如图1.用户A对项目I和项目J 的评分分别为1 和1.5，用户B对项目I的评分为2，用户B对J 的评分可以用对项目I的评分加上用户A对项目I，J的差值表示.用户B称为目标用户，项目J称为目标项目.在已知的评分数据中有很多像(i，j)这样的项目对，将最后计算得到的平均值作为预测值.

2.3 Slope One算法具体实现

2.3.1 Slope One算法

Slope One算法可以分为计算评分偏差和预测两个过程：

用户对项目j，k的评分偏差：

(1)

Sj，k(U)表示对项目j，k都进行了评分的用户U的集合.

用户u对目标项目i的预测评分：

(2)

N(·)表示集合的数目，Ritem表示目标用户的已经评分的项目集合.

2.3.2 Weighted Slope One算法

考虑到不同的项目对(i，j)被共同评分的次数不同，不能采用相同的权值进行简单的计算.在传统Slope One算法基础上加上共同评分次数作为计算权重.改进的Weighted Slope One算法的预测部分如下：

(3)

3 融合巴氏系数的用户聚类Slope One算法

根据以上问题描述和Slope One算法的介绍分析，Slope One算法因其实现简单，在在线推荐和动态分析方面具有较大优势，但在计算过程中对所有的项目采取了一致性的对待，没有体现出项目之间差异性对推荐的影响，相对于其他基于项目的协同过滤算法推荐准确度有所降低.本文提出一种融合巴氏系数的用户聚类Slope One算法(BCUC Slope One Algorithm)，在保证其在线推荐能力的前提下提高预测准确度.

3.1 相似度计算

在推荐算法中，尤其是在协同过滤算法中，相似性的计算是最重要的步骤之一，针对不同的推荐场景和推荐算法，不同的相似性度量方法也表现出不同的效果.Pearson相关系数和余弦相似性是应用最广泛的相似性度量方法.

3.1.1 Pearson 相关系数

Pearson相关系数的计算方式如下：

(4)

Pearson相关系数计算的是对象之间的线性相关性，在基于用户的协同过滤中运用广泛.如公式所示，每一个用户对所有项目的评分向量作为用户特征，计算结果在区间[-1，+1].Pearson相关系数计算的是两个用户对项目评分的趋势差异，对用户评分大小并不敏感，如u1=[1，2，3，4]，u2=[3，4，6，7]，u3=[4，5，6，7]，直觉上u3和u2更为相似，但是Pearson的计算结果为u1和u3更加相似.另外，Pearson相关系数计算的是共同评分项目下的趋势差异，由于评分矩阵的稀疏性，共同评分项目太少甚至没有而影响相似度的计算.而且只对部分评分内容进行了计算，只考虑到了评分数据中的局部信息.

3.1.2 余弦距离

余弦距离，顾名思义，计算的两个向量夹角的余弦值.以项目之间的相似性为例，项目特征为各个用户对它的评分向量，计算方法如公式(5).

(5)

Ui，j表示对项目i，j评分的用户集合.

由于余弦计算的是向量之间的夹角，仅仅考虑了项目向量维度上的相似性，而忽视了用户之间评分值的大小问题.所以提出了修正的余弦距离，计算方法如公式(6).

(6)

与Pearson相关系数存在同样的问题是，余弦距离考虑的也是共同评分项目的评分值，由于矩阵的稀疏性而丢失了很多信息.

3.1.3 巴氏系数(Bhattacharyya coefficient)

巴氏系数被广泛应用于信号处理，图像处理，模式识别等领域[14-16]，计算的是两个概率分布之间的相似性.令p1(x)和p2(x)分别为同一定义域上的两个概率分布，巴氏系数计算两个概率分布之间的相似性如公式(7)(8).

概率分布连续情况下：

(7)

概率分布离散情况下：

(8)

基于以上分析，Slope One算法中并没有考虑到项目之间的相似性差异，没有将项目的相似度加入权重的计算.而由于矩阵的稀疏度和计算的复杂度等方面的考虑，常规的一些相似性度量方法并不适合Slope One算法中，所以提出引入巴氏系数作为Slope One的权重计算.

3.2 融合巴氏系数的Slope One算法

使用巴氏系数计算项目之间相似度，巴氏系数计算简单，计算复杂度较低，不影响Slope One算法 的在线推荐和动态更新能力.利用巴氏系数的离散计算方式，将评分的范围作为离散变量的取值范围，用户对项目的评分值的个数作为每个变量的概率，巴氏系数中的概率分布表示为pi=[pi，1，pi，2，pi，3，pi，4，pi，5]，其中pi，1表示用户i已经作出的评分中分值为1的概率.

(9)

pi，r表示对项目i评分值为r的概率分布，D∈[1，2，3，4，5]

(10)

预测公式：

(11)

巴氏系数计算相似度过程中考虑了所有的评分数据而非共同评分数据，降低了在稀疏性条件下造成的相似性计算偏差[17].例如两个项目向量Ri=[1，0，1，0，1，0]和Rj=[0，1，0，1，0，1]，分别表示各个对项目i，j的评分值，评分分值大小取值为[1，2，3].在直觉上判断i，j两个项目的相似度显然是非常高的，因为所有对项目i 和j评过分的用户对两者的评分值均为1.但是由于两个项目被同一用户评分的次数为0，所以利用Pearson相关系数和余弦距离计算的相似度为0，而利用巴氏系数计算两者的相似度为1.显然在共同评分次数较少的情况下，巴氏系数计算相似度更为准确.在计算复杂度方面，巴氏系数的项目评分向量维度大大减小，由原来的m维(用户数量)变成5维，从而在计算效率上相较于其他相似性度量方法高很多，对Slope One的在线推荐和动态更新方面的能力影响较小.

3.3 考虑评分习惯的用户聚类

经过前面改进的Slope One算法，融合了项目相似度，改变了传统Slope One中的一致性权重.但是巴氏系数在计算项目相似度时只计算了用户对项目评分值的次数，而没有考虑用户偏好之间的差异.提出使用聚类方法针对用户的历史评分数据将偏好相似的用户划分为同一类，增加使用巴氏系数计算项目相似性的准确度.

而用户评分习惯的不同会对聚类产生一定影响.用户评分习惯可以理解为用户对项目喜爱程度的表达，例如，有些用户对于喜爱的项目会打5分，对于好感度不是那么强的会打3分，我们可以称之为“乐观用户”，而“悲观用户”则对项目表现得更加苛刻，在打分过程中很少打出5分，而3分可能就能表示该用户对于项目的喜爱了.在喜爱程度的表达上，“积极用户”和“消极用户”存在很大差异，会影响到用户聚类的效果.

经过上述分析，为了消除用户评分习惯影响，提高聚类效果，需要对用户评分矩阵进行预处理.预处理方法如公式(12)，用户的平均评分值可以表示用户的评分习惯，将用户评分大于自己平均评分值的记作“高评分”，并置为1；小于等于自己平均评分值的为“低评分”，置为-1；用户未评分项分值仍为0.

(12)

表2 预处理前Table 2 Before the preprocessing

表3 预处理后Table 3 After the preprocessing

预处理具体例子如表2、表3所示：

从表2、表3可以看出，A用户和B用户评分值非0项较少，说明A、B用户评分次数多，属于系统的“活跃用户”.处理前表中A的平均评分比B高，表示A是一个“乐观用户”，而B为“悲观用户”，经过预处理之后，两人的评分情况如表2，两者评分的高低只与自己的评分习惯相关，与评分的取值范围无关.用户C的评分习惯与用户A相似，但是用户C 的评分次数不多，属于系统中的“非活跃用户”.经过预处理后的矩阵保留了原来矩阵的特征，弱化了绝对分值的影响，消除了用户评分习惯差异，可以增加聚类效果.

3.4 改进后算法步骤

输入：用户评分矩阵 R

输出：目标用户预测评分最高的K个项目

1.对用户评分矩阵根据式(12)进行预处理,根据用户的评分习惯,使用k-means聚类方法将用户聚成s类,C={C1,C2…,Cn,…,Cs}

2.在每个用户聚类Cn中：

1)利用巴氏系数公式计算每个项目之间的相似度.

2)对聚类中用户使用改进的Slope One算法， 根据巴氏Slope One算法预测公式(11)计算预测评分.

3.目标用户预测评分中根据分值大小将前K个项目推荐给用户.

步骤1中使用k-means算法对预处理之后的评分矩阵进行聚类，k-means算法是一种传统的聚类算法， 具有低计算复杂度和计算效果较好的优点[2].在步骤2中，对每个聚类使用融入了巴氏系数的Slope One算法.最后在步骤 3 中根据预测评分的大小将前K个项目作为推荐项目.

4 实验分析

4.1 数据集

本实验数据采用个性化推荐中常用的由美国明尼苏达大学GroupLens团队收集整理的MovieLens数据集[19].数据集包含943个用户对1682部电影的100，000 条评分记录，评分范围为1到5分，数值越大说明用户对电影越喜欢.其中每个用户有超过20条的评分记录.数据集的稀疏度为93.7%.实验将数据集按80%/20%随机划分成训练集和测试集，训练集作为算法的输入评分矩阵，测试集用于衡量算法的准确度.

4.2 相似度计算复杂度比较

本实验针对3.1中提到的推荐算法中常用的几种相似性度量方法和巴氏系数度量方法进行计算复杂度的比较.进行实验的相似性度量方法有欧式距离、余弦距离、Pearson相关系数、修正余弦距离和本文算法中的巴氏系数.在硬件环境等相同条件下，几种度量方法在MovieLens的数据集下进行相似度计算的平均时间的实验结果如表4所示.

表4 相似度计算时间Table 4 Time of similarity calculation

表中可以看出，巴氏系数由于每个向量的维度大大减小，计算的复杂度降低，相对于其他几种常用的相似性计算方法计算时间明显降低，其他几种常用的相似性计算方法的平均计算时间是巴氏系数的20-80倍左右.所以巴氏系数在推荐算法动态更新的要求下优势较大，更加适合应用于在线推荐领域的Slope One算法中相似度的计算.

4.3 准确度评价指标

实验采用推荐算法较常用的平均绝对误差(MAE)和均方根误差(RMSE)做为评价指标.MAE和RMSE 的值越小，代表推荐的质量越高.MAE和RMSE 的公式如下：

(13)

(14)

pi表示推荐算法的预测值，qi表示实际的评分值.N为预测评分的个数.

4.4 实验结果分析

本文使用k-means聚类方法对用户评分习惯进行聚类，聚类簇的数目会对实验效果产生影响.为了找到最适合的聚类簇数目k，首先对数据集进行聚类效果实验，找出最佳的聚类簇数目.

图2 聚类效果Fig.2 Clustering results

在MovieLens数据集上进行聚类实验，聚类簇的数目选取为2到7簇，分别计算在不同簇下的MAE值，实验结果图2所示.聚类簇实验表明，在MovieLens数据集下，对于消除了评分习惯差异的用户聚类中，聚类簇选取3或4时效果较好.本文实验中选取聚类簇数目为4.

为了验证本文算法的有效性，针对传统Slope One算法与本文算法(BCUC Slope One Algorithm)在五组MovieLens数据集上分别进行了实验对比，实验结果见图3、图4.两个算法对评分矩阵中所有未评分项都做了填充预测，MAE和RMSE对测试集中的打分项目与预测结果进行对比计算准确度.实验结果表明，本文算法在两个指标上比传统Slope One都有一定的提高.说明考虑了用户差异和项目相似性的Slope One算法可以提高推荐准确度.

图3 平均绝对误差结果对比Fig．3 MAEresults图4 均方根误差结果对比Fig．4 RMSEresults

如下页表5所示，本文算法在MovieLens 各个数据集上的平均准确度为MAE：0.738，RMSE：0.938.张玉连等人[13]将机器学习融入加权Slope One算法中，通过梯度下降的方法，迭代求解最优参数，有效提高了Slope One算法的推荐准确度.其提出的多种改进算法的准确度大致为MAE：0.72-0.74，RMSE：0.93-0.95.本文算法虽然在推荐准确度上相较之没有明显提高，但是其算法融合了机器学习的方法，在求解过程中需要利用梯度下降法不断迭代求解，求解结果也会受到下降步长和迭代次数的影响.而本文算法具有计算实现过程简便，解释性强，计算复杂度低的优势.

表5 本文算法在整个数据集上的平均指标Table 5 Average accuracy of the algorithm in the data set

5 结束语

针对目前Slope One算法没有考虑项目相似性的差异和用户评分习惯的偏差，采用了一致性权重计算，导致个性化推荐的准确度低的问题.本文通过加入一种新的相似性度量方法——巴氏系数，作为项目相似性的计算方法.巴氏系数对比其他常见的相似度计算方法，在计算复杂度上的优势较大，降低对Slope One算法在线推荐能力的影响.而且，巴氏系数能够较好解决在稀疏性问题下的相似度计算.本文又通过聚类的方法，将消除了评分习惯差异的用户进行聚类，降低了用户偏好差异对Slope One算法的影响.最后实验表明，本文提出的算法相对传统Slope One算法，保证低复杂度的前提下，在推荐准确度上也有所提高.

[1] Park D H，Kim H K，Choi I Y，et al.A literature review and classification of recommender systems research[J].Expert Systems with Applications An International Journal(ESWA)，2012，39(11)：10059-10072.

[2] Ricci F，Rokach L，Shapira B，et al.Recommender systems handbook [M].Springer，2011.

[3] Liu L M，Zhang P X，Lin L，et al.Research of data sparsity based on collaborative filtering algorithm[J].Applied Mechanics & Materials(APMSIT)，2013，462-463：856-860.

[4] Pirasteh P，Jung J J，Hwang D.Item-based collaborative filtering with attribute correlation：a case study on movie recommendation[M].Intelligent Information and Database Systems,Springer International Publishing，2014.

[5] Deng Ai-lin，Zuo Zi-ye，Zhu Yang-yong.Collaborative filtering recommendation algorithm based on item clustering[J].Journal of Chinese Computer Systems，2004，25(9)：1665-1670.

[6] Wang J，Lin K，Li J.A collaborative filtering recommendation algorithm based on user clustering and Slope One scheme[M].International Conference on Computer Science& Education(ICCSE ),2013:1473-1476.

[7] Yu Xue，Li Min-qiang.Collaborative filtering recommendation model based on effective dimension reduction and K-means clustering[J].Application Research of Computers，2009，26(10)：3718-3720.

[8] Wang X，Zhang J.SVD-based privacy preserving data updating in collaborative filtering[J].Lecture Notes in Engineering & Computer Science(LNCS)，2012，2197(1):377-384.

[9] Wang X，Zhang J，Lin P，et al.Incorporating auxiliary information in collaborative filtering data update with privacy preservation[J].International Journal of Advanced Computer Science and Applications(IJACSA)，2014，5(4)：224-235.

[10] Luo X，Zhou M，Xia Y，et al.An efficient Non-negative matrix-factorization-based approach to collaborative filtering for recommender systems[J].IEEE Transactions on Industrial Informatics(IEEE Trans Ind.Informat)，2014，10(2)：1273-1284.

[11] Lemire D，Maclachlan A.Slope one predictors for online rating-based collaborative filtering[C].Computer Science(CS)，2007：21-23.

[12] He Huai-qing，Li Tu-bo，Li Tie-jun.Slope one algorithm improved by resource allocation[J].Journal of Chinese Computer Systems，2015，36(5)：1056-1058.

[13] Zhang Yu-lian，Huan Si-si，Liang Shun-pan.Integrating machine learning into weighted slope one algorithm[J].Journal of Chinese Computer Systems，2016，37(8)：1712-1716.

[14] Nielsen F，Boltz S.The Burbea-rao and bhattacharyya centroids[J].IEEE Transactions on Information Theory(IEEE Trans.Inf.Theory)，2012，57(8)：5455-5466.

[15] Comaniciu D，Ramesh V，Meer P.Real-time tracking of non-rigid objects using mean shift[C].Computer Vision and Pattern Recognition(CVPR)，2000，2：142-149.

[16] Kailath T.The divergence and bhattacharyya distance measures in signal selection[J].Communication Technology IEEE Transactions on(IEEE Trans.Commun.Technol)，1967，15(1)：52-60.

[17] Patra B K，Launonen R，Ollikainen V，et al.A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J].Knowledge-Based Systems，2015，82(2)：163-177.

[18] Xu D，Tian Y.A comprehensive survey of clustering algorithms[J].Annals of Data Science(AODS)，2015，2(2)：165-193.

[19] Harper F M，Konstan J A.The movieLens datasets：history and context[J].ACM Transactions on Interactive Intelligent Systems(TIIS)，2016，5(4)：1-19.

附中文参考文献：

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

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

[12] 贺怀清，李图波，李铁军.资源分配的改进Slope One算法[J].小型微型计算机系统，2015，36(5)：1056-1058.

[13] 张玉连，郇思思，梁顺攀.融合机器学习的加权Slope One算法[J].小型微型计算机系统，2016，37(8)：1712-1716.