摘  要： 提出一種基于譜聚類的協(xié)同推薦算法(SCBCF)。首先從用戶——項(xiàng)目二分網(wǎng)絡(luò)的單頂點(diǎn)投影中得到用戶之間的相似矩陣，然后對(duì)該矩陣應(yīng)用譜聚類算法，將用戶聚成k類，并將得到的聚類結(jié)果用于數(shù)據(jù)平滑和鄰居結(jié)點(diǎn)的選擇，最后基于最近鄰居集評(píng)分行為，對(duì)目標(biāo)用戶產(chǎn)生推薦。在MovieLens上的實(shí)驗(yàn)結(jié)果證明本文方法比傳統(tǒng)的協(xié)同過濾算法能更好地應(yīng)用于二分網(wǎng)絡(luò)的協(xié)同推薦。
關(guān)鍵詞： 協(xié)同過濾；譜聚類；推薦算法；平均絕對(duì)偏差

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

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

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