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

劉如娟

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

〔關(guān)鍵詞〕社會化網(wǎng)絡(luò)；社會標(biāo)簽系統(tǒng)；標(biāo)簽聚類；用戶模型；個性化推薦

〔中圖分類號〕G250.73 〔文獻(xiàn)標(biāo)識碼〕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時代，用戶不僅是內(nèi)容的瀏覽者，同時也是內(nèi)容的創(chuàng)造者。由于網(wǎng)絡(luò)信息的爆炸式增長，用戶常常在海量信息中無法快速找到自己需要的資源。目前，大多數(shù)Web2.0網(wǎng)站都提供了社會標(biāo)簽系統(tǒng)，例如：Delicious，Last.fm，F(xiàn)lickr，CiteULike以及豆瓣網(wǎng)等。在這些網(wǎng)站中，用戶可以按照自己的理解，自由地用標(biāo)簽對自己感興趣的資源進(jìn)行標(biāo)注。同時，用戶還可以根據(jù)標(biāo)簽對資源進(jìn)行訪問，并且可以利用對自己感興趣的其他人所做的標(biāo)簽去發(fā)現(xiàn)一些自己感興趣的新資源。用戶在標(biāo)注資源時所使用的標(biāo)簽既反映了用戶自身的興趣愛好，又反映了資源的特點。作為聯(lián)系用戶和資源的紐帶，標(biāo)簽是反映用戶數(shù)據(jù)的重要數(shù)據(jù)源。因此可以利用用戶在標(biāo)注資源時所使用的標(biāo)簽為用戶推薦其所需要的資源。

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

近幾年來，基于標(biāo)簽數(shù)據(jù)的推薦方法研究獲得了學(xué)術(shù)界廣泛的關(guān)注，如何利用用戶標(biāo)簽數(shù)據(jù)設(shè)計高效準(zhǔn)確的個性化推薦算法，為用戶提供適合其個性化需求的資源和標(biāo)簽，已經(jīng)成為個性化推薦研究領(lǐng)域重要的研究內(nèi)容之一。

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

文章結(jié)構(gòu)如下：第一部分對本文的研究內(nèi)容進(jìn)行簡單介紹。第二部分對國內(nèi)外研究現(xiàn)狀進(jìn)行介紹。第三部分描述本文采用的標(biāo)簽推薦算法，通過標(biāo)簽聚類提高推薦系統(tǒng)的性能，實現(xiàn)資源推薦。第四部分的實驗設(shè)計評測指標(biāo)驗證該推薦系統(tǒng)各方面的性能。第五部分總結(jié)全文并且對未來工作進(jìn)行展望。

1 國內(nèi)外研究現(xiàn)狀

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

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

文獻(xiàn)[7]提出了一種基于資源共現(xiàn)的隨機(jī)游走方法來聚類標(biāo)簽；文獻(xiàn)[8]利用標(biāo)簽共現(xiàn)的分布相似性來增強(qiáng)標(biāo)簽相關(guān)性，結(jié)合遞歸貪婪算法和模塊化函數(shù)實現(xiàn)了標(biāo)簽的聚類；文獻(xiàn)[9]介紹了一種基于資源共現(xiàn)的標(biāo)簽單鏈接層次聚類算法來提高信息檢索的效率；文獻(xiàn)[10]通過建立標(biāo)簽共現(xiàn)網(wǎng)絡(luò)，提出了一種基于標(biāo)簽相似性的聚類算法對標(biāo)簽共現(xiàn)網(wǎng)絡(luò)進(jìn)行分割，并建立標(biāo)簽聚類簇。

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

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

2 基于標(biāo)簽聚類的個性化推薦

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

表1展現(xiàn)了利用上述公式計算出的CiteULike數(shù)據(jù)集中recommendersystem標(biāo)簽的相關(guān)標(biāo)簽及對應(yīng)的相似度。

2.2 標(biāo)簽聚類算法

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

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

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

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

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

通過算法3.1，這樣可以完成社會化標(biāo)簽的聚類。經(jīng)過聚類，聚類數(shù)目能夠遠(yuǎn)遠(yuǎn)小于基本標(biāo)簽的數(shù)目，即kn。后續(xù)的實驗將對該方法進(jìn)行驗證。

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

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

3 實驗評測

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

3.1 數(shù)據(jù)處理

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

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

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

3.2 評估標(biāo)準(zhǔn)

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

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

其中，rb為協(xié)同過濾推薦算法推薦的目標(biāo)資源的排名，rp為基于標(biāo)簽聚類的算法推薦的目標(biāo)資源的排名。

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

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

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

綜上所述，和一般推薦方法相比，基于標(biāo)簽聚類的方法可優(yōu)化指定文獻(xiàn)在推薦列表中的排名，能達(dá)到較好的效果，驗證了算法的有效性。

4 存在的問題及展望

本文通過計算標(biāo)簽相似度，實現(xiàn)了一種標(biāo)簽聚類算法，在此基礎(chǔ)上提出推薦算法進(jìn)行個性化推薦。通過實驗證明，和傳統(tǒng)的協(xié)作過濾算法相比較，該方法有比較明顯的改進(jìn)，驗證了標(biāo)簽聚類在Folksonomy個性化服務(wù)中確實能夠有效提高推薦服務(wù)質(zhì)量。未來工作將繼續(xù)優(yōu)化標(biāo)簽的聚類方法，并能夠運用在個性化推薦服務(wù)系統(tǒng)中，提高推薦個性化服務(wù)質(zhì)量。

參考文獻(xiàn)

[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]王萍，張際平.一種社會性標(biāo)簽聚類算法[J].計算機(jī)應(yīng)用與軟件，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.