基于綜合相似度和社交標簽的推薦算法①

時念云,張 蕓,馬 力

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

基于綜合相似度和社交標簽的推薦算法①

時念云,張 蕓,馬 力

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

針對傳統個性化推薦方法所面臨的冷啟動、數據稀疏等問題,本論文結合了項目組的前期研究,在綜合考慮用戶特征和用戶信任度的基礎上,引入了用戶興趣,形成綜合相似度.針對目前推薦系統中評分數據較少的問題,論文結合了社交標簽,豐富了推薦數據.首先利用綜合相似度,找到用戶的相似近鄰,并將相似近鄰所標注的標簽形成一個標簽集.其次利用基于標簽的推薦算法,產生最終的推薦列表.實驗結果表明,該算法能夠有效提高推薦的準確率和召回率.

用戶特征; 信任度; 冷啟動; 用戶興趣; 社交標簽

隨著互聯網與信息技術的高速發展,人們已逐漸從信息匱乏時代進入到信息過載時代[1].推薦系統[2]的出現使人們能夠快速找到自己感興趣的資源.然而目前的推薦系統多是根據用戶對資源或商品的評分進行相關推薦.研究顯示在商業推薦系統中,用戶的評分密度小于1%,造成可用于推薦的數據較稀疏,致使推薦的準確率大大降低[3].同時,大部分推薦系統需要通過分析用戶歷史數據,預測用戶興趣進行相關推薦,而對于新用戶,推薦系統沒有其歷史數據,因此無法預測其興趣,即推薦系統存在冷啟動問題[4,5].可以說數據稀疏和冷啟動是影響當前推薦系統準確率的兩個重要因素[6].

隨著Web2.0的發展,社交網站進入人們的生活,如微博和QQ等,同時也產生了豐富的標簽數據和其他特征信息數據,將標簽應用到推薦系統已成為新的研究方向.標簽可以作為聯系用戶興趣和物品的重要媒介,通過將標簽集這個含有大量特征信息的數據應用到推薦系統中,在一定程度上緩解了用戶物品評分矩陣的數據稀疏問題,提高了推薦質量[7].

近些年,為了解決目前推薦系統面臨的上述問題,學者們提出了各種解決方法如:混合推薦、信任機制等.文獻[8,9]中,利用了社交標簽、信任關系等來做社會化推薦,以緩解目前推薦系統所面臨的數據稀疏問題.文獻[10-12]中,針對推薦系統中存在的冷啟動問題,利用了簡單的用戶和項目的屬性信息,為新用戶和新項目進行預測推薦.文獻[13,14]只考慮了用戶或項目間的相似性,忽略了用戶的興趣相似性.文獻[15]針對用戶評分數據較少的問題,提出了利用協同過濾與社交網絡相結合的混合推薦算法,充分利用了標注書簽和朋友關系信息,在一定程度上解決了數據稀疏問題.在文獻[16]提出的算法中,利用用戶已聲明的信任用戶來構建信任網絡,并結合用戶評分相似度產生推薦,提高了推薦的準確率.文獻[17]針對傳統基于標簽的推薦存在的覆蓋率不足問題,提出了利用用戶信任度和社交用戶標注動機相結合的推薦算法.該算法考慮了用戶標注動機,在一定程度上提高了推薦的覆蓋率.文獻[18]針對傳統協同過濾算法存在的冷啟動問題,提出了引入人口統計特征和信任機制的協同過濾推薦算法.該算法充分利用了用戶的人口統計特征信息和信任關系,在一定程度上緩解了冷啟動問題.

這些算法雖然在一定程度上緩解了數據稀疏和冷啟動問題,但仍存在一定的不足,如文獻[15]沒有考慮用戶間信任關系,準確率不高.文獻[16]和文獻[18]仍然存在評分數據稀疏問題.文獻[17]沒有考慮冷啟動問題和用戶興趣相似問題.而且這些算法沒有充分利用含有豐富特征信息的標簽數據,同時,缺乏對用戶興趣和用戶信任度等的綜合考慮.事實上,在現實生活中,來自朋友的推薦有時會具有更高可信度,并且與自己背景相同的人興趣相似的可能性更大,而這種現實關系通常也體現在社交網絡中.

