文章快速检索     高级检索
  浙江大学学报(工学版)  2017, Vol. 51 Issue (2): 408-415  DOI:10.3785/j.issn.1008-973X.2017.02.025
0

引用本文 [复制中英文]

张亚楠, 陈德运, 王莹洁, 刘宇鹏. 基于增量图形模式匹配的动态冷启动推荐方法[J]. 浙江大学学报(工学版), 2017, 51(2): 408-415.
dx.doi.org/10.3785/j.issn.1008-973X.2017.02.025
[复制中文]
ZHANG Ya-nan, CHEN De-yun, WANG Ying-jie, LIU Yu-peng. Incremental graph pattern matching based dynamic recommendation method for cold-start user[J]. Journal of Zhejiang University(Engineering Science), 2017, 51(2): 408-415.
dx.doi.org/10.3785/j.issn.1008-973X.2017.02.025
[复制英文]

基金项目

国家自然科学基金青年基金资助项目(61300115,61502410)

作者简介

张亚楠(1981—), 男, 讲师, 博士, 从事社交网络推荐等研究.
orcid.org/0000-0002-0633-826X.
E-mail: ynzhang_1981@163.com

文章历史

收稿日期:2016-04-30
基于增量图形模式匹配的动态冷启动推荐方法
张亚楠1,2 , 陈德运3 , 王莹洁4 , 刘宇鹏2     
1. 哈尔滨理工大学 计算机科学与技术博士后科研流动站, 哈尔滨 150080;
2. 哈尔滨理工大学 软件学院, 哈尔滨 150040;
3. 哈尔滨理工大学 计算机科学与技术学院;
4. 烟台大学 计算机与控制工程学院, 烟台264000
摘要: 针对忽视用户的社交关系变化可能得到不准确的推荐结果这一问题, 为冷启动用户基于社交网络拓扑结构增量更新相似用户, 并基于更新的相似用户给出准确的推荐.用户社交关系是动态变化的, 然而现有基于社交网络的冷启动推荐却没有充分考虑社交关系的变更对推荐结果的影响.为了给冷启动用户实时准确的推荐, 提出基于增量图形模式匹配的动态冷启动推荐方法(IGPMDCR), 增量地更新冷启动用户的相似用户, 为冷启动用户给出实时准确的推荐结果.在真实社交网站的数据集的实验结果表明, IGPMDCR可以在用户间社交关系变更的情况下, 为冷启动用户给出实时准确的推荐结果.
关键词: 冷启动推荐    社交网络    增量图形模式匹配    社交网络拓扑结构    
Incremental graph pattern matching based dynamic recommendation method for cold-start user
ZHANG Ya-nan1,2 , CHEN De-yun3 , WANG Ying-jie4 , LIU Yu-peng2     
1. Post-doctoral Research Station of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China;
2. Software school, Harbin University of Science and Technology, Harbin 150040, China;
3. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China;
4. School of computer and control engineering, YanTai University, YanTai 264000, China
Abstract: Since ignoring the change of user's social relationships would lead to inaccurate recommendations, similar users for cold start users were updated based on social network topology incrementally, and accurate recommendations were provided based on updated similar users. User social relationships might be dynamically changed, however, the existing social network based cold-start recommendation methods did not fully consider the impact caused by the change of social relationships on recommendations as time pass by. In order to give accurate and timely in manner recommendations for cold start users, an incremental graph pattern matching based dynamic cold-start recommendation method (IGPMDCR) was proposed, which could update similar users for cold-start user incrementally, and give accurate and timely in manner recommendations for cold-start user. Experimental results on the real social network websites datasets show that IGPMDCR can give cold-start user accurately and timely in manner recommendations when user's social relationships are changing.
Key words: cold-start recommendation    social network    incremental graph pattern matching    topology of social network    

