一种基于游客选择景点的旅游拼团算法

梁弼，赵文辉，杨斌，许晓红

(四川文理学院，智能制造学院，四川，达州 635000)

0 引言

我国旅游业自改革开放以来经历了起步、成长、拓展和综合发展4个阶段，实现了从旅游短缺型国家到旅游大国的历史性跨越。如今，我国已经进入大众旅游时代，并成为世界最大的旅游市场[1]，伴随着GPS定位、地图API和网络技术的迅速发展与广泛应用，国内已出现了许多旅游服务平台，如途牛、携程、去哪儿等[2]。然而，目前大部分旅游服务平台中的团游模块都是基于景点的拼团，即先定景点，再让游客选择目标景点参加拼团，最后在旅游公司相关人员的安排下完成拼团游。这种模式属于“景点”选择“游客”，而不是“游客”选择“景点”，它是一种简单的拼团方式，存在着很多问题和限制(譬如很低的拼团成功率)。这不能满足现代游客及旅游公司的需求。

随着拼团游越来越流行，智能拼团问题已成为旅游研究领域的一个新问题，为了将个性化需求相同或相似的游客恰当地拼在一起，提高拼团的成功率和游客的满意度，减少游客在旅游途中的经济负担等问题，本文提出了一种基于游客需求特征的旅游拼团算法(TGA)，该算法能够恰当处理游客个性化需求的特征信息，如目标景点、性别、年龄、距离、费用、出游人数和天数等，并按照这些需求特征信息快速匹配出优选的拼团组合及对象，有效提高拼团的成功率，进而促进旅游业发展。

1 基础算法

1.1 正向最大匹配算法

基于词典的最大正向匹配算法源于“每次从句子中切分出尽量长的词语”的思想[3]。一般情况下，一个词语所含的信息量和这个词的长度有正相关的关系，其算法步骤是从左到右将待分词文本中的几个连续字符与词表匹配，匹配成功则切分出一个词，否则去掉匹配字段的最后一个字再重新匹配，循环重复，直至切分出所有词[4]。但这里有一个问题是要做到最大匹配，并不是第一次匹配到就可以切分，同时最大匹配出的词必须保证下一个扫描不是词表中的词或词的前缀才可以结束。

1.2 逆向最大匹配算法

逆向最大匹配算法也是基于字符串匹配分词算法的一种，与之前所述的正向最大匹配算法类似，其主要的区别在于扫描方向的不同。正向最大匹配算法是从左往右依次扫描，而逆向最大匹配算法则从右往左扫描。与正向最大匹配算法相比，逆向最大匹配算法出现歧义现象较少，且准确度往往比前者高，其分词步骤[5]如下：

(1) 将文章分成句子(通过标点符号来实现)；

(2) 将分成的每一个句子S循环地读入，并且把句子字数设为x；

(3) 规定一个最大词的长度，这便是即将要截取词的最大长度m；

(4) 取句子中n-m到x的字符串s，并在字典查找，如果查到则执行(5),没有就执行(6)；

(5) 记住s，从n-m赋值给x，继续执行(4)，直到x=0；

(6) 将m-1，再执行(4)。

1.3 N-Gram语言模型

简化版本的N-Gram语言模型为p(wt|w1,w2,…,wt-1)≈p(wt|wt-n+1,…,wt-1)，该模型是自然语言处理中一个非常重要的概念，通常在NLP中人们基于一定的语料库，可以利用N-Gram来预计或者评估一个句子是否合理，常见的如bigram模型(N=2)和trigram模型(N=3)[6]。N-Gram的另外一个作用是用来评估2个字符串之间的差异程度，这是模糊匹配中常用的一种手段[7]。通过对模型进行一些处理，让其能够在算法中对分词结果进行相关歧义的消除。

2 问题描述及数学建模

2.1 问题描述

本文研究的旅游拼团问题属于多游客带有特定条件的智能匹配问题。在拼团的过程中，有3个至关重要的问题需要解决：① 游客的个性化需求该如何处理；② 面对如此多的拼团信息，如何才能匹配到最佳的拼团组合及对象；③ 拼团的成功率和准确率如何进一步提高。具体来讲，游客通过输入起点、终点以及相应的个性化需求信息(如年龄、距离、费用、出游人数和天数等)，然后拼团算法通过比对这些需求特征并筛选出初步的拼团组合，再结合地图返回的经纬度以及目的地等详细信息，运用最大匹配算法及相关距离公式来计算相似度并进行比较，从而得出合适的拼团组合及对象，成功完成了游客拼团信息的智能匹配。

