基于地理位置和上下文偏好的使用Geos社会网络的推荐系统

1、基于地理位置和上下文偏好的使用Geo社会网络的数据的推荐系统摘要随着基于位置的社会网络逐渐流行，我们拥有了一个研究基于用户历史位置信息发现用户偏好的良好平台。在本文中，我们提出了一种基于位置和上下文偏好的推荐系统，该系统可以结合地理空间上的两方面的信息，为特定的用户推荐一系列的场所（如餐馆），该系统需要考虑的信息包括：1）用户偏好，用户偏好可以通过从用户的历史位置信息自动学习到；2）社会评价，这个通过Local experts在位置信息中挖掘得到的。本文的推荐系统不仅可以在用户的生活活跃区而且也可以在一个陌生的城市对人们的旅行进行帮助。由于一个用户访问地点数量的限制，用户位置矩阵是非常稀疏的，

2、对于传统的基于协同过滤算法的推荐系统来说是一个巨大的挑战。矩阵稀疏问题对于一个刚到新城市的用户来说更加严重。最后，我们提出了一种新颖的位置推荐系统，该系统主要包括两个方面：离线模型和线上推荐。离线模型部分是通过类别层次权重（weighted category hierarchy,WCH）为用户的个性化偏好进行建模并且推断出每个用户对于一个城市的知识通过不同类别的位置，根据用户位置历史信息使用迭代学习模型完成。在线推荐部分在地理空间上选择候选Local experts，Local experts匹配了用户的偏好通过使用一种感知偏好候选选择算法，并且之后在基于已选择的Local experts评价

3、意见中，推断出一个对于候选位置的评分。最后，为用户推荐出top-k的位置排名。我们的系统是在一个真实的大的数据集上进行评价的，该数据集搜集于Foursquare。我们的推荐结果比baseline推荐算法的效果更好，同时也可以退位置进行推荐。关键字：基于位置的社交网络，基于位置的服务，用户偏好，推荐系统简介随着位置信息获得技术和无线通讯技术的发展，使得传统社会网络上可添加地理位置信息，滋养出一批基于位置的社交网络服务（LBSN），例如，Foursquare，Loopt,和GeoLife，在这些应用服务上，用户可以非常轻松地通过手机设备在现实世界中将自己的精彩生活分享出来。例如，一个用户可以在一个

4、LBSN的站点对一家饭店的服务进行评价，之后在其他用户去这家店时，就可以通过她的社交构成结构获得这条评论。地理位置信息作为用户上下文中重要组成之一隐含了大量信息，包括用户个人兴趣以及行为，这就提供给我们一个机会，那就是更好的了解用户在一个社交结构中，不单单是用户的线上行为，而且包括了用户在现实生活中的流动性和活跃度信息。例如，如果一个人经常去体育馆，说明这个人很有可能细化体育锻炼，如果一个人经常去一家饭店去吃晚餐，则说明很有可能喜欢类似口味儿的饭店。有时，一些在物理位置上没哟交集的人可能仍然是有联系的，只要他们访问过相同类别的地方就可以表明这些人有一种相同的兴趣爱好，如到海边或者到博物馆。在这

5、种情形下，基于位置的推荐系统是非常有价值的，基于位置社交网络服务已经在【16,25】两篇文章中有实现，特别的，位置推荐给一个用户提供一些场所（例如一个意大利餐馆或者是用户喜欢的电影院），这些场所满足在地理位置上满足了人们的兴趣需求【25】。当人们在一个陌生的地方旅游时，这种应用是非常有用的。然而，一个高质量的位置推荐系统必须同时满足一下三个因素：1）用户偏好：例如，一个吃货会对一个高质量的饭店有兴趣，而一个购物狂会将更多的注意力集中到附近的购物店【17】。2）用户的当前位置：要想给用户推荐用户最感兴趣的位置，当前用户位置信息直接指出了用户的空间范围对于候选场所，并且可能会影响推荐的排名情况【1