冷启动用户的历史行为信息稀少, 因此对冷启动推荐的研究一直围绕着挖掘、扩充冷启动用户的信息以及为冷启动用户发现相似用户[1-2].国内外学者对冷启动推荐的研究, 主要可以分为基于规则的推荐, 基于内容的推荐, 基于协同过滤的推荐, 基于社交网络的推荐.1) 基于规则的推荐如基于用户消费方式变化规律构建推荐规则, 评估候选项目对规则的投影, 并给出推荐[3].通过抽取冷启动用户的特征, 根据特征分簇并制定推荐规则, 给出推荐[4].基于规则的推荐只能将符合规则的信息推荐给用户, 推荐信息的覆盖范围较小, 且很难反映出由于用户间社交关系变化而导致的推荐结果变更.2) 基于内容的推荐将与用户关注的关键词相似度较高的信息推荐给用户[5].基于内容的推荐效果取决于准确的特征抽取, 如Yin等[6]提出一种潜类统计混合模型.基于内容的推荐结果中包含大量与用户历史浏览信息重复的信息.3) 基于协同过滤的推荐根据用户之间的相似程度或者项目之间的相似程度给出推荐[7].为解决用户数据稀疏的问题, Jamali等[8]提出非负矩阵分解(non-negative matrix factorization, NMF).Ma等[9]提出基于概率矩阵分解(probabilistic matrix factorization, PMF)的推荐.Wu等[10]提出在矩阵分解的过程中引入影响用户喜好的特征向量可以提高推荐的准确度.Koren[11]提出时间敏感的协同过滤推荐算法.Ren等[12]提出平衡评分预测机制的协同过滤推荐方法.基于协同过滤的推荐效果受用户历史行为信息数量的影响非常明显.4) 基于社交网络的推荐通过用户社交关系标签的方法为冷启动用户发现相似用户进而给出推荐[13-17].准确地发现用户间信任关系是基于信任推荐的关键.国内外学者的研究主要包括信任关系的传递策略[18-19]、验证信任网络具有小世界特征[20], 基于社交网络的小世界特性和用户间弱关系构建信任网络[21].如Liu等[22]提出传播过程中扩散的相对量与绝对量的权重博弈.Guha等[23]提出用户间的信任关系可通过由用户给出少量不信任或信任实例预测.Deng等[24]提出一种基于增强信任社交网络的服务推荐方法.Moradi等[25]提出一种基于可信度的信任感知协同过滤方法.然而用户间社交关系不是静止不变的, 冷启动用户本身及其他用户的社交关系会随着时间发生变化[26], 现有基于社交网络的冷启动推荐方法却没有充分考虑社交关系的变更对推荐结果的影响[27-28].本文提出一种基于增量图形模式匹配的动态冷启动推荐方法(Incremental graph pattern matching based dynamic cold-start recommendation, IGPMDCR), 基于社交网络中用户间社交关系拓扑结构随时间变化的情况, 实时地更新冷启动用户的相似用户, 进而给出实时的推荐.

1 社交关系拓扑

社交网络中丰富的用户社交关系信息可以用来反映用户在现实社会中的偏好, 通过为冷启动用户发现具有一定数量购物记录和评价信息的相似用户, 可以为冷启动用户给出推荐.然而, 社交网络中用户间的社交关系不是静止不变的, 多数用户间的社交关系会随着时间的推移而发生变化, 当与冷启动用户相关联的社交关系发生变化后, 如果仍然基于变化前的相似用户为冷启动用户给出推荐, 显然会产生差异.社交网络中用户的规模已经非常庞大, 尤其在用户间社交关系频繁变更的情况下为冷启动用户重新匹配相似用户是代价昂贵的.因此, 在冷启动用户已有相似用户的基础上, 基于冷启动用户及其他用户社交关系拓扑结构的变化, 为冷启动用户动态更新相似用户, 给出实时的推荐是一种可行的方法.

社交关系拓扑是由表示用户的节点以及表示用户间社交关系的边组成的有向图.其中边的权重值可以表示社交关系的紧密程度, 对边标记类型可以区分不同种类的社交关系.令u′表示与冷启动用户u存在某种社交关系的用户, uu′之间的社交关系紧密程度用uu′之间路径长度fe(u, u′)表示, 路径长度越短则对应的社交关系越紧密, 路径长度越长则对应的社交关系越疏远.fe(u, u′)=∞表示用户uu′之间不存在社交关系.uu′间的社交关系类型用fL(u, u′)表示.通过社交关系类型和社交关系的路径长度可以描述用户在社交网络中的社交关系拓扑.令G=(V, E, fA)表示社交网络的拓扑, 其中1)V表示有限的节点集合;2) EV ×V表示从vv′的边, 其中vv′表示社交网络中任意用户;3) fA(·)表示节点v的属性, 如fA(v) = (A1 = a1, …, An = an), Ai 是用户v的一种属性, ai是一个常量.以冷启动用户的社交关系拓扑为匹配模式, 则匹配模式为Q=(VQ, EQ, fL, fe), 其中VQ是有限的点集, EQ是有向边的集合.

