基于Hadoop的旅游景點推薦的算法實現與應用

馬騰騰，朱慶華，曹 菡，沈 超

(1.南京大學 信息管理學院，江蘇 南京 210023；2.陜西師范大學 計算機科學學院，陜西 西安 710119；3.南京郵電大學 經濟與管理學院，江蘇 南京 210046)

基于Hadoop的旅游景點推薦的算法實現與應用

馬騰騰1，朱慶華1，曹 菡2，沈 超3

(1.南京大學 信息管理學院，江蘇 南京 210023；2.陜西師范大學 計算機科學學院，陜西 西安 710119；3.南京郵電大學 經濟與管理學院，江蘇 南京 210046)

通過提高挖掘效率、增強算法擴展性,解決傳統的推薦算法在旅游景點推薦方面響應時間長、推薦效率低，無法適應大數據挖掘需求的問題。對現有協同過濾推薦算法進行深入分析，選取適用于旅游景點推薦的Slope One算法和Item-based算法。將這兩種算法高效結合，并基于MapReduce編程在Hadoop云平臺上實現算法并行化，通過采集“旅評網”的真實旅游景點評分數據驗證算法的有效性。通過測試真實的旅游景點評分數據，表明算法不僅提高了推薦的準確度,而且比傳統的協同過濾算法具有更高的運行速度。實驗結果較好地說明了該算法具有更高的挖掘性能和可擴展性，能夠更好地適應旅游景點數據量大、數據矩陣稀疏的特性，滿足旅游景點推薦高命中率和個性化的要求。

Hadoop；旅游景點推薦；協同過濾；Mahout；Item-based；Slope One

1 概 述

旅游業是國內經濟支柱產業之一，近年來國內旅游行業持續升溫。在旅游領域，隨著信息技術發展，互聯網信息飛速膨脹，使得旅游者對信息的使用效率大大降低，因此關于旅游服務的各種推薦應運而生。

目前關于旅游的推薦有景點推薦、線路推薦和酒店推薦等[1]。文獻[2]設計和實現了一個基于混合模式的簡單的個性化旅游推薦原型系統；文獻[3]設計了一種本體和地理信息系統相結合的推薦系統；文獻[4]使用協同過濾算法對從在線旅游網站上提取的游客對桂林旅游景點的評價數據進行旅游景點推薦。在推薦算法上，普遍使用的推薦算法有基于協同過濾的推薦、基于內容的推薦和基于模型的推薦等。其中基于協同過濾的推薦算法在個性化系統中應用最廣[5]。同時，針對協同過濾的推薦算法的研究成果比較多，如MovieLens[6]、GroupLens[7]、視頻推薦系統[8]以及Ringo[9]，這些應用都在互聯網上擁有廣泛的用戶。在商業方面，一些知名的網站已經成功運用協同過濾技術，如Amazon.com、Launch.com、MovieFinder.com和CDNow.com。近幾年，研究學者也對協同過濾算法進行了很多優化與改進。Sarwar B等[10]研究了基于項目的協同過濾推薦算法，并對余弦相似度算法進行了優化。Lemire D等[11]提出了Slope One算法，較好地解決了數據稀疏性和冷啟動問題。

信息化時代在為旅游者提供便捷的同時也帶來了挑戰。雖然潛在旅游者可以借助互聯網搜集到大量的信息，但由于信息量大且參差不齊，信息搜集者需要耗費大量的時間去篩選，且仍不能保證最終信息搜集的準確性。這種情況大大增加了旅游者制定出行計劃的難度，增加了旅游者的出行成本，降低了對景點的滿意度。隨著推薦系統得到廣泛的認可，現有的推薦系統也面臨著關鍵性挑戰，如何提供高質量的推薦結果，如何能快速為數以萬計的用戶做出高質量的推薦，如何能在數據極度稀疏的情況下滿足高命中率和個性化的需求，這些都是亟待解決的問題。

文中結合旅游消費行為的特點與大數據的特性，探索一種針對旅游景點推薦的協同過濾算法，提出一種基于項目的協同過濾算法和Slope One算法相結合的解決方法，從而進一步提高推薦的速度和精度，同時使用Apache Mahout項目在Hadoop平臺上將其實現。

2 推薦算法的優化

文中采用Slope One與Item-based的結合算法，能有效針對旅游景點進行推薦。

2.1 Slope One算法