6、4】。3）其他用户对一个地点的意见：来自周围用户的社会意见对于推荐是非常有价值的【9】。但是一些大众喜欢的场所不一定符合一个特别的用户的口味。在LBSN上使用一个用户的位置历史信息，推断计算出一个位置的分数是一件非常困难的事情。首先，一个用户只能访问到有限个物理位置，这种稀疏矩阵问题在位置推荐系统中经常出现，例如【14】【9】，这些推荐方法都是基于物理位置的协同过滤的算法模型上的。其次，为一个没到过几个位置点的用户在新的城市中推荐位置是一个很艰巨的任务（而这时人们往往又是最需要位置推荐的）。例如，在图1中，a和b绘制出了位置信息（根据在Foursquare上的提示数据），这些位置信息是来自纽约

7、的人们访问洛杉矶和纽约的分布情况。很明显，访问洛杉矶的纽约人很少，在他们的地理位置信息中，只有0.47%的数据信息这种现象在现实世界中是普遍存在的【20】。对于位置推理评分来说（如果我们想为纽约人推荐在洛杉矶的地理位置），这种现象加重了数据的稀疏性。在这种情况下，单独使用CF模型是不适合的。首先，我们不能简单的将用户的来自不同城市的位置历史信息放到一个用户位置矩阵中，这种方法既没有效果也没有可扩展性。其次，在每个城市分别得使用协同推荐的方法不能处理新增城市问题，在图1中显示的问题。原因是 一个用户通常不会有足够的位置历史信息在一个新的城市里。基于此，我们提出了一个基于位置和用户感知偏好的推荐系

8、统，该方法提供给特定的用户一个场所集合，这些场所在用户能够接受的地理空间范围之内，并且满足前面提出的3个要考虑的因素。通过基于用户位置历史分类信息对用户偏好进行建模在LBSN中，我们的推荐系统不仅可以在人们生活的附近帮助他们，而且还可以在一个陌生的城市帮助他们。构建位置推荐的两大难点是：1）学习用户的偏好。首先，一个用户的偏好往往是各种兴趣的一个合体，比如用户偏好可能是购物，看电影，骑车，艺术等兴趣的合体。一个用户的偏好并不是一个简单的二项选择，例如，是喜欢还是不喜欢一些事物，并且，用户偏好是有粒度的，如，“食物-意大利食物-意大利面”。再者，用户的偏好是随着时间的变化而变化的。人工指定用户的

9、偏好是不实用的。因此，根据用户的位置历史信息对用户偏好进行建模是件有挑战的事。2）为一个用户推断一个没有访问过的地点的评分。评分的推断需要两个方面的考虑，一个是用户偏好，另外一个是其他用户的意见，尤其是Local experts【2,13】。以及用户间的相似度。这种推断要求三方面的计算：a）预测一个用户的专业知识b）计算用户之间的相似度c）将社交意见对于一个地点的推断协同到前面两者计算的合并结果中，例如使用系统过滤模型【8】【12】，他们彼此之间是相互联系的。现将我们的成果贡献总结如下：1. 我们从一个用户的历史位置信息中学习用户偏好，并且使用类别层次权值(WCH)对偏好进行建模。我们将会估计

10、两个用户偏好之间的相似度通过计算两个用户的WCHS的相似度得到。这个方法用于对用户偏好进行建模并对位置稀疏问题进行解决。2. 我们提前计算和提取Local expert对一个城市的每个位置类别，使用一个建立在用户位置历史信息的迭代推理模型，这使得我们的在线推荐过程效率增强。3. 我们在线推断一个场所的评分结合Local experts 选择的候选集，这些候选集是通过偏好感应候选选择算法和CF得到。这个算法可以实时给用户一个地理位置，并且还能考虑到用户的当前位置，偏好粒度，从Local experts中的意见。4. 我们评估我们的系统使用真实世界的数据，数据来源于Foursquare，包括221