2 基于增量图形模式匹配的动态相似用户更新

在冷启动用户已有相似用户的基础上, 基于冷启动用户及其他用户社交关系的变化, 为冷启动用户动态更新相似用户, 给出实时的推荐.

基于增量图形模式匹配的动态相似用户发现是基于冷启动用户已有相似用户的基础上, 动态的为冷启动用户更新相似用户.因此首先要发现冷启动用户的相似用户.为冷启动用户发现相似用户的过程是在G中发现所有与匹配模式Q相匹配的节点集合, 即基于有界图形模式匹配发现相似用户.令SVQ×V, 基于有界图形模式匹配的相似用户条件:1) 用户v的属性与用户u的属性相似.2) 对于(u, u′), 有向图中存在一个非空且长度不超过fe (u, u′)的路径v/…/ v′, 且存在(u, v)∈S.3) 对于(u, u′), G中存在路径v/…/ v′, 使fL(v, v1)…fL(vn, v′)满足(u, u′)上的关系fL(u, u′), 其中路径v/…/ v′中节点的顺序为(v, v1, …, vn, v′).基于有界图形模式匹配的相似用户发现算法如算法1所示.其中, mat (u)记录G中可以匹配Q中节点u的节点, demat (u)记录G中不能匹配Q中节点u的节点. Anc()和desc()分别表示节点前驱和后继节点.对于任意xV且(u′, u)∈EC, anc (fe(u′, u), fv(u′), x)表示x的符合如下条件的前驱节点x′, x′满足1) x′到x的距离不大于fe(u′, u), 2) fv(x′)满足fv(u′); desc (fe(u, u′), fv(u′), x)表示x的符合如下条件的后继节点z, z满足1) zx的距离不大于fe(u′, u), 2) fv(z)满足fv(u′).

算法1 基于有界图形模式匹配的相似用户发现

输入: Q = (VQ, EQ, fL, fe), G = (V, E, fA).

输出:最大匹配集合S

1.计算G的距离矩阵M;

2. for each (u′, u) ∈EQ , xV do

3.计算anc (fe(u′, u), fv(u′), x), desc (fe(u′, u), fv(u′), x);

4. for each uEQ do

5. mat (u): = {x | xV, fA(x)符合fv(u), 且out-degree (a) ≠0, out-degree (x) ≠ 0 };

6. if (out-degree (a) ≠0, 并且∃(u′, u) ∈EQ (x′ ∈mat (u), fA(x)满足fv (u′), 并且len (x/.../x′) ≤ fe(u′, u)) demat (u): = {x| xV, out-degree (x)};

7. while (uVQ的demat (u) ≠ ∅) do

8. for each (u′, u) ∈EQ, z ∈ demat (u) ∩ mat (u′)) do

9. mat (u′): = mat (u′) \ {z};

10. if (mat (u′) = ∅) then return ∅;

11. for each u″ with (u″, u′) ∈EQ do

12. for (z′ ∈Anc (fe(u″, u′), fv(u″), z) ∧ z′ ∈demat (u′)) do

13. if (desc (fe(u″, u′), fv(u′), z′) ∩ mat (u′) = ∅)

14. then demat (u′): = demat (u′)∪{z′};

15. demat (u): = ∅;

16. S := ∅;

17. for (uVQ and x ∈mat (u)) do S := S∪{(u, x)};

18. return S

当社交网络中用户间关系发生变化, 即无论是冷启动用户本身发生变化, 还是与冷启动用户关联的用户发生变化, 都需要重新为冷启动用户计算相似用户.基于增量图形模式匹配为冷启动用户更新相似用户, 根据G中用户间路径的变化, 为冷启动用户删除或增加相似用户.其过程可表示如下, 令M(Q, G)表示符合Q的最大匹配集合, 令ΔG表示在原G中删除或者添加边的集合, 即G的更新, ⊕表示应用更新, 令G′表示更新后的用户集合, 则G′=G⊕ΔG, G更新后符合Q的最大匹配记为M(Q, G⊕ΔG), 令ΔM表示变化的最大匹配, 则M(Q, G⊕ΔG)= M(Q, G)⊕ΔM. IGPMDCR为冷启动用户更新相似用户可分为删除相似用户和增加相似用户. IGPMDCR迭代的发现社交关系变更的节点的前驱节点的路径长度变化, 进而判断社交关系变更的最大范围, 再判断冷启动用户的已有相似用户是否处于社交关系变更的范围内.