Daniel Lemire和Anna Maclachlan在2005年發表的論文中提出Slope One算法[11]。Slope One算法是對基于項目的協同過濾算法的簡化和改進。該算法的實現過程簡單而高效，而且與其他費時復雜的算法相比，其精度不相上下[12]。

Slope One算法的原理是根據各個用戶對各項目的偏好平均分差來對未評分的項目進行評分預測。計算平均分差的公式為：

(1)

其中：s表示同時對景點i和j給予了評分的用戶集合;card表示集合中所包含的評分數量。

根據式(1)就可以獲得某特定用戶對未評分景點的預測評分結果。當把所有可能的預測評分平均起來,就得到式(2)：

(2)

其中:P(u)j表示用戶對景點j的預測評價；Rj表示所有已經被用戶u給予評價的項目集合。

SlopeOne算法適用于旅游景點推薦的原因有：

第一，與其他協同過濾算法比較而言，SlopeOne算法無需計算景點或者用戶的相似度，直接根據用戶的已有評分進行預估，原理簡單，計算速度快，能在海量旅游數據中快速得出推薦結果，提高效率。

第二，SlopeOne算法對評分記錄很少的用戶也能得出推薦結果，有效地解決了稀疏矩陣問題。這對實際運作中推薦系統能否在稀疏矩陣的情況下進行有效推薦具有重要意義。

2.2 基于項目的推薦算法

基于項目的協同過濾(Item-based collaborative filtering)算法是目前業界應用最多的算法，主要分為兩步：

(1)計算物品與物品之間的相似度。

Pearson相似度算法：設U為對項目i和項目j都評過分的用戶集合，且Uij=Ui∩Uj，則Sim(i,j)為：

Sim(i,j)=

(3)

(2)根據物品之間的相似度和用戶的行為記錄，使用權重求和的方法來計算預測評分，給用戶推薦相應物品。目標用戶u對項目i的預測評分Pu,i為：

(4)

其中：Ru,n表示用戶u對相似項目集中項目n的評分；Si,n表示項目i與項目n的相似程度。

選擇基于項目的協同過濾算法作為景點推薦算法的原因是每個人喜歡的景點大多局限于一類或兩類中，且具有一定的相似性。而基于項目的協同過濾算法即是通過計算景點之間的相似度，將與用戶喜愛的景點相似的推薦給用戶，符合旅游行為的特征。

2.3 推薦算法的改進

人們喜愛的景點大多僅限于特定類型。對此，基于項目的協同過濾算法完全符合相似性這一旅游行為特點。該算法能夠根據其他用戶對景點的偏好，發現與當前用戶喜好的景點相類似的景點，為當前用戶進行推薦。然而，該算法不能解決稀疏矩陣的問題，這在實際的推薦系統中反映為不能為新用戶進行推薦，大大影響了算法的整體性。

Slope One算法則不同，即使只有一條數據該算法也能進行推薦，且運算速度快。如果將這兩種算法相結合，既能根據旅游數據的特點進行有效推薦，又能解決數據稀疏性問題。

文中根據基于項目協同過濾算法和Slope One推薦算法的優缺點，將兩種算法相結合，共同構成旅游景點的推薦算法，并利用真實的旅游數據進行測算。統計后發現在用戶記錄數低于3的情況下，基于用戶協同過濾算法由于數據量太小不能得出推薦結果，因此選擇記錄數“3”作為算法選擇的臨界點。如果記錄數大于等于3，那么就通過Item-based算法得到推薦結果，否則采用Slope One算法獲得推薦結果。

該方法的優點是將兩種算法相結合，進一步提高了旅游景點推薦的準確性，而且解決了數據稀疏性問題。

3 推薦系統的實現

3.1 總體架構設計

將推薦系統在云計算平臺上實現，不僅可以解決超大規模數據集的存儲、處理難題，而且增強了系統的可擴展性。文中在Hadoop云平臺上研究旅游景點推薦算法，其框架如圖1所示。

圖1 景點推薦系統框架

該系統主要包括數據采集模塊、數據預處理模塊和算法推薦模塊三部分。

數據采集模塊：利用“火車頭”軟件從“旅行網”上爬取所需的數據，即用戶對景點的評分集。文中使用的所有數據均來自于正規的旅游網站，真實可靠，確保了算法與旅游景點推薦的切合性；

數據預處理模塊：將采集來的數據進行編碼，轉化為CSV文件格式，以便算法程序能夠識別；