用戶特征含有豐富的用戶信息,且社交標簽數據較為豐富,增大了用于推薦的數據量,本文提出的算法將兩者合理結合,有效緩解了冷啟動和數據稀疏問題.同時,將用戶信任關系和用戶興趣考慮進來,有助于準確找到用戶信任且與其興趣相同的用戶,提高推薦的準確率,減少盲目性.

1 基于綜合相似度和社交標簽的推薦算法

基于綜合相似度和社交標簽的推薦算法步驟如下.(1)計算用戶特征、用戶信任度和用戶興趣相似度,作為綜合相似度.(2)根據綜合相似度找到相似近鄰,并利用相似近鄰的標簽形成標簽集.(3)與社交標簽相結合,利用基于標簽的推薦算法產生推薦列表.

1.1 用戶特征

用戶特征即指人的年齡、性別、工作、學歷、居住地和國籍等,即一般情況下用戶注冊時需要填寫的信息[19].而這些特征對預測用戶興趣有很重要的作用,比如男性和女性的興趣不同,不同年齡的人興趣不同.Krulwhich設計了一個AB實驗,其中一組利用用戶特征推薦,而另一對照組則是利用完全隨機推薦.實驗結果顯示,前者的用戶點擊率為89%,而隨機算法的點擊率只有27%.實驗證明,利用用戶特征推薦相對隨機推薦能夠獲得更好的推薦效果[20].

本文中用到的Last.fm數據集包含了較多的用戶特征,包括用戶的性別、年齡和國籍等.據統計該數據集中男性用戶約占3/4.數據集中用戶年齡分布主要集中在20～25歲,而在0～13歲和60～100的用戶相加不足1%,為提高推薦效率,我們暫不考慮.該數據集中用戶主要集中在美國、德國和英國.

本文只對Last.fm數據集中用戶的年齡、性別和國家等用戶特征進行用戶相似度度量.由于數據集中用戶信息大多不是數值型,因此要對用戶特征進行量化或轉化為數值型,以方便計算[19].其中對國籍量化方法如下.

數據集中用戶分布較多的有30個國家.這30個國家約占了用戶的98%.將這30個國家分為30類,并利用1-30的數字作為量化值.

通過以上對數據集中用戶的用戶特征進行量化,形成了用戶-特征矩陣,如表1所示.

表1 用戶-特征矩陣

其中Ui為第i個用戶,Fj為第j個用戶特征.Pij表示第i個用戶的第j個用戶特征值.用戶特征相似度計算方法公式如下.

因為不同用戶特征對用戶興趣的影響程度不同,所以本文賦予特征相似度不同權值.公式如下:

其中SFp(a,b)為用戶a與用戶b的性別特征相似度,SFq(a,b)為用戶a與用戶b的年齡特征相似度,SFr(a,b)為用戶a與用戶b的國家特征相似度.其中,α∈[0,1],β∈[0,1],θ∈[0,1],且α+β+θ=1.

1.2 用戶興趣相似度

在社交網絡中,用戶興趣相似度對推薦準確率影響較大.例如,我們每個人大都和自己的父母很熟悉,但是很多時候我們發現自己和父母的興趣卻極不相似,那么他們喜歡的物品就與我們有很大不同.因此在度量用戶的綜合相似度時還需要考慮用戶興趣相似度,而用戶興趣相似度跟兩個用戶喜歡物品集合的重合度有關.物品集合的重合度越高,則說明兩個用戶的興趣相似度越高.

