融合“用戶-項目-用戶興趣標簽圖”的協同好友推薦算法*

陳潔敏，李建國+，湯非易，湯 庸，陳笑凡，唐婷芳

1.華南師范大學 計算機學院，廣州 510631

2.維多利亞大學 工程與科學學院，澳大利亞 墨爾本 3011

1 引言

隨著Web 2.0網絡技術的不斷發展，在線社交網絡（online social network，OSN）和社會化標簽系統（social tagging systems，STS）得到了蓬勃的發展，例如Facebook、Twitter、Last.fm及新浪微博等網站。其中，如何為用戶推薦具有相同興趣愛好的好友已成為社交網絡推薦的研究熱點之一。目前大部分社交網站的好友推薦算法主要分為兩種：一種是利用用戶的共同興趣愛好來進行好友推薦，主要是根據用戶提供的個人信息進行基于內容的協同推薦；另一種是基于用戶的社交網絡關系圖來進行推薦，主要思想是將用戶好友的好友作為推薦對象。這兩種方法都存在局限性，前者當用戶信息不完整時，特別是新注冊的用戶，那么推薦效果將受到影響；后者由于用戶的平均好友數遠遠小于用戶總數，而且好友的好友可能是已認識的人，不利于拓展用戶的好友圈，同時隨著用戶數據的增加或變更，該方法難以捕捉到用戶興趣愛好的變化。

社會化標簽（http://de.wikipedia.org/wiki/Social_Tagging）作為Web2.0的重要技術之一，它允許用戶根據自己的需要和理解自由地對各種資源進行標簽標注。目前，大量的基于標簽系統的網站都得到了用戶的青睞并取得了巨大的成功，例如YouTube、Delicious、Last.fm和豆瓣等。在Last.fm音樂網站中，歌曲《Roll in the Deep》被307 915人評價過，并被61個標簽進行了標注，其中5 091人打了“amazing voice”標簽，5 068人打了“best of 2011”標簽。

在社會化標簽中，用戶對資源標注的標簽及使用次數能有效地反映用戶的興趣偏好和用戶對某種資源的喜好程度，因此標簽是用戶和資源之間的重要橋梁。文獻[1]提出一種新穎的推薦框架，利用用戶的標簽信息來擴張用戶的興趣愛好，從而提高物品的推薦準確度；文獻[2]通過對用戶和項目的標簽進行主題建模，提出隱藏的語義信息，將其融入到矩陣分解中來提高推薦準確率；文獻[3]將標簽作為項目的特征，提出以特征為中心的推薦方法；文獻[4]提出一種新穎的用戶推薦框架UserRec，對用戶標簽圖進行社區發現來構建用戶興趣模型，利用KL距離（Kullback-Leibler divergence）來計算用戶之間的相似度。雖然現有不少推薦方法是根據用戶標簽標注行為來進行推薦，但往往著重于標簽的主題挖掘，而沒有同時考慮用戶、項目和標簽之間的關系。針對該問題，本文通過構建用戶的興趣標簽圖來發掘用戶的興趣主題，并在分析“用戶-項目-標簽”的標注行為的基礎上，提出了一種基于“用戶-項目-用戶興趣標簽圖”的協同好友推薦算法（collaborative filtering recommendation algorithm by combining diffusion on user-item-tag graph and users’personal interest model，UITGCF）。

2 相關工作

2.1 基于社會化標簽的三部圖物質擴散算法

基于社會化標簽的三部圖物質擴散算法（collaborative filtering with diffusion-based similarity on tripartite graphs，DTGCF）[5]是利用物質擴散的過程來獲得用戶之間的相似度，主要分為“用戶-項目”和“用戶-標簽”兩個二部圖的計算。具體的資源-分配過程為目標用戶u將其資源值的能量平均分配到所評分或購買過的項目中，同時也將能量平均分配到其使用過的標簽上。項目i從用戶u處獲得的資源為riu:

