基于模糊聚類的旅游推薦算法

張應輝,李 雪

(東北大學 計算機科學與工程學院，遼寧 沈陽 110000)

基于模糊聚類的旅游推薦算法

張應輝,李 雪

(東北大學 計算機科學與工程學院，遼寧 沈陽 110000)

在旅游領域中，旅游者常常在旅游前從互聯網上獲取所需信息，但是在線旅游業日益嚴重的信息過載現象，使得用戶不能得到他們想要的個性化信息。傳統的基于協同過濾的旅游推薦研究普遍都存在稀疏性和可擴展性等問題，基于知識的推薦研究有時因用戶無法表達清楚他們的需求而無法得到滿意的推薦。針對已有的旅游推薦算法存在的問題，提出了一種基于模糊聚類的旅游推薦算法，為用戶推薦符合其需求和偏好的旅游產品。該算法利用標簽構建用戶偏好景點模型和景點特征屬性模型，對數據集進行模糊聚類，同時提出新的相似度度量。在此基礎上，組合基于內容和協同過濾技術進行混合推薦。實驗結果表明，該算法能顯著提高推薦系統的效率以及可擴展性和準確度。

個性化；標簽；相似性度量；模糊聚類；混合推薦

0 引 言

旅游推薦算法[1-3]的研究是旅游領域研究的熱點。旅游網站不斷興起，推薦精度的高低直接影響用戶是否選擇預定該線路，影響用戶對該旅游網站信息的興趣度，興趣度的高低決定了用戶對該旅游網站的使用率。針對個性化旅游推薦[4-6]問題，學者們進行了深入研究。例如，基于協同過濾技術的旅游推薦研究[7]在一定程度上提高了推薦的多樣性，但是普遍都存在稀疏性和可擴展性的問題?；谥R的、會話式的旅游推薦[8]方式使用交互&個性化代理以會話的形式逐步發現用戶的偏好和需要，然后利用多屬性效用理論對推薦結果進行排序，一定程度上提高了推薦的精確度。但此方法需要大量的領域知識和推理技術，需要考慮多方面的因素，有時用戶很難準確地表達自己的需求，推薦效率緩慢。

針對上述問題，提出一種基于模糊聚類[9-12]的旅游推薦算法(Tourism Recommendation algorithm Based on Fuzzy Clustering,TRBFC)，建立了新的用戶偏好景點模型[13-14]，提出了一種新的相似度計算方法，使用模糊聚類的方法對數據集進行聚類，在此基礎上，組合基于內容和協同過濾的技術進行混合推薦。該算法使得系統的推薦效率、可擴展性進一步提高，改善了系統的稀疏性，進一步提高了推薦的準確率。

1 相關定義

TRBFC算法在構建用戶偏好景點模型時，主要考慮了用戶使用過的景點標簽。當用戶瀏覽旅游網站時，用戶喜歡的景點都會有相應的標簽，比如Tom喜歡的景點標簽中經常出現“主題”、“海邊”等短語，那么他可能喜歡主題游或海邊游，其中“主題”出現的頻率較高，Tom可能更喜歡此類景點。

定義1：如果系統中有q類景點標簽，那么對用戶，通過TRBFC算法構建的用戶景點偏好模型如式(1)所示：

(1)

其中，pq表示標簽q被用戶ui使用的頻率(即次數)。

定義2：如果系統中有q類景點標簽，那么對于景點，通過TRBFC算法構建的景點特征屬性模型如式(2)所示：

(2)

其中，aq表示標簽q是否是景點si的標簽。

(3)

其中，xij表示用戶ui使用標簽ti的個數。

(4)

其中，yij表示景點si是否包含標簽ti，包含則值為1，反之為0。

(5)

其中，rij表示用戶ui對景點si的評分。

評分值為[1,5]之間的整數,評分值由高到低表明用戶對該景點興趣的高低。若未評分，則取值0。

定義6：歐氏距離。歐幾里德距離又叫歐氏距離，常用來計算兩個向量間的距離，并認為這是兩個向量的差距。TRBFC算法采用歐氏距離，如式(6)所示：

(6)