1) 删除相似用户:首先, 确定由于删除用户节点, 用户间社交关系变化的影响范围(AFF)cs, 即用户退出以及用户间社交关系删除对原有用户间路径长度的影响.计算用户间最短路径长度的更改, 以及用户间最短路径包含节点的变化.其次, 在冷启动用户已有的相似用户中搜索并删除用户属性、路径长度不再匹配的用户, 再分别以最短路径变更节点为起始节点, 搜索其前驱节点, 判断所经历路径是否既包含在匹配模式Q的路径中, 又在符合Q的最大匹配集合M(Q, G)中仅存在一条与该路径匹配的路径, 删除变更后的路径长度不满足限制条件的相似用户.动态删除相似用户算法propCS如算法2所示, 其中Gr表示原相似用户集合, VrEr分别表示相似用户节点和边的集合, Gr表示动态更新后的相似用户集合.Ecs记录AFFcs中的边, v′的前驱节点v″. propCS首先检测e=(v′, v)是否为匹配模式的关键路径, 如果不是关键路径则原相似用户集合Gr不改变.如果是关键路径, 则递归的发现所有与v′匹配且由于删除e不再满足条件的边和节点.

算法2  动态删除相似用户

Input: Q, Gr= (Vr, Er), Ecs.

Output: Gr.

1. if (Ecs := ∅ & & eEr) then return Gr;

2.Ecs:push (e);

3. while Ecs do

4. e := Ecs:pop();

5. for each eQ = (u′, u) match e = (v, v′) do

6. if v′匹配u′;

7. else v′不匹配u′ then

8. for each e′= (v″, v′) in Er do

9. Er := Er \{e′}; Ecs:push (e′);

10. Vr := Vr \{v′}; mat (u′): = mat (u′) \{v′};

11. if mat (u′) = ∅ then return ∅;

12. return Gr.

2) 增加相似用户:首先, 确定由于增加用户节点导致用户间社交关系变化的影响范围AFFcc.其次, 分别以最短路径变更节点为起始节点, 搜索其前驱节点, 判断所经历路径是否既包含在匹配模式Q的路径中, 又包含在符合Q的最大匹配集合M(Q, G)的路径中, 新增变更后的路径长度满足限制条件的用户作为相似用户.动态增加相似用户算法propCC如算法3所示, 其中Ecc记录AFFcc中的边.

算法3 动态增加相似用户

Input: Ecc, Q, Gr.

Output: Gr.

1. if (Ecc := ∅ & & eEr) then return Gr;

2. for each eGr do

3. Ecc:= {(v′, v)|(v′, v)的长度小于(u′, u)的长度};

4. if Ecc ∅ then

5. for each uGr do mat (u′): = mat (u);

6.为Gr计算匹配项;

7. if mat(u′) ∅ then更新Gr, Ecc;

8. return Gr;

基于增量图形模式匹配为冷启动用户更新相似用户如算法4所示.动态更新相似用户分别识别AFFcs和AFFcc, 当有新插入的边, 调用propCC, 删除边的过程调用propCS.基于增量图形模式匹配为冷启动用户更新相似用户的时间复杂度与匹配模式Q, 更新社交关系EccEcs成正比.即动态更新相似用户的时间复杂度为O((|EQ|+|VQ|)(|Ecc|+|Ecs|)), 展开(|EQ|+|VQ|)(|Ecc|+|Ecs|), 得到(|EQ||Ecc|+|EQ||Ecs|+|Ecc||VQ|+|VQ||Ecs|), EccEcs近似同一个数量级.在用户社交关系变化范围较小的情况下, 即Ecc远远小于E的情况下, 动态更新相似用户的时间复杂度为O(|EQ||Ecc|+|Ecc||VQ|)远小于重新计算相似用户的时间复杂度O(|V||VQ|+|EQ||V|+|EQ||E|+|VQ||E|).当社交关系发生显著变化时, 即EccE近似为同一个数量级, 动态更新相似用户的时间复杂度为O(|EQ||Ecc|+|Ecc||VQ|)与重新计算相似用户的时间复杂度O(|V||VQ|+|EQ||V|+|EQ||E|+|VQ||E|)为同一个数量级, 所以社交关系发生显著变化后, 基于增量图形模式匹配更新冷启动用户的相似用户退化为重新计算冷启动用户的相似用户.

算法4 动态更新相似用户

Input: Q, Gr, Ecc, Ecs.

