基于稀疏軌跡聚類的自駕車旅游路線挖掘

楊奉毅，馬玉鵬，包恒彬，韓云飛，馬 博

（1. 中國科學院新疆理化技術研究所，烏魯木齊830011； 2. 中國科學院大學，北京100049；3. 新疆民族語音語言信息處理實驗室，烏魯木齊830011）

（?通信作者電子郵箱ypma@ms.xjb.ac.cn）

0 引言

隨著國民經濟水平提升，私家車保有量迅速增加，自駕車旅游逐漸成為人們旅游出行的熱門選擇。通過對游客的自駕軌跡進行分析，可以發現流行的自駕車旅游路線，為旅行者的旅行路線的規劃提供支持。然而，自駕車游客的活動具有較高的自主性，導致行程軌跡數據難以收集，數據的代表性和覆蓋性不足。

本文采用覆蓋新疆的加油數據集，挖掘流行的新疆自駕車旅游路線。該數據集記錄了用戶在新疆的所有加油行為，其中同樣包含了所有自駕車游客的加油記錄。按照時間先后將加油站點組成序列就可以得到一條加油軌跡，加油軌跡是游客旅游路線的某種采樣，能夠真實反映游客的時空移動軌跡，可以作為新疆自駕車旅游路線挖掘的重要數據來源。然而，利用加油數據挖掘流行的自駕車旅游路線主要面臨兩個挑戰。首先，原始數據中人員數量眾多，加油行為復雜多樣，難以準確識別出自駕車游客群體；其次，相比全球定位系統（Global Positioning System，GPS）軌跡數據，加油記錄產生的頻率非常低，數據十分稀疏，導致同一條加油軌跡中的兩個連續軌跡點之間的路徑不確定，從中還原出具體的路線十分困難。如圖1 所示，圖中的線條為某游客自駕游的確切軌跡，圓點表示該游客實際的加油地點。可以看出，依靠單一游客稀疏的加油軌跡點數據，并不足以推斷出游客實際的旅游路線。

本文的主要工作如下:針對游客群體識別的問題，通過分析已知的游客加油行為，總結出游客加油的基本特征，進而從大量原始加油記錄中識別出游客群體。針對軌跡點稀疏問題，受word2vec［1］的啟發，提出一種基于語義表示的稀疏軌跡聚類算法:將每個加油站看作一個單詞，每條加油軌跡看作一個句子，通過word2vec學習加油站點的分布式表示，然后使用每條軌跡中站點向量的平均值表示該加油軌跡，最后通過k均值算法完成軌跡聚類，根據聚類結果挖掘流行的自駕車旅游路線。圖2為本文方法的總體流程。

圖1 某游客旅游路線與加油軌跡對比Fig. 1 Comparison between tour route and refueling trajectory of a tourist

圖2 本文算法的總體流程Fig. 2 Overall flow of the proposed algorithm

1 相關工作

1.1 旅游路線挖掘

近些年來出現了大量旅游路線規劃和推薦的相關研究。目前研究采用的數據主要是用戶分享的GPS 軌跡數據、帶地理標簽的照片數據和簽到數據［2］。Zheng 等［3-5］基于GPS 軌跡數據做了一系列的旅游路線挖掘和推薦的工作，取得了優秀的成果。Cui等［6］基于用戶的GPS 軌跡信息，考慮用戶的個性化信息，基于協同過濾技術提出了兩種旅游路線推薦算法，提高了推薦結果的個性化程度。然而，GPS 軌跡雖然可以反映游客的具體旅行路線，但是相對難以獲得。隨著基于位置服務的發展，利用社交媒體數據進行旅游路線挖掘和推薦成為新的研究熱點。文獻［7］提出了一種基于主題模型的協同過濾方法，利用旅游照片進行旅游推薦。文獻［8］基于游客簽到數據，提出一種基于集體知識的路線推理框架，從不確定軌跡中挖掘流行的旅游路線。目前，采用這些用戶分享數據進行自駕車旅游的研究較少，主要原因在于這些數據難以區分普通游客與自駕游客，其中能夠完全確定為自駕游客數據的數量很少。文獻［9］基于自駕游客分享的924 條GPS 軌跡，結合路網信息與旅游景點信息，以季節強度指數、多維緩沖區、核密度等方法分析自駕車游客的時空行為特征。

