一種基于游客選擇景點的旅游拼團算法

梁弼，趙文輝，楊斌，許曉紅

(四川文理學院，智能制造學院，四川，達州 635000)

0 引言

我國旅游業(yè)自改革開放以來經歷了起步、成長、拓展和綜合發(fā)展4個階段，實現了從旅游短缺型國家到旅游大國的歷史性跨越。如今，我國已經進入大眾旅游時代，并成為世界最大的旅游市場[1]，伴隨著GPS定位、地圖API和網絡技術的迅速發(fā)展與廣泛應用，國內已出現了許多旅游服務平臺，如途牛、攜程、去哪兒等[2]。然而，目前大部分旅游服務平臺中的團游模塊都是基于景點的拼團，即先定景點，再讓游客選擇目標景點參加拼團，最后在旅游公司相關人員的安排下完成拼團游。這種模式屬于“景點”選擇“游客”，而不是“游客”選擇“景點”，它是一種簡單的拼團方式，存在著很多問題和限制(譬如很低的拼團成功率)。這不能滿足現代游客及旅游公司的需求。

隨著拼團游越來越流行，智能拼團問題已成為旅游研究領域的一個新問題，為了將個性化需求相同或相似的游客恰當地拼在一起，提高拼團的成功率和游客的滿意度，減少游客在旅游途中的經濟負擔等問題，本文提出了一種基于游客需求特征的旅游拼團算法(TGA)，該算法能夠恰當處理游客個性化需求的特征信息，如目標景點、性別、年齡、距離、費用、出游人數和天數等，并按照這些需求特征信息快速匹配出優(yōu)選的拼團組合及對象，有效提高拼團的成功率，進而促進旅游業(yè)發(fā)展。

1 基礎算法

1.1 正向最大匹配算法

基于詞典的最大正向匹配算法源于“每次從句子中切分出盡量長的詞語”的思想[3]。一般情況下，一個詞語所含的信息量和這個詞的長度有正相關的關系，其算法步驟是從左到右將待分詞文本中的幾個連續(xù)字符與詞表匹配，匹配成功則切分出一個詞，否則去掉匹配字段的最后一個字再重新匹配，循環(huán)重復，直至切分出所有詞[4]。但這里有一個問題是要做到最大匹配，并不是第一次匹配到就可以切分，同時最大匹配出的詞必須保證下一個掃描不是詞表中的詞或詞的前綴才可以結束。

1.2 逆向最大匹配算法

逆向最大匹配算法也是基于字符串匹配分詞算法的一種，與之前所述的正向最大匹配算法類似，其主要的區(qū)別在于掃描方向的不同。正向最大匹配算法是從左往右依次掃描，而逆向最大匹配算法則從右往左掃描。與正向最大匹配算法相比，逆向最大匹配算法出現歧義現象較少，且準確度往往比前者高，其分詞步驟[5]如下：

(1) 將文章分成句子(通過標點符號來實現)；

(2) 將分成的每一個句子S循環(huán)地讀入，并且把句子字數設為x；

(3) 規(guī)定一個最大詞的長度，這便是即將要截取詞的最大長度m；

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

(5) 記住s，從n-m賦值給x，繼續(xù)執(zhí)行(4)，直到x=0；

(6) 將m-1，再執(zhí)行(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 數學建模

個性化需求特征包括游客對于拼團有不同的要求，有的游客希望節(jié)省費用，而有的希望在有限的出行天數內觀賞到盡量多的景點?；诖?，拼團算法在為游客匹配最佳的拼團組合及對象前，需要對這些個性化需求信息進行預處理，這對提高拼團算法的準確度有所幫助。我們定義一個條件集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 構建有向無環(huán)圖的最優(yōu)路徑；

Step6 計算相似度分數；

Step7 返回分值最高的10個對象與t的集合。

3.2 算法流程

根據TGA算法核心思想及描述過程，我們設計出該算法的執(zhí)行流程如下。

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語言模型為得到的兩個分詞結果消除歧義，構建有向無環(huán)圖的最優(yōu)路徑。

(11) 得到score(score為相似度分數，是對similarity進行處理后的數據)。

(12) returnt的集合與分值最高的10個拼團對象。

具體流程圖如圖1所示。

圖1 TGA算法流程圖

4 實驗及結果分析

為了驗證TGA算法的有效性及性能，我們以爬取到的旅游拼團信息作為數據集，并將拼團信息數量劃分為5個點，即100、200、300、500、1 000，同時設性別、年齡、時間、距離、費用、出游人數和天數等作為實驗的驗證參數。實驗內容包括：不同需求特征數對拼團成功率及時間的影響；拼團信息數量對拼團成功率及時間的影響；拼團結果經緯度的區(qū)間分布情況分析。其實驗環(huán)境為：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 拼團結果經緯度的區(qū)間分布情況分析

通過對拼團的結果數據進行分析，可以得出數據樣本具有分布的不均勻性、類間分布的差異性2個特點，以及拼團信息主要的分布區(qū)間、拼團成功的主要分布區(qū)間、拼團失敗的主要分布區(qū)間等信息，具體情況如圖6、圖7所示。

從圖6、圖7可以看出，拼團失敗較多的經緯度范圍，并對該范圍內的拼團數據進行處理和優(yōu)化，進一步提高拼團的準確度和成功率。

(c) 拼團未成功的反類出發(fā)地經緯度的樣本分布

(c) 拼團未成功的反類目的地經緯度的樣本分布

5 總結

隨著國內外旅游業(yè)的發(fā)展，拼團游開始流行起來，但由于游客個人需求不一樣，從而導致他們很難找到合適的驢友一起外出旅游。雖然現在很多的旅游服務平臺已有拼團這一模塊，但其中大部分拼團模塊都是基于景點的拼團，即“景點”選擇“游客”的模式，該模式以景點為目的地讓游客拼團，這使得游客只能選擇平臺中已有的景點作為旅游地點，有著極大的限制。而本文所提出的TGA算法是一種“游客”選擇“景點”模式，它可以根據游客的個性化需求特征來匹配合適的拼團組合及對象，這在一定程度上提高了游客的自由度和滿意度。然而，該算法還存在一些不足之處，譬如需求特征目前考慮得較少，沒完全體現出游客的個性化需求，后續(xù)將根據游客的個人偏好特征來進行優(yōu)化，使其能更智能地為游客匹配到滿意度更高的拼團組合及對象。