一種基于標簽譜聚類的協同過濾推薦算法研究

張震雷，崔蘋，楊新凱

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

0 引言

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

1 相關研究現狀

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

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

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

2 基于標簽譜聚類的協同過濾推薦策略

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

2.1 標簽譜聚類

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

最終得到一個共現相似度矩陣[6]。

2.2 基于標簽簇的用戶分組

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

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

2.3 組內用戶相似度

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

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

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

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

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

2.4 TSCF算法描述

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

圖1 改進算法流程圖

3 實驗及分析

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

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

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

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

圖2 不同標簽簇時的模塊度值

（1）準確率和召回率

表1 準確率、召回率

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

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

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

（3）運行效率

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

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

4 結語

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