上述數據大多來自于用戶的分享，這些用戶僅僅占全部游客的一小部分，因此分析結果帶有較大的偏差。與上述研究采用的數據不同，本文采用加油軌跡數據進行自駕車旅游路線的挖掘，數據集本身包含全部自駕車游客在新疆的加油行為，對于分析新疆自駕游的整體情況具有重要作用。

1.2 軌跡聚類

為了發現不同移動對象軌跡中的代表路徑或共同趨勢，通常將相似的軌跡進行聚類［10］。傳統的軌跡聚類方法一般先使用一定的度量方法比較軌跡之間的相似性，之后采用一些經典的聚類算法進行聚類。Lee 等［11］提出了一個軌跡聚類框架，首先將每個軌跡劃分為多個子軌跡，然后采用基于密度的聚類方法對這些子軌跡進行聚類。Tang 等［12］提出了出行行為聚類算法，使用結合采樣的密度聚類算法解決軌跡數據中的噪聲問題。Besse等［13］定義了一種新的距離度量方法，實現了基于距離的軌跡聚類。

時空軌跡聚類的核心在于衡量軌跡之間的相似性，常用的軌跡相似性度量方法包括動態時間扭曲（Dynamic Time Warping，DTW）［14］、最 長 公 共 子 序 列（Longest Common Subsequence，LCSS）［15］和編輯距離方法EDR（Edit Distance on Real sequence）［16］。

上述度量方法主要考慮了軌跡點的空間位置信息，適合用于采樣頻率高的GPS數據。然而，游客的加油頻率非常低，通常在2～3 d，加油軌跡十分稀疏，兩個連續訪問的加油站點之間甚至相隔數百公里。因此，上述方法并不適用于極其稀疏的加油軌跡數據。

1.3 分布式表示

在自然語言處理領域，傳統的將單詞表示為高維、稀疏向量的方法基本上被基于神經網絡的語言模型所取代。神經網絡語言模型通過考慮詞序和單詞的共現來訓練，其概念基于分布式假設，即在句子中經常出現在一起的單詞具有更高的統計相關性。Mikolov 等［1］提出的word2vec 是其中的突出代表，它可以簡單高效地學習到單詞的低維向量表示，在包括機器翻譯、情感分析等傳統的自然語言處理任務上取得了優秀的表現。

最近，分布式表示的概念逐漸擴展到網頁搜索、電子商務、推薦系統等其他領域。研究人員意識到可以將用戶的行為序列視作句子，進而學習商品或用戶的嵌入表示，如用戶的點擊、查詢或購買序列。分布式表示被用于各種類型的網絡推薦中，包括淘寶推薦［17］、求職推薦［18］、應用推薦［19］、房源推薦［20］等。同樣，類似的方法也被提出用于社交網絡分析，利用網絡中節點的隨機游走序列學習網絡節點的嵌入表示［21］。本文同樣利用這一思想，將加油軌跡中的加油站看作單詞，整條軌跡看成句子，運用word2vec學習加油站的語義向量表示，用于加油軌跡聚類，還原游客的旅行路線。

2 自駕車游客群體識別

原 始 加 油 數 據 集 中 的 記 錄r ={u，v，s，t，area}，其 中:u、v、s、t 分別代表司機、車輛、加油站和加油時間戳；area 代表加油站所屬的行政區劃。從中選取數據構建人員加油軌跡數據集，選取時間范圍是2016 年1 月1 日至2018 年12 月31 日。將加油記錄按照人員進行重組，每個用戶的所有加油記錄可以組成一條加油軌跡tra ={s1，s2，…，sn}，它是一個用戶按時間順序訪問過的加油站點集合。

