推荐系统研究

1 主要算法

1.1 协同过滤算法

“协同过滤(CF)”是最为学者广泛使用并深化研究的算法之一，该思想的提出极大地推动了推荐算法的研究和发展[3].协同过滤推荐算法整体大致可以总结为下列表述:依据集体智慧，借助与目标用户有相似行为特征的其他的大量用户的数据，来预测该用户对某一产品是否有兴趣，从而给用户进行推荐.经过多年的发展，根据不同的处理方式主要分为如下几种主要类型[4－6].

基于记忆方法主要是采用类似与表1这样的评价矩阵，对目标用户可能感兴趣某一项目的进行评分或建立一个推荐列表.如表1所示，在这个矩阵中存在一系列的数字、空白等等，数值是对物品的评分，需要去进行预测或待评分的目标对象用“?”表示.

表1 用户－项目评分矩阵Tab.1 User－item scoring matrix

基于模型方法采用统计、数据检索及挖掘和深度学习等方法，根据目标用户的过去一段时期的行为数据挖掘出用户潜在的行为特征然后建立用户模型(user model)，再根据此模型进行推荐.

1.1.1 基于记忆的推荐算法.该推荐算法[7]在经过大量研究者的优化后有如下过程:①首先就是建立相似度矩阵或表格，这是一个数据的收集与整理过程；②使用对应的算法在步骤①建立的相似度矩阵的基础上进行评估，然后由此进行推荐.这类算法不仅能对单一目标进行评估也可产生一个推荐列表供用户参考.

1)基于用户的协同过滤推荐.该型的协同过滤推荐算法[8]是对基于记忆算法的一个深度延伸，以用户作为主要的考量，不去关注项目的具体情况.如表1中的数据，对评分数据整理后很容易得到各个用户I的评分状态，如下面表达式所示用余弦相似度方法[9]计算用户Ui和其他用户之间的相似度，将Ij评过分的用户组成集合对结果然排序得到最相关的评分，这里计算的是U1对I3的预估值.

同理，sim(U1，U3)＝0；sim(U1，U4)＝1；sim(U1，U5)＝0.894.

那么就易得:

该算法是应用较广的推荐算法之一，因为其自身的简单性很容易被人接受，然而其灵活性较差，无法解决冷启动问题，一旦用户数量增加迅速，就会使其的扩展性受到限制.

2)基于项目的协同过滤推荐算法.该类型推荐算法[9]所针对的对象是项目数.因项目数不常变化，那么基于项目的相似度矩阵就随之较为稳定，利用已经被用户评分的项目推测未知的目标项目.以表1为例，该方法计算P1，3的过程如下:

类似地，假如其项目的数目发生了剧烈的变化，其复杂度也会急速上升，也面临着扩展性较差的问题.

3)基于内存的Top－K推荐算法.该算法的目的是按照用户的偏好度高低选取排行前N的项目构成列表然后推荐给用户，文献[10－14]按照不同的侧重点基于内存的Top－N推荐算法也分成如下两种形式.

A.基于用户的Top－K推荐算法.基于用户的Top－K推荐算法[15]的基本思路与上述基于记忆方法有很大的相似，在后者的基础上对项目进行排序，找出最相关的前K个用户组成U∗，然后再从中进行统计，选出前N个显示给用户.具有的过程如下面表述的，其中参数K、N根据实验数据的大小按需求而定.

该算法为用户U1进行推荐的过程如下所述(K＝2，N＝2):使用余弦相似算法计算后得出得出各用户之间的相似程度，然后对这些系数进行排序得到最大的两个数值即与U1行为最接近的两个其他用户，那么就有U∗为{U2，U4}，I∗则包含{I3，I4，I5，I6}，对I∗中的四个用户的评分记录进行统计，得到评分不小于3出现的频数，其相应依次为1、2、1、0.因为存在出现频次相同的项，那么就需要利用相似度算法计算出评分的均值.由此易得用户U1得到的推荐项为I4、I5.但是在实际应用中，用户的数量可能是巨大的而且用户数量的流动情况也是不确定，所以该算法的可扩展性不高.

