基于標簽聚類與用戶模型的個性化推薦方法研究

劉如娟

〔摘 要〕社會標簽系統是Web2.0中提出的概念，旨在更好地表達用戶的興趣和意愿。而標簽聚類是社會標簽系統的個性化推薦中一個重要的研究課題。本文研究了如何基于標簽聚類與用戶模型來進行個性化推薦的方法。通過計算標簽的相似度進行標簽聚類，結合用戶模型，根據標簽聚類結果做出推薦。通過采用CiteULike公布的數據集進行實驗證明，與未采用標簽聚類的推薦方法相比，本方法不僅可提高推薦的命中率，優化目標資源的排名，而且能為用戶發現更多新的感興趣的資源。

〔關鍵詞〕社會化網絡；社會標簽系統；標簽聚類；用戶模型；個性化推薦

〔中圖分類號〕G250.73 〔文獻標識碼〕A 〔文章編號〕1008-0821（2016）06-0074-05

〔Abstract〕Social tag system is a new concept proposed in Web2.0 to express users interest more clearly.And tag clustering is an important research topic in personalized recommendation.This paper proposed a personalized recommendation method based on tag clustering and user model.Tag clustering was realized by calculating similarity between tags and made recommendations according to tag clustering results.Experiment results using CiteULike data set show，proposed method which could improve the recommendation hit ratio compared with general recommendation algorithm，optimize ranking of objective resources，and help users to discover new resources easier.

〔Key words〕social networks；social tag system；tag clustering；user model；personalized recommendation

在Web2.0時代，用戶不僅是內容的瀏覽者，同時也是內容的創造者。由于網絡信息的爆炸式增長，用戶常常在海量信息中無法快速找到自己需要的資源。目前，大多數Web2.0網站都提供了社會標簽系統，例如：Delicious，Last.fm，Flickr，CiteULike以及豆瓣網等。在這些網站中，用戶可以按照自己的理解，自由地用標簽對自己感興趣的資源進行標注。同時，用戶還可以根據標簽對資源進行訪問，并且可以利用對自己感興趣的其他人所做的標簽去發現一些自己感興趣的新資源。用戶在標注資源時所使用的標簽既反映了用戶自身的興趣愛好，又反映了資源的特點。作為聯系用戶和資源的紐帶，標簽是反映用戶數據的重要數據源。因此可以利用用戶在標注資源時所使用的標簽為用戶推薦其所需要的資源。

但是傳統的協同過濾推薦算法并沒有將標簽信息考慮到推薦過程中，因此不能挖掘到標簽所蘊含的豐富的個性化信息，無法適應社會標簽系統中個性化推薦的要求。同時，由于社會化標注具有一定的隨意性和不可控性，帶來的標簽語義模糊性以及數據稀疏性問題，影響了利用標簽進行個性化推薦的效果。因此，研究如何通過標簽聚類發現同一標簽所表達的不同含義，理解用戶的真正意圖，為其推薦更加符合其興趣的資源具有重要意義。

近幾年來，基于標簽數據的推薦方法研究獲得了學術界廣泛的關注，如何利用用戶標簽數據設計高效準確的個性化推薦算法，為用戶提供適合其個性化需求的資源和標簽，已經成為個性化推薦研究領域重要的研究內容之一。

本文主要研究用戶給資源標注標簽的行為，對標簽進行聚類，通過分析用戶標簽數據確定推薦算法，將基于用戶模型與基于鏈接關系的相似度計算方法相結合，研究增加標簽聚類后的個性化推薦方法，通過與以往推薦方法的比較，證明可提高推薦的質量和性能。

文章結構如下：第一部分對本文的研究內容進行簡單介紹。第二部分對國內外研究現狀進行介紹。第三部分描述本文采用的標簽推薦算法，通過標簽聚類提高推薦系統的性能，實現資源推薦。第四部分的實驗設計評測指標驗證該推薦系統各方面的性能。第五部分總結全文并且對未來工作進行展望。

1 國內外研究現狀

隨著社會化網絡的迅速發展，基于標簽數據的推薦算法的研究已經成為該領域的研究熱點之一。文獻[1-2]提出的基于圖的FolkRank算法是其中之一，這種方法的基本思想主要是利用標簽與資源以及標簽與用戶之間的鏈接信息，但這種方法并沒有很好的考慮用戶標簽中所蘊含的個性化涵義，因此無法給不同的用戶推薦個性化標簽。

