方 瀟,劉曉寒,柴永平,周文曼
(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ò)濾算法。
協(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.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.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%。
本文通過(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)。