基于异质信息网络的模糊推荐算法*

李 娴,赵 霞,张泽华,张晨威

(1.太原理工大学信息与计算机学院,山西 晋中 030600;2.伊利诺伊大学芝加哥分校计算机科学学院,芝加哥 60607)

1 引言

推荐系统预测用户可能感兴趣的项目，是解决信息过载的有用工具[1]。近年来，推荐系统在数字化进程中扮演着越来越重要的角色，例如微博的好友推荐、淘宝的产品推荐、Netflix的电影推荐、Pandaro的音乐推荐等。

协同过滤作为推荐系统中最经典的模型之一，是研究2个对象(user和item)相似性的算法。换句话说，用户购买物品时可能会参考朋友的建议(userCF)或者考虑用户历史购买记录(itemCF)。然而，数据稀疏问题仍然是推荐系统面临的一大挑战。针对数据稀疏问题，Jamali等人[2]探索社交网络找到用户信任的邻域，通过聚合用户邻域的评级来进行推荐。Zhang等人[3]过滤项目-用户矩阵中不重要的评级，通过融合相似用户群和相似项目群预测未评级项目。Jesús等人[4]采用Jaccard相似度为与邻居用户相似的活跃用户投票。这些推荐算法在一定程度上解决了数据稀疏问题，但是用户选择某一项目的原因不仅来自于朋友关系。这种单一的关系类型，不利于挖掘用户偏好。

基于评级历史的用户之间的相似性计算在许多实际应用中是不准确的，并且应该使用诸如用户的人口统计数据之类的其他信息，因为这些数据反映了用户之间的相关性。通过融合用户的各种属性比仅根据评级历史作推荐更严格。近年来，异质信息网络HIN(Heterogeneous Information Network)为推荐系统的研究提供了一种新的思路[5]。Shi等人[6]提出异质信息网络融合多种类型的辅助信息。Hu等人[7]利用异质信息网络中的元路径表示用户偏好。在实际推荐系统中异质信息网络融合了电影的导演、演员和类型等多种对象关系类型来改善推荐性能。然而，离散的用户评分无法合理表达用户的实际情况。例如，离散的评分无法表达用户评分为3～4分时的喜好程度。为此，本文借鉴模糊集理论构建三角模糊评分模型将电影用户离散的评分模糊化，还加入了电影的演员、导演等属性信息生成元路径；在此基础上提出了一种新的相似性度量，并预测评分获得最终的推荐结果。

本文的主要贡献包括2个方面：

(1)提出了基于异质信息网络的模糊推荐系统算法HFR(Fuzzy Recommendation algoritym based on Heterogeneous information network)。该算法在异质信息网络的基础上通过一种新的相似性度量预测评分，有效地解决在数据稀疏情况下推荐任务中的模糊评分问题。

(2)本文实现了基于异质信息网络的模糊推荐HFR算法的评测平台。在不同数据集的不同稀疏度下，验证了HFR算法的可行性与有效性。

2 相关工作

2.1 异质信息网络

随着互联网数据的爆炸式增长，信息的“丰富”和“稀疏”并存，如何在海量的数据中提取有用信息变得越来越困难。异质信息网络包含多种类型的对象及对象之间的关系，它的出现为不同类型的信息建模提供了思路。从图的角度融合不同类型的对象关系和语义信息，解决了传统同质网络信息缺失的问题。相关定义[5]如下所示：

定义1异质信息网络表示为G={ν,ε}，由对象集ν和链接集ε组成。异质信息网络还与对象类型映射函数Φ：ν→A和链接映射函数Ψ:ε→R相关联。A和R表示预定义对象和链接的集合，|A|+|R|>2。

