基于协同过滤和网络结构的个性化推荐算法

1、基于协同过滤和网络结构的个性化推荐算法    摘要:综合了经典的协同过滤算法和基于网络结构的个性化推荐算法。项目同其他所有项目的相似度之和被认为是项目在个性化推荐系统中的初始推荐资源,然后通过二部图的网络结构将这种资源进行重新分配。同时考虑两个项目之间的相互作用关系,提出了最终的推荐算法。最后,根据用户未曾收集项目最终所获得的资源进行排序,向用户推荐资源最多的项目。通过考察项目之间相互作用可以发现,推荐系统的算法衡量指标不能同时达到最优。同时为了进一步增强算法的可扩展性,引入了一个度指数来调节算法,这样在实际应用中就可以根据需要,通过调整项目之间的相互作

2、用以及项目自身的度指数,达到最好的用户体验和系统多样性。关键词:协同过滤;用户相似度;项目相似度;用户-项目二部图网络结构;个性化推荐0引言互联网技术的迅猛发展使得我们不得不面对信息过载:面对太多的信息以至于不能从中找到与我们相关的信息1。比如,在互联网上面有成千上万的网页可以浏览,数不胜数的音乐可以欣赏,可是面对如此多的选择,有时很难找到真正所需要的信息。信息过滤技术发展的一个标识就是搜索引擎的出现,它给用户提供了很大的方便。搜索引擎可以根据提供的关键字来返回用户感兴趣的东西。可是搜索引擎有两个缺点:1)搜索引擎根据用户的关键字返回给用户的信息都是一样的,也就是缺乏个性化的信息;2)并不是所

3、有的用户感兴趣的信息都可以用关键字表示(比如我们对音乐的感受)或者用户由于自身的原因根本无法提供关键字,在这种情况下,搜索引擎就失去了作用。推荐系统被认为是解决信息检索最有效的工具之一。推荐系统根据用户过去的历史信息,利用推荐系统的推荐算法,来向用户推荐用户未曾收集的项目。当前推荐系统的推荐算法2-3主要包括:基于内容的推荐算法4-5,基于协同过滤的推荐算法6-10,谱分析方法11,主元素分析方法7-12,以及最近提出的基于网络结构的推荐算法13-14和混合的推荐算法15-16等。同时,Web 2.0的出现使得用户不再是单纯网站的浏览者,用户也成为网站信息的交互者17。这使得互联网上面存储的信

4、息量更进一步增加,但同时也使得个性化推荐成为可能。所谓个性化推荐就是在传统推荐的基础上针对不同的用户,根据用户的不同兴趣,返回不同的推荐结果集。在当前,协同过滤算法应用最为广泛,同时也是最为成熟的一种算法。但是传统的推荐算法由于受到系统的可扩展性以及数据稀疏性的限制,在很多情况下效果并不是很好。最近提出的利用物理方法,如物质扩散14,热传导18,在个性会推荐方面取得了很好的效果。因此在本文中,考虑将传统的协同过滤算法和利用二部图网络结构的推荐算法进行结合,从而向用户进行个性化的推荐。1算法描述在一个推荐系统中,不同的用户可以根据自己的爱好来选择不同的项目。通常可以将该系统构建成一个二部图网络1

5、9,其中用户和项目分别构成两个节点集,分别用U=u1,u2,un和O=o1,o2,om来表示。用户选择过的项目构成一个m×n的邻接矩阵A=aijm×n。在该矩阵A中,如果用户j选择过项目i,则元素aij的值为1;否则该元素的值为0。全局排序算法14,主要是根据项目度的大小来向用户呈现推荐列表,如在百度,谷歌搜索引擎中看到TOP列表。改进该算法,使它能应用到个性化推荐算法:对所有的项目依据度的大小进行排序,针对每一位用户,对该用户未曾收集的项目按项目度进行排序,然后向用户进行推荐。传统的协同过滤算法主要包括基于项目的协同过滤算法以及基于用户的协同过滤算法。二者都是首先计算各自

