協(xié)同過濾算法中擴展性問題研究

摘 要：針對協(xié)同過濾算法中擴展性問題，文章將用戶興趣看成多個興趣的集合，然后提出一種基于局部興趣的協(xié)同過濾算法，算法通過改善候選項目集來減少推薦時間。最后，文章給出了MovieLens數(shù)據(jù)集上的比較實驗，實驗結(jié)果表明，文章提出的算法在提高系統(tǒng)的實時性的同時，可以進一步提高系統(tǒng)的推薦精度。

關(guān)鍵詞：協(xié)同過濾；擴展性；推薦精度；候選項目集

中圖分類號：TP391

隨著電子商務(wù)和個性化網(wǎng)站的迅猛發(fā)展，個性化推薦已經(jīng)成為網(wǎng)絡(luò)應(yīng)用的熱點問題。在諸多的推薦方法中，協(xié)同過濾算法是應(yīng)用最廣泛，也是最成功的技術(shù)之一[1]。隨著系統(tǒng)用戶數(shù)和項目數(shù)的增加，協(xié)同過濾算法面臨著嚴(yán)重的可擴展性問題，推薦系統(tǒng)的實時性越來越難以滿足用戶的需求。本文提出了一種新的基于局部興趣的協(xié)同過濾算法（Local-Interesting-Based Collaborative Filtering，LICF），改善了傳統(tǒng)協(xié)同過濾算法在產(chǎn)生候選項目集中的不足，大大降低候選項目的個數(shù)，進而改善了系統(tǒng)的擴展性。

1 相關(guān)工作

1.1 協(xié)同過濾技術(shù)

目前研究和使用最多的兩種協(xié)同過濾算法是：基于用戶的協(xié)同過濾算法（User-based Collaborative Filtering，UBCF）和基于項目的協(xié)同過濾算法（Item-based Collaborative Filtering，IBCF）[2]?；谟脩舻膮f(xié)同過濾算法的基本原理是：通過計算用戶對項目評分的相似性，搜索目標(biāo)用戶的最近鄰居，然后根據(jù)最近鄰居的評分向目標(biāo)用戶產(chǎn)生推薦?；陧椖康膮f(xié)同過濾算法的原理是：能夠引起用戶興趣的項目，必定與其之前評分高的項目相似[3]。

協(xié)同過濾算法使用用戶對項目的評分進行產(chǎn)生推薦，假設(shè)在推薦系統(tǒng)中，存在m個用戶和n個項目，則所有用戶-項目評分可以用m×n階矩陣Rmn表示，其中rij（1≤i≤m，1≤j≤n）是一個用戶-項目對，表示用戶i對項目j的評分。矩陣中每一行ru={ru1，ru2，…run}代表一個用戶的評分向量，每一列ri={r1i，r2i，…rmi}代表一個項目的評分向量。本文中假設(shè)目標(biāo)用戶為u，待預(yù)測的目標(biāo)項目為i。

1.2 基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾算法是通過用戶向量計算用戶之間的相似性，為目標(biāo)用戶找到若干最近鄰居，然后根據(jù)最近鄰居對目標(biāo)項目的評分來預(yù)測目標(biāo)用戶的評分，最后選擇預(yù)測評分最高的前N項（top-N）作為推薦結(jié)果反饋給用戶?；谟脩舻膮f(xié)同過濾算法有如下核心步驟：

（1）計算用戶間相似度。計算目標(biāo)用戶與其他所有用戶的相似度，然后選取出k個相似度最大的用戶作為目標(biāo)用戶的最近鄰居。目前，比較常用相似度方法有Pearson相關(guān)系數(shù)、余弦向量相似度和修正余弦向量相似度等，本文中使用余弦向量相似度，公式如下。

其中，simuv表示用戶u與用戶v之間的相似度，和分別表示用戶u與用戶v的評分向量，與分別表示用戶u與用戶v評分向量的模，·表示向量的內(nèi)積。

（2）預(yù)測評分。根據(jù)k個最近鄰居對目標(biāo)項目的評分預(yù)測目標(biāo)用戶的評分，預(yù)測評分一般采用以下公式。

其中，表示目標(biāo)用戶u對目標(biāo)項目i的預(yù)測評分，simuv是目標(biāo)用戶u與鄰居用戶v之間的相似度，rvi是鄰居用戶v對項目i的評分，和分別是目標(biāo)用戶u與鄰居用戶v的平均評分，N為目標(biāo)用戶的最近鄰居集合。

