相关电子技术论文

相关标签

基于分层结构的兴趣点推荐算法的设计与实现

发布时间:2019-12-04 12:14

  摘要

  随着基于地理位置的社交网络(Location Based Social Networks,LBSN)的迅速发展,兴趣点(Point Of Interest,POI)推荐已经成为了一个重要的研究问题。然而POI推荐会受到时间和地理位置的影响。此外,现实世界中的推荐系统的POI呈现出一定的分层结构,同样,用户的偏好的也会呈现分层结构。最近的研究表明,结合项目或用户偏好的分层结构可以提高推荐系统的性能。显式的分层结构例如用户偏好通常是不可用的,因此,分层结构并没有很好地应用到推荐系统上。

  本文首先研究了时间和地理位置对POI推荐的影响。设计和实现了一种分层结构的POI推荐算法HMF-G(Hierarchical Matrix Factorization-Geographical),来获得用户和POI之间的隐式分层结构。在两个现实世界的数据集,Foursquare和Gowalla上的实验结果证明了所提出的算法的有效性。

  关键词:推荐算法;兴趣点;分层结构

  前 言

  城市的迅速发展带来了数量越来越多的兴趣点(Point of Interest,POI),例如餐馆,商店,酒店,为我们提供了越来越多的体验生活的机会。日常生活中,人们乐意去探索城市和社区,并根据自己的个人兴趣决定“去哪里”。与此同时,如何在大量的POI中做出令人满意的决定也成为了用户的一个棘手的问题,俗称“选择困难症”。POI推荐任务旨在帮助用户过滤用户不感兴趣的POI来缩短其决策时间。

  基于位置的社交网络(Location Based Social Network,LBSN)已经吸引了数百万用户在他们中意的兴趣点签到,并与朋友分享他们访问这些POI的体验。例如,截至2014年12月,Foursquare拥有超过60亿的签到信息,每天有5千5百万用户进行数百万的签到。这些历史签到信息包含了关于用户和POI的丰富的信息,为挖掘用户的POI偏好并进行POI推荐提供了新的机会。

  POI推荐易受时间和地理位置的影响。在不同的时间内,用户有着不同的POI偏好。同时用户的地理位置也对用户访问POI产生了约束。而且,POI往往呈现出一种分层结构,例如餐馆类的POI往往还分为中餐,西餐,咖啡厅等,博物馆类的POI还可以分为历史博物馆,艺术博物馆,科学博物馆等。同理,用户的POI偏好往往也呈现出一种分层结构,例如用户往往只喜欢去中餐类的餐馆。

  本文研究了时间和地理位置对POI推荐的影响,以及如何将时间因素和地理因素纳入到POI推荐中。同时,本文还深入研究了用户和POI之间的分层结构的关系,并提出一种全新的算法HMF-G来捕获用户POI的分层结构。并进行了实验验证。本文的完成主要工作如下:

  (1)探讨了时间对POI推荐的影响,提出将数据集按不同时间段进行切片来处理时间因素的方法。

  (2)探讨了地理位置对POI推荐的影响,采用一种地理区域筛选的方法将地理因素纳入到POI推荐中。

  (3)研究用户POI之间的分层结构,提出一种算法HMF-G来对用户POI的分层结构进行建模。

  (4)在两个数据集(Foursquare和Gollawa)上对进行实验,并于其他几种POI推荐算法进行比较,实验结果证明了(3)中所提出的算法的有效性。

  第一章 绪 论

  本文首先介绍了POI推荐的研究背景和意义,之后简单介绍了POI推荐的特点和影响因素,并详细地说明了本文的主要工作。在本章的最后,介绍了一下本论文的组织结构。

  1.1 研究背景及意义

  随着具有无线通信和定位功能的移动设备的迅速普及,一些基于位置的社交网络(Location Based Social Network,LBSN)的互联网应用,例如Foursquare,Gowalla,Brightkite,Yelp和Facebook已经越来越受到人们的欢迎,并吸引了数百万人的用户。LBSN具有将物理世界和虚拟世界联系起来的功能。兴趣点(英文:Point of Interest,POI)即电子地图的某些地标,例如餐馆,商店和电影院等,如图1.1显示了苏州市的部分兴趣点。

  在LBSN(下页图1.2)中,用户可以建立起彼此的社交链接,通过在某些地方用移动设备签到(check in)来向其他人分享一些他们所去过的兴趣点的体验心得。智能手机的锐增导致了LBSN的繁荣,Foursquare,Facebook Places和Yelp等LBSN现在越来越流行。直到2016年6月,Foursquare已经收集了全球包括80亿次签到信息和6500多万次的地形测绘业务。

  LBSN中有大量社区贡献的数据,包括用户彼此之间的社交关系,用户在POI上的签到信息,用户的地理位置信息和POI的种类。这些丰富的数据反映了人们在现实中的行为,并且为了用户访问POI的决策过程提供了新的机会。在LBSN中,根据从社区贡献的数据中了解到用户对POI的访问偏好,来向用户提供他/她可能感兴趣但之前未访问过的POI。POI推荐非常重要,一方面,它有助于当地居民或游客探索城市中一些有趣的未知地点。另一方面,还为POI的拥有者创造机会和商业利润,通过发现和吸引潜在的游客来增加POI拥有者的收入。

  事实上,LBSN服务中的关键就是准确和个性化的POI推荐。首先,考虑到大量的POI,用户很难通过有效的方式来找到他们喜欢的POI。个性化的POI推荐系统可以帮助用户轻松找到相关的POI,而无需花费太多时间进行搜索,特别是用户来到新地区时。此外,对于POI所有者说,向各种用户提供正确的POI也是非常具有挑战性的。个性化的POI推荐系统不仅能够减轻负担,还能通过推荐的POI来吸引更多的用户。

  1.2 POI推荐概述及研究现状

  POI推荐是LBSN中最重要的任务之一,它可以帮助用户在LBSN中发现新的有趣的地点。POI推荐通常会挖掘用户的POI签到记录,地点信息(如类别)和用户的社交关系,以推荐用户最可能在将来访问的POI列表。POI推荐不仅提高了用户对LBSN供应商的粘性,而且还为广告代理商提供了向潜在消费者发布广告的有效方式。具体来说,用户可以使用Foursquare探索附近的餐馆和市中心的购物商场。同时,商家也可以通过POI推荐让他们的目标用户轻松地找到他们。为了方便用户以及商家所提供的商机,POI推荐已经吸引了大量的关注,最近许多研究人员提出了一堆POI推荐系统。

  尽管开发POI推荐系统可以极大地使用户和POI推荐者都收益,但它仍然是一个非常的具有挑战性的问题。事实上,用户的签到决策过程非常复杂,可能会受到不同因素的影响。首先,用户访问POI很大程度上会受到朋友的影响。对于某些特定的POI,一些朋友可能会对用户访问该POI产生正面影响,然而另一些朋友可能会产生负面影响。此外,距离POI的距离也会影响用户对该POI的偏好程度。一般来说,用户喜欢去附近的POI而不是距离很远的POI。因此,模拟社交朋友关系和地理距离对用户访问POI的影响非常重要。另外,用户是否在POI签到可能取决于用户的具体目的。例如,当人们想吃午饭时,他们更想选择与食物相关的兴趣点而不是景点。

  基于记忆的协同过滤(Collaborative Filtering,CF)技术(例如基于用户的CF和基于物品的CF)经常被用于POI推荐。Levandoski[1]对基于物品的CF进行修改,将用户的旅行距离作为一个惩罚项,对学习的过程进行了优化。M. Ye等人[2]通过采用线性插值的方法将地理和社交关系影响纳入到基于用户的CF模型,显著的提高了推荐算法的准确性,而且社交关系对推荐系统的性能影响不大。

  基于记忆的CF很容易受到数据稀疏的问题的困扰,因为用户与用户或物品与物品的相似性需要根据用户平时的签到信息进行计算。当签到信息很少时,两个用户或物品之间将共享很少的签到信息,因此根据这些签到信息产生的相似性提供推荐结果是不可靠的。C. Cheng等人[3]引入一个多中心高斯模型来计算地理位置对推荐结果的影响,因为用户的平时的签到地点通常在几个中心附近,并将它与矩阵分解(Matrix Factorization,MF)结合起来用于兴趣点推荐。然而在这种方法中,MF仅通过适配非零的签到信息来执行,因此它容易遭受数据稀疏的问题。基于模型的CF技术也被应用于POI推荐,Noulas[4]发现对于POI推荐而言,MF比基于用户的CF和基于项目的CF的表现效果更差。在他们的研究中,他们将用于显示反馈数据的常规MF技术应用到POI推荐中,这种不适合POI推荐的方法导致效果不佳。B. Liu等人[5]提出了一个地理概率因素的分析框架,即GTBNMF,它结合了基于贝里斯非负矩阵分解的地理影响。但是BNMF是通过满足零和非零签到来执行的,因为零签到可能会缺失值,所以可能导致算法结果的不合理。所有的这些方法都不能反应出POI推荐的隐式反馈属性。

  与传统的推荐系统(如音乐推荐,电影推荐不同),POI推荐要考虑各种因素,例如用户对POI的内容偏好和受地理约束的空间偏好。J.-D. Zhang等人[6]通过核密度估计的方法对每个用户的个性化二维地理影响进行建模,预测出用户访问新位置的概率。D. Lian等人[7]将地理信息纳入到加权矩阵分解以提高POI推荐的有效性。

  1.3 本文的主要工作

  (1)提出一种将数据集按不同的时间段进行切片的方法,处理时间对POI推荐的影响。

  (2)对用户的活动区域进行建模,对最终推荐的不在区域内的POI进行筛除,该方法考虑了地理因素对POI推荐的影响。

  (3)提出了一种推荐算法HMF-G,它能够使我们在这些结构不明确可用的情况下捕获用户和POI的分层结构,并对其进行建模。

  (4)在两个大型的现实世界的数据集(Foursquare和Gowalla)上进行实验,并将结果与其他几种推荐算法进行比较。实验结果充分验证了(3)中所提出方法的有效性。

  1.4 本文的组织结构

  本文是一共分为六章,各章的内容如下:

  第一章:绪论。本章主要介绍了分层结构的兴趣点推荐的意义和研究背景,并简单介绍了POI推荐的特点和影响因素,而且还详细地说明了本文主要工作,最后介绍了本文的组织结构。

  第二章:相关技术介绍。主要介绍了常用的推荐算法,以及常用的推荐算法的评测指标。

  第三章:POI推荐的影响因素。本章详细地讨论了时间和地理位置对POI推荐的影响,并提出了对数据集进行切片和地理区域筛除的方法。

  第四章:分层结构的POI推荐算法。本章深入地讨论了POI推荐的分层结构,并以非负矩阵分解NMF为基础,提出一种HMF-G算法来对POI推荐的分层结构进行建模。

  第五章:实验分析。在Gowalla和Foursquare数据集对所提出的HMF-G算法进行了实验,并将实验结果与几种推荐算法相比较,实验结果证明了所提出的算法的有效性。

  第六章:总结与展望。对全文进行了细致性的总结,并思考了在本文中的一些不足的地方,提出了未来的工作的安排与期望。

  第二章 相关技术介绍

  本章对推荐算法的相关技术进行介绍,介绍了一些常用的推荐算法,如协同过滤算法和基于内容的推荐算法。并简单介绍了一下推荐算法常用的评测指标。

  2.1 推荐算法概述

  推荐系统中,最重要的技术所在就是推荐算法。对不同的推荐系统,需要认真考虑该选择何种推荐算法。到现在为止,已经有很多种类的推荐算法。每一种推荐算法都有它们的缺点和优点,而且,不同的算法也有其对应的限制条件。推荐算法一般都是建立了一个模型,用于推断用户感兴趣的项目。首先获取数据,例如用户偏好和可供推荐的项目的特征,然后推测哪些项目会迎合用户的偏好。

  2.1.1 基于协同过滤的推荐

  协同过滤(Collaborative Filtering,CF)是一种通过收集许多用户(协同)的偏好或口味信息来对用户的兴趣进行自动检测(过滤)的方法。CF的假设是,如果一个用户甲在某个问题上,和某个人乙有相同的意见,那么与其他随机选择的人的想法比起来,甲的想法可能和乙的更相似。简单来说,就是分析一群有着相似爱好的用户组的行为,来去判断相关用户的项目偏好。当我们想向用户推荐某些东西时,最合理的做法是找到和用户品味爱好相同的人,看看他们都选择了哪些项目,然后用户推荐相同的项目。或者我们可以查看和用户之前购买的产品类似的产品。协同过滤算法主要分为两种,以用户为基础的CF(User-Based CF,UCF)和以项目为基础的CF(Item-Based CF,ICF)。

  (1)基于用户的CF(UCF)

  UCF的主要做法是找到一群爱好相似的用户,即基于用户的(User-based)的CF或基于相邻者的CF(Neighbor-based Collaborativen Filtering)。用户与用户之间相似度通常用Jaccard公式或余弦相似度来计算。这样的话,两个用户的相似度可以更直观的观察到。设M(u)是用户u的中意的项目的集合,M(v)为用户v中意的项目的集合,则u和v相似度的计算公式为:

  UCF的具体方式为:通过收集有关用户的信息,了解用户的项目偏好。然后通过计算用户之间的相似度来找到与该用户相似的一组用户,用这组用户的偏好记录信息来预测该用户对相关项目的评分

  (2)基于项目的CF(Item-Based CF,ICF)

  随着用户数量增加,UCF所消耗的计算时间越来越多。2001出现另一种CF,即基于项目的协同过滤算法(Item-based Collaborative Filtering Algorithms)。ICF的基本假设为,若用户中意一个项目,那么,与该项目相似的其他项目也有可能引起用户的兴趣。项目之间的相似性用数学的方法进行计算。项目的相似度的计算公式为

  其中,|M(i)|是喜欢项目i的用户数,|M(j)|是喜欢项目j的用户数。

  ICF的方法步骤如下:收集相应信息,计算已评价的项目和预测项目的相似度,并以此为基础得到预测项目的预测分数,最终产生推荐结果。

  2.1.2 基于内容的推荐

  基于内容的推荐(Content-based Recommendation)方法来自于信息获取领域。原理为:根据用户已选的项目,从推荐的项目之中,选择其他特征与之相似的项目,并作为推荐结果。

  (1)第一步,获取推荐项目的特征,然后去和用户偏好相比较,匹配度较高的项目就可作为推荐结果。

  (2)重点是计算出项目特征和用户偏好的相似性。

  (3)通过计算出相应项目的评分值,并进行排序,将排名较高的项目作为推荐结果。

  描述项目特征和用户偏好是基于内容的推荐算法中的重点。这样避免项目的冷启动问题。

  2.2 推荐算法的评测指标

  2.2.1 准确性指标

  (1)分类准确度,指判断一个项目是否迎合了用户的偏好,并且结果正确的比例,包括召回率和准确率。

  设U为用户集,Ru为用户u的推荐列表,Bu为测试集中用户给予正反馈的项目。

  准确率,指在推荐的结果中,用户在现实中给过正反馈的项目所占的比例。单个用户u准确率为:2.2.2 非准确性指标

  (1)覆盖率。是指推荐结果中的项目占总项目集合的比例,这样可以观察推荐出的项目能不能很好的覆盖所有的商品,是不是每个项目都有机会被推荐。计算覆盖率的一种简单方法就是计算被推荐的项目数量占项目总数的比例。更精确的办法是用基尼系数和信息熵来衡量。较高的覆盖率也能反映出推荐系统有着较好的性能。

  (2)多样性。是指推荐出来的结果要有多样性,能覆盖到用户不同的兴趣领域。多样性可以基于项目间的相似度来计算,如果推荐出来的项目之间相似度较高,那么说明都是同一种类的项目,缺乏多样性。

  第三章 POI推荐的影响因素

  本章详细探讨了时间和地理位置对POI推荐的影响,并提出了相应的解决方法,即对数据集进行切片和地理区域筛选。

  3.1 时间的影响及解决方法

  时间影响对POI推荐至关重要,因为检查活动的物理限制导致了特定的模型。POI推荐系统中的时间影响主要表现在三个方面:周期性,连续性和不一致性。

  用户在LBSN中的签到行为呈现周期性模式[8]。例如,用户总是在中午签到入住餐厅,晚上在夜总会玩乐,用户还可以在周一至周日前往办公室周围的地方,并在周末花时间在购物中心购物。图4显示用户在一天内的签到频率的分布。非一致性特

  描述了用户在一天的不同时间的签到偏好差异。据观察,用户对POI的访问偏好在一天内的不同时间变化,用户最常访问的POI在一天内的不同时间发生改变。类似的时间特征也出现在一年的不同月份,以及一周的不同日子。这种非均匀特征可以从用户的日常生活习惯中解释:(1)早上,用户倾向于在用户家附近的POI签到,中午倾向于访问在办公室周围的地点,晚上倾向于在酒吧里消遣。(2)用户可以在工作日访问用户家附近或办公室周围的更多地点。在周末,用户可以在商场或度假地点签到。(3)在不同的月份,用户可能对事务和娱乐有不同的兴趣。例如,用户将在夏季的几个月去冷饮店,而在在冬季去火锅餐馆。为了在不同的时间为用户提供正确的POI推荐,本文采用的方法是将一天分成不同的时间片段,然后应用协同过滤技术分别在每个时间片段来推断用户对POI的偏好。具体的做法是根据用户的签到时间,将原有的数据集划分为四个子数据集,分别保存了用户在早上(6:00-12:00),午后(12:00-17:00),夜晚(17:00-22:00),深夜(22:00-次日6:00)四个不同时间段的签到信息。根据用户在不同的时间段的POI签到频率分布,预测出用户的POI偏好。

  3.2 地理位置的影响及解决方法

  地理学第一定律(Tobler’s First Law)指出:“任何东西都与其他的东西之间有着千丝万缕的关系,但是,附近的东西比远处的东西有更强的关系。”例如,一个人在现实生活中经常访问一个POI,例如博物馆,那么,他就更有可能去访问博物馆附近的POI,如一些餐馆和酒店。也就是说,近距离的POI比远距离的POI具有更强的地理相关性,地理上邻近的POI更可能具有相似的特征,另外,用户访问POI的概率与地理距离成反比。地理影响是区分POI推荐与传统物品推荐的重要因素,因为用户的签到行为取决于地理特征。对用户签到数据的分析表明,用户的活动范围通常受到了一些地理限制,并且,用户更倾向于访问用户签到处附近的POI。而且,对用户的签到行为产生的地理影响往往是因人而异的。例如,户内人士喜欢访问生活区周围的POI,而户外人士往往喜欢环游世界以探索新的POI。因此,在为用户推荐POI时,地理信息对个人的签到行为应该是个性化的。

  目前,有一些研究通过利用地理位置建议的影响来了解用户的偏好,然而这些研究使用位置之间的一维距离来进行推荐,例如认为用户访问POI的倾向与离POI的距离成反比。然而,将地理影响考虑到二维层面上才是更合理和客观的。而且,访问概率不仅受到距离的影响,还会受到位置的内在特征的影响,所以,用户访问每个位置的概率并不是单单被距离所影响。例如,实际上,用户的登记位置通常分布在若干区域。J.-D. Zhang等人[6],针对POI推荐的个性化二维地理影响,利用了核函数计算了每个用户的个性化二维签到概率密度的基本分布。下页图图3.2为从Foursquare中随机选择的三个用户在二维地理坐标上的签到概率的分布,纵坐标表示了用户访问位该地理坐标点的概率,从图中可以发现,地理特征对这三个人的签到行为产生的影响

  不同的,而且,登记概率的分布往往是多模式的而不是单峰或单调的。

  由此可以得出结论,每个人的签到行为都会受到不同的地理影响。用户的活动范围通常分布在若干区域。而且,这些区域的中心往往是用户访问概率最高的POI,与这些POI相近的地方较其他而言也有更高的访问概率。

  因此,为了平衡地理影响,本文提出了一种地理区域筛除的方法。首先对用户的活动范围进行了建模。设Lu={l1,l2, ,…,ln}为用户u访问的n个POI,Rm为最终的推荐列表。我们按照Lu中兴趣点被访问次数的数量进行排序,设lk1,lk2,lk3,lk4,lk5为用户u访问的概率高于N的几个点,用户访问POI l的概率的计算公式为用户访问l的次数和除以用户访问的总次数。以这些点为中心,适当的地理距离R(单位:千米)为半径,在二维地理坐标上画出用户的活动区域,如图6所示。在最终的推荐列表中,筛出掉用户活动区域之外的POI,保留区域内的POI。 至于N和R的大小该如何设置,在之后的实验会得到合适的N和R值。

  第四章 分层结构的POI推荐算法的设计

  本章深入探讨了POI推荐的分层结构,并以非负矩阵分解NMF为基础,提出一种新的算法HMF-G,实现了分层结构的POI推荐。

  4.1 分层结构的POI推荐的定义

  现实中的POI推荐具有某些分层结构。基于对POI的理解,我们发现用户对POI的内容偏好可以以分层结构的形式出现。例如,图4.1显示了POI的层次结构。我们可以看到,POI被组织成分层次的类别,某些类别的POI被进一步分类为子类别。因此,用户的内容偏好也表现出一定的分层结构。举个例子,美食家平时喜欢去餐馆,更具体的说,他更喜欢中餐馆,同一类别的POI可能共享一些相关的属性。此外,同一层次的用户倾向于具有相似的偏好。

  简单来说,一般的POI推荐系统会根据用户的偏好对用户进行推荐,例如推荐一个餐馆,但不能确定这个餐馆是否能真正符合用户偏好,有可能给一个不吃辣的用户的推荐了一个四川火锅店,导致推荐结果的准确度较低。分层结构的POI推荐能够很好的捕捉到用户偏好的分层结构,来向用户提供更准确更符合用户要求的推荐。因此,我们需要捕捉用户和POI之间的分层结构,实现分层结果的POI推荐,来为用户提供更加准确的推荐结果。

  4.2 分层结构的POI推荐算法HMF-G

  本节提出了HMF-G(Hierarchical Matrix Factorization-Geographical)算法来捕捉POI推荐的分层结构。在本章中矩阵被写成加粗的大写英文字母,如A和Bi。对于任意矩阵M,M(i,j)表示M矩阵的(i,j)项。||M||F是M的Frobenius范数。令U={u1u2,u3,…,un}是n个用户的集合,V={v1,v2,v3,…,vm}是m个POI的集合。我们使用X∈Rn×m来表示用户POI评分矩阵。如果ui对vi进行了评分,令X(i,j)等于评分值,否则X(i,j)等于0。我们假设用户和POI的分层结构是不可用的,所以所研究问题的输入项仅仅是用户POI评分矩阵X,这一点和传统的推荐系统相同。在详细讨论如何建模用户和POI的层次结构时,我们首先要介绍一下所提出的算法的基本模型。

  4.2.1 HMF-G的基本模型

  在本文中,我选择了非负矩阵分解(Nonnegative Matrix Factor,NMF)作为所提出的算法的基本模型。1999年在Nature杂志上,Lee和Seuang提出了一种全新的矩阵分解方法,这种MF即为非负矩阵分解。使用该方法分解后的分量均为非负值,并且同时实现非线性的维度约减。NMF将评分矩阵分解为两个非负的低秩矩阵U∈Rn×d和V∈Rd×m其中U是用户偏好矩阵,U(i,:)是ui的偏好向量。V是POI特征矩阵,V(:,j)是vj的特征向量。通过NMF,可以获得ui对vj的评分X(i,j)=U(i,:)V(:,j)。U和V可以通过解决下面的优化问题进行学习:

  其中表示Hadamard积,W(i,j)控制X(i,j)都学习过程的贡献。如果ui对vj进行了评分,则W(i,j)=1,否则W(i,j)=0。

  4.2.2 HMF-G的具体内容

  在非负矩阵分解中,用户偏好矩阵U和项目特征矩阵V可以分别体现出用户偏好和POI特征。既然U和V都是非负的,那就可以进一步地对它们进行非负矩阵分解,从而为建模用户和POI的分层结构铺平道路。在本节中,首先介绍如何基于非负矩阵分解对层次结构,进行建模,然后介绍所提出的算法HMF-G(Hierarchical Matrix Factorization-Geographical)。

  POI特征矩阵V∈Rd×m表示m个POI和d个隐藏因子的关系。由于V是非负的,我们可以进一步将V分解为两个非负矩阵V1∈Rm1×m和V2∈Rd×m1,得到如图4.2(a)所示的2层层次结构

  V≈V2V1 (式4.2)

  其中m1是第2层隐藏因子的数量,V1表示了m个POI与m1个隐藏因子的关系。在这里将V2命名为2层层次结构的隐藏因子矩阵。由于V2非负的情况下,我们可以进一步将V2分解为V2∈Rm2×m1和V3∈Rd×m2,得到如图4.2(b)所示的三层层次结构令Vq-1为(q-1)层层次结构的隐藏因子矩阵。进一步将Vq-1得到两个非负矩阵,根据上述过程可以从q-1层的层次结构获得q层的层次结构,如图4.2(c)所示:

  根据Ui和Vj的更新规则,HMF-G的优化算法如图4.4所示。接下来我们简要回顾图4.4,为了优化HMF-G中因子的近似值,我们对每一层进行了预训练,使其具有矩阵Ui和Vi的初始近似值。为了进行预训练,我们首先使用了NMF将用户POI矩阵分解为U1V1。之后,进一步使用非负矩阵分解将U1分解成U1≈U1U2和V1≈V2V1。不断地进行深度分解,直到获得了p个用户层和q个项目层。这个初始化过程在图4.4中从第1行到第9行进行了总结。在初始化之后,使用(式4.13)和(式4.17)中的更新规则分别更新Ui和Vi,进行微调。具体过程是,首先依次更新Vi,然后依次按顺序更新Ui,这在图4.4中从第10行到第20行进行了总结。在算法1的第21行,我们将用户评分矩阵Xpred=U1…UpVq…V1。ui对vj的空值评分被预测为Xpred(i,j)。最后,我们在根据Xpred产生的推荐列表进行地理区域筛选,将地理因素的影响考虑到最终的POI推荐结果中。

  第五章 实验分析

  本章在两个大型的社交网络数据集(Foursquare和Gowalla)上对所提出的算法HMF-G进行了实验,并将实验结果与其他几种推荐算法进行比较,分析各个推荐算法的特点,得出本次实验的结论

  5.1 数据集

  所有的实验都是在现实世界的数据集上进行的[9]上进行的,包括2015年8月以来来自伦敦的Foursquare签到数据,以及2011年3月至11月间来自加利福尼亚州的Gowalla签到数据。Foursquare是一个社交服务网络,它的特点是能够提供用户定位功能。Gowalla是一个基于位置社交服务网络,用户可以通过移动网站或者专门的移动应用顺序在当地附近的景点进行签到。签到时有时候会为用户产生虚拟的“物品”,其中的一些被开发成了游戏合作伙伴的促销工具。截至2010年10月,Gowalla已经有大约60万注册的用户。如表2所示,Fouesquare包括了8771个用户在18045个POI进行的187822次签到信息,其用户POI矩阵的稀疏度为99.87%,密度为0.13%。Gowalla数据包括由5332个用户在9699个POI进行的115698次签到信息,其用户POI矩阵为99.79%,密度为0.21%。为了确保选择的而数据真实且具有代表性。我先对数据集进行了一定的处理,去除掉重复值和缺失值,并且筛选出访问POI少于10个的用户和访问者少于3为的POI。对于每个用户,我将20%的签到信息的随机子集作为本次实验的测试集,80%的签到信息作为训练集。

  5.2 实验设置

  学习后的模型预测了每个用户的为访问POI的分数,然后根据这些分数对他们排名。本文采用了两种广泛应用的评估指标。即准确率Precision@k和召回率Recall@k(分别表示为Pre@k和Rec@k),k是所推荐的POI的数量。Pre@k表示推荐的k个POI中用户已访问过的POI的百分比,Rec@k表示推荐的k的POI中用户已访问过的POI的数量占所有被用户访问过的POI数量的百分比。在形式上,我们将Lu(k)定义为给用户u提供的排名前k个的POI,Bu表示用户已访问过的POI,这两个指标定义如下:

  在本文实验中,进行了十次独立的实验以获得平均精确度和召回率。对于这两个指标,本次实验中分别进行了k=5,10和20实验,这意味着分别推荐排名最高的5,10,20个POI。

  另外,我们还需要设置控制算法复杂度的参数。本问只讨论一个2层的层次结构,即U≈U1U2,V≈V1V2。其中,U1≈Rn×n1,U2∈Rn1×d,V1∈Rd×m1,V2∈Rm1×m。我们将潜在因子K的维度设为100,将n1的值改为{50,100,200,400,800},m1的值为{100,200,400,800,1000}。

  5.3 推荐算法的性能比较

  与其他推荐算法的结果分别汇总于下页图5.1中的准确率和召回率。表中的基线方法定义如下:

  NMF:非负矩阵分解的目标很清楚,先是将大矩阵分解为两个较小的子矩阵,之后,将两个子矩阵相乘后就能够获得一个于原矩阵大小相同的评分矩阵。非负的意思是指所分解的矩阵中都不包含负值。从现实应用的角度来看,非负矩阵分解能够很好的发现用户和项目之间的潜在特征。非负矩阵分解的一个最常见的应用就是协同过滤中的预测出评分值。因为用户对项目的打分都是正的,评分值不会是负值,从协同过滤的这个角度来说,非负也是可以理解的。在本文中,选择NMF作为所提出的HMF-G的基本模型。

  HMF:即去除掉地理区域筛选的HMF-G。

  5.4 实验结果

  图5.1(a)和(c)表示了在Foursqure和Gowalla两个数据集上几种方法的Pre@k表现,图5.2(b)和(d)表示了在Foursquare和Gowalla两个数据集上几种方法的Rec@k表现。在实验中我们调整了HMF-G中的n1和m1的值,发现了HMF-G的表现有相同的变化趋势,开始的时候增加然后减少,如图8所示。在n1和m1中,HMF-G的表现对m1比较敏感,导致了m1方向的波动更加明显。此外,我们在实验中发现,在n1=400和m1=800时,Foursquare的Pre@k和Rec@k都达到了顶部位置,而Gowalla的Pre@k和Rec@k在n1=800和m1=800时达到了顶部位置。对于地理区域筛除法的参数N和R,经过实验发现,当N=0.5,R=5时,Foursquare和Gowalla的Pre@k和Rec@k表现最好。

  关于POI推荐的结果,在本节中,我们将提出的方法HMF-G与三种基线方法(包括NMF,HMF)进行比较。在这些方法中,NMF的表现一般。HMF由于考虑到了分层结构的影响,效果比NMF好。由于考虑到地理信息,HMF-G的表现最好,证明了地理信息对推荐算法的有效影响,同时也表明HMF-G受益于用户偏好和POI的隐含分层结构,换句话说,它表明了POI推荐的层次结构的有效性,以及POI内容的分层结构对于POI推荐是有价值的。HMF-G使用加权矩阵分解来考虑负POI,并给它们分配较低的权重。因此,HMF-G是一种有效的POI推荐方法。本文提出的HMF-G是一种基于地理因子分解和POI的内容的层次结构的综合算法,显示了对POI推荐算法的改进。

  5.5 结论

  本章发现了POI和用户的内容偏好可以呈现出一种分层结构,我们发现,可以通过地理因子分解方法将地理影响纳入到用户POI矩阵中。为了提高POI推荐的有效性,本文提出了一种推荐算法,一种纳入地理影响的POI推荐的分层地理矩阵分解方法HMF-G。HMF-G在不同的层次上捕获了POI的内容影响,并有效地将用户对具有层次结构的POI内容偏好建模。进一步对用户的内容偏好矩阵和POI的特征矩阵进行矩阵分解,对分层结构进行建模,并通过地理区域筛除的方法将地理位置对POI推荐的影响纳入最终的推荐结果中。本文在两个大型数据集上的实验结果证明了HMF-G的有效性,其效能较其他算法有显著提升。

  第六章 总结与展望

  6.1 本文总结

  和传统的推荐任务不同,POI推荐受到多种因素的影响,如时间限制,地理约束和用户对POI的内容偏好。时间对POI推荐的影响至关重要,用户在一天不同时间的POI偏好是不同的。地理条件也约束着人们对POI的选择,空间兴趣点与其他非空间项目完全不同,例如传统的书籍,音乐和电影推荐系统,因为用户需要物理交互来访问POI,POI的地理信息(即经度和纬度坐标)显著地影响用户的登记行为。此外,现实世界的推荐系统中的项目可能会呈现某些分层结构,用户的偏好也可能会呈现分层结构。

  本文主要研究了时间,空间对POI推荐的影响,并深入分析了用户和POI之间的分层结构关系,对传统的非负矩阵分解提出了改进,并提出了一种用户偏好和POI特征的分层关系的建模方法。

  本文的主要贡献如下:

  (1)综合考虑了时间和空间对POI推荐的影响,将原有的数据集按照不同的时间段进行切片,根据用户在不同时间段的POI偏好来预测出推荐分数。采用一种地理区域筛选的方法,将地理影响纳入到POI推荐中。

  (2)提出一种名为HMF-G的推荐算法,以非负矩阵分解为基本模型。用于捕获用于用户和POI之间的层次结构,并将地理因素考虑到最终的POI推荐分数。

  (3)本文已经在两个大型实际数据集(即Foursquare和Gowalla)对HMF-G算法进行了评估。实验结果表明所提出的算法的有效性,在准确率和召回率方面优于基准方法。

  6.2 后续工作展望

  然而,本文提出的算法也有不足的地方:

  (1)未考虑到用户POI矩阵的稀疏性问题和签到数据的隐式反馈问题。在LBSN中,因为用户只在几个POI签到,导致了用户POI的签到关系非常稀疏[10]。因此推荐方法存在数据稀疏问题。用户的签到数据通常表示为一个用户POI矩阵。正如我们在本文中第4章的实验所看到的 ,签到矩阵的密度通常小于0.5%。这与Netflix数据的11%相比非常小。更严重的是,签到信息是一种隐式反馈[11],这让POI推荐更加困难。与传统的电影或音乐不同,用户对项目的不同分数明确表示了他们对该项目是“喜欢”或“不喜欢”,但是POI的签到数据只提供了用户所喜欢的项目,不能明确确定用户对没有去过的POI的评价。这些用户未访问过的POI,可能是没有吸引力,但也有可能是未被用户发现但对用户更有吸引力。换句话说,需要通过签到数据来推断用户的偏好或者是非偏好的。大多数现有的POI推荐方法忽略了数据稀疏性和隐藏的反馈事实,本文中提出的方法也可能遭受数据的稀疏问题。

  (2)POI推荐还可能受到其他多种因素的影响。除了时间和空间的影响外,POI还可能受到其他因素的影响。①社会影响。在现实世界中,人们之间相互交流。例如,人们通常和好友一起去餐馆或者电影院,如果一个地方倍受好友的好评,人们也会倾向于去那个地方看看到底如何。因此一个人的POI偏好很可能受到他的好友或者一群兴趣相投的朋友的影响。在LBSN中,用户也会在相应的社区中分享他们访问POI的经历。②分类影响[12]。POI的种类反映了其通常进行的业务活动和性质。例如,一个在餐厅签到的人表明他可能在吃饭,在电影院签到表明他可能在那里看电影。在现实中,用户对POI的种类也表现出了不同的观点,美食家经常到餐馆品尝各种食物,而旅游爱好者通常会在世界各地的旅游景点中旅行。③顺序影响。实际上,人类的活动通常呈现出一种顺序。例如,人们在餐馆用餐之后可能会去电影或酒吧,因为人们在饭后想要放松。如果一个人先去了餐馆,那么之后有很小的概率去健身房,因为饭后运动是不健康的。因此,POI的访问顺序也会对用户的行为产生重要影响。本文的研究范围有限,未能考虑到时间空间外的其他因素,这可能导致最终的推荐结果会出现一点偏差。

  在今后的进一步工作中,会充分考虑到POI签到数据的稀疏性和隐式反馈问题,并综合多种对POI推荐产生影响的因素,进一步优化算法,提供更准确的POI推荐结果,更能符合用户的POI偏好。

毕业论文:http://www.3lunwen.com/jsj/dzjs/5412.html

上一篇:基于多链编码遗传算法的二维卷材下料问题优化方法

下一篇:没有了

     移动版:基于分层结构的兴趣点推荐算法的设计与实现

本文标签:
最新论文