基于相似度优化和流形学习的协同过滤算法改进研究*

宋月亭，吴 晟

(昆明理工大学信息工程与自动化学院,云南 昆明 650500)

1 引言

互联网技术极速发展的当下，各类网络应用中的用户量不断增加，互联网中的信息也呈现出指数爆炸型增长的趋势。海量资讯致使用户难以快速有效地检索到所需资源，因此如何有效地筛选和过滤信息成为当今互联网研究领域的重要问题。个性化推荐系统是现行信息过滤应用最为广泛的一种重要手段，它已经成为当前解决“信息过载”问题的重要手段，被广大电子商务系统和个性化网站所采用[1]。

在个性化推荐系统中，提出了大量的推荐算法，其中，协同过滤CF(Collaborative Filtering)算法是目前最成功、应用最广泛的个性化推荐技术之一[2]。协同过滤算法假设拥有相似兴趣的用户可能会喜欢相似的项目或者用户可能对相似的项目表现出相似的偏好程度[3]。因此，协同过滤算法依据用户相关评分记录，推荐质量较高，而且还可以发现用户本身没有发现的潜在兴趣。

协同过滤推荐算法包括：基于记忆的协同过滤算法Me-BCF(Memory-Based Collaborative Filtering)和基于模型的协同过滤算法Mo-BCF(Model-Based Collaborative Filtering)。基于记忆的协同过滤算法利用用户-项目评分矩阵，获得用户或物品间的相似关系，然后用这个相似关系产生预测评分进行个性化推荐，因而，基于记忆的协同过滤算法又可分为基于用户的协同过滤UBCF(User-Based Collaborative Filtering)算法和基于项目的协同过滤IBCF(Item-Based Collaborative Filtering)[4]算法。基于模型的协同过滤推荐算法是在离线情况下对目标用户进行建模，然后在线上使用构建好的模型对用户进行推荐，进而达到快速推荐的效果。基于用户的协同过滤算法的基本原理是：根据所有用户偏好信息(评分)，寻找与当前活动用户兴趣相似的邻居用户，然后基于邻居用户的偏好记录，为当前活动用户进行个性化推荐[5]。基于项目的协同过滤推荐算法的基本原理是：根据所有用户对项目的偏好信息(评分)，得到项目之间的相似性，然后根据活动用户的历史偏好信息，将类似的项目推荐给用户[6]。

不难看出，基于用户的协同过滤算法和基于项目的协同过滤算法本质都是基于邻域的推荐方法，在整个用户或者项目空间上对目标项进行最优邻域搜索，将最近邻居集合进行加权处理，进而产生推荐集。其核心步骤采用的方法主要为通过余弦相似度(Cosine Similarity)或Pearson相关系数法(Pearson Correlation Coefficient)得到用户间的相似度之后，运用K最近邻方法KNN(K Nearest Neighbors)为活动用户寻找偏好相似的近邻，最后运用Top-N推荐列表根据相似近邻的评分信息为活动用户产生推荐。

协同过滤算法虽然被广泛使用，但依旧存在一些问题：(1)数据稀疏性问题。每个用户拥有的评价数据只占大量数据中的一小部分，致使求解相似度时共同评分过少，用户项目评分矩阵形成高维稀疏矩阵，导致求得的相似度存在噪声。(2)可扩展性问题。推荐系统通常需要面对数以百万计的用户和项目，计算量的上升导致实时性和推荐质量的下降，为此通常采用聚类、降维的方法解决[7]。通常采用K-means聚类，该算法不用考虑用户间的相似度是多少，只选择与目标用户相似度最大的用户作为相似近邻，但其聚类结果收敛于局部最优解，优化过程与初始的聚类中心有关，选取不同的聚类中心会有不同的解，初始聚类中心数据的不同选择，可能导致最终推荐准确率不佳。

基于以上问题，本文提出一种基于相似度优化和流形学习的协同过滤算法，通过改进相似度计算，再运用流形学习的方法根据相似度对用户求解最近邻，最后求得推荐结果。考虑数据稀疏性，将评价存在的内在信息也充分使用的同时，提高推荐准确率。

