一種基于標(biāo)簽譜聚類的協(xié)同過濾推薦算法研究

張震雷，崔蘋，楊新凱

（上海師范大學(xué)信息與機電工程學(xué)院，上海200234）

0 引言

日新月異的互聯(lián)網(wǎng)技術(shù)使信息爆炸式地增長。與此同時，信息過載（Information Overload）的問題日益突出，用戶如何在互聯(lián)網(wǎng)浩如煙海的資源中快速有效地獲取高質(zhì)量的信息就成為了亟待解決的問題。搜索引擎的出現(xiàn)，在一定程度上滿足了用戶查找信息的需求。然而，很多時候用戶找不到精確的關(guān)鍵詞來描述目標(biāo)信息，無論是信息的生產(chǎn)者還是消費者，都需要讓“信息智能地去找人”。于是，推薦系統(tǒng)（Recommenda?tion System）應(yīng)運而生，近幾年來該技術(shù)在電子商務(wù)、音樂視頻、新聞旅游等領(lǐng)域均有廣泛應(yīng)用。但是在如今動輒數(shù)以TB的互聯(lián)網(wǎng)環(huán)境中，數(shù)據(jù)的稀疏性和復(fù)雜性對推薦系統(tǒng)的精度提出了新的挑戰(zhàn)。

1 相關(guān)研究現(xiàn)狀

協(xié)同過濾（Collaborative Filtering）是推薦領(lǐng)域較為成熟的技術(shù)之一。當(dāng)前，這種方法存在兩個主要問題：第一，數(shù)據(jù)稀疏性致使構(gòu)建近鄰集合的開銷增大，影響推薦的效率；第二，僅僅通過用戶評分計算出的相似度精度不夠，致使推薦準(zhǔn)確度遇到瓶頸。

為了克服數(shù)據(jù)稀疏性，降低近鄰搜索空間,聚類是一個不錯的選擇。Li等人提出了一種基于用戶模糊聚類的推薦策略[1]，Ren等人提出了一種基于項目聚類的協(xié)同過濾方案[2]。為了進一步縮小近鄰搜索空間，Gong SJ提出了一種基于用戶和物品的聯(lián)合聚類協(xié)同過濾算法。這些方法在一定程度上改善了數(shù)據(jù)稀疏性，但是傳統(tǒng)的聚類方法在數(shù)據(jù)劇增時因計算而產(chǎn)生的開銷巨大。

針對用戶相似性計算精度的問題，現(xiàn)有的方法往往使用人口統(tǒng)計學(xué)信息。但是隨著用戶對隱私意識的加強，系統(tǒng)通常無法獲取足夠的人口統(tǒng)計學(xué)信息。標(biāo)簽（Tag）作為組織管理信息的一種方式，已經(jīng)成為大型網(wǎng)站的標(biāo)配。Hotho等人把用戶、資源、標(biāo)簽之間的關(guān)系作為無向三部圖來研究[3]；Rendle等人提出了一種基于用戶-資源-標(biāo)簽的張量分解方法，并使用梯度下降法對該方法做出了優(yōu)化[4]；Reyn等人利用標(biāo)簽相似度，構(gòu)建一種基于情景的協(xié)同過濾推薦。這些方法都考慮了標(biāo)簽在挖掘用戶興趣時的作用，但是忽略了最終的推薦效率。

2 基于標(biāo)簽譜聚類的協(xié)同過濾推薦策略

鑒于以上問題，本文從實際出發(fā)提出一種基于標(biāo)簽譜聚類的協(xié)同過濾推薦算法（Tag Spectral-cluster based Collaborative Filtering，TSCF）。該方法首先使用譜聚類技術(shù)把UGC標(biāo)簽聚合成若干簇，然后根據(jù)用戶基于標(biāo)簽簇的信任度，把用戶分成若干用戶組，同時在用戶組內(nèi)利用基于標(biāo)簽的用戶信任度修正用戶相似度，進而改善推薦系統(tǒng)的整體性能。這種方法大體可以分為三大步。

2.1 標(biāo)簽譜聚類

UGC標(biāo)簽是用戶產(chǎn)生的內(nèi)容（User Generated Con?tent），它描述了資源的特征，又代表了用戶對資源的主觀感受。由于UGC標(biāo)簽的開放性，其一詞多義會影響最終的推薦精度[5]。本文采用譜聚類（SpectralCluster）算法對UGC標(biāo)簽降維去噪。相較于別的聚類算法，譜聚類算法具有適應(yīng)性強，計算量小，易于實現(xiàn)，聚類效果好等優(yōu)點。本文通過對標(biāo)簽的個體相似度（Individu?al Similarity）和群體相似度（Group Similarity）線性加權(quán)后得到標(biāo)簽的共現(xiàn)相似度（Common Similarity）：

最終得到一個共現(xiàn)相似度矩陣[6]。

2.2 基于標(biāo)簽簇的用戶分組

標(biāo)簽譜聚類之后，就得到了k個標(biāo)簽簇，不同的標(biāo)簽簇代表不同的用戶興趣?；趉個標(biāo)簽簇，可以把所有用戶劃分成k個用戶組，d(ua)表示用戶ua使用標(biāo)簽的次數(shù)，d(ua,Cj)表示用戶ua使用Cj標(biāo)簽簇中標(biāo)簽的次數(shù)，故此可以定義用戶ua的對標(biāo)簽簇Cj的興趣度In?tcj(ua)：