其中，k(u)為用戶u在“用戶-項目”二部圖中的度；α′ui為1表示用戶u購買或點評了項目i，否則為0。同理標簽t從用戶u處獲得的資源為rtu:

其中，k′(u)為用戶u在“用戶-標簽”二部圖中的度；α′ut為1表示用戶u使用了標簽t，否則為0。

然后資源從項目和標簽再流回到用戶u。設“用戶-項目”二部圖所得到的資源分配矩陣為S，用戶u到用戶v的資源分配權重suv可以表示為：

在“用戶-標簽”二部圖中也有對應的資源分配矩陣為 S′,用戶u到用戶v的資源分配權重s′uv可以表示為：

最后將從項目和標簽中擴散回來的能量進行線性整合作為最后的資源分配矩simDTG。simDTG(u,v)代表用戶v從目標用戶u所能獲得的能量，體現了用戶間的相似度。

2.2 基于用戶興趣的建模

目前用戶興趣建模還沒有明確的定義，大多文獻[6-7]認為用戶興趣建模是通過對用戶個人資料、行為等信息的收集和分析，形成用戶個人的興趣模型。在社會化標簽系統中，用戶可以自由地使用標簽對項目進行標注，同時不同的標簽也表達了用戶自身多樣化的興趣偏好，因此可利用標簽的使用情況來為用戶興趣建模，并應用到協同推薦中，從而提高推薦效果[8-11]。然而大部分基于標簽的協同推薦算法主要有兩種：一是利用用戶或物品擁有共現標簽的數目來計算用戶或物品的相似度[12]，然而會忽略標簽本身所具有的語義以及標簽之間的關聯關系；二是利用LDA（latent Dirichlet allocation）等模型來為用戶進行興趣建模，但當標簽數量稀疏時，將影響到模型的效果。因此文獻[4]提出了一種新穎的用戶推薦框架（user recommendation，UserRec），對用戶標簽圖進行社區發現來構建用戶興趣模型，利用KL距離來計算用戶之間的相似度。

盡管UserRec框架能根據標簽為用戶進行興趣建模，但缺少了用戶和項目之間的考慮。而DTGCF算法雖然考慮了“用戶-項目”和“用戶-標簽”之間的關系，但忽略了標簽之間的共現及語義的問題，在不同程度上造成信息損失。針對以上問題，本文首先利用基于“用戶-項目-標簽”的三部圖物質擴散推薦算法來計算用戶之間的相似度；同時借鑒了UserRec用戶興趣建模的方法，增加了標簽預處理；通過構建用戶的興趣標簽圖來發掘用戶的興趣主題，并根據用戶主題分布，利用KL距離來計算用戶之間的相似度；最后將兩組結果利用調和平均數方式融合得到最終的用戶相似度，并進行好友推薦。

3 融合“用戶-項目-用戶興趣標簽圖”的協同好友推薦

3.1 標簽預處理

由于標簽是用戶自主用來標注項目和個性化分類的，在語義上可能存在同義性、歧義性和不確定性（http://en.wikipedia.org/wiki/General_semantics）。例如，用戶給項目a打了“purchasing”標簽，用戶v用標簽“buying”標注了項目a，這兩個標簽是同義詞，如果只考慮標簽使用的次數，而忽略標簽之間語義的相似度，將會造成推薦不準確。同時由于標簽是用戶自發標注的，可能存在無意義的標簽，例如//@，????等。因此，需要對標簽進行預處理。首先對標簽進行符號正則化處理，符合Regular expressionR=[a-z,A-Z]{2,}的標簽保留。然后利用JWS（Java WordNet similarity）開發包（http://search.cpan.org/dist/WordNet-Similarity/doc/intro.pod）[13]中的 Lin 算法對標簽進行語義處理。

3.2 用戶標簽興趣圖

