一種基于協同過濾的旅游行程推薦算法

方 瀟，劉曉寒，柴永平，周文曼

（1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2. 92292部隊，山東 青島 266000；3.東華理工大學 地球科學學院，江西 南昌 330000）

一種基于協同過濾的旅游行程推薦算法

方 瀟1，劉曉寒1，柴永平2，周文曼3

（1.信息工程大學 地理空間信息學院，河南 鄭州 450052；2. 92292部隊，山東 青島 266000；3.東華理工大學 地球科學學院，江西 南昌 330000）

針對現有的個性化推薦算法在旅游行程推薦領域應用較少，技術不成熟等缺陷，提出基于一種改進協同過濾算法的行程推薦算法。該算法首先依據偏好度計算方法分析用戶對于不同類型旅游目的地的偏好程度，形成用戶-旅游目的地偏好矩陣，并基于偏好矩陣優化K-Means算法的初始聚類中心，為目標用戶建立鄰近用戶集，最后利用改進的相似度計算方法為目標用戶尋找偏好相似的歷史用戶，從而產生行程推薦。實驗結果表明，該算法能夠快速搜索較小的鄰近用戶，得出推薦結果，不僅具有較快的推薦效率，而且具備較好的推薦精準度，在一定程度上為個性化旅游行程推薦服務提供了支撐。

個性化推薦；用戶偏好；協同過濾算法

旅游業的蓬勃發展及大眾旅游熱情的高漲，使得目前主流旅游信息服務平臺提供的海量旅游信息過載，而解決旅游信息過載的一個重要方法是個性化推薦技術[1]。國內外關于個性化旅游推薦的研究成果非常多，現有算法可分為兩類：①通過問答交互的方式獲取用戶需求，產生景點和酒店的推薦。例如：Ahas R[2]等以愛沙尼亞為例，對旅游者的旅游活動進行了問卷調查，并分析了其偏好的個性化旅游目的地信息；麻風梅[3]等通過在線訪談的方式獲取用戶旅游需求，以計算旅游綜合興趣度的方法為其推薦景點；王顯飛[4]等通過會話的方式啟發用戶需求，以約束旅游知識庫的方式產生景點和酒店的推薦。②通過挖掘用戶歷史日志的方式來獲取用戶興趣偏好。例如，HAO Qiang[5]等通過主題建模從游記中挖掘信息并給用戶推薦旅游目的地；呂紅亮[6]等通過挖掘用戶-景點-線路的方式來提取旅游行程，以匹配旅游行程庫的方式來產生推薦；侯新華[7]等通過在線挖掘獲取用戶日志對景點的評價來產生旅游信息的推薦。

當前大多數算法都是依靠用戶對于景點與旅游路線的評分信息來匹配“相似用戶”，實現旅游推薦的。雖然能有效地為用戶推薦旅游信息，然而，在當前繁忙的網絡社會中，顯式的評分信息只會越來越少，隱式的操作信息與歷史記錄會逐漸成為獲取用戶信息的主要來源，傳統的評分式推薦方法將面臨更大的挑戰，如何有效地挖掘用戶的隱式偏好信息成為了推薦領域中亟待解決的難題。

本文基于用戶對于旅游目的地類型的偏好影響行程選擇這一基礎理論來構建用戶模型，依據用戶對于多種旅游目的地類型的偏好來優化K-Means的初始聚類中心，并引入偏好度與改進相似度的計算方法來優化傳統的協同過濾算法。

1 傳統的協同過濾算法

協同過濾算法的核心思想是通過對用戶評估矩陣的分析得到目標用戶的最鄰近用戶集合，然后根據最鄰近用戶集合對項目的評價來預測目標用戶對該項目的評價，從而產生推薦[8]。迄今為止，協同過濾算法在個性化推薦技術中應用非常廣泛，技術也相對成熟。

協同過濾算法分為兩類：基于項目的協同過濾算法與基于用戶的協同過濾算法。本文主要針對研究內容，著重介紹基于用戶的協同過濾算法。

基于用戶的協同過濾算法分為3個階段[9]： ①數據表述，在協同過濾算法中，輸入的初始數據通常可以表達為一個M×N的用戶-評分矩陣，在這個矩陣中，M為用戶的數量，N為項目數量，而矩陣中的值可以認為是用戶M對于項目N的評分。②建立鄰近矩陣，在獲取用戶-項目評分矩陣數據后，如何搜尋與目標用戶具有相同興趣的相似用戶成為協同過濾算法的關鍵。常用的鄰近矩陣建立方法是先利用K-Means算法聚類用戶，然后計算類中目標用戶與其他用戶之間的興趣相似度，通過相似度的大小對用戶進行排序，從而為目標用戶構建最鄰近用戶集。③產生推薦數據集，通過尋找相似用戶集中用戶評分較高項目，產生Top-N的推薦集合。

2 基于協同過濾的旅游行程推薦算法

2.1 算法流程

