范海林，梁 明，李 佳，段 平，王姍姍，王 彤

(1. 廣東繪宇智能勘測科技有限公司，廣東 廣州 510665； 2. 安徽大學資源與環(huán)境工程學院，安徽 合肥 230601； 3. 云南師范大學旅游與地理科學學院，云南 昆明 650500)

旅游活動是重要的人類活動行為之一。隨著移動互聯(lián)網的發(fā)展，對用戶的旅游軌跡獲取已經變得越發(fā)便捷。如何深度挖掘旅游軌跡及其他旅游行為數(shù)據(jù)中的價值，已經成為智慧旅游的重要議題[1]。對旅游軌跡的停留點進行語義標注，既可以作為智慧旅游個性化路線推薦的依據(jù)，也是開展軌跡數(shù)據(jù)挖掘的重要基礎[2]。

軌跡數(shù)據(jù)作為典型的時空大數(shù)據(jù)，受到了廣泛的關注。近年來，對軌跡數(shù)據(jù)的壓縮、聚類等針對軌跡數(shù)據(jù)挖掘的研究[3-5]，以及對軌跡數(shù)據(jù)的停留點和Move/Stop模式的識別研究越來越多[6-7]。軌跡語義的挖掘，特別是對軌跡停留點進行語義標注，不僅有利于刻畫軌跡的特征，也是對軌跡行為模式進行深度挖掘的基礎[8]。但是目前對軌跡數(shù)據(jù)研究主要聚焦于軌跡數(shù)據(jù)的幾何和空間特征，而較少顧及語義特征。因此，本文選擇旅游軌跡停留點的語義標注為本文的主要研究內容。

如何高效自動地識別和標注軌跡的停留點，主要涉及3個關鍵問題：①如何從用戶軌跡中發(fā)現(xiàn)和提取停留點？②如何對停留點周邊的POI進行自動分類？③如何利用停留點的地理語境(周邊的POI類型及其分布特征)對停留點進行語義標注？

1 軌跡停留點及其語義標注概述

軌跡停留點，又被稱為軌跡的重要地點、重要區(qū)域，通常并不是指某一個單純的GPS位置，而是指用戶花費較長時間駐留或較頻繁次數(shù)到訪的區(qū)域[6]。軌跡中停留點的提取是進行頻繁位置的發(fā)現(xiàn)、POI的挖掘、語義標注等的基礎，在軌跡分析中起著重要作用[9]。

停留點的識別通常以時間和距離閾值為條件，又或兼顧軌跡的速度和方向[10]。在具體算法上，停留點識別以基于密度的聚類方法效果較為突出。相關學者通過以時間代替DBSCAN中點數(shù)量閾值，以消除軌跡點缺失的影響來開展軌跡停留點識別[11]；或通過增加軌跡距離和軌跡鄰域兩個概念判斷核心點的方式進行基于密度的聚類方式發(fā)掘軌跡停留點[12]。諸多停留點識別的方法目前已經取得了較好的效果。

軌跡停留點的語義標注，又被稱為地點命名[8]，可以從兩種不同的思路出發(fā)：一是充分利用用戶活動行為進行標注[13]；二是利用停留點的地理語境進行標注[14]。前者便于發(fā)現(xiàn)用戶在停留點的獨特行為模式，而后者通常更注重用戶的共有行為模式或狀態(tài)。反映停留點地理語境最典型的方法是其周圍POI的類型和分布。

2 基于改進TF-IDF的POI自動分類方法

2.1 POI的特征擴展

POI名稱通常是一種典型的短文本。對于短文本分類問題，由于其具有特征少、領域相關性強等特點而無法直接復用業(yè)已成熟的文本分類方法，是文本分類的難點和研究熱點。針對其特征稀疏的特點，最常見的思路是進行特征擴展，通?？梢圆捎镁S基百科擴展、WordNet擴展等方法[15-16]；針對領域相關性強的特點，常采用面向主題分類、LDA等方法[15-16]。雖然以上相關研究在微博消息分類、短信分類等領域取得了一定的進展，但是相較于微博等百余字左右的文本對象而言，POI文本更加簡短，這就要求針對POI短文本的特點，發(fā)展更具針對性的算法。

短文本分類問題的根源主要在于其特征的稀疏性。一個POI數(shù)據(jù)的樣本特征極為稀疏，語義表達能力弱。同一類的POI數(shù)據(jù)近義詞和同義詞現(xiàn)象頻繁出現(xiàn)，常使用不同的語言載體來表示相同的意思，沒有直接歸為同一類的特征依據(jù)，使自動分類難度加大。依據(jù)POI數(shù)據(jù)特征之一即關鍵詞后置，將每一條預處理后的POI最后一個詞作為關鍵詞，通過《同義詞詞林》進行特征擴展。主要步驟如下：

(1) 提取數(shù)據(jù)預處理后的POI數(shù)據(jù)的關鍵詞，將每個POI提取出的關鍵詞按順序存儲，得到對應的關鍵詞集K={k1,k2,…,km}。

(2) 將《同義詞詞林》中所有詞條的第一個詞設置為索引詞，并以詞條為單位，以同一行的其余詞與該行索引詞的關聯(lián)程度為依據(jù)，按照關聯(lián)程度依次降低的順序進行排列。

(3) 將一個POI的關鍵詞集K中的第i個關鍵詞與《同義詞詞林》的索引詞進行一一匹配。

(4) 如果匹配成功，將該索引詞所在詞條中的所有詞按照權重依次遞減的規(guī)則加入到第i個關鍵詞對應的POI中。

(5) 如果匹配不成功，不對該POI進行任何操作。

(6) 直至關鍵詞集K全部搜索完畢。

(7) 對下一個未進行特征擴展的POI的關鍵詞集K進行匹配處理，重復步驟(3)—步驟(6)。

(8) 直至所有POI的關鍵詞集均處理完畢。

2.2 改進TF-IDF的特征權重

除了特征高度稀缺的問題，現(xiàn)有成熟的文本分類算法不能較好適用于POI分類原因還在于：①POI文本中同一類別的關鍵詞往往較為集中。一個POI文本常由幾個詞組成，實際場景中為了用最精簡的文本體現(xiàn)最直觀的描述，體現(xiàn)其特征的關鍵詞通常直接放入POI文本，如“百好樂比薩”“老山西刀削面”“四方烤肉”等餐飲類POI，其中關鍵詞“比薩”“刀削面”“烤肉”都是餐飲類標志特征詞，因此POI數(shù)據(jù)中同一類別的POI關鍵詞常具有高度的集中性和相似性。②不同類別間混淆詞分散。POI文本中除了關鍵詞，常有混淆詞出現(xiàn)，這類混淆詞對分類貢獻不高，大多由人名、地名等組成，如“張記面館”“張記商鋪”和“張記藥房”，分別是餐飲類、購物類和醫(yī)療類，雖類別不同但都包含同樣的混淆詞“張記”，是自動分類主要障礙之一。③關鍵詞后置。POI數(shù)據(jù)中體現(xiàn)其特征的關鍵詞以后置情況為主，如“八大鍋餐廳”“平方超市”“雙語幼兒園”等是現(xiàn)代漢語常用語法結構。針對POI短文本的以上不足，本文提出了基于改進的TF-IDF特征權重算法進行POI自動分類。

借鑒TF-IDF對POI分類，主要從以下幾個方面考慮：①某個詞集中出現(xiàn)在一個類別中次數(shù)越多，越能提高該類別與其余類別的區(qū)分度；②統(tǒng)計詞頻TF能提高某一類別中關鍵詞的權重，強化模型對類別內部特征的表達；③統(tǒng)計某個詞在各個類別中的詞頻，詞頻間方差越小，該詞對某一類別與其余類別的區(qū)分度貢獻程度越低。計算逆文本頻率指數(shù)IDF降低不同類別間混淆詞的權重，加強不同類別間特征項的區(qū)分度。鑒于POI數(shù)據(jù)體現(xiàn)其特征的關鍵詞多以后置情況為主，以一個POI文本數(shù)據(jù)為單位，按照內部關鍵詞的排放順序賦予不同位置權重W，位置越靠后其權重越高?；诟倪M的TF-IDF特征權重分類算法如下：