2 传统协同过滤算法

2.1 用户-项目评分矩阵

定义用户集合U={1,2，…，m}，其中|U|=m，定义项目集合I={1，2，…，n}，其中|I|=n，定义用户对项目评分矩阵R=[ri,j]m×n,如式(1)所示。

(1)

2.2 用户间相似度计算

根据用户间共同评分项目的评分数据，利用相似度计算公式，求出用户i和用户j间的相似度sim(i,j)。常见的相似度计算公式如下所示：

(1)修正的余弦相似度如式(2)所示。

simcosine(i,j)=

(2)

(2)Person相关系数相似度如式(3)所示。

simpearson(i,j)=

(3)

其相似度取值为[-1,1]，值越大，则表示用户间相似程度越高。

2.3 最近邻居搜索

根据目标用户与所有其他用户的相似度，通过K-means聚类，选取与目标用户最接近的前k个用户作为其最近邻居。

2.4 评分预测

令目标用户的最近邻集合为N(u)，则利用N(u)中的用户对用户u的未评分项目进行评分。计算公式如式(4)所示。

(4)

3 基于相似度优化和流形学习的改进协同过滤算法

3.1 相似度优化

在传统的协同过滤算法相似度计算中，存在着一些问题。假设2个用户间共同评分项目很多，且2个用户对这些共同项目的评分均不高，则间接表明2个用户并不倾向于这些项目。假设2个用户间共同评分项目不多，但是对于这少量的共同评分项均有较高的评分，则间接表明2个用户更倾向于这些项目。故可以看出，用户对共同评分项的评分比重对相似度计算精度有一定的影响，因此本文引入一种共同评分项评分所占比重的加权因子优化相似度计算，该加权因子表述如式(5)所示。

(5)

式(5)中的加权因子尽管考虑了2个用户共同评分项分数所占比重，但当某个用户的评分项目很少时，该用户与某个评分很多的用户产生的共同评分项目很多，且项目评分相近或相同时，传统的相似度计算方法会产生高相似度的结果，但2个用户在非共同评分项目上的评分可能存在较大的差异。因此，考虑到共同评分项目个数在2个用户总评分项目集合中所占的比例，进一步改进加权因子，如式(6)所示。

w(i,j)=w1(i,j)·w2(i,j)=

(6)