B.基于项目的Top－K推荐算法.基于项目的Top－K推荐算法[15－17]以项目作出主参考对象，其可扩展性相对有所提升.整体上其推荐过程归纳为:①计算出每个项目的相似邻居集合，然后排序并为每一个项目都构建出一个包含有K个对象的最相邻集合②从该邻居集合中删除目标用户已经评分过的项目，得到候选推荐集I∗；③最后在I∗中分别计算出每个项目与目标用户的项目之间的相似度，对结果排序，把前N个显示并推荐给用户.以表1的数据为例，为用户U1进行推荐(K＝2和N＝2).用余弦相似度算法对表内的所有数据进行计算然后排序易得与I1最相似的2个近邻为I5、I3，与I2最相似的2个近邻为I3、I5.其中{I1，I2}，I∗＝{I5，I3，I4，I6}.I5与的相似度为(sim(I1，I5)＋sim(I2，I5))/2＝1，同理可得余下各项与的相似度分别为0.999，0.874，因此为用户U1产生的推荐列表为

上述几种基于记忆的推荐算法相较都比较简单易懂，但是都存在一些缺陷，比如用户的评分矩阵往往都是高稀疏的，不利于计算相似度，所以还需要对数据进行预处理并对算法进行优化.

1.1.2 基于模型的协同过滤算法.在基于模型的方法[18]中，经过长期的实践研究按数据类型渐分为两个类型处理方法:离散型和数值型.前者则可以用深度学习[19]的方法来从松散的数据集中挖掘出潜在的特征以此建立特征模型[20－21]；后者则因是固定数值就可以用使用聚类等方式来处理.基于模型的方法是为了克服数据稀疏的影响而建立的，但随着数据挖掘技术的提高以此同时也提高了该类型推荐算法的准确度.

1)基于线性回归的协同过滤方法.该算法对用户的历史评价数据使用线性回归的方法[22－23]建立模型，然后根据模型对用户行为进行预测.例如，设U＝(X1，X2，…，Xn)，表示用户对n种项目的评分，那么如果去预测该用户对下一个项目的评分，需要设p＝(a1，a2，…，an)，表示各项的评分系数，那么其模型可是系统化表示化为:

M是补偿(偏差)系数，由表1的数据可以计算出各参数的值或是最近似值.但是也正是因为要用到评分矩阵，那么其自带的稀疏性、噪音等外部因素也必将干扰模型的工作，为此需要对数据进行预处理，常用的方法有奇异值分解[24]、稀疏因子分解[25]等.

2)基于马尔科夫决策过程(MDP)的协同过滤算法.深度学习的推广，使得MDP[26－27]的思想被应用到推荐系统之上，因为MDP考虑了动作，使得下个状态既和当前状态相关也和当前的动作相关.文献[28－30]把推荐过程转化为MDP最优选择问题，即找出一个让用户利益最大化的推荐列表.它将MDP模型模式化表示为(S，A，R，Pr).推荐过程对应的MDP过程可描述如下:

s∈S表示当前状态，πi＋1(s)是在状态s下为获得最大收益而应执行的动作，vi(s)是做出该动作获得的收益值，即最应该向用户推荐哪个项目.从初始活动开始，重复计算该表达式，直至出现一组结果，对结果排序然后以此推荐给用户.

除了上述的方法，还存在许多其他形式基于模型的推荐许比如:极大熵方法[31]、概率相关方法[32]等，虽然该类型的方法在一定程度上缓解了基于记忆方法的缺点、推荐效果也更好但是其算法较为复杂，所占时间开销也较大.还有一个比较大的问题协同过滤方法不能对新加入的项目进行推荐，必须在用户对该新项目评价之后才能被纳入相似度计算的范围之内.

1.2 基于内容的推荐

与协同过滤推荐相比较两者最大的不同点在于，基于内容的推荐[33]考虑的参考因子更多，不仅仅有用户对项目的评分，还包含用户发出评价的时间、地点以及用户的性别、年龄、身份等等.多因素被纳入参考范围带来效果是推荐更加的准确，也更具个性化.

