一种基于协同过滤的旅游行程推荐算法

方 潇，刘晓寒，柴永平，周文曼

（1.信息工程大学 地理空间信息学院，河南 郑州 450052；2. 92292部队，山东 青岛 266000；3.东华理工大学 地球科学学院，江西 南昌 330000）

一种基于协同过滤的旅游行程推荐算法

方 潇1，刘晓寒1，柴永平2，周文曼3

（1.信息工程大学 地理空间信息学院，河南 郑州 450052；2. 92292部队，山东 青岛 266000；3.东华理工大学 地球科学学院，江西 南昌 330000）

针对现有的个性化推荐算法在旅游行程推荐领域应用较少，技术不成熟等缺陷，提出基于一种改进协同过滤算法的行程推荐算法。该算法首先依据偏好度计算方法分析用户对于不同类型旅游目的地的偏好程度，形成用户-旅游目的地偏好矩阵，并基于偏好矩阵优化K-Means算法的初始聚类中心，为目标用户建立邻近用户集，最后利用改进的相似度计算方法为目标用户寻找偏好相似的历史用户，从而产生行程推荐。实验结果表明，该算法能够快速搜索较小的邻近用户，得出推荐结果，不仅具有较快的推荐效率，而且具备较好的推荐精准度，在一定程度上为个性化旅游行程推荐服务提供了支撑。

个性化推荐；用户偏好；协同过滤算法

旅游业的蓬勃发展及大众旅游热情的高涨，使得目前主流旅游信息服务平台提供的海量旅游信息过载，而解决旅游信息过载的一个重要方法是个性化推荐技术[1]。国内外关于个性化旅游推荐的研究成果非常多，现有算法可分为两类：①通过问答交互的方式获取用户需求，产生景点和酒店的推荐。例如：Ahas R[2]等以爱沙尼亚为例，对旅游者的旅游活动进行了问卷调查，并分析了其偏好的个性化旅游目的地信息；麻风梅[3]等通过在线访谈的方式获取用户旅游需求，以计算旅游综合兴趣度的方法为其推荐景点；王显飞[4]等通过会话的方式启发用户需求，以约束旅游知识库的方式产生景点和酒店的推荐。②通过挖掘用户历史日志的方式来获取用户兴趣偏好。例如，HAO Qiang[5]等通过主题建模从游记中挖掘信息并给用户推荐旅游目的地；吕红亮[6]等通过挖掘用户-景点-线路的方式来提取旅游行程，以匹配旅游行程库的方式来产生推荐；侯新华[7]等通过在线挖掘获取用户日志对景点的评价来产生旅游信息的推荐。

当前大多数算法都是依靠用户对于景点与旅游路线的评分信息来匹配“相似用户”，实现旅游推荐的。虽然能有效地为用户推荐旅游信息，然而，在当前繁忙的网络社会中，显式的评分信息只会越来越少，隐式的操作信息与历史记录会逐渐成为获取用户信息的主要来源，传统的评分式推荐方法将面临更大的挑战，如何有效地挖掘用户的隐式偏好信息成为了推荐领域中亟待解决的难题。

本文基于用户对于旅游目的地类型的偏好影响行程选择这一基础理论来构建用户模型，依据用户对于多种旅游目的地类型的偏好来优化K-Means的初始聚类中心，并引入偏好度与改进相似度的计算方法来优化传统的协同过滤算法。

1 传统的协同过滤算法

协同过滤算法的核心思想是通过对用户评估矩阵的分析得到目标用户的最邻近用户集合，然后根据最邻近用户集合对项目的评价来预测目标用户对该项目的评价，从而产生推荐[8]。迄今为止，协同过滤算法在个性化推荐技术中应用非常广泛，技术也相对成熟。

协同过滤算法分为两类：基于项目的协同过滤算法与基于用户的协同过滤算法。本文主要针对研究内容，着重介绍基于用户的协同过滤算法。

基于用户的协同过滤算法分为3个阶段[9]： ①数据表述，在协同过滤算法中，输入的初始数据通常可以表达为一个M×N的用户-评分矩阵，在这个矩阵中，M为用户的数量，N为项目数量，而矩阵中的值可以认为是用户M对于项目N的评分。②建立邻近矩阵，在获取用户-项目评分矩阵数据后，如何搜寻与目标用户具有相同兴趣的相似用户成为协同过滤算法的关键。常用的邻近矩阵建立方法是先利用K-Means算法聚类用户，然后计算类中目标用户与其他用户之间的兴趣相似度，通过相似度的大小对用户进行排序，从而为目标用户构建最邻近用户集。③产生推荐数据集，通过寻找相似用户集中用户评分较高项目，产生Top-N的推荐集合。

2 基于协同过滤的旅游行程推荐算法

2.1 算法流程