（3）產(chǎn)生推薦。根據(jù)預(yù)測評分從大到小排序，將預(yù)測評分最大的N個項目（Top-N）推薦給用戶。

2 基于局部興趣的協(xié)同過濾算法

2.1 擴展性問題分析

在基于用戶的協(xié)同過濾算法中，計算量最大的兩步是用戶間相似度計算以及對目標(biāo)用戶未評分項目的評分預(yù)測。為了緩解協(xié)同過濾中的擴展性問題，學(xué)者們引入了矩陣分解、聚類等技術(shù)[4]，目的是為了降低評分矩陣的維數(shù)，縮小搜索空間，但在降維過程中往往伴隨著用戶信息丟失，導(dǎo)致推薦質(zhì)量下降。因此，系統(tǒng)擴展性的提高往往是以犧牲推薦質(zhì)量為代價的。

本文從一個新的角度來緩解系統(tǒng)擴展性問題，傳統(tǒng)協(xié)同算法在產(chǎn)生候選項目集時會引入大量的無關(guān)項目，導(dǎo)致算法需要為無關(guān)項目預(yù)測評分而增加了計算量。一般情況下，基于用戶的協(xié)同過濾算法不會為目標(biāo)用戶預(yù)測所有的未評分項目的評分，而是先為目標(biāo)用戶生成候選項目集，然后再對候選項目集中的項目進行預(yù)測。假設(shè)目標(biāo)用戶u的最近鄰居集（候選近鄰）為Nk={u1，u2，…uk}，用戶u及其最近鄰居對應(yīng)的已評分項目集為Iu和{I1，I2，…Ik}，則目標(biāo)用戶的候選項目集C=I1∪I2∪…∪Ik-Iu。

本文提出了一種新的基于局部興趣的協(xié)同過濾算法（Local-Interesting-Based Collaborative Filtering，LICF），算法中改善了傳統(tǒng)協(xié)同過濾算法在產(chǎn)生候選項目集中的不足，大大降低候選項目的個數(shù)，進而改善了系統(tǒng)的擴展性。

2.2 基于局部興趣的協(xié)同過濾算法

本文認為用戶的興趣并不是固定的，而是一般會擁有一個或多個興趣，例如，有的用戶對科幻電影和愛情感興趣，而有的用戶對科幻電影和恐怖電影感興趣，本文中將用戶的興趣模型定義為：

定義1（用戶興趣模型）每個用戶的興趣可以表示為E={e1，e2，…et}，其中et表示用戶的一個興趣，每個興趣會對應(yīng)一系列相應(yīng)的項目。

一般情況下，用戶之間通常只有部分興趣相似，其余興趣并不相似，甚至是相反的。對于兩個相似用戶u和v，其用戶模型又可以分別表示為Eu={e，eu}，Ev={e，ev}，其中e表示用戶u和v共同的興趣，eu，ev分別表示用戶u和用戶v與彼此不同的個人興趣。

用戶u的最近鄰居至少是在部分興趣上與用戶u存在相似性，換句話說就是圍繞興趣e1，用戶u將鄰居N1={u1，u2，…uk}聚集在一起。興趣e1對應(yīng)一系列項目Ie1，用戶u及鄰居N1非?？赡軐@些項目感興趣，所以對于這部分項目，在極大程度上有多個用戶對其有過評分。而對應(yīng)于用戶個人興趣的項目，基本上只有該用戶本身或極其少數(shù)的其他用戶有過評分。同樣最近鄰居N2中的用戶與用戶u圍繞興趣e2也有著相似的結(jié)果。

因此，本文認為并非是鄰居用戶感興趣的所有項目，目標(biāo)用戶u都可能感興趣。于是，在生成候選集的過程中，需要找出共同興趣所對應(yīng)的項目，去除鄰居用戶個人興趣所對應(yīng)的項目。本文認為在所有近鄰用戶評分過的項目中，只有評分用戶較多的項目才是與共同興趣相對應(yīng)的項目，而評分用戶過少的項目可能是由于某鄰居用戶的個人興趣帶來的。同時，本文引入了閾值α，定義最近鄰居所有的評分過的項目，只有評分的鄰居數(shù)超過閾值α的項目才入選候選項目集，否則不入選候選項目集。閾值α的取值與最近鄰居數(shù)有關(guān)，一般情況下，鄰居數(shù)越大，閾值α取值就越大，具體應(yīng)用中，可以根據(jù)經(jīng)驗或?qū)嶒灁?shù)據(jù)來得到。