1.2.1 基于文本的推荐.基于文本的推荐[34]的基本思想是收集该用户在过去的一段时间中做出的所有的行为，然后对收集的资料进行预处理，通过一定的方法得到用户的行为规律，比如收集用户在微博或贴吧中发过的评论或者是该用户关注的人或物品等，从而可以得出用户的兴趣偏向.基于这一思想，收集用户数据从而建立用户兴趣模型.对于那些想推荐给用户的项目，先对其项目的文本信息先进行预处理，降纬除燥[35]之后再提取特征，然后将物品特征与用户兴趣模型相比较，按相似度高低加入推荐列表中，更理性的说这属于数据挖掘[36]的范畴，但是现在已是多与推荐系统融合在一起.关键词的特征提取使用优化之后的TF－IDF模型[37]进行处理，根据不同的权重，对关键词进行排序提取.

其中:tfw，d表示查询词在数据集中出现次数，权重值与出现次数成正比，idfw，d，s表示在仅查询词组｜D，S｜中某个关键词出现次数的倒数；wmax表示该组关键词中最大权重值.

但是建立用户模型首先得有一定数量的历史数据且质量比较高，而实际状态是从网络上直接抓取数据是不可靠的，个人隐私使得获取数据十分困难.随着挖掘算法技术的发展以及在线数据质量和数量的提高，可使得该类型方法得到更好的发展.而在计算相似度时，使用最简单余弦相似度算法基本就可满足需求.

1.2.2 基于语义分析的推荐.使用基于内容的推荐时需要进行特征提取也就是找出某几项关键词，然后进行匹配，但是在用户评论或是产品描述时不可避免的会有同义词或多义词的出现，如此就会在相似度计算时产生评估不合实际的情况.为了解决这些问题，经过大量的研究者一些学者提出潜在语义分析方法[38]，简单的说就是建立数个相似子数据集，通过引入并使用编辑距离这一概念，对哪些经常出现的词汇进行归类，计算他们之间的编辑距离，找出相似度较高的关键词然后存入最小堆中，这样就获得了大量相似的关键词，然后把用户输入的关键词与相似词集比较，从而避免有误词的进入，然后对矩阵进行奇异值分解从而找到相关的推荐项目，采用这种措施后使得该算法具有了一定的容错性，更利于被用来做推荐研究.但是随着数据矩阵的变大，奇异值分解的运算效率会明显下降，无法满足高效的要求.文献[39]中提出了概率潜在语义分析模型不设置固定阈值，且将相似矩阵分块运算，相当程度上克服了LSA算法的不足.

当然还有一些其他的基于内容的推荐算法，尤其是随着计算机技术的发展计算速度及运行内存的急速上升，各种大数据挖掘技术相互融合，通过归类拟合获得一些更好的特征模型.综合分析后可以得出，相较于协同过滤推荐方法不能对新进入的项目进行推荐，基于内容的推荐不存在这方面的问题，因为基于内容的推荐方法是先对项目处理，所以新加入的项目将被进行特征提取建立特征向量然后才可以进行相似度计算，根据计算结果进行排序，然后将最合适的项目推荐给其他可能对此项目有兴趣用户.但是该类型的推荐也存在着许多且无法忽视的问题，比如许多用户评论内容的语法是很不规范的，一些网络词汇也可能被使用，这就导致特征提取的难度呈指数级上升.另外虽然这种方法受信息稀疏性的影响较小，也可以处理冷启动问题，但却受到信息获取技术的限制.

1.3 基于图结构的推荐算法

为了不受信息获取技术的限制，克服评价数据稀疏性的影响，一些研究者开始使用基于二部图网络结构[36]的推荐算法.这种算法把用户和产品作为节点，把用户与项目串联起来的边表示用户的评价.该算法的基本思路如下:

1)构建二部图.设在有M个项目和N个用户的系统中，用户Ui对项目Ij有偏好，那么aij＝1，否则aij＝0，从而得出一个如图1所示的简化后的二部图框架.

2)计算资源分配矩阵W.使用下面的公式计算项目Ii到Ij的资源分配的权重值wij:

Dj是二部图节点的度.

