融合多信息的跨域推荐算法

钟俊伟，张立臣

（广东工业大学计算机学院，广州 510006）

0 引言

随着互联网的快速发展，如今的信息量也呈几何式的增长，信息超载已经成为了不可忽视的问题。推荐系统是解决信息超载问题的有效途径，它能通过用户和项目的信息向用户推荐其感兴趣的信息和商品，使人们更高效地获取需要的信息。

协同过滤是推荐系统中效果比较好的算法，其为一个用户找到与他有相似兴趣的其他用户，将他们感兴趣的内容推荐给此用户，由于其速度与效果均比较良好，是目前互联网邻域使用较多的一个算法。然而，在当前的互联网环境下，随着用户规模和项目数量的急剧增长，传统的协同过滤推荐算法的缺陷逐渐暴露出来，特别是新用户、新项目和新系统的冷启动以及用户行为数据稀疏等问题，这些问题致使协同过滤推荐性能降低，推荐效果不佳。

而来自于不同平台（社交媒体和电子商务网站等）的用户兴趣偏好或项目特征（属性、类别等）之间存在很强的关联性和依赖性。跨域推荐可以从其它邻域中获取有效的用户偏好或项目特征的信息来丰富目标邻域中的数据，精准地预测用户行为，提供更加合理和个性化的推荐服务。

近年来，国内外研究人员对跨域推荐进行了不少研究。Li等提出了通过基于码本的知识转移（Codebook Transfer，CBT）进行跨域推荐，该方法可以从其他一些邻域的辅助评分矩阵中转移有用的知识，以弥补评分矩阵的稀疏性。通过将集群级别的用户项目评分模式压缩为信息丰富且紧凑的知码本进行迁移，可以通过扩展码本来重建稀疏目标评级矩阵。Yu等提出了一种具有扩展的双边跨域协同算法，通过辅助域的潜在因子空间进行用户和项目特征分类，可以将知识辅助域的用户和项目侧扩展到目标域的原始特征向量。Veeramachaneni等提出了使用最大边际矩阵分解对评级矩阵进行知识提取，通过重建目标评级矩阵进行跨域推荐。陈燕等利用概率矩阵分解对源域评分矩阵进行提取特征，再利用给予模拟退火和遗传算法优化的K-means算法进行聚类，最后利用得到的各领域重叠分组得到共享评级。

上述算法从跨域推荐的角度来解决数据稀疏与冷启动的问题，相对于传统单域中的协同过滤，在一定程度上减少了数据稀疏带来的预测问题，提高了预测的准确性。但大多依然停留在仅对评分矩阵进行知识的提取，对于数据源含有的如评论时间、项目分类等信息依然没有充分地利用，如果能够将这些信息融入到推荐的过程中，那么推荐的精准度将能有所提升。

为了解决上述问题，本文的工作如下：

（1）提出使用谱聚类取代传统跨域推荐CBT算法的双边K-means聚类，提升提取信息时的准确度。

（2）提出对用户侧数据处理中引入时间信息的加权相似度方法，项目侧引入类别信息的加权相似度方法，将多信息融入到推荐中。

（3）在MovieLens-Latest与豆瓣电影数据集中使用改进的算法与对比推荐算法进行实验分析，结果表明本文的算法准确性优于对比推荐算法。

1 密码本迁移算法（CBT）

CBT算法是目前通过矩阵分解进行推荐中使用较多的跨域协同过滤算法，其利用正交非负三分解（ONMTF）将源评分矩阵进行三分解，从而获取评分矩阵中用户侧的聚类知识与项目侧的聚类知识，ONMTF不同于非负矩阵分解（NMF）将矩阵分解为两个部分，ONMTF将非负正交矩阵分解为三个因子，如公式（1）所示：

式（1）中代表了矩阵的行向量的聚类特征，代表了矩阵的列向量的聚类特征，则可以认为是缩放因子。

由于矩阵的正交非负限制，一般来说实现ONMTF会利用对矩阵进行双边kernel K-means聚类来获得分解结果，则对评分矩阵使用ONMTF就可以获得评分矩阵用户侧的聚类知识与项目侧的聚类知识。

获取到了源域的聚类知识并进行交替更新后，CBT算法根据这些群集的聚类知识构造密码本，以密码本作为两个邻域的信息传输媒介，密码本的构建方法如公式（2）所示：

式中为源域的评分矩阵；，是二值化矩阵，先从源域中通过ONMTF分解得来的两个因子，交替更新，每行中最大的表示为1，其余为0；1表示元素全为1的向量。