而將標簽信息與傳統的推薦模型相結合的研究是個性化推薦研究的一個新方向。文獻[3]提出一種新的基于標簽的協同推薦模型，將用戶的標簽信息抽象為用戶向量，從而對資源進行協同推薦[4]。文獻[5]采取了類似的方法，主要是采用WordNet來計算不同用戶之間的相似度，來進行協同推薦。文獻[6]中提出了基于張量分解的標簽推薦方法，該方法將社會標簽系統數據集合表示為3階張量的形式，利用高階奇異值分解技術來挖掘用戶、標簽及資源之間的潛在語義。通過與兩種重要的推薦算法進行比較，證明在準確率和召回率上都有明顯提高。

文獻[7]提出了一種基于資源共現的隨機游走方法來聚類標簽；文獻[8]利用標簽共現的分布相似性來增強標簽相關性，結合遞歸貪婪算法和模塊化函數實現了標簽的聚類；文獻[9]介紹了一種基于資源共現的標簽單鏈接層次聚類算法來提高信息檢索的效率；文獻[10]通過建立標簽共現網絡，提出了一種基于標簽相似性的聚類算法對標簽共現網絡進行分割，并建立標簽聚類簇。

將聚類技術應用到資源推薦中也是個性化推薦領域的研究方向之一。文獻[11]的研究表明可以利用層次聚類的方法將資源進行分類，可以在一定程度上消除標簽的冗余性和歧義性等問題。文獻[12]提出了一種基于核信息傳播的標簽聚類方法，利用余弦夾角函數在標簽的資源向量空間上來測量標簽之間的相關性。文獻[13]的研究認為利用層次聚類可以將標簽聚類成與主題相關的類，將標簽表示為基于Web資源的向量，運用層次聚類算法進行標簽聚類，并將聚類結果應用到社會標簽系統的個性化推薦系統中，以此來提升用戶體驗，但是層次聚類方法不具有很好的可伸縮性，合并或分裂點選擇比較困難，同時在合并或分裂的過程中需要檢查和估算大量的對象或結果。

以上方法主要通過建立標簽的資源向量空間模型或以標簽的資源共現為基礎來計算標簽的相似性，缺點在于忽略了三元標注數據中的用戶信息，無法利用標簽與標簽之間的語義關系以及標簽與用戶之間的關系，使得聚類的結果不能完整表達標簽的語義。為了解決以上問題，本文采用了一種基于標簽相似度計算的聚類方法，實驗證明，該方法可提高個性化推薦系統的性能。

2 基于標簽聚類的個性化推薦

對標簽聚類的研究中，最重要的是能夠找到一種好的聚類方法，該方法能夠綜合考慮到標簽與用戶間以及標簽與資源間的關系，使得算法所產生的聚類既能充分的反映用戶對某一主題的偏好程度，又能夠體現對資源的反應程度。而聚類算法中的核心問題就是如何計算標簽之間的相似度，使得聚類能夠更加準確地描述標簽的個性化特征，更好地為推薦打下基礎。本節通過計算標簽的相似度，研究一種標簽聚類算法，將基于用戶和資源鏈接關系相結合計算標簽相似度。實驗證明進行標簽聚類后確實能夠提高目標資源的推薦排名和命中率。

表1展現了利用上述公式計算出的CiteULike數據集中recommendersystem標簽的相關標簽及對應的相似度。

2.2 標簽聚類算法

目前的聚類方法有很多，本文采用的聚類算法是借用k-means算法的思想，基于標簽相似度的計算實現的。同時對k-means算法進行了改進，提高了標簽聚類的精度。

首先計算基本標簽兩兩之間的相似度，將相似性大于一定閾值的基本標簽歸于同一原始類別中。然后將只包含極少數標簽的類作為奇異值去掉，進行進一步聚類，如算法3.1所示。標簽聚類算法可以離線運行。

Step 1 經過初始化，將所有具有共同標注資源的標簽對（ti，tj）及其相似度Simr（ti，tj）存儲到集合SimRe中；

Step 2 在SimRe中尋找具有最大相似度的簇進行合并，直到簇中標簽對的最高相似度差值小于limit；

Step 3 將同一聚類的所有標簽作為該聚類的中心，重新計算聚類中標簽的相似度，直到聚類中心不再發生變化。

通過算法3.1，這樣可以完成社會化標簽的聚類。經過聚類，聚類數目能夠遠遠小于基本標簽的數目，即kn。后續的實驗將對該方法進行驗證。

2.3 基于用戶模型的個性化資源推薦