基于异质信息网络的推荐方法通常分为3个方面：(1)基于语义：Chen等人[8]通过优化PathSim全局权重，融合项目的配置文件缓解推荐系统的数据稀疏问题；Shi等人[6]提出Sem-Rec获得元路径上用户偏好的优先权重和个性化权重。(2)基于矩阵分解：Zhu等人[9]利用矩阵分解提取出源网络中的潜在因子，通过锚链接(Anchor Links)将提取的潜在因子从源网络转移到目标网络。(3)基于社会关系：Luo等人[10]提出基于社会异质关系的协同过滤推荐Hete-CF(social-based Collaborative Filtering recommendation using Heterogeneous relations)有效整合所有社会关系，包括用户-用户、项目-项目和用户-项目之间的关系，解决数据稀疏问题。Zheng等人[11]为提高用户点击率，利用用户之间的信任信息、朋友关系和其他类型的信息提高推荐质量。

这些研究者通过细微地描述对象关系，探索更加详细的语义信息。可见，基于异质信息网络的推荐正在快速发展。

2.2 模糊集

社交网络中存在的信息模糊性和不确定性带来的结果随机性直接影响用户体验，从不确定的信息中挖掘用户的实际偏好显得尤为重要。模糊集是处理不确定信息的一种形式，通过设置阈值，判断某个元素是否属于这个集合。相关定义[12,13]如下：

定义3模糊集F由论域U中的隶属函数μF(u)表示：

μF(u)：u∈U→[0,1]

(1)

定义4存在多种类型的隶属函数，例如三角模糊数f表达喜好程度：

f=(a,b,c;w)

(2)

其中，a,c分别是上下界；b是中间值；w表示用户决策的模糊权重，且0

(3)

Figure 1 Triangular fuzzy number f=(t1,t2,t3)图1 三角模糊数

模糊集中，用户的喜好程度用语言术语表达，如极高、高、低等。在现实世界中有很多问题不能以定量的形式评估，而是以模糊或者不精确的形式定性分析[14]。Wu等人[15]在传统余弦相似度的基础上引入模糊集，解决了数据稀疏问题。Kant等人[16]将用户年龄模糊化，合理表达用户属性。Jiménez等人[17]验证了基于模糊规则的分类方法的有效性。张冰等人[18]依据模糊的评价信息得到了合理的聚类结果。同时，有很多研究者将模糊集理论应用到医疗诊断、图像处理等任务中[19,20]。

3 HFR算法

3.1 问题描述

在推荐任务中以网络或图的形式对用户-项目之间的交互进行建模，根据观察到的节点以及节点之间的链接预测未知的评分。给定异质信息网络G={ν,ε}，从多种关系类型出发，对不同类型的关系进行建模，并挖掘用户的实际偏好，但忽略了用户的不确定性，会直接影响推荐结果。在原始的用户评分中，用离散的评级刻画用户的喜好程度。由于每个用户的标准不同，评分是主观的、模糊的、不确定的。由此，本文提出基于异质信息网络的模糊推荐算法。

3.2 异质信息网络的模糊推荐算法

HFR算法的核心是提出一种新的相似性度量，结合基于异质信息网络的用户之间相似度与根据模糊评分计算出的用户相似度形成最终相似度。根据用户属性和评分更准确地反映用户之间的相关性。每个相似度(模糊相似度/基于元路径相似度)都将根据相似用户数自动计算权重。一旦计算出最终的相似度，根据用户的邻居预测最终的评分。具体算法步骤如下所示：

算法1基于异质信息网络的模糊推荐算法

输入：评分矩阵r∈M,元路径P。

输出：预测评分矩阵R′。

步骤2MS(ua,ub)；//计算基于元路径的相似性

for eachi//对于每一个项目i

FS(ua,ub)；//计算模糊相似度

ifFS(ua,ub)≤θ：

k=k+1；

end for

步骤3

SIM(ua,ub)=α×MS(ua,ub)+β×FS(ua,ub)/*基于元路径相似性的权重为α,基于模糊相似度的权重为β,得到最终相似度*/

步骤4

3.2.1 相似性度量

现实网络包含多种类型的对象和交互信息，将对象及其关系建模为异质信息网络。利用元路径表示不同对象之间丰富的语义信息，本文设计UM*MU和UMU格式的元路径，表示用户选择电影可能是因为喜欢该部电影的导演(D)、演员(C)、类型(T)等。如图2所示。

Figure 2 An example of heterogeneous information network图2 异质信息网络示例

在元路径刻画用户偏好的基础上，采用Sun等人[21]提出的PathSim，计算基于元路径的相似性。给定1个对称的元路径，用户ua和ub基于元路径的相似性为：

MS(ua,ub)=(2×|{pua→ub:pua→ub∈P}|)/

(|{pua→ua:pua→ua∈P}|+|{pub→ub:pub→ub∈P}|)

(4)

其中，pua→ub表示用户ua到ub的路径，pua→ua表示用户ua到ua的路径，pub→ub表示用户ub到ub的路径。对象之间的连通性由它们之间的路径实例数决定。因此，MS(ua,ub)的值在0～1，越接近1，则ua和ub越相似。

在异质信息网络中，用户的离散评分使得用户喜好具有片面性，引入模糊集使用户评分模糊化，可更加合理地表达用户偏好。

以数据集MovieLens评分等级(1～5)为例，含有用户u∈U，项目i∈I。根据定义2构建三角模糊评分模型，如图3所示。其中，VL(非常低)、L(低)、M(中)、H(高)、VH(非常高)表示用户的喜好程度，z表示用户对项目的满意度。

Figure 3 Triangular fuzzy rating model图3 三角模糊评分模型

每1个喜好程度对应的评分等级模糊数如表1所示。

Table 1 Preference degree and its semantics表1 喜好程度及其语义

三角模型评分处理后，离散的电影评级通过隶属函数模糊化。由此，得到隶属函数：

μVL(z)=(0.25-z)/0.25,0≤z≤0.25

(5)

μVH(z)=(z-0.75)/0.25,0.75≤z≤1.0

选取用户ua和ub共同评分的项目i∈Iij的模糊权重[22]为：

(6)

(7)

(8)

3.2.2 预测评分

将基于元路径的相似性和模糊相似性赋予不同的权重，获得最终的相似性：

SIM(ua,ub)=α×MS(ua,ub)+β×FS(ua,ub)

(9)

其中，α和β满足以下条件：

α+β=1

(10)

(11)

其中，α、β分别表示基于元路径相似度MS(ua,ub)的权重和模糊相似度FS(ua,ub)的权重，k表示用户邻居数。根据这种新的相似性度量预测最终的评分：

(12)

综上所述，考虑多种关系类型以及用户评分的不确定性，融合基于元路径相似性和模糊相似性，预测最终评分。

4 实验设计与分析

4.1 测试数据集

为了验证HFR算法的性能，选择3个真实的数据集进行实验。MovieLens数据集包含6 040名用户对3 706部电影的1 000 209个评分(1～5分)。Douban Movie数据集包含13 367名用户对12 677部电影的1 068 178个评分(1～5分)。2个电影数据集都含有电影的类型(T)、导演(D)、演员(C)等信息。Douban Book数据集包含13 024名用户对22 347本书的792 026个评分(1～5分)。图书数据集中含有书的作者(O)、出版社(Q)、出版年份(Y)等信息，数据集信息如表2所示。

Table 2 MovieLens,Douban Movie and Douban Book datadets表2 MovieLens、Douban Movie 和 Douban Book数据集

在HFR算法中，定位用户对电影的偏好是首要问题，需要通过元路径计算用户相似性。为此，选择包含用户实体和项目属性的元路径。MovieLens和Douban Movie 2个数据集都涉及到电影推荐，Douban Book是图书数据集。如表2中所示，UMU表示用户看了同一部电影；UMTMU表示用户根据电影类型进行选择；UMCMU表示用户因为喜欢某个演员而选择电影；UMDMU表示用户因为喜欢某个导演而选择电影。UBU表示用户看了同一本书；UBOBU表示用户因为喜欢某个作者而选择图书；UBQBU表示用户根据出版社选择图书；UBYBU表示用户根据出版年份选择图书。实验将数据的80%作为训练集，20%作为测试集。为了减少随机分割数据带来的误差，实验结果取运行3次的平均值。

