一種基于協(xié)同過(guò)濾的旅游行程推薦算法

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

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

一種基于協(xié)同過(guò)濾的旅游行程推薦算法

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

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

針對(duì)現(xiàn)有的個(gè)性化推薦算法在旅游行程推薦領(lǐng)域應(yīng)用較少，技術(shù)不成熟等缺陷，提出基于一種改進(jìn)協(xié)同過(guò)濾算法的行程推薦算法。該算法首先依據(jù)偏好度計(jì)算方法分析用戶對(duì)于不同類型旅游目的地的偏好程度，形成用戶-旅游目的地偏好矩陣，并基于偏好矩陣優(yōu)化K-Means算法的初始聚類中心，為目標(biāo)用戶建立鄰近用戶集，最后利用改進(jìn)的相似度計(jì)算方法為目標(biāo)用戶尋找偏好相似的歷史用戶，從而產(chǎn)生行程推薦。實(shí)驗(yàn)結(jié)果表明，該算法能夠快速搜索較小的鄰近用戶，得出推薦結(jié)果，不僅具有較快的推薦效率，而且具備較好的推薦精準(zhǔn)度，在一定程度上為個(gè)性化旅游行程推薦服務(wù)提供了支撐。

個(gè)性化推薦；用戶偏好；協(xié)同過(guò)濾算法

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

當(dāng)前大多數(shù)算法都是依靠用戶對(duì)于景點(diǎn)與旅游路線的評(píng)分信息來(lái)匹配“相似用戶”，實(shí)現(xiàn)旅游推薦的。雖然能有效地為用戶推薦旅游信息，然而，在當(dāng)前繁忙的網(wǎng)絡(luò)社會(huì)中，顯式的評(píng)分信息只會(huì)越來(lái)越少，隱式的操作信息與歷史記錄會(huì)逐漸成為獲取用戶信息的主要來(lái)源，傳統(tǒng)的評(píng)分式推薦方法將面臨更大的挑戰(zhàn)，如何有效地挖掘用戶的隱式偏好信息成為了推薦領(lǐng)域中亟待解決的難題。

本文基于用戶對(duì)于旅游目的地類型的偏好影響行程選擇這一基礎(chǔ)理論來(lái)構(gòu)建用戶模型，依據(jù)用戶對(duì)于多種旅游目的地類型的偏好來(lái)優(yōu)化K-Means的初始聚類中心，并引入偏好度與改進(jìn)相似度的計(jì)算方法來(lái)優(yōu)化傳統(tǒng)的協(xié)同過(guò)濾算法。

1 傳統(tǒng)的協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法的核心思想是通過(guò)對(duì)用戶評(píng)估矩陣的分析得到目標(biāo)用戶的最鄰近用戶集合，然后根據(jù)最鄰近用戶集合對(duì)項(xiàng)目的評(píng)價(jià)來(lái)預(yù)測(cè)目標(biāo)用戶對(duì)該項(xiàng)目的評(píng)價(jià)，從而產(chǎn)生推薦[8]。迄今為止，協(xié)同過(guò)濾算法在個(gè)性化推薦技術(shù)中應(yīng)用非常廣泛，技術(shù)也相對(duì)成熟。

協(xié)同過(guò)濾算法分為兩類：基于項(xiàng)目的協(xié)同過(guò)濾算法與基于用戶的協(xié)同過(guò)濾算法。本文主要針對(duì)研究?jī)?nèi)容，著重介紹基于用戶的協(xié)同過(guò)濾算法。

基于用戶的協(xié)同過(guò)濾算法分為3個(gè)階段[9]： ①數(shù)據(jù)表述，在協(xié)同過(guò)濾算法中，輸入的初始數(shù)據(jù)通?？梢员磉_(dá)為一個(gè)M×N的用戶-評(píng)分矩陣，在這個(gè)矩陣中，M為用戶的數(shù)量，N為項(xiàng)目數(shù)量，而矩陣中的值可以認(rèn)為是用戶M對(duì)于項(xiàng)目N的評(píng)分。②建立鄰近矩陣，在獲取用戶-項(xiàng)目評(píng)分矩陣數(shù)據(jù)后，如何搜尋與目標(biāo)用戶具有相同興趣的相似用戶成為協(xié)同過(guò)濾算法的關(guān)鍵。常用的鄰近矩陣建立方法是先利用K-Means算法聚類用戶，然后計(jì)算類中目標(biāo)用戶與其他用戶之間的興趣相似度，通過(guò)相似度的大小對(duì)用戶進(jìn)行排序，從而為目標(biāo)用戶構(gòu)建最鄰近用戶集。③產(chǎn)生推薦數(shù)據(jù)集，通過(guò)尋找相似用戶集中用戶評(píng)分較高項(xiàng)目，產(chǎn)生Top-N的推薦集合。

2 基于協(xié)同過(guò)濾的旅游行程推薦算法

2.1 算法流程

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

圖1 算法流程圖

2.2 算法框架

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

用戶模型是實(shí)現(xiàn)個(gè)性化旅游行程推薦的基礎(chǔ)，本文采用基于旅游目的地類型的空間向量模型來(lái)表示用戶對(duì)目的地選擇的偏好，即將模型表示為一個(gè)N×6的用戶-旅游目的地類型偏好度矩陣SNM，其中，N代表用戶的數(shù)量，M代表6類旅游目的地類型，SNM值代表第N個(gè)用戶對(duì)第M項(xiàng)旅游目的地類型的偏好度。該矩陣可以用表1來(lái)解釋。

2.2.2 偏好度計(jì)算

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

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