2.2 数学建模

个性化需求特征包括游客对于拼团有不同的要求，有的游客希望节省费用，而有的希望在有限的出行天数内观赏到尽量多的景点。基于此，拼团算法在为游客匹配最佳的拼团组合及对象前，需要对这些个性化需求信息进行预处理，这对提高拼团算法的准确度有所帮助。我们定义一个条件集D= {d1,d2,d3,…,dn}，它代表每位游客具体的个性化需求特征(即个性化条件限制)。本文考虑的游客个性化需求特征主要包括目标地点、性别、年龄、时间、距离、费用、出游人数和天数等。

距离计算。游客输入目的地之后百度地图返回经纬度，这里有2种方法可以计算出2个地点之间的真实距离。一是根据百度地图的API调用相应的方法直接得到两地之间的距离；二是通过相应的经纬度计算公式来计算2个地点之间的真实距离[8]。所提出的TGA算法采用的是第二种方法，而且游客在输入目的地进行拼团信息匹配的时候，利用经纬度能够让游客所处的地点更加精确，这样更有利于精确地计算距离，其公式为distance=arccos(sin(lat1)×sin(lat2)+cos(lat1)×cos(lat2)×cos(lng2-lng1))×R。其中，distance代表两地之间的真实距离，lat1、lat2、lng1、lng2分别代表两地的纬度和经度，R则代表地球半径。

相似度计算。在进行拼团信息处理时，本拼团算法先采用正、反最大匹配算法来得到2组分词结果，再使用N-Gram语言模型来对所产生的分词结果进行处理，接着根据分词的结果来计算2个目标之间的相似度。关于如何匹配正确的目的地及计算2个地点的相似度，常用的方法有余弦相似度、欧几里得距离、SimHash + 汉明距离、编辑距离等，本文所设计的TGA算法中采用余弦相似度方式进行计算，其具体计算公式[9]为

(1)

3 游客选择景点的拼团算法(TGA)设计

3.1 算法描述

为了提高拼团的成功率和满意度，本文提出了一种“游客”选择“景点”的旅游拼团算法(即TGA算法)。该算法的关键点在于分词，其难度是如何正确地切分以及切分准确度。如果单一地使用正向最大匹配算法或逆向最大匹配算法，那么根据分词词典的好坏便会产生不同的分词结果。虽然使用双向最大匹配算法可以解决大部分的中文分词问题，并且分词的准确度也有所提升，但还是存在着诸多的不足，例如分词划分不合理等。综上，本文采用N-Gram语言模型对最大匹配算法产生的分词结果进行处理，消除了相关的歧义，从而提高了分词结果的准确度。

TGA算法核心思想是通过结合游客的个性化需求特征，在需求特征限制条件的约束下，使用地图返回的经纬度进一步筛选范围内的拼团信息集合，然后根据目的地等详细信息，运用最大匹配算法及相关距离公式计算相似度并进行比对，从而得出合适的拼团组合及对象，成功完成游客的拼团。另外，本文把经纬度及相似度分数等作为匹配拼团对象的重要指标。TGA算法的具体描述如下。

输入：游客个性化需求特征D及目标地点。

输出：满足游客需求的拼团对象。

Step1 遍历拼团信息集合S，筛选满足游客个性化需求特征D的拼团信息；

Step2 通过经纬度计算目标地点与要匹配的地点之间的距离，可以筛选出部分合适的拼团对象(t的集合)；

Step3 使用最大匹配算法分别对目标地点详细信息与拼团详细信息进行分词，得出2组分词结果；

Step4 通过使用N-Gram语言模型来消除分词歧义，并对N-Gram分值进行对比和计算，从而得到最终的分词结果；

Step5 构建有向无环图的最优路径；

Step6 计算相似度分数；

Step7 返回分值最高的10个对象与t的集合。

3.2 算法流程