傳統的用戶興趣相似度算法對于熱門物品的影響沒有處理.為了減小熱門物品對推薦的影響,以減小用戶u和用戶v共同興趣以及列表中熱門物品對他們相似度的影響.本文采用了John S.Breese[21]提出的用戶興趣相似度計算公式,公式如下:

N(u)為用戶u喜歡的物品集,N(v)為用戶v喜歡的物品集,N(i)為用戶u和用戶v共同喜歡的物品集.

本文將以上用戶特征相似度與用戶興趣相似度相結合,計算公式如下:

1.3 信任度度量

信任關系指在社交網站中,用戶通過綜合考慮自身與其他目標用戶的歷史記錄及表現,主觀判斷其他目標用戶在網絡上所推薦信息和分享的資源是否真實安全,為用戶自身購物提供一定的實際參考價值.用戶對不同目標用戶這種信任程度即信任度.信任度也是信任關系的量化.信任度又分為全局信任度和局部信任度[22].

全局信任度即指在整個系統中所有其他用戶對某一用戶的總體信任程度.在推薦系統中,用戶越活躍且信任他的用戶越多即信譽值越高,那么他在系統中的全局信任度則越高.本文將用戶活躍度和用戶信譽值作為全局信任度.

在社交標簽系統中,用戶活躍度與用戶所標注標簽個數成正相關,用戶在系統中,所標注標簽越多則其活躍度越高[23].用戶活躍度公式如下:

其中,Act∈[0,1],q為用戶對所有項目所標注標簽數量,閾值Q為小于最活躍用戶的標簽數量和.

用戶信譽值即用戶在社交網絡中,其他用戶對該用戶的整體信任值表現為用戶節點的度[24].

其中,fi為節點i的度,fmax為信任網絡中節點的最大度,且 Ucti∈[0,1].

用戶活躍度Act和用戶信譽值Ucti綜合計算公式如下:

本文采用基于節點相似性方法中的Jaccard系數作為局部信任度度量方法[25].基于節點相似性方法大部分來源于復雜網絡的鏈接預測,該類方法把共同鄰居或兩端節點度作為考慮屬性,其中較著名的有共同鄰居法和Jaccard系數法,共同鄰居方法(CN)公式如下:

Jaccard系數方法通過對兩個用戶物品集進行操作,消除了物品集大小程度對用戶相似性的影響.

用戶在系統中的信任度是其全局信任度和局部信任度加權之和,公式如下:

將上述得到的用戶相似度和用戶信任度進行融合[18],公式如下:

1.4 組合推薦模型

通過利用以上方法計算出綜合相似度后,找到目標用戶的相似近鄰,并利用他們所使用的標簽形成標簽集,其次利用TF-IDF公式進行推薦.TF-IDF是一種用于資訊檢索與資訊探勘的常用加權技術,這個公式利用用戶的標簽向量對用戶興趣進行建模,其中每個標簽都被用戶使用過,而標簽權重是用戶使用該標簽的次數[26].這種建模方法的缺點是給熱門標簽過大的權重,從而不能反映用戶的個性化興趣.因此,為了減小熱門標簽的權重,對熱門物品進行了懲罰,推薦公式如下:

其中nu,b是用戶u打過標簽b的次數,nb,i是物品i被打過標簽b的次數,記錄了物品i被多少個不同用戶打過標簽.本文算法記為TFI-TP.

本文總的算法思想為:通過計算綜合相似度找到目標用戶信任且用戶特征和興趣相同的相似近鄰,并利用他們對歌唱藝術家所打標簽形成標簽集,通過利用標簽推薦方法將目標用戶可能喜歡的歌手形成最終推薦列表,推薦給目標用戶.

2 實驗結果及其分析

2.1 數據集

本文使用的數據來源于Last.fm數據集,該數據集包含了2100個用戶的18萬條信息,18745名歌手,11947個標簽.平均每個用戶有12.5個朋友,有13個標簽.Last.fm是一個著名的音樂網站.為了更好地服務用戶,在不進行復雜音頻分析的情況下獲取音樂內容,并為用戶快速找到其可能喜歡的歌手,Last.fm引入了UGC標簽系統,方便用戶利用標簽標記歌手.實驗將隨機選取數據集的90%作為訓練集,10%作為測試集.