Output: Gr

1. Ecs := {(v′, v) | (v′, v)属于AFFcs对应存在(u′, u)∈EQ};

2. propCS (Ecs; Q; Gr);

3. Ecc:= {(v1′, v1)|(v1′, v1)属于AFFcc对应存在(u1′, u)∈EQ};

4. propCC (Ecc; Q; Gr);

5. return Gr.

3 由冷启动用户的相似用户给出推荐

对冷启动用户的推荐实质是预测用户商品矩阵R=[ru, i]m×s中的未知元素, 即冷启动用户对未知商品的评价值, 依据评价值的排序, 将Top-N评价值对应的商品推荐给冷启动用户.令i表示商品, ru, i表示冷启动用户u对商品i的评价值, m表示冷启动用户个数, s表示商品个数.由于冷启动用户具有很少的购物记录和评价, 因此冷启动用户的用户商品矩阵是一个极其稀疏的矩阵.为冷启动用户推荐, 其实质是一个矩阵补全过程, 即通过为冷启动用户发现相似用户, 再根据其与冷启动用户的相似程度和其本身的评价值补全冷启动用户的用户商品矩阵.为冷启动用户推荐的第一步是发现冷启动用户的相似用户.第二步根据相似程度预测冷启动用户在用户商品矩阵中的未知项, 其中冷启动用户对未知项的评价值可由式(1) 求得, 式(1) 中wa, u表示由第一步计算出的用户au的社交关系相似程度, wa, u的值越大, 相应的推荐权重越大, ra, i表示用户a对商品i的评价值, ${\bar r_a}$表示用户a的平均评价值, ${\bar r_u}$表示冷启动用户u的平均评价值. σ表示与冷启动用户相似且评价过商品i的用户数量.为冷启动用户u给出N个推荐结果的形式化描述如式(2) 所示, 其中I={i1, i2, …, is}表示商品集合, N表示给出推荐的个数.准确的为冷启动用户发现相似用户, 即可以准确地为冷启动用户给出推荐.为冷启动用户u给出推荐的形式化描述如式(1) 和(2) 所示.

${r_{u,{\rm{ }}i}} = \overline {{r_u}} + \frac{1}{\sigma }\sum {{w_{a,{\rm{ }}u}}} ({r_{a,{\rm{ }}i}} - \overline {{r_a}} ).$ (1)
${\rm{Top}}\left( {u,N} \right): = \mathop {{\rm{max}}}\limits_{i \in I}^N \;{r_{u,{\rm{ }}i}}.$ (2)
4 实验结果与分析 4.1 实验数据及评测方法

实验数据集取自Epinions和YouTube网站, 其中Epinions记录用户对商品的评价值, 以及用户间评价、分享、回复、转发评论关系, 用户对商品的评价值分为5个档次, 其中1表示不推荐, 5表示非常推荐.数据集中有49 289个用户对139 544个不同商品的评价, 评价总数达到586 361条.其中有35.8%的用户至少评价过8个商品, 47.3%的用户评价过3~7个商品, 16.9%的用户至多评价过2个商品.在实验中将评价个数少于2的用户作为冷启动用户, 测试集中冷启动用户的数量占16.9%.为了验证IGPMDCR能够实时反映用户社交关系变化并给出准确的推荐, 数据集收集了Epinions网站640 d的用户数据, 这些用户数据反映了社交关系随时间而发生变化的情况.

YouTube是一个视频分享网站.YouTube中包含不同的社交关系.从YouTube爬取30 522个用户的配置文件.基于所获取的信息, 构建5种不同的社交关系.这些关系包括:用户之间的联络关系;共享好友关系;用户之间共享订阅数量的关系;用户间共享用户数;共享喜爱视频的数量.将有不超过3个共享订阅和共享喜欢视频的用户作为冷启动用户.在获取的YouTube数据集中, 冷启动用户占27.37%.同样收集了YouTube 640d的用户数据用来反映社交关系随时间而发生变化的情况.

实验结果比较方法采用均方根误差(root mean square error, RMSE), RMSE是评估算法计算的预测值与真实值之间差距的指标, 可用于衡量推荐效果[22], RMSE的定义如式(3) 所示, 其中u, i表示由算法预测的用户u对商品i的评价值, T表示用户评价的商品数目. RMSE值越小, 则算法的推荐效果越好.