3)计算目标用户各项目的资源分配策略.用户Ui的对m个项目最初的资源分配策略表示为fi＝(ai1，ai2，…，aim)，fi′表示最终资源分配策略，即fi′＝W×fi.

4)按照fi′的结果，依照从大到小的顺序产生一个推荐列表.

如图1所示，有3个用户U1、U2、U3和5个项目I1到I5，以用户U1为例构成对应的二部图.

那么初始的资源f1为(1，0，1，0，0)，经过权重公式计算后可的W，然后可以由此计算出用户U1对应的资源矩阵fi′.

删除用户U1原来已经关注过的项目即I1，I3，那么排序后I4，I2，I5就是其最后得到的推荐项目.至于会有多少个项目被推荐可以根据实际需要在排序算法中进行设置.

虽然基于图结构的推荐算法，解决了数据的稀疏性的影响但是其在兴趣点的关注上有较大的问题，例如对项目有兴趣就设置aij＝1，而不去考虑用户对改项目的喜欢程度，这样就可能造成推荐结果不合实际的情况发生，所以给aij设计一个参考系数是很有必要的，而该参考系数如何设置且设置为多少就需要进一步研究了.

图1 二部图Fig.1 The bipartite graph

1.4 基于位置的社会化网络推荐

近年来智能移动设备应用日益普及，使得用户对位置服务的要求也愈加旺盛，位置服务与社交网络的融合也是越来越深，两者结合形成基于位置的社会化网络[40].它通过用户的签到把线下的真实世界与网络上的虚拟社会串联起来，从而使得用户在签到的时候，将自己的位置信息在线上虚拟社会的传播，以此获得样式繁多的位置服务，而推荐系统由于自身的天然属性，很自然地被用来进行信息的过滤与推荐.该系统的基本框架如图2所示.

文献[41]分析用户分析一个周期内(24h)用户的活动轨迹，使用概率分布模型，从而得到用户的活动规律然后由此进行推荐.Saleem等人对处于同一范围的用户通过聚类结合在一起，然后使用协同过滤、基于内容的推荐等算法实现把有共同爱好的用户的推荐给对方.

推荐算法是最为核心的部分，单用某一种方法必然无法满足系统的需要，上述的各种算法相结合进行混合推荐才可能产生实用性较好的结果.而且基于位置的社会化网络推荐研究还处于初步阶段，数据的稀疏性、用户的隐私保护、合适的推荐算法等等一系列的问题亟待解决.

图2 基于位置的社会化网络推荐基本框架Fig.2 The basic framework of the location－based social network recommendation system

2 研究热点和难点

涉及到数据挖掘研究，首先想到的问题就是数据的稀疏性.协同过滤算法其本质就是基于用户－项目的评分矩阵进行相似计算，但是实际情形是很难找到较为密集的数据源，要找出目标用户和其它用户共同评分的项目是比较困难的，因而大部分用的还是用稀疏的数据进行研究，这样就会造成推荐结果的不准确.所以如何降低数据的稀疏性仍是当前研究的重点之一.

其次是扩展性，推荐技术发展给民众带来了巨大的便利，所以无论是普通用户或商家都乐于使用推荐系统，那么商业推荐系统的用户数量亦或是项目数量很容易就达到百万级以上，这时其扩展性就成了一个大问题.因为其实时性无法得到满足，在百万级的数据中计算其花费的时间是很大的，例如协同过滤算法时间复杂度为O(n2m)，一旦用户数量n和项目m过大，其时间花销是难以想象的.

还有就是特征提取，各主要推荐算法都离不开对特征的挖掘与匹配，可以说特征提取的结果直接影响到推荐算法的准确性.目前对文本特征的挖掘技术较为成熟，但是随着互联网的发展图片、视频等多媒体数据增长迅速，而与之对应的挖掘算法就显得相对落后，比如优酷土豆等视频网站给其用户推荐视频时是根据用户所看过视频类型(经过人工标注的)进行相关推荐，而不是根据视频内容自动推荐，这样一旦出现人工标注的视频名字和视频内容不匹配的现象就可能发生推荐不合实际需要的情况.