2.2 度量標準

本文采用推薦系統常用的評測指標即準確率和召回率[27].準確率是檢索出相關文檔數與檢索出的文檔總數的比率,衡量的是檢索系統的查準率.召回率是指檢索出的相關文檔數和文檔庫中所有相關文檔數的比率,衡量的是檢索系統的查全率.

2.3 參數實驗及結果分析

因為以上公式含有未知參數,所以應先確定未知參數的值.在計算用戶特征相似度時即公式(2),出現了α,β,θ等三個未知參數,用來衡量特征權重.因為α+β+θ=1,所以只需確定α、β的值.取鄰居用戶 N 為5時,λ為0.6時,α以步長為0.1,β步長為0.2進行實驗.實驗結果如下.

由圖1可知,當α為0.1,β為0.3時準確率最高.從α、β值可以得出,當預測用戶對音樂的興趣時,用戶性別對用戶的喜好影響較小,而用戶年齡對用戶影響稍大,用戶國籍對用戶的影響比用戶年齡和性別特征影響都大.這也證實了語言不同,文化背景不同,用戶對音樂的喜好不同.例如中國的年輕人和美國的年輕人所喜愛的音樂有很大差異.

圖1 不同α、β值下的準確率

全局信任度和局部信任度對用戶信任度的影響程度確定即λ的確定,其中λ的取值為[0,1].本文將λ的值以步長0.1進行取值,實驗結果如圖2.

圖2 λ取不同值時的準確率和召回率

由圖2可知當λ取0.6時,準確率達到最高,而此時的召回率比λ取0.5時有所下降.為了提高準確率,本文選取λ為0.6.其中λ為0時為沒有考慮全局信任度得情況,而λ為1時為沒有考慮局部信任度的情況.

由于向目標用戶推薦的標簽集是由用戶近鄰標簽所組成,因此近鄰的個數也將影響推薦效率.為此我們取近鄰個數N為不同值,實驗結果如圖3.

圖3 近鄰數量N取不同值時的實驗結果

由圖3可知,當N小于5時準確率和召回率都在逐漸升高,而當近鄰數量大于5時準確率和召回率,則越來越低.這是由于標簽集數量過大,使得準確找到能夠預測用戶興趣的標簽的難度也隨之增大.

為了對比改進前后算法的效率,將基于用戶特征相似度的社交標簽推薦算法標記為F-TP,將基于用戶信任度的社交標簽推薦算法標記為T-TP,將基于興趣相似度的社交標簽推薦算法標記記為I-TP,將基于用戶信任度和用戶特征的社交標簽推薦算法標記為TFTP,本文算法記為TFI-TP.算法效果對比圖如下.

圖4 不同算法的實驗結果對比圖

通過對以上實驗結果分析可以得出以下結論:傳統只考慮用戶興趣的I-TP算法準確率較低.而考慮用戶特征的F-TP推薦算法準確率和召回率都較I-TP有了提高,這是因為特征相同的用戶,所喜愛的音樂相似性較大.而考慮用戶信任度的T-TP算法相較于前兩個算法有了提高,這與日常生活中人們比較相信有較好信譽的人有關,這也體現在網絡中[28].而融合了用戶特征和用戶信任度的TF-TP算法,在準確率和召回率上比前三個算法都有所提高,這是因為用戶比較信任那些來自與自己特征相似度和信任度都較高的用戶的推薦.同時,實驗結果顯示,本文提出的TFI-TP推薦算法較其他算法推薦效果更佳.