$\text{RMSE}=\sqrt{\frac{\sum\nolimits_{i=1}^{T}{{{({{r}_{u,i}}-{{{\hat{r}}}_{u,i}})}^{2}}}}{T}}.$ (3)
4.2 实验结果

分别与在实时冷启动推荐中取得较好效果的方法和效果较好的基于社交网络的推荐算法做对比试验.

在实时冷启动推荐中取得较好效果的方法包括:Bobadilla等[1]提出一种基于神经学习优化的相似度量方法, 动态的为冷启动用户给出推荐. Koren[11]提出时间敏感的协同过滤推荐算法, 在用户、项目特征向量中引入时间特征, 有效地区分瞬时效应和长期模式的用户兴趣.Lika等[2]提出基于分类算法的协同过滤方法动态的发现相似用户, 进而为冷启动用户给出实时推荐.Ling等[4]提出通过矢量余弦法获取用户相似矩阵, 实时的为各组用户给出推荐.

基于社交网络的推荐算法中推荐结果较好的方法包括:基于增强信任社交网络的服务推荐方法和基于可信度的信任感知协同过滤方法.基于增强信任社交网络的服务推荐方法, 又称为关联信任游走(relevanttrustwalker, RTW). Deng等[24]首先构建可获取用户在社交网络中信任度的矩阵分解方法, 然后改进随机游走方法获取推荐结果.基于可信度的信任感知协同过滤方法(reliability-based trust-aware collaborative filtering method, RTCF)提升基于信任感知推荐的准确度.由用户相似值和信任状态构建初始信任网络, 基于信任的可信度量初始评估构建信任网络的可信度, 重构可信度低于预设值的信任网络[25].

由于推荐算法需要一定的训练集, 因此使用不同百分比的训练集, 分别占整个测试集的10%, 20%, 40%和80%.测试集中包含640 d的用户数据, 包含了用户社交关系随时间而发生变化的情况, 选取社交关系变动明显的9个阶段, 分别是:第1个阶段初次使用数据集的时间;第2个阶段距离起始时刻1~5 d;第3个阶段距离起始时刻6~10 d;第4个阶段距离起始时刻11~20 d;第5个阶段距离起始时刻21~40 d;第6个阶段距离起始时刻41~80 d;第7个阶段距离起始时刻81~160 d;第8个阶段距离起始时刻161~320 d;第9个阶段距离起始时刻321~640 d.分别在Epinions和YouTube测试集中测试Bobadilla、Koren、Lika、Ling、RTW、RTCF和IGPMDCR在不同时间阶段的推荐效果.在Epinions测试集中的实验结果如图 1(a)~(d)所示, 其中图 1(a)~(d)分别对应测试集占10%, 20%, 40%和80%的情况, 横坐标t为社交关系变动明显的9个阶段距离起始时刻的时间, 纵坐标y表示由算法给出推荐结果的RMSE值, 在图 1(a)~(d)中IGPMDCR的RMSE值始终小于Bobadilla、Koren、Lika, Ling、RTW、RTCF的RMSE值, 并且随着时间的推移IGPMDCR的RMSE值与Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE值差距逐渐增加, 当超过20 d后, Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE与IGPMDCR的RMSE差距开始加速扩大, 到321~640 d Bobadilla、Lika、Ling、RTW、RTCF的RMSE与IGPMDCR的RMSE差距达到最大.这是由于Bobadilla、Koren、Lika、Ling、RTW、RTCF的方法对用户社交关系的变化不敏感, 不能实时反映用户社交关系的变化和与其对应的用户偏好变化.

图 1 在Epinions测试集的推荐效果比较 Fig. 1 Comparison of recommendation effectivenessagainst RMSE on Epinions

在YouTube测试集的实验结果如图 2(a)~(d)所示, 其中图 2(a)~(d)分别对应测试集占10%, 20%, 40%和80%的情况.在图 2(a)~(d)中IGPMDCR的RMSE值始终小于Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE值, 并且随着时间的推移IGPMDCR的RMSE值与Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE值差距逐渐增加, 当超过20 d后, Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE与IGPMDCR的RMSE差距开始加速扩大, 到321~640 d Bobadilla、Koren、Lika、Ling、RTW、RTCF的RMSE与IGPMDCR的RMSE差距达到最大.在Epinions和YouTube测试集的实验结果表明IGPMDCR在用户社交关系随时间而改变的过程中, 可以为冷启动用户给出更准确的推荐.

图 2 在YouTube测试集的推荐效果比较 Fig. 2 Comparison of recommendation effectiveness against RMSE on YouTube

