張思明，游天童

（福州大學 數(shù)學與計算機學院，福建 福州350108）

隨著互聯(lián)網(wǎng)信息的不斷膨脹，信息過載也越來越嚴重，因而推薦系統(tǒng)越來越受到人們的重視。最簡單的推薦算法是全局排名方法 GRM(Global Ranking Method)，該算法不考慮用戶的個性化需求，因而其推薦結果的質量并不好。于是，考慮用戶偏好的協(xié)同過濾CF(Collaborative Filtering)推薦算法被廣為應用，并迅速成為最受歡迎的推薦算法之一。協(xié)同過濾算法考慮用戶興趣，在用戶群中尋找目標用戶的相似用戶組，綜合這些相似用戶對某一項目的評價，預測目標用戶對此項目的興趣。

目前，協(xié)同過濾算法主要分為兩類[1]：基于內(nèi)存的方法和基于模型的方法?；趦?nèi)存的方法在整個數(shù)據(jù)庫上執(zhí)行，從訓練數(shù)據(jù)庫中找出與目標用戶最相關的K個用戶，然后把他們的評分信息結合在一起對目標用戶的評分情況進行預測。主要有基于Pearson相關性的方法、基于向量相似度的方法等。這些算法主要有兩個缺點：易受稀疏的評分數(shù)據(jù)的影響；算法的可伸縮性差。與之相對，基于模型的方法并不直接使用單個用戶的評分信息，而是預先按照用戶評分的模式對用戶進行聚類，然后計算目標用戶與各個類別之間的相似度，找出最相似的類，用該類對某個項目的評分作為目標用戶對該項目的評分。主要的方法有貝葉斯網(wǎng)絡方法、聚類的方法?；谀Ｐ偷姆椒ㄔ诮⒕垲惖倪^程中較為耗時，而且對目標用戶做出的評分預測也存在準確性較低的問題。

本文考慮將譜聚類的方法引入到協(xié)同過濾推薦算法中，對訓練集中的用戶進行譜聚類，結合基于內(nèi)存和基于模型這兩種方法的優(yōu)勢，而對目標用戶評分的預測任務則交由其最相關的用戶群組來完成。對于如何構造譜聚類算法的輸入矩陣，本文將用戶——項目二分網(wǎng)絡投影到只包含用戶結點的單頂點網(wǎng)絡，構造n×n的用戶相似矩陣?？紤]到評分數(shù)據(jù)的稀疏性，本文利用類的信息對類中每個用戶未評分的項目進行數(shù)據(jù)平滑處理，從得到的N個聚類中找出與目標用戶最相似的一個或幾個類別作為最近鄰居候選集，再從候選集中找出最相似的K個用戶進入最近鄰居集，最后預測目標用戶對每個項目的評分。

1 相關工作

1.1 二分網(wǎng)絡的投影

二分網(wǎng)絡單頂點投影[2]是研究二分網(wǎng)絡的一個重要方法。二分網(wǎng)絡投影成單頂點網(wǎng)絡的方式主要分為兩類：無權投影和加權投影。如圖1所示，圖1(b)、圖1(c)分別為圖1(a)關于 X、Y的單頂點投影，單頂點網(wǎng)絡中的任意兩個點之間邊的權值大小為這兩點在二分網(wǎng)絡中的共同鄰居數(shù)。雖然單頂點網(wǎng)絡無法完全描述二分網(wǎng)絡的全部信息，但是這個只含一種結點的單結點網(wǎng)絡完美地保存了二分網(wǎng)絡中此類結點的拓撲關系，網(wǎng)絡中邊的權值構成的關系矩陣可以用來表示同類結點之間的相似關系。

圖1 二分網(wǎng)絡及其X投影和Y投影圖

1.2 譜聚類

近年來，譜聚類已經(jīng)成為一種廣受歡迎的現(xiàn)代聚類算法[3]。與傳統(tǒng)的聚類算法如K-means算法相比，這種算法效率更高，聚類結果更優(yōu)。譜聚類易于實現(xiàn)，可以用標準的線性代數(shù)的方法來高效解決。

給定數(shù)據(jù)點集 x1，x2，…，xn，以及所有點對 xi和 xj之間的相似度sij≥0所構成的n×n的相似度矩陣S。聚類的目標是把這些點劃分進不同的類中，使得類內(nèi)點的相似度大，而類間點的相似度小。本文用一個相似圖G=(V，E)來表示上述信息，每個頂點vi表示數(shù)據(jù)點 xi。如果sij≥0，那么頂點 vi和 vj之間存在邊，且其邊的權值即為wij。將二分網(wǎng)絡抽象成二分圖之后，可以這樣來闡述聚類問題：找到一個圖的劃分，使得不同組之間的邊的權值和小，而組內(nèi)邊的權值和大。

