基于標(biāo)簽和云模型的協(xié)同過濾算法

雷建云，何　順，李白楊

(1 中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074；2 云南大學(xué) 軟件學(xué)院，昆明 650500)

?

基于標(biāo)簽和云模型的協(xié)同過濾算法

雷建云1，何順1，李白楊2

(1 中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074；2 云南大學(xué) 軟件學(xué)院，昆明 650500)

引入云模型改進基于標(biāo)簽的用戶相似性和資源相似性度量方法，進而提出了基于標(biāo)簽和云模型的協(xié)同過濾算法.通過在MovieLens數(shù)據(jù)集上的實驗表明：改進后的算法在precision, recall和F1-measure三個指標(biāo)上均取得較好的推薦效果，推薦效率均優(yōu)于傳統(tǒng)的方法.

標(biāo)簽；協(xié)同過濾；云模型；相似性

冷啟動和數(shù)據(jù)稀疏性[1]是推薦系統(tǒng)面臨的重要問題，也是研究的熱點.自進入Web2.0時代以來，用戶可以根據(jù)自己的理解和喜好自由選擇和添加標(biāo)簽.研究表明標(biāo)簽可以用于Blogs分類[2]，信息檢索領(lǐng)域[3,4]和推薦系統(tǒng)[5].為了降低冷啟動和數(shù)據(jù)稀疏性對于協(xié)同過濾推薦性能的影響[6]，將傳統(tǒng)協(xié)同過濾算法擴展為基于標(biāo)簽的協(xié)同過濾算法.文獻[7]首次將標(biāo)簽信息引入?yún)f(xié)同過濾算法中，利用標(biāo)簽標(biāo)注情況擴展了用戶資源評分矩陣，一定程度上提高了推薦的效果.文獻[8]將標(biāo)簽信息融入到基于模型的協(xié)同過濾算法中，對于稀疏數(shù)據(jù)和冷啟動問題獲得較好的推薦效果.文獻[9]提出一種基于標(biāo)簽語義相似度度量方法，相似性度量借助普林斯頓大學(xué)心理學(xué)家、語言學(xué)家和計算機工程師聯(lián)合開發(fā)的基于認(rèn)知學(xué)的英語詞典WordNet，提高了最近鄰選擇的準(zhǔn)確度，但其準(zhǔn)確度依賴于詞典.基于標(biāo)簽的相似性計算大多采用統(tǒng)計方法，通過標(biāo)簽對用戶或資源的關(guān)聯(lián)度求得[10-12].云模型是處理定性概念與定量描述的不確定轉(zhuǎn)換模型，本文將云模型引入基于標(biāo)簽的協(xié)同過濾算法中，利用量化的標(biāo)簽關(guān)聯(lián)度，計算用戶或項目之間的定性概念相似度，提出基于標(biāo)簽和云模型的協(xié)同過濾算法.

1　基于標(biāo)簽和云模型的協(xié)同過濾算法

云模型是實現(xiàn)定性概念與定量數(shù)值之間不確定性轉(zhuǎn)換的數(shù)學(xué)模型[13,14].由于其良好的數(shù)學(xué)性質(zhì),可以表示自然科學(xué)、社會科學(xué)中大量的不確定現(xiàn)象.每個云由很多云滴組成，(Ex,En,He)表示云的數(shù)字特征,分別是云期望、云熵和云超熵[14].

1.1改進的標(biāo)簽關(guān)聯(lián)度度量

使用TF-IDF思想的關(guān)聯(lián)度計算方法是一種統(tǒng)計型計算，計算時認(rèn)為每個標(biāo)簽視為孤立的，即每個特征關(guān)聯(lián)度向量是正交的、不相關(guān)的，但是實際上標(biāo)簽之間存在一定的語義關(guān)系，例如“教材”和“課本”兩個標(biāo)簽是存在一定語義關(guān)系的.本文借鑒文本挖掘中AlessRB的TF-IWF[15]思想提出新的關(guān)聯(lián)度計算方法.