采用的推薦系統結構如圖1所示，推薦過程分為兩個階段：在第一階段，用戶點擊標簽時，運行協同過濾算法做出初始的推薦，為用戶提供資源集合；在第二階段，考慮用戶模型和標簽聚類后，對該資源集合重新排名，生成個性化的推薦結果。實現過程如算法3.2所示：

3 實驗評測

本文采用CiteULike公布的數據集進行算法性能的評測。CiteULike具有大量帶標簽的資源數據集，本文從中取出約10%的數據進行試驗。原始數據庫中，每條數據都包括文章號、用戶名（MD5值）、收藏時間及收藏時用的標簽4個字段。若用戶在標注一篇文章時使用了多個標簽，則這些標簽分別存入多條數據中。由于本文研究是根據用戶標簽來對用戶進行聚類，考慮用戶標簽與所標注的文章間的關系，因此從原始數據表中提取文章號、用戶名與標簽3個字段的數據，形成一個以用戶名、其使用標簽及所標注的文章號為字段的表。

3.1 數據處理

對數據進行簡單的預處理，包括對無實際意義的標簽，如詞組“no-tag”或純數字標簽等進行刪除，為簡化后續計算對只被一個用戶使用的標簽將不進入聚類分析計算。經過處理后，數據包含3 276個用戶、30 667篇論文和11 377個標簽。采用5層交叉驗證（5-fold cross validation）的方法，即將用戶集分成5份，依次將每一份作為測試集，另4份合并作為訓練集進行實驗，得到5個不同的測試/訓練集，標簽的聚類算法在訓練集上進行。依次對每個（測試/訓練集）測試，將最終得到的5個測試結果做算術平均計算，得到最終的評估結果。

具體試驗是在Java JDk 1.6.0的環境下，運用MySQL數據庫存儲用戶、標簽和文獻信息，形成（用戶-標簽-文獻）數據庫，并且使用navicat可視化客戶端管理數據，在MyEclipse 6.5下計算社會化標簽與資源（這里就是論文數據）間的關聯系數。

標簽數據的聚類分析實驗采用由新西蘭懷卡托大學開發的開源數據挖掘工作平臺——懷卡托智能分析環境WEKA3.7.0運行算法3.1，進行標簽聚類。在初步聚類后，得到一些只包含極少數標簽的類，這些特殊的類包含了那些興趣特殊、異于他人的用戶所產生的標簽，與其他用戶興趣缺乏重疊，很難利用這些標簽進行資源推薦，因此將這部分標簽作為奇異值刪除。繼續進行聚類分析，得到的聚類結果中雖然已經沒有包含極少數標簽的類，但仍存在一個大類，其中包含的標簽數量占總標簽數量的近一半。比較理想的聚類效果應該是每個類中的標簽相對比較均衡，因此對這樣的大類單獨提取出來繼續進行聚類。若再聚類后依然得到標簽數量極少的類別，則再進行奇異值處理。經過上述的反復聚類后，發現再繼續聚類也不能聚成幾個有明顯區別的類時停止聚類。通過多次的聚類分析，解決了標簽的數據稀疏性問題，為提高推薦性能做好準備。

3.2 評估標準

運行算法3.2，首先采用imp[14]方法對推薦結果進行評估。運用“leave one out”方法，對任意指定資源，即文獻，先將其對應的（用戶-標簽-資源）組從推薦列表中移除，再分別運行基于標簽的協同過濾推薦算法及增加聚類后的推薦算法，檢查提出的推薦算法能否提高該篇文獻在推薦列表中的排名。

在imp方法中，推薦算法的推薦資源數目沒有限制。推薦列表中如果有目標資源，排名等于它在列表里面的真實排名，如果沒有找到排名就等于∞。

其中，rb為協同過濾推薦算法推薦的目標資源的排名，rp為基于標簽聚類的算法推薦的目標資源的排名。

對所有測試用戶計算imp然后求出算術平均，可以看出，imp值越高，目標資源的排名越靠前，說明相應的算法的推薦效果越好。圖2是利用imp評測方法得到的實驗結果。本實驗中，應用標簽聚類的推薦算法α值為0.7的時候其結果最佳，而協同過濾推薦算法α值為0.2的時候最佳。從圖2中可以看出推薦結果的線形加權值對資源排名的影響，α值的過高或過低都影響算法的性能。同時能夠證明，基于標簽聚類的推薦系統確實可以提高目標資源的排名。