其中，dti表示用戶ut對用戶ui偏好景點之間的距離；xij為定義3中矩陣B中用戶使用標簽的頻率(即個數)。

2 TRBFC算法的實現

由于一個景點可能擁有多個標簽，可以屬于多個不同的類，所以首先采用模糊聚類的方法對用戶-標簽數據集和景點-標簽數據集進行聚類，使相近的景點或用戶分為一組，其次組合基于內容和協同過濾的推薦算法，按照一定的關系組合二者，進行旅游景點的推薦。

首先對Oui進行模糊聚類。

(1)基本參數初始化。聚類的最終類別個數c，2≤c0)；用戶-標簽頻率矩陣B；聚類中心矩陣V0和迭代次數計數器f=0。

(2)用戶-標簽隸屬度矩陣Uf的更新。用式(7)進行更新：

(7)

(3)用戶-標簽聚類中心矩陣Vf+1更新,使用式(8):

(8)

(4)如果‖Vf-Vf+1‖<θ,則算法停止并返回用戶-標簽隸屬度矩陣U和用戶-標簽聚類中心矩陣V,否則f=f+1,轉向步驟(2)進行迭代計算。

(5)對于目標用戶ut,根據隸屬度找到它所在的類別，把式(6)作為新的相似度度量，計算ut與其所在類別中其他用戶之間的相似度，按照相似度大小排序，排在最前面的N位即可作為目標用戶的鄰居集，記為N(ut)。

同理可以對Isi模糊聚類后獲取景點-標簽隸屬度矩陣I和景點-標簽聚類中心矩陣Q。此處不再證明。

在此基礎上，推薦結果由基于內容和協同過濾的混合推薦算法來推薦獲得。

(1)使用協同過濾方法對于目標用戶ut的鄰居集N(ut)，結合式(5)給出的用戶評分矩陣R，對目標用戶未選擇的景點做預測評分，如式(9)所示：

(9)

其中，rtw表示目標用戶ut對景點w做的預測評分；dij的值應該大于等于1。

得到預測評分后，按其高低把獲得預測評分最高的Top-K個項目放入一個集合M中。

(2)使用基于內容的方法，根據隸屬度判斷目標用戶ut正在查看的或者已經存在景點si所在的模糊類類別。si可能屬于多個類。利用式(10)計算目標用戶ut與所屬聚類類別中其他景點的相似性：

(10)

其中，sim(a,si)是由景點si和類中其他景點a之間標簽相同的個數比兩者標簽總的個數所得。

設置一個集合H，一個閾值β，當sim(a,si)>β，把景點si放入H中。對集合中的景點按相似度值大小排序。獲取top-N個景點的推薦集合，N的值取5。

(3)綜合集合M和H中的景點，兩個集合相交得到最終的景點推薦集合HM。

3 實驗結果及分析

3.1 數據來源

使用從途牛網中獲取的旅游景點信息進行實驗。在選取的整個數據集中，所有的景點數據為512，景點評分數據為67 690，評分取[1,5]中的任意整數，評分值由高到低代表旅游者對該景點的滿意程度。在得到的數據集中，以用戶-標簽矩陣為例，形式如表1所示。

3.2 評價指標

訓練集由隨機抽取50 000條景點評分組成，測試集由剩余的數據組成，分別用傳統的基于知識的旅游推薦、基于用戶的協同過濾方法和改進算法進行比較。采用準確率和召回率作為評測標準。

表1 用戶-標簽矩陣B

(11)

(12)

其中，Pu為準確率；Ru為召回率；TMu為算法用戶推薦景點的集合；Tu為用戶在測試集上喜歡的景點的集合。

3.3 實驗分析

圖1和圖2分別為傳統的基于知識推薦、協同過濾推薦和文中算法的準確率測試和召回率測試。其中，U1是最終推薦景點數目為10的數據集，U2～U5分別是最終推薦景點數目為15、20、25、30的數據集，當最終推薦景點數目達到30時，準確率值上升緩慢，所以最終推薦景點數目不宜選擇過大。

圖1 準確率測試

圖2 召回率測試

從兩圖中可以看出，與傳統的算法相比，數據模糊聚類后，混合推薦算法的推薦精度要高一些。