標簽網絡圖是一種共現網絡[14]，節點是標簽，如果兩個標簽被標注在同一資源上則存在共現的情形，它們之間存在著重要的內在關聯，用邊連接兩個標簽節點來體現共現的情況。標簽網絡圖不僅能反映用戶的興趣偏好，同時也能體現資源的主題，因此可以通過它來構建用戶的興趣模型。

首先，用UG=(T,E,W)表示用戶的標簽圖，其中集合T為用戶u使用過的標簽集合，T={t1,t2,…,tr}，r為標簽的總數；E是標簽之間邊的集合；ekm代表標簽tk和標簽tm的共現關系；W是連接邊的權重集合，w(tk,tm)代表標簽tk和tm的共現次數；然后采用Louvain社區發現算法[15]對用戶個人標簽圖進行社區發現，原來的用戶標簽圖會被劃分成若干個社區，每個社區可以看作是用戶的興趣主題，用C表示所有用戶主題的集合。

定義1UC(u)表示用戶u的興趣主題集合，其定義如下：

Fig.1 Tag graph of one user圖1 用戶個人標簽圖

3.3 用戶相似度計算

通過社區發現后，每個用戶都能得到自己的興趣主題集合UC(u)，利用概率分布的原理來量化每個興趣主題對用戶的影響程度。如果用戶對某個興趣主題的標簽使用越多，意味著用戶對該主題越感興趣?；谶@個假設，興趣主題對用戶的影響如式（6）所示：

Table 1 Topics of user's interests表1 用戶的興趣主題

除了要考慮單個興趣主題對用戶的影響，還要考慮所有興趣主題對用戶的整體影響，通過計算每個興趣主題的概率值，可以得到用戶的主題分布，如式（7）所示：

然后根據兩個用戶的興趣主題分布，利用KL距離計算兩個用戶之間的相似度：

通過KL距離計算兩個用戶的興趣主題分布來體現用戶間的相似度，值越大，距離越遠，相似度越低。為了方便計算，對其進行歸一化轉換，simUIG(u,v)值越大，用戶之間的相似程度越高。

除了考慮用戶興趣主題的相似度，還需要考慮用戶和項目之間及項目和標簽之間的關系，因此本文采用調和平均數方式將DTGCF算法所獲得的用戶相似度simDTG(u,v)與通過用戶興趣主題分布獲得的用戶相似度simUIG(u,v)進行融合產生最終用戶相似度sim(u,v)。

將與用戶u非好友關系的用戶按用戶綜合相似度大小降序排列，取相似度最高的前N個用戶進行好友推薦。

4 實驗結果與分析

4.1 實驗數據與環境

本文實驗采用hetrec2011-delicious-2k數據集和hetrec2011-last.fm-2k數據集（http://grouplens.org/datasets/hetrec-2011/）。 Delicious（https://delicious.com/）是目前網絡上最大的書簽類站點，可幫助用戶共享他們喜歡網站鏈接的流行網站，而Last.fm（http://www.last.fm/）是全球最大的社會音樂平臺，提供網絡電臺與音樂社群功能。數據詳細描述如表2所示。

Table 2 Datasets statistics表2 數據集的統計信息

4.2 評測指標

本文主要研究的是Top-N的推薦問題，采用準確率（Precision）和召回率（Recall）作為推薦質量的評測指標。R(u)是推薦系統根據用戶在訓練集上的行為給用戶提供的推薦列表，T(u)是用戶在測試集上的行為列表。

在實驗中，算法將用20種不同的推薦長度N∈[5,100]進行計算。

4.3 結果分析

為了評價基于“用戶-項目-用戶興趣標簽圖”推薦算法（UITGCF）的推薦質量，將其與以下推薦算法進行比較：（1）UserRec算法；（2）DTGCF算法；（3）CosTag，根據用戶使用標簽的歷史記錄，采用余弦相似度計算出用戶相似度。

4.3.1 用戶興趣圖劃分結果

