LBSN中基于聚类的二分图网络推荐算法
摘要：兴趣点推荐是基于位置的社交网络（Location Based Social Network，LBSN）的重要服务，近年来关于兴趣点推荐的算法深受学者关注，然而由于多方面的原因，许多推荐算法仍存在一些不足。

该文提出的是在用户聚类的基础上利用二分图网络进行推荐的算法。

实验表明，该算法取得了比较良好的推荐效果。

关键词：基于位置的社交网络聚类二分图网络兴趣点推荐
近年来随着移动互联网技术的飞速发展，基于位置的社交网络（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计算出来的用户相似度，按照从大到小选出和其他用户相。