4 結束語

針對傳統旅游推薦算法推薦效率不高的問題，提出了一種模糊聚類方法，采用新的相似度度量，在一定程度上縮短了尋找用戶鄰居集和相似景點的時間，提高了效率和擴展性。另外采用混合推薦技術，在一定程度上改善了推薦系統的稀疏性和冷啟動問題。

[1]HwangS,YanW.On-tourattractionrecommendationinamobileenvironment[C]//IEEEconferenceonpervasivecomputingandcommunications.NewJersey:IEEEPress,2012.

[2]RicciF,RokachL,ShapiraB,etal.Recommendersystemhandbook[M].[s.l.]:Springer,2011.

[3] 陳 梅.旅游信息智能推薦系統的研究與設計[D].貴陽:貴州大學,2010.

[4]LiuQ,GeY,LiZM,etal.Personalizedtravelpackagerecommendation[C]//IEEEinternationalconferenceondatamining.NewJersey:IEEEPress,2011:407-416.

[5] 安 維，劉啟華，張李義.個性化推薦系統的多樣性研究進展[J].圖書情報工作，2013，57(20):127-135.

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

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

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

[9]ZenebeA,ZhouLina,NorcioAF.Userpreferencesdiscoveryusingfuzzymodels[J].FuzzySetsandSystems,2010,161:3044-3063.

[10]SrivastavaV,TripathiBK,PathakVK.AnevolutionaryfuzzyclusteringwithMurkowskidistances[C]//Proceedingsofthe2011internationalconferenceonneuralinformationprocessing.Shanghai,China:[s.n.],2011.

[11]ZhangChen,LiuBing.Possibilisticfuzzyclusteringalgorithmbasedonsampleweighted[C]//Proceedingsof3rdinternationalworkshoponintelligentsystemsandapplications.Wuhan,China:[s.n.],2011.

[12]TsaiDu-Ming,LinChung-Chan.FuzzyC-meansbasedclusteringforlinearlyandnonlinearlyseparabledata[J].PatternRecognition,2011,44(8):1750-1760.

[13]HuangWeidong,KhouryR,DawbornT,etal.WeBeVis:analyzinguserwebbehaviorthroughvisualmetaphors[J].ScienceChinaInformationSciences,2013,56(5):1-15.

[14]WuXiyuan,ZhengQinghua,WangPing.Aintelligentmethodofmodellingwebuserinterest[J].JournalofNewIndustrialization,2014(9):39-43.

[15] 肖曼生,陽姊蘭，張居武，等.基于模糊相關度的模糊C均值聚類加權指數研究[J].計算機應用,2010,30(12):3388-3390.

A Tourism Recommendation Algorithm Based on Fuzzy Clustering

ZHANG Ying-hui，LI Xue

(School of Computer Science and Engineering,Northeastern University,Shenyang 110000,China)

In the field of tourism,tourists often get the information they need on the Internet before traveling,but the phenomenon of information overload online in tourism industry is becoming more and more serious,so that personalized information cannot be obtained by users.The problems of sparsity and scalability exist in the traditional tourism recommendation algorithm based on collaborative filtering,and sometimes users can’t express their needs and can’t be satisfied with the recommendation based on the knowledge of the recommendations.For these problems,a tourism recommendation algorithm based on fuzzy clustering is proposed,which is used for the users to recommend the tourism products that meet their needs and preferences.Tags are used by the algorithm to build user’s preference models and sights feature attribute model,fuzzy clustering on them.A new similarity measure is proposed.On this basis,the combination of content-based and collaborative filtering technology is recommended.Experimental results show that the proposed algorithm can significantly improve the efficiency,scalability and accuracy of the recommendation system.

individualization;tags;similarity measurement;fuzzy clustering;hybrid recommendation

2016-06-03

2016-09-08

時間：2016-11-22

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

張應輝(1972-),男,副教授,碩士生導師,研究方向為計算機圖像處理、機器學習；李 雪(1991-),女,碩士研究生,研究方向為數據挖掘、機器學習。

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

TP301.6

A

1673-629X(2016)12-0099-04

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