摘  要： 提出一種基于譜聚類的協同推薦算法(SCBCF)。首先從用戶——項目二分網絡的單頂點投影中得到用戶之間的相似矩陣，然后對該矩陣應用譜聚類算法，將用戶聚成k類，并將得到的聚類結果用于數據平滑和鄰居結點的選擇，最后基于最近鄰居集評分行為，對目標用戶產生推薦。在MovieLens上的實驗結果證明本文方法比傳統的協同過濾算法能更好地應用于二分網絡的協同推薦。
關鍵詞： 協同過濾；譜聚類；推薦算法；平均絕對偏差

    隨著互聯網信息的不斷膨脹，信息過載也越來越嚴重，因而推薦系統越來越受到人們的重視。最簡單的推薦算法是全局排名方法GRM(Global Ranking Method)，該算法不考慮用戶的個性化需求，因而其推薦結果的質量并不好。于是，考慮用戶偏好的協同過濾CF(Collaborative Filtering)推薦算法被廣為應用，并迅速成為最受歡迎的推薦算法之一。協同過濾算法考慮用戶興趣，在用戶群中尋找目標用戶的相似用戶組，綜合這些相似用戶對某一項目的評價，預測目標用戶對此項目的興趣。
    目前，協同過濾算法主要分為兩類[1]：基于內存的方法和基于模型的方法。基于內存的方法在整個數據庫上執行，從訓練數據庫中找出與目標用戶最相關的K個用戶，然后把他們的評分信息結合在一起對目標用戶的評分情況進行預測。主要有基于Pearson相關性的方法、基于向量相似度的方法等。這些算法主要有兩個缺點：易受稀疏的評分數據的影響；算法的可伸縮性差。與之相對，基于模型的方法并不直接使用單個用戶的評分信息，而是預先按照用戶評分的模式對用戶進行聚類，然后計算目標用戶與各個類別之間的相似度，找出最相似的類，用該類對某個項目的評分作為目標用戶對該項目的評分。主要的方法有貝葉斯網絡方法、聚類的方法。基于模型的方法在建立聚類的過程中較為耗時，而且對目標用戶做出的評分預測也存在準確性較低的問題。
    本文考慮將譜聚類的方法引入到協同過濾推薦算法中，對訓練集中的用戶進行譜聚類，結合基于內存和基于模型這兩種方法的優勢，而對目標用戶評分的預測任務則交由其最相關的用戶群組來完成。對于如何構造譜聚類算法的輸入矩陣，本文將用戶——項目二分網絡投影到只包含用戶結點的單頂點網絡，構造n×n的用戶相似矩陣。考慮到評分數據的稀疏性，本文利用類的信息對類中每個用戶未評分的項目進行數據平滑處理，從得到的N個聚類中找出與目標用戶最相似的一個或幾個類別作為最近鄰居候選集，再從候選集中找出最相似的K個用戶進入最近鄰居集，最后預測目標用戶對每個項目的評分。
1 相關工作
1.1 二分網絡的投影
    二分網絡單頂點投影[2]是研究二分網絡的一個重要方法。二分網絡投影成單頂點網絡的方式主要分為兩類：無權投影和加權投影。如圖1所示，圖1(b)、圖1(c)分別為圖1(a)關于X、Y的單頂點投影，單頂點網絡中的任意兩個點之間邊的權值大小為這兩點在二分網絡中的共同鄰居數。雖然單頂點網絡無法完全描述二分網絡的全部信息，但是這個只含一種結點的單結點網絡完美地保存了二分網絡中此類結點的拓撲關系，網絡中邊的權值構成的關系矩陣可以用來表示同類結點之間的相似關系。
1.2 譜聚類
    近年來，譜聚類已經成為一種廣受歡迎的現代聚類算法[3]。與傳統的聚類算法如K-means算法相比，這種算法效率更高，聚類結果更優。譜聚類易于實現，可以用標準的線性代數的方法來高效解決。
    給定數據點集x1，x2，…，xn，以及所有點對xi和xj之間的相似度sij≥0所構成的n×n的相似度矩陣S。聚類的目標是把這些點劃分進不同的類中，使得類內點的相似度大，而類間點的相似度小。本文用一個相似圖G=(V，E)來表示上述信息，每個頂點vi表示數據點xi。如果sij≥0，那么頂點vi和vj之間存在邊，且其邊的權值即為wij。將二分網絡抽象成二分圖之后，可以這樣來闡述聚類問題：找到一個圖的劃分，使得不同組之間的邊的權值和小，而組內邊的權值和大。
    譜聚類的衍化算法有很多種，此處介紹的是非正規化譜聚類算法，這也是本文在后面推薦算法中用到的。非正規化的譜聚類算法描述如下：
  
 
其中，分子為兩個用戶評分向量的內積，分母為兩個用戶向量模的乘積。
    修正的余弦相似性（adjusted cosine）：修正的余弦相似性度量方法考慮不同用戶的評分尺度問題。設經用戶i和用戶j共同評分的項目集合用Iij表示，Ii和Ij分別表示經用戶i和用戶j評分的項目集合，則用戶i和用戶j之間的相似性sim(i，j)為：
 

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

    從表1可以看出，協同過濾易受數據稀疏性的影響。本文的方法對訓練集的數據進行了平滑處理，從而減輕了這一因素的影響。同時，隨著最近鄰居數的增加，實驗結果也隨之改善。這是因為考慮更多相似用戶的評分行為，使目標用戶的預測評分趨于穩定，從而使得預測值與實際值之間的偏差減小。本文提出的算法在很大程度上縮小了最近鄰居候選集的大小，與傳統的協同過濾算法相比，算法的伸縮性得到了提高，時間復雜度也進一步降低。
    本文考慮將更加高效的譜聚類算法引入到協同過濾推薦中來，實驗結果證明本文提出的SCBCF算法比傳統的協同過濾推薦算法能更好地提高推薦系統的推薦質量。在對用戶進行譜聚類時，本文發現聚類結果的各個類之間的用戶數并不均衡，這限制了預測能力的進一步提升，因此如何將用戶更準確地歸類將是未來的研究工作之一。
參考文獻
[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.