1)用戶標(biāo)簽關(guān)聯(lián)度.

已知用戶集合U={u1,u2,…，un}，標(biāo)簽集合T={t1,t2，…，tm}，任意標(biāo)簽tk(k=1,2,…,m)與任意用戶ui(i=1,2,…,n)的關(guān)聯(lián)度計算方法為：

(1)

其中N(ui,tk)表示用戶ui使用標(biāo)簽tk的次數(shù),N(ui,t)表示用戶ui使用的所有標(biāo)簽的總次數(shù)，N(Utj)表示所有用戶使用標(biāo)簽tj的總次數(shù).

2)資源標(biāo)簽關(guān)聯(lián)度.

已知資源集S={s1,s2,…,sp}, 標(biāo)簽集合T={t1,t2,…,tm}，任意標(biāo)簽tk(k=1,2,…,m)對于任意資源si(i=1,2,…,p)關(guān)聯(lián)度計算公式如下:

(2)

其中N(si,tk)表示資源si被標(biāo)注為標(biāo)簽tk的次數(shù)，N(Stk)表示資源集被標(biāo)注為標(biāo)簽tk的總次數(shù).

1.2基于標(biāo)簽的云相似性度量

1) 用戶標(biāo)簽云相似度.

(3)

2)資源標(biāo)簽云相似度.

(4)

1.3基于標(biāo)簽和云模型的相似性度量

為更準(zhǔn)確地度量用戶或資源的相似性，將表征用戶或資源的標(biāo)簽信息所表示的定性概念相似度即云相似度與基于標(biāo)簽關(guān)聯(lián)度計算的相似度，通過引入權(quán)重因子λ進行加權(quán)組合，λ用于反映兩種相似度對最終相似度的貢獻，設(shè)定λ的取值為(0,1).計算方法見公式(5)和公式(6).

simui,uj(w,c)=(1-λ)simui,uj(w)+λsimui,uj(c),

(5)

(5)式為基于標(biāo)簽和云模型的用戶相似性度量方法，其中simui,uj(w)是基于改進標(biāo)簽關(guān)聯(lián)度公式(1)計算的用戶相似度，simui,uj(c)為用戶標(biāo)簽云相似度，計算參照公式(3).

simsi,sj(w,c)=(1-λ)simsi,sj(w)+λsimsi,sj(c),

(6)

(6)式為基于標(biāo)簽和云模型的資源相似性度量方法，其中simsi,sj(w)是基于改進標(biāo)簽關(guān)聯(lián)度公式(2)計算的資源相似度，simsi,sj(c)為資源標(biāo)簽云相似度，計算參照公式(4).

1.4基于標(biāo)簽和云模型的協(xié)同過濾算法描述

根據(jù)上面提出的基于標(biāo)簽和云模型的相似性度量方法，提出新的基于標(biāo)簽和云模型的協(xié)同過濾算法，算法描述如下.

算法1.基于標(biāo)簽和云模型的協(xié)同過濾算法.

輸入：用戶-標(biāo)簽-資源記錄，參數(shù)λ，目標(biāo)用戶u，用戶最近鄰數(shù)K，推薦的資源數(shù)N.

輸出：目標(biāo)用戶u的TOP-N資源推薦.

方法：

1) 統(tǒng)計用戶-標(biāo)簽-資源記錄文件中每個用戶對于每個標(biāo)簽的使用頻度信息(或每個資源被標(biāo)注為每個標(biāo)簽的次數(shù)信息)；

2) 使用公式(1)計算用戶標(biāo)簽關(guān)聯(lián)度信息，得到用戶標(biāo)簽關(guān)聯(lián)度矩陣(或使用公式(2)計算資源標(biāo)簽關(guān)聯(lián)度信息，得到資源標(biāo)簽關(guān)聯(lián)度矩陣)；

3) 根據(jù)關(guān)聯(lián)度向量計算用戶相似性simu(w)(或計算資源相似性sims(w));