經過調查可發現自駕車游客通常具有3 個特征:1）只來過新疆一次且停留時間不超過30 d；2）具有連續加油行為，相鄰兩次加油時間間隔小于5 d；3）加油地點不固定且分散在各個地州市，通常不少于3 個地州市。同時，為了避免軌跡過于稀疏，本文只對加油次數大于8 次的軌跡進行分析。根據以上特征，定義了四條規則，用以自駕車游客群體的識別。對于加油軌跡數據集中的任意一條軌跡tra ={s1，s2，…，sn}，如果滿足:

則認為軌跡tra為自駕加油軌跡，對應人員為自駕游客。

根據以上規則，從加油軌跡數據集中提取出20 646 條加油軌跡。為了驗證這些軌跡確為自駕游人員所產生，本文對軌跡對應人員的基本特征做了統計分析。首先，這些人員的男女比例高達21∶1，遠遠高于原始數據集中3.5∶1 的男女比例，這符合長途自駕旅游中司機絕大多數為男性的實際情況。其次，游客的主要來源省份與整體情況也有著很大差異，如圖3所示。

圖3 外來人員與自駕游客的省份分布Fig. 3 Provincial distribution of migrants and self-driving tourists

圖3（a）為原始數據集中外來人員的主要省份分布，這在很大程度上體現了外地人在新疆生活及工作的情況，可以看到，四川、甘肅和陜西等距離較近的省份，與新疆的人員交流比較密切；同時，河南、山東等省份由于人口總量大，在新疆也有大量的人員活動。如圖3（b）所示，游客的來源省份發生了很大的變化，較發達省份的人員占比明顯增加，來自北京的人員數量最多，而來自甘肅的游客數量很少，這體現了居民收入及消費水平對自駕車旅游的重要影響。最后，對自駕游人員的月份分布做了統計，如圖4 所示。結果顯示，游客的數量受季節變化十分明顯，主要集中在7、8、9 三個月，與此同時，幾乎沒有游客選擇在冬季進行自駕游，這與新疆的氣候條件有著密切的關系，符合新疆旅游市場的基本情況。

圖4 自駕車游客人數隨時間變化的統計Fig. 4 Histogram of self-driving tourist number variation with time

由此可見，本文定義出的規則有效識別出了自駕車游客群體，能夠支撐進一步的研究工作。

3 基于語義表示的加油軌跡聚類

3.1 問題定義及分析

定義1 自駕路線。游客實際的自駕路線是一個連續的空間曲線，是游客駕車自駕的確切移動路徑。

定義2 加油軌跡tra。每條加油軌跡都是按照時間先后排序的游客加油的站點序列，是自駕路線的一種采樣，形式化表示為tra ={s1，s2，…，sn}。加油軌跡tra 和加油站s 對應的向量表示分別為traj和st。

定義3 加油軌跡聚類。給定游客加油軌跡集T，我們的目標是將軌跡集T劃分為k個不相交的簇C ={C1，C2，…，Ck}，同一個軌跡簇的加油軌跡對應同一條自駕路線，T ={tra1，tra2，…，traf}。

同一條自駕路線上會有數量眾多的加油站，游客的加油行為具有極大的自主性，每條加油軌跡都可以看作是對路線上的所有加油站的隨機采樣。因此，雖然游客的旅游路線相同，最終的加油軌跡依然有著很大的差別。這些軌跡都反映了旅游路線的部分信息，將這些軌跡進行聚類可以得到完整的旅游路線信息。然而，加油軌跡的高度稀疏性導致基于軌跡點空間相似性的傳統軌跡聚類算法無法得到理想的效果，因此本文將自然語言處理中語義相似性的概念引入加油軌跡聚類，用以更好地衡量加油站點之間的相似性。