得到密码本后，由于密码本含有源域中获取的群集聚类知识，可以通过目标域的评分矩阵与的交互扩展来取得结合源域中迁移的知识的新目标域预测矩阵。具体重建矩阵方法如公式（3）所示：

通过CBT算法可以将通过信息更新为稠密的辅助源域提取信息，将原来稀疏的目标域评分矩阵扩充为评分信息更为饱满的评分矩阵，从而达到缓解数据稀疏和冷启动问题的目的。

2 融合多信息的跨域推荐

本文针对传统跨域推荐算法在辅助域评分矩阵提取信息时的精确性和未使用域中更多信息的问题，提出一种基于谱聚类的融合多信息的改进跨域推荐算法。首先使用双边谱聚类替换在ONMTF分解时使用的双边K-means聚类，再利用谱聚类的特性，将用户评价时间信息和物品分类信息通过相似度矩阵的加权融合加入到提取信息的过程，完成多信息的融合。

2.1 谱聚类

CBT算法中使用ONMTF算法分解获得辅助域的行聚类特征和列聚类特征，分解过程直接使用与NMF等价的kernel K-means，对辅助域评分矩阵进行双边的K-means聚类，但由于评分矩阵的稀疏性，K-means聚类的结果并不一定能达到最好的效果。

谱聚类的主要思想是将数据看作无向权重图，每条数据当作图中的点，点与点之间的边根据权重值来决定，通过对所有数据点组成的图进行切图，使得切图后不同子图间的边权重和尽可能低，子图内的边权重高，从而达到聚类的目的。

谱聚类由于只需要数据之间的相似度矩阵，因此对于稀疏数据的聚类很有效，与之对比，K-means一般难以达到其精准度，这是非常有利于对稀疏评分矩阵使用的，而谱聚类在使用ncut方式来切图的时候与kernel K-means是等价的，因此在ONMTF分解时，同样可以使用双边的谱聚类来完成，其依然能够将矩阵中的数据提取出来。本文提出将ONMTF算法中使用的K-means双边聚类替换为使用谱聚类进行双边聚类，其不仅可以将提取信息的准确性提升，同时也为引入数据中更多信息用于推荐提供了可能性。

具体的，谱聚类首先需要生成相似矩阵，根据相似矩阵构建邻接矩阵和度矩阵，再通过邻接矩阵和度矩阵求出拉普拉斯矩阵，归一化拉普拉斯矩阵后，生成最小的聚类个数特征值和对应的特征向量，最后将特征向量使用传统聚类算法聚类即可得到结果，由于谱聚类返回的结果并不包含聚类中心，本文取聚类标签的点的平均值作为ONMTF中双边聚类的结果。

2.2 融入用户侧时间信息

用户评价时间可以反映用户的兴趣趋势，由于用户的兴趣点将随着时间而迁移，因此可能曾经喜欢的物品在当下就会变得没有那么喜欢，用户会更倾向于选择目前兴趣最浓厚的物品，如果能够将时间信息融入到推荐过程中，那么推荐的结果将更为准确。

本文利用用户随时间迁移兴趣的特征，设计了一种随时间的变化而改变的函数以表示用户的兴趣度，如公式（4）所示：

式中T表示用户在评价物品时的时间，表示用户第一次评价的时间，T表示用户最新评价的时间。

在获得了时间兴趣度函数F后，目标就是将其整合到推荐过程中，由于谱聚类对相似度矩阵的敏感性，因此将相似度矩阵作为融合切入点，将时间信息融入其中，本文通过将皮尔逊相关系数与F融合得到综合相似度，从而达到融入信息的目的，具体如公式（5）所示：

得到了融合时间信息的相似度算法后就可以构建用户侧相似度矩阵用于用户侧信息提取。

2.3 融入项目侧分类信息

对于项目侧，由于项目本身就拥有天然的分类方式——类型信息，同类型项目的相似度一般会比不同类型的相似度更高，本文在项目侧引入分类信息。

具体的，由于项目数据中一般都含有项目所属类型信息，且其一般不只是唯一的，因此如果通过类型信息来决定相似度则需要使用一个相似度的衡量方法。由于类型信息一般都为文本信息，且拥有公共集，两个项目间拥有交集的可能性也比较大，本文使用Jaccard相似度作为分类信息的相似度度量方法，如公式（6）所示：

式中，表示两个项目的类型集合。