4) 使用公式(3)計算用戶標(biāo)簽云相似性simu(c)(或者使用公式(4)計算資源云相似性sims(c));

5) 將λ代入公式(5)計算用戶基于標(biāo)簽和云模型的相似度simu(w,c)(或結(jié)合公式(6)計算資源基于標(biāo)簽和云模型的相似度sims(w,c));

6) 重復(fù)3)，4)，5)計算得到相似度矩陣Matrixsim；

7) 計算資源興趣度，產(chǎn)生TOP-N推薦列表.

2　實驗及分析

2.1實驗數(shù)據(jù)集

實驗采用的數(shù)據(jù)集由GroupLens站點提供的MovieLens數(shù)據(jù)集，它由美國 Minnesota 大學(xué)計算機科學(xué)與工程學(xué)院的 GroupLens 項目組創(chuàng)辦，該數(shù)據(jù)集有多個版本，本實驗選擇MovieLens 20M作為實現(xiàn)對象，該數(shù)據(jù)集包括138000個用戶，27000部電影和465000個標(biāo)簽記錄.為保證實驗的穩(wěn)定性，對數(shù)據(jù)集進行了預(yù)處理.實驗最終選取的數(shù)據(jù)集包含2606個用戶，1278部電影和2636個標(biāo)簽.為保證實驗結(jié)果的準(zhǔn)確性，排除其他偶然因素的影響，本文將數(shù)據(jù)集隨機劃分為兩部分，從每個用戶標(biāo)注過的電影集中選取80%作為訓(xùn)練數(shù)據(jù)，另外20%作為測試數(shù)據(jù).

2.2評價標(biāo)準(zhǔn)

推薦的準(zhǔn)確度是評價推薦算法的最基本的指標(biāo).本文采用的評價指標(biāo)包括準(zhǔn)確率(precision)、召回率(recall)和F1-measure[16].準(zhǔn)確率表示用戶對推薦系統(tǒng)推薦資源感興趣的概率.召回率表示一個用戶喜歡的商品被推薦的概率.準(zhǔn)確率和召回率越高，表示推薦效果越好.F1-measure綜合了準(zhǔn)確率和召回率的結(jié)果，當(dāng)F1-measure較高時則說明實驗方法比較理想.設(shè)R(u)是根據(jù)用戶在訓(xùn)練集上的行為給用戶做出的推薦列表，T(u)是用戶在用戶測試集上的行為列表.那么推薦結(jié)果的準(zhǔn)確率為：

(7)

推薦結(jié)果的召回率計算公式如下：

(8)

F1-measure定義為：

(9)

2.3實驗結(jié)果

實驗1 將推薦列表的長度N設(shè)為10，實驗中設(shè)置的最近鄰數(shù)目K從10 開始，依次增加，增至80.實驗對比文獻[7]和文獻[11]中的方法，分別比較基于用戶的協(xié)同過濾算法和基于資源的協(xié)同過濾算法.文獻[7]，[11]中基于用戶的協(xié)同過濾算法分別記為UTCF，UTTCF，基于資源的協(xié)同過濾算法分別記為ITCF，ITTCF.基于本文中改進關(guān)聯(lián)度計算的用戶協(xié)同過濾算法和資源協(xié)同過濾算法分別記為UTMCF和ITMCF.基于本文提出的標(biāo)簽云相似性的用戶協(xié)同過濾算法和資源協(xié)同過濾算法分別記為UTCCF和ITCCF.實驗結(jié)果如表1～4所示.

從表1～4的實驗結(jié)果值可以看出，對比同類型的協(xié)同過濾算法，基于改進關(guān)聯(lián)度的協(xié)同過濾算法(UTMCF，ITMCF)和基于標(biāo)簽云相似度的算法(UTCCF，ITCCF)的推薦質(zhì)量均有一定程度提高，優(yōu)于文獻[7]和文獻[11]的方法.實驗可發(fā)現(xiàn)，隨著最近鄰數(shù)量的增加，推薦的質(zhì)量并不是一直增加，而是增大到某一值后逐漸減小的.其中在基于用戶的協(xié)同過濾算法中算法UTMCF在最近鄰為50時取得較好的推薦效果，在基于資源的協(xié)同過濾算法中算法ITMCF的precision值和recall值均較好些，且在最近鄰數(shù)為60時取得較優(yōu)的推薦效果.基于標(biāo)簽云相似度的算法UTCCF和ITCCF比文獻[7]和[11]均有一定程度提高，但效果低于基于改進關(guān)聯(lián)度的協(xié)同過濾算法.

