張應(yīng)輝,李 雪

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110000)

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

張應(yīng)輝,李 雪

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110000)

在旅游領(lǐng)域中，旅游者常常在旅游前從互聯(lián)網(wǎng)上獲取所需信息，但是在線旅游業(yè)日益嚴(yán)重的信息過(guò)載現(xiàn)象，使得用戶不能得到他們想要的個(gè)性化信息。傳統(tǒng)的基于協(xié)同過(guò)濾的旅游推薦研究普遍都存在稀疏性和可擴(kuò)展性等問(wèn)題，基于知識(shí)的推薦研究有時(shí)因用戶無(wú)法表達(dá)清楚他們的需求而無(wú)法得到滿意的推薦。針對(duì)已有的旅游推薦算法存在的問(wèn)題，提出了一種基于模糊聚類的旅游推薦算法，為用戶推薦符合其需求和偏好的旅游產(chǎn)品。該算法利用標(biāo)簽構(gòu)建用戶偏好景點(diǎn)模型和景點(diǎn)特征屬性模型，對(duì)數(shù)據(jù)集進(jìn)行模糊聚類，同時(shí)提出新的相似度度量。在此基礎(chǔ)上，組合基于內(nèi)容和協(xié)同過(guò)濾技術(shù)進(jìn)行混合推薦。實(shí)驗(yàn)結(jié)果表明，該算法能顯著提高推薦系統(tǒng)的效率以及可擴(kuò)展性和準(zhǔn)確度。

個(gè)性化；標(biāo)簽；相似性度量；模糊聚類；混合推薦

0 引 言

旅游推薦算法[1-3]的研究是旅游領(lǐng)域研究的熱點(diǎn)。旅游網(wǎng)站不斷興起，推薦精度的高低直接影響用戶是否選擇預(yù)定該線路，影響用戶對(duì)該旅游網(wǎng)站信息的興趣度，興趣度的高低決定了用戶對(duì)該旅游網(wǎng)站的使用率。針對(duì)個(gè)性化旅游推薦[4-6]問(wèn)題，學(xué)者們進(jìn)行了深入研究。例如，基于協(xié)同過(guò)濾技術(shù)的旅游推薦研究[7]在一定程度上提高了推薦的多樣性，但是普遍都存在稀疏性和可擴(kuò)展性的問(wèn)題。基于知識(shí)的、會(huì)話式的旅游推薦[8]方式使用交互&個(gè)性化代理以會(huì)話的形式逐步發(fā)現(xiàn)用戶的偏好和需要，然后利用多屬性效用理論對(duì)推薦結(jié)果進(jìn)行排序，一定程度上提高了推薦的精確度。但此方法需要大量的領(lǐng)域知識(shí)和推理技術(shù)，需要考慮多方面的因素，有時(shí)用戶很難準(zhǔn)確地表達(dá)自己的需求，推薦效率緩慢。

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

1 相關(guān)定義

TRBFC算法在構(gòu)建用戶偏好景點(diǎn)模型時(shí)，主要考慮了用戶使用過(guò)的景點(diǎn)標(biāo)簽。當(dāng)用戶瀏覽旅游網(wǎng)站時(shí)，用戶喜歡的景點(diǎn)都會(huì)有相應(yīng)的標(biāo)簽，比如Tom喜歡的景點(diǎn)標(biāo)簽中經(jīng)常出現(xiàn)“主題”、“海邊”等短語(yǔ)，那么他可能喜歡主題游或海邊游，其中“主題”出現(xiàn)的頻率較高，Tom可能更喜歡此類景點(diǎn)。

定義1：如果系統(tǒng)中有q類景點(diǎn)標(biāo)簽，那么對(duì)用戶，通過(guò)TRBFC算法構(gòu)建的用戶景點(diǎn)偏好模型如式(1)所示：

(1)

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

定義2：如果系統(tǒng)中有q類景點(diǎn)標(biāo)簽，那么對(duì)于景點(diǎn)，通過(guò)TRBFC算法構(gòu)建的景點(diǎn)特征屬性模型如式(2)所示：

(2)

其中，aq表示標(biāo)簽q是否是景點(diǎn)si的標(biāo)簽。

(3)

其中，xij表示用戶ui使用標(biāo)簽ti的個(gè)數(shù)。

(4)

其中，yij表示景點(diǎn)si是否包含標(biāo)簽ti，包含則值為1，反之為0。

(5)

其中，rij表示用戶ui對(duì)景點(diǎn)si的評(píng)分。

評(píng)分值為[1,5]之間的整數(shù),評(píng)分值由高到低表明用戶對(duì)該景點(diǎn)興趣的高低。若未評(píng)分，則取值0。

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

(6)

其中，dti表示用戶ut對(duì)用戶ui偏好景點(diǎn)之間的距離；xij為定義3中矩陣B中用戶使用標(biāo)簽的頻率(即個(gè)數(shù))。

2 TRBFC算法的實(shí)現(xiàn)

由于一個(gè)景點(diǎn)可能擁有多個(gè)標(biāo)簽，可以屬于多個(gè)不同的類，所以首先采用模糊聚類的方法對(duì)用戶-標(biāo)簽數(shù)據(jù)集和景點(diǎn)-標(biāo)簽數(shù)據(jù)集進(jìn)行聚類，使相近的景點(diǎn)或用戶分為一組，其次組合基于內(nèi)容和協(xié)同過(guò)濾的推薦算法，按照一定的關(guān)系組合二者，進(jìn)行旅游景點(diǎn)的推薦。