6、的相似度,然后根据相似度对用户未曾收集过的项目进行预测打分,根据得分的高低向用户推荐。只是二者在计算相似度时有些不同。在基于项目的协同过滤算法中,项目项目之间的相似度S为S=k=1akakmin(k(o),k(o)(1)式中,k(o)=nk=1ak为收集项目的用户的数目,k(ui)=mk=1aki为用户i收集过的项目的数目(下同)。在计算相似度之后,对用户未曾收集的项目进行打分预测。用户i对项目的预测打分为voi=mk=1,kiSkaimk=1,kiSk(2)考虑项目同所有项目的相似度之和,即S=mk=1,kSk(3)由式(3)可以看出,当项目同所有项目的相似度之和S非常大时,表明该项目在整个

7、系统中是非常活跃的。因此该项目在向其他项目进行推荐时也就应该具有更大的权重。因此将其视作该项目在整个推荐系统中的初始推荐资源。同时,为了克服数据稀疏性局限,可以利用二部图的网络结构,得到项目在二部图上的资源分配方案w=1k(o)nk=1akakk(uk)Sk(o)(4)w=1k(oa)k1-(o)nk=1akakk(uk)Sk(o)(5)fi() =m=1wfi() (6)式(4)中,w表示项目将该项目同所有项目的相似度之和S作为推荐系统的初始资源,根据二部图的网络结构分配给项目。为了更好的观察项目和项目之间的相互作用关系,将上式继续改进,如式(5)式所示,该式表示增加了项目对项目相互作用后,

8、项目最终分配获得的资源,当=0时,式(5)退化成了式(4),式(6)表示对用户i未曾收集的项目的预测打分。fi()取1当用户选择过该项目,否则为0。只有该用户以前选择的项目才能对未选择的项目进行资源传递,这样不同的用户具有不同的项目初始资源,因而预测打分时也就包含了用户个性化信息。2数值模拟测试算法采用的数据集可以从网站20得到。该数据集包含943位用户和1 682部电影,共105条记录。该数据集中,用户对电影进行打分,从1到5,其中1表示很不喜欢,5表示非常喜欢,3表示用户对该电影既不讨厌也不喜欢。根据算法的需要对数据进行了预处理:只选取用户打分不小3的记录,因为只有这样的项目才能对其他的项

9、目进行推荐。在数据集中,85·25%的记录不小于3。接着数据集被随机的分成两部分,其中一部分占数据集的90%,用来做算法的训练集,剩余的10%用作算法的测试集。一个好的推荐算法应该给用户提供一个用户未曾收集项目的推荐列表,且列表的长度不能太长。对于任意一位用户ui,在测试集中如果含有一条这样的记录uio,就可以用o在推荐列表中的位置来衡量算法。例如某位用户未曾收集的项目为1 000,在测试集中含有该用户的1条记录,该项目在推荐列表中的位置为50,那么就用排序值ri=50/1 000=0·05来衡量算法的效率。在用户的推荐列表中,项目在列表中的位置越靠前,则排序值越小,算法的

10、效率就越好,预测的准确性就越高。然后用平均排序值,即对测试集中的所有排序值取平均,来衡量算法的整体效率。在测试集中,全局排序算法,基于项目的协同过滤算法的排序值分别为0·137,0·121,但是从图2可以看出即使在排序值很大情况下得到的结果也要比前面两个算法得到的结果好的多。这就证明考虑了项目间相互作用对于提高算法有帮助。3改进的算法引入一个度指数来调节项目度在算法中作用,其中k(o)表示对项目的度进行指数运算。当>1时,具有较大度项目的相似度的作用受到抑制;当<1时,具有较大度项目的相似度作用得到增强,当=1,算法就退化成了式(4)提到的算法。这样,式(5)可

11、以修改为w=1k(oa)k1-(o)nk=1akakk(uk)Sk(o)(7)任意两个用户之间海明距离定义为长度为L的推荐列表中,二者推荐列表中项目的不同程度,用式(8)表示。hij=1-Q/L (8)式中,Q为长度为L的推荐列表中,两用户相同项目的数目;n为推荐系统中用户的数目。用H(式(9)表示算法的平均海明距离,它表明了整个系统推荐给用户的项目所具有的多样性,距离越大,系统多样性越好。H =1n(n-1)hij(9)用平均度di来衡量推荐系统向单个用户推荐项目的多样性,由(10)式计算。di=1LLk=1k(ok) (10)其中,k(ok)为用户i推荐列表L中的第k个项目的度。这样整个推

12、荐系统的平均度D可以由式(11)计算。D =1nnk=1dk(11)它表明了整个推荐系统推荐给用户的项目的多样性,di越小,表明推荐列表中产品的度越小,项目所包含的非流行信息就越多,单个用户多样性也就越好,用户体验也就越好。由图1图3可见,两个项目之间的相互作用对算法衡量指标有直接的调节作用。随着第1个项目权重的增大,图1中平均度急剧减小,而图3中海明距离增大,且排序值在=0·7左右的时候取得最优值,但图2中的排序值的变化确没有规律。同样在考察单个项目的度指数时,算法的推荐指标的整体变化更加的复杂。图4中,在=-2时,排序值取得了最优值,图5显示此时平均度并不是最小。由图6可以看出此

13、时海明距离不是最大的,=2的时候,海明距离取得最优值。同一个不能使推荐系统的3个指标同时最优。通过这个两个参数,推荐系统的管理者就可以通过调节参数,直观的获得调整后的效果,从而更加便于管理。在实际的推荐系统中,为了更好的增加用户体验,可以通过调节项目之间的相互作用以及项目自身的度来达到最佳的效果。4结论在本文中,通过将传统的协同过滤算法和二部图的网络结构相结合,同时考虑项目之间的相互作用,得到改进的推荐算法。通过基准测试集的比较知道,相比于传统的协同过滤算法,改进后算法在排序值提高很大。同时通过加入度指数来调整项目的度对相似度的影响来观察算法指标的变化,平均海明距离和平均度两个指标也被用来考察

14、算法的效果。测试数据表明,对于一个特定的推荐系统,排序值,平均海明距离以及平均度指标并不能同时达到,因此在算法的实际应用中,可以通过调整项目之间的相互作用以及项目自身的度指数来获得最好的用户体验以及系统多样性。参考文献:1 Berghel H. Cyberspace 2000: dealing with information overloadJ. Communications of the ACM. 1997, 40 (2): 19-24.2 Adomavicius G, Tuzhilin A. Toward the next generation of recommender system

15、s: a survey of the state-of-the-art andpossible extensionsJ. IEEE transactions on knowledge and data engineering, 2005, 17 (6): 734-749.3 Liu J G, Zhou T, Wang B H. research process of the personal recommendation systemJ. Progress in Natural Scie,2009, 19 (1):1- 15.4 Balabanovic'M, Shoham Y. Fab

16、: content-based, collaborative recommendationJ. Communications of the ACM, 1997,40 (3): 66-72.5 Melville P, Mooney R J, Nagarajan R. Content-boosted collaborative filtering for improved recommendationsC. Pro-ceedings of the National Conference on Artificial Intelligence, Edmonton, 2002: 187-192.6 He

17、rlocker J L, Konstan J A, Terveen L G, et al. Evaluating collaborative filtering recommender systemsJ. ACMTransactions on Information Systems (TOIS), 2004, 22 (1):5- 53.7 Honda K, Sugiura N, Ichihashi H, et al. Collaborative filtering using principal component analysis and fuzzy cluster-ingJ. Web In

18、telligence: Research and Development,2001,2198: 394-402.8 Marlin B. Collaborative filtering: a machine learning perspectiveD. Toronto: Department of Computer Science Univer-sity of Toronto,2004.9 McLaughlin M R, Herlocker J L. A collaborative filtering algorithm and evaluation metric that accurately model the userexperienceC. Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in In-formation Retrieval,New York: ACM Press,2004:329-336.10 Connor M, Herlocker J. Clustering items for collabor