表14種基于用戶的協(xié)同過濾算法的precision值

Tab.1Precision of four kinds of user-based collaborative filtering algorithm

KprecisionUTCFUTTCFUTMCFUTCCF100.065480.111580.113530.11331200.076300.112310.116560.11450300.086470.112770.118830.11634400.091340.113960.120670.11872500.092430.114940.121210.11883600.092210.114180.119370.11753700.091340.114090.118750.11677800.090480.113880.118720.11522

表2　4種基于用戶的協(xié)同過濾算法的recall值

表3　4種基于資源的協(xié)同過濾算法的precision值

表4　4種基于資源的協(xié)同過濾算法的recall值

實驗2將推薦列表的長度N設(shè)為10，最近鄰數(shù)目K從10 開始，依次增加，增至80.基于標(biāo)簽和云模型協(xié)同過濾算法中λ為設(shè)定調(diào)節(jié)兩種來源相似性的權(quán)重因子，選擇合適λ值將影響推薦的精度，實驗中將λ的值設(shè)為從0.1到0.9，每次增加0.1，分別測試λ對推薦結(jié)果的影響.對應(yīng)的基于用戶的協(xié)同過濾算法和基于資源的協(xié)同過濾算法分別記為UWTCF和IWTCF.

實驗發(fā)現(xiàn)算法UWTCF對于不同的λ值，在最近鄰數(shù)K=50時均取得較好推薦效果.當(dāng)K=50時，隨著λ的變化，算法UWTCF的F1-measure變化如圖1所示；算法IWTCF對于不同λ值，在最近鄰K=60時均取得較好推薦效果.當(dāng)K=60時，隨著λ的變化算法IWTCF的F1-measure指標(biāo)變化如圖2所示.圖1中算法UWTCF(K=50)對應(yīng)的F1-measure的變化曲線可以看出，當(dāng)λ=0.2時算法的推薦性能是較好的；當(dāng)λ的值大于0.2時F1-measure的值逐漸減小.從圖2中算法IWTCF(K=60)對應(yīng)的F1-measure的變化曲線可以看出，當(dāng)λ=0.5時算法的推薦性能是較好的，隨著λ取值大于0.5，F(xiàn)1-measure的值也逐漸減小.

λ圖1　λ對算法UWTCF(K=50)F1-measure的影響Fig.1　The effect of λ on the F1-measure of UWTCF (K=50)

λ圖2　λ對算法IWTCF(K=60)F1-measure的影響Fig.2　The effect of λ on the F1-measure of IWTCF(K=60)

為驗證算法的有效性，在同等數(shù)據(jù)集的基礎(chǔ)上，UWTCF對比實驗1中本文所提算法UTMCF，UTCCF，IWTCF對比算法ITMCF，ITCCF.將算法UWTCF中參數(shù)λ設(shè)置為0.2，IWTCF算法中參數(shù)λ設(shè)為0.5.

從表5可以看出3種基于用戶的協(xié)同過濾算法均在最近鄰數(shù)K=50時，取得較大的準(zhǔn)確率(precision)和召回率(recall).實驗發(fā)現(xiàn)最近鄰數(shù)量較少時，不足以充分挖掘出與目標(biāo)用戶相似的用戶.最近鄰數(shù)量較大時，因為考慮了一些相似性較低的

用戶，使得推薦的資源產(chǎn)生誤差，進而影響到推薦質(zhì)量.雖然伴隨著最近鄰數(shù)量的變化，算法UWTCF(λ=0.2)準(zhǔn)確率和召回率也在變動，但是推薦效果總是較優(yōu)的.