旅游目的地的偏好度定義為：將旅游用戶某時(shí)間段內(nèi)選擇的行程的特點(diǎn)進(jìn)行統(tǒng)計(jì)，旅游目的地類型i的偏好度Ci為用戶已選擇的行程中包含旅游目的地類型i的數(shù)量與其旅游總次數(shù)的比值[10]：

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

2.2.3 基于旅游目的地類型偏好的K-Means改進(jìn)算法

K-Means算法的核心在于其能隨機(jī)產(chǎn)生聚類中心，對(duì)目標(biāo)群體進(jìn)行無(wú)監(jiān)督分類，然而隨機(jī)選取的聚類中心無(wú)法體現(xiàn)各旅游目的地類型的偏好差異。因此，本文通過(guò)前文分析得出的6類旅游偏好設(shè)定6個(gè)初始聚類中心，將所有旅游用戶聚類成6個(gè)最鄰近用戶集。

1）設(shè)定每個(gè)旅游用戶最多歸屬到3類最鄰近用戶集，依據(jù)由大至小的排序方式對(duì)當(dāng)前用戶的偏好度進(jìn)行排序，選取前3項(xiàng)偏好值進(jìn)行比較：

其中，Ri、Rj、Rk為當(dāng)前用戶偏好度最大的3 項(xiàng)偏好值；ε為閾值，用來(lái)區(qū)分偏好度的大小。

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

該分類算法相比傳統(tǒng)的K-Means算法具有較好的穩(wěn)定性，無(wú)需算法迭代。

2.2.4 偏好相似度算法

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

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

通過(guò)計(jì)算得出目標(biāo)用戶與最鄰近用戶的相似度大小，并依據(jù)相似度大小對(duì)相似用戶進(jìn)行排序。

2.2.5 產(chǎn)生推薦

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本研究分別從螞蜂窩和攜程網(wǎng)的攻略社區(qū)選取游記或攻略數(shù)量超過(guò)10篇的旅游用戶70人；通過(guò)文本挖掘與用戶分析手段，隨機(jī)提取每名用戶的10條旅游行程，并確定用戶歷次選擇旅游目的地的類型（表2）。采用C#語(yǔ)言，基于VS2010開發(fā)平臺(tái)，并利用SQL數(shù)據(jù)庫(kù)技術(shù)進(jìn)行用戶建表與數(shù)據(jù)存儲(chǔ)。

表2 實(shí)驗(yàn)用戶-歷史行程數(shù)據(jù)表

3.2 實(shí)驗(yàn)方法

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

3.3 實(shí)驗(yàn)結(jié)果及分析

利用互聯(lián)網(wǎng)將140份行程推薦列表發(fā)送至原始實(shí)驗(yàn)用戶，返回結(jié)果116份，隨機(jī)抽取100份結(jié)果，并通過(guò)準(zhǔn)確率評(píng)價(jià)算法與滿意度調(diào)查（采用第1推薦時(shí)，滿意度記為非常好；采用第2推薦記為良好；采用第3推薦記為一般；未采用推薦則將滿意度記為差）來(lái)檢驗(yàn)推薦結(jié)果。

其中，RC為用戶采納的行程推薦數(shù)量；RU為未采納的行程推薦數(shù)量；RC+RU為100。統(tǒng)計(jì)結(jié)果如表3所示。

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

4 結(jié) 語(yǔ)

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

表3 推薦結(jié)果表

[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] 麻風(fēng)梅.基于游客綜合興趣度的旅游景點(diǎn)推薦[J].測(cè)繪與空間地理信息,2014(3):56-58

[4] 王顯飛,陳梅,李小天.基于約束的旅游推薦系統(tǒng)的研究與設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展,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] 呂紅亮,王勁林,鄧峰.一種個(gè)性化旅游線路推薦算法[J].網(wǎng)絡(luò)新媒體技術(shù),2012(3):42-48

[7] 候新華,文益民.基于協(xié)同過(guò)濾的旅游景點(diǎn)推薦[J].計(jì)算技術(shù)與自動(dòng)化,2012,31(4):116-119

[8] 雷錕.電子商務(wù)個(gè)性化推薦系統(tǒng)研究[D].成都:電子科技大學(xué),2012

[9] 王桂芬.電子商務(wù)個(gè)性化推薦系統(tǒng)中協(xié)同算法的研究與應(yīng)用[D].南昌:南昌大學(xué),2012

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

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

表6 安置區(qū)和轉(zhuǎn)移單元各自滿意優(yōu)先順序

表7 安置區(qū)與轉(zhuǎn)移單元的最佳匹配

參考文獻(xiàn)

[1] 胥淼.從自然災(zāi)害透視人與自然的和諧發(fā)展[D].成都:成都理工大學(xué),2011

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

[3] 藍(lán)秋萍. GIS在洪水受災(zāi)人員轉(zhuǎn)移方案設(shè)計(jì)中的應(yīng)用研究[D].武漢:華中科技大學(xué),2007

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

[5] 吳大親,么文學(xué).基于層次分析法的應(yīng)用型人才培養(yǎng)評(píng)價(jià)模式研究[J].長(zhǎng)春師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2010(8):28-31

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

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

第一作者簡(jiǎn)介：征程，碩士研究生，研究方向?yàn)榭臻g信息分析與應(yīng)用。

P208

B

1672-4623（2016）07-0053-04

10.3969/j.issn.1672-4623.2016.07.016

方瀟，碩士研究生，主要研究方向?yàn)榈貙W(xué)可視化。

2015-01-23。

項(xiàng)目來(lái)源：國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目（2012AA12A404）；國(guó)家自然科學(xué)基金資助項(xiàng)目（41171353）。