基于增量图形模式匹配为冷启动用户更新相似用户, 基于变化前的社交网络G中用户u的最相似用户, 然后根据增量挖掘技术增加或者删减最相似用户, 生成社交关系变化后u的最相似用户.当社交关系发生显著变化时, 通过实验来进行验证社交网络中社交关系发生变化的用户的百分比与基于增量图形模式匹配为冷启动用户更新相似用户的时间关系.如图 3所示, 横轴R为社交网络中社交关系变化的百分比, 纵轴O为基于增量图形模式匹配为冷启动用户更新相似用户的时间与完全重新计算相似用户的时间的百分比. O取值越接近0, 基于增量图形模式匹配为冷启动用户更新相似用户的时间越少;O取值越接近1, 则基于增量图形模式匹配为冷启动用户更新相似用户退化为重新计算冷启动用户的相似用户.图 3中, 当社交网络中有10%的用户社交关系变化时, 基于增量图形模式匹配为冷启动用户更新相似用户的时间远小于重新计算相似用户的时间, 随着用户社交关系变化比率的升高, 基于增量图形模式匹配为冷启动用户更新相似用户的时间不断增加.当社交网络中有20%以上的用户社交关系变化时, 基于增量图形模式匹配为冷启动用户更新相似用户的时间加速上升, 当有30%以上用户社交关系变化时, 基于增量图形模式匹配为冷启动用户更新相似用户的时间与用户社交关系变化百分比几乎成正比关系.当有90%以上用户社交关系变化时, 基于增量图形模式匹配为冷启动用户更新相似用户退化为重新计算冷启动用户的相似用户.

图 3 社交网络中社交关系发生变化的用户百分比与基于增量图形模式匹配为冷启动用户更新相似用户的时间关系 Fig. 3 Relationship between percentage of users whose social relationship changed and time of updating similar users for cold-start user with incremental graph pattern matching
5 结语

社交网络中冷启动用户不是孤立静止的, 随着时间的推移冷启动用户和其已有相似用户的社交关系都可能会发生变化, 如果不考虑用户间社交关系的变化, 还是基于原来的相似用户给出推荐则可能无法得到准确的推荐结果.社交网络中用户的规模已经非常庞大, 无论是冷启动用户, 或者是其他用户的社交关系变更, 为冷启动用户重新匹配相似用户是代价昂贵的.本文提出基于增量图形模式匹配的相似用户发现方法(IGPMDCR), 在冷启动用户已有相似用户的基础上, 为冷启动用户动态更新相似用户, 进而给出实时、准确的推荐.在包含大量冷启动用户且用户间社交关系随时间发生变化的数据集的实验结果表明, IGPMDCR在较长的时间里可以动态的为冷启动用户更新相似用户, 为冷启动用户给出准确的推荐.