本文提出的TFI-TP算法其準確率和召回率都有所提高的原因在于同時考慮了用戶特征信息和社交標簽,使得冷啟動問題和數據稀疏問題得到了緩解.由于傳統推薦系統對無任何歷史記錄的新用戶的推薦是盲目的,這大大降低了推薦準確率,而冷啟動問題的解決將有效提高推薦準確率.豐富的社交標簽數據為推薦系統提供了足夠的數據集用于分析用戶興趣,解決了由于評分數據稀疏而帶來的準確率低的問題.同時,TFI-TP算法將用戶信任度考慮進來,提高了用戶對推薦資源的信任度,而將用戶興趣考慮進來,減少了推薦的盲目性,提高了推薦召回率.

3 結語

本文提出的TFI-TP算法引入了用戶特征信息、用戶信任度和用戶興趣,利用用戶特征和用戶興趣所形成的相似度,并結合信任度形成綜合相似度確定鄰居用戶,利用鄰居用戶的標簽集結合標簽推薦方法,進而產生最終的推薦結果.實驗結果表明,用戶特征和用戶信任度的引入過濾掉了不符合用戶興趣且用戶不太信任的資源,緩解了冷啟動問題,提高了推薦的質量.將用戶興趣考慮進來,使得目標用戶的興趣更加明確,提高推薦準確率.將社交標簽引入到TFI-TP算法中來,充分地利用了豐富的標簽數據,緩解了數據稀疏問題.實驗結果說明,本文提出的TFI-TP能夠有效緩解冷啟動問題和數據稀疏問題.

社會的進步發展,人們對于推薦系統的要求更高.如根據用戶情感變化、地理位置、時間因素等進行相關推薦,這也是以后研究的方向.另外,本文沒有考慮用戶標注標簽時間,希望以后有機會能在這方面繼續學習和探索.

1易明,鄧衛華.基于標簽的個性化信息推薦研究綜述.情報理論與實踐,2011,34(3):126–128.

2Resnick P,Iacovou N,Suchak M,et al.GroupLens:An open architecture for collaborative filtering of netnews.Proc.of the 1994 ACM Conference on Computer Supported Cooperative Work.New York,NY,USA.1994.175–186.

3Gunawardana A,Meek C.Tied boltzmann machines for cold start recommendations.Proc.of the 2008 ACM Conference on Recommender Systems.New York,NY,USA.2008.19–26.

4Gunawardana A,Meek C.A unified approach to building hybrid recommender systems.Proc.of the 3rd ACM Conference on Recommender Systems.New York,NY,USA.2009.117–124.

5Park ST,Chu W.Pairwise preference regression for coldstart recommendation.Proc.of the 3rd ACM conference on Recommender systems.New York,NY,USA.2009.21–28.

6李春,朱珍民,葉劍,等.個性化服務研究綜述.計算機應用研究,2009,26(11):4001–4005,4009.[doi:10.3969/j.issn.1001-3695.2009.11.001]

7Kim HN,Ji AT,Ha I,et al.Collaborative filtering based on collaborative tagging for enhancing the quality of recommendation.Electronic Commerce Research and Applications,2010,9(1):73–83.[doi:10.1016/j.elerap.2009.08.004]

8Wang D,Ma J,Lian T,et al.Recommendation based on weighted social trusts and item relationships.Proc.of the 29th Annual ACM Symposium on Applied Computing.New York,NY,USA.2014.254–259.

9Wu L,Chen EH,Liu Q,et al.Leveraging tagging for neighborhood-aware probabilistic matrix factorization.Proc.of the 21st ACM International Conference on Information and Knowledge Management.New York,NY,USA.2012.1854–1858.

10Agarwal D,Chen BC.Regression-based latent factor models.Proc.of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris,France.2009.19–28.

11Sarwar B,Karypis G,Konstan J,et al.Item-based collaborative filtering recommendation algorithms.Proc.of the 10th International Conference on World Wide Web.New York,NY,USA.2001.285–295.

