一種基于特征的協(xié)同聚類模型

張 飛 張立波 羅鐵堅 武延軍

1(中國科學(xué)院大學(xué) 北京 101408) 2 (中國科學(xué)院軟件研究所 北京 100190) (tjluo@ucas.ac.cn)

互聯(lián)網(wǎng)的蓬勃發(fā)展促使信息總量呈現(xiàn)指數(shù)上升，這使得互聯(lián)網(wǎng)用戶從龐雜的信息中獲取有用的信息變得越來越困難.推薦系統(tǒng)能夠根據(jù)用戶的特點和興趣有針對性地為他們推薦有價值的信息.因此推薦系統(tǒng)的作用越來越突出，已經(jīng)被應(yīng)用到商品推薦等諸多領(lǐng)域中.

協(xié)同過濾(collaborative filtering, CF)[1-3]算法是推薦系統(tǒng)中一種被廣泛采用的算法.與傳統(tǒng)基于內(nèi)容(content-based)[4]的推薦算法不同，協(xié)同過濾算法不需要用戶的個人資料以及物品本身的信息，僅僅利用用戶和物品之間的交互關(guān)系(如點擊、瀏覽、評分等)就能做出準(zhǔn)確的推薦.在用戶越來越重視個人信息安全的形勢下，協(xié)同過濾算法相比基于內(nèi)容的推薦算法具有更大的優(yōu)勢.

傳統(tǒng)的協(xié)同過濾算法在取得一定性能的同時仍然存在一些問題.例如數(shù)據(jù)的高稀疏性使得算法的推薦性能難以提高，對此研究人員提出一種基于聚類的協(xié)同過濾算法，通過對用戶和物品進行聚類，將有相同愛好的用戶和相同特征的物品分為一組，然后在各個分組上分別利用協(xié)同過濾算法進行推薦.但是，大部分聚類方法都只允許用戶或者物品屬于一個分組，而現(xiàn)實中一個用戶可能有多種愛好并且一個物品可能具備多種特征，因此只允許用戶和物品屬于一個分組具有很大的局限性.

基于上述考慮，本文提出了一種基于特征的協(xié)同聚類模型，它充分利用用戶與物品之間的交互信息來挖掘它們的潛在特征，并根據(jù)這些特征將他們分配到合適的多個分組中.例如某用戶同時喜歡喜劇電影與動作電影，則應(yīng)該將該用戶分配到喜劇和動作這2個分組中去.這種聚類方式充分利用了用戶和物品的特征，使得聚類的結(jié)果更加可信.最后將本文算法得到的聚類結(jié)果使用傳統(tǒng)的協(xié)同過濾算法進行推薦，通過與多種最新算法在3種公開數(shù)據(jù)集上的比較，驗證了本文提出的模型能夠顯著提高預(yù)測與推薦的準(zhǔn)確度.

本文的主要貢獻有2個方面：

1) 提出一種快速提取用戶以及物品特征的方法以及給出該方法的求解過程；

2) 提出一種圖模型將用戶評分信息與特征信息結(jié)合，用來計算最終的聚類結(jié)果.

1 相關(guān)工作

Breese等人[5]將協(xié)同過濾推薦算法分為2種類型:基于內(nèi)存(memory-based)的協(xié)同過濾算法與基于模型(model-based)的協(xié)同過濾算法.

基于內(nèi)存的協(xié)同過濾算法主要是通過尋找用戶[6]或者物品[7]之間的相似性來進行推薦，雖然這種推薦系統(tǒng)實現(xiàn)簡單并且很有效，但是它還存在很多問題，比如無法有效處理大規(guī)模數(shù)據(jù)以及高稀疏性的數(shù)據(jù).為了解決基于內(nèi)存的協(xié)同過濾算法的這種問題，許多基于模型的協(xié)同過濾算法被提出，比如貝葉斯模型[8]、基于回歸的模型[9]、潛在語義模型[10]、聚類模型[11-12]和矩陣分解模型[13].在這些模型中，矩陣分解模型被廣泛使用，比如著名的SVD(singular value decomposition)[14]模型、NMF(non-negative matrix factorization)[15]模型、MMMF(maximum margin matrix factorization)[16]、NPCA(nonparametric probabilistic principal component analysis)[17]等，它們在處理大規(guī)模數(shù)據(jù)時有著杰出的表現(xiàn)，但是推薦系統(tǒng)數(shù)據(jù)高稀疏性的特點仍舊限制了這些算法性能.

為了克服數(shù)據(jù)的高稀疏性等問題，基于聚類的協(xié)同過濾算法被提出.聚類的協(xié)同過濾算法首先將用戶與物品進行適當(dāng)?shù)木垲惙纸M，然后在每個分組上分別使用協(xié)同聚類算法進行推薦.由于互聯(lián)網(wǎng)的發(fā)展，越來越多的算法在對用戶物品進行聚類時，加入了很多額外的信息來增強聚類性能[18-22]，比如產(chǎn)品分類信息[23]、用戶信任網(wǎng)絡(luò)[24]等.但是這些額外的信息有時候并不能增加聚類的準(zhǔn)確度，比如某用戶購買了某件商品，他的好友們可能不會對這件商品感興趣，因此本文的聚類過程僅僅使用了隱式反饋信息，如用戶物品評分.這種只使用隱式反饋信息的聚類算法一般分為3種:基于用戶的聚類、基于物品的聚類以及雙側(cè)聚類.