首先對(duì)Oui進(jìn)行模糊聚類。

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

(2)用戶-標(biāo)簽隸屬度矩陣Uf的更新。用式(7)進(jìn)行更新：

(7)

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

(8)

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

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

同理可以對(duì)Isi模糊聚類后獲取景點(diǎn)-標(biāo)簽隸屬度矩陣I和景點(diǎn)-標(biāo)簽聚類中心矩陣Q。此處不再證明。

在此基礎(chǔ)上，推薦結(jié)果由基于內(nèi)容和協(xié)同過(guò)濾的混合推薦算法來(lái)推薦獲得。

(1)使用協(xié)同過(guò)濾方法對(duì)于目標(biāo)用戶ut的鄰居集N(ut)，結(jié)合式(5)給出的用戶評(píng)分矩陣R，對(duì)目標(biāo)用戶未選擇的景點(diǎn)做預(yù)測(cè)評(píng)分，如式(9)所示：

(9)

其中，rtw表示目標(biāo)用戶ut對(duì)景點(diǎn)w做的預(yù)測(cè)評(píng)分；dij的值應(yīng)該大于等于1。

得到預(yù)測(cè)評(píng)分后，按其高低把獲得預(yù)測(cè)評(píng)分最高的Top-K個(gè)項(xiàng)目放入一個(gè)集合M中。

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

(10)

其中，sim(a,si)是由景點(diǎn)si和類中其他景點(diǎn)a之間標(biāo)簽相同的個(gè)數(shù)比兩者標(biāo)簽總的個(gè)數(shù)所得。

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

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

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

3.1 數(shù)據(jù)來(lái)源

使用從途牛網(wǎng)中獲取的旅游景點(diǎn)信息進(jìn)行實(shí)驗(yàn)。在選取的整個(gè)數(shù)據(jù)集中，所有的景點(diǎn)數(shù)據(jù)為512，景點(diǎn)評(píng)分?jǐn)?shù)據(jù)為67 690，評(píng)分取[1,5]中的任意整數(shù)，評(píng)分值由高到低代表旅游者對(duì)該景點(diǎn)的滿意程度。在得到的數(shù)據(jù)集中，以用戶-標(biāo)簽矩陣為例，形式如表1所示。

3.2 評(píng)價(jià)指標(biāo)

訓(xùn)練集由隨機(jī)抽取50 000條景點(diǎn)評(píng)分組成，測(cè)試集由剩余的數(shù)據(jù)組成，分別用傳統(tǒng)的基于知識(shí)的旅游推薦、基于用戶的協(xié)同過(guò)濾方法和改進(jìn)算法進(jìn)行比較。采用準(zhǔn)確率和召回率作為評(píng)測(cè)標(biāo)準(zhǔn)。

表1 用戶-標(biāo)簽矩陣B

(11)

(12)

其中，Pu為準(zhǔn)確率；Ru為召回率；TMu為算法用戶推薦景點(diǎn)的集合；Tu為用戶在測(cè)試集上喜歡的景點(diǎn)的集合。

3.3 實(shí)驗(yàn)分析

圖1和圖2分別為傳統(tǒng)的基于知識(shí)推薦、協(xié)同過(guò)濾推薦和文中算法的準(zhǔn)確率測(cè)試和召回率測(cè)試。其中，U1是最終推薦景點(diǎn)數(shù)目為10的數(shù)據(jù)集，U2～U5分別是最終推薦景點(diǎn)數(shù)目為15、20、25、30的數(shù)據(jù)集，當(dāng)最終推薦景點(diǎn)數(shù)目達(dá)到30時(shí)，準(zhǔn)確率值上升緩慢，所以最終推薦景點(diǎn)數(shù)目不宜選擇過(guò)大。

圖1 準(zhǔn)確率測(cè)試

圖2 召回率測(cè)試

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

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)旅游推薦算法推薦效率不高的問(wèn)題，提出了一種模糊聚類方法，采用新的相似度度量，在一定程度上縮短了尋找用戶鄰居集和相似景點(diǎn)的時(shí)間，提高了效率和擴(kuò)展性。另外采用混合推薦技術(shù)，在一定程度上改善了推薦系統(tǒng)的稀疏性和冷啟動(dòng)問(wèn)題。

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

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

[3] 陳 梅.旅游信息智能推薦系統(tǒng)的研究與設(shè)計(jì)[D].貴陽(yáng):貴州大學(xué),2010.

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

[5] 安 維，劉啟華，張李義.個(gè)性化推薦系統(tǒng)的多樣性研究進(jìn)展[J].圖書(shū)情報(bào)工作，2013，57(20):127-135.

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

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

[8] 王顯飛，陳 梅，李小天.基于約束的旅游推薦系統(tǒng)的研究與設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展，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] 肖曼生,陽(yáng)姊蘭，張居武，等.基于模糊相關(guān)度的模糊C均值聚類加權(quán)指數(shù)研究[J].計(jì)算機(jī)應(yīng)用,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

時(shí)間：2016-11-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61262058)

張應(yīng)輝(1972-),男,副教授,碩士生導(dǎo)師,研究方向?yàn)橛?jì)算機(jī)圖像處理、機(jī)器學(xué)習(xí)；李 雪(1991-),女,碩士研究生,研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。

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