梁棟屹+陶宏曜+劉興旺

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

關(guān)鍵詞：社交網(wǎng)絡(luò)；深度表示模型；Kmeans聚類；用戶移動模式；訓(xùn)練特征向量

DOIDOI：10.11907/rjdk.171932

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

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

1 數(shù)據(jù)預(yù)處理

首先介紹本文所用的簽到數(shù)據(jù)集屬性，并進(jìn)行預(yù)處理操作。

1.1 數(shù)據(jù)屬性

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

3 實驗分析

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

3.1 用戶移動模式

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

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

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

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

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

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

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

3.2 推薦效果測試

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

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

表6列出了當(dāng)?shù)睾灥饺藬?shù)最多的三簇休閑娛樂移動模式。表7是針對旅客在不同類型地點進(jìn)行第一次簽到后，根據(jù)表6的移動模式為下一個目的地的出現(xiàn)概率進(jìn)行的預(yù)測。

4 結(jié)語

本文嘗試用一種新的深度表示模型對用戶簽到軌跡進(jìn)行特征值訓(xùn)練，并利用訓(xùn)練所得的移動模式特征值聚類作為旅游路線推薦的依據(jù)。聚類結(jié)果顯示：同種類型的用戶移動軌跡如包含夜生活標(biāo)簽的軌跡，向量間相似度極高，顯示了具備該標(biāo)簽的地點在當(dāng)?shù)氐牧餍卸?，并且挖掘出了原本沒有標(biāo)記的同類景點。此外在用戶路線推薦時，很容易發(fā)現(xiàn)與當(dāng)?shù)亓餍熊壽E向量斜率相似的新的軌跡，基于當(dāng)?shù)貙嶋H情況的路線推薦在效率與可行性上也有所提升。

參考文獻(xiàn)：

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

[2] 余凱，賈磊，陳雨強(qiáng)，等.深度學(xué)習(xí)的昨天、今天和明天[J].計算機(jī)研究與發(fā)展，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].計算機(jī)應(yīng)用，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] 麻風(fēng)梅.基于游客綜合興趣度的旅游景點推薦[J].測繪與空間地理信息，2014（3）：56-58.

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

[11] 王顯飛，陳梅，李小天.基于約束的旅游推薦系統(tǒng)的研究與設(shè)計[J].計算機(jī)技術(shù)與發(fā)展，2012（2）：23-26

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

[13] 王瑞琴，蔣云良，李一嘯，等.一種基于多元社交信任的協(xié)同過濾推薦算法[J].計算機(jī)研究與發(fā)展，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.

（責(zé)任編輯：杜能鋼）endprint