通过研究分析现有的旅游用户资料，总结得出旅游目的地的6种主要类型：自然风景型、历史文化型、民俗风情型、宗教圣地型、刺激冒险型与商务会议型。算法首先通过数据挖掘技术与偏好度计算，获取旅游用户对于这些目的地类型的偏好度，建立用户-旅游目的地类型偏好矩阵；然后利用多种类型偏好作为K-Means的初始聚类中心，聚类偏好相似度较高的旅游用户，形成多个最邻近旅游用户集；最后将偏好度代替项目评分值计算各邻近集中的用户相似性，从而为目标用户寻找最相似用户，得出一个或多个Top-N行程推荐集。算法流程如图1所示。

图1 算法流程图

2.2 算法框架

2.2.1 旅游用户目的地偏好建模

用户模型是实现个性化旅游行程推荐的基础，本文采用基于旅游目的地类型的空间向量模型来表示用户对目的地选择的偏好，即将模型表示为一个N×6的用户-旅游目的地类型偏好度矩阵SNM，其中，N代表用户的数量，M代表6类旅游目的地类型，SNM值代表第N个用户对第M项旅游目的地类型的偏好度。该矩阵可以用表1来解释。

2.2.2 偏好度计算

本研究引入电商推荐的偏好度算法。根据用户一段时间对行程的选择，分析其对各旅游目的地类型的偏好程度；然后依据用户的偏好程度，对这些旅游目的地类型特征赋相应的值，即当前用户对于旅游目的地类型的偏好度。

表1 用户-旅游目的地类型偏好度矩阵

旅游目的地的偏好度定义为：将旅游用户某时间段内选择的行程的特点进行统计，旅游目的地类型i的偏好度Ci为用户已选择的行程中包含旅游目的地类型i的数量与其旅游总次数的比值[10]：

其中，n为某段时间内用户选择行程的总数量；m为某段时间内用户选择行程时包含某旅游目的地类型数量。若用户未曾选取包含某旅游目的地类型的行程时，则用户对于该旅游目的地类型的偏好度为0。

2.2.3 基于旅游目的地类型偏好的K-Means改进算法

K-Means算法的核心在于其能随机产生聚类中心，对目标群体进行无监督分类，然而随机选取的聚类中心无法体现各旅游目的地类型的偏好差异。因此，本文通过前文分析得出的6类旅游偏好设定6个初始聚类中心，将所有旅游用户聚类成6个最邻近用户集。

1）设定每个旅游用户最多归属到3类最邻近用户集，依据由大至小的排序方式对当前用户的偏好度进行排序，选取前3项偏好值进行比较：

其中，Ri、Rj、Rk为当前用户偏好度最大的3 项偏好值；ε为阈值，用来区分偏好度的大小。

2）通过上述约束条件输出用户偏好值，确定所有旅游用户所归属的最邻近用户集。

该分类算法相比传统的K-Means算法具有较好的稳定性，无需算法迭代。

2.2.4 偏好相似度算法

用户获取了最邻近用户集后，相似度计算方法成为目标用户寻找相似用户的重要手段，也是用户获取最终Top-N推荐集的关键步骤。本文分析了电商推荐的相似性算法，并考虑旅游行程推荐的现实情况，尝试以偏好度代替项目评分的方法，计算用户对于旅游目的地类型的偏好相似性。

其中，Ra,p与Rb,p分别为用户a与用户b对于某项旅游目的地类型的偏好度；与分别表示用户a与用户b所有旅游目的地类型的偏好度平均值；Q（ a， b）为用户a与用户b旅游目的地类型的偏好相似度；T（ a， b）为用户a与用户b共同的旅游目的地类型偏好集。

通过计算得出目标用户与最邻近用户的相似度大小，并依据相似度大小对相似用户进行排序。

2.2.5 产生推荐

为了不让推荐的结果过于复杂，本文将尽可能依据目标用户历次旅游的真实情况来筛选最邻近用户集中的历史行程（例如，目标用户的主要出发地为北京，平均旅游花销约为3 000元，出行方式主要为自驾，且该用户一般在法定假期出游，那么算法将筛选最邻近用户集中符合出游时间在法定假期、旅游花销约为3 000元、目的地距离北京较近且目标用户未曾拥有的历史行程，产生推荐），并依据最邻近用户的相似程度，对获取的行程进行排序，形成Top-N推荐集合。

3 实验结果及分析

3.1 实验数据

本研究分别从蚂蜂窝和携程网的攻略社区选取游记或攻略数量超过10篇的旅游用户70人；通过文本挖掘与用户分析手段，随机提取每名用户的10条旅游行程，并确定用户历次选择旅游目的地的类型（表2）。采用C#语言，基于VS2010开发平台，并利用SQL数据库技术进行用户建表与数据存储。

表2 实验用户-历史行程数据表

3.2 实验方法