為Delicious和Last.fm數據集中的用戶進行用戶個人興趣圖構建，并通過Louvain算法進行社區發現，其結果如表3所示。

Table 3 Statistics of datasets'communities表3 數據集的社區統計信息

4.3.2 參數λ的權重設置

式（5）中參數λ決定了從項目和標簽中擴散回來的能量以多大的比例進行線性整合作為最后的資源分配矩陣simDTG。當λ為0時，相當于只使用純粹的基于項目-標簽二部圖的信息，當λ為1時，相當于退化為基于用戶-標簽二部圖的算法。設置λ值在[0,1]范圍內以0.1遞增，通過在不同數據集上的實驗獲取λ的最佳閾值。圖2和圖3分別為λ在選取不同值的情況下，UITGCF算法在Delicious數據集和Last.fm數據集上進行TOP5、TOP10和TOP15推薦的實驗結果?？梢钥闯?，λ=0.4為Delicious數據集的最佳值，而λ=0.5為Last.fm數據集的最佳值。

4.3.3 性能對比

為了驗證本文UITGCF算法的推薦質量，與其他算法進行對比，結果如圖4和圖5所示。對比4種算法在Delicious數據集上的實驗結果，如圖4所示，UITGCF算法的準確率和查全率明顯要比其他3種算法高。隨著Top-N值增大，4種算法在準確率上呈下降趨勢，但是UITGCF算法仍有一定的提高。在Precision@5、Precision@20和Precision@50上，UITGCF算法相對于DTGCF算法分別提高了6.95%、13.07%和11.14%，而在Recall@50、Recall@75和Recall@100上，比DTGCF算法分別提高了8.89%、7.29%和5.08%。

Fig.2 Impact of parameterλon Delicious dataset圖2 參數λ在Delicious數據集上的權重設置

Fig.3 Impact of parameter λ on Last.fm dataset圖3 參數λ在Last.fm數據集上的權重設置

同樣在Last.fm數據集上，UITGCF算法的準確率和查全率比其他3種算法也有所提高。在Preci-sion@5、Precision@20和Precision@50上，UITGCF算法比DTGCF算法分別提高了18.60%、9.29%和7.59%，而在 Recall@50、Recall@75和 Recall@100上，比DTGCF算法分別提高了7.53%、5.73%和6.69%。

Fig.4 Comparison of performance on Delicious dataset圖4 算法在Delicious數據集上的性能對比

Fig.5 Comparison of performance on Last.fm dataset圖5 算法在Last.fm數據集上的性能對比

4.4 推薦模型的應用

通過上述的實驗分析得知，UITGCF算法具有良好的推薦質量。因此可以將該算法應用于在線學術信息服務平臺——學者網上，為用戶推薦更多的權威用戶。核心用戶具有詳細的個人信息（論文、項目和教學等）、豐富的好友關系等。在實際應用中，將用戶的論文關鍵字和研究領域作為用戶的標簽，由于不存在用戶對項目評分，將simDTG(u,v)改為利用文本向量空間模型（text vector space model，TVSM）對學者網用戶u和用戶v的個人信息進行用戶相似度simprofile(u,v)計算，公式如下：

與基于用戶個人信息相似度的推薦相比，本文算法能提高同一研究領域中核心用戶的推薦度。圖6是學者網向研究領域為數據庫方向的用戶203進行用戶推薦的結果分析，用戶66為數據庫領域中的核心用戶，可以發現，該推薦算法明顯提高了權威用戶66對用戶203的推薦度。

Fig.6 Comparison of recommended results圖6 推薦結果對比

5 結束語