另外，我們對標簽聚類算法中的閾值limit進行不同的取值，通過對命中率[15]的比較來檢驗limit取值對命中率的影響及改進后的推薦算法是否能得到對命中文獻更高的排名。命中率是指系統為測試集中每個用戶做出正確推薦的概率，所謂一次正確推薦（命中）是指推薦列表中包含被去除的那篇文獻。命中率定義為如下公式：

其中hit表示對測試集中用戶做出的推薦列表包含被去除的文獻的次數，testset表示測試用戶集的大小。圖3是命中率的實驗結果。從圖中可以看出，增加標簽聚類后的命中率要比一般協同過濾方法的高，而且當閾值limit取值為0.3時，命中率是最高的。

綜上所述，和一般推薦方法相比，基于標簽聚類的方法可優化指定文獻在推薦列表中的排名，能達到較好的效果，驗證了算法的有效性。

4 存在的問題及展望

本文通過計算標簽相似度，實現了一種標簽聚類算法，在此基礎上提出推薦算法進行個性化推薦。通過實驗證明，和傳統的協作過濾算法相比較，該方法有比較明顯的改進，驗證了標簽聚類在Folksonomy個性化服務中確實能夠有效提高推薦服務質量。未來工作將繼續優化標簽的聚類方法，并能夠運用在個性化推薦服務系統中，提高推薦個性化服務質量。

參考文獻

[1]R.Jaschke，L.Marinho，A.Hotho，L.Schmidt-Thieme，and G.Stumme.Tag Recommendations in Folksonomies.Lecture Notes In Computer Science，4702：506，2007.

[2]A.Hotho，R.Jaschke，L.Schmidt-Thieme，and G.Stumme.FolkRank：A Ranking Algorithm for Folksonomies.In Proc.FGIR，2006.

[3]R.Nakamoto，S.Nakajima，J.Miyazaki，and S.Uemura.Tag-based Contextual Collaborative Filtering.In 18th IEICE Data Engineering Workshop，2007.

[4]J Wang，Arjen P.de Vries，Marcel J.T.Reinders.Unifying User-based and Item-based Collaborative Filtering Approaches by Similarity Fusion，sigir 06.

[5]S.Zhao，N.Du，A.Nauerz，X.Zhang，Q.Yuan，and R.Fu.Improved Recommendation based on Collaborative Tagging Behaviors.IUI08，January 13-16，2008，Maspalomas，Gran Canaria，Spain.

[6]PanagiotisSymeonidis，AlexandrosNanopoulos，YannisManolopoulos.Tag recommendations based on tensor dimensionality reduction.In RecSys08，October 23-25，2008，Lausanne，Switzerland.

[7]Cui Jianwei，Liu Hongyan，He Jun，et al.Tagclus：A random walk based method for tag clustering[J].Knowledge and Information Systems，2011，27（2）：193-225.

[8]Begelman G，Keller P，Smadja F.Automated tag clustering：Improving search and exploration in the tag space[C].Collaborative Web Tagging Workshop at WWW2006.Edinburgh：ACM，2006：15-33.

[9]Knautz K，Soubusta S，Stock W G.Tag clusters as information retrieval interfaces[C].Proceedings of the 43rd Hawaii International Conference on System Sciences.Big Island，Hawaii：IEEE Computer Society Press，2010：1-10.

[10]王萍，張際平.一種社會性標簽聚類算法[J].計算機應用與軟件，2010，27（2）：126-129.

[11]P.Heymann and H.Garcia-Molina.Collaborative Creation of Communal Hierarchical Taxonomies in Social Tagging Systems.Technical report，Technical Report 2006-10，Computer Science Department，April 2006.

[12]Xu Guandong，Zong Yu，Jin Ping，et al.KIPTC：A kernel information propagation tag clustering algorithm[J].Journal of Intelligent Information Systems，2013：1-18.

[13]Shepitsen A，Gemmell J，Mobasher B，et al.Personalized recommendationin social tagging systems using hierarchical clustering[C].Proceedings of the 2008 ACM Conference on Recommender Systems.New York：ACM，2008：259-266.

[14]Ellen M.Voorhees.The TREC-8 Question Answering Track Report.Proceedings of TREC8：77-82，1999.

[15]S.McNee，I.Albert，D.Cosley，P.Gopalkrishnan，S.K.Lam，A.M.Rashid，J.A.Konstan，J.Riedl.On the Recommending of Citations for Research Papers.In Proceedings of the ACM 2002 Conference on Computer Supported Cooperative Work（CSCW 2002），New Orleans，LA，2002：116-125.