11、,128个位置点信息，这些位置信息在纽约，由49,062个用户产生，104478个在洛杉矶由31544个用户产生的位置信息。我们的实验结果说明我们的位置推荐比baseline方法更有效果。第二部分给出概述，第三部分和第四部分是系统实现的主要部分：离线模型和线上推荐。第五章是讨论，第六章是总结相关工作。最后是总结全文。2概述这节首先介绍关键的数据结构，之后介绍了应用场景和位置推荐系统的整体架构。2.1 准备在图2中显示出五个关机的数据结构：1）user，2）venue，3）check-in，4）user location history，5）category hierarchy。在一个基于位置的

12、社交网络中，一个用户u需要维护他的个人信息，如ID，姓名，年龄，性别，籍贯等。同时，当用户到达一个场所，并在LBSN中，在该场所进行签到，那么该用户可以标记该场所（如餐馆）并对其进行评论，一个用户可以访问多个地点并可在每个地点进行签到，如图2 a)中实线部分。用户的所有签到信息影响该用户的在现实生活中的位置历史信息，像在squares地图描述的那样，一个场所的位置信息与一对地理位置坐标和表示其功能的一组类别相关联。场所的类别有不同的粒度，如图2a）底部所示。例如，食物类别包括中国餐馆和意大利餐馆等。在本系统中，我们使用从Foursquare获取的两层类别层次，如图2b）所示。2.2应用场所图3

13、显示了一个我们的应用场景，在这个场景中，有N=10个场所匹配了用户的偏好，这些场所是基于当前视角geo-地区进行推荐的，在此，推荐场所的数量以及地理区域的规模是由用户决定的（通过放大缩小地图区域，同时推荐地点的排名是在后天系统中完成的，根据用户位置信息和其他用户的意见）。通常，属于一个类别推荐位置的数量是根据用户偏好的类别分布而定的。例如，一个用户（用户的位置如图3中钉子所在）的最喜欢的位置类别是“中国餐馆”，第二个喜欢的是“购物中心”，那么，在图3 a中，那么“中国餐馆”的推荐力度就比“购物中心”的大，当这个用户在唐人街时。当我们将位置定位到第七街时，如图3b所示，购物中心将会最主要的推荐选

14、项，尽管中国餐馆是用户的第一兴趣，即跟用户所处的地理环境有关系。原因是根据人们在特别区域的位置历史记录，购物中心比中国餐馆更有价值。这是对个人偏好和社会评价的一个权衡。2.3 系统结构离线模型：离线模型主要由两个方面构成：1）社会知识学习；2）个人用户偏好发现。如图4下半部分所示。对于社会知识学习过程，每个用户在每个类别的专业知识根据用户位置历史信息得到。给一个预先定义好的类别层次，如图2b，我们将用户在一个城市中的位置历史信息break出来并分到不同的位置类别组中。之后，我们对每个位置历史信息类别组使用用户位置矩阵进行建模，在矩阵中，每个条目指示一个用户对地点的访问次数。通过应用一个迭代的推

15、断模型对每个用户位置矩阵，我们计算出一个得分W.r.t是对每个用户的一个类别，表示一个用户在一个城市中的类别的专业知识。通过对类别得分进行排序，我们可以发现在一个城市中的不同类别的Local experts。每个用户的推断知识将会在之后的感应偏好候选算法中使用，以及对在线部分产生高效地推荐而使用较少的计算。对于第二部分模型，即个人偏好发现，每个用户的个人偏好使用一个WCH，利用位置类别信息根据用户的位置历史，使用这种方法可以克服数据稀疏问题。特别地，一个WCH是一个预先设定的类别层次的子树，每个节点携带了关于用户访问一个类型的次数。这些值将被进一步规范化在每一个使用TF-IDF的WCH层在线推

