基于分层结构的兴趣点推荐算法的设计与实现分析研究电子科学与技术专业.docx

5.15.25.35.4.1.2.2 .3.7.7.7 .8.9.9.10.11.11.12.14.14.15.15.15.17.21.21.22 .22.23目录,.Z11H1Jt4j'g右,*1.1 研究背景及意义1.2 Pc)I推荐概述及研究现状1.3 本文的主要工作1.4 本文的组织结构第二章相关技术介绍2.1 推荐算法概述2.1.1 基于协同过滤的推荐2.1.2 基于内容的推荐2.2 推荐算法的评测指标2.2.1 准确性指标2.2.2 非准确性指标第三章POI推荐的影响因素3.1 时间的影响及解决方法3.2 地理位置的影响及解决方法.第四章分层结构的POl推荐算法的设计4.1 分层结构的POl推荐的定义4.2 分层结构的POl推荐算法HMF-4.2.1 HMF-G的基本模型4.2.2 HMF-G的具体内容4.2.3 HMF-G的优化算法第五早驮分析实验设置推荐算法的性能比较实验结果5.5结论25第六章总结与展望266.1 本文总结266.2 后续工作展望26参考文献28致.错误!未定乂书签o摘要随着基于地理位置的社交网络(LocationBasedSocialNetworks,LBSN)的迅速发展，兴趣点(PointOfInterest,POD推荐已经成为了一个重要的研究问题。然而Pol推荐会受到时间和地理位置的影响。此外，现实世界中的推荐系统的Pol呈现出一定的分层结构，同样，用户的偏好的也会呈现分层结构。最近的研究表明，结合项目或用户偏好的分层结构可以提高推荐系统的性能。显式的分层结构例如用户偏好通常是不可用的，因此，分层结构并没有很好地应用到推荐系统上。本文首先研究了时间和地理位置对Pc)I推荐的影响。设计和实现了一种分层结构的POI推荐算法HMF-G(HierarchicalMatrixFactorization-GeogmphicaD,来获得用户和POI之间的隐式分层结构。在两个现实世界的数据集，Foursquare和Gowalla上的实验结果证明了所提出的算法的有效性。关键词：推荐算法；兴趣点；分层结构AbstractWiththerapiddevelopmentoflocation-basedsocialnetworks(LBSN),Point-of-Interest(POI)recommendationhasbecomeanimportantresearchissue.However,POIrecommendationisaffectedbytimeandlocation.Inaddition,therecommendationsysteminreal-worldpresentsahierarchicalstructureofPOLSimilarly,theuserpreferencesalsoshowahierarchicalstructure.Recentstudieshaveshownthatcombiningthehierarchicalstructureofprojectsoruserpreferencescanimprovetheperformanceoftherecommendationsystem.Explicithierarchicalstructuressuchasuserpreferencearegenerallynotavailable.Therefore,thehierarchicalstructureisnotwellappliedtotherecommendationsystem.ThisdissertationfirststudiestheinfluenceoftimeandgeographicallocationonPOIrecommendation.AndahierarchicalstructureofPOIrecommendationalgorithmHMF-G(HierarchicalMatrixFactorization-Geographical)isdesignedandimplementedtoobtainanimplicithierarchicalstructurebetweenusersandPOIs.Experimentalresultsontworeal-worlddatasets(FoursquareandGowalla)demonstratetheeffectivenessoftheproposedalgorithm.Keywords:recommendationalgorithm;pointofinterest;hierarchicalstructure城市的迅速发展带来了数量越来越多的兴趣点(POintOfInterest,POD,例如餐馆，商店，酒店，为我们提供了越来越多的体验生活的机会。日常生活中，人们乐意去探索城市和社区，并根据自己的个人兴趣决定“去哪里”。与此同时，如何在大量的POI中做出令人满意的决定也成为了用户的一个棘手的问题,俗称“选择困难症”。POI推荐任务旨在帮助用户过滤用户不感兴趣的POI来缩短其决策时间。基于位置的社交网络(LOCatiOnBaSedSOCiaINetWork,LBSN)已经吸引了数百万用户在他们中意的兴趣点签到，并与朋友分享他们访问这些Pol的体验。例如，截至2014年12月，Foursquare拥有超过60亿的签到信息，每天有5千5百万用户进行数百万的签到。这些历史签到信息包含了关于用户和POl的丰富的信息，为挖掘用户的POI偏好并进行POI推荐提供了新的机会。Pe)I推荐易受时间和地理位置的影响。在不同的时间内，用户有着不同的Pe)I偏好。同时用户的地理位置也对用户访问Pol产生了约束。而且，Pol往往呈现出一种分层结构，例如餐馆类的Pc)I往往还分为中餐，西餐，咖啡厅等，博物馆类的Pol还可以分为历史博物馆，艺术博物馆，科学博物馆等。同理，用户的PC)I偏好往往也呈现出一种分层结构，例如用户往往只喜欢去中餐类的餐馆。本文研究了时间和地理位置对POI推荐的影响，以及如何将时间因素和地理因素纳入到POl推荐中。同时，本文还深入研究了用户和Pol之间的分层结构的关系，并提出一种全新的算法HMF-G来捕获用户POl的分层结构。并进行了实验验证。本文的完成主要工作如下：(I)探讨了时间对PoI推荐的影响，提出将数据集按不同时间段进行切片来处理时间因素的方法。(2)探讨了地理位置对Pc)I推荐的影响，采用一种地理区域筛选的方法将地理因素纳入到Pol推荐中。(3)研究用户POI之间的分层结构，提出一种算法HMF-G来对用户POI的分层结构进行建模。(4)在两个数据集(FOUrSqUare和GolIaWa)上对进行实验，并于其他几种Pc)I推荐算法进行比较，实验结果证明了(3)中所提出的算法的有效性。第一章绪论本文首先介绍了POI推荐的研究背景和意义，之后简单介绍了POI推荐的特点和影响因素，并详细地说明了本文的主要工作。在本章的最后，介绍了一下本论文的组织结构。1.1 研究背景及意义随着具有无线通信和定位功能的移动设备的迅速普及，一些基于位置的社交网络(LocationBasedSocialNetwork,LBSN)的互联网应用，例如FoUrSqUare,Gowalla,Brightkite,Yelp和Facebook已经越来越受到人们的欢迎,并吸引了数百万人的用户。LBSN具有将物理世界和虚拟世界联系起来的功能。兴趣点(英文：PointofInterest,POD即电子地图的某些地标，例如餐馆，商店和电影院等，如图1.1显示了苏州市的部分兴趣点。在LBSN(下页图1.2)中，用户可以建立起彼此的社交链接，通过在某些地方用移动设备签到(checkin)来向其他人分享一些他们所去过的兴趣点的体验心得。智能手机的锐增导致了LBSN的繁荣，Foursquare,FacebookPlaces和Yelp等LBSN现在越来越流行。直到2016年6月，Foursquare已经收集了全球包括80亿次签到信息和6500多万次的地形测绘业务。图1.2：基于地理位置的社交网络1.BSN中有大量社区贡献的数据，包括用户彼此之间的社交关系，用户在PC）I上的签到信息，用户的地理位置信息和POI的种类。这些丰富的数据反映了人们在现实中的行为，并且为了用户访问POI的决策过程提供了新的机会。在LBSN中，根据从社区贡献的数据中了解到用户对POI的访问偏好，来向用户提供他/她可能感兴趣但之前未访问过的POLPol推荐非常重要，一方面，它有助于当地居民或游客探索城市中一些有趣的未知地点。另一方面，还为POl的拥有者创造机会和商业利润，通过发现和吸引潜在的游客来增加POI拥有者的收入。事实上，LBSN服务中的关键就是准确和个性化的POl推荐。首先，考虑到大量的PeH,用户很难通过有效的方式来找到他们喜欢的POL个性化的PCH推荐系统可以帮助用户轻松找到相关的POI,而无需花费太多时间进行搜索，特别是用户来到新地区时。此外，对于POI所有者说，向各种用户提供正确的POI也是非常具有挑战性的。个性化的POl推荐系统不仅能够减轻负担，还能通过推荐的POl来吸引更多的用户。1.2 POI推荐概述及研究现状POI推荐是LBSN中最重要的任务之一，它可以帮助用户在LBSN中发现新的有趣的地点。PcH推荐通常会挖掘用户的Pol签到记录，地点信息（如类别）和用户的社交关系，以推荐用户最可能在将来访问的POI列表。POI推荐不仅提高了用户对LBSN供应商的粘性，而且还为广告代理商提供了向潜在消费者发布广告的有效方式。具体来说，用户可以使用FOUrSqUare探索附近的餐馆和市中心的购物商场。同时，商家也可以通过POI推荐让他们的目标用户轻松地找到他们。为了方便用户以及商家所提供的商机，POl推荐已经吸引了大量的关注，最近许多研究人员提出了一堆POl推荐系统。尽管开发POI推荐系统可以极大地使用户和POI推荐者都收益，但它仍然是一个非常的具有挑战性的问题。事实上，用户的签到决策过程非常复杂，可能会受到不同因素的影响。首先，用户访问PoI很大程度上会受到朋友的影响。对于某些特定的POI,一些朋友可能会对用户访问该POl产生正面影响，然而另一些朋友可能会产生负面影响。此外，距离Pol的距离也会影响用户对该POl的偏好程度。一般来说，用户喜欢去附近的Pe)I而不是距离很远的POIo因此，模拟社交朋友关系和地理距离对用户访问Pol的影响非常重要。另外，用户是否在POl签到可能取决于用户的具体目的。例如，当人们想吃午饭时，他们更想选择与食物相关的兴趣点而不是景点。基于记忆的协同过滤(CollaborativeFiltering,CF)技术(例如基于用户的CF和基于物品的CF)经常被用于Pol推荐。LeVandOSki对基于物品的CF进行修改，将用户的旅行距离作为一个惩罚项，对学习的过程进行了优化。M.Ye等人通过采用线性插值的方法将地理和社交关系影响纳入到基于用户的CF模型，显著的提高了推荐算法的准确性，而且社交关系对推荐系统的性能影响不大。基于记忆的CF很容易受到数据稀疏的问题的困扰，因为用户与用户或物品与物品的相似性需要根据用户平时的签到信息进行计算。当签到信息很少时，两个用户或物品之间将共享很少的签到信息，因此根据这些签到信息产生的相似性提供推荐结果是不可靠的。CCheng等人引入一个多中心高斯模型来计算地理位置对推荐结果的影响，因为用户的平时的签到地点通常在几个中心附近，并将它与矩阵分解(MatriXFactorization,MF)结合起来用于兴趣点推荐。然而在这种方法中，MF仅通过适配非零的签到信息来执行，因此它容易遭受数据稀疏的问题。基于模型的CF技术也被应用于Pol推荐，NOUlaS发现对于POl推荐而言，MF比基于用户的CF和基于项目的CF的表现效果更差。在他们的研究中，他们将用于显示反馈数据的常规MF技术应用到PoI推荐中，这种不适合Pol推荐的方法导致效果不佳。B.Liu等人提出了一个地理概率因素的分析框架，即GTBNMF,它结合了基于贝里斯非负矩阵分解的地理影响。但是BNMF是通过满足零和非零签到来执行的，因为零签到可能会缺失值，所以可能导致算法结果的不合理。所有的这些方法都不能反应出POI推荐的隐式反馈属性。与传统的推荐系统（如音乐推荐，电影推荐不同），POI推荐要考虑各种因素，例如用户对POl的内容偏好和受地理约束的空间偏好。J.-D.Zhang等人通过核密度估计的方法对每个用户的个性化二维地理影响进行建模，预测出用户访问新位置的概率。D.Lian等人将地理信息纳入到加权矩阵分解以提高POI推荐的有效性。1.3 本文的主要工作（1）提出一种将数据集按不同的时间段进行切片的方法，处理时间对POI推荐的影响。（2）对用户的活动区域进行建模，对最终推荐的不在区域内的POl进行筛除，该方法考虑了地理因素对PeH推荐的影响。（3）提出了一种推荐算法HMF-G,它能够使我们在这些结构不明确可用的情况下捕获用户和POl的分层结构，并对其进行建模。（4）在两个大型的现实世界的数据集（FOUrSqUare和GOWana）上进行实验，并将结果与其他几种推荐算法进行比较。实验结果充分验证了（3）中所提出方法的有效性。1.4 本文的组织结构本文是一共分为六章，各章的内容如下：第一章：绪论。本章主要介绍了分层结构的兴趣点推荐的意义和研究背景，并简单介绍了POl推荐的特点和影响因素，而且还详细地说明了本文主要工作，最后介绍了本文的组织结构。第二章：相关技术介绍。主要介绍了常用的推荐算法，以及常用的推荐算法的评测指标。第三章：Pol推荐的影响因素。本章详细地讨论了时间和地理位置对POl推荐的影响，并提出了对数据集进行切片和地理区域筛除的方法。第四章：分层结构的POI推荐算法。本章深入地讨论了POI推荐的分层结构，并以非负矩阵分解NMF为基础，提出一种HMF-G算法来对POI推荐的分层结构进行建模。第五章：实验分析。在Gowalla和Foursquare数据集对所提出的HMF-G算法进行了实验，并将实验结果与几种推荐算法相比较，实验结果证明了所提出的算法的有效性。第六章：总结与展望。对全文进行了细致性的总结，并思考了在本文中的一些不足的地方，提出了未来的工作的安排与期望。第二章相关技术介绍本章对推荐算法的相关技术进行介绍，介绍了一些常用的推荐算法，如协同过滤算法和基于内容的推荐算法。并简单介绍了一下推荐算法常用的评测指标。2.1 推荐算法概述推荐系统中，最重要的技术所在就是推荐算法。对不同的推荐系统，需要认真考虑该选择何种推荐算法。到现在为止，已经有很多种类的推荐算法。每一种推荐算法都有它们的缺点和优点，而且，不同的算法也有其对应的限制条件。推荐算法一般都是建立了一个模型，用于推断用户感兴趣的项目。首先获取数据，例如用户偏好和可供推荐的项目的特征，然后推测哪些项目会迎合用户的偏好。2.1.1 基于协同过渡的推荐协同过滤(COlIaboratiVeFiItering,CF)是一种通过收集许多用户(协,同)的偏好或口味信息来对用户的兴趣进行自动检测(过滤)的方法。CF的假设是，如果一个用户甲在某个问题上，和某个人乙有相同的意见，那么与其他随机选择的人的想法比起来，甲的想法可能和乙的更相似。简单来说，就是分析一群有着相似爱好的用户组的行为，来去判断相关用户的项目偏好。当我们想向用户推荐某些东西时，最合理的做法是找到和用户品味爱好相同的人，看看他们都选择了哪些项目，然后用户推荐相同的项目。或者我们可以查看和用户之前购买的产品类似的产品。协同过滤算法主要分为两种，以用户为基础的CF(USer-BaSedCF,UCF)和以项目为基础的CF(Item-BasedCF,ICF)0(1)基于用户的CF(UCF)UCF的主要做法是找到一群爱好相似的用户，即基于用户的(User-based)的CF或基于相邻者的CF(Neighbor-basedCollaborativenFiltering)0用户与用户之间相似度通常用JaCCard公式或余弦相似度来计算。这样的话，两个用户的相似度可以更直观的观察到。设M色)是用户的中意的项目的集合，MW)为用户U中意的项目的集合，则N和U相似度的计算公式为：余弦相似度:Jaccard 公式:M(")cM(u) m(w)×M(v)_ I (w)n(v) I M(w)uM(v)(式 2.1)(式 2.2)UCF的具体方式为：通过收集有关用户的信息，了解用户的项目偏好。然后通过计算用户之间的相似度来找到与该用户相似的一组用户，用这组用户的偏好记录信息来预测该用户对相关项目的评分(2)基于项目的CF(Item-BasedCF,ICF)随着用户数量增加，UCF所消耗的计算时间越来越多。2001出现另一种CF,即基于项目的协同过滤算法(Item-basedCollaborativeFilteringAlgorithms)«ICF的基本假设为，若用户中意一个项目，那么，与该项目相似的其他项目也有可能引起用户的兴趣。项目之间的相似性用数学的方法进行计算。项目的相似度的计算公式为：(式 2.3)IM(z)nM(y)IJlMa)IXlMe/)|其中，IMa)I是喜欢项目i的用户数，IM(Z)I是喜欢项目)的用户数。ICF的方法步骤如下：收集相应信息，计算已评价的项目和预测项目的相似度，并以此为基础得到预测项目的预测分数，最终产生推荐结果。2.1.2 基于内容的推荐基于内容的推荐(Content-basedRecommendation)方法来自于信息获取领域。原理为：根据用户已选的项目，从推荐的项目之中，选择其他特征与之相似的项目，并作为推荐结果。(1)第一步，获取推荐项目的特征，然后去和用户偏好相比较，匹配度较高的项目就可作为推荐结果。(2)重点是计算出项目特征和用户偏好的相似性。(3)通过计算出相应项目的评分值，并进行排序，将排名较高的项目作为推荐结果。描述项目特征和用户偏好是基于内容的推荐算法中的重点。这样避免项目的冷启动问题。2.2 推荐算法的评测指标2.2.1 准确性指标（1）分类准确度，指判断一个项目是否迎合了用户的偏好，并且结果正确的比例，包括召回率和准确率。设U为用户集,Ru为用户u的推荐列表,Bu为测试集中用户给予正反馈的项目。准确率，指在推荐的结果中，用户在现实中给过正反馈的项目所占的比例。单个用户U准确率为：整个推荐系统的准确率为：好”（式25）召回率，在测试集中，用户给过正反馈的项目占测试集的比例。单个用户U的召回率为：R（LD=Au（式2.6）lt整个系统的召回率为：RL=LER（R）（式2.7）nueU（2）预测准确度，预测用户对项目的评分的行为，包含均方根误差（ROOtMeanSquareError,RMSE）和平均绝对误差（MeanAbSOhIteError,MAE）0均方根误差RMSE：RMSE=JE"'L"l（式2.8）VtestICteSt为测试集，加用户U对项目V的实际评分，Wy表示预测评分。平均绝对误差MAE：MAE=£"""一%（式2.9）ICltestI2.2.2 非准确性指标（1）覆盖率。是指推荐结果中的项目占总项目集合的比例，这样可以观察推荐出的项目能不能很好的覆盖所有的商品，是不是每个项目都有机会被推荐。计算覆盖率的一种简单方法就是计算被推荐的项目数量占项目总数的比例。更精确的办法是用基尼系数和信息燧来衡量。较高的覆盖率也能反映出推荐系统有着较好的性能。（2）多样性。是指推荐出来的结果要有多样性，能覆盖到用户不同的兴趣领域。多样性可以基于项目间的相似度来计算，如果推荐出来的项目之间相似度较高，那么说明都是同一种类的项目，缺乏多样性。第三章Pol推荐的影响因素本章详细探讨了时间和地理位置对POI推荐的影响，并提出了相应的解决方法,即对数据集进行切片和地理区域筛选。3.1 时间的影响及解决方法时间影响对POl推荐至关重要，因为检查活动的物理限制导致了特定的模型。PC）I推荐系统中的时间影响主要表现在三个方面：周期性，连续性和不一致性。用户在LBSN中的签到行为呈现周期性模式。例如，用户总是在中午签到入住餐厅，晚上在夜总会玩乐，用户还可以在周一至周日前往办公室周围的地方，并在周末花时间在购物中心购物。图4显示用户在一天内的签到频率的分布。非一致性特征Hour ofthe Day图3.1： 一天内不同时间的签到分布I DaiIy CheCk-ins |Aznbu:usqo描述了用户在一天的不同时间的签到偏好差异。据观察，用户对Pol的访问偏好在一天内的不同时间变化，用户最常访问的Pol在一天内的不同时间发生改变。类似的时间特征也出现在一年的不同月份，以及一周的不同日子。这种非均匀特征可以从用户的日常生活习惯中解释：（1）早上，用户倾向于在用户家附近的Pol签到，中午倾向于访问在办公室周围的地点，晚上倾向于在酒吧里消遣。（2）用户可以在工作日访问用户家附近或办公室周围的更多地点。在周末,用户可以在商场或度假地点签到。（3）在不同的月份，用户可能对事务和娱乐有不同的兴趣。例如，用户将在夏季的几个月去冷饮店，而在在冬季去火锅餐馆。为了在不同的时间为用户提供正确的PC）I推荐,本文采用的方法是将一天分成不同的时间片段，然后应用协同过滤技术分别在每个时间片段来推断用户对POl的偏好。具体的做法是根据用户的签到时间，将原有的数据集划分为四个子数据集，分别保存了用户在早上（6：00-12：00）,午后（12：00-17：00）,夜晚（17：00-22：00）,深夜（22：00-次日6：00）四个不同时间段的签到信息。根据用户在不同的时间段的PC）I签到频率分布，预测出用户的PoI偏好。3.2 地理位置的影响及解决方法地理学第一定律（TObIeESFirStLaW）指出：“任何东西都与其他的东西之间有着千丝万缕的关系，但是，附近的东西比远处的东西有更强的关系。“例如，一个人在现实生活中经常访问一个POL例如博物馆，那么，他就更有可能去访问博物馆附近的POI,如一些餐馆和酒店。也就是说，近距离的Pe）I比远距离的POl具有更强的地理相关性，地理上邻近的POI更可能具有相似的特征，另外，用户访问POI的概率与地理距离成反比。地理影响是区分Pol推荐与传统物品推荐的重要因素，因为用户的签到行为取决于地理特征。对用户签到数据的分析表明，用户的活动范围通常受到了一些地理限制，并且，用户更倾向于访问用户签到处附近的POL而且，对用户的签到行为产生的地理影响往往是因人而异的。例如，户内人士喜欢访问生活区周围的POI,而户外人士往往喜欢环游世界以探索新的PoI。因此，在为用户推荐Pol时，地理信息对个人的签到行为应该是个性化的。目前，有一些研究通过利用地理位置建议的影响来了解用户的偏好，然而这些研究使用位置之间的一维距离来进行推荐，例如认为用户访问POI的倾向与离POI的距离成反比。然而，将地理影响考虑到二维层面上才是更合理和客观的。而且，访问概率不仅受到距离的影响，还会受到位置的内在特征的影响，所以，用户访问每个位置的概率并不是单单被距离所影响。例如，实际上，用户的登记位置通常分布在若干区域。J.-D.Zhang等人，针对POl推荐的个性化二维地理影响，利用了核函数计算了每个用户的个性化二维签到概率密度的基本分布。下页图图3.2为从Foursquare中随机选择的三个用户在二维地理坐标上的签到概率的分布，纵坐标表示了用户访问位该地理坐标点的概率，从图中可以发现，地理特征对这三个人的签到行为产生的影响UXLUser2User3c U-2BQOQ.UEWOx 10-30Latitude: tf -180 Longitude:,图3.2：二维地理坐标是的个人签到概率分布不同的，而且，登记概率的分布往往是多模式的而不是单峰或单调的。由此可以得出结论，每个人的签到行为都会受到不同的地理影响。用户的活动范围通常分布在若干区域。而且，这些区域的中心往往是用户访问概率最高的POh与这些POI相近的地方较其他而言也有更高的访问概率。因此，为了平衡地理影响，本文提出了一种地理区域筛除的方法。首先对用户的活动范围进行了建模。设Lu=儿/2,为用户U访问的n个PoI,Rm为最终的推荐列表。我们按照LU中兴趣点被访问次数的数量进行排序，设kl,k2,k3,Zk4,后为用户U访问的概率高于N的几个点，用户访问POI/的概率的计算公式为用户访问I的次数和除以用户访问的总次数。以这些点为中心，适当的地理距离R（单位：千米）为半径,在二维地理坐标上画出用户的活动区域,如图6所示。在最终的推荐列表中，筛出掉用户活动区域之外的POL保留区域内的P0I。至于N和R的大小该如何设置，在之后的实验会得到合适的N和R值。BPn=OUO-图3.3：二维坐标上的活动区域第四章分层结构的Pol推荐算法的设计本章深入探讨了Pol推荐的分层结构，并以非负矩阵分解NMF为基础，提出一种新的算法HMF-G,实现了分层结构的POI推荐。4.1 分层结构的Pol推荐的定义现实中的POl推荐具有某些分层结构。基于对POI的理解，我们发现用户对POl的内容偏好可以以分层结构的形式出现。例如，图4.1显示了Pe)I的层次结构。我们可以看到，Pol被组织成分层次的类别，某些类别的Pol被进一步分类为子类别。因此，用户的内容偏好也表现出一定的分层结构。举个例子，美食家平时喜欢去餐馆，更具体的说，他更喜欢中餐馆，同一类别的Pc)I可能共享一些相关的属性。此外，同一层次的用户倾向于具有相似的偏好。简单来说，一般的PeH推荐系统会根据用户的偏好对用户进行推荐，例如推荐一个餐馆，但不能确定这个餐馆是否能真正符合用户偏好，有可能给一个不吃辣的用户的推荐了一个四川火锅店，导致推荐结果的准确度较低。分层结构的Pol推荐能够很好的捕捉到用户偏好的分层结构，来向用户提供更准确更符合用户要求的推荐。因此,我们需要捕捉用户和POI之间的分层结构，实现分层结果的POI推荐，来为用户提供更加准确的推荐结果。美食中餐店、外国餐厅、小吃快餐店、蛋桂甜品点、咖啡厅、茶座、酒吧酒店星级酒店、快捷酒店、公寓式酒店购物购物中心、超市、便利店、家居建材、家电数码、商铺、集市生活服务通讯营业厅、邮局、物流公司、洗衣店、照相馆、房屋中介机构丽人美容、美发、美甲、美体旅游景点公园、动物园、植物园、游乐园、博物馆、水族馆、海滨浴场休闲娱乐度假村、农家院、电影院、KTV、剧院、歌舞厅、网吧，游戏场所运动健身体育场馆、极限运动场所、健身中心教育培训高等院校、中学、小学、幼儿园、成人教育、亲子教育、培训机构文化传媒新闻出版、广播电视、艺术团体、美术馆、展览馆、文化宫医疗综合医院、专科医院、诊所、药店、体检机构、疗养院、急救中心汽车服务汽车销仰、汽车维修、汽车美容、汽车配件、汽车租赁、汽车检测场交通设施E机场、火车站、地铁站、长途汽车站、公交车站、港I、停车场金融银行、ATMx信用社、投资理财、典当行房地产写字楼、住宅区、宿舍4.2 分层结构的Pol推荐算法HMFG本节提出了HMF-G(HierarchicalMatrixFactorization-Geographical)算法来捕捉POl推荐的分层结构。在本章中矩阵被写成加粗的大写英文字母，如A和Bi。对于任意矩阵M,M(i,j)表示M矩阵的(i,j)项。IlMllF是M的Frobenius范数。令U=u1u2,u3,.,un是n个用户的集合，V=vl,V2,V3,vm是m个POI的集合。我们使用XRtl"来表示用户Pol评分矩阵。如果Ui对Vi进行了评分，令X(i,j)等于评分值，否则X(i,j)等于Oo我们假设用户和POl的分层结构是不可用的，所以所研究问题的输入项仅仅是用户POl评分矩阵X,这一点和传统的推荐系统相同。在详细讨论如何建模用户和POl的层次结构时，我们首先要介绍一下所提出的算法的基本模型。4.2.1 HMF-G的基本模型在本文中，我选择了非负矩阵分解(NOnnegatiVeMatriXFaCtor,NMF)作为所提出的算法的基本模型。1999年在NatUre杂志上，Lee和SeUang提出了一种全新的矩阵分解方法，这种MF即为非负矩阵分解。使用该方法分解后的分量均为非负值，并且同时实现非线性的维度约减。NMF将评分矩阵分解为两个非负的低秩矩阵URnXd和VR"m其中U是用户偏好矩阵，U(i,:)是Ui的偏好向量。V是Pe)I特征矩阵，V(:,j)是vj的特征向量。通过NMF,可以获得ui对vj的评分X(ij)=U(i,:)V(:j)oU和V可以通过解决下面的优化问题进行学习：周,。IIWW(X-UV)II泊尔IU抵+11VlH)(式4.1)其中表示Hadamard积，W(i,j)控制X(i,j)都学习过程的贡献。如果Ui对Vj进行了评分，贝JW(i,j)=l,否则W(i,j)=O°4.2.2 HMF-G的具体内容在非负矩阵分解中，用户偏好矩阵U和项目特征矩阵V可以分别体现出用户偏好和Pol特征。既然U和V都是非负的，那就可以进一步地对它们进行非负矩阵分解，从而为建模用户和POl的分层结构铺平道路。在本节中，首先介绍如何基于非负矩阵分解对层次结构，进行建模，然后介绍所提出的算法HMF-G(HierarChiCalMatriXFactorization-Geographical)oPOI特征矩阵VRtjxm表示rn个POI和d个隐藏因子的关系。由于V是非负的，我们可以进一步将V分解为两个非负矩阵VRm,×mV2Rdxml,得到如图4.2(a)所示的2层层次结构VV2V1(式4.2)其中ml是第2层隐藏因子的数量，Vl表示了m个POI与ml个隐藏因子的关系。在这里将V2命名为2层层次结构的隐藏因子矩阵。由于V2非负的情况下，我们可以进一步将V2分解为V2Rm2'ml和V3Rd2,得到如图4.2(b)所示的三层层次结构VV3V2V(式4.3)令Vq-I为(q-l)层层次结构的隐藏因子矩阵。进一步将Vq-I得到两个非负矩阵，根据上述过程可以从q-1层的层次结构获得q层的层次结构，如图4.2(C)所示：VVqvq.V2VI(式4.4)同样，也可以对U进行深度分解，获得一个P层的用户偏好矩阵的层次结构：UUU2.Up,Up(式4.5)Ul是一个大小为nXn的矩阵，Ui(l<i<p)是一个nuXm矩阵，UP是一个np-×d的矩阵。通过对多层的层次结构的数学建模，HMF-G需要解决以下的优化问题。pquxvW(X-Ui.UVD÷2(UJ三÷V7)，'''fj=j=X工Iq.o/s.U,0,il,2,.,p),Vj0,l,2,.q图4.3展示了三层HMF-G的示例。HMF-G分别对用户偏好矩阵U和POI特征矩阵V进行深度分解来对用户和POI的分层结构进行建模。图4. 3三层HMF-G的示例（式 4.7）（式 4.8）Hz =Ui.UM.M ifiP（式 4.9）4.2.3 HMF-G的优化算法(1) Ui的更新规则为了对Ui进行更新，我们需要修复除Ui之外的其他变量。通过删除与Ui无关的项目，(式4.6)可以重写为：minHW®（X-AlUfHl）÷/tUil其中Ai和Hi,IWiWp被定义为:U1U2U1ifiIifi=l(式4.7)的拉格朗日函数是:1.（Ui）=IlWG（XA,U,H）H+IIUiH-PTUi（式4.10）其中P是拉格朗日乘数。L(Ui)相对于Ui的导数是:(£(U=2A；W®(A1U,H,-X)JHf+22U,-Peu,(式4.11)通过设定导数为零并且使用KarUSh-KUhn-TUCker互补条件，即P(s,t)U(s,t)=O,我们得到：fA11W(AfUy-X)IHf+4UJd)=O(式4.12)由(式4.12)可以得到Ui的更新规则为:UWUGJ)Af(WX)H11(5)A：(WG(A,UH)!：+2UJ(SJ)(式4.13)(2)Vi的更新规则和更新Vi一样，为了更新Vi,我们修复了除Vi之外的其他变量。删除了与Vi无关的项目后，可以得到Vi的优化问题为:minW(X-BjVM)I+4IlMI。Bi和Mi,liq被定义为：JuLUM.Vrifiq1.u.Upifi=q和(式4.14)(式4.15)MV-1VifiM；=<Iifi=l通过按照与Ui类似的方式求解出Vi的更新规则，如下所示:(式4.16)VWY(S,/)Bf(W0X)M11r)Bf(W0(B,VMz)M+VJ(5)(式4.17)本节也用伪代码的形式来详细说明了HMF-G的优化算法，如下页图4.4所示。Input:XRnm.入PqdanddimensionsofeachlayerOutput：Xpred1: Initialize-andV,f.12: U1.V1<-4F(X.<)3: fori=ltop-1do4: U1.Ul,1<-J1VlWF(UrMf)5: endfor6: fori=ltoq-1do7: 可V-MWF(%m)8: endfor9: Up=6.=10: repeat11: fori=ltopdo12: updateBiadM/usingEq.(4.15)andEq.(4.16)13: updateVzbyEq.(4.17)14: endfor15:16: fori=ltopdo17: