基于深度表示模型的旅游路線推薦算法研究

梁棟屹+陶宏曜+劉興旺

摘要：針對現有旅游路線推薦算法在實際應用中景點標簽缺失、依賴用戶評分等缺陷，提出一種基于深度表示模型的旅游路線推薦算法。根據時空軌跡隱含的位置順序和時間中的用戶移動模式，建立深度表示模型對每個用戶的時空間序列訓練特征向量，并用Kmeans算法對訓練結果進行聚類。為驗證實驗結果，將用戶的移動模式應用到旅游路線推薦上，選擇使用Gowalla上的簽到數據集進行檢測。實驗結果表明，包含諸如“購物”，“夜生活”等標簽的移動軌跡具備推薦價值。

關鍵詞：社交網絡；深度表示模型；Kmeans聚類；用戶移動模式；訓練特征向量

DOIDOI：10.11907/rjdk.171932

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）012-0158-04

Abstract：In currently， there are some weakness like lacking of feature spot label and the large distance between different places for the travel route recommendation algorithm. In this paper， we analyze the sequence of locations and time which hide the user moving model and create a depth representation model to train the feature vector about the space-time list. At last， we select the Kmeans algorithm to cluster the value of feature. To test the result of experiment and apply it in the recommendation of travel route， I select to use the check-in data list Gowalla as the resource。According to the result， some moving route including shopping or night life label have the value of recommendation.

Key Words：social network； depth representation model； Kmeans clustering； user moving model； training feature vector

0 引言

隨著移動設備和基于位置的服務廣泛應用，用戶簽到數據的獲取更加方便且成本大大降低，人們在通過微信朋友圈、QQ空間等社交網絡平臺分享圖片、感想的同時，也產生了時空簽到數據。這些數據至少具備3種屬性：用戶ID、簽到時間與經緯度，這促使了基于地理位置的移動社交網絡（LBSN）迅猛發展，這些個體行為軌跡數據為研究用戶移動模式以及探究其內在規律提供了機會。例如收集一個用戶在一定時間內的時空數據連線就可得到一條時空軌跡，而時空軌跡在城市智能化發展中扮演著越來越重要的角色，2012年，Science就發現了這個現象[1]。

在LBSN網站中，可由用戶的一系列簽到點繪制出軌跡，這些軌跡同時具有地理信息和社交信息屬性，是許多分析用戶移動軌跡研究的基礎。Tang[3]等提出根據海量用戶的 GPS歷史軌跡來挖掘旅途中目標一致的同伴。Backstrom[4]等通過分析 Facebook上用戶間的社會關系來預測好友的地理位置信息。Wang[6]等提出基于朋友關系向用戶推薦其可能感興趣的地點算法FBCA，該算法將朋友關系應用于軌跡聚類，很好地利用了社交網絡中的社交屬性。Zheng[7]提出一個基于社交網絡位置推薦系統，但實際生活中，人們的活動通常會受到與用戶關系密切或其他人言行的影響，因此在研究社交軌跡聚類時必須考慮其他用戶對軌跡的評價，這里引入用戶愛好相似度評估矩陣。

隨著旅游業的蓬勃發展，出現了許多旅游推薦算法，而大多數算法都是依靠用戶對于景點與旅游路線的評分信息來匹配“相似用戶”，實現旅游推薦的。例如AhasR[8]等以愛沙尼亞為例，對旅客的旅游活動進行了問卷調查，并分析了其偏好的旅游目的地信息；麻風梅[9]等通過在線訪談的方式獲取用戶旅游需求，以計算游客相似興趣度的方法推薦景點；王顯飛[11]等通過會話的方式了解用戶需求，以篩選旅游知識庫的方式產生景點和酒店的推薦。基于用戶調查與評分的方法雖然能有效地為用戶推薦旅游信息，但在繁忙的網絡社會中，顯式評分信息只會越來越少，而簽到操作和歷史記錄中包含的隱式路線流行度將成為重要的推薦依據。

為解決用戶評分信息的缺失，不同于傳統的基于用戶評分推薦，本文提出基于Gowalla簽到數據集建立位置時間序列，通過一種新的深度表示模型訓練特征向量，從結果中探討用戶隱含的移動模式價值。通過kmeans聚類算法和KNN分類算法對位置時間序列特征向量進行處理，提取流行移動模式幫助旅客選擇路線。

1 數據預處理

首先介紹本文所用的簽到數據集屬性，并進行預處理操作。

1.1 數據屬性

Gowalla是一個基于位置的社交網絡，網站用戶可以分享簽到數據。這里收錄了共6 442 890條用戶簽到數據，時間為2009年2月到2010年10月。每條簽到數據包含5種屬性，分別是用戶編號、經度、緯度、時間和地點編號。具體數據記錄見表1。

3 實驗分析

利用Gowalla數據集進行測評，通過深度表示模型探索用戶的移動模式，并用模擬游客數據驗證用戶移動模式對旅游路線推薦的效果。endprint

3.1 用戶移動模式

由于訓練所得的位置時間序列向量很難直觀顯示出用戶隱含的移動模式，因此選擇使用Kmeans聚類算法對數據特征進行歸納。Kmeans算法作為最基礎的聚類算法之一，不需要從外部確定類，完全根據訓練數據的特征進行聚類，屬于無監督學習，非常適合對實驗所得的無標簽、雜亂的數據進行處理。但其缺陷是需要人為確定簇的數量，所以選擇兩份不同的向量集分別測試簇總數為5、10、15三種情況，見表2，這里選取簇總數為10的情況介紹。

要將向量特征聚類，需要計算向量間的相似度，即數學上的距離。一般有基于余弦距離和歐幾里得距離公式兩種方法選擇，這里使用計算余弦值的公式：

sim（si，sj）=cosθ=v（si）*v（sj）‖v（si）‖‖v（sj）‖（5）

通過聚類算法，具備相似特征的向量聚集在一個簇中，易于發現用戶隱患的移動模式。首先觀察周末和工作日人們移動模式的變化，發現差異較大，見圖3。為減小誤差，按工作日和周末分類后進行訓練。

根據文獻[14]對地點進行分類，見表3，完成后抽取距離簇中心最近的幾個用戶軌跡，根據地點ID和經緯度數據，選擇具備清晰標簽的軌跡，且忽略掉簇中心為 “公路-公路”，“家-上班”的簇，最后得到含有娛樂標簽的記錄，見表4、表5。

觀察對比表4和表5，可以發現休息的用戶移動模式明顯包含更多娛樂標簽，工作日的移動模式在經過篩選后仍包含大量與旅游路線推薦無關的移動模式，例如：“公路—公路”。所以選擇基于休息日的聚類結果作為旅游路線推薦的依據。

根據表4，可以直觀展現用戶移動模式的類型，如簇二，最流行的5種移動模式都包含了夜生活的標簽，可以證明這類移動軌跡的目的都是享受夜生活服務，類似于這種具備明顯特征屬性的軌跡，可以為旅游路線推薦提供有價值的信息。

3.2 推薦效果測試

通過聚類將具備相似特征的向量聚集在一起，且通過少量位置標簽對用戶移動軌跡進行分類，有利于KNN（最近鄰居）分類算法的實現，這需要人為設定類別并指定k個鄰近點作為分類依據，但不需要前期訓練，時間復雜度為O（n），反饋速度較塊。

假設有一名旅客在某地進行簽到，并想獲得下一步行動指引，這種行為類似于一條用戶軌跡數據缺乏第二個位置點，可以直接為旅客確定下一個目的地的屬性，從而得到對應的移動軌跡向量，然后從對應的用戶軌跡特征向量簇中選擇斜率相似的向量。例如，旅客的第一次簽到在帶有娛樂標簽的位置點，將游客可能感興趣的類型分別設置為下一個目標并訓練特征向量，最后將結果與聚類集合比較，通過KNN算法對位置時間序列向量進行分類，會發現下一個目標含有飯店標簽屬性的例子可能性最高。由此發現旅客潛在的移動軌跡，將當地人流行的休閑移動軌跡推薦給游客。實驗結果表明，推薦路線目標間距離較近，且景點標簽描述準確率高，對旅游路線推薦有一定價值。

表6列出了當地簽到人數最多的三簇休閑娛樂移動模式。表7是針對旅客在不同類型地點進行第一次簽到后，根據表6的移動模式為下一個目的地的出現概率進行的預測。

4 結語

本文嘗試用一種新的深度表示模型對用戶簽到軌跡進行特征值訓練，并利用訓練所得的移動模式特征值聚類作為旅游路線推薦的依據。聚類結果顯示：同種類型的用戶移動軌跡如包含夜生活標簽的軌跡，向量間相似度極高，顯示了具備該標簽的地點在當地的流行度，并且挖掘出了原本沒有標記的同類景點。此外在用戶路線推薦時，很容易發現與當地流行軌跡向量斜率相似的新的軌跡，基于當地實際情況的路線推薦在效率與可行性上也有所提升。

參考文獻：

[1] COOK D， GRADY M， HARE G. How smart is your home？[J].Science，2012，335（6076）：1579-1581.

[2] 余凱，賈磊，陳雨強，等.深度學習的昨天、今天和明天[J].計算機研究與發展，2013，50（9）：1799-1804.

[3] TANG LUAN，ZHENG YU，YUAN JING，et al.On discovery of traveling companions from streaming trajectories[C].Proceedings of the 28th IEEE International Conference on Data Engineering，2012：186-197.

[4] BACKSTROM L，SUN E，MARLOW C.Find me if you can：improving geographical prediction with social and spatial proximity[C].Proceedings of the Conference on WWW，2010：61-70.

[5] 陳勐，禹曉輝，劉洋.基于深度表示模型的移動模式挖掘[J].計算機應用，2016（1）：33-38.

[6] WANG HAO，TERROVITIS M，MAMOULIS N.Location recommendation in location-based social networks using user check-in data[C].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in GIS，2013：364-373.

[7] ZHENG Y，XIE X.Learning travel recommendations from user-generated GPS traces[J].ACM TIST，2011，2（1）：2-3.

[8] AHAS R，ASAS A，ROOSE A，et al.Evaluating Passive Mobile Positioning data for tourism surveys：an estonianease study[J].Tourism Management，2007，3（4）：l-18

[9] 麻風梅.基于游客綜合興趣度的旅游景點推薦[J].測繪與空間地理信息，2014（3）：56-58.

[10] 方瀟，劉曉寒，柴永平，等.一種基于協同過濾的旅游行程推薦算法[J].地理空間信息，2016（7）：53-56.

[11] 王顯飛，陳梅，李小天.基于約束的旅游推薦系統的研究與設計[J].計算機技術與發展，2012（2）：23-26

[12] 胡振，傅昆，張長水.基于深度學習的作曲家分類問題[J].計算機研究與發展，2014，51（9）：1945-1954.

[13] 王瑞琴，蔣云良，李一嘯，等.一種基于多元社交信任的協同過濾推薦算法[J].計算機研究與發展，2016（6）：1389-1399.

[14] YUAN J， ZHENG Y， XIE X. Discovering regions of different functions in a city using human mobility and POIs[C].SIGKDD 2012：Proceeding of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2012：186-194.

（責任編輯：杜能鋼）endprint