2019, Vol. 40
随着信息技术和互联网技术的不断发展, 人类逐渐从信息匮乏的时代走入了信息过载的时代, 并且信息过载问题越来越严重.推荐系统就是解决这一矛盾的重要工具[1].目前, 推荐系统已经广泛应用于各大电子商务网站, 成为其中重要的组成部分, 为用户和商家带来了极大便利, 并越来越受欢迎[2-3].协同过滤是推荐系统中应用最广泛的推荐算法, 包括基于用户的协同过滤和基于商品的协同过滤[4-7].通过计算用户的历史评分相似度[8], 得到与目标用户有相同喜好的用户, 然后将相似用户过去喜欢的物品推荐给目标用户.虽然协同过滤算法被广泛应用, 但是目前协同过滤算法面临着数据稀疏和冷启动的问题[9-10], 当有新的用户加入时, 由于新用户没有历史评分记录, 此时协同过滤技术表现得不是很理想.
此外, 用户购买商品的情形各种各样, 例如个人的喜好、朋友推荐[11]、时尚买手的推荐等.因此, 只依赖用户的历史评分进行协同过滤推荐是远远不够的.潘新等[12]分析了对于流行度比较高的商品, 用户的从众心理比较大, 新用户更容易依赖系统推荐的流行商品.为解决用户冷启动问题, 将HITS模型应用到推荐系统中[13].此外挖掘数据的隐含信息等也是改善推荐系统比较常用的方法[14].
本文通过引入用户之间的社交关系和用户对商品的偏好兴趣度来改进原始的HITS算法.此外, 由于许多传统的推荐算法只依赖历史数据并没有考虑时间问题, 在现实生活中无论是时尚买手推荐的还是流行商品都是具有时效性的, 所以在HITS模型中引入时间维度, 通过引入时间函数来惩罚陈旧过时的商品.最后, 将改进的HITS算法和协同过滤算法相结合对用户进行推荐.这样对于新用户, 即使没有历史数据, 也可以根据改进的HITS算法提取流行商品进行推荐, 可以有效解决用户冷启动问题.同时, 根据用户的评分将用户分为活跃用户和非活跃用户, 计算用户之间相似度时只需计算用户与活跃用户之间的相似度, 即基于活跃用户进行协同过滤推荐.这样, 不仅降低了计算的复杂度, 也在一定程度上缓解数据稀疏所带来的影响.
1 传统的推荐算法介绍与本文直接相关的两个经典算法:基于用户的协同过滤算法(UCF) [5]和HITS算法[15].
1.1 基于用户的协同过滤算法假设推荐系统中有m个用户, n个商品, 用户集合、商品集合及用户对商品的评分矩阵分别为U={u1, u2, …, um}, I={i1, i2, …, in}和R=[rui]m×n.其中rui代表用户u对商品i的评分, 评分的取值为1~5的整数.评分矩阵中的缺失项代表用户未对商品评分, 暂时用零填充.评分矩阵中隐含了用户对商品的潜在偏好信息及用户之间的潜在信任关系, 是推荐算法的主要数据.
传统的基于用户的协同过滤算法首先要获取用户的历史偏好, 通常由评分矩阵给出.当给目标用户u做推荐时, 只要找出和u有相似行为的用户, 把他们购买的商品推荐给目标用户u.基于用户的协同过滤算法包括两个步骤.
步骤1 确定用户的近邻用户.计算目标用户u和其他用户间的相似度, 将相似度大的前k个用户确定为目标用户u的近邻用户, 记为N(u).
采用文献[5]中的修正余弦相似度公式计算用户u和v之间的相似度sim(u, v), 即
|
(1) |
式中:Iuv是用户u和v同时评过分的商品集合; ri是所有用户对商品i的平均评分.
步骤2 计算目标用户对项目的预测评分值.预测评分式为
|
(2) |
式中: 
根据式(2), 对目标用户未评分的项目进行预测评分, 将评分值高的前k个项目推荐给目标用户.
1.2 HITS算法HITS算法是网页搜索的经典算法之一.它通过分析页面之间的超链接, 找出页面集合中的authority页面和hub页面.authority页面是与查询主题最为相关并具有高质量、权威性的网页, 而hub页面是包含指向查询主题最为重要的站点链接.
构造一个有向图G=(V1, V2, E), 表示网页的链接结构.其中:V1是hub网页顶点构成的集合；V2是authority网页顶点构成的集合，若V1和V2中的顶点之间存在链接关系则连边；E是所有边构成的集合.
对于V1中的任一顶点v, 它的hub值h(v)是v所指向的authority页面的authority值之和, 对于V2中的任一顶点u的authority值a(u)是所有u指向的hub网页的hub值之和.计算authority值和hub值的具体步骤如下.
步骤1 初始化:
对所有的v∈V1, u∈V2, h(v)=a(u)=1.
步骤2 求a(u)和h(v)的值:
|
(3) |
|
(4) |
步骤3 对a(u)和h(v)进行标准化:
|
(5) |
|
(6) |
步骤4 重复执行步骤2和步骤3, 直到达到指定迭代次数或a(u)和h(v)收敛.这里a(u)和h(v)收敛是指:对于给定的ε>0, 有
|
(7) |
式中:at和ht分别为迭代t次后的authority值和hub值.
步骤5 返回authority值和hub值.
HITS算法中authority和hub的概念引起了一些学者的注意, 并且已将HITS算法应用到位置社交网络中, 在位置社交网络中通过HITS算法提取受欢迎的地点推荐给用户[13].由于位置社交网络只有签到数据, 没有评分数据, 改进的HITS算法不能直接应用到商品推荐中.本文在文献[13]的基础上, 针对商品推荐问题及HITS算法存在的问题对其进行改进, 然后将改进的算法应用到推荐系统中.
2 改进的HITS算法:Timed-HITS在传统的HITS算法中, 任一个网页的authority值和hub值, 只是单纯考虑从该网页链出或链入该网页的网页数量, 并未考虑其他网页对该网页影响程度的大小.然而在实际情况下, 与该主题最为相关的、优质的网页对其影响更重要.文献[13]中的HITS算法没有考虑用户对景点的偏好程度对景点推荐的影响，也没有考虑时效性, 导致一些时间久远的景点, 由于链接次数多而被作为流行的景点.针对HITS算法的这些问题, 对其进行改进.
用hub值和authority值分别代表推荐系统中时尚买手和流行商品, 一个商品的authority值由购买过该商品的所有用户的hub值决定.但是, 这些用户对该商品的喜好程度是不同的, 那些差评用户的hub值的权重应该较小, 评分较高的用户的hub值的权重应该较大.在推荐系统中, 信任关系也在影响着用户的行为, 用户信任的“朋友”购买的商品, 该用户也可能会购买, 这样一个用户的hub值, 不仅由他所购买商品的authority值决定, 还与他的“信任好友”的hub值有关.此外, 对于推荐流行产品, 它的时效性很重要.因为在实际生活中当前流行的商品一直在随时间推移而不断更换, 推荐系统环境实际上是动态的, 它处在持续的变化中, 过去流行的商品在当前和未来未必受欢迎.综合以上分析, 本文把信任关系、兴趣偏好程度及时间因素加入到原始的HITS模型中.
本文改进的HITS算法仅应用在活跃用户上, 来提取“专家”用户和流行商品, 这样就可以避免因新用户的加入而造成HITS算法结构不稳定的问题.同时, 降低了整体算法的时间复杂度, 提高算法的效率.
2.1 信任关系通常的数据集并没有直接提供真实的用户间信任关系数据.从用户的行为角度考虑, 认为购买相同商品越多的用户, 兴趣越可能相同, 越容易成为朋友, 他们彼此之间的推荐越值得信任.信任关系大小定义为两个用户共同评分的商品数.设Iu和Iv分别表示用户u和用户v评过分的商品集合, 则用户u和v间信任度大小为
|
(8) |
信任度矩阵T=[t(u, v)]m×m.
2.2 时间函数推荐系统环境是动态的, 它处在持续的变化中.考虑流行商品的时效性, 在HITS模型基础上增加了一个时间维度, 引入一个时间函数f(t)(0 < f(t)≤1)来惩罚陈旧的商品.这样就能突出用户最新兴趣的权重, 降低了先前兴趣的权重, 从而能更准确地推荐.根据“牛顿冷却公式”, 给出时间函数:
|
(9) |
式中:δ是调节惩罚力度的参数, 通过实验确定; tmax是数据集中的最大时刻值, 代表最近时刻, 是衡量商品陈旧的一个标准; tmax-t是距离最近时刻的时间间隔, 间隔越小, 说明商品越新, 反之代表商品越陈旧.
2.3 偏好兴趣度估计兴趣度矩阵F=[f(u, i)]m×n中的f(u, i)最初定义为
|
(10) |
这样定义的兴趣度只能反映用户对商品是否喜欢, 不能反映用户对商品的偏好程度.在文献[12]中定义了一个随着评分递增而递增的函数, 用来计算用户对商品的偏好兴趣度.该函数只给出了已评分用户对不同商品的偏好兴趣度, 但是对于没有评分的项, 偏好兴趣度的值都是一样的.事实上, 用户对没有评分的商品的偏好程度未必都是一样的.对于未评分的商品存在以下几种情况:可能是没注意到该商品; 可能是商品价格较高; 可能是时间上的冲突; 也可能是不喜欢等多种可能.鉴于存在这些情况, 对偏好兴趣度矩阵进行改进, 对于评分为零的商品也有不同的偏好兴趣度.本文基于逻辑回归的思想估计偏好程度, 给出兴趣度矩阵.
首先, 兴趣度矩阵中0和1本身体现了用户对物品的喜欢和不喜欢信息.把评分0和1看成用户对物品偏好的两个维度, 估计出用户对项目偏好在1这个维度上的可能性有多大, 利用逻辑回归的思想估计用户喜欢一个商品的概率大小, 作为偏好兴趣度的大小.逻辑回归函数为
|
(11) |
设训练集为[Zm×n, Fm×n], 利用矩阵分解方法[16]得, Zm×n=Pm×kQk×n, 其中Pm×k和Qk×n分别表示m个用户的隐因子特征向量构成的矩阵和n个商品的隐因子特征向量构成的矩阵.令pu表示用户u的隐因子特征向量, qi表示商品i的隐因子特征向量.由逻辑回归模型得兴趣度矩阵:
|
(12) |
将每个样本代入式(11), 有
|
(13) |
最小化如下似然函数:
|
(14) |
利用随机梯度下降算法求得pu和qi, pu和qi的更新法则为
|
(15) |
算法如下:
输入:兴趣度矩阵F, 学习率η, 迭代次数k.
输出:偏好兴趣度矩阵Wui.
步骤1 随机初始化pu和qi.
步骤2 对于每个样本(u, i)∈(U, I), 利用式(15)更新pu和qi.
步骤3 当达到指定迭代次数k, 停止迭代.
步骤4 求得pu和qi, 将每对pu和qi代回逻辑函数, 即得到用户u对商品i的偏好兴趣度w(u, i), 所有偏好兴趣度w(u, i)构成偏好兴趣度矩阵Wui.
2.4 用户商品网络图一个推荐系统可以用一个赋权的无向图G(U, I, E, W)来表示, 其中U={u1, u2, …, um}代表所有用户构成的节点集合, I={i1, i2, …, in}代表所有的商品构成的节点集合.E为边集合, 由Eu和Eui两部分组成, Eu表示用户间的边集合, 代表用户间的信任关系, 若两个用户ui和uj对应的信任度值t(i, j)>0, 那么用户ui和uj之间存在连边; Eui表示用户和商品之间的连边, 代表用户对商品的购买行为, 如果用户对商品评过分, 用户和商品之间连边.W表示权值矩阵, 与Eu和Eui对应的权值矩阵分别记为Wu和Wui，即Wu表示用户和用户之间边的权值矩阵，Wu=T=(t(ui, uj))m×m；Wui表示用户和商品之间边的权值矩阵，Wui=(w(uk, ij))m×n.
2.5 Timed-HITS模型引入用户间的信任关系、用户对商品的偏好兴趣度及时间函数对原始的HITS算法进行改进.将改进后的HITS算法称为Timed-HITS算法.Timed-HITS算法的authority值和hub值的更新公式分别为
|
(16) |
|
(17) |
式中:β是参数, 通过实验确定; f(tij)代表商品ij对应的时间函数的值; f(tuk)代表用户uk对应的时间函数的值.将式(16), (17)应用到基本HITS算法中, 通过迭代过程得到流行商品和“专家”用户.
3 混合推荐算法:Timed-HCF 3.1 活跃用户对于每个用户ui, 定义其活跃值pos(ui)为用户ui评分向量中非零元素所占的比例.对于pos(ui)大于评分稀疏度λ的用户ui定义为活跃用户, 活跃用户的集合为
|
(18) |
式中, λ值根据具体数据集而定.
由所有的活跃用户的评分向量构成的矩阵称为密集子矩阵.后面的算法在密集子矩阵上提取“专家”和“流行商品”, 这样可以提高算法的效率.同时可以缓解推荐算法面临的数据稀疏性的问题.
3.2 Timed-HCF推荐算法下面给出基于Timed-HITS与协同过滤的混合推荐算法(记为Timed-HCF).
为解决用户冷启动问题, 本文将用户分为活跃用户和非活跃用户两部分分别进行推荐.对活跃用户基于Timed-HITS与协同过滤的混合推荐算法Timed-HCF进行推荐.应用改进的Timed-HITS算法获取专家用户和流行商品.将Timed-HITS算法得到的“专家”对商品评分的均值和协同过滤算法预测的评分加权, 作为用户对商品的预测值.为更准确描述用户间的相似性, 在协同过滤算法中引入信任度.为降低算法的复杂度, 本文改进的Timed-HITS算法和协同过滤算法中寻找近邻集合的过程均在密集子矩阵上进行.
对于非活跃用户, 考虑到非活跃用户的历史评分信息很少, 并且很容易依赖推荐系统推荐的流行商品, 本文通过Timed-HITS算法提取的流行商品对用户进行推荐.下面分别给出针对活跃用户和非活跃用户的预测公式.
针对活跃用户:
|
(19) |
|
(20) |
式中:rcf(u, i)代表通过协同过滤算法求得的用户u对商品i的预测值; ru代表用户的平均评分; t(u, v)代表用户之间的信任关系; rhub(i)代表“专家”对商品i的平均评分; rthcf(u, i)代表利用Timed-HCF算法得到的用户u对商品i的预测值; α(0 < α < 1)为权重因子, 权重参数α通过交叉验证得到.
针对非活跃用户:将利用Timed-HITS算法得到的流行商品推荐给非活跃用户.
Timed-HCF算法如下:
输入:评分矩阵R, 信任矩阵T.
输出:用户u对商品i的评分rthcf(u, i).
步骤1 将用户分为活跃用户和非活跃用户.
步骤2 通过Timed-HITS算法得到流行商品集Nathority和“专家”用户集合Nhub.
步骤3 计算“专家”用户对商品i的平均评分rhub(i):
|
(21) |
其中, Nhub表示专家用户集合.
步骤4 利用式(19)预测用户u对商品i的评分rcf(u, i).
步骤5 对于活跃用户u, 利用式(20)预测用户u对商品i的评分rthcf(u, i).
步骤6 对于非活跃用户, 将流行商品推荐给非活跃用户.
4 实验分析 4.1 数据集在Movielens数据集中100 K的部分对本文所提出的Timed-HCF算法进行实验.该数据集记录了943位用户对1 682部电影的100 000条评分数据, 数据集中的所有评分值是1~5的整数(1表示“很不喜欢”, 5表示“很喜欢”).实验在Movielens数据集上进行, 采用五折交叉验证的方式进行测试.表 1是MovieLens-100 K数据集的统计特性.
|
表 1 MovieLens-100K数据集的统计特性 Table 1 Characteristics of MovieLens-100 K databases |
为了评估本文算法的性能, 选择两个常用的精确度指标, 平均绝对误差(mean absolute error, MAE)和均方根误差(root mean squared error, RMSE).对于测试集中的一个用户u和物品i, rui是用户u对商品i的实际评分, 
|
(22) |
|
(23) |
MAE和RMSE值越低, 算法预测的准确度越高.
4.3 实验结果与分析将本文算法和基于用户的协同过滤算法进行预测精度的比较.为了说明本文最终得到的Timed-HCF算法的有效性, 根据算法的改进过程, 实验中作了4个算法的比较.首先在基于用户的协同过滤算法(UFC)的基础上引入信任矩阵T(算法记为TUFC), 再结合改进的HITS算法(算法记为HCF), 最后引入时间因素得Timed-HITS算法(记为Timed-HCF).所提到的算法均采用MAE和RMSE指标来评估预测准确度.
算法中的参数调节惩罚力度的系数δ、综合权重因子α和β, 通过交叉验证法得到.对于每种模型, 选用的邻居大小k均等于20, 参数δ=5, β=0.95, α=0.46.表 2给出了逐步改进的各推荐算法的误差.
|
|
表 2 改进算法的误差比较 Table 2 Errors comparison of improved algorithm |
由表 2可知, 本文提出的Timed-HCF算法相比UCF算法的MAE和RMSE值分别降低了17 %和13 %, 改进的过程中, 4个推荐算法的MAE值和RMSE值逐渐降低, 并且本文的Timed-HCF算法表现更好.
Timed-HCF算法和UCF算法的RMSE和MAE值随k值变化如图 1, 2所示.
|
图 1 MAE随k的变化 Fig.1 Changes of MAE with k |
|
图 2 RMSE随k的变化 Fig.2 Changes of RMSE with k |
图 1和图 2表明, 本文提出的Timed-HCF算法的MAE和RMSE值均低于UCF算法的.
5 结论1) 利用逻辑回归函数和矩阵分解改进了兴趣度矩阵, 使评分为零的情况也能估计出兴趣度, 更准确地反映了用户的兴趣, 同时缓解了数据的稀疏性问题.
2) 对HITS算法进行了改进, 使其更符合实际情况并应用到商品推荐中.
3) 将改进的HITS算法与协同过滤算法结合得到一个混合推荐算法.算法不仅缓解了数据稀疏性和用户冷启动问题, 同时提高了推荐精度, 降低了推荐的时间复杂度, 是一个有效的推荐算法.
| [1] |
Lu L, Medo M, Yeung C H, et al.
Recommender system[J]. Physics Reports, 2012, 519(1): 1–49.
DOI:10.1016/j.physrep.2012.02.006 |
| [2] |
Wang X, Wang Y.Improving content-based and hybrid music recommendation using deep learning[C]//Proceedings of the ACM International Conference on Multimedia.Orlando, 2014: 627-636.
https://www.researchgate.net/publication/297689918_Improving_Content-based_and_Hybrid_Music_Recommendation_using_Deep_Learning |
| [3] |
Wang C, Blei D M.Collaborative topic modeling for recommending scientific articles[C]// Proceedings of the 17th ACM International Conference on Knowledge Discovery and Data Mining.Sab Diego, 2001: 448-456.
https://www.researchgate.net/publication/221654332_Collaborative_topic_modeling_for_recommending_scientific_articles |
| [4] |
Adomavicius G, Tuzhilin A.
Towards the next generation of recommend systems:a survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 734–749.
DOI:10.1109/TKDE.2005.99 |
| [5] |
Choi K, Suh Y.
A new similarity function for selecting neighbors for each target item in collaborative filtering[J]. Knowledge-Based Systems, 2013, 37(1): 146–153.
|
| [6] |
APirasteh P, Jung J J, Hwang D.
Item-based collaborative filtering with attribute correlation:a case study on movie recommendation[M]. Berlin: Springer-Verlag, 2014: 245-252.
|
| [7] |
赵晓煜, 黄小原, 曹忠鹏, 等.
基于顾客交易数据的协同过滤推荐方法[J]. 东北大学学报(自然科学版), 2009, 30(12): 1792–1795.
( Zhao Xiao-Yu, Huang Xiao-Yuan, Cao Zhong-Peng, et al. Improved collaborative filtering recommendation based on customers′ transaction data[J]. Journal of Northeastern University(Natural Science), 2009, 30(12): 1792–1795. ) |
| [8] |
Sarwar B, Karypis G, Konstan J, et al.Item-based collaborative filtering recommendation algorithms[C]// International Conference on World Wide Web.Hong Kong, 2001: 285-295.
https://www.researchgate.net/publication/2369002_Item-based_Collaborative_Filtering_Recommendation_Algorithms |
| [9] |
Goldberg D, Nichols D, Oki B M, et al.
Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM, 1992, 35(12): 61–70.
DOI:10.1145/138859.138867 |
| [10] |
Liu L M, Zhang P X, Lin L, et al.
Research of data sparsity based on collaborative filtering algorithm[J]. Applied Mechanics and Materials, 2014, 462(463): 856–860.
|
| [11] |
潘一腾, 何发智, 于海平.
一种基于信任关系隐含相似度的社会化推荐算法[J]. 计算机学报, 2016, 39(175): 1–19.
( Pan Yi-teng, He Fa-zhi, Yu Hai-ping. Social recommendation algorithm using implicit similarity in trust[J]. Chinese Journal of Computers, 2016, 39(175): 1–19. ) |
| [12] |
潘新, 邓贵仕, 刘建国.
用户兴趣对个性化推荐的影响[J]. 控制工程, 2010, 17(1): 59–62.
( Pan Xin, Deng Gui-shi, Liu Jian-guo. Effects of user tastes on personalized recommendation[J]. Control Engineering of China, 2010, 17(1): 59–62. DOI:10.3969/j.issn.1671-7848.2010.01.016 ) |
| [13] |
Long X, Joshi J.A HITS-based POI recommendation algorithm for location-based social networks[C]// Proceedings of the ACM International Conference on Advances in Social Networks Analysis and Mining.Niagara Falls, 2013: 642-647.
https://www.researchgate.net/publication/259029795_A_HITS-based_POI_Recommendation_Algorithm_in_Location-Based_Social_Networks |
| [14] |
Hu Y, Koren Y, Volinsky C.Collaborative filtering for implicit feedback datasets[C]//IEEE International Conference on Data Mining.Pisa, 2008: 263-272.
https://www.researchgate.net/publication/220765111_Collaborative_Filtering_for_Implicit_Feedback_Datasets |
| [15] |
喻金平, 朱桂祥, 梅宏标.
基于Web链接分析的HITS算法研究与改进[J]. 计算机工程与应用, 2013, 49(21): 42–45.
( Yu Jing-ping, Zhu Gui-Xiang, Mei Hong-Biao. Research and improvement of HITS algorithm based on Web link analysis[J]. Computer Engineering and Applications, 2013, 49(21): 42–45. DOI:10.3778/j.issn.1002-8331.1304-0301 ) |
| [16] |
孟迪.基于隐因子的逻辑回归推荐模型研究[D].汕头: 汕头大学, 2015.
( Meng Di.A research of recommendation model using logistic regression based on latent factors[D].Shantou: Shantou University, 2015. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=D706688 ) |