12Kim BM,Li Q,Kim JW,et al.A new collaborative recommender system addressing three problems.Proc.of the 8th Pacific Rim International Conference on Artificial Intelligence.Auckland,New Zealand.2004.495–504.

13李聰,梁昌勇,董珂.基于項目類別相似性的協同過濾推薦算法.合肥工業大學學報(自然科學版),2008,31(3):360–363.

14Xia WW,He L,Ren L,et al.A new collaborative filtering approach utilizing item’s popularity.Proc.of IEEE International Conference on Industrial Engineering and Engineering Management.Singapore.2008.1480–1484.

15李琦.基于社交網絡好友信任度的個性化推薦系統研究[碩士學位論文].哈爾濱:哈爾濱工業大學,2014.

16任磊.推薦系統關鍵技術研究[博士學位論文].上海:華東師范大學,2012.

17何波.基于社交用戶信任度和標注動機的標簽推薦系統研究[碩士學位論文].重慶:重慶大學,2015.

18時念云,葛曉偉,馬力.基于用戶人口統計特征與信任機制的協同推薦.計算機工程,2016,42(6):180–184.

19布海喬.基于用戶評分和用戶特征的混合協同過濾算法研究[碩士學位論文].天津:天津師范大學,2015.

20項亮.推薦系統實踐.北京:人民郵電出版社,2015:44–60.

21Breese JS,Heckerman D,Kadie C.Empirical analysis of predictive algorithms for collaborative filtering.Proc.of the 14th Conference on Uncertainty in Artificial Intelligence.Madison,Wisconsin,USA.1998.43–52.

22Ziegler CN,Lausen G.Spreading activation models for trust propagation.Proc.of the 2004 IEEE International Conference on e-Technology,e-Commerce and e-Service.Washington,DC,USA.2004.83–97.

23吳慧,卞藝杰,趙喆,等.基于信任的協同過濾算法.計算機系統應用,2014,23(7):131–135.

24劉迎春,鄭小林,陳德人.信任網絡中基于角色信譽的信任預測.北京郵電大學報,2013,36(1):72–76.

25張富國.基于社交網絡的個性化推薦技術.小型微型計算機系統,2014,35(7):1470–1476.

26Social Media.Social media accounts for 22% of time spent online.http://www.webpronews.com/social-networks-blogsaccount-for-22-of-time-spent-online-2010-06/.[2016-05-10].

27Herlocker JL,Konstan JA,Terveen LG,et al.Evaluating collaborative filtering recommender systems.ACM Trans.on Information Systems,2004,22(1):5–53.[doi:10.1145/963770]

28Sinha R,Swearingen K.Comparing recommendations made by online systems and friends.Proc.of the DELOS-NSF Workshop on Personalization and Recommender Systems in Digital Libraries.Dublin,Ireland.2001.1–6.

Recommendation Algorithm Based on Synthetic Similarity and Social Tag

SHI Nian-Yun,Zhang Yun,MA Li
(College of Computer and Communication Engineering,China University of Petroleum,Qingdao 266580,China)

The traditional methods of personalized recommendation are faced with the problems of sparse data and cold start.This paper combines the previous research of the project team and introduces the user interest to form the comprehensive similarity,based on the comprehensive consideration of user characteristics and user trust degree.At the same time,this paper uses the social tags which enrich the recommendation data to solve the problem of sparse data in current recommendation system.Firstly,the similarity degree is used to find the similar neighbors of the users and form a tag set by labeling the similar neighbors.Secondly,a tag-based recommendation algorithm is used to generate the final recommendation list.The experimental results show that the proposed algorithm can effectively improve the accuracy of recommendation and the recall rate.

user characteristics; trust degree; cold start; user interest; social tag

時念云,張蕓,馬力.基于綜合相似度和社交標簽的推薦算法.計算機系統應用,2017,26(10):178–183.http://www.c-s-a.org.cn/1003-3254/6025.html

2017-01-16; 采用時間:2017-02-26