算法推薦模塊：以Hadoop平臺為基礎，將MapReduce并行化，推薦算法后臺程序生成推薦模型，根據采集來的真實數據計算推薦結果[13-14]。

3.2 數據的獲取

3.2.1 采集網站

文中選擇“旅評網”作為數據采集網站。旅評網是國內領先的在線旅游景點信息平臺，同時也是旅行者對景點點評和經驗分享的社區。鑒于旅評網在驢友中有較好的口碑，是分享旅游心得和景點評分的權威平臺，所以選擇該網站作為數據爬取網站。

文中所需要的數據格式為“用戶+景點+評分”，因此對旅評網上各個景點的名稱和評論該景點的用戶名及其對該景點的評分進行采集。

3.2.2 采集工具

文中使用火車頭采集器(LocoySpider)進行旅游數據的采集。該軟件是一款功能齊全且易于上手的專業采集軟件，具有內容采集和數據導入、導出功能。利用系統內置標簽,將采集到的數據對應表的字段導出到本地的Access數據庫中。

3.2.3 采集過程

數據采集采用“前后截取”的方法，根據網頁源代碼，確定所需內容所在的位置并截取。文中只截取三列信息，分別為：用戶、景點和評分。

3.2.4 數據預處理

采集來的景點名稱、用戶名都是漢字，在Hadoop下Mahout不能識別，因此必須對景點名稱和用戶名進行編碼，用戶編碼為1～1404，景點編碼為10001～10200。

整理后得到評分數據5 144條，1 404個用戶，景點200個。

3.3 Hadoop平臺上景點推薦算法的實現

3.3.1 Hadoop平臺的搭建

Hadoop的運行模式主要有三種：單機模式、偽分布式和完全分布式。文中搭建的是偽分布式Hadoop平臺。

(1)硬件配置。

處理器：Intel Core i5-2400(3.10 GHz四核64 bit)；

內存(RAM)：4 GB；

硬盤：500 GB(7200轉)；

主板：HP 1497(Inter Q65芯片組)。

(2)軟件環境。

操作系統：Ubuntu 12.10；

JDK版本：1.7.0_04。

3.3.2 用戶記錄的計數

文中需要對用戶評分數據進行計數，根據記錄數將用戶分類選擇合適的算法。由于數據量龐大，不適宜采用耗時耗力的人工計數。Hadoop平臺具有運算速度快、穩定性高的特點，因此文中利用搭建好的Hadoop平臺，將用戶數據上傳至HDFS，調用WordCount程序，計算出每個用戶的評分數，以便進行下一步的算法選擇。

3.3.3 算法的Map/Reduce化

在Hadoop環境下，Slope One推薦算法的整個過程如下：

(1)根據用戶id找出用戶沒有偏好過的集合作為被推薦物品，并找出用戶偏好過的物品及其評分。

(2)對每一個被推薦物品列表中的物品i，根據用戶偏好過的物品列表中物品對i計算預測評分。

(3)把所有的推薦物品及其預測評分組成一個列表并排序。沒有評分的可以省去。

(4)對推薦結果進行處理。

圖2是描述Slope One算法計算用戶對被推薦物品的預測評分的偽代碼。其主要過程如下：

圖2 Slope One的MapReduce化

Map的輸入是以userId為鍵值，根據步驟2組合的itemId為value。Map輸出的結果是以要預測的物品j為key值，以同時評分個數count以及計算結果的字符串連接為value。在Reducer之前這些結果會被MapReduce框架合并在一起交給Reducer計算。Reducer經過計算，其結果即為用戶對物品j的預測評分。

Item-based實現的主要流程就在Mahout包的RecommenderJob類中。所有的步驟均包含在這個類的run方法中。計算過程共分為10步，其中相似度的計算被拆分成3個job。圖3為詳細的步驟分析。

圖3 Item-based的MapReduce化

至此，已經形成了推薦結果，Item-based推薦算法完成。

4 結果分析及討論

對任意一個用戶，推薦系統會按照推薦算法模塊中的設定條件，選擇基于項目協同過濾算法或者Slope One算法進行計算，得出一組推薦景點的ID和用戶對該景點的預估評分(文中設定為每位用戶推薦10個景點)，并按預測評分降序排序。相應內容如圖4所示。

圖4 推薦結果示例

結果的輸出格式為：