基于用戶的聚類算法是根據(jù)用戶的相似度將最相似的若干用戶分為一組，在為具體的用戶進行推薦時只考慮用戶所在的分組.例如Sarwar等人[25]就是將全部的用戶根據(jù)相似度進行聚類，并將每一個聚類結(jié)果中的用戶視為鄰居；Xue等人[26]則是通過訓(xùn)練數(shù)據(jù)將用戶進行聚類，為每個用戶挑選出最好的若干鄰居并學(xué)習(xí)出預(yù)測矯正信息，然后利用這些矯正信息以及鄰居來為具體的用戶進行推薦；相反，基于物品的聚類算法則是根據(jù)物品之間的相似度來進行聚類，例如O’Connor等人[27]提出的方法.

除了上述的一些單側(cè)聚類算法外，還有一些基于雙側(cè)聚類的聚類算法，這與本文的主要方法一致，Ungar等人[28]通過使用吉比斯采樣與k-means方法對用戶與物品進行聚類，該方法在模擬數(shù)據(jù)上有一定的效果，但是在真實數(shù)據(jù)上卻不樂觀；George等人[29]則是對用戶物品同時聚類，然后根據(jù)聚類分組中的平均打分以及用戶自身的矯正量來進行最后的推薦；除了以上這些單類聚類算法外，Xu等人[30]還提出了一種多類協(xié)同聚類算法，它與本文核心思想一致：允許用戶和物品同時屬于多個分組.但是它的聚類原理比較片面，僅僅考慮用戶對物品的評分而忽略了用戶自身的特點與物品自身的特點.

2 基于特征的協(xié)同聚類模型

本文提出的基于特征的協(xié)同聚類算法主要框架及其在推薦系統(tǒng)中的作用如圖1所示，主要包括2個模塊：1)一個特征表示模型，用來挖掘用戶的興趣以及物品的特征;2)一個圖模型，利用挖掘出來的特征以及用戶的評分信息計算最終的聚類結(jié)果.在推薦系統(tǒng)中，可以先利用本文算法完成數(shù)據(jù)的聚類工作，再將聚類的結(jié)果應(yīng)用到推薦模型中，從而提高最終的推薦性能.

2.1 相似度的計算

通過圖1可以發(fā)現(xiàn)在本文模型中需要計算用戶相似度與物品相似度，在推薦系統(tǒng)中，著名的基于相似度的推薦算法如Item-Based[7]，User-Based[6]等所采用的相似度算法主要是余弦相似度、Pearson相關(guān)系數(shù)以及約束Pearson相關(guān)系數(shù)等，它們的計算方法如表1所示.

從表1可以看出，當(dāng)Ist=?時,也即用戶s和t之間不存在共同打分過的物品，那么這3種相似度算法都無法計算s和t的相似度;另一方面當(dāng)2個用戶共同打分過的物品較少甚至只有1個時，僅僅利用這些少量的打分信息來判斷用戶之間的相似度顯然是不夠準(zhǔn)確的.而在推薦系統(tǒng)中，其數(shù)據(jù)的高稀疏性是其最大的特點，2個用戶之間共同打分過的物品集合Ist往往都比較少甚至為空，因此，采用上述方法計算得到的相似度不夠可靠，為了解決這個問題，本文采用一種新的特征表示模型來挖掘用戶以及物品的特征信息，然后用這些特征信息來計算相似度，我們將在2.2節(jié)討論如何提取特征.

Table 1 Measures of Similarity[31]表1 相似度的計算方法[31]

2.2 特征信息的提取

在本節(jié)我們將介紹圖1中的特征表示模塊，該部分用來提取用戶與物品的特征以便計算它們的相似度.

設(shè)n個用戶對m個物品的評分矩陣為T∈n×m，用戶的特征信息矩陣為U∈n×a，其中第u行的a維行向量Uu表示第u個用戶的特征信息向量,a為一個較小的指定的特征信息維度;同樣地，用矩陣V∈m×b表示全部物品的特征信息矩陣，b表示物品特征信息的維度.我們將通過二次回歸模型用第u個用戶的特征信息Uu以及第v個物品的特征信息Vv去擬合評分Tu v.

在傳統(tǒng)的二次回歸模型中，對于特征向量x，其對應(yīng)的監(jiān)督值y通過表達式去擬合：

(1)

其中,z表示常數(shù)項系數(shù)，w表示一次項系數(shù)，W表示二次項系數(shù)，l則表示向量x的維度.則在本文的模型中，顯然有x=(Uu,Vv)，y=Tu v，于是得到：

(2)

我們令：

(3)

(4)

可以觀察到，pu只和用戶u有關(guān)，qv只和物品v有關(guān)，于是我們得到最終的二次回歸模型：

(5)

注意到此處我們重新定義W∈a×b.式(5)表示用戶u對物品v的評分可近似由1個全局常數(shù)z、1個與用戶有關(guān)的常數(shù)pu、1個與物品有關(guān)的常數(shù)qv、以及他們的特征元素之間的兩兩乘積的加權(quán)和組成.所以，我們可以令z為整個數(shù)據(jù)集評分的均值，令pu為用戶u的全部評分的均值，令qv為物品v被評分的均值，即：

(6)

(7)

(8)

其中,當(dāng)Tu v=0時表示用戶u對物品v的評分不存在，此時δu v=0，否則δu v=1.

根據(jù)式(5)我們可以得到模型的擬合誤差：

(9)

優(yōu)化式(9)使得L最小即可得到我們所需的特征信息矩陣U和V.我們利用隨機梯度下降法求解，并設(shè)學(xué)習(xí)率為η，我們得到參數(shù)更新公式：

(12)

下面給出本文提取特征的算法的偽代碼，如算法1所示：

算法1. 特征提取算法.

輸入：評分矩陣T、參數(shù)n,m,a,b,η；