表53種基于用戶的協(xié)同過濾算法的precision和recall

Tab.5Precision and recall of three kinds of user-based collaborative filtering algorithm

KprecisionUTMCFUTCCFUWTCFrecallUTMCFUTCCFUWTCF100.113530.113310.115370.061680.061560.06268200.116560.114500.118290.063330.062210.06427300.118830.116340.124350.064560.063210.06756400.120670.118720.125320.065560.064500.06809500.121210.118830.126080.065860.064560.06850600.119370.117530.124350.064860.063860.06756700.118750.116770.120780.064520.063440.06562800.118720.115220.118750.064500.062850.06452

表6中3種基于資源的協(xié)同過濾算法推薦性能指標(biāo)隨著最近鄰數(shù)量的增加，先增大后減少，算法IWTCF(λ=0.5)總是能取得較好的推薦效果，且在最近鄰數(shù)K=60時，推薦效果最佳.

表63種基于資源的協(xié)同過濾算法的precision和recall

Tab.6Precision and recall of three kinds of item-based collaborative filtering algorithm

KprecisionITMCFITCCFIWTCFrecallITMCFITCCFIWTCF100.114610.110280.123590.062270.059920.06715200.114390.113640.124890.062150.061510.06785300.115580.114070.125430.062800.062280.06815400.120350.116880.125000.065380.063500.06791500.121000.117750.126840.065740.063970.06891600.123160.119910.128030.066910.065150.06956700.121860.118510.127160.066210.064390.06909800.119910.118030.126280.065150.064020.06855

從表5和表6 中可以看出算法UWTCF(λ=0.2)和算法IWTCF(λ=0.5)分別在最近鄰數(shù)為50和60時取得較好的推薦效果.同類型算法在同等的最近鄰數(shù)目下的F1-measure取值對比，如圖3和圖4所示.

圖3　K=50時，同類型基于用戶的協(xié)同過濾算法的F1-measureFig.3　When K=50, the same type of user-based collaborative filtering algorithm in F1-measure

從圖3和圖4可以看出，算法UWTCF，IWTCF在同類型算法中F1-measure的值均較大，即具有更好的推薦效果.

圖4　K=60時，同類型基于資源的協(xié)同過濾算法的F1-measureFig.4　When K=60, the same type of item-based collaborative filtering algorithm in F1-measure

綜上所述，本文所提基于標(biāo)簽和云模型的協(xié)同過濾算法比其他兩種改進方案在一定程度上具有更好的推薦效果，通過權(quán)重因子λ加權(quán)標(biāo)簽信息所表示的云相似性與基于標(biāo)簽關(guān)聯(lián)度計算的相似度更能準(zhǔn)確挖掘相似用戶或相似資源，實驗表明本文所提方案在準(zhǔn)確率(precision)，召回率(recall)和F1-measure三個指標(biāo)上均取得較優(yōu)值，更能準(zhǔn)確發(fā)現(xiàn)用戶感興趣的資源，更好地進行個性化推薦.

3　結(jié)束語

本文首先介紹了基于標(biāo)簽的協(xié)同過濾算法，對算法中常用的相似性度量方法進行簡單介紹，提出改進的標(biāo)簽關(guān)聯(lián)度計算方法；然后將云模型引入到基于標(biāo)簽的協(xié)同過濾算法中，考慮用戶或資源間的標(biāo)簽所提供的定性信息，提出云相似性計算方法，并從基于用戶和基于資源兩個角度，提出基于標(biāo)簽和云模型的協(xié)同過濾算法.通過實驗對比同類型算法并結(jié)合3種評價指標(biāo)，結(jié)果表明本文提出的方案均能取得較好的推薦質(zhì)量和效果.

[1]雷建云,何順,王淑娟. 一種改進的基于用戶項目喜好的相似度度量方法[J]. 中南民族大學(xué)學(xué)報(自然科學(xué)版),2015(4):94-97.