<用戶代碼 [推薦景點1：預測評分1，……，推薦景點10：預測評分10]>

每行中的第一個數字是用戶代碼，中括號里的是推薦的景點代碼及其對應的預測評分，按評分由高到低排列。該算法為每個用戶推薦10個景點，以逗號間隔。如圖4所示，為1號用戶推薦10113號景點，且該用戶對10113號景點的預估評分為5.67分。

為了對比各個算法的運算速度以及對旅游數據的適用程度，在算法實現后，筆者從“旅評網”采集三組大小不同的旅游數據，調試和運行分布式協同過濾算法。

此次采集的旅游數據共有5 144條評分記錄，如表1所示。

表1 數據采集統計表

在算法的精確度方面，文中采用平均絕對誤差(MAE)作為評價指標。它是協同過濾算法中統計精度的常用評價標準，其計算公式為：

(5)

MAE越小，表示精度越高。在評分記錄數不同的情況下，各個算法的MAE值如圖5所示。

圖5 MAE比較

可以看出，隨著數據量逐漸增大，各個算法的精度都有所提高。在數據量相同的情況下，基于項目協同過濾算法的精度始終高于SlopeOne算法，結合算法的精度位于二者之間。

在算法的耗時方面，文中依然取以上三組數據作為實驗數據，測算基于用戶協同過濾算法、SlopeOne算法以及結合算法對數據處理的響應時間，結果如圖6所示。

可以看出，基于項目協同過濾算法花費的時間要比SlopeOne算法多。原因是基于項目協同過濾需要計算景點之間的相似度，然后將相似度加權計算得到最終推薦結果，而SlopeOne算法無需計算景點或者用戶的相似度，直接根據用戶已有數據進行預估評分。結合算法的運算速度介于兩者之間。

圖6 響應時間比較

通過以上實驗結果得出，基于項目協同過濾算法在精度上優于SlopeOne算法，然而通過分析采集來的旅游數據發現，人們受各種因素的限制，去過的旅游景點數較為有限，因此評分數據矩陣相比于電影評分、圖書評分等較為稀疏。這一點決定了基于項目協同過濾算法在旅游景點推薦上具有一定的局限性。雖然SlopeOne算法在精度上不及基于項目協同過濾算法，卻能有效解決數據稀疏性問題，且運算速度較快。結合算法在精度和運算時間上均介于兩種算法之間，發揮了兩種算法的優勢，因此十分適用于矩陣稀疏、數據量較大的旅游景點推薦。

從算法的應用效果來看，將SlopeOne與基于項目的協同過濾算法相結合，揚長避短，既發揮了SlopeOne算法運算速度快的優勢，又利用基于項目協同過濾算法提高了推薦結果的準確性；其次，在用戶記錄數很少的情況下選用SlopeOne算法，有效地解決了數據稀疏性問題，使系統即使在數據矩陣十分稀疏的情況下也能進行推薦；并且，使用的基于項目協同過濾算法和SlopeOne算法能貼切地迎合旅游消費者的動機和行為，提高用戶的體驗，避免了用戶需要花費大量的時間才能找到自己感興趣的景點的情況，具有一定的針對性。

從算法的運行效果來看，系統能準確地按照當前用戶的喜好信息以及相似用戶的喜好信息推薦旅游景點。系統通過算法計算出的各個景點的預測值，并將推薦結果的預測值由高到低進行排序，將排名前10的景點推薦給用戶。同時，通過多次測試表明，相同用戶在喜好信息沒有發生變化的前提下，該推薦系統的推薦結果保持不變，表現出較好的算法穩定性。因此在推薦結果方面，該景點推薦系統能根據用戶對景點的已有評分較為準確地預測對未評分景點的喜好程度，并依據預測評分進行景點推薦。

在技術應用創新方面，利用Hadoop云平臺進行服務推薦不僅可以提高數據存儲與處理能力，而且可以增強系統的可擴展性。

5 結束語

文中提出了Item-based協同過濾算法與SlopeOne推薦算法相結合的解決方案。采集真實旅游景點評分數據，將推薦系統在Hadoop云平臺上加以實現，具有一定的實際應用價值。

同時，算法仍存在一些不足和需要進一步研究的方面：

(1)文中在云平臺上實現了Item-based和SlopeOne相結合的算法，并沒有真正實現推薦系統，僅對算法進行了實現與應用。今后可以考慮開發完整的旅游景點推薦系統。