其中，Tij={(ts|ts∈T∧ri,s≠0∧rj,s≠0},为2个用户共同评分项目集合，Ti和Tj分别为各用户的评分项目集合，Ti={ts|ts∈T∧ri,s≠0}，Tj={ts|ts∈T∧rj,s≠0}。

综上，通过加权因子对传统的相似度计算方法进行优化，最终得到如下所示的相似度计算方法：

(1)基于修正余弦相似度优化方法。

sim′cosine(i,j)=

(7)

(2)基于Pearson相似度优化方法。

sim′pearson(i,j)=

(8)

3.2 流形学习聚类算法

流形学习是解决高维大数据问题的方法，对于数据稀疏且高维的协同过滤推荐系统，流形聚类可通过降维发现数据内在联系，减少传统聚类存在的局部最优解问题[8]。其中较为典型的是谱聚类算法，谱聚类以图论为基础，将一个样本作为定点，样本间相似度作为带权边，寻找组成边权重较低且组内边权重较高的图[9,10]。该流形聚类算法以样本间相似度为核心，相较传统K-means聚类方法，将聚类问题转换为图分割问题，不受形状限制，可求得全局最优解。本文采用流形聚类改进协同过滤推荐算法中传统的基于距离的K-means聚类，可在搜索最近邻居的过程中，通过降维降低计算成本的同时获得全局最优解，提高推荐准确率。步骤如下所示：

(1)输入一个M×N的矩阵W，即W中共包含N个数据点。

(2)构建W的相似度矩阵D∈RN×N，其中，Dij=Dji(i,j=1,…,N)。以所有顶点度为对角元素构成的矩阵D的具体构建方法如式(9)所示。

D=diag(D11,D12,…,DNN)

(9)

(3)计算拉普拉斯矩阵L，如式(10)所示。

L=D-W

(10)

(4)对L进行归一化处理，得到归一化矩阵E。其中

令：

(5)计算矩阵L的归一化矩阵E的Y个最大特征值及其对应的特征向量，形成一个N×Y的特征矩阵，记为Q。

(6)将特征矩阵Q的每一行看成k维空间中的一个向量，使用K-means对其进行聚类。

3.3 基于相似度优化和流形学习的协同过滤算法

针对传统协同过滤算法中存在的不足，通过对相似度和搜索最近邻居进行优化改进，本文提出一种基于相似度优化和流形学习的协同过滤算法MLCF+(Collaborative Filtering algorithm based on Manifold Learning and similarity optimization)。其基本思想为：基于用户间共同评分项目通过加权因子获得更为精确的用户相似矩阵，利用流形学习中的谱聚类算法将与目标用户相似度最大的最近邻居聚为一类，在最近邻域中对目标用户进行TOP-N推荐。该算法旨在通过加权相似度计算影响因子对相似度计算进行优化，同时通过流形学习中的谱聚类算法，缓解传统协同过滤算法中运用的K-means等聚类算法初始聚类中心选择对最后推荐准确率的影响，使聚类收敛于全局最优，通过对分类结果精度的提高进而提高推荐准确率。MLCF+算法流程如图1所示，具体步骤如下所示：

步骤1对用户评分矩阵R=[ri,j]m×n，根据加权相似度优化计算公式计算各用户间的相似度，本文选用优化后的Pearson相似度计算方法，得到用户间的相似矩阵A∈Rm×m，其中Ai,j=sim(i,j)。

步骤2将每个用户对应到谱图中的一个顶点，利用谱聚类，通过构建拉普拉斯矩阵、求取特征向量进而重组矩阵进行聚类，将所有用户分成k类，分别记为U1,U2,…,Uk，其中，Ui∩Uj=∅，1≤i,j≤k,U1∪U2∪…∪Uk=U。

步骤3设目标用户i∈Uj，该集合内用户和评分项目间的信息矩阵记作Hi∈Rni×m，目标用户i已评分项目集合为G，未评分项目集合为S，其中，ni为Uj集合中用户个数。计算矩阵Hi中各项目间相似度，得到项目间相似度矩阵V∈Rn×n。

步骤6选取集合S中对目标用户i评分最高的前X个项目作为推荐集合。

Figure 1 Flow chart of MLCF+ algorithm图1 MLCF+算法流程图

4 实验结果及分析

4.1 实验数据及评价指标

本文选用Epinions数据集和MovieLens数据集进行实验。其中，Epinions数据集包含49 290个用户对139 738个项目的共664 824条评分数据，评分为1～5分，数据稀疏度为99.99%。MovieLens数据集包含943个用户对1 682个项目的共100 000条评分数据，评分为1～5分，数据稀疏度为93.7%。实验中，随机取80%的数据作为训练集，20%的数据为测试集。

利用平均绝对误差MAE(Mean Absolute Error)、均方根误差RMSE(Root Mean Squared Error)和召回率Recall作为实验结果评价指标。MAE和RMSE的值越小，召回率越大，则推荐准确率越高。计算公式分别如式(11)～式(13)所示。

(11)

(12)

(13)

4.2 实验结果及分析

取0～200内10个不同的K值来测试基于相似度优化和流形学习的协同过滤算法MLCF+、传统协同过滤算法CF和不优化相似度的流形学习协同过滤算法MLCF(Collaborative Filtering algorithm based on Manifold Learning)。采用5折交叉验证法进行验证，重复实验5次取平均值作为最终结果。

实验1在Epinions数据集上，K∈[0,200]时传统CF算法、MLCF算法和MLCF+算法的平均绝对误差MAE和均方根误差RMSE对比如图2和图3所示。从图2和图3可以看出，在Epinions数据集上，随着K值的增大，3种算法的MAE值和RMSE值均呈先快速下降后逐渐平稳的趋势。其中，MLCF算法相对传统CF算法，MAE和RMSE均有降低，准确率得到了提高。与此同时，优化相似度的MLCF+算法比不优化相似度的MLCF算法的MAE和RMSE更低，准确率最高。

Figure 2 MAE comparison of different algorithms on Epinions dataset图2 在Epinions数据集上不同算法的MAE对比

Figure 3 RMSE comparison of different algorithms on Epinions dataset图3 在Epinions数据集上不同算法的RMSE对比

实验2在MovieLens数据集上，K∈[0,200]时传统CF算法、MLCF算法和MLCF+算法的平均绝对误差MAE和均方根误差RMSE对比如图4和图5所示。

Figure 4 MAE comparison of different algorithms on MovieLens dataset图4 在MovieLens数据集上不同算法的MAE对比

Figure 5 RMSE comparison of different algorithms on MovieLens dataset图5 在MovieLens数据集上不同算法的RMSE对比

从图4和图5可以看出，在MovieLens数据集上，实验结果呈现的整体趋势与Epinions数据集上的一致，随着K值的增大，3种算法的MAE值和RMSE值同样呈先快速下降后逐渐平稳的趋势。相较Epinions数据集上的实验结果，各算法在MovieLens数据集上稳定性稍有不足，但总体准确率均有提高，MAE和RMSE值更小。与此同时，优化相似度的MLCF+算法对比不优化相似度的MLCF算法和传统CF算法，拥有更低的MAE和RMSE值，准确率更高。

实验3在用户聚类过程中设定将用户分割为2～6个类，进而在每个类中对项目进行推荐，计算平均召回率。在MovieLens数据集上，针对传统CF算法在不同K值下推荐结果的召回率结果如表1所示。由表1中可看出，当K=130时，传统CF算法召回率最高，因此对于MLCF算法和MLCF+算法也取K=130，即表示在推荐过程中项目最近相似项目集合数为130。表2和表3所示分别为MLCF算法和MLCF+算法在不同聚类数下推荐结果的召回率。

结果表明，与传统协同过滤推荐算法(CF)相比，MLCF算法和MLCF+算法的召回率都有明显提高，另外，在相同聚类数和迭代次数下，相似度优化的MLCF+算法比不优化相似度的MLCF算

Table 1 Recall of traditional CF algorithm under different K values表1 传统CF算法在不同K值下的召回率

法推荐结果的召回率高。说明本文提出的基于相似度优化和流形学习的协同过滤算法(MLCF+)在推荐准确率上相较传统方法和单一改进方法得到了一定的提升。同时可以看出，当迭代次数为15时，MLCF算法和MLCF+算法的召回率基本达到最大值。用户聚类数为2时，2种算法的召回率最大，推荐准确率最高，且当聚类数小于4时，2种算法的召回率均基本都大于传统协同过滤算法的。

综合上述实验，表明本文提出的MLCF算法可以更为精准地通过聚类找到与目标用户具有相似爱好的用户，进而获得更高准确率的推荐。结合相似度优化的MLCF+算法，拥有优于其他算法的召回率，缓解了数据稀疏性的问题，从而进一步提高了协同过滤推荐算法的准确率。

Table 2 Recall of MLCF algorithm without optimized similarity under different clustering numbers表2 不优化相似度的MLCF算法在不同聚类数下的召回率

Table 3 Recall of MLCF+ algorithm with optimized similarity under different clustering numbers表3 优化相似度的MLCF+算法在不同聚类数下的召回率

5 结束语

传统的协同过滤算法存在数据稀疏性和可扩展性的问题，面对高维稀疏数据，如何降维后精准发现相似项进而进行推荐，是该算法改进的关键。本文提出了一种基于相似度优化和流形学习的协同过滤算法，通过考虑加权因子优化传统相似度计算，提高相似度计算准确率，同时利用流形学习中的谱聚类对矩阵进行用户聚类搜索最近邻居，降低用户维度的同时，使用户聚类结果收敛于全局最优，进而提高协同过滤算法推荐准确率。实验结果表明，基于相似度优化和流形学习的协同过滤算法相较传统算法，推荐准确率得到了改善。下一步将结合冷启动问题进一步改善协同过滤算法性能。