輸出：矩陣U,V.

① 隨機初始化W,U,V；

② 根據(jù)式(6)計算z；

③ foru=1 tondo

④ 根據(jù)式(7)計算pu；

⑤ end for

⑥ forv=1 tomdo

⑦ 根據(jù)式(8)計算qv；

⑧ end for

⑨ repeat

最終得到U,V矩陣即可表示為用戶和物品的特征信息矩陣，然后利用表1中的相似度算法就能夠得到用戶以及物品的特征信息相似度.

2.3 圖模型的構(gòu)建

在本節(jié)我們將介紹圖1中的圖模型模塊，將2.2節(jié)計算得到的相似度與用戶的評分信息結(jié)合構(gòu)建出一個無向圖，利用它來計算最終的聚類結(jié)果.

在我們的圖模型中，所有的頂點由用戶和物品組成，邊則分別由3部分構(gòu)成:用戶相似度、物品相似度以及用戶對物品的評分.另外，為了強調(diào)高評分在圖中的重要性，有變換函數(shù)：

f(Tu v)=(1+e-τ(Tu v-Tmed))-1，

(13)

其中,Tmed表示評分制的中值，τ為超參數(shù).該函數(shù)的作用是將中值映射為權(quán)重值0.5，當(dāng)評分高于中值時，表示用戶對該物品有喜歡的傾向，因此在聚類中應(yīng)該有較高權(quán)重，但同時弱化高評分之間的差距，比如4分與5分的權(quán)重差距顯然應(yīng)該小于4分與3分之間的差距，同理，評分小于中值時應(yīng)該具有較低的權(quán)重，且同樣需要弱化低評分之間的權(quán)重差距.

因此，該圖模型的構(gòu)建過程如下:

1)n個用戶與m個物品組成n+m個節(jié)點，用戶節(jié)點編號為1,2,…,n，物品節(jié)點表示為編號n+1,n+2,…,n+m，第v個物品編號為n+v；

2) 用戶u與物品v之間邊的權(quán)值定義為Wu(n+v)=f(Tu v)；

3) 用戶i與用戶j之間邊的權(quán)值定義為Wi j=α×sim(Ui,Uj)，其中α表示放縮因子，其目的是為了均衡用戶評分所轉(zhuǎn)化的權(quán)值與根據(jù)相似度得到的權(quán)值之間的差異，函數(shù)sim(Ui,Uj)表示用戶i與用戶j之間的特征信息相似度，可以采用表1中的相似度算法計算，本文采用的是余弦相似度算法；

4) 物品i與物品j之間邊的權(quán)值定義為W(n+i)(n+j)=β×sim(Vi,Vj)，函數(shù)sim(Vi,Vj)表示物品i與物品j之間的特征信息相似度，參數(shù)β也是放縮因子，為了平衡物品相似度與評分權(quán)值之間的差異.

通過上述步驟構(gòu)建好圖模型后，便得到該無向圖的權(quán)值矩陣W∈(n+m)×(n+m)，下面討論如何利用它得到最終的聚類結(jié)果.

2.4 聚類結(jié)果的計算

顯然，在2.3節(jié)的圖模型中，權(quán)值越大的邊對應(yīng)的2個頂點，表明用戶對該物品更加關(guān)注或者用戶之間、物品之間更加相似，它們應(yīng)該更有可能被分在同一組中，即它們在矩陣P中對應(yīng)的2行行向量近似.有損失函數(shù):

(14)

本文利用Belkin等人[32]的方法來求解式(14)，首先我們定義對角型矩陣D∈(n+m)×(n+m)，其元素Di i為矩陣W的第i行之和，即:

(15)

則將式(14)展開并經(jīng)過一定的線性變換，得到:

ε(P)=2tr(PT(D-W)P).

(16)

因此,要使得ε(P)最小，則只需要找到一個矩陣P，使其滿足PT(D-W)P的跡最小.為了使得最優(yōu)化問題式(14)有解并且使得解空間的維度不低于c，我們對矩陣P進行限制:

PTDP=I.

(17)

經(jīng)過上述討論，聚類結(jié)果的評價矩陣P的求解轉(zhuǎn)化為求解滿足式(17)的矩陣P，使得PT(D-W)P的跡最小.根據(jù)文獻[32]，這樣的矩陣P應(yīng)當(dāng)是由矩陣D-W的前c個非0最小特征根對應(yīng)的特征向量組成的.則可以根據(jù)(D-W)p=λDp求得矩陣D-W的廣義特征根，其中p為廣義特征根λ對應(yīng)的廣義特征向量.最后，將前c個非0最小特征根對應(yīng)的特征向量組成的矩陣P即為所求.

得到用戶和物品的評價分布矩陣后，再根據(jù)評價值的大小確定某個用戶或者物品所屬的分組.在本文的算法中，只要用戶或者物品對某個分組持有正的評價值，則將該用戶或者物品分配到該分組中去，這樣便得到了最終的聚類結(jié)果.

2.5 推薦結(jié)果的生成

如圖2所示，圖2(a)表示非聚類的協(xié)同過濾算法生成推薦結(jié)果的流程，它直接將原始的用戶評分矩陣通過協(xié)同過濾算法進行計算，得到用戶對其他物品的預(yù)測評分從而進行推薦;而在基于聚類的協(xié)同過濾算法中，如圖2(b)所示，首先利用聚類算法對原始的用戶評分矩陣進行聚類，得到若干聚類分組，然后對每個聚類分組分別使用傳統(tǒng)推薦方法得到在這些分組上的推薦結(jié)果，最后，將所有分組得到的推薦結(jié)果進行匯總即得到最終的推薦結(jié)果.在將各個分組上的推薦結(jié)果匯總的過程中，由于聚類算法允許1個用戶或者物品屬于多個分組，因此可能會存在1個用戶與1個物品同時屬于2個不同分組但是預(yù)測得分不同，本文的處理方式為選擇用戶評價得分較高分組上的預(yù)測得分作為最終結(jié)果.