(1) 假定有m個類C1，C2,…,Cm，對于一個未知分類的POI數(shù)據(jù)樣本X，X由關鍵詞{x1,x2,…,xn}組成。計算關鍵詞xi在Cj中的詞頻TFi,j、逆文本頻率指數(shù)IDFi、位置權重Wi

(1)

(2)

式中，|{j:xi∈Cj}|為包含關鍵詞xi的類別數(shù)目(如果所有類別中均不包含關鍵詞xi，則分母為1)。

(3)

(2) 計算xi對未知分類的數(shù)據(jù)樣本X劃分為類別Cj的共享程度Hi,j

Hi,j=TFi,j×Wij∈[1,m]

(4)

(3) 計算x1，x2，…,xn的共享程度Hi,j之和

(5)

(4) 分類器將POI數(shù)據(jù)樣本X分類到Sj最大時所對應的類別Cj。

3 基于Native Bayes的停留點語義標注

停留點是軌跡的重要語義單元，也是用戶行為模式的重要外部特征。旅游軌跡中的停留點是用戶行為的重要特征。停留點的語義與其所處位置的地理語境密不可分。因此，本文以停留點所處位置周邊的POI的類型和分布特征作為度量停留點地理語境的依據(jù)，開展停留點的語義標注研究。

在旅游軌跡中，停留點通常意味著用戶下車休憩、駐足觀賞、瀏覽拍照、用餐、購物等旅游行為模式。這些行為模式僅僅從軌跡數(shù)據(jù)本身出發(fā)是很難挖掘出來的，通常需要結合軌跡停留點的環(huán)境背景或停留行為的地理語境，可以采用軌跡停留點周圍的眾多POI的類型、密度和分布特征等作為軌跡停留點的地理語境特征。如商店、賣場密集的區(qū)域，可能是游客購物的場所；而美食密集的地方，則可能是用戶休憩進餐的位置。停留點周邊的少量POI可能具有一定的偶然性或隨機性，選擇停留點周邊較多的POI并用它們統(tǒng)計特征作為停留點語義標注的特征，是剔除這種偶然性影響的有效手段。

本文首先選擇停留點周邊最近鄰的K個POI；其次，利用改進的TF-IDF方法對POI進行自動分類；再次，分別統(tǒng)計停留點最近鄰的K個POI中各類POI的個數(shù)，以及到達停留點距離；最后以這些不同類的POI的個數(shù)代表密度、距離表征遠近，作為停留點的不同維度特征，構造當前停留點的特征向量。剩下的工作即使用Native Bayes分類器對軌跡停留點進行語義分類。Native Bayes具有不確定性的知識表達形式、豐富的概率表達能力、綜合先驗知識的增量學習特性，在自然語言處理和語義分析等領域有著廣泛的應用。Native Bayes分類器核心思想可以描述為：①假設目標分類的類別集合C={y1,y2,…,yn}；②x={a1,a2,…,am}為待分類項，而每個a為x的一個特征屬性；③計算P(y1|x)，

P(y2|x)，…，P(yn|x)；④ 如果P(yk|x)=max{P(y1|x),

P(y2|x),…,P(yn|x)}，則x∈yk。

其中，最為關鍵的是如何計算上述步驟③中的各個條件概率，可以按以下步驟實現(xiàn)：

(1) 找到一個已知分類的待分類項集合，即訓練樣本集。

(2) 統(tǒng)計得到在各類別下各個特征屬性的條件概率估計，即計算P(ai|yi)。

(3) 如果各個特征屬性條件獨立，則根據(jù)貝葉斯定理推導如下

(6)

(4) 計算所有假設的概率，并選擇概率最大的假設作為分類的結果。

4 案例分析

對于軌跡停留點的識別方法較多，其中ITBCA算法能夠自動確定重要位置的個數(shù),并且對偏移點等異常點并不敏感。ITBCA算法基于時間和距離閾值，能夠過濾掉那些用戶只是經過但沒有長時間逗留的地點，可以將靜態(tài)停留點和動態(tài)停留點識別出來,因此，本文選用ITBCA算法識別軌跡的停留點。本文討論重點為停留點的語義標注，具體算法請參考文獻[19]。

