|
|
前20％的参赛者百分比
78.7%
用户
表1.数据概述
3.当计算用户的两个位置的概率时，考虑几个因素，包括对用户u的位置y的偏好，可用的旅行时间，位置y的流行度以及这两个位置之间的距离。 在等式 如图3所示，Te表示旅行结束时间，Tc表示当前时间，Move（x，y）表示从x移动到y所花费的时间，其可以通过x和y之间的距离来计算; 即Dis（x，y）。 逗留（y）表示在y中停留的典型持续时间。 在本文中，我们根据经验定义每个位置类别的停留时间; 例如，Cine-ma的停留时间为两小时，属于Coffee的地点为一小时。
（R（u，r，y）+H（y，m）]×sgn
TP\\\\\\Te-Tc-Move（x，y） - Stay（y）]
1+log（Dis（x，y））
(3)
利用估计的用户从位置x到位置y的转换概率，可以生成旅行路线。 首先，用户从路径树的根开始旅行。 然后我们从中计算转换概率树。 在我们从等级2选择一个位置后，我们计算当前时间并确定当前时间是否仍处于同一时间段。 如果是这样，我们从相同级别的位置中选择下一个要推荐的位置，除了之前选择的位置。 另一方面，如果当前时间在下一个时间段，我们建议下一个地点的下一个地点（即3级）。 我们重复上述过程，直到没有时间或地点可供选择。 相同级别的地点没有访问订单限制; 因此，我们需要找到所有可能的旅行路线。 获得所有可能的旅行路线后，我们需要对它们进行排名，以便为用户提供更好的选择。 旅行路线的热量被设置为该路线中所有POI的平均热量。 然后我们根据他们的热度对旅行路线进行排名
实施和评估
数据采集
我们从中国最受欢迎的LBSN之一Jie Pang抓取了一个真实的入住数据集，用户可以分享位置，撰写旅游提示，上传照片等。 我们使用杰邦提供的开放式应用编程接口（API）\来收集用户的登记数据。 本文中使用的数据集是2012年4月至2012年6月收集的。
我们随机选择一组89,936名匿名用户，这些用户在注册后至少在杰朋至少进行了一次登记。 该数据集共包含2,407,647条记录，每条记录包含用户ID，登记时间和地理坐标（纬度/经度）。 表1列出了该数据集的概况。每个用户的平均入场次数约为27.通过检查前20％的活跃用户所做的签入的百分比，我们还可以发现这些活跃用户已经拥有大约80％的登记入场费用。 每个顶级用户平均进行了大约105次签入，这远远超出了常规。
用户界面
我们已经实现了一个系统原型，并在Android平台上构建了一个作为用户界面的应用程序。 可以通过移动用户界面输入旅行需求，包括起始点和开始/结束时间（图3a和3b）。 图3c显示了由几个旅行包组成的推荐结果。 结果列表中的每个项目都包含软件包的简要说明，持续时间和符号标记。 用户可以在电子地图上浏览每个包裹的详细信息（图3d），例如目的地的位置和目的地的建议旅行顺序，然后选择首选包裹。 系统服务器在安装有Web服务器的PC工作站上运行。 客户端和服务器通过HTTP进行通信。
实验结果
为了测试系统的性能，我们分析了从系统中随机选择的10个用户的35个推荐过程。 作为一个真实的例子，系统向用户推荐九个旅行套餐，每个套餐平均包含四个目的地。 大部分推荐目的地都是风景类型，而且包裹中的娱乐目的地非常少。 这是合理的，因为人们总是经常去观光和吃饭，但很少在白天进行娱乐。 整个推荐过程大约需要3秒，这是可以接受的。
| 平均套餐 | 8.2 |
|
|
|
| 平均时隙 | 4 |
|
|
|
| 时间/包 | 358 |
|
|
|
| 目的地/时间段 | 1.34 |
|
|
|
| 餐饮 | 18% |
|
|
|
| 景点 | 63% |
|
|
|
| 娱乐 | 19% |
|
|
|
表2.推荐结果统计
表2显示了35个推荐程序的统计数据。结果表明，推荐程序包的平均数量为8.2，这意味着用户有足够的软件包可供选择。 数据包中的目的地数量与时隙数量有关，每个时隙可以映射到多个目的地。
图4.推荐时间
推荐程序消耗的时间取决于旅行时间的长短。 图4显示了消耗时间和旅行时间之间的关系。 它们之间有近似的线性关系，但最大时间消耗低于5秒，这是用户可以接受的，并且可以通过升级服务器进一步改善。
结 论
在本文中，我们研究了基于移动众包数据的个性化旅行包推荐问题。 该系统不仅可以帮助用户找到有趣的地点，还可以生成由不同类型的地点和访问序列组成的旅行套餐。 作为未来的工作，我们计划将用户反馈纳入系统，旨在为用户提供更准确的建议。 我们还计划考虑多个用户在旅行中的偏好，以便向一组用户推荐旅行套餐[12]。
致 谢
这项工作得到了中国国家基础研究计划（2012CB316400），国家自然科学基金项目（61222209,61373119,61332005）和高等学校博士点专项科研基金（20126102110043）的部分支持。
参考文献
[1]D. Zhang等人，“社会和社区智能的出现”，IEEE Computer，vol。44，2011年7月7日，第21-28页。
[2]Y. Zheng等人，“用户生成的GPS跟踪的学习旅行推荐”，ACM TIST，第2卷，2011年第1期，第2页。
[3]KWT Leung等人，“Clr：A Collaborative Location Recommendation Framework on Co-Clustering，”Proc。 SIGIR '11，2011，第305-14页。
[4]H.Yoon等人，“基于用户生成的GPS轨迹的智能行程推荐”，Proc.Natl.Acad.Sci.USA， UIC '10,2010，pp.19-34。
[5]X.Lu等人，“Photo2trip：Generating Travel Routes from Geo-Tagged Photos for Trip Planning，”Proc。 ACM多媒体会议，2010年，第143-52页。
[6]J. Sang等人的“Probabilistic Sequential POIs Recommendation Via Check-In Data”，Proc。ACM SIGSPATIAL GIS'12,2012，第402-05页。
[7]Q.Liu等人，“Personalized Travel Package Recommendation”，Proc。 ICDM '11，2011，第407-16页。
[8]M. Xie等人，“打破盒子建议：从项目到包装”，Proc。 ACM RecSys'2010年10月，第151-58页。
[9]Y.Ye等人，“A Parallel Apriori Algorithm for Trequent Itemsets Mining，”Proc。 SERA '06,2006，第87-94页。
[10]VW Zheng等人，“GPS历史数据的协作定位和活动建议”，Proc。 WWW '10。，2010，pp.1029-38。
[11]Y. Zheng等人，“GeoLife：一种在用户，位置和轨迹之间的协作社交网络服务”，IEEE Data Eng。 公报，第一卷。 2010年第33卷第2期，第32-39页。
[12]Z. Yu等人，“基于用户配置文件合并的多种观看者的电视节目推荐”，用户模型和用户适应交互，第一卷。 16，没有。 1，2006年，第63-82页。
[13]HP Hsieh等人，“利用大规模签入数据推荐时间敏感路由”，Proc。 SIGKDD'12 Wksp。 “城市计算”，2012年，第55-62页。
[14]EHC Lu等人，“通过挖掘用户签入行为获得多个约束的个性化旅程推荐”
PROC。 ACM SIGSPATIAL GIS'12,2012，第209-18页。
[15]T.Kurashima等人，“在照片共享站点中使用地理标签的旅行路线推荐”，Proc。 “CIKM'2010年10月，第579-88页。
,基于移动众包数据推荐旅游套餐
摘 要
来自基于位置的社交网络服务（LBSN）的移动聚合数据提供了有关个人对位置偏好的信息。 在本文中，我们提出了一个旅行套餐推荐系统，通过利用移动众包数据帮助用户制定旅行计划。 我们提取用户偏好，发现兴趣点（POI），并从登机手续记录中确定位置关系。 然后，我们通过考虑用户偏好，POI特征以及时间 - 空间限制（如旅行时间和开始位置）来生成个性化的旅行套餐。 原型系统是根据中国最受欢迎的LBSN之一Jie Pang的实际众包数据构建和评估的。
介绍
随着传感器嵌入智能手机的日益普及，基于位置的社交网络服务（LBSN）近年来取得了巨大的成功，如Foursquare，\Bliin，\和Jie Pang。\用户不仅可以探索这些LBSN上的位置感知信息，还可以撰写评论并与他人分享他们的经验。 用户共享的所有信息（包括地理坐标和时间信息）组成了这些用户日常生活的时空轨迹。 它们可以被认为是数字化的足迹[1]，它可以被众包并用于帮助我们创造更好的生活。
来自LBSN的移动众包数据提供关于用户对不同位置的偏好的信息以及位置流行度，这可以用于为用户制定旅行计划。 在本文中，我们提出了一个个性化的旅行套餐推荐系统，它利用LBSN中众包的数据。 我们首先从众包数据中构建用户配置文件和位置模型。在LBSN上登记和/或上传照片的行为可以被视为用户与位置之间的实际连接。 在LBSN中，用户访问兴趣点（POI），在那里检查并上传该位置的照片，表明他们对该位置感兴趣。 因此，可以从登记记录中提取用户偏好，POI和位置相关性。 我们然后通过考虑用户偏好，POI特征以及时空约束（如旅行时间和出发地点）来生成个性化的旅行套餐。 与以前的位置推荐系统不同，后者通常会向用户推荐单个位置，我们的系统向用户推荐旅行套餐 旅行套餐不仅包含各种类型的兴趣点（如食物，景点和娱乐设施），还包括所选兴趣点的访问顺序。 最后，我们基于来自中国最受欢迎的LBSN之一Jie Pang的实际众包数据，实施了一个原型旅游套餐推荐系统。 Jie Pang是一个以中国真实地点为基础的领先社区。 除传统社会服务提供的三个维度（时间，人物和事件）外，杰邦还成功引入了第四个维度 - 位置 - 为全球最多的移动互联网用户提供基于位置的社交网络服务。 用户可以使用由Jie Pang提供的服务在某个位置办理登机手续。 这种记录数字足迹的创新和有趣的方式为人们与朋友分享地点，事件和感受提供了极大的方便。 人们还可以在杰邦做很多其他的事情，比如赢得徽章和写作技巧。 这样，在线网络生活和离线现实生活就会更加接近。
本文的其余部分组织如下， 我们回顾相关工作，介绍了个性化旅游套餐推荐系统的体系结构。 我们分别描述用户和位置建模，以及旅行包推荐。 介绍原型实施和评估结果。 然后我们结束这篇文章。
相关工作
位置推荐一直是基于位置服务的热门研究课题。 郑和谢[2]根据多个用户的GPS轨迹在特定的地理空间区域挖掘了文化重要的地方。 考虑到经验和位置利益之间的关系以找到热门位置。 Leung等人 [3]提出了协作定位推荐（CLR）框架，通过考虑活动和不同的用户类来为用户生成定位建议。
图1.系统架构
近年来，基于GPS数据，地理标签照片和入住登记数据，对旅行线路推荐进行了大量研究Yoon等人。 [4]提出了一种基于多用户生成的GPS轨迹生成高效和平衡旅行路线的推荐器。用户只需提供由起点，终点和行程持续时间组成的最小查询即可接收行程推荐。T. Kurashima et al。[15]设计了一种基于概率行为模型的旅行路线推荐方法，该模型估计摄影师从地理标签照片访问地标的概率。 另外，Lu等人 [5]通过利用从带地理标记的照片中恢复的现有旅行线索，提出了自定义的旅行路线计划。 Hsieh等人 [13]建议考虑到地方的普及程度，地点的访问顺序，每个地点的适当访问时间以及从一个地方到另一个地方的过境时间，推荐时间敏感的旅行路线。
Lu等人[14]还从Gowalla挖掘检查数据，根据多种约束条件，社会关系和时间属性推荐个性化旅行。 桑等人。 [6]提出了一种概率方法来排序连续POI类别和POI的列表。 该方法基于当前上下文和签入历史来估计从一个位置到另一个位置的转移概率。
现有的推荐系统主要为用户提供建议列表，但每个建议只包含单个项目或单一类型。 但是，用户打算接收更具体的综合推荐。 例如，向用户提供包含一系列不同类型的位置以及可行的旅行路线的旅行计划将是有用的。
一项研究利用在线旅游信息进行个性化旅行套餐推荐。 然而，目标推荐的旅行套餐是从旅游公司收集的。 我们发现用户可能会喜欢的位置，并根据用户的输入条件动态生成旅行套餐。 谢等人。 [8]认可的综合建议，其中每个建议包括一组项目。 这项工作主要侧重于生成包含一系列物品的包裹，其中所有物品的成本必须由预算覆盖。 尽管我们的工作还生成了由多个旅行地点组成的旅行包，但我们考虑了从LBSN中提取的用户偏好，用户旅行时间以及地点的旅行顺序。
系统架构
我们的目标是建立一个个性化的旅行套餐推荐系统，能够在智能手机上推荐旅行套餐。图1说明了系统架构，主要由三部分组成：用户和位置建模，推荐引擎和移动用户界面。
图2.旅行套餐建议的示意图
用户和位置建模用于从用户登记记录中提取时空特征，例如登记时间，位置和位置类别。 我们使用两级分层分类机制对POI进行分类，每个POI属于一个类c，c是i的一个子类。 例如，POI“p”属于“烧烤”类别，“烧烤”是“食品”的子类别。我们还测量POI的热量。 我们知道，一年中的不同季节或时段对POI的访问流行度有不同的影响。 我们将POI的热量定义为当前POI的受欢迎程度寻找受欢迎的POI以为用户提供更好的选择。 我们将用户的登记数据转换为时空轨迹，以发现经常访问的位置序列。 有了这些信息，我们可以离线模拟用户偏好和位置加热。
推荐引擎旨在生成旅行套餐以满足用户的偏好和特定要求，并在线执行。 它包含三个功能块：POI发现和排名，旅行路线规划和旅行包生成。 POI发现和排名模块用于发现用户可能感兴趣的位置，并根据用户偏好和位置模型对这些发现的POI进行排名。 通过发现和排序的位置，旅行路线规划将根据位置转换概率找出适当的访问顺序。 转移概率表示从一个POI转移到另一个POI的概率。 它是通过考虑两个POI之间的距离，候选POI的热量等来获得的。 旅行包生成块计算计划的旅行路线的转移概率之和，并选择转移概率和最高的旅行路线。
移动用户界面允许用户输入需求并在用户的手机上显示推荐结果。 用户需求包括访问城市，起点，开始时间和结束时间。 系统然后将建议的结果返回给用户移动电话。 用户可以查看地图服务中推荐的每个旅行套餐的详细信息，例如套餐中包含的POI和访问顺序。
用户和位置建模
在本节中，我们将详细描述用户和位置建模。 首先，我们展示如何根据用户签入历史记录生成用户配置文件。 然后我们描述测量POI热量的方法。 最后，我们提出了提取频繁位置序列的方法。
用户资料
位置的用户偏好在一天中的不同时间是不同的。 例如，人们通常在早上和下午去观光，并在中午和晚上吃饭。 我们将一天划分为六个时段，并在每个时段（即0：00-8：00,8：00-12：00,12：00-14：00,14：00-18：00 ，18：00-20：00和20：00-24：00）。 由于人们通常在0：00-8：00期间入睡，因此我们在这些时间内不会考虑用户的偏好。 我们的系统主要推荐三种类型的位置：食物，景点和娱乐。 因此，我们测量了三种类型的POI在每个时间段的用户偏好。
用户配置文件被表示为特征向量。 每个元素指示用户对一种位置类型的偏好。 我们将位置类型i的时间段r中的用户偏好表示为F\，其被计算为用户的次数的比率已经访问了位置类型i到用户在时间段r访问过所有位置类型的时间。 根据上述定义，我们可以获得用户配置文件（即，用户在一天中的不同时间针对不同类型的位置的偏好。
POI HEAT
据我们所知，地点的受欢迎程度可能会逐月变化。 例如，一个植物园通常在春季有很多游客，冬季游客较少。 我们在向用户推荐兴趣点时会考虑时间对地点流行度的影响。
我们测量每个月的POI热量。 我们将m月的POI o的热量定义为Eq。 1，其中VT（o，m）表示第m个月POI o的访问次数。 评级（o）代表POI o的平均分数。 许多LBSN像杰邦，允许用户根据他们的经验评估地点。 由于地理位置的评分范围从1到10，因此我们需要在计算位置的流行度时对其进行标准化。 a和b表示方程（2）中两部分的权重。 我们在现行制度中将它们设定为1.5和1。
| H（o，m）=α* | VT（o，m） | + β * | 评级（o） |
|
|
|
|
|
|
| ||
| Σ\VT（o，m） | 10 | (1) |
|
位置依赖性
访问过的位置之间有相关性。 例如，人们喜欢晚餐后去附近的咖啡店或酒吧。 在上海，游客往往在参观东方明珠塔后去外滩。 因此，探索相关POI推荐的频繁位置序列是很有用的。首先，我们根据用户签入记录中的位置访问顺序生成时空轨迹。 然后我们使用Apriori算法[9]来提取频繁的位置序列。
旅行套餐建议
图2显示了旅行套餐推荐的流程。我们首先发现用户当前位置周围的有趣位置，并根据用户的登记历史对发现的位置进行排名。我们重复上述过程，直到我们获得每个时间段的位置列表。因此，我们可以在一天的不同时间段获得POI的排名列表。 然后我们根据这些POI列表进行旅行路线规划。我们定义转换概率来估计从一个位置移动到另一个位置的概率。 我们利用这个概率来绘制这些位置的最佳访问顺序，并生成组合位置以及访问顺序的包。
POI发现和排名
我们将旅行时间分为用户输入旅行开始时间和结束时间之间的时间段。 然后我们可以得到时间段列表在其上发生旅行，记为TimeList。 我们根据用户的登记历史确定TimeList中每个时间段的推荐位置类型。 根据每个用户在不同时间段的访问地点类型，我们发现人们倾向于在一定时期访问同一类型的地点。 因此，我们选择用户最常访问的位置类型作为每个时间段的目标推荐位置类型。 使用TimeList中每个时间段的推荐位置类型，我们在用户的起始位置周围指定一个区域。 在我们的工作中，我们选择一个圆形区域作为目标推荐区域，以用户的起点为中心。该区域中的所有位置组成目标推荐位置集。
在设定目标推荐位置后，我们需要根据用户的喜好对位置进行排名。 让Like（u，r，j）表示用户u对时间段r中的位置j感兴趣。 我们应该为用户喜欢的位置分配更高的分数。 一般来说，在旅行中品味相同的用户通常会有类似的旅行历史。 我们采用基于用户的协作过滤[10]来估计用户对位置j的偏好，其基本思想是基于类似用户的偏好来测量用户对位置的偏好。 在这里我们使用余弦相似度[11]来衡量用户之间基于用户pro-files的相似度。 因此，我们可以测量用户对位置j的偏好，如公式（1）所示。2，其中Sim（u，v，i）表示位置类型i的用户u和用户v之间的相似度。U（u，i）是位置类型i的u的类似用户的集合。 我们可以根据用户v的签入历史记录计算Like（v，r，j）。Like（v，r，j）表示用户v的位置j的签到号码与签到用户在时间段r在所有地点的人数。
| 像（u，r，j）= | Σ我明白了\\\\\Sim（u，v，i）Like（v，r，j） |
|
|
| ΣTFU（u，i）辛（U\\\\ | (2) |
我们对类型与此时间段的推荐位置类型相匹配的位置进行排名，然后选择每个排名列表中前N个位置作为每个时间段的推荐位置列表。
旅行路线规划
旅行路线规划旨在根据用户的旅行时间和地点从POI列表中选取一系列位置，然后生成一系列合适的旅行路线供用户选择。 我们提出了一个旅行路线生成算法。 该算法将旅行路线构建为路径树，并将用户的旅行起始位置作为根。 我们将每个时间段的POI列表中的位置映射到不同级别的树节点中。 发现时间为r的POI被映射到路径树的第rth层节点。 然后，旅行路线规划可以被视为漫游在树节点之间并产生可行路径的问题。
我们将从用户u的位置x到位置y的转移概率定义为TP（u，x，y）in我们提出了一个旅行路线生成算法。 算法将旅行路径构建为路径树，以用户的旅行起始位置为根。 我们将每个时间段的POI列表中的位置映射到不同级别的树节点中。
图3.移动用户界面：a）-b）出差需求输入; c）包装清单; d）包装细节。
| 条目数量 | 2,407,647 |
|
|
|
|
|
| 用户数量 | 89,936 |
|
|
|
|
|
| 每个用户的平均条目数 | 26.77 |
|
|
|
|
|
| 顶部条目的平均数量 | 105.3 |
|
| 20％的用户 |
| |
|
|
| |
|
|
|
|