4.2 实验及评测指标

为了验证HFR算法的性能，与以下4个算法进行比较：

User-CF：实验采用推荐系统算法库surprise实现。基于用户的协同过滤，采用余弦相似度发现具有共同兴趣的用户。

Fuzzy-CF[16]：将用户年龄模糊化，通过协同过滤引入模糊相似性度量预测评分。

Fuzzy-UBCF[15]：引入模糊集，扩展余弦相似度，提高推荐质量。

Hete-CF[10]：通过融合多种关系类型，缓解推荐系统的数据稀疏问题。

实验采用的评测指标是均方根误差(RMSE)及平均绝对误差(MAE)，其计算公式如下所示：

(13)

(14)

其中，Γ是测试集。

为了验证HFR算法的性能，与User-CF、Fuzzy-CF、Fuzzy-UBCF和Hete-CF 4种算法在MovieLens、Douban Movie和Douban Book 3个数据集的不同稀疏度下进行比较，并分析用户邻居数k对推荐结果的影响。

4.3 与其他推荐算法比较

HFR算法与上述4种算法的RMSE、MAE比较结果如表3所示。可以看出，与其他推荐算法相比，HFR算法具有较好的推荐效果。因为User-CF算法只考虑用户-项目的评分，在实际推荐任务中用户与项目的交互往往很稀疏。Fuzzy-CF算法将用户年龄模糊化，未考虑其他因素。Fuzzy-UBCF算法基于单一的朋友关系，引入模糊相似性。Hete-CF算法考虑了多种社会关系类型，如用户-项目、用户-用户和项目-项目等关系，但是忽略了用户评分的不确定性。而HFR算法考虑了多种关系类型并且将用户评分模糊化，使得推荐结果更优。

在MovieLens、Douban Movie和Douban Book数据集原有稀疏度的基础上删除一部分数据，得到不同稀疏度下的RMSE和MAE。随着数据稀疏度的不断增加，User-CF算法准确度下降得最快；Fuzzy-CF、Fuzzy-UBCF和Hete-CF较为平缓；由此看来，HFR算法在高稀疏度的数据集中仍然有较好的表现。

4.4 参数敏感性分析

参数的变化影响着实验结果的好坏。本节在MovieLens、Douban Movie和Douban Book数据集上分析邻居个数k对Hete-CF算法的RMSE和MAE的的影响。

邻居个数k直接影响着推荐结果，如图4和图5所示，分别取邻居个数为10，20，…，80，观察RMSE和MAE的变化。可以看出，当邻居个数为40时，HFR算法在MovieLens数据集上的效果最好；当邻居个数为50时，HFR算法在Douban Movie数据集上的效果最好；当邻居个数为70时，HFR算法在Douban Book数据集上的效果最好。Douban Movie数据集比MovieLens数据集更加稀疏，并且用户数较多，因此获得最优结果时，Douban Movie需要的邻居个数较多。整体来看，HFR算法含有丰富的用户信息，所以在稀疏数据集上有较少的邻居数。

Table 3 Experimental results comparison of HFR algorithm表3 HFR算法实验结果比较

Figure 4 Effect of k on RMSE图4 k对RMSE的影响

Figure 5 Effect of k on MAE图5 k对MAE的影响

综上所述，HFR算法的优势在于通过多种关系挖掘用户喜好，同时构建三角模糊评分模型，将用户离散的评分模糊化，使得其所携带的信息更加充分，解决用户评分的模糊性。因此，在稀疏的数据集上HFR算法比传统的推荐算法效果更优。

5 结束语

本文提出了一种基于异质信息网络的模糊推荐系统算法，针对传统协同过滤推荐算法存在的数据稀疏问题，融合用户的多种关系类型，并且考虑用户评分的模糊性，提出了一种新的相似性度量算法，解决了推荐任务中信息稀疏的问题。HFR算法在一定程度上能够缓解数据稀疏问题；同时，与其他推荐系统算法比较，HFR算法具有较好的性能。