首先依据算法流程和实验数据，计算每名用户对于各种旅游目的地类型的偏好度，且偏好度之和为1；然后设定阈值ε = 0.3进行用户聚类，得到以旅游目的地类型偏好为聚类中心的6类最邻近用户集；分别计算每类最邻近用户集中各用户之间的旅游目的地类型偏好相似度，为每个用户求解最邻近用户集（用户集中一般包含10个用户），并通过每个用户历次旅游的真实情况来筛选该最邻近用户集的历史行程，产生维度为3的推荐列表（即产生3个的行程推荐）。

3.3 实验结果及分析

利用互联网将140份行程推荐列表发送至原始实验用户，返回结果116份，随机抽取100份结果，并通过准确率评价算法与满意度调查（采用第1推荐时，满意度记为非常好；采用第2推荐记为良好；采用第3推荐记为一般；未采用推荐则将满意度记为差）来检验推荐结果。

其中，RC为用户采纳的行程推荐数量；RU为未采纳的行程推荐数量；RC+RU为100。统计结果如表3所示。

实验结果表明，推荐的准确率（用户采纳率）为87.4%。以非常好记10分、良好记8分、一般记6分、差记0分的积分手段，累计得出用户综合满意值为806（总分1 000），则满意度为80.6%。

4 结 语

本文通过研究旅游行程的个性化推荐问题，提出了基于改进协同过滤的旅游行程推荐算法。该算法通过计算用户对于旅游目的地类型的偏好度，并用其代替项目评分计算用户之间的相似度，使之适合用户多兴趣下的个性化推荐[11]。实验表明，该算法具有较高的准确度与推荐效率，能提高个性化旅游行程推荐的满意度。但目前的旅游偏好模型构建尚不完善，旅游用户的兴趣建模还需深入研究。在下一步工作中，可从用户旅游动机入手，获取更多用户建模方法，以寻求更优推荐。

表3 推荐结果表

[1] Adomavicius G,Tuzhilin A.Toward the Next Generation of Recommender Systems:a Survey of the State-of-the-art and Possible Extensions[J].IEEE Transactions on Knowledge and Data Engineering, 2005,3(5):734-749

[2] Ahas R,Aasa A,Roose A,et al.Evaluating Passive Mobile Positioning Data for Tourism Surveys:an Estonianease Study[J]. Tourism Management,2007,3(4):l-18

[3] 麻风梅.基于游客综合兴趣度的旅游景点推荐[J].测绘与空间地理信息,2014(3):56-58

[4] 王显飞,陈梅,李小天.基于约束的旅游推荐系统的研究与设计[J].计算机技术与发展,2012(2):23-26

[5] HAO Qiang,CAI Rui,WANG Changhu,et a1.Equip Tourists with Knowledge Mined from Travelogues[C].Raleigh NC USA,2010

[6] 吕红亮,王劲林,邓峰.一种个性化旅游线路推荐算法[J].网络新媒体技术,2012(3):42-48

[7] 候新华,文益民.基于协同过滤的旅游景点推荐[J].计算技术与自动化,2012,31(4):116-119

[8] 雷锟.电子商务个性化推荐系统研究[D].成都:电子科技大学,2012

[9] 王桂芬.电子商务个性化推荐系统中协同算法的研究与应用[D].南昌:南昌大学,2012

[10] 李峰,李军怀,王瑞林,等.基于商品特征的个性化推荐算法[J].计算机工程与应用,2007,43(17):194-197

[11] 余力,刘鲁,李雪峰.用户多兴趣下的个性化推荐算法研究[J].计算机集成制造系统,2004,10(12):1 610-1 615

表6 安置区和转移单元各自满意优先顺序

表7 安置区与转移单元的最佳匹配

参考文献

[1] 胥淼.从自然灾害透视人与自然的和谐发展[D].成都:成都理工大学,2011

[2] 田质胜,朱庆利,李明霞,等.基于GIS的洪灾避迁方案的模糊综合评判[J].中国农村水利水电,2009(10):81-83

[3] 蓝秋萍. GIS在洪水受灾人员转移方案设计中的应用研究[D].武汉:华中科技大学,2007

[4] 文成日,耿祥义.层次分析法在购车决策中的应用[J].电脑知识与技术,2009(30):8 514-8 515

[5] 吴大亲,么文学.基于层次分析法的应用型人才培养评价模式研究[J].长春师范学院学报(自然科学版),2010(8):28-31

[6] 黄晓菁.基于AHP方法的图书馆信息服务能力研究[J].情报杂志,2007(9):149-151

[7] 段春生.基于双向选择的匹配问题[J].西南师范大学学报(自然科学版),2012(8):15-18

第一作者简介：征程，硕士研究生，研究方向为空间信息分析与应用。

P208

B

1672-4623（2016）07-0053-04

10.3969/j.issn.1672-4623.2016.07.016

方潇，硕士研究生，主要研究方向为地学可视化。

2015-01-23。

项目来源：国家高技术研究发展计划资助项目（2012AA12A404）；国家自然科学基金资助项目（41171353）。