Fig. 2 The framework of the CF and clustering CF method圖2 協(xié)同過濾算法與聚類的協(xié)同過濾算法的推薦框架

3 實驗評估

3.1 數(shù)據(jù)集

本文的實驗將使用3個公開數(shù)據(jù)集來檢驗聚類模型的性能:

1) MovieLens-100K

由于大部分推薦系統(tǒng)規(guī)模較小，這類系統(tǒng)的數(shù)據(jù)表現(xiàn)為數(shù)據(jù)少、用戶平均打分?jǐn)?shù)量中等，因此本文選用了MovieLens-100K數(shù)據(jù)集，它來自于MovieLens網(wǎng)站上的用戶對電影的打分?jǐn)?shù)據(jù)，包含943個用戶對1 682部電影作品的近100 000條評分記錄，用戶的打分均為不大于5的正整數(shù).

2) MovieLens-1M

部分推薦系統(tǒng)較為成熟，積累了一定的用戶，但是物品品種類較為固定，因此此類推薦系統(tǒng)表現(xiàn)為用戶量較多、商品數(shù)量較少、平均用戶打分次數(shù)多.針對該系統(tǒng)的特點，本文選用了MovieLens-1M數(shù)據(jù)集，它與MovieLens-100K數(shù)據(jù)集來源相同，不同的是它更晚發(fā)布且擁有了更多的用戶與更多的評分記錄，它包含了6 040個用戶對3 952部電影的1 000 209條評分?jǐn)?shù)據(jù)，且每個用戶都至少對20部電影進行了打分.

3) Epinions

某些推薦系統(tǒng)表現(xiàn)為用戶量與商品量都是龐大的，但是卻只有很少的評分記錄，很難從中分析用戶喜好，因此，本文選用了Epinions數(shù)據(jù)集，該數(shù)據(jù)集包含了22 166個用戶對296 277個商品的打分信息，顯然，它比前2個數(shù)據(jù)集要大得多，但是，該數(shù)據(jù)集有很多用戶打分次數(shù)較少以及很多物品缺乏有價值的評分信息，因此，本文對該數(shù)據(jù)集進行了預(yù)處理，將打分次數(shù)低于10次的用戶從數(shù)據(jù)集中移除，同樣地，將被打分次數(shù)少于10次的商品也移除，最后，得到了21 109個用戶對13 957件商品的433 507條評分?jǐn)?shù)據(jù).

這3個數(shù)據(jù)集的統(tǒng)計信息如表2所示.其中，Sparsity表示評分矩陣中空元素(未評分)所占的比例，即：

Table 2 The Statistics of the Three Datasets表2 3個數(shù)據(jù)集的統(tǒng)計信息

從表2可以看出,MovieLens-100K數(shù)據(jù)集規(guī)模最小;MovieLens-1M數(shù)據(jù)集平均用戶打分次數(shù)最高，意味著信息更加豐富;而Epinions數(shù)據(jù)集最為稀疏，有著龐大的用戶與物品量卻擁有著較低的打分?jǐn)?shù)量.

3.2 評估指標(biāo)

在實驗性能的評估上，本文分別從預(yù)測性能與推薦性能2個方面進行測試.

1) 在預(yù)測性能上.本文采用推薦系統(tǒng)領(lǐng)域內(nèi)比較常用的平均絕對誤差(mean absolute error,MAE)指標(biāo)，其表達式為

2) 在推薦性能上.本文采用TopK推薦方法，即從預(yù)測結(jié)果中選出預(yù)測評分最高的K個物品并排序，然后比較選出的這K個物品與測試集中用戶最喜愛的K個物品的吻合程度.采用的評估指標(biāo)為歸一化折損累積增益(normalized discounted cumu-lative gain,NDCG)，對用戶u，其對應(yīng)NDCG計算為

其中,Nu表示測試集中用戶u的評分?jǐn)?shù)量，當(dāng)模型推薦結(jié)果的第i個物品出現(xiàn)在測試集中用戶的TopK列表中時，ri=1，否則ri=0.IDCG(ideal discounted cumulative gain)為常量，表示完美推薦時的累積增益，其表達式為

對所有用戶的NDCG求平均值，即為最終的評估指標(biāo)，顯然，NDCG值越大，表示模型性能越好.

3.3 評估方法與對比算法

如圖2(b)所示，利用本文算法進行推薦的過程是先將用戶以及物品進行聚類，再在每個不同的聚類小組上調(diào)用其他協(xié)同過濾推薦算法得到推薦結(jié)果.因此，本文對比方法為采用不同的聚類算法進行分組，然后在各種算法得到的聚類分組上調(diào)用同一種協(xié)同過濾推薦算法來對比最終的預(yù)測性能和推薦性能.

在協(xié)同過濾推薦算法的選擇上，本實驗選擇了當(dāng)下較為主流的推薦系統(tǒng)所采用的算法，包括2個基于內(nèi)存的協(xié)同過濾算法以及4個著名的基于模型的協(xié)同過濾算法:

1) Item-Based(IB)[7].其基本思想是預(yù)先根據(jù)所有用戶的歷史偏好數(shù)據(jù)計算物品之間的相似性，然后把與用戶喜歡的物品相類似的物品推薦給用戶.

