一種基于特征的協同聚類模型

張 飛 張立波 羅鐵堅 武延軍

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

互聯網的蓬勃發展促使信息總量呈現指數上升，這使得互聯網用戶從龐雜的信息中獲取有用的信息變得越來越困難.推薦系統能夠根據用戶的特點和興趣有針對性地為他們推薦有價值的信息.因此推薦系統的作用越來越突出，已經被應用到商品推薦等諸多領域中.

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

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

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

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

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

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

1 相關工作

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

基于內存的協同過濾算法主要是通過尋找用戶[6]或者物品[7]之間的相似性來進行推薦，雖然這種推薦系統實現簡單并且很有效，但是它還存在很多問題，比如無法有效處理大規模數據以及高稀疏性的數據.為了解決基于內存的協同過濾算法的這種問題，許多基于模型的協同過濾算法被提出，比如貝葉斯模型[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]等，它們在處理大規模數據時有著杰出的表現，但是推薦系統數據高稀疏性的特點仍舊限制了這些算法性能.

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

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

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

2 基于特征的協同聚類模型

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

2.1 相似度的計算

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

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

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

2.2 特征信息的提取

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

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

在傳統的二次回歸模型中，對于特征向量x，其對應的監督值y通過表達式去擬合：

(1)

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

(2)

我們令：

(3)

(4)

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

(5)

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

(6)

(7)

(8)

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

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

(9)

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

(12)

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

算法1. 特征提取算法.

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

輸出：矩陣U,V.

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

② 根據式(6)計算z；

③ foru=1 tondo

④ 根據式(7)計算pu；

⑤ end for

⑥ forv=1 tomdo

⑦ 根據式(8)計算qv；

⑧ end for

⑨ repeat

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

2.3 圖模型的構建

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

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

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

(13)

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

因此，該圖模型的構建過程如下:

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

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

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

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

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

2.4 聚類結果的計算

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

(14)

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

(15)

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

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

(16)

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

PTDP=I.

(17)

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

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

2.5 推薦結果的生成

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

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

3 實驗評估

3.1 數據集

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

1) MovieLens-100K

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

2) MovieLens-1M

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

3) Epinions

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

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

Table 2 The Statistics of the Three Datasets表2 3個數據集的統計信息

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

3.2 評估指標

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

1) 在預測性能上.本文采用推薦系統領域內比較常用的平均絕對誤差(mean absolute error,MAE)指標，其表達式為

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

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

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

3.3 評估方法與對比算法

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

在協同過濾推薦算法的選擇上，本實驗選擇了當下較為主流的推薦系統所采用的算法，包括2個基于內存的協同過濾算法以及4個著名的基于模型的協同過濾算法:

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

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

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

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

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

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

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

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

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

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

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

Fig. 3 The evaluation result of the prediction performance on MovieLens-100K圖3 在MovieLens-100K數據集上的預測性能測試結果

3.4 參數設置

在進行實驗之前，需要對本文模型有關參數進行設置.

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

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

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

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

關于上述參數的選擇原因及其對模型性能的影響，本文將在3.7節進行討論.

3.5 實驗結果

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

1) 在數據集MovieLens-100K上的測試

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

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

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

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

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

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

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

2) 在數據集MovieLens-1M上的測試

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

Fig. 5 The evaluation result of the prediction performance on MovieLens-1M圖5 在MovieLens-1M數據集上的預測性能測試結果

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

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

3) 在數據集Epinions上的測試

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

Fig. 7 The evaluation result of the prediction performance on Epinions圖7 在Epinions數據集上的預測性能測試結果

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

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

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

3.6 實驗結果的總結和分析

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

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

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

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

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

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

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

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

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

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

Fig. 9 The image of the mapping function with different τ value圖9 不同τ值對應的映射函數圖像

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

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

3.7 參數的影響

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

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

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

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

Table 3 Comparison of MAE Results with Different α on Three Datasets表3 不同α值在3個數據集上的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個數據集上的MAE結果對比

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

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

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

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個數據集上的MAE結果對比

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

4 總 結

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