通過研究分析現有的旅游用戶資料，總結得出旅游目的地的6種主要類型：自然風景型、歷史文化型、民俗風情型、宗教圣地型、刺激冒險型與商務會議型。算法首先通過數據挖掘技術與偏好度計算，獲取旅游用戶對于這些目的地類型的偏好度，建立用戶-旅游目的地類型偏好矩陣；然后利用多種類型偏好作為K-Means的初始聚類中心，聚類偏好相似度較高的旅游用戶，形成多個最鄰近旅游用戶集；最后將偏好度代替項目評分值計算各鄰近集中的用戶相似性，從而為目標用戶尋找最相似用戶，得出一個或多個Top-N行程推薦集。算法流程如圖1所示。

圖1 算法流程圖

2.2 算法框架

2.2.1 旅游用戶目的地偏好建模

用戶模型是實現個性化旅游行程推薦的基礎，本文采用基于旅游目的地類型的空間向量模型來表示用戶對目的地選擇的偏好，即將模型表示為一個N×6的用戶-旅游目的地類型偏好度矩陣SNM，其中，N代表用戶的數量，M代表6類旅游目的地類型，SNM值代表第N個用戶對第M項旅游目的地類型的偏好度。該矩陣可以用表1來解釋。

2.2.2 偏好度計算

本研究引入電商推薦的偏好度算法。根據用戶一段時間對行程的選擇，分析其對各旅游目的地類型的偏好程度；然后依據用戶的偏好程度，對這些旅游目的地類型特征賦相應的值，即當前用戶對于旅游目的地類型的偏好度。

表1 用戶-旅游目的地類型偏好度矩陣

旅游目的地的偏好度定義為：將旅游用戶某時間段內選擇的行程的特點進行統計，旅游目的地類型i的偏好度Ci為用戶已選擇的行程中包含旅游目的地類型i的數量與其旅游總次數的比值[10]：

其中，n為某段時間內用戶選擇行程的總數量；m為某段時間內用戶選擇行程時包含某旅游目的地類型數量。若用戶未曾選取包含某旅游目的地類型的行程時，則用戶對于該旅游目的地類型的偏好度為0。

2.2.3 基于旅游目的地類型偏好的K-Means改進算法

K-Means算法的核心在于其能隨機產生聚類中心，對目標群體進行無監督分類，然而隨機選取的聚類中心無法體現各旅游目的地類型的偏好差異。因此，本文通過前文分析得出的6類旅游偏好設定6個初始聚類中心，將所有旅游用戶聚類成6個最鄰近用戶集。

1）設定每個旅游用戶最多歸屬到3類最鄰近用戶集，依據由大至小的排序方式對當前用戶的偏好度進行排序，選取前3項偏好值進行比較：

其中，Ri、Rj、Rk為當前用戶偏好度最大的3 項偏好值；ε為閾值，用來區分偏好度的大小。

2）通過上述約束條件輸出用戶偏好值，確定所有旅游用戶所歸屬的最鄰近用戶集。

該分類算法相比傳統的K-Means算法具有較好的穩定性，無需算法迭代。

2.2.4 偏好相似度算法

用戶獲取了最鄰近用戶集后，相似度計算方法成為目標用戶尋找相似用戶的重要手段，也是用戶獲取最終Top-N推薦集的關鍵步驟。本文分析了電商推薦的相似性算法，并考慮旅游行程推薦的現實情況，嘗試以偏好度代替項目評分的方法，計算用戶對于旅游目的地類型的偏好相似性。

其中，Ra,p與Rb,p分別為用戶a與用戶b對于某項旅游目的地類型的偏好度；與分別表示用戶a與用戶b所有旅游目的地類型的偏好度平均值；Q（ a， b）為用戶a與用戶b旅游目的地類型的偏好相似度；T（ a， b）為用戶a與用戶b共同的旅游目的地類型偏好集。

通過計算得出目標用戶與最鄰近用戶的相似度大小，并依據相似度大小對相似用戶進行排序。

2.2.5 產生推薦

為了不讓推薦的結果過于復雜，本文將盡可能依據目標用戶歷次旅游的真實情況來篩選最鄰近用戶集中的歷史行程（例如，目標用戶的主要出發地為北京，平均旅游花銷約為3 000元，出行方式主要為自駕，且該用戶一般在法定假期出游，那么算法將篩選最鄰近用戶集中符合出游時間在法定假期、旅游花銷約為3 000元、目的地距離北京較近且目標用戶未曾擁有的歷史行程，產生推薦），并依據最鄰近用戶的相似程度，對獲取的行程進行排序，形成Top-N推薦集合。

3 實驗結果及分析

3.1 實驗數據

本研究分別從螞蜂窩和攜程網的攻略社區選取游記或攻略數量超過10篇的旅游用戶70人；通過文本挖掘與用戶分析手段，隨機提取每名用戶的10條旅游行程，并確定用戶歷次選擇旅游目的地的類型（表2）。采用C#語言，基于VS2010開發平臺，并利用SQL數據庫技術進行用戶建表與數據存儲。

表2 實驗用戶-歷史行程數據表

3.2 實驗方法