譜聚類的衍化算法有很多種，此處介紹的是非正規(guī)化譜聚類算法，這也是本文在后面推薦算法中用到的。非正規(guī)化的譜聚類算法描述如下：

輸入：相似度矩陣 S∈Rn×n，聚類數(shù) k；

輸出：k 個聚類 A1，A2，…Ak，Ai={j|yj∈Ci}；

其中算法的輸入矩陣S，可以用二分圖的鄰接矩陣W來近似表示。1.3協(xié)同過濾

作為構建推薦系統(tǒng)的最成功方法之一，協(xié)同過濾使用已知用戶群組的偏好來預測與該群組相似的其他用戶的未知偏好。協(xié)同過濾基于以下兩個假設：(1)人與人之間存在偏好興趣上的某種程度的相似或者重疊；(2)人對事物的偏好是具有穩(wěn)定性的。因此，尋找目標用戶的最相似的用戶群組對協(xié)同過濾推薦來說是至關重要的。一般來說，協(xié)同過濾的步驟為：(1)構建用戶檔案，即收集用戶的評分、評價行為等，并進行數(shù)據(jù)清理、轉換，最終形成用戶——項目的評價矩陣；(2)最近鄰居搜索，即計算目標用戶與數(shù)據(jù)庫內(nèi)各個用戶的相似度，找出相似度最高的N個用戶作為最近鄰居集；(3)推薦產(chǎn)生，即根據(jù)最近鄰居集的評價值產(chǎn)生推薦。

用戶相似度的主要度量方式有Pearson相關系數(shù)法、余弦相關性法和修正的余弦相關性法[4]。

Pearson相關系數(shù)：設經(jīng)用戶i和用戶j共同評分的項目集合用Iij表示，則用戶i和用戶j之間的相似性sim(i，j)通過Pearson相關系數(shù)度量為：

其中，Ri，c表示用戶 i對項目 c的評分，和分別表示用戶i和用戶j對項目的平均評分。

余弦相似性(cosine)：把用戶評分看做是n維項目空間上的向量，用戶間的相似性通過向量間的余弦夾角來度量。設用戶i和用戶j在n維項目空間上的評分分別為向量和，則用戶i和用戶j之間的相似性sim(i，j)為：

其中，分子為兩個用戶評分向量的內(nèi)積，分母為兩個用戶向量模的乘積。

修正的余弦相似性（adjusted cosine）：修正的余弦相似性度量方法考慮不同用戶的評分尺度問題。設經(jīng)用戶i和用戶 j共同評分的項目集合用 Iij表示，Ii和 Ij分別表示經(jīng)用戶i和用戶j評分的項目集合，則用戶i和用戶j之間的相似性 sim(i，j)為：

其中，Ri，c表示用戶 i對項目 c 的評分，Ri和Rj分別表示用戶i和用戶j對項目的平均評分。

2 SCBCF算法

本文將基于譜聚類的協(xié)同過濾算法記為SCBCF算法，以方便說明。

2.1 問題定義

給定一個二分圖 G=〈T∪U，E〉， 其中 T={ti|1≤i≤m}，U={ui|1≤i≤n}。 這里用 T表示項目集，U表示用戶集。同類結點之間不允許存在邊。二分圖G可以用m×n的矩陣 W 來表示，W(i，j)表示邊〈i，j〉的權值。 現(xiàn)在的任務是，給定一個目標用戶ua，預測其在T上已經(jīng)評價過的項目的評分，并與ua對該項目的實際評分相比較，以此來驗證算法的準確性。

2.2 SCBCF算法框架

預處理階段：用1.2節(jié)中給出的算法對用戶集進行聚類，形成 k 個類別：C1，…，Ck。

推薦階段：給定一個目標用戶 ua，項目 t，最近鄰居數(shù)K。

(1)從譜聚類的結果中，選擇幾個與ua最相似的類，作為最近鄰居的候選集。

(2)對候選集中的每個用戶，計算其與ua的相似度sim(ua，u)，其中 u 的評分結合了 Ru(t)和 RCu(t)，前 者 表 示u對t的評分，后者表示u所在類對t的類評分。

(3)選擇K個最相似的用戶作為最近鄰居。

(4)基于最近鄰居的評價行為，預測ua對項目 t的評分。

2.2.1聚類算法