本文共選取了中國POI數(shù)據(jù)網提供的25 976個已分類POI作為總樣本，類別包括餐飲、購物、交通設施、教育、金融、醫(yī)療和政府機構。將POI數(shù)據(jù)集分成兩個子集：一個用于訓練改進TF-IDF分類器，即訓練集；另一個用于對分類器進行評估測試，即測試集。從總樣本中隨機抽取20 784個POI作為訓練集，其中各類樣本容量為：餐飲6376個、購物4941個、交通設施2723個、教育1881個、金融1992個、醫(yī)療1411個、政府機構1460個。其余5192個POI作為測試集。針對POI的短文本特征，本文選用了由哈爾濱工業(yè)大學信息檢索實驗室擴展和維護的《同義詞詞林》對文本特征進行擴展。該《同義詞詞林》每條詞條中的詞語語義相同或具有很強的相關性，所有收錄到的詞條按照樹狀的層次結構組織到一起。結果(見表1)表明，基于改進TF-IDF的方法實現(xiàn)的POI自動分類，其分類精度達到83%。

表1 基于改進TF-IDF特征權重分類算法自動分類POI的混淆矩陣

其次，在POI自動分類的基礎上，開展旅游軌跡停留點語義標注。本文將停留點分為以下5種語義類型：購物、用餐、拍照游覽、中轉交通和休憩入住。用戶的旅游軌跡數(shù)據(jù)部分來源于OpenStreetMap中云南地區(qū)用戶共享的GPX軌跡；另外一部分來自筆者所在團隊師生在云南自行采集的軌跡樣本。接著篩選了783個軌跡停留點樣本，并人工對這些停留點樣本作語義標注。然后以這783個樣本為基礎，以其中的一部分樣本(90%)作訓練，以另外一部分樣本作校驗，開展10折交叉校驗。結果顯示，采用Native Bayes停留點語義分類精度為74%。

圖1中，?表示“休憩入住”，□表示“觀光游覽”。從圖1可以清晰地看出用戶在大理市整個旅游過程的宏觀語義路徑。該用戶先在大理市區(qū)“中轉交通”(很可能用戶從昆明等外地趕到大理)；稍作停留后，便前往大理古城“休憩入住”；然后到喜洲古鎮(zhèn)“拍照游覽”。由此可見，本文方法對于時空數(shù)據(jù)的挖掘，提升用戶對海量軌跡數(shù)據(jù)的語義認知具有積極意義。

5 結論與展望

本文針對POI自然語言描述中的特征高度稀缺的特點，提出了基于《同義詞詞林》擴展的方法；針對反映地理語境特征的POI的分類問題，提出了改進TF-IDF的POI自動分類方法；針對旅游軌跡中停留點語義標注的問題，提出了顧及停留點地理語境的Native Bayes語義標注方法。研究結果表明，采用語義擴展后的TF-IDF方法能夠較好地實現(xiàn)POI的自動分類；同時，通過充分顧及停留點周邊最近鄰的K個POI的類型、距離等特征的Native Bayes分類器，能夠實現(xiàn)對停留點的自動語義標注，并獲得較高的精度。本文研究對軌跡數(shù)據(jù)時空特征挖掘，特別是旅游軌跡挖掘具有一定的參考價值；同時也為POI的自動分類提供了一個獨特的視角。

本文對停留點的語義標注，主要是考察停留點的地理語境，并沒有充分發(fā)掘用戶停留行為自身的特征。如同樣的一個地理位置，不同的用戶停留時間可能反映的是用戶停留行為的差異，長時間的停留可能是休憩和購物，而短時間的停留可能是等待或中轉。之所以沒有將用戶的停留時間等行為特征考慮進去，主要是受制于樣本的限制。

本文通過時空聚類的方式獲取了用戶的停留點，但是對于樣本中停留點語義類別的標注是基于筆者的主觀判斷，并沒有用戶行為的實際記錄。因此，樣本中軌跡停留點的語義類別并不能完全表征用戶的實際行為，該問題需要在以后的研究中加以改進。