(2)文中主要根據用戶對景點的已有評分預測用戶的偏好，考慮的因素不夠全面。在今后的研究中，可以綜合多個影響評分的因素，如在算法中加入用戶的社交關系和情感因素等參數。

[1] 汪英姿,馬 慰,徐守坤.一種基于本體的旅游資源二次推薦方法[J].情報科學,2012,30(12):1866-1871.

[2] 石 靜.基于混合模式的個性化推薦系統的應用研究[D].武漢:武漢理工大學,2010.

[3] 胡納納,李琳琳,武 尚.個性化的旅游推薦系統[J].信息技術,2013(2):135-139.

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

[5] 奉國和,梁曉婷.協同過濾推薦研究綜述[J].圖書情報工作,2011,55(16):126-130.

[6]BradleyNM,AlbertI,ShyongKL,etal.MovieLensunplugged:experienceswithanoccasionallyconnectedrecommendersystem[C]//Proceedingsofthe8thinternationalconferenceonintelligentuserinterfaces.NewYork,USA:[s.n.],2003:263-266.

[7]KonstanJA,MillerBN,MaltzD,etal.GroupLens:applyingcollaborativefilteringtoUsenetnews[J].CommunicationsoftheACM,1997,40(3):77-87.

[8]HillW,SteadL,RosensteinM,etal.Recommendingandevaluatingchoicesinavirtualcommunityofuse[C]//Proceedingsoftheconferenceonhumanfactorsincomputingsystems.Denver,USA:ACM,1995:194-201.

[9]ShardanandU,MaesP.Socialinformationfiltering:algorithmsforautomating"wordofmouth"[C]//Proceedingsoftheconferenceonhumanfactorsincomputingsystems.Denver,USA:ACM,1995:210-217.

[10]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalworldwidewebconference.HongKong,China:IW3C2,2001:285-295.

[11]LemireD，MaclachlanA.Slopeonepredictorsforonlinerating-basedcollaborativefiltering[C]//ProceedingsofSIAMdatamining.NewPortBeach,California:CompensationCommittee,2005.

[12] 王 毅,樓恒越.一種改進的SlopeOne協同過濾算法[J].計算機科學,2011,38(10A):192-194.

[13]DeanJ,GhemawatS.MapReduce:simplieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.

[14]ShvachkoK,KuangH,RadiaS,etal.TheHadoopdistributedfilesystem[C]//Proceedingsofthe26thsymposiumonmassstoragesystemsandtechnologies.InclineVillage,USA:IEEE,2010:1-10.

Implementation and Application of Algorithm of Tourist Attractions Recommendation Based on Hadoop

MA Teng-teng1,ZHU Qing-hua1,CAO Han2,SHEN Chao3

(1.School of Information Management,Nanjing University,Nanjing 210023,China;2.School of Computer Science,Shannxi Normal University,Xi’an 710119,China;3.School of Engineering and Management,Nanjing University,Nanjing 210046,China)

The problems that the traditional tourist recommendation algorithm has long response and low efficiency in tourist recommendation,and have been unable to meet the mining needs of large amount of data can be solved by improving mining efficiency and enhancing scalability.It conducts a deep analysis for existing collaborative filtering algorithms in this paper and selects the Slope One algorithm and the Item-based algorithm suitable for tourist attractions recommendation to efficiently combine.Then the new algorithm is paralleled based on Hadoop framework,and the algorithm’s validity is proved by the data collected from “www.ilvping.com”.The faster speed and higher accuracy of the recommendation algorithm have been proved by the data collected from “www.ilvping.com”.Experimental results show that the new algorithm has a better performance and scalability,which can be better to solve the problems of big data and sparse matrix,and meet the requirement of high percentage shot and personalization.

Hadoop;tourist attractions recommendation;collaborative filtering;Mahout;Item-based;Slope One

2015-06-21

2015-09-23

時間：2016-02-18

國家自然科學基金資助項目(71473114)

馬騰騰(1992-)，女，碩士研究生，研究方向為互聯網用戶行為分析；朱慶華，教授，博士生導師，研究方向為互聯網用戶行為分析；曹菡，教授，博士生導師，研究方向為并行計算與大數據處理、GIS與智慧旅游。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1634.060.html

TP393

A

1673-629X(2016)03-0047-06

10.3969/j.issn.1673-629X.2016.03.012