[2]Brooks B C H, Montanez N. An analysis of the effectiveness of tagging in blogs, in: Computation Approaches to Analyzing Weblogs. Papers from the 2006 AAAI[J]. Ultramicroscopy, 2012, 23(2):234.

[3]Lamere P. Social tagging and music information retrieval[J]. Journal of New Music Research, 2008, 37(2):101-114.

[4]Morrison P J. Tagging and searching: search retrieval effectiveness of folksonomies on the World Wide Web[J]. Information Processing & Management, 2008, 44(4): 1562-1579.

[5]Kim H N, Ji A T, Ha I, et al. Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation[J]. Electronic Commerce Research & Applications, 2010, 9(1):73-83.

[6]Huang C L, Lin C W. Collaborative and content-based recommender system for social bookmarking Website[J]. World Academy of Science Engineering & Technology, 2010(68):748.

[7]Tso-Sutter K H L, Marinho L B, Schmidt-Thieme L. Tag-aware recommender systems by fusion of collaborative filtering algorithms[C]//ACM.Proceedings of the 2008 ACM symposium on Applied computing. New York: ACM, 2008: 1995-1999.

[8]Zhen Y, Li W J, Yeung D Y. TagiCoFi: tag informed collaborative filtering[C]// ACM.ACM Conference on Recommender Systems. New York: ACM, 2009:69-76.

[9]Zhao S, Du N, Nauerz A, et al. Improved recommendation based on collaborative tagging behaviors[C]//ACM.Proceedings of the 2008 International Conference on Intelligent User Interfaces.New York:ACM, 2008:413-416.

[10]蔡強,韓東梅,李海生,等. 基于標(biāo)簽和協(xié)同過濾的個性化資源推薦[J]. 計算機科學(xué),2014,01:69-71,110.

[11]Huang C L, Yeh P H, Lin C W, et al. Utilizing user tag-based interests in recommender systems for social resource sharing websites[J]. Knowledge-Based Systems, 2014, 56(C):86-96.

[12]Larrain S, Trattner C, Parra D, et al. Good times bad times: a study on recency effects in collaborative filtering for social tagging[C]// ACM. ACM RecSys 2015. New York: ACM, 2015:269-272.

[13]李德毅, 劉常昱, 杜鹢,等. 不確定性人工智能[M].北京:國防工業(yè)出版社, 2014:123-128.

[14]李德毅, 劉常昱. 論正態(tài)云模型的普適性[J]. 中國工程科學(xué), 2004, 6(8):28-34.

[15]Aless R B, Moschitti A, Pazienza M T. A text classifier based on linguistic processing[C]//IJCAI. International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann,1999:163-168.

[16]Hao F, Zhong S. Tag recommendation based on user interest lattice matching[C]//IEEE. IEEE International Conference on Computer Science and Information Technology. Budapest: ICC,2010:276-280.

Collaborative Filtering Algorithm Based on Tag and Cloud Model

LeiJianyun1,HeShun1,LiBaiyang2

(1 College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China;2 College of Software,Yunnan University,Kunming 650500)

In order to use the tag information more accurately reflect the characteristics of users and resources, the cloud model was introduced to improve the user similarity and resource similarity measurement method based on tags,and a collaborative filtering algorithm based on tag and cloud model was proposed. Experiments on the MovieLens data set showed that the improved algorithm has better recommendation effects on three evaluation metrics which are precision, recall and F1-measure, the effectiveness of the recommendation is better than traditional method.

tag; collaborative filtering; cloud model; similarity

2016-06-27

雷建云(1972-)，男，博士，教授，研究方向:信息安全,數(shù)據(jù)庫技術(shù)，E-mail: leijianyun@mail.scuec.edu.cn.

湖北省自然科學(xué)基金資助項目(2013CFB445)；中南民族大學(xué)研究生創(chuàng)新基金資助項目(2016sycxjj207)

TP393

A

1672-4321(2016)03-0117-06