3 實驗結(jié)果及分析

3.1 數(shù)據(jù)集及評價指標(biāo)

實驗采用的是公開的MovieLens數(shù)據(jù)集，數(shù)據(jù)集包括943名用戶在1682部電影上的100000條評分記錄，評分的范圍是1-5的整數(shù)。以下實驗中，我們將數(shù)據(jù)集分成80%的訓(xùn)練集和20%的測試集，并使用五折交叉法進行實驗。

本文采用的測量指標(biāo)是平均推薦時間與P@n值（推薦精度），一般情況下，系統(tǒng)擁有大量的優(yōu)質(zhì)資源，單個用戶不可能也沒有精力去瀏覽或購買所有的優(yōu)質(zhì)資源，因此，如何推薦出部分用戶所需要優(yōu)質(zhì)資源比找出所有的優(yōu)質(zhì)資源更符合實際，因此，文章采用的了P@n值。其定義如下：

P@n=test∩topN/N

其中，test是測試集中的項目，topN是推薦列表。P@n值測量是前N項推薦列表中相關(guān)項目所占比率。

3.2 實驗結(jié)果及分析

首先，文章比較了傳統(tǒng)基于用戶的協(xié)同過濾算法（UBCF）與本文提出的基于局部興趣的協(xié)同過濾算法方法在P@n值上的區(qū)別，如圖1所示。實驗中，候選近鄰數(shù)為5（生成候選項目集所用鄰居數(shù)），相似度算法都使用余弦相似度，閾值α取值為2（LICF-2）和4（LICF-4），預(yù)測近鄰取30（預(yù)測評分時所用鄰居數(shù)），Top-N值從2增加到20，間隔為2。

從整體上來說，本文提出的算法要明顯優(yōu)于傳統(tǒng)算法，比如推薦列表長度取常見值10時，三種算法的推薦精度分別約為16%，19%和22%。同時，LICF-2的效果整體上來說要優(yōu)于LICF-4的效果，主要是因為候選近鄰數(shù)為5，而閾值α取值為4時，過分降低了候選項目集的大小，將一部分用戶可能感興趣的項目也排除出了候選項目集。

圖1 推薦精度比較

圖2 推薦實時性比較

隨后，文章比較了兩種算法在平均推薦時間的上的比較，實驗計算推薦所用CPU時間，單位為秒，取top-N=5，候選近鄰數(shù)從5增長到10，間隔為1，結(jié)果如圖2所示。從圖中可以看出，隨著近鄰數(shù)的增加，兩算法所用時間都是不斷增長，但本文提出算法所用時間明顯小于傳統(tǒng)UBCF算法。

4 結(jié)束語

面對擴展性問題，傳統(tǒng)的方法是用推薦質(zhì)量換取推薦效率，本文從一個新的角度來緩解系統(tǒng)擴展性問題，通過改善候選項目集來減少推薦時間。實驗證明本文提出的算法在提高系統(tǒng)的實時性的同時，還可以取得更優(yōu)的推薦精度（P@n值）。另外，本文提出的算法與以往的解決方法并不沖突，下一步的工作是把本文提出的算法與以往的解決算法相結(jié)合，以便進一步提高推薦實時性和推薦效果。

參考文獻：

[1]吳湖，王永吉，王哲等.兩階段聯(lián)合聚類協(xié)同過濾算法[J].軟件學(xué)報， 2010，21（5）：1042-1054.

[2]S.J.Gong.A Collaborative Filtering Recommendation Algorithm Based on User Clustering and Item Clustering [J]. Journal of Softwar，2010，5（7）：745-752.

[3]王茜，王均波.一種改進的協(xié)同過濾推薦算法[J].計算機科學(xué)，2010，37（6）：226-243.

[4]姚勁勃，余宜誠，于卓爾等.基于PCA降維協(xié)同過濾算法的改進[J].吉林大學(xué)學(xué)報：信息科學(xué)版，2011，5：494-497.

作者簡介：韓淑云（1982-），女，碩士，助教，主要研究方向：知識服務(wù)，計算機應(yīng)用技術(shù)。