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

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

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

1 引言

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

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

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

2 相關(guān)工作

2.1 基于社會化標(biāo)簽的三部圖物質(zhì)擴散算法

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

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

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

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

在“用戶-標(biāo)簽”二部圖中也有對應(yīng)的資源分配矩陣為 S′,用戶u到用戶v的資源分配權(quán)重s′uv可以表示為：

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

2.2 基于用戶興趣的建模

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

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

3 融合“用戶-項目-用戶興趣標(biāo)簽圖”的協(xié)同好友推薦

3.1 標(biāo)簽預(yù)處理

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

3.2 用戶標(biāo)簽興趣圖

標(biāo)簽網(wǎng)絡(luò)圖是一種共現(xiàn)網(wǎng)絡(luò)[14]，節(jié)點是標(biāo)簽，如果兩個標(biāo)簽被標(biāo)注在同一資源上則存在共現(xiàn)的情形，它們之間存在著重要的內(nèi)在關(guān)聯(lián)，用邊連接兩個標(biāo)簽節(jié)點來體現(xiàn)共現(xiàn)的情況。標(biāo)簽網(wǎng)絡(luò)圖不僅能反映用戶的興趣偏好，同時也能體現(xiàn)資源的主題，因此可以通過它來構(gòu)建用戶的興趣模型。

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

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

Fig.1 Tag graph of one user圖1 用戶個人標(biāo)簽圖

3.3 用戶相似度計算

通過社區(qū)發(fā)現(xiàn)后，每個用戶都能得到自己的興趣主題集合UC(u)，利用概率分布的原理來量化每個興趣主題對用戶的影響程度。如果用戶對某個興趣主題的標(biāo)簽使用越多，意味著用戶對該主題越感興趣。基于這個假設(shè)，興趣主題對用戶的影響如式（6）所示：

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

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

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

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

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

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

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)與環(huán)境

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

Table 2 Datasets statistics表2 數(shù)據(jù)集的統(tǒng)計信息

4.2 評測指標(biāo)

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

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

4.3 結(jié)果分析

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

4.3.1 用戶興趣圖劃分結(jié)果

為Delicious和Last.fm數(shù)據(jù)集中的用戶進行用戶個人興趣圖構(gòu)建，并通過Louvain算法進行社區(qū)發(fā)現(xiàn)，其結(jié)果如表3所示。

Table 3 Statistics of datasets'communities表3 數(shù)據(jù)集的社區(qū)統(tǒng)計信息

4.3.2 參數(shù)λ的權(quán)重設(shè)置

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

4.3.3 性能對比

為了驗證本文UITGCF算法的推薦質(zhì)量，與其他算法進行對比，結(jié)果如圖4和圖5所示。對比4種算法在Delicious數(shù)據(jù)集上的實驗結(jié)果，如圖4所示，UITGCF算法的準(zhǔn)確率和查全率明顯要比其他3種算法高。隨著Top-N值增大，4種算法在準(zhǔn)確率上呈下降趨勢，但是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 參數(shù)λ在Delicious數(shù)據(jù)集上的權(quán)重設(shè)置

Fig.3 Impact of parameter λ on Last.fm dataset圖3 參數(shù)λ在Last.fm數(shù)據(jù)集上的權(quán)重設(shè)置

同樣在Last.fm數(shù)據(jù)集上，UITGCF算法的準(zhǔn)確率和查全率比其他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數(shù)據(jù)集上的性能對比

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

4.4 推薦模型的應(yīng)用

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

與基于用戶個人信息相似度的推薦相比，本文算法能提高同一研究領(lǐng)域中核心用戶的推薦度。圖6是學(xué)者網(wǎng)向研究領(lǐng)域為數(shù)據(jù)庫方向的用戶203進行用戶推薦的結(jié)果分析，用戶66為數(shù)據(jù)庫領(lǐng)域中的核心用戶，可以發(fā)現(xiàn)，該推薦算法明顯提高了權(quán)威用戶66對用戶203的推薦度。

Fig.6 Comparison of recommended results圖6 推薦結(jié)果對比

5 結(jié)束語

本文在基于“用戶-項目-標(biāo)簽”的三部圖物質(zhì)擴散推薦算法基礎(chǔ)上，提出了一種基于“用戶-項目-用戶興趣標(biāo)簽圖”的混合協(xié)同過濾推薦算法。利用“用戶-項目-標(biāo)簽”三部圖計算用戶之間的相似度，同時引入用戶興趣主題，根據(jù)用戶主題分布，利用KL距離來計算用戶之間的相似度，將兩種結(jié)果進行融合得到最終的用戶相似度，并根據(jù)相似度進行用戶好友的推薦。實驗證明，本文算法能有效提高Top-N推薦的準(zhǔ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].南京大學(xué)學(xué)報:自然科學(xué)版,2013,49(5):588-594.