2) User-Based(UB)[6].該算法與Item-Based算法類似，不同之處在于該算法計算的是用戶之間的相似度.

3) SVD[14].該算法是基于SVD矩陣分解算法，將評分矩陣分解為多個矩陣的乘積，最后將利用這些矩陣的乘積預(yù)測用戶的評分.

4) NMF[15].和SVD方法類似，不同的是它將原始評分矩陣分解為2個矩陣的乘積.

5) MMMF[16].該算法也是一種矩陣分解模型的算法，由于其具有較好的推薦性能而被廣泛采用.

6) NPCA[17].該算法在文獻[17]中被提出，它擁有著更高的預(yù)測準(zhǔn)確度.

在聚類算法的選擇上，本文采用4種算法來與本文方法進行對比:

1) UserClu(UC).它是單側(cè)聚類算法，該算法基本思想是利用k-means算法對數(shù)據(jù)集進行基于用戶的聚類，將用戶分成多個組.

2) ItemClu(IC).該算法與UserClu算法類似，不同之處在于該算法是利用k-means算法對物品進行聚類.

3) CoClust(CoC)[29].它是雙側(cè)協(xié)同聚類算法，其思想是將用戶與物品進行聯(lián)合聚類，但是1個用戶或者1個物品只能屬于1個分組.

4) MCoC[30].它是雙側(cè)多類協(xié)同聚類算法，它和CoClust算法思想一致，不同之處在于該算法允許1個物品或者用戶屬于多個分組，這一點與本文的算法一致，這也更符合現(xiàn)實情況:1個用戶可能對多個領(lǐng)域感興趣.

Fig. 3 The evaluation result of the prediction performance on MovieLens-100K圖3 在MovieLens-100K數(shù)據(jù)集上的預(yù)測性能測試結(jié)果

3.4 參數(shù)設(shè)置

在進行實驗之前，需要對本文模型有關(guān)參數(shù)進行設(shè)置.

1) 在特征提取階段.用戶特征維度a和物品特征維度b與具體的數(shù)據(jù)集有關(guān)，在MovieLens-100K數(shù)據(jù)集中，我們設(shè)置a=16，b=18；在MovieLens-1M數(shù)據(jù)集中，我們設(shè)置a=20，b=18；在Epinions數(shù)據(jù)集中，我們設(shè)置a=24，b=22；在學(xué)習(xí)率的設(shè)置上，在3個數(shù)據(jù)集中均為η=0.01.

2) 在圖模型構(gòu)建階段.參數(shù)τ=1.5，由于3個數(shù)據(jù)集的評分制度都是1～5分的整數(shù)，因此有評分制中值Tmed=3.參數(shù)α與β是為了均衡評分權(quán)重與相似度權(quán)重之間的差異，而且，不同數(shù)據(jù)集相似度取值情況也有所不同，在MovieLens-100K數(shù)據(jù)集中α=1.3，β=1.3；在MovieLens-1M數(shù)據(jù)集中α=1.1，β=1.2；在Epinions數(shù)據(jù)集中α=1.9，β=1.5.

3) 在聚類計算階段.聚類分組個數(shù)c是實驗中的控制因素，我們主要考查在不同分組下本文模型與其他算法性能優(yōu)劣.

4) 在性能評估階段.由于大部分推薦系統(tǒng)都采用的Top10推薦，因此，評測指標(biāo)NDCG的K值在3個數(shù)據(jù)集上均取K=10.

關(guān)于上述參數(shù)的選擇原因及其對模型性能的影響，本文將在3.7節(jié)進行討論.

3.5 實驗結(jié)果

在本文的實驗中，我們將3個公開數(shù)據(jù)集都分成2部分，隨機選取80%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩下的20%作為測試數(shù)據(jù)，用來檢測算法的預(yù)測和推薦性能.測試方法為先固定分組的個數(shù)，然后利用上述4種聚類算法對訓(xùn)練數(shù)據(jù)集進行分組，然后對所有算法得到的分組結(jié)果中選用同一種協(xié)同過濾推薦算法進行預(yù)測或推薦，統(tǒng)計各個算法的MAE值與NDCG值.由于矩陣分解模型的結(jié)果與分解的維度有關(guān)，因此，實驗中分別對SVD，NMF，MMMF，NPCA算法的分解維度進行了不同的設(shè)置并進行實驗，在所有不同緯度下取得的性能中，記錄最好的一個來作為與本文方法的對比結(jié)果.

1) 在數(shù)據(jù)集MovieLens-100K上的測試

由于MovieLens-100K數(shù)據(jù)集規(guī)模最小，因此分組不易過多，否則由于數(shù)據(jù)過度分散導(dǎo)致信息丟失嚴(yán)重.在參數(shù)設(shè)置方面，本文通過多個分組規(guī)模測試，選取了最優(yōu)效果較為集中的分組區(qū)間(5～30組).

預(yù)測性能的測試結(jié)果如圖3所示，6個子圖分別表示了6種不同協(xié)同過濾算法下的測試結(jié)果，在每個子圖中，我們對比了包括本文算法在內(nèi)的5種聚類算法在不同分組個數(shù)情況下的預(yù)測性能，橫軸表示分組個數(shù)，縱軸表示測試指標(biāo)MAE值，每個子圖中的水平虛線(基準(zhǔn)線)表示了在不分組的情況下直接使用協(xié)同過濾算法得到的MAE值，也即使用圖2(a)的方法得到的結(jié)果.

從圖3中可以看出，當(dāng)分組較少時，各不同聚類算法差別不太明顯，但是隨著分組個數(shù)的增多，本文算法的優(yōu)勢越來越突出，分組數(shù)為20左右時，除了NPCA算法以外，在其他算法上都表現(xiàn)出了明顯的性能優(yōu)勢.驗證了本文的算法能夠很好地應(yīng)對小規(guī)模的推薦系統(tǒng)，提升它們的預(yù)測性能.

