張震雷，崔蘋(píng)，楊新凱

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

0 引言

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

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

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

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

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

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

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

2.1 標(biāo)簽譜聚類(lèi)

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

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

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

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

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

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

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

其中，cos(u,v)是協(xié)同過(guò)濾中基于用戶(hù)(二值化)評(píng)分的余弦相似度，可以用式（4）來(lái)計(jì)算：

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

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

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

2.4 TSCF算法描述

改進(jìn)后的算法過(guò)程如圖1：

圖1 改進(jìn)算法流程圖

3 實(shí)驗(yàn)及分析

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

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

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

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

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

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

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

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

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

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

（3）運(yùn)行效率

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

圖3 多樣性、覆蓋率、流行度、運(yùn)行時(shí)間

4 結(jié)語(yǔ)

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