16、荐模型：在线推荐部分给每个用户提供了一个场所列表，考虑每个用户的偏好，当前的位置，来自被选择的Local experts的社会评价，具体细节分成两个部分：1）感知偏好候选选择。这个部分是选择一个Local experts集合，这些experts是访问过这些场所，这些场所是在用户的推荐范围R之内的，并且在用户喜欢的类别中，这些experts有一个很高的专业知识。一个感知偏好候选选择算法被构造出来是为了适当的选择Local experts从不同的类别，这些类别是根据一个用户的不同的偏好权重在用户的WCH中的取得。2）位置评分计算。这部分第一个要计算的是每个被选择的Localexperts和用户的相

17、似度，相似度的计算是使用相似度函数基于他们的WCHs。计算相似度得分将会被引入到CF模型中，计算出一个评分用来预测该用户对一个未访问过的场所的喜好程度。之后，这些场所推荐得分将会被返回到作为推荐部分的内容。3离线模型在这个章节中，我们的离线模型包括：1）社会知识学习，这个是评价一个用户的专业知识并发现一个城市中的Local experts；2）个人偏好发现。这个事提取出一个用户的偏好从他的位置历史信息中。3.1 社会知识学习为了识别一个位置类别的Local experts，比如像“中国饮食”，“购物中心”等类别，这个部分要计算一个用户在不同城市中的每个类别，以封装在用户位置历史信息为基础。直观

18、的，一种类别的Local experts能够比普通用户发现高质量的该种类型的场所。再者，使用Local experts我们可以忽略一些极少的用户，这些用户只有很少的数据信息在位置类别上。这样就可以减少一些不必要的在线计算量。在我们的方法中，我们首先将说的用户位置历史信息进行分割，通过城市来分割，因为一个用户的的知识一般是通过地理信息得到的。例如，一个纽约旅游experts也许对北京的一些有趣的场所是不清楚的。再者，用户也许在不同的位置类别中有不同的知识储备，比如，一个喜欢“中国餐饮”的用户不需要知道太多关于“意大利餐饮”的知识，这样，我们进一步分割用户在一个城市中的那些用户访问过的位置历史信息

19、。最终，一个城市中有n个用户-位置矩阵，其中，n是预定的类别的总数。之后，我们应用HITS（超文本诱导主题搜索），基于推荐模型【4】【10】，对每个基于类别的的用户位置矩阵，推断出一个用户对于该类别的专业知识程度。如图5，本方法认为一个用户对一个场所的访问产生一条从用户到场所的有向边，每个用户有一个hub score来代表他的知识水平，每个位置被用户连接，其拥有一个authority score用来表示他的兴趣度。【29】这样，那些在同一地区访问过许多高质量的场所的人就有丰富的关于这个区域的专业知识。反过来，一个被许多拥有专业知识的人访问过的场所就是高质量的场所。这样，如公式1和2 所示，一个

20、用户的专业知识能够使用被该用户访问过的场所的authority score（例如兴趣等级）之和进行计算，一个场所的的兴趣等级可以使用那些访问过该场所的用户的Hub score之和进行计算。使用一个强大的迭代推到方法，我们产生了一个最终的对于每个用户和每个场所的得分公式，那些拥有高authority score的用户被认为是Local experts在这个类别中。其中，代表在类别c中用户u的Hub score，代表场所v的authority score。我们定义分别代表在第n次迭代的authority scores和Hub scores，M代表用户-类别矩阵，那么最终的结果是：其中，我们初始化a

21、uthority和Hub score使用一个用户访问的次数。?3.2 个人偏好发现我们提取用户的偏好是通过用户访问的地点的类别得到的。如图6，首先，我们构建一个用户位置历史信息根据所有的已经预定义好的类别层次的城市，那些节点出现的层次越低说明划分粒度越细。这样，每一个节点和一个值联系起来，这个值代表一个用户对于一个类别的访问次数。在实际中，一个人的偏好是由多重兴趣构成。（比如购物和徒步旅行），而这些多重兴趣又有不同粒度的划分，例如，“餐饮”-“中国餐饮”。第二，我们计算了在一个层次中每个节点的TF-IDF值，其中，每个用户的位置历史信息看做一个文档，类别认为是在该文档中的一个条目。直观上看，一