当然还有许多其他的问题需要解决，上述的研究多是建立在显示反馈的基础上，但是现实情形是许多人为了个人隐私，是不会特意去评价商品或提交历史记录，这样获取数据的完整性就很难得到保证.而且对于项目不仅仅有正面的评价还可能有负面的评价，如何综合利用这些数据也是一个问题.

3 结论

推荐系统作为能有效解决信息过载的手段之一，越来越受到人们的重视，经过长时间的研究其算法能解决的问题越来越多，推荐结果也越来越来符合人们的期望.但是问题仍然存在，比如数据的稀疏性、过拟合、特征提取困难等等，随着推荐系统应用范围的扩展，相关技术如深度学习、信息检索、特征提取等仍将是研究的热点.

[1] ZHAO Z D，SHANG M S.User－based collaborative－filtering recom－mendation algorithms on hadoop[C]//Knowledge Discovery and Data Mining，WKDD'10 Third International Conference on IEEE，2010:478－481.

[2] 吴颜，沈洁，顾天竺，等.协同过滤推荐系统中数据稀疏问题的解决[J].计算机应用研究，2007，24(6):94－97.

[3] 罗奇，余英，赵呈领，等.自适应推荐算法在电子超市个性化服务系统中的应用研究[J].通信学报，2006(11):183－186.

[4] 邓爱林，朱扬勇，施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报，2003，14(9):1621－1628.

[5] 赵良辉，熊作贞.电子商务推荐系统综述及发展研究[J].电子商务，2013(12):58－60.

[6] Dietmar Jannach Markus Zanker.Recommander Systems[M].北京:人民邮电出版社，2014:8－14.

[7] LIAN D F，ZHAO C，XIE X.Joint geographical modeling and matrix factorization for point－of－interest recommendation//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[M].New York:USA，2014:831－840.

[8] CAO JIN－XIN，DONG YI，YANG PENG－WEI，et al.POI recommendation based on meta－path in LBSN[J].Chinese Journal of Computers，2016，39(4):675－684.

[9] 张亮，赵娜.改进的协同过滤推荐算法[J].计算机系统应用，2016，25(7):45－52.

[10] 乔亚飞，张霞，张文博.智能图书系统中的个性化推荐[J].计算机系统应用，2016，25(9):152－159.

[11] 朱郁筱，吕琳媛.推荐系统评价指标综述[J].电子科技大学学报，2012，41(2):163－175.

[12] 朱扬勇，孙婧.推荐系统研究进展[J].计算机科学与探索，2015，9(5):52－61.

[13] 严海兵，刘昊.基于文献引证关系的数字图书馆协同推荐系统[J].苏州科技学院学报(自然科学版)，2014，31(3):75－80.

[14] 陈雅茜，刘韬，方诗虹.推荐系统及其相关技术研究[J].西南民族大学学报(自然科学版)，2014，40(3):125－128.

[15] 张中峰，李秋丹.社交网站中潜在好友推荐模型研究[J].情报学报，2011，30(12):1319－1325.

[16] PATHAK B，GARFINKEL R，GORAL R D，et al.EmpiricalAnalysis of the Impact of Recommender Systems on Sales[J].Journal of Management Information Systems，2010，27(2):159－188.

[17] 梁昌勇，冷亚军，王勇胜，等.电子商务推荐系统中群体用户推荐问题研究[J].中国管理科学，2013，21(3):153－158.

[18] ANAND D，BHARADWAJ K K.Utilizing Various Sparsity Measures forEnhancing Accuracy of Collaborative Recommender Systems Basedon Local and Global Similarities[J].Expert Systems with Applica－tions，2011，38(5):5101－5109.

[19] CHOI K，SUH Y.A New Similarity Function for Selecting Neighborsfor Each Target Item in Collaborative Filtering[J].Knowledge－BasedSystems，2013，37:146－153.

[20] 胡勋，孟祥武，张玉洁.一种融合项目特征和移动用户信任关系的推荐算法[J].软件学报，2014(8):1817－1830.

[21] 陈可寒，韩盼盼，吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报，2013，36(2):349－359.

[22] LIU Y，WEI W，SUN A X.Exploiting geographical neighborhood characteristics for location recommendation[C]//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management，Shanghai，China，2014:739－748.