首先依據算法流程和實驗數據，計算每名用戶對于各種旅游目的地類型的偏好度，且偏好度之和為1；然后設定閾值ε = 0.3進行用戶聚類，得到以旅游目的地類型偏好為聚類中心的6類最鄰近用戶集；分別計算每類最鄰近用戶集中各用戶之間的旅游目的地類型偏好相似度，為每個用戶求解最鄰近用戶集（用戶集中一般包含10個用戶），并通過每個用戶歷次旅游的真實情況來篩選該最鄰近用戶集的歷史行程，產生維度為3的推薦列表（即產生3個的行程推薦）。

3.3 實驗結果及分析

利用互聯網將140份行程推薦列表發送至原始實驗用戶，返回結果116份，隨機抽取100份結果，并通過準確率評價算法與滿意度調查（采用第1推薦時，滿意度記為非常好；采用第2推薦記為良好；采用第3推薦記為一般；未采用推薦則將滿意度記為差）來檢驗推薦結果。

其中，RC為用戶采納的行程推薦數量；RU為未采納的行程推薦數量；RC+RU為100。統計結果如表3所示。

實驗結果表明，推薦的準確率（用戶采納率）為87.4%。以非常好記10分、良好記8分、一般記6分、差記0分的積分手段，累計得出用戶綜合滿意值為806（總分1 000），則滿意度為80.6%。

4 結 語

本文通過研究旅游行程的個性化推薦問題，提出了基于改進協同過濾的旅游行程推薦算法。該算法通過計算用戶對于旅游目的地類型的偏好度，并用其代替項目評分計算用戶之間的相似度，使之適合用戶多興趣下的個性化推薦[11]。實驗表明，該算法具有較高的準確度與推薦效率，能提高個性化旅游行程推薦的滿意度。但目前的旅游偏好模型構建尚不完善，旅游用戶的興趣建模還需深入研究。在下一步工作中，可從用戶旅游動機入手，獲取更多用戶建模方法，以尋求更優推薦。

表3 推薦結果表

[1] Adomavicius G,Tuzhilin A.Toward the Next Generation of Recommender Systems:a Survey of the State-of-the-art and Possible Extensions[J].IEEE Transactions on Knowledge and Data Engineering, 2005,3(5):734-749

[2] Ahas R,Aasa A,Roose A,et al.Evaluating Passive Mobile Positioning Data for Tourism Surveys:an Estonianease Study[J]. Tourism Management,2007,3(4):l-18

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

[4] 王顯飛,陳梅,李小天.基于約束的旅游推薦系統的研究與設計[J].計算機技術與發展,2012(2):23-26

[5] HAO Qiang,CAI Rui,WANG Changhu,et a1.Equip Tourists with Knowledge Mined from Travelogues[C].Raleigh NC USA,2010

[6] 呂紅亮,王勁林,鄧峰.一種個性化旅游線路推薦算法[J].網絡新媒體技術,2012(3):42-48

[7] 候新華,文益民.基于協同過濾的旅游景點推薦[J].計算技術與自動化,2012,31(4):116-119

[8] 雷錕.電子商務個性化推薦系統研究[D].成都:電子科技大學,2012

[9] 王桂芬.電子商務個性化推薦系統中協同算法的研究與應用[D].南昌:南昌大學,2012

[10] 李峰,李軍懷,王瑞林,等.基于商品特征的個性化推薦算法[J].計算機工程與應用,2007,43(17):194-197

[11] 余力,劉魯,李雪峰.用戶多興趣下的個性化推薦算法研究[J].計算機集成制造系統,2004,10(12):1 610-1 615

表6 安置區和轉移單元各自滿意優先順序

表7 安置區與轉移單元的最佳匹配

參考文獻

[1] 胥淼.從自然災害透視人與自然的和諧發展[D].成都:成都理工大學,2011

[2] 田質勝,朱慶利,李明霞,等.基于GIS的洪災避遷方案的模糊綜合評判[J].中國農村水利水電,2009(10):81-83

[3] 藍秋萍. GIS在洪水受災人員轉移方案設計中的應用研究[D].武漢:華中科技大學,2007

[4] 文成日,耿祥義.層次分析法在購車決策中的應用[J].電腦知識與技術,2009(30):8 514-8 515

[5] 吳大親,么文學.基于層次分析法的應用型人才培養評價模式研究[J].長春師范學院學報(自然科學版),2010(8):28-31

[6] 黃曉菁.基于AHP方法的圖書館信息服務能力研究[J].情報雜志,2007(9):149-151

[7] 段春生.基于雙向選擇的匹配問題[J].西南師范大學學報(自然科學版),2012(8):15-18

第一作者簡介：征程，碩士研究生，研究方向為空間信息分析與應用。

P208

B

1672-4623（2016）07-0053-04

10.3969/j.issn.1672-4623.2016.07.016

方瀟，碩士研究生，主要研究方向為地學可視化。

2015-01-23。

項目來源：國家高技術研究發展計劃資助項目（2012AA12A404）；國家自然科學基金資助項目（41171353）。