在Top10推薦性能測試中，我們的實驗結(jié)果如圖4所示：

Fig. 4 The evaluation result of the Top10 recommendation performance on MovieLens-100K圖4 在MovieLens-100K數(shù)據(jù)集上的Top10推薦性能測試結(jié)果

從實驗結(jié)果可以看出，除了在圖3(c)中推薦性能比MCoC稍差以外，本文聚類模型在其他算法的測試上均取得了較好的推薦性能.另外，對比圖3與圖4我們注意到，采用Item-based推薦算法雖然預(yù)測性能不高，但是推薦性能卻比較好，相反采用NPCA推薦算法雖然取得了最高的預(yù)測性能，但是推薦效果卻很差，經(jīng)分析，我們認(rèn)為出現(xiàn)這種“反?！爆F(xiàn)象的原因除了算法本身特點外，還包括數(shù)據(jù)集特點與推薦規(guī)則等原因.首先，分析表2可知MovieLens-100K數(shù)據(jù)集平均用戶打分?jǐn)?shù)量在106左右，則測試集中打分?jǐn)?shù)約為20，這些評分中為5分的顯然就更少了(不足10個)，因此，用戶Top10列表中會包含很多低分物品，而我們的推薦規(guī)則只推薦高分物品，這導(dǎo)致用戶列表中多數(shù)物品無法被推薦到，因此推薦性能取決于對測試集中僅有的若干高分物品的預(yù)測準(zhǔn)確度，盡管NPCA算法MAE值較低，但是有可能其對高分物品的評估存在一定誤差，從而導(dǎo)致預(yù)測性能好反而推薦效果不理想，另一方面，Item-based推薦效果好的原因，則是由于基于物品相似度的推薦往往符合用戶的心理，相似的物品往往更容易引起用戶注意，盡管Item-based方法會將原本低評分卻與高評分物品相似的物品預(yù)測為高分并推薦(預(yù)測性能較差)，但該物品可能正好被用戶因為與其喜歡的物品相似而購買或者關(guān)注(盡管用戶購買后不喜歡)，因而在測試集高分物品不足的情況下，Item-based推薦算法可能會起到不錯的效果.

盡管NDCG指標(biāo)會出現(xiàn)上述“反?！爆F(xiàn)象，但仍然被眾多推薦系統(tǒng)作為重要指標(biāo)之一，因為它只關(guān)注算法對高分物品的預(yù)測準(zhǔn)確度，而不必關(guān)心對低分物品是否也有準(zhǔn)確的預(yù)測，這正是“推薦”所需要的.

2) 在數(shù)據(jù)集MovieLens-1M上的測試

MovieLens-1M數(shù)據(jù)集與MovieLens-100K數(shù)據(jù)源一致，區(qū)別在于前者數(shù)據(jù)規(guī)模更大，并且平均每個用戶打分?jǐn)?shù)與平均每個物品被打分次數(shù)在3個數(shù)據(jù)集里都是最高的.該測試用來檢驗本文算法在數(shù)據(jù)信息相對豐富的情況下的性能.我們在該數(shù)據(jù)集上做了同MovieLens-100K一致的實驗，預(yù)測性能實驗結(jié)果與Top10推薦性能實驗結(jié)果分別如圖5和圖6所示.

Fig. 5 The evaluation result of the prediction performance on MovieLens-1M圖5 在MovieLens-1M數(shù)據(jù)集上的預(yù)測性能測試結(jié)果

Fig. 6 The evaluation result of the Top10 recommendation performance on MovieLens-1M圖6 在MovieLens-1M數(shù)據(jù)集上的Top10推薦性能測試結(jié)果

從圖5實驗結(jié)果可以看出，在數(shù)據(jù)集打分?jǐn)?shù)量足夠多的情況下，各個算法都表現(xiàn)出一定的穩(wěn)定性，說明足夠多的評分?jǐn)?shù)能夠幫助各聚類算法更加準(zhǔn)確地捕捉用戶和物品的特征，降低不同算法之間的差異.盡管如此，從實驗結(jié)果來看本文算法所帶來的預(yù)測性能提升與其他算法相比仍然是有優(yōu)勢的.另一方面，通過觀察圖6的推薦結(jié)果也證實了上述分析：與圖4相比，圖6中各算法的推薦性能差異也變得較小，波動幅度在0.03左右.但是本文模型以及MCoC與其他聚類模型相比仍然取得了微弱優(yōu)勢，另外，圖6的實驗結(jié)果也沒有出現(xiàn)“反?！爆F(xiàn)象，正是由于測試集評分足夠多，在用戶的Top10列表中幾乎都是高分物品，因此，預(yù)測性能越好一定程度上可以反映出推薦性能較好.

3) 在數(shù)據(jù)集Epinions上的測試

在所有3個數(shù)據(jù)集中，Epinions數(shù)據(jù)集規(guī)模最為龐大，該數(shù)據(jù)集稀疏率也是最高的，我們利用該數(shù)據(jù)集檢驗本文算法在應(yīng)對大規(guī)模數(shù)據(jù)時的性能，實驗結(jié)果如圖7和圖8所示.

Fig. 7 The evaluation result of the prediction performance on Epinions圖7 在Epinions數(shù)據(jù)集上的預(yù)測性能測試結(jié)果

Fig. 8 The evaluation result of the Top10 recommendation performance on Epinions圖8 在Epinions數(shù)據(jù)集上的Top10推薦性能測試結(jié)果