[23] YIN H Z，CUI B，SUN Y Z，et al.Lcars:a spatial item recommender system[J].Journal of the ACM Transactions on Information Systems，2014，32 (3):1－11，37.

[24] FARRAHI K，GATICA－PEREZ D.Discovering routines from large－scale human locations using probabilistic topic models[J].Journal of the ACM Transactions on Intelligent Systems and Technology，2011，2(1):1－3，27.

[25] 程飞，贾彩燕.一种基于用户相似性的协同过滤推荐算法[J].计算机工程与科学，2013，35(5):161－165.

[26] 杨博，赵鹏飞.推荐算法综述[J].山西大学学报，2011，34(3):337－350.

[27] 胡勋，孟祥武，张玉洁.一种融合项目特征和移动用户信任关系的推荐算法[J].软件学报，2014(8):1817－1830.

[28] YUAN Q，CONG G，SUN A X.Graph－based point－of－interest recommendation with geographical and temporal influences[C]//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management，Shanghai，China，2014:659－668

[29] 朱郁筱，吕琳媛.推荐系统评价指标综述[J].电子科技大学学报，2012，41(2):164－175.

[30] ZHANG J D，CHOW C Y，GSLR I.Personalized geo－social location recommendation－a kernel density estimation approach[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，Orlando，USA，2013:334－343.

[31] ZHANG J D，CHOW C Y，CO Re.Exploiting the personalized influence of two－dimensional geographic coordinates for location recommendations [J].Journal of Information Sciences，2015，293(1):163－181.

[32] 昝欣，宗鹏，吴祈宗.高等院校教师人才流动的Markov－chain预测模型[J].南京师范大学学报(工程技术版)，2006(9):75－78.

[33] YING J J C，KUO W N，TSENG V S.Mining user check－in behavior with a random walk for urban point－of－interest recommendations[J].Journal of the ACM Transactions on Intelligent Systems and Technology，2014，5(3):1－26.

[34] 俞琰，邱广华.基于局部随机游走的在线社交网络朋友推荐算法[J].系统工程，2013，2(1):47－54.

[35] 徐建民，张猛，吴树芳.基于话题的事件相似度计算[J].计算机工程与设计，2014(4):1193－1197.

[36] 刘晓光，谢晓尧.一种结合遗忘机制与加权二部图的推荐算法[J].河南科技大学学报(自然科学版)，2015(3):48－53.

[37] 肖扬，王道平，杨岑.基于三部图网络结构的知识推荐算法[J].计算机应用研究，2015，32(2):386－390.

[38] 田芳.基于词语情感倾向的问句相似度计算[J].安庆师范学院学报(自然科学版)，2014(2):33－36.

[39] RAHIMI S M，WANG X.Location recommendation based on periodicity of human activities and location categories[C]//Proceedingsof the17th Pacific－Asia Conference on KnowledgeDiscovery and Data Mining，Gold Coast，Australia，2013:377－389.

[40] 王国霞，刘贺平.个性化推荐系统综述[J].计算机工程与应用，2012，48(7):66－76.

[41] 刘树栋，孟祥武.基于位置的社会化网络推荐系统[J].计算机学报，2015，38(2):322－336.

责任编辑:时凌

Review of Research on Recommendation System

ZHANG Suzhi，ZHAO Yanan，YANG Rui
(School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002，China)

With the rapid development of information industry，the scale of information resources presents a geometric expansion，how to find useful information in this huge amount of data becomes an urgent problem to be resolved.One of the main ways to solve the overloading of Internet information is recommendation.Although many recommendation algorithms have been developed over the years，more intelligent recommendation system has been built.However，there are still many problems，recommendation algorithm is still a hot topic.This paper introduces the main current recommendation algorithms，points out the shortcomings，and illustrates possible future research directions.

information overload；recommendation algorithm；depth learning；data mining

TP393

1008－8423(2017)01－0001－06

10.13501/j.cnki.42－1569/n.2017.03.001

2016－11－24.

国家自然科学基金项目(61201447).

张素智(1965－)，男，博士，教授，主要从事Web数据库、分布式计算和异构系统集成的研究.