然后把Ua歸入Intcj最大的用戶組。當(dāng)然同一用戶可能對不同標(biāo)簽簇的偏好相同，則把該用戶同時歸入不同的用戶組。這樣，按照“人以群分”的原則就把用戶劃歸到k個用戶組中。

2.3 組內(nèi)用戶相似度

使用用戶u，v之間基于標(biāo)簽的信任度來修正二者之間的相似度，修正之后如下：

其中，cos(u,v)是協(xié)同過濾中基于用戶(二值化)評分的余弦相似度，可以用式（4）來計算：

其中N(u)表示用戶u評價過的物品。接著，我們可以構(gòu)建目標(biāo)用戶ua的近鄰集合，并完成top N推薦。針對同時屬于多個用戶組的用戶，可以綜合該用戶在各用戶組中的top N列表，票選出得分最高的物品作為推薦，這種做法在一定程度上可以提升推薦的多樣性。

由于標(biāo)簽簇數(shù)k太大太小都會對最終的推薦結(jié)果造成影響。結(jié)合社區(qū)劃分理論本文設(shè)計一個模塊度函數(shù)[7]，通過一次實驗就可以自動確定合適的標(biāo)簽簇數(shù)，模塊度函數(shù)定義如式（5）：

其中S(Cj,Cj)表示第j個簇內(nèi)的所有標(biāo)簽綜合共現(xiàn)相似度之和，S(C,C)則表示相似性矩陣所有元素之和，S(Cj,C)則表示Cj簇中的所有標(biāo)簽到其他簇中標(biāo)簽的權(quán)重之和。

2.4 TSCF算法描述

改進后的算法過程如圖1：

圖1 改進算法流程圖

3 實驗及分析

本文選用ACM第五屆推薦大會（RecSys2011）公布的Last.fm數(shù)據(jù)集（網(wǎng)址：http://recsys.acm.org/2011），這個數(shù)據(jù)集包含了1892名注冊用戶，17632名歌手，11946個標(biāo)簽以及186479個標(biāo)簽標(biāo)注行為，此外還有12717對雙向好友關(guān)系，數(shù)據(jù)較為完整，具有較高的學(xué)術(shù)科研價值。

首先剔除活躍度較低的用戶以及流行度較低的歌手，過濾掉明顯虛假的信息，得到一個高質(zhì)量的核心數(shù)據(jù)子集，然后使用一次模塊度函數(shù)，對標(biāo)簽譜聚類。

當(dāng)k=1時，Q(k)最小，說明聚類效果最差，因為相當(dāng)于沒有進行聚類，這和實際相符。在Last.fm的核心數(shù)據(jù)集上，當(dāng)k=2時，模塊度最大,所以本文把標(biāo)簽聚成兩簇。

為了驗證TSCF算法的有效性，將與基于用戶的協(xié)同過濾（UserCF）和基于用戶聚類（KmeansCF）的推薦算法，從準(zhǔn)確率、召回率、覆蓋率、多樣性、流行度以及計算時間等六個方面對比說明。依次取近鄰集合大小為k=5,10,15,20,25,30,35，標(biāo)簽簇數(shù)為K=2，推薦列表長度為20。

圖2 不同標(biāo)簽簇時的模塊度值

（1）準(zhǔn)確率和召回率

表1 準(zhǔn)確率、召回率

由于使用了基于標(biāo)簽簇的用戶信任度對原有用戶相似度進行修正。如表1所示，本文提出的TSCF算法的準(zhǔn)確率和召回率，相較于UserCF算法和KmeansCF算法都有了明顯提升。

（2）多樣性、覆蓋率和平均流行度

基于標(biāo)簽簇對用戶分組之后，有些用戶有可能會被同時分到若干個組中。這與實際情況相符，標(biāo)簽簇描述的是用戶的興趣，而有些用戶的興趣是多樣的。觀察圖2，可以發(fā)現(xiàn)，TSCF方法可以提高系統(tǒng)的多樣性和覆蓋率，相較于KmeansCF聚類，多樣性提升不是非常明顯。

（3）運行效率

譜聚類算法對大型稀疏矩陣劃分時只需要求出前k個特征值即可，所以計算效率較為高效。由下面的time折線圖可以看出，TSCF算法的效率比UserKmeans方法的效率提高了將近一倍。往往為了取得較好的聚類效果，K-means的迭代次數(shù)遠(yuǎn)遠(yuǎn)要大于上述設(shè)定的10次，由此可見，KmeansCF算法是相對耗時間的。

圖3 多樣性、覆蓋率、流行度、運行時間

4 結(jié)語

本文提出了一種基于標(biāo)簽譜聚類的協(xié)同過濾推薦策略（TSCF）。首先，該方法結(jié)合用戶UGC標(biāo)簽來挖掘用戶興趣，提高了推薦精度；其次，把關(guān)聯(lián)度較高的用戶分到同一組，在組內(nèi)完成推薦，可以縮減近鄰搜索空間，提升推薦效率和多樣性，緩解數(shù)據(jù)稀疏性帶來的弊端。最后，在仿真環(huán)境中，通過對比試驗驗證了TSCF推薦策略的有效性。本文下一步計劃，準(zhǔn)備在不影響推薦性能的同時，結(jié)合評價指標(biāo)設(shè)計一個更為合理的評價函數(shù)，確定用戶組數(shù)k。