從圖7的預(yù)測結(jié)果可以看出，大部分算法的預(yù)測結(jié)果MAE值都在0.85以上，和在MovieLens-1M數(shù)據(jù)集上的0.75相比性能大打折扣，說明該數(shù)據(jù)集大的稀疏性使得各個算法都難以捕捉用戶物品的特征，預(yù)測準(zhǔn)確度降低，即使增大分組個數(shù)，能夠發(fā)掘的有效信息也是有限的，無法大幅度提升準(zhǔn)確度，但是本文的算法依然能夠發(fā)掘比其他算法更多的信息，提升了更大的預(yù)測性能，在所有同類算法中表現(xiàn)優(yōu)異.驗證了本文算法也能夠應(yīng)對具有高稀疏性數(shù)據(jù)的推薦系統(tǒng).

但是另一方面，觀察圖8可以發(fā)現(xiàn)，各個算法的NDCG指標(biāo)都在0.20～0.25之間，隨著分組個數(shù)增大多數(shù)算法的推薦性能呈現(xiàn)無規(guī)律波動，且波動幅度達到0.1左右，通過分析表2我們認(rèn)為，造成這種情況的原因是由于該數(shù)據(jù)集用戶評分太少，只有平均20個左右，因此測試集中用戶評分的物品數(shù)往往只有一兩個甚至沒有，這使得所有算法都難以正確推薦出測試集中的物品，即使增大分組個數(shù)也不一定能夠提升推薦性能.

3.6 實驗結(jié)果的總結(jié)和分析

在3.1節(jié)所述的3個不同數(shù)據(jù)集上的實驗中，從實驗結(jié)果圖3、圖5、圖7對比各個算法的預(yù)測性能可以得到6個結(jié)論:

1) 圖3、圖5以及圖7中大部分實驗結(jié)果都位于基準(zhǔn)線下方，這表示通過聚類得到的推薦結(jié)果要比無聚類的要好，說明通過聚類的方式能夠提升協(xié)同過濾算法的預(yù)測準(zhǔn)確度.

2) 基于特征的協(xié)同聚類算法在所有3個數(shù)據(jù)集上都有杰出的表現(xiàn)，證明了該算法在預(yù)測功能上的有效性.

3) 在3個數(shù)據(jù)集上本文算法與MCoC同其他聚類算法如UC與IC等相比，有更好地表現(xiàn).原因是數(shù)據(jù)集的高稀疏性使得僅僅使用k-means進行聚類不能夠得到理想的結(jié)果，并且雙側(cè)聚類算法能夠獲得比單側(cè)聚類更多的信息.

4) 雖然MCoC算法也能夠提升不錯的預(yù)測性能，但是從實驗結(jié)果上來看，本文的算法總是比MCoC更好一些，說明加入用戶之間以及物品之間的相似性聯(lián)系比單純的依賴用戶對物品的打分進行聚類能夠得到更好的結(jié)果，能夠利用更多的數(shù)據(jù)本身帶來的信息.

5) 當(dāng)分組數(shù)較少時，所有聚類算法的性能差別不大，有的聚類后的性能要比不聚類的協(xié)同過濾算法還要差.這說明較少的分組不能夠完全區(qū)分用戶以及物品的特點，分類不夠準(zhǔn)確，當(dāng)分組個數(shù)適當(dāng)時，大部分聚類后的預(yù)測性能都有明顯提升.

6) 分組不易過多，所有的實驗中當(dāng)分組過大時，在折線圖中都表現(xiàn)出了上升的趨勢，意味著繼續(xù)增大分組個數(shù)可能會得到更差的結(jié)果.原因可能是分組數(shù)太多，導(dǎo)致數(shù)據(jù)過度分散，丟失了過多的數(shù)據(jù)之間的聯(lián)系，因此導(dǎo)致性能下降.

另一方面，觀察實驗結(jié)果圖4、圖6以及圖8對比各個算法的推薦性能，我們有得到3個結(jié)論：

1) 在MovieLens-100K數(shù)據(jù)集上，NDCG指標(biāo)值大約在0.3～0.45之間；在MovieLens-1M上則提升至0.41～0.48之間；而在Epinions數(shù)據(jù)集上，則只有0.2～0.25.在通過觀察表2的數(shù)據(jù)集統(tǒng)計信息后，我們認(rèn)為數(shù)據(jù)集中用戶的打分?jǐn)?shù)量一定程度上影響各個算法的推薦性能，打分?jǐn)?shù)量越少，TopK推薦時測試集包含的低分物品就會越多，而這些物品一般不會被推薦到，因此推薦性能就會變差，顯然，評分?jǐn)?shù)量越多，越有可能獲得準(zhǔn)確的推薦.

2) 盡管數(shù)據(jù)集的特征對模型推薦性能產(chǎn)生一定的影響，但是在3個數(shù)據(jù)集上本文模型都取得了不錯的推薦效果，經(jīng)本節(jié)分析，推薦性能很大程度上取決于對測試集中高分物品的預(yù)測準(zhǔn)確度，而本文模型在聚類過程中，評分越高越有可能出現(xiàn)在一個聚類結(jié)果中，因此，本文模型對于高分物品的預(yù)測準(zhǔn)確度有一定的保障，從實驗結(jié)果也可以看出，正是由于該原因，MCoC算法也保持著高預(yù)測準(zhǔn)確度以及高推薦準(zhǔn)確度.

Fig. 9 The image of the mapping function with different τ value圖9 不同τ值對應(yīng)的映射函數(shù)圖像