22、个用户喜欢一个地点的类别，那么他将经常访问这种类别的地方。更进一步，如果一个用户经常访问一个其他用户很少访问的地方，那么该用户会更喜欢属于这种类型的地方。例如，餐馆的访问次数就远比像博物馆这样类别地方的多。这并不意味着餐饮就是所有人的第一大兴趣，这时，如果发现一个用户经常去访问博物馆，那么他的兴趣领域很可能是艺术或历史方面的。总之，一个用户的偏好权重可用公式5进行计算，其中，第一部分的等式是在一个用户的位置历史中类别c的TF值，第二个部分代表一个类别的IDF值。其中，是一个用户在类别c中访问的个数，是代表用户总体的访问次数。代表在系统中访问过类别c的用户数，经过计算之后，使用IDF，计算WCH

23、，中国餐馆不再是用户的第一兴趣，颜色变浅。这个WCH代表了用户的兴趣。就有下面的有优点：1）由于不同的用户有不同的数据规模，使用WCH可以不用考虑数据规模2）可处理稀疏数据的问题，并可减少计算下面介绍的用户相似度计算量3）可以计算用户间的相似度，这些用户是没有任何物理位置信息的，如生活在不同的城市。4 在线模型在线模型主要包括：1）感应偏好候选集选择。这个根据用户的偏好选择候选Local expert。2）地点评分计算。这是指一个候选地点的预测评分，基于CF推断模型，使用相似度对用户和被选择的Local experts进行比较。4.1 偏好候选集选择这个部分选择一组候选Local expert

24、s和场所在用户指定的地理范围内，使用我们的偏好候选选择算法（如算法1所示），该算法可以保证候选地点符合用户指定的个数并且候选Local experts也匹配用户的偏好。特别的，用户制定一个地理范围R，这个算法一开始检索位于这个地理范围的的场所集合V和访问过这些场所的用户集合U（第1,2行）。候选Local experts选择过程从个人的WCH的底层进行初始化，如果候选场所的数目没有达到要求的推荐的数目则将移入上一层。当在WCH的一层中选择好了场所，我们将选择一个节点（一个类别），这个节点具有最小值，之后，我们计算一个k值使用来决定我们要在这个类别中国要选的Local experts的个数，之后

25、，前k个拥有高Hub score的用户在类别c中的被选择出来作为候选experts e （第7-8行），那些分布在R范围内的并被e中的用户访问过的场所将会被加入到V中，之后，候选experts集合e和集合E合并（第9-11行）。算法会在我们获得了一个足够数量的场所集合或者所有在R范围内的用户都被检索完成时结束。作为结果，一个地点集合V和一个Local experts结合E将被返回。4.2位置评分推断第一步：用户相似度计算。在这一步中，我们将要计算一个提出推荐请求的用户和Local experts E中的每个expert计算相似度得分根据他们的WCHs。因为从本质上看，WCH是一颗树，我们计算两个WCH的相似度，通过哪些树中重叠的节点。特别的，我们分解两个WCHs的相似度作为一个权重和，这个和是在每一WCH中对应的层次的相似度，例如。层次越深权重越大，这样符合用户的偏好。更进一步，连个不同的WCH的同一层的相似度是通过下面两个方面计算：一方面是在同一层中重叠的个数和他们的值，如等式6所示。两个WCH重叠的个数越多，两个用户就月相似。最小的重叠节点c的偏好权重会被选出来作为两个用户的共同兴趣。另外一个部分是每个层次的熵，这个熵可以有效的计算一个用户偏好的多样性【7】，如等式7所示。其中，是一个户