项目的相似度单独使用类型信息来衡量的话显然不是很好的选择，因此本文还使用了项目侧评分矩阵的余弦相似度作为加权组合，余弦相似度如公式（7）所示：

最终的相似度矩阵由对类型信息使用Jaccard相似度取得的相似矩阵和对项目侧评分矩阵使用余弦相似度取得的相似矩阵加权综合求出，如公式（8）所示：

得到了融入类别信息的加权相似度算法后则能够构建项目侧相似度矩阵，结合之前获取到的用户侧相似度矩阵则能够进行双边的谱聚类，获取融合了多信息的知识聚类，从而能够构建更为准确的密码本进行知识的迁移。

3 实验验证

3.1 实验数据集

（1）豆瓣电影数据集：包含416万条电影评分，63万用户，14万部电影，评分范围为1～5。从中提取拥有较稠密评分的子矩阵作为转移信息的辅助域，其中包含173个用户和247个项目，数据总条目为12775条，其密度为29.89%。同时，也提取部分数据作为目标域，为了稀疏矩阵的模拟，提取其中的500个评分数目大于20的用户，提取后的数据总条目为17656条，拥有500个用户，975个项目。其中300个用户共10935条评分条目作为训练集，200个用户共6721条评分条目作为测试集。

（2）MovieLens-Latest数据集：包含10万条电影评分，600名用户，9000个项目，评分范围为1～5。同样提取出500个评分数目大于20的用户，提取后的数据总条目为55372条，拥有500个用户，1297个项目。其中300个用户共32741条评分条目作为训练集，200个用户共22631条评分条目作为测试集，数据稀疏度如表1所示。

表1 数据稀疏度

3.2 评价指标

本文采用平均绝对误差（MAE）作为评价指标，MAE评价值越低越好，计算见公式（9）：

式中p为预测评分，r为真实评分，为测试的次数。

3.3 实验算法

（1）奇异值分解SVD：一种经典的单域协同过滤算法，这里主要使用的是User-Based SVD，可以与跨域协同算法比较预测结果。

（2）非负矩阵分解NMF：同样是经典的单域协同过滤算法，这里用来与SVD进行比较，防止单个算法的预测不佳是由于对数据的不支持所导致。

（3）CBT：一种跨域协同过滤算法，是本文改进算法的基础算法，用于比较改进算法的效果。

（4）SC-CBT（Spectral Clustering-CBT）：本文提出的基于谱聚类的CBT算法，主要用于比较加入多信息后的GSC-CBT是否效果更佳。

（5）GSC-CBT（Gathered Spectral Clustering-CBT）：本文提出的算法，与其他算法进行对比。

3.4 实验流程

实验首先对两个稀疏数据集使用传统的协同过滤算法SVD和NMF，在不同的近邻个数下查看预测MAE，实验结果使用matplotlib进行绘图，以便与跨域协同过滤算法进行对比。

从图1和图2可以看到，对稀疏度如此高的评分矩阵使用SVD与NMF两种单域算法的效果并不好，预测的结果较差，传统单域推荐算法在数据稀疏条件下的发挥并不理想。

图1 对豆瓣数据集使用SVD与NMF的结果

图2 对MovieLens-Latest数据集使用SVD与NMF的结果

之后对跨域协同过滤算法进行对比实验，实验中迁移密码本用户侧聚类数目和项目侧聚类数目设置为*，用提取的密度较高的豆瓣数据对稀疏的豆瓣数据和稀疏的MovieLens-Latest数据进行跨域推荐实验。

图3 不同跨域推荐算法在豆瓣数据集下的MAE对比

图4 不同跨域推荐算法在MovieLens数据集下的MAE对比

实验结果表明，加入多信息的GSC-CBT比单纯改用谱聚类的SC-CBT的预测结果更优秀，且两个改进算法都比原始CBT算法更精准。值得注意的是聚类个数为40时，三个算法在MovieLens-Latest数据集中的差别并不大，且在豆瓣数据集中SC-CBT效果比CBT要差，推测在这个聚类数目时三种算法从辅助域提取的信息差别不大。总体来看，融入多信息的GSC-CBT是最佳的选择。

4 结语

本文提出了一种基于谱聚类融入多信息的跨域推荐算法，可以较好地解决协同过滤中冷启动用户和评分矩阵稀疏度较高的问题。实验结果表明，GSC-CBT算法可以对传统单域推荐无法得到较好结果的推荐问题进行跨域知识迁移，获得一个不错的预测结果，与现有算法对比准确度也有所提升。