在自然語言處理領域，語義相似的單詞擁有相似的上下文。同樣，在加油軌跡中，加油站的上下文通常是同一路線上的加油站，這些站點具有更高的語義相似性。使用word2vec學習站點的語義信息，得到站點的向量表示，之后取所有站點向量的平均值作為加油軌跡的向量，最后使用經典的k 均值算法實現軌跡聚類。本文算法的整體框架描述如下。

算法1 基于語義表示的加油軌跡聚類。

輸入 加油軌跡數據集T，聚類簇數k，skip-gram 模型窗口大小m，嵌入向量維度d。

3.2 站點向量表示

本節將介紹使用word2vec進行站點表示的方法。給定加油軌跡數據集T，目標是學習到每個站點的d維向量表示。實際上，word2vec 包括兩個模型，分別為連續詞袋模型（Continuous Bag-of-Words model，CBOW）和skip-gram 模型。其中，CBOW 的目標是根據上下文預測中心詞的概率，skipgram 模型則相反。一般而言，skip-gram 模型的效果會更好，因此本文選擇使用skip-gram模型學習站點的向量表示。

skip-gram 雖然是一種無監督的方法，但它仍然在內部定義了一個輔助的預測任務。如圖5 所示，首先選定中心詞si，在它的前后各m 個詞距內選定上下文，組成訓練的單詞對（si，si-m），…，（si，si-1），（si，si+1），…，（si，si+m）。在訓練期間，使用包含當前中心詞及其上下文的滑動窗口在語料庫中移動，得到所有的訓練樣本，目的是借助中心詞預測上下文出現的概率。構造這個監督學習的目標并不是想要解決這個監督學習問題本身，而是想要借助這一問題來學習一個好的詞嵌入模型。

圖5 基于skip-gram模型的站點嵌入表示Fig. 5 skip-gram model based station embedding representation

skip-gram 模型的結構如圖6 所示，是一個簡單的神經網絡模型，僅擁有輸入層、隱藏層和輸出層三層結構。

圖6 skip-gram模型結構Fig. 6 skip-gram model structure

輸入層和輸出層都由一個N 維的one-hot 編碼向量表示，N代表加油站的總數，隱藏層由維度為d的向量表示。權重矩陣WN×d和W′d×N，分別位于輸入層與隱藏層之間和隱藏層與輸出層之間。隱藏層沒有使用任何激活函數，輸出層使用softmax作為激活函數。模型的具體的訓練過程如下。

3）通過反向傳播算法及隨機梯度下降來更新權重矩陣W 和W′，最小化損失函數。整個訓練樣本集上的損失函數為

4）取權重矩陣W的每一行作為站點的向量表示。

3.3 軌跡聚類

當獲得了站點的向量表示之后，就可以利用站點向量得到軌跡的向量表示。在自然語言處理中，句子向量表示的一種簡單有效的方法是將句子中所有詞向量進行平均［22］。類似地，對于軌跡tra，它的向量表示traj 為其包含的所有加油站s1，s2，…，sn向量表示的平均值，公式表示為:

至此可以得到每條軌跡的向量表示，然后使用經典的聚類算法進行軌跡聚類。本文采用k均值（k-means）算法進行軌跡聚類。給定樣本集D 和聚類簇數k，k 均值算法將樣本集劃分為k個不同的聚類簇C1，C2，…，Ck，最小化平方誤差:

1）從樣本集D 中隨機選擇k個樣本作為初始聚類簇的均值向量；

2）計算每個樣本與各個簇均值向量的距離，選擇距離最近的簇，作為樣本的簇標記；

3）依據新劃分的簇，重新計算簇均值向量；

4）若簇均值向量未發生變化，算法終止，返回聚類簇；否則，重復步驟2）～3）。

4 實驗與結果分析

4.1 實驗配置