参考文献
[1] BOBADILLA J S, ORTEGA F, HERNANDO A, et al. A collaborative filtering approach to mitigate the new user cold start problem[J]. Knowledge-Based Systems, 2012, 26(1): 225–238.
[2] LIKA B, KOLOMVATSOS K, HADJIEFTHYMIADES S. Facing the cold start problem in recommender systems[J]. Expert Systems with Applications, 2014, 41(4): 2065–2073. DOI:10.1016/j.eswa.2013.09.005
[3] REN Y L, LI G, ZHOU W L. PRICAI 2012: Trends in Artificial Intelligence[M]. Berlin: Springer, 2012: 887-890.
[4] LING Y X, GUO D K, CAI F, et al. User-based Clustering with Top-N Recommendation on Cold-Start Problem[C]//Proceedings of the 2013 3rd International Conference on Intelligent System Design and Engineering Applications. Hong Kong: IEEE Computer Society, 2013: 1585-1589.
[5] LOPS P, DE GEMMIS M, SEMERARO G. Recommender systems handbook[M]. Berlin Heidelberg: Springer, 2011: 73-105.
[6] YIN H, CUI B, CHEN L, et al. A temporal context-aware model for user behavior modeling in social media systems [C]//Proceedings of the 2014 ACM SIGMOD international Conference on Management of Data. Snowbird, USA: ACM, 2014: 1543-1554. http://dl.acm.org/citation.cfm?id=2588555
[7] WANG J, DE VRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[C]//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Washington, USA: ACM, 2006: 501-508.
[8] JAMALI M, ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks [C]//Proceedings of the 4th ACM Conference on Recommender Systems. Barcelona, Spain: ACM, 2010: 135-142. http://www.oalib.com/references/16308300
[9] MA H, YANG H, LYU M R, et al. Sorec: social recommendation using probabilistic matrix factorization[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management. Napa Valley, USA: ACM, 2008: 931-940.
[10] WU L, CHEN E H, LIU Q, et al. Leveraging tagging for neighborhood-aware probabilistic matrix factorization[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. Maui Hawaii, USA: ACM, 2012: 1854-1858.
[11] KOREN Y. Collaborative filtering with temporal dynamics[J]. Communications of the ACM, 2010, 53(4): 89–97. DOI:10.1145/1721654
[12] REN L, GU J Z, XIA W W. An item-based collaborative filtering approach based on balanced rating prediction [C]//Proceedings of 2011 International Conference on Multimedia Technology. Hangzhou: IEEE, 2011: 3405-3408.
[13] ZHAO W X, LI S, HE Y, et al. Connecting social media to e-commerce: cold-start product recommendation using microblogging information[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(5): 1147–1159.
[14] 李洋, 陈毅恒, 刘挺. 微博信息传播预测研究综述[J]. 软件学报, 2016, 27(2): 247–263.
LI Y, CHEN YH, LIU T. Survey on predicting information propagation in microblogs[J]. Journal of Software, 2016, 27(2): 247–263.
[15] 赵泽亚, 贾岩涛, 王元卓, 等. 大规模演化知识网络中的关联推理[J]. 计算机研究与发展, 2016, 53(2): 492–502.
ZHAO ZY, JIA YT, WANG YZ, et al. Link inference in large scale evolutionable knowledge network[J]. Journal of Computer Research and Development, 2016, 53(2): 492–502. DOI:10.7544/issn1000-1239.2016.20148283
[16] REAFEE W, SALIM N, KHAN A. The power of implicit social relation in rating prediction of social recommender systems[J]. Plos One, 2016, 11(5): 1–20.
[17] PENG F, LU J, WANG Y, et al. N-dimensional markov random field prior for cold-start recommendation[J]. Neurocomputing, 2016, 191(1): 187–199.
[18] MA H, KING I, LYU M R. Learning to recommend with social trust ensemble [C]//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. Gold Coast, Australia: ACM, 2009: 203-210.
[19] KIM Y A, SONG H S. Strategies for predicting local trust based on trust propagation in social networks[J]. Knowledge-Based Systems, 2011, 24(8): 1360–1371. DOI:10.1016/j.knosys.2011.06.009
[20] YUAN W W, GUAN D H, LEE Y K, et al. Improved trust-aware recommender system using small-worldness of trust networks[J]. Knowledge-Based Systems, 2010, 23(3): 232–238. DOI:10.1016/j.knosys.2009.12.004
[21] JIANG W J, WANG G J, WU J. Generating trusted graphs for trust evaluation in online social networks[J]. Future generation computer systems, 2014, 31(1): 48–58.
[22] LIU R R, LIU J G, JIA C X, et al. Personal recommendation via unequal resource allocation on bipartite networks[J]. Physica A: Statistical Mechanics and its Applications, 2010, 389(16): 3282–3289. DOI:10.1016/j.physa.2010.04.004
[23] GUHA R, KUMAR R, RAGHAVAN P, et al. Propagation of trust and distrust[C]// Proceedings Of The 13th International Conference on World Wide Web. New York, USA: ACM, 2004: 403-412.
[24] DENG S, HUANG L, XU G. Social network-based service recommendation with trust enhancement[J]. Expert Systems with Applications, 2014, 41(18): 8075–8084. DOI:10.1016/j.eswa.2014.07.012
[25] MORADI P, AHMADIAN S. A reliability-based recommendation method to improve trust-aware recommender systems[J]. Expert Systems with Applications, 2015, 42(21): 7386–7398. DOI:10.1016/j.eswa.2015.05.027
[26] LE H S. Dealing with the new user cold-start problem in recommender systems: A comparative review[J]. Information Systems, 2014, 58(1): 87–104.
[27] WANG Y, YIN G, CAI Z, et al. A trust-based probabilistic recommendation model for social networks[J]. Journal of Network & Computer Applications, 2015, 55(1): 59–67.
[28] WANG Y, CAI Z, YIN G, et al. An Incentive Mechanism with privacy protection in mobile crowdsourcing systems[J]. Computer Networks, 2016, 102(1): 157–171.