基于融合相似度和层次聚类的冷启动推荐算法
时间：2022-11-18 19:15:04 来源：雅意学习网 本文已影响 人 
韩胜宝，伊华伟，李晓会，李 波，景 荣
1(辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001)
2(燕山大学 信息科学与工程学院，河北 秦皇岛 066044)
随着互联网以及社会化媒体的高速发展，在网络资源愈加丰富的同时，也出现了信息超载(Information Overload)[1，2]的问题.信息超载给用户在选择资源上带来了很大的困惑(比如面对电商平台五花八门的商品难以抉择、在新闻资讯平台不能及时获取真正想要的新闻信息以及在视频网站耗费大量的时间寻找合适的影片等等).搜索引擎在一定程度上能够帮助用户进行资源的选择，但未能从本质上解决信息过载的问题.在这种情况下，推荐系统(Recommendation System)应运而生，它利用数据挖掘等技术，向用户推送其可能感兴趣的信息[3-5].不仅如此，高效的推荐结果会增加用户与系统的粘合度，提升用户的忠诚度，防止用户的流失，为商家带来良好的经济效益.推荐系统的核心是推荐算法，协同过滤推荐算法是目前最流行以及最成功的推荐技术之一[6，7]，它分为基于用户的协同过滤算法和基于项目的协同过滤算法[8].基于用户的协同过滤算法利用用户对商品的评分记录(包括隐式的交互，如浏览记录、收藏的信息)寻找与目标用户相似的邻居用户，根据这些邻居用户喜欢的商品为目标用户做出推荐，其中的关键是需要大量的用户历史数据.对于新用户而言，历史数据的缺乏使得系统难以计算他和其余用户的相似性，也就不能很好地获取新用户的兴趣与需求，从而系统无法为新用户做出推荐或者推荐的准确性不高，这个问题被称作用户冷启动(User Cold Start)[9，10]问题.因为任何一个用户对产品的评价都是从无到有、从少量到众多，所以冷启动问题是推荐系统无法避免的.用户没有对任何产品评价的情况被称为纯冷启动问题，用户对少许产品评价的情况被称为非纯冷启动问题.本文主要是针对协同过滤算法中的用户非纯冷启动问题而展开研究的.
近年来，研究人员就如何缓解用户冷启动问题开展了诸多研究工作.Liu H F等人[11]提出了NHSM方法，将用户评分行为因素融入到传统的相似度计算公式中，扩展了传统的几何距离式计算方法，从而提高了推荐精确度.Ahn H J[12]提出了一种启发式度量计算相似度方法PIP，该方法综合了相似度、邻近度、影响力和受欢迎程度4种指标，在冷启动环境下能有效提高系统的推荐性能.张凯涵等人[13]提出了一种基于社区专家信息的协同过滤推荐算法，首先利用用户的社交关系将用户进行划分，然后根据相关规则确定社区专家，利用社区专家对新用户的评分记录进行填充，最后计算用户相似度，完成对目标用户的推荐.毛明松等人[14]首先对用户构建多重关系网络和计算各关系网络间的结构差异性，然后利用多重图排序模型得到目标用户的最近邻集合，进而对目标用户产生推荐.该方法能有效提高冷启动用户的推荐准确率，但图形的构建难度以及计算量会随着数据规模的增大而增大.王媛媛等人[15]首先结合用户人口统计学数据和用户评分矩阵计算用户间的相似度，然后对用户进行分层近邻传播聚类，产生目标用户的最近邻居列表，最后根据最近邻对目标用户进行推荐.Zheng X L等人[16]结合用户的全局信任关系和局部信任关系，提出一种基于信任的推荐算法，有效提升了对冷启动用户的推荐精度.Liu Y等人[17]在个性化方面利用矩阵分解求得项目的潜在特征个数以及用户间的相似度，在非个性化方面利用K-means方法对用户进行聚类，最后不断迭代更新用户评分矩阵，使得预测结果达到最优，此方法可以提升推荐精度，但计算量会随着用户量增多而增大，而且精度的提升是有限的.潘一腾等[18]利用矩阵分解和社交关系获取用户之间的隐含信任关系，然后综合利用评分相似度和隐含信任关系得到更精准的最近邻，进而提升系统的推荐精度.郭磊等人[19]利用信任关系和兴趣爱好对用户进行建模，在识别具有共同兴趣爱好的用户过程中对模型不断进行优化，使得最后的推荐效果达到最好.Viktoratos I等人[20]将基于社区的知识与关联规则挖掘相结合，采用了基于概率度量的创新评分函数，缓解了推荐系统的冷启动问题.Gupta S等人[21]利用模糊C-means聚类算法对用户的人口统计学数据进行聚类，将冷启动用户所在簇中评分最高的项目推荐给冷启动用户，有效地提升了推荐质量.
上述方法虽然在一定程度上缓解了用户冷启动问题，但仍然存在以下问题：1)在冷启动环境下，采用传统用户相似度计算方法为目标用户寻找近邻，结果不够准确或者找不到近邻；
2)一些算法的计算量过于庞大，导致算法时间复杂度增加.
本文在已有的研究工作基础上，提出一种基于融合相似度和层次聚类的冷启动推荐算法.首先，针对传统相似度寻找近邻的不足，基于对人口统计学信息、用户评分信息和项目种类信息的深入挖掘，以及对传统的用户相似度计算方法进行改进，构建一种融合相似度计算方法，克服了单一的从用户关系角度去寻找近邻的局限性.其次，针对随着用户的增多，算法计算量增大的情况，利用层次聚类算法快速获取冷启动用户的初始近邻用户集，以此来降低算法的复杂度，提升算法的运行效率.通过与其他方法进行实验对比，本文提出的方法在MAE和RMSE两个推荐精度评价指标上表现良好，有助于后续冷启动问题的研究.
本节提出基于融合相似度和层次聚类的冷启动推荐算法(Cold Start Recommendation Algorithm Based on Fusion Similarity and Hierarchical Clustering，CSRA-FH)，算法的框架如图1所示，本文所提的算法由融合相似度计算、基于层次聚类的初始近邻用户确定和为目标用户进行推荐3个部分组成.
图1 基于融合相似度和层次聚类的冷启动推荐算法框架图
3.1 融合相似度
通过对人口统计学信息、用户评分信息和项目种类信息进行深入挖掘，分别得到人口统计学相似度计算方法、兴趣偏好相似度计算方法和基于动态调整的用户评分相似度计算方法，将三者进行加权融合，得到融合相似度计算方法.
3.1.1 人口统计学相似度
冷启动用户是系统新注册的用户，对商品的评价或者浏览记录较少，而用户注册时填写的人口统计学信息包括年龄、性别、职业、收入水平、文化程度以及地理位置等.相关研究[22]表明，具有相似的人口统计学信息特征的用户在兴趣爱好上有很大的相似性，因此本文引入用户的人口统计学信息，选取年龄、性别和职业共3个维度的数据，先计算用户在各个维度的相似性，然后综合3个维度的相似性，最后提出用户在人口统计学信息属性上的相似度计算方法.
由于用户的年龄从几岁到几十岁不等，年龄差距比较大.因此，本文参考文献[23]提出的方法，利用负指数衰减函数将距离值映射到相似值，用户u和用户v之间的年龄相似性计算方法如公式(1)所示：
sima(u，v)=exp(-ηdisσ(au，av))
(1)
其中，η=3.8，σ=2[23].本文利用最大最小缩放法将用户au和av代表的用户年龄值进行相应的处理，保证相似度的值在0～1之间，具体如公式(2)所示：
(2)
其中，uai表示用户的实际年龄(i=u，v)，maxa和mina分别表示用户集中的最小年龄值和最大年龄值.
对于人口统计学中的性别和职业属性，本文将二者用同样的方式进行处理.因为两者皆为非数值型数据，所以需要将这些数据进行量化，用0和1分别表示“男”和“女”，用不同的数字代表不同的职业.基于量化后的数据，利用欧氏距离计算用户u和用户v在性别和职业属性上的相似程度，如公式(3)所示：
(3)
其中，ui和vi分别表示用户u和用户v的第i个属性特征值.从公式中可以看出，距离越大，说明用户之间在性别和职业属性上的差异就越大，从而两个用户在这两个属性上的相似度就越小；
反之亦然.因此，用户在性别和职业属性上的相似性可以用欧氏距离的倒数来表示，如公式(4)所示：
(4)
将上述获得的用户年龄相似度和性别职业相似度进行加权融合，得到用户在人口统计学上的相似度计算方法，如公式(5)所示：
dem_simu，v=ω×sima(u，v)+θ×simg，o(u，v)
(5)
其中，ω和θ分别代表公式(1)和公式(4)计算出的相似度的权重，这两个维度是相互独立，互不影响的，它们对于用户在人口统计学上的相似度的影响力应该是一样的，所以将ω和θ的值分别设置为0.5.
3.1.2 兴趣偏好相似度
每个项目对应着一个或者多个特征，统计用户对每一类项目的评价次数，就可以挖掘出用户对某种类型项目的喜好程度.以推荐系统研究中的经典数据集MovieLens为例，它包含了用户对所有电影的评价记录，每部电影至少属于一种电影类型.统计所有用户对每种类型电影的评价总次数，就可以获得用户对各种类型电影的偏好程度.基于这种思想，提出用户间的兴趣偏好相似度计算方法，具体如下所示.
该过程主要分为两步：首先基于用户评分信息以及项目的种类信息，获得所有用户的项目特征偏好矩阵M；
然后根据已获得的矩阵M，计算用户之间的兴趣偏好相似度.用户的项目特征偏好矩阵M如公式(6)所示：
(6)
其中，m表示用户的数量，n表示项目的类型个数，Smn表示用户m对项目类型n总共的评价次数，其数值越大，表示用户对这个类型产品的偏好程度越大.
根据矩阵M提出用户之间的兴趣偏好相似度计算方法，具体如公式(7)所示：
(7)
其中，train代表训练集，test代表测试集(冷启动用户集合)，ut代表训练集用户对某种类型项目的评价次数的映射值，vt代表冷启动用户对某种类型项目的评价次数的映射值.规定：如果测试集中的冷启动用户的第t种特征偏好统计数据大于或者等于1，则vt等于1，否则等于0.由于训练集中用户对某种类型项目的评价次数存在较大的差异，所以首先计算出训练集用户对所有项目每种类型的平均评价次数n，然后比较用户的第t种特征偏好统计数据St和n的大小关系，对应关系如公式(8)所示：
(8)
之所以进行这样的设置，是因为训练集中的用户评价记录较多，所以用户的兴趣偏好需要较大的特征偏好值来体现.同理，冷启动用户的评价记录偏少，较小的特征偏好值可以体现出冷启动用户的潜在兴趣偏好.
3.1.3 基于动态调整的用户评分相似度
用户对项目的评分可以体现用户之间的相似性，但是对于一些流行程度较高的项目来说，虽然大多数用户进行了评分，但是偏好并不一定相似，所以，如果两个用户共同评分项中流行项目较多，就会影响相似度的准确性.在传统的Person相似度计算中，算法对所有的项目赋予同样的计算权重，忽略了项目流行度对相似度结果的影响.所以，应该降低流行项目在相似度计算中的权重.本文基于参考文献[24]，对传统的Person相似度计算公式进行改进，得到基于动态调整的用户评分相似度计算如公式(9)所示：
(9)
上述公式考虑了项目流行度对相似度计算的影响，使得计算获得的用户相似度更具合理性.
为了克服单一的从用户关系角度去寻找近邻的局限性，综合考虑3.1.1、3.1.2和3.1.3中提出的3种相似度计算方法，将三者进行加权融合，得到融合相似度.该相似度计算综合考虑了人口统计学信息、用户评分信息和项目种类信息3个方面的因素，使得算法在冷启动环境下的预测评分更准确.具体定义如公式(10)所示：
F_simu，v=α×user_simu，v+β×dem_simu，v+γ×pre_simu，v
(10)
其中，α、β和γ分别是基于动态调整的用户评分相似度、人口统计学相似度以及兴趣偏好相似度的权重，取值的依据见4.2节.
3.2 基于层次聚类的初始近邻用户确定
本节采用层次聚类算法为冷启动用户寻找初始近邻用户，提出基于层次聚类的初始近邻用户确定算法(Initial User Neighbor Determination Algorithm Based on Hierarchical Clustering，IUND_HC).传统的协同过滤推荐算法根据用户的评分相似度来确定用户的近邻集合.在冷启动环境下，冷启动用户评分记录较少，但是其人口统计学数据是相对比较完整且较为真实的，所以本节基于人口统计学数据的内部特征，利用层次聚类算法根据特征的关联性将用户进行聚类.目的是在为冷启动用户进行推荐时，只计算冷启动用户与其所在类簇的其他用户之间的相似度，可以减少计算量，提高算法的运行效率.
层次聚类[25]算法主要分为凝聚算法和分裂算法，本文采用凝聚算法.在算法的初始状态，将每个数据样本看成一类，通过计算两两样本之间的距离，将距离最小的两个类合并成一个类，不断地重复这个过程，直到类簇的数目达到预先设置的数目.在算法的设计过程中，主要涉及两个样本之间距离的计算和两个类簇之间距离的计算.
假设两个数据样本X和Y分别表示为X=(X1，X2，X3，…，Xn)，Y=(Y1，Y2，Y3，…，Yn)，他们之间的距离用D(X，Y)表示，两个样本之间距离的计算公式如公式(11)所示：
(11)
对于两个类簇之间距离的计算，本文采用最短距离法，即将两个类簇中最近的两个点之间的距离作为类簇之间的距离，具体如公式(12)所示：
D(C1，C2)=minq1∈C1，q2∈C2，(q1，q2)
(12)
式(12)中，C1和C2表示两个不同的类簇，q1和q2表示不同类簇里面两个样本.
综上所述，算法IUND_HC的基本思想为：首先，基于人口统计学信息，利用层次聚类算法对用户进行聚类，将具有相似偏好的用户聚到同一类簇内，方便冷启动用户获取初始近邻用户，通过对比不同聚类数目下的实验结果可知，当聚类数目为3时，本文算法的推荐结果达到最优.下面给出基于层次聚类的初始近邻用户确定的具体算法描述.
算法1.基于层次聚类的初始近邻用户确定算法IUND_HC
输入：人口统计学数据矩阵Rg，类簇数目t=3；
输出：用户的聚类结果C.
Begin
1.Initialize(Rg)；
//将每个样本(用户)归为一类；
2.依据公式(11)计算每两个样本之间的距离；
3.Repeat
4. 将最近的两个类归为一类；
5. 依据公式(12)计算新生成的类簇与每个已有类簇之间的距离；
6.Untilt；
7.ReturnC={c1，c2，…，ct}；
//返回新生成的t个类簇
End
3.3 算法CSRA-FH
基于用户的推荐算法(User-based Recommendation Algorithm)是协同过滤算法中常见的一种，它的中心思想是根据目标用户的最近邻居对某个项目的评分来预测目标用户对该项目的评分.本节利用基于用户的协同过滤推荐算法模型，结合3.1节提出的融合相似度计算方法和3.2节提出的基于层次聚类的初始近邻用户确定算法，设计基于融合相似度和层次聚类的冷启动推荐算法CSRA-FH.
首先，通过对人口统计学信息、用户对项目的评分信息和项目种类信息进行深入挖掘，得到融合相似度计算方法；
然后利用层次聚类将用户分为不同的类簇，方便目标用户获得初始近邻用户集合；
再利用融合相似度计算方法对目标用户的初始近邻用户做进一步的筛选，获得最终的近邻用户集合，最后对目标用户作预测评分推荐，预测评分计算方法如公式(13)所示:
(13)
基于上述算法思想，给出用户冷启动推荐算法CSRA-FH算法描述如下：
算法2.用户冷启动推荐算法CSRA-FH
输入：用户-项目评分矩阵R，目标用户近邻数目k，用户人口统计学数据矩阵Rg，项目类型矩阵It，类簇数目t；
Begin
1.similar_users←Ø；
2.featureitem←count(R，It)；
//统计用户的项目特征偏好；
3.{c1，c2，…，ct}←IUND_HC(Rg，t)；
4.Fors=1 totdo
5. Ifu∈{c1，c2，…，ct} then
6. Forv∈{c1，c2，…，ct} andu≠vdo
7.demsimilarity←dem_simu，v(Rg)；
8.presimilarity←pre_simu，v(featureitem)；
9.usersimilarity←user_simu，v(R)；
10.F_simu，v←α×user_simu，v+β×dem_simu，v+γ×pre_simu，v；
11.similar_users←F_simu，v；
12. End For
13. End IF
14.End For
15.C1～k(u)←sort(similar_users)；
//将融合相似度从大到小排序，取前k个用户
End
4.1 数据集及评价标准
1)数据集：本文采用MovieLens 100K数据集.该数据集总共有10万条评分记录，包含943个用户以及1682部电影.用户的评分范围在1～5分，5分表示用户对某部电影非常喜欢，如果用户没有看过或者没有评价这部电影，相应的评分记为0.
本文首先在943个用户中按20%的比例抽取评分记录最少的用户作为冷启动用户，然后针对每个冷启动用户随机抽取10个项目评分，将抽出来的项目评分组成测试集，最后将冷启动用户的其余评分记录和剩余80%的用户评分记录作为训练集.
在MovieLens数据集中，除了用户评分数据，还包括用户的人口统计学信息，它包括年龄、性别、职业和邮编(表示用户的地理位置)4个属性.本文在计算用户基于人口统计学信息的相似度时，使用年龄、性别以及职业三个维度的信息.其中，用户年龄的范围是7～73岁，职业总共有21种.在量化职业信息时，因为具有相近职业的用户相似程度是比较高的.因此，首先将21种职业进行分类，然后同一个类别用统一的数值表示.本文将21种职业分为10个种类，分别用5～14来进行量化.同时对于人口统计学信息中的年龄信息，本文也将其划分为4个不同的阶段，分别用1～4进行量化.性别信息只有两种，因此用两种不同的数值分别表示即可.职业信息量化表示如表1所示：
表1 职业信息量化表
2)评价标准：评价推荐算法的推荐精度主要有平均绝对误差MAE和均方根误差RMSE这两个指标，二者的值越小，说明算法的推荐效果越好.
(14)
(15)
4.2 参数设置
在本文提出的融合相似度计算公式中，权重α、β和γ对推荐算法的性能尤为重要，因此，我们采用实验的手段对权重α、β和γ的取值进行设置.
从已经划分好的测试集中随机抽取50%的用户，将这些用户的评分记录作为验证集(剩余的用户评分记录作为4.3节实验使用的最终测试集)，采用已划分好的训练集进行参数设置的实验.首先将α、β和γ三者的取值范围均确定在0.1～0.8之间，且α+β+γ=1，然后对α、β和γ进行不同的取值，每次取值的间隔为0.1.
根据以上设计，针对算法CSRA-FH进行多次实验，算法的推荐精度(MAE)结果如表2所示.
表2 算法CSRA-FH在不同权重下的MAE值
从表2可以看出，当权重α、β和γ值分别为0.4、0.5和0.1时，算法CSRA-FH的MAE值最小，由于MAE值越小，推荐精度越高，所以我们设置α=0.4、β=0.5、γ=0.1.
4.3 对比实验结果分析
为了评价本文提出的基于融合相似度和层次聚类的冷启动推荐算法(CSRA-FH)的性能，将其与以下3种推荐算法进行了实验对比及分析，具体结果如图2和图3所示.
图2 不同邻居个数下4种算法的MAE值
图3 不同邻居个数下4种算法的RMSE值
1)UBCF：传统的基于用户的协同过滤推荐算法.
2)NPBM：文献[26]提出基于统计用户偏好的推荐算法.
3)UCKF：文献[27]提出改进基于用户聚类的推荐算法.
从图2和图3中可以看出，在邻居个数为50的时候，4种算法的MAE和RMSE值都达到各自的最小值，但是本文所提出的算法CSRA_FH的MAE和RMSE值要明显小于其他3种对比算法.相比算法UBCF、算法NPBM和算法UCKF，算法CSRA_FH在MAE值上分别降低了2.9%、2.4%和2.7%，在RMSE值上分别降低了2.6%、3.0%和2.4%.由于MAE值和RMSE值越小，算法的推荐效果越好，因此，算法CSRA-FH在冷启动环境下的推荐效果是最优的.主要原因是在非纯冷启动的情况下，算法CSRA-FH除了根据少量的用户评分记录挖掘出用户的兴趣偏好，还提出了基于人口统计学信息的相似度计算方法和基于动态调整的用户相似度计算方法，最后将三者进行融合，提高了用户相似度计算的合理性及准确性；
除此之外，在不依靠更多的数据信息之下，利用层次聚类根据人口统计学信息初步确定目标用户的近邻用户，然后根据改进后获得的融合相似度进一步确定近邻用户，使得整体的推荐效果得到优化，同时提升了算法效率.
本文提出了一种推荐算法用于解决协同过滤推荐系统中存在的用户冷启动问题.该算法首先在对用户的人口统计学信息、评分信息和项目种类信息进行深入挖掘、对传统的评分相似度计算模型加以改进的基础上，提出了融合相似度计算模型.然后利用层次聚类方法初步确定冷启动用户的近邻.最后将融合相似度融入到基于用户的推荐模型中对目标用户进行推荐.实验结果表明所提算法在一定程度上缓解了用户冷启动问题.本文的研究还存在一定的不足，如模型参数的选取采用实验的方式来确定，在后面的研究过程中，可以尝试构建一种自动确定参数的算法.
猜你喜欢 计算方法聚类评分 槽道侧推水动力计算方法研究舰船科学技术(2022年10期)2022-06-17车联网系统驾驶行为评分功能开发汽车实用技术(2022年10期)2022-06-09基于示踪气体法的车内新风量计算方法研究煤气与热力(2022年4期)2022-05-23基于数据降维与聚类的车联网数据分析应用汽车实用技术(2022年4期)2022-03-07极限的计算方法研究客联(2021年5期)2021-09-10APACHEⅡ评分在制定ICU患者护理干预措施中的应用研究中国药学药品知识仓库(2021年18期)2021-02-28基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11双周最佳阵容足球周刊(2017年27期)2018-04-16第二重要极限的几种计算方法数学学习与研究(2016年23期)2017-03-15基于密度的自适应搜索增量聚类法电子技术与软件工程(2016年23期)2017-03-06