3) 在所有3個數(shù)據(jù)集上，本文模型取得最佳推薦性能時(NDCG值最大)在聚類結(jié)果上所用的推薦算法均為Item-based，說明在推薦性能上，Item-based算法最簡單也最為有效，因為它總是推薦和用戶興趣相似的物品，但是由于該原因，導(dǎo)致Item-based算法的推薦結(jié)果缺乏多樣性[29].

通過以上對預(yù)測性能與推薦性能的分析，我們可以認(rèn)為，本文模型能夠有效處理不同特點的推薦系統(tǒng)，提升它們的預(yù)測性能與推薦性能.

3.7 參數(shù)的影響

在本節(jié)，我們將討論本文實驗所采用3.4節(jié)參數(shù)設(shè)定的原因，主要討論參數(shù)a，b，τ，α，β對模型性能的影響，以下涉及實驗的部分均采用MAE指標(biāo).

首先分析參數(shù)τ，它是式(13)中的參數(shù)，該函數(shù)將評分映射成圖模型中邊的權(quán)重，我們分別選取不同的τ值來觀察它將評分映射為權(quán)重的情況，如圖9所示.從圖9可以看出，當(dāng)參數(shù)τ=1.5時，1～5分的映射權(quán)重比較合理，既弱化了高分間的差距，又不至于像τ=2.5時那樣差距過小，當(dāng)τ過小比如τ=0.5時，可以發(fā)現(xiàn)映射后的權(quán)值基本還是線性關(guān)系，沒有起到弱化高分之間的差距的作用.

參數(shù)α與β是為了平衡圖模型中上述函數(shù)映射的權(quán)重與基于相似度的權(quán)重之間的差異，當(dāng)τ=1.5時，評分為5分時映射后的權(quán)重最大，為0.95，由于相似度的最大值可能大于0.95，也可能遠小于0.95，因此需要用α與β去平衡這種差異.

參數(shù)α對模型性能的影響情況如表3所示，除了α外，其他參數(shù)同3.4節(jié)相同，從表3我們可以看出，在MovieLens-100K數(shù)據(jù)集上，本模型在不同推薦算法下取得最佳性能的α約為1.3，在MovieLens-1M數(shù)據(jù)集上取得最佳性能的α約為1.1，而在Epinions數(shù)據(jù)集上就需要α達到1.9.在3個數(shù)據(jù)集上，MAE值都隨著α的增大而呈現(xiàn)先降低后升高的趨勢，說明α過小會降低用戶相似度的重要性，而導(dǎo)致聚類效果變差;如果α過大時，聚類主要取決于用戶相似度了，因此模型退化為基于用戶的聚類模型.同理可以分析，當(dāng)β過大時，模型就退化為基于物品的單側(cè)聚類模型，而表4的實驗結(jié)果也證實了這一分析，觀察表4可以發(fā)現(xiàn)，取得最好性能時的β值與我們3.4節(jié)所設(shè)置的一致.

Table 3 Comparison of MAE Results with Different α on Three Datasets表3 不同α值在3個數(shù)據(jù)集上的MAE

Note: The best experimental results by setting differentαvalues under the same data set and recommendation algorithm are in bold.

Table 4 Comparison of MAE Results with Different β on Three Datasets表4 不同β值在3個數(shù)據(jù)集上的MAE結(jié)果對比

Note: The best experimental results by setting differentβvalues under the same data set and recommendation algorithm are in bold.

最后，我們簡單討論參數(shù)a和b對模型性能的影響，該參數(shù)控制著特征提取過程中用戶特征與物品特征的維度，實驗結(jié)果如表5和表6所示.可以看出，隨著特征維度的增長，模型性能提升較快，直到達到最好性能，但是繼續(xù)增大維度，MAE值就會緩慢上升.分析認(rèn)為，當(dāng)維度較低時，特征提取不完全，沒有很好的區(qū)分度，導(dǎo)致相似度計算不準(zhǔn)確；當(dāng)維度較高時，有可能會出現(xiàn)過擬合現(xiàn)象，因此模型性能緩慢下降.從實驗結(jié)果可以看出，取得最好性能時的特征維度正如3.4節(jié)所設(shè)置.

Table 5 Comparison of MAE Results with Different a on Three Datasets表5 不同a值在3個數(shù)據(jù)集上的MAE結(jié)果對比

Note: The best experimental results by setting differentavalues under the same data set and recommendation algorithm are in bold.

Table 6 Comparison of MAE Results with Different b on Three Datasets表6 不同b值在3個數(shù)據(jù)集上的MAE結(jié)果對比

Note: The best experimental results by setting differentbvalues under the same data set and recommendation algorithm are in bold.

4 總 結(jié)

本文提出了一種新的基于特征的協(xié)同聚類模型，它通過從用戶評分信息中提取用戶以及物品的特征，并將其應(yīng)用在聚類過程中以提高聚類準(zhǔn)確度，從而提高協(xié)同過濾算法的預(yù)測性能與推薦性能.本文模型首先通過二次回歸模型發(fā)掘用戶與物品的特征，然后通過一個圖模型將用戶物品的特征與用戶對物品的評分等信息綜合起來，從中計算出最終聚類結(jié)果.經(jīng)過在3個真實的數(shù)據(jù)集上從預(yù)測性能與推薦性能2個方面來進行測試，實驗結(jié)果有效地驗證了本文模型的確能夠更好地提升協(xié)同過濾算法的預(yù)測性能與推薦性能.在今后的工作中，我們考慮將這種從用戶評分矩陣中發(fā)掘用戶物品特點的方式進行拓展，添加一些其他信息來更準(zhǔn)確地發(fā)掘用戶和物品的特征，也能更進一步提升本文模型的性能.