根据TGA算法核心思想及描述过程，我们设计出该算法的执行流程如下。

Input：游客个性化需求特征D及目标地点。

Result：满足游客需求的拼团对象。

(1) for 要匹配的拼团信息集合S。

(2) if 满足游客个性化需求特征D。

(3) returns(s为满足条件的拼团信息)。

(4) for 满足游客个性化限制条件的集合T。

(5) if 两地经纬度计算的真实距离<10 km。

(6) returnt(t为满足在10 km范围内的拼团信息)。

(7) else。

(8) 对目的地与拼团信息进行分词。

(9) 通过N-gram语言模型为得到的两个分词结果消除歧义，构建有向无环图的最优路径。

(11) 得到score(score为相似度分数，是对similarity进行处理后的数据)。

(12) returnt的集合与分值最高的10个拼团对象。

具体流程图如图1所示。

图1 TGA算法流程图

4 实验及结果分析

为了验证TGA算法的有效性及性能，我们以爬取到的旅游拼团信息作为数据集，并将拼团信息数量划分为5个点，即100、200、300、500、1 000，同时设性别、年龄、时间、距离、费用、出游人数和天数等作为实验的验证参数。实验内容包括：不同需求特征数对拼团成功率及时间的影响；拼团信息数量对拼团成功率及时间的影响；拼团结果经纬度的区间分布情况分析。其实验环境为：Intel(R)Core(TM)CPU@2.80 GHz，2.79 GHz，8 GB 内存，操作系统为 Windows 10。

4.1 不同需求特征数对拼团成功率及时间的影响

设置不同数量的需求特征参数(包括性别、年龄、时间、距离、出游人数和天数等)，在匹配之前根据个性化需求特征的限制条件去搜索合适的对象，然后再进行分词相似度的计算，并显示所用的时间。其实验结果如图2、图3所示。

由图2、图3可看出，TGA算法按照游客的个性化需求特征匹配到了合适的拼团对象，并且游客的个性化需求特征限制条件数量越多，拼团的准确度会越精确，但拼团的成功率会下降，同时所花费的时间也会逐渐增长。

图2 拼团成功率

图3 拼团所耗时间

4.2 拼团信息数量对拼团成功率及时间的影响

设置拼团信息数量从100增加到1 000，因为拼团信息数据量的增加，TGA算法需要计算的数据便会增大，所耗费的时间也会随之增加。同时，根据游客的输入需求特征，所能匹配的数据量也会增大，所以拼团成功率也会相应的提升。其实验结果如图4、图5所示。

图4 拼团成功率

由图4、图5可看出，拼团信息数量越多，拼团的成功率会越高，但所花费的时间也会随之增长。

图5 拼团所耗时间

4.3 拼团结果经纬度的区间分布情况分析

通过对拼团的结果数据进行分析，可以得出数据样本具有分布的不均匀性、类间分布的差异性2个特点，以及拼团信息主要的分布区间、拼团成功的主要分布区间、拼团失败的主要分布区间等信息，具体情况如图6、图7所示。

从图6、图7可以看出，拼团失败较多的经纬度范围，并对该范围内的拼团数据进行处理和优化，进一步提高拼团的准确度和成功率。

(c) 拼团未成功的反类出发地经纬度的样本分布

(c) 拼团未成功的反类目的地经纬度的样本分布

5 总结

随着国内外旅游业的发展，拼团游开始流行起来，但由于游客个人需求不一样，从而导致他们很难找到合适的驴友一起外出旅游。虽然现在很多的旅游服务平台已有拼团这一模块，但其中大部分拼团模块都是基于景点的拼团，即“景点”选择“游客”的模式，该模式以景点为目的地让游客拼团，这使得游客只能选择平台中已有的景点作为旅游地点，有着极大的限制。而本文所提出的TGA算法是一种“游客”选择“景点”模式，它可以根据游客的个性化需求特征来匹配合适的拼团组合及对象，这在一定程度上提高了游客的自由度和满意度。然而，该算法还存在一些不足之处，譬如需求特征目前考虑得较少，没完全体现出游客的个性化需求，后续将根据游客的个人偏好特征来进行优化，使其能更智能地为游客匹配到满意度更高的拼团组合及对象。