LBSN中基于聚类的二分图网络推荐算法

来源:用户上传      作者:

　　摘  要：兴趣点推荐是基于位置的社交网络（Location Based Social Network，LBSN）的重要服务，近年来关于兴趣点推荐的算法深受学者关注，然而由于多方面的原因，许多推荐算法仍存在一些不足。该文提出的是在用户聚类的基础上利用二分图网络进行推荐的算法。实验表明，该算法取得了比较良好的推荐效果。
　　关键词：基于位置的社交网络  聚类  二分图网络  兴趣点推荐
　　中图分类号：TP391.3    文献标识码：A 文章编号：1672-3791（2019）12（a）-0018-02
　　近年来随着移动互联网技术的飞速发展， 基于位置的社交网络（Location Based Social Network，LBSN）也得到迅猛发展[1]，如Foursquare、Gowalla、微博等，与传统社交网络最大的区别就是有了地理位置信息，用户可以对自己访问过的兴趣点进行签到，并且可以随时分享给好友。LBSN的服务宗旨就是要为用户推荐一些新兴趣点，帮助用户更好地发现生活乐趣，同时还能促进兴趣点相关的商业发展，具有重要的意义。
　　个性化的推荐技术在不同应用领域也受到广泛关注，然而用户面对生活中庞大的信息量做选择时还是有些迷茫，用户所想要的是可以根据其所处的状态信息给出一些个性化的兴趣点推荐，但是LBSN中的签到密度通常较为稀疏，给兴趣点推荐带来了困难。因此兴趣点推荐的研究仍需要进一步探索。
　　1  相关工作
　　基于位置的社交网络推荐技术发展至今已经有了不少进展。高榕等人[2]在矩阵分解的基础上利用兴趣点的评论信息、用户社会关系以及地理信息这3种因素推荐兴趣点。LIU等人认为用户属性、兴趣点属性以及兴趣点间距离共同决定着用户评分，因此构建了贝叶斯图模型给用户推荐他们可能喜欢的兴趣点[3]。以上的这些研究整体上来说都是在所有用户签到信息的基础上利用各种签到信息进行推荐。
　　有学者研究表明聚类方法可以降低推荐算法的计算复杂度[4]，同时有研究表明用户签到的兴趣点类型与时间有一定的关联度[5]，利用二分图网络模型的相关算法[6]可以很好地把签到信息中的用户、兴趣点、时间这3个重要信息很好地联合起来，对于研究在特定时间给用户推荐兴趣点有重要意义。
　　2  基于用户聚类的二分图兴趣点推荐
　　2.1 基本定义
　　在LBSN中，u是用户集合U中的一个用户，l是兴趣点集合L中的一个兴趣点，cui=1表示用户签到过（或者是访问过）兴趣点l，cui=0表示没有签到。t是时间集合T中的一个时间段，可以划分为几个连续时间的时间段，以时间段作为时间单位。因为在实际生活中，很少有用户在一天的0：00到6：00这个时间段有簽到活动，所以该文只考虑从6点开始到晚上24：00的这段时间。
　　定义1  用户相似度：用户相似度是由常用的余弦相似度cos（u，v）和用户之间本身存在的好友关系trust（u，v）结合起来由α平衡两者的权重影响从而计算得到的：
　　Sim（u，v）=α*trust（u，v）+（1-α）*cos（u，v）                        （1）
　　其中
　　 （2）
　　trust（u，v）是用户之间的好友关系值
　　，u和v是好友关系                           （3）
　　，u和v不是好友关系
　　定义2  用户-兴趣点二分图网络：令G（U，L，E）表示一个二分图网络，其中U代表用户节点集，L为兴趣点节点集，E为用户-兴趣点二分图边集，每一条边表示用户签到过此兴趣点。假设用户节点数|U|=m，兴趣点节点数|L|=n，则节点总数为r=m+n。
　　定义3  时间-兴趣点二分图网络：令G（T，L，E）表示一个二分图网络，其中T代表时间节点集，L为兴趣点节点集，E为时间-兴趣点二分图边集，每一条边表示在该时间段有用户签到过此兴趣点。
　　2.2 用户聚类
　　为了提高推荐结果国的有效性和准确性，首先需要用户聚类，从中找出聚类结果中的有用信息，为下一步的联合推荐奠定基础。为了保证比较好的聚类结果，我们借鉴k-means算法的思想，提出了比较有效的聚类算法。该聚类算法的具体步骤如下。
　　（1）基于定义1计算出来的用户相似度，按照从大到小选出和其他用户相似度总和处于前p位的用户作为用户聚类中心。
　　（2）利用用户相似度判断每个用户与哪个中心用户的相似度最大，然后就可以把除用户聚类中心以外的所有用户加入到与它有最大相似度的中心用户中。
　　（3）直到所有用户都加入到对应的用户聚类中心时算法终止，所有用户成功聚类到p个用户群体中。
　　2.3 基于二分图网络物质扩散的推荐
　　在二分图中基于物质扩散的推荐算法相当于传统推荐中的随机游走算法，它将视野汇聚在那些较流行的节点上， 倾向于推荐较流行的物品，从而提高推荐的精确性。图1是一个典型的二分图网络。该文中用到了定义2和定义3的两个二分图。
　　下面我们以用户-兴趣点二分图网络为例描述对应的物质扩散推荐算法：
　　定义用户节点集U={0，1，2，…，m-1};兴趣点节点集L={0，1，2，…，n-1}。物质扩散算法在整个传递过程中，每个节点的资源都是通过二分图中的边均匀传递，总资源始终不变。算法可以分为以下三步。 　　（1）对目标用户签到过的兴趣点节点赋予一个初始的资源αul=cl=1，否则αul=cl=0。
　　（2）兴趣点节点资源通过二分图中的连边均匀地分配到所有签到过该兴趣点的用户节点。用户节点对从不同兴趣点得到的资源值进行累加，从而求得用户u得到的资源值bu。
　　（4）
　　k（Ol）为二分图中兴趣点节点l的度。
　　（3）所有用户的资源值也将通过二分图中的连边均匀地分配到他们签到过的兴趣点节点。兴趣点节点对从不同用户得到的资源值进行累加，从而求得兴趣点l得到的资源值：
　　（5）
　　k（Ou）为二分图中用户节点u的度。
　　在给定目标用户的情况下，通过上面的算法就可以求得所有興趣点节点的资源值。同理，在时间-兴趣点二分图网络中，我们也可以在给定时间的情况下，利用物质扩散算法求出所有兴趣点节点的资源值c''l。
　　2.4 联合推荐
　　给定用户u和时间t，然后给用户u推荐他感兴趣的兴趣点。我们利用用户-兴趣点、时间-兴趣点二分图网络分别通过物质扩散算法得到目标用户相应的兴趣点资源值c'l和时间段相应的兴趣点资源值c''l。为了进一步提高推荐的准确性，因此我们通过引入的可调节参数λ∈[0，1]调节这两个网络的影响权重：
　　cl=λc'l+（1-λ）c''l                                                         （6）
　　然后按照兴趣点资源值cl的大小降序排列，选取前top-k个未签到过的兴趣点推荐给目标用户u。
　　3  实验与分析
　　3.1 实验数据集
　　该文实验所用的数据集是Gowalla公开数据集，此数据集中每条签到记录提供的信息有用户ID、兴趣点ID、签到兴趣点的经纬度坐标以及签到时间，此数据集总共包含6442882条用户签到记录。在该文中对该数据集经过预处理后，得到了包含18737个用户对32510个兴趣点的总共1278274条签到记录，所有的签到记录按从6点开始到晚上24点按每6个小时划分一个时间段，总共划分3个时间段。整个数据集按签到时间顺序选取了70%的数据作为训练集，剩下的30%作为测试集。
　　3.2 评价指标
　　在兴趣点推荐问题中，一般采用准确率（precision）和召回率（recall）来评价算法的推荐效果。在该文中先要计算每个时间段的准确率和召回率，计算公式如下：
　　（7）
　　 （8）
　　其中R（ut）是算法给用户u在t时间推荐的兴趣点结果，F（ut）是测试集中户u在t时间真实签到的兴趣点结果。
　　接下来可以通过求所有时间段准确率和召回率的平均值得出整体的准确率和召回率，计算公式如下：
　　（9）
　　 （10）
　　3.3 实验结果与分析
　　该文算法的所有的实验都是取p=3个用户聚类中心开始的，在得到用户的聚类结果后开始给聚类结果中的每个用户进行推荐。首先评估了公式（6）中λ参数对推荐结果的影响，从中得出参数λ取值0.7时推荐效果最好。
　　接下来把该文的推荐算法与包含时间信息的协同过滤方法（CF-T）进行对比和分析，此次对比实验中我们的算法对公式（6）中的参数λ取值0.7，以便实验效果达到最佳。此次对比实验针对的同一数据集，推荐兴趣点个数k分别取值5、10、15、20这4种情况，就这两种推荐算法的准确率和召回率进行对比（见图2、图3）。
　　实验结果显示，随着推荐兴趣点个数k的增长，两种算法的准确率（precision）开始降低，召回率（recall）逐渐升高，符合预期的实验效果。同时也可以看到该文提出的基于聚类的二分图网络推荐算法不管在准确率还是召回率方面都明显优于CF-T推荐算法。
　　4  结语
　　该文首先通过引入聚类算法对用户聚类，降低了与目标用户不想似的其他用户对推荐结果的干扰，之后在用户、兴趣点、时间构成的两个二分图网络利用物质扩散算法进行联合推荐，实验结果表明该文算法取得了预期效果，但是如果能考虑兴趣点种类、用户性别等因素，将更有利于实现个性化的推荐，提高推荐效果。
　　参考文献
　　[1] Zheng Y，Zhou X.Computing with Spatial Trajectories[M]. Springer New York，2011：243-276.
　　[2] 高榕，李晶，杜博，等.一种融合情景和评论信息的位置社交网络兴趣点推荐模型[J].计算机研究与发展，2016，53（4）：752-763.
　　[3] Liu B，Fu Y，Yao Z，et al. Learning geographical preferences for point-of-interest recommendation[A].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining[C].2013：1043-1051.
　　[4] 郑怀宇.基于用户聚类的二分图网络协同推荐算法[J].沈阳工业大学学报，2018，40（3）：316-321.
　　[5] Yuan Q，Cong G，Ma Z，et al.Time-aware point-of-interest recommendation[A].International Acm Sigir Conference on Research & Development in Information Retrieval.ACM[C].2013：363-372.
　　[6] 陈桂林.基于物质扩散的个性化推荐算法研究[D].北京邮电大学，2018.
转载注明来源:https://www.xzbu.com/8/view-15125034.htm