為了挖掘新疆自駕車旅游路線，采用覆蓋新疆全區的加油數據集作為原始數據集，該數據集記錄了2016 年1 月1 日至2018 年12 月31 日3 年時間內，所有人員在新疆的加油記錄。首先對原始加油數據集進行預處理（詳見第2 章），挖掘出20 646 名自駕車游客的加油軌跡作為實驗數據集，涉及到全新疆1 856個加油站。實驗機器系統為Ubuntu 18.04，CPU型號為Intel Core i7-3770 CPU@3.4 GHz，內存12 GB，Python版本3.6。

本文的主要參數包括:窗口大小m，站點向量維度d 和聚類簇數k。其中，m 和d 設置為默認值，分別為5 和100。新疆的自駕游路線主要分為北疆線和南北疆大環線，因此將k 值設置為2。

4.2 站點分布式表示結果分析

為了驗證算法是否學習到了有效的站點嵌入表示，本文文使用余弦相似度衡量站點向量之間的相似性，觀察相似的站點之間具有怎樣的關聯關系。本文選擇阿勒泰地區的喀納斯加油站作為目標，該站點位于著名景區喀納斯附近，適合分析游客的加油行為。表1展示了與喀納斯加油站最相似的10個站點。其中的1號、2號、4號、6號和8號站點同樣位于喀納斯景區附近，表明站點的向量表示有效學習到了站點的空間位置特征。除此之外，還發現10 個站點均位于著名旅游景點附近，3 號、5 號和10 號加油站位于白沙湖景區附近，7 號和9號加油站位于那拉提景區附近。這種結果表明站點向量有效地包含了站點的語義信息，將游客旅行中訪問過的景點信息包含在內，有利于進一步的路線挖掘。

表1 與喀納斯加油站最相似的10個站點Tab. 1 Ten most similar stations to Kanas gas station

4.3 聚類可視化結果分析

由于數據本身完全無標注，因此選擇通過聚類結果的可視化，人工驗證結果的有效性。如圖7 所示，圖中的圓點代表每個聚類簇中加油次數前100 的站點，三角形代表新疆的12個5A級景區，線條代表流行的旅游路線。

圖7 聚類結果可視化Fig. 7 Visualization of clustering results

可以看出，北疆的旅游資源更為豐富和集中，幾乎所有游客都會前往北疆進行游覽，因此兩條路線都涉及到了北疆景點的游覽，二者在北疆地區的行程幾乎一致，包含了北疆的10 個5A 級景區。相比北疆，南疆的旅游景點集中在喀什地區，與其他景點相隔較遠，因此一部分游客在游覽完北疆后選擇直接返程（路線A），其余的游客則繼續前往喀什地區游覽，最終經由巴州的若羌縣前往青海省（路線B）。圖8 為馬蜂窩旅游網推薦的新疆自駕游路線，可以看出該路線與圖7 中的路線A 有著很高的重合度，不同之處在于馬蜂窩推薦路線以烏魯木齊市為起止點，這是因為旅游網站通常將烏魯木齊作為游客的集結地點。

圖8 馬蜂窩旅游網推薦的一條自駕游路線Fig. 8 A self-driving tour route recommended by Mafengwo website

5 結語

本文利用用戶在新疆的加油數據，成功挖掘出兩條流行的新疆自駕車旅游路線。首先，根據自駕車游客的行為特征從全疆加油數據集中挖掘出自駕車游客人群，并分析了游客的基本特征，結果說明了游客群體數據的可靠性。然后，鑒于現有軌跡聚類算法不能解決加油軌跡過于稀疏的問題，提出一種基于語義表示的加油軌跡聚類算法，最終的可視化結果表明該方法很好地還原了游客的旅行路線。但是本文方法僅僅考慮了軌跡點的語義信息，沒有將軌跡點本身的空間信息考慮在內，后續的研究工作將考慮把空間與語義信息進行結合，學習更好的站點及軌跡分布式向量表示。另外，本文挖掘出的流行路線為長途自駕游路線，后續的工作將結合節日、季節等信息進一步挖掘短途的自駕游路線。