本文采用1.2節(jié)中的非正規(guī)化的譜聚類算法對訓練集中的用戶進行聚類。聚類之前，根據(jù)圖1中的形式，先將二分圖投影成只含用戶的單頂點網(wǎng)絡，頂點之間的權值即為這兩個用戶收集的共同項目數(shù)，所有頂點之間的權值構成權值矩陣W，作為聚類算法中的輸入矩陣。

2.2.2數(shù)據(jù)平滑處理

正如前面所提到的，數(shù)據(jù)的稀疏性是協(xié)同過濾面臨的一個基本問題。本文應用基于聚類的數(shù)據(jù)平滑策略[5]。以下定義一個特別的評分值：

其中，Tu表示 u收集的項目集，R?u(t)表示 u對未收集的項目t的平滑評分值。R?u(t)定義如下：

2.2.3 最近鄰居選擇

首先根據(jù)式(7)，選擇與ua最相似的聚類作為最近鄰居的候選集，然后，根據(jù)Pearson相關系數(shù)，由式（1）計算ua與候選集中每個用戶的相似度，找出最相似的K個用戶構成最近鄰居集。

2.2.4 產(chǎn)生推薦

協(xié)同過濾是基于最近鄰居集的用戶評價行為，根據(jù)以下公式，為目標用戶ua預測其對項目t的評分。

其中sim(ua，u)表示目標用戶與最近鄰居集中的用戶u之間的相似度。

3 實驗

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

本實驗的數(shù)據(jù)來自于MovieLens，這個數(shù)據(jù)庫包含了1 682部電影和943個用戶。本文從中抽取出評價電影數(shù)大于50的用戶，把滿足條件的563個用戶分為訓練集和測試集，其中后163個用戶為測試集。本文進行3次訓練，訓練集分別表示為ML_200、ML_300和ML_400，大小分別為200、300和400。每次訓練前，對訓練集進行二分網(wǎng)絡的單頂點投影得到用戶之間的相似矩陣，為后面的聚類做準備。在此過程中本文不考慮評分值小于3的邊，排除了兩個用戶評分行為不一致的情況。訓練集用戶的譜聚類過程通過Matlab實現(xiàn)。

3.2 評價指標

本文使用絕對評價誤差MAE(Mean Absolute Error)評價推薦質量：

其中，Ru(tj)表示訓練集中的用戶 u對項目 tj實際的評分，(tj)表示用戶u對項目tj的預測評分。T是測試集，|T|表示測試集的大小。MAE值越小，說明預測的質量越高。

3.3 實驗結果及分析

本文將聚類數(shù)設為20，分別取最近鄰居數(shù)為 5、10、20。在實驗中，本文將傳統(tǒng)的基于Pearson相關系數(shù)的協(xié)同過濾算法作為基線方法進行了比較，并把該方法記為TCF。對比結果如表1所示。

表1 實驗結果數(shù)據(jù)及其對比

從表1可以看出，協(xié)同過濾易受數(shù)據(jù)稀疏性的影響。本文的方法對訓練集的數(shù)據(jù)進行了平滑處理，從而減輕了這一因素的影響。同時，隨著最近鄰居數(shù)的增加，實驗結果也隨之改善。這是因為考慮更多相似用戶的評分行為，使目標用戶的預測評分趨于穩(wěn)定，從而使得預測值與實際值之間的偏差減小。本文提出的算法在很大程度上縮小了最近鄰居候選集的大小，與傳統(tǒng)的協(xié)同過濾算法相比，算法的伸縮性得到了提高，時間復雜度也進一步降低。

本文考慮將更加高效的譜聚類算法引入到協(xié)同過濾推薦中來，實驗結果證明本文提出的SCBCF算法比傳統(tǒng)的協(xié)同過濾推薦算法能更好地提高推薦系統(tǒng)的推薦質量。在對用戶進行譜聚類時，本文發(fā)現(xiàn)聚類結果的各個類之間的用戶數(shù)并不均衡，這限制了預測能力的進一步提升，因此如何將用戶更準確地歸類將是未來的研究工作之一。

[1]SU X，KHOSHGOFTAAR T M.A survey of collaborative filtering techniques[J].Adv.Artif.Intell，2009(1)：421-425.

[2]ZHOU T，REN J，MEDO M，et al.Bipartite network projection and personal recommendation[J].Phys.Rev.E，2007，76(4)：046115-046121.

[3]LUXBURG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17(4)：395-416.

[4]SARWAR B，KARYPIS G，KONSTAN J，et al.Item-based collaborative ltering recommendation algorithms[C].In www10，Hong Kong，2001.

[5]XUE G R，LIN C，YANG Q，et al.Scalable collaborative filtering using cluster-based smoothing[C].In Proceedings of the ACM SIGIR Conference，Salvador，Brazil，2005：114-121.