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

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

中圖分類號(hào)：TP391

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

2.1 擴(kuò)展性問題分析

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

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

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

P@n=test∩topN/N

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

圖1 推薦精度比較

圖2 推薦實(shí)時(shí)性比較

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

4 結(jié)束語

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

參考文獻(xiàn)：

[1]吳湖，王永吉，王哲等.兩階段聯(lián)合聚類協(xié)同過濾算法[J].軟件學(xué)報(bào)， 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]王茜，王均波.一種改進(jìn)的協(xié)同過濾推薦算法[J].計(jì)算機(jī)科學(xué)，2010，37（6）：226-243.

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

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