本文在基于“用戶-項目-標簽”的三部圖物質擴散推薦算法基礎上，提出了一種基于“用戶-項目-用戶興趣標簽圖”的混合協同過濾推薦算法。利用“用戶-項目-標簽”三部圖計算用戶之間的相似度，同時引入用戶興趣主題，根據用戶主題分布，利用KL距離來計算用戶之間的相似度，將兩種結果進行融合得到最終的用戶相似度，并根據相似度進行用戶好友的推薦。實驗證明，本文算法能有效提高Top-N推薦的準確度。在下一步的研究中，將考慮提取更多的用戶行為信息來提高推薦的效果，同時采用不同方法進行信息融合。

[1]Zhang Zhu,Zheng Xiaolong,Zeng D D.A framework for diversifying recommendation lists by user interest expansion[J].Knowledge-Based Systems,2016,105:83-95.

[2]Chen Chaochao,Zheng Xiaolin,Wang Yan,et al.Capturing semantic correlation for item recommendation in tagging systems[C]//Proceedings of the 30th Conference on Artificial Intelligence,Phoenix,Feb 12-17,2016.Menlo Park:AAAI,2016:108-114.

[3]Zhang Chenyi,Wang Ke,Lim E P,et al.Are features equally representative?A feature-centric recommendation[C]//Proceedings of the 29th Conference on Artificial Intelligence,Austin,Jan 26-30,2015.Menlo Park,AAAI,2015:389-395.

[4]Zhou T C,Ma Hao,Lyu M R,et al.UserRec:a user recommendation framework in social tagging systems[C]//Proceedings of the 24th Conference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2010:1486-1491.

[5]Shang Mingsheng,Zhang Zike,Tao Zhou,et al.Collaborative filtering with diffusion-based similarity on tripartite graphs[J].Physica A:Statistical Mechanics and Its Applications,2010,389(6):1259-1264.

[6]Stamou S,Ntoulas A.Search personalization through query and page topical analysis[J].User Modeling and User-Adapted Interaction,2009,19(1/2):5-33.

[7]Lipczak M.Tag recommendation for folksonomies oriented towards individual users[C]//Proceedings of the 2008 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases Discovery Challenge,Antwerp,Sep 15-19,2008.Berlin,Heidelberg:Springer,2008:84-95.

[8]Zhang Yantao,Wang Guoyin,Yu Hong.A users'interest similarity calculating method in Folksonomy[J].Journal of Nanjing University:Natural Sciences,2013,49(5):588-594.

[9]Shepitsen A,Gemmell J,Mobasher B,et al.Personalized recommendation in social tagging systems using hierarchical clustering[C]//Proceedings of the 2008 Conference on Recommender Systems,Lausanne,Oct 23-25,2008.New York:ACM,2008:259-266.

[10]Liu Chuang,Yeung C H,Zhang Zike.Self-organization in social tagging systems[J].Physical Review E:Statistical Nonlinear&Soft Matter Physics,2011,83(2):066104.

[11]Jelassi M N,Ben Yahia S B,Nguifo E M.A personalized recommender system based on users'information in Folksonomies[C]//Proceedings of the 22nd International Conference on World Wide Web,Rio de Janeiro,May 13-17,2013.New York:ACM,2013:1215-1224.

[12]Halpin H,Robu V,Shepherd H,The complex dynamics of collaborative tagging[C]//Proceedings of the 16th International Conference on World Wide Web,Banff,May 8-12,2007.New York:ACM,2007:211-220.

[13]Pedersen T,Patwardhan S,Michelizzi J.WordNet:similaritymeasuring the relatedness of concepts[C]//Proceedings of the 19th National Conference on Artificial Intelligence,San Jose,Jul 25-29,2004.Menlo Park:AAAI,2004:1024-1025.

[14]Li Xin,Guo Lei,Zhao Y E.Tag-based social interest discovery[C]//Proceedings of the 17th International Conference on World Wide Web,Beijing,Apr 21-25,2008.New York:ACM,2008:675-684.

[15]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:155-168.

附中文參考文獻：

[8]張艷桃,王國胤,于洪.面向Folksonomy的用戶興趣相似性度量方法[J].南京大學學報:自然科學版,2013,49(5):588-594.