一種面向協(xié)同過濾的快速最近鄰居搜索方法

王 永，趙旭輝，李曉光，肖 玲

重慶郵電大學 電子商務與現(xiàn)代物流重點實驗室，重慶400065

互聯(lián)網(wǎng)的發(fā)展帶來了信息的爆炸式增長，在為人們提供生活便捷的同時也帶來了信息過載問題[1-2]。推薦算法利用用戶歷史數(shù)據(jù)，挖掘其興趣愛好，提供個性化推薦服務，是解決信息過載問題的有效手段之一。基于鄰居的協(xié)同過濾模型是最典型的推薦算法，被廣泛運用于電子商務等領域[3-4]。該模型通常分為兩類，分別為：基于鄰居用戶的推薦模型和基于鄰居項目的推薦模型，即通過最近鄰居用戶（項目）的已有信息預測目標用戶對目標項目的評價。以此為基礎，邢長征等[5]將用戶評論集和物品評論相結(jié)合，提出一種聯(lián)合評論文本層級注意力和外積的推薦方法；陸航等[6]針對傳統(tǒng)的協(xié)同過濾算法中單一評分相似性計算不準確的問題，提出一種融合用戶興趣和評分差異的推薦方法；王宇琛等[7]將LDA模型與Bandits相結(jié)合提出了一種新的推薦方法，這些方法均有效提高了推薦的準確性。

在基于鄰居的協(xié)同過濾模型中，鄰居數(shù)據(jù)集的確定是非常關鍵的步驟，同時由于在該步驟中需要計算目標用戶（項目）與其余所有用戶（項目）間的相似性，鄰居集的確定也是該模型中最耗時步驟。為了提高推薦的準確性與計算效率，許多研究者對此進行了深入的研究[8-12]。Choi等[8]認為鄰居集應該隨目標項目的改變而改變，因此以用戶的共同評分項與目標項目間的相似性作為權(quán)重因子，調(diào)節(jié)其余用戶與目標用戶之間的相似性。Koohi等[9]通過子空間聚類為目標用戶尋找最近鄰居，有效緩解了數(shù)據(jù)的稀疏性問題。Liang等[10]采用局部敏感的哈希方法，通過哈希表查找最近鄰居，以提高算法效率。Hwang等[11]選擇部分用戶作為類別專家，然后依據(jù)目標用戶與類別專家間的相似性來選擇最近鄰居，以此縮短尋找鄰居的時間。Chae等[4]依據(jù)相似性度量方法的約束條件，設計了新的數(shù)據(jù)結(jié)構(gòu)，有效減少了相似性度量中的無效計算，提高了算法的運行效率。此外，在實際應用中常通過在離線條件下提前計算所有用戶（項目）間的相似性的方式來提高模型的運行效率。但這種方法有一個突出的缺點：忽略了用戶的最新評分，難以發(fā)現(xiàn)用戶的最新變化，特別是在稀疏數(shù)據(jù)的環(huán)境中，這種影響尤為明顯[12]。此外，離線確定鄰居的方式還會加劇冷啟動問題。

當前多數(shù)方法是圍繞推薦準確性與推薦效率之間的平衡展開研究，對推薦模型進行改進，很難同時提升推薦質(zhì)量和算法效率。此外，大多數(shù)研究側(cè)重如何提高相似性度量的準確性，從而找到更合適的鄰居。然而卻忽略了找到鄰居后，該鄰居是否能有效用于預測值的計算中。針對這些研究不足，提出了一種新的搜索最近鄰居的方法。該方法利用相似性測量方法與預測方法中所隱含的約束條件首先對潛在鄰居進行篩選，僅對那些對預測評分值產(chǎn)生影響的用戶或項目才進行相似性計算。為此構(gòu)建了項目的用戶評分列表與用戶的項目評分列表來篩選出有效的用戶或項目。這樣一方面極大地降低了相似性的計算量，另一方面也能保證每一位鄰居的評分信息都對預測值的計算做出了貢獻，從而實現(xiàn)了推薦質(zhì)量與推薦效率的同時提升。

1 預備知識

為了描述方便，列出了協(xié)同過濾模型中常用的符號及意義，如表1所示。

表1 協(xié)同過濾模型中常用的符號及意義Table 1 Notations related to collaborative filtering model

1.1 典型的相似性度量方法

基于鄰居的協(xié)同過濾模型中，根據(jù)鄰居集的不同，可分為基于用戶的協(xié)同過濾算法和基于項目的協(xié)同過濾算法。PCC與ACOS分別為最常用的用戶相似性度量方法與項目相似性度量方法，其計算公式如下[13-16]：

上述相似性度量方法具有結(jié)構(gòu)簡單、計算便捷的特點，強調(diào)了共同評分項的重要性，對所使用的數(shù)據(jù)有嚴格的條件要求。

1.2 典型的預測方法

傳統(tǒng)協(xié)同過濾模型根據(jù)相似性計算結(jié)果確定鄰居集，然后依據(jù)鄰居信息展開預測。對于基于用戶的協(xié)同過濾算法與基于項目的協(xié)同過濾算法，最為常用的預測公式如下[17-19]：

上述預測公式通過鄰居的評分信息來計算預測值，雖然計算簡單，但卻具有鄰居利用率低的缺陷。

2 問題的引出與分析

本章通過引導性實驗說明當前協(xié)同過濾算法中存在的問題。選取典型的公開數(shù)據(jù)集Movielens100k與Movielsn1M作為實驗的數(shù)據(jù)集（https://grouplens.org/datasets/movielens），對基于用戶的協(xié)同過濾算法（UBCF）和基于項目的協(xié)同過濾算法（IBCF）進行測試。分別以PCC與ACOS作為UBCF和IBCF的相似性度量方法，以公式（3）與公式（4）作為相應的算法的預測公式。實驗內(nèi)容包含兩部分：（1）模型運行時間比較；（2）鄰居利用率統(tǒng)計。

2.1 運行時間

在協(xié)同過濾推薦算法中，確定鄰居集是其中最為耗時的步驟，因為該步驟需要計算并比較目標用戶（項目）與其他所有用戶（項目）之間的相似性。在實際應用中，一種常用的處理方式是在線下事先計算出用戶或項目之間的相似性，在推薦時直接使用該計算結(jié)果確定鄰居集，從而提高推薦的效率。這種方式被稱之為線下推薦方式。此處，將采用這種方式的UBCF和IBCF稱之為UBCF_offline和IBCF_offline。相應的，將采用線上直接計算相似性和推薦結(jié)果的UBCF和IBCF稱之為UBCF_online和IBCF_online。

完成一次推薦，線上的推薦方法（UBCF_online和IBCF_online）所需的時間主要包含兩個部分，即計算相似性并確定鄰居集的時間和通過加權(quán)組合計算預測評分的時間。對線下的推薦方法（UBCF_offline和IBCF_offline），由于已經(jīng)提前完成了相似性計算和鄰居集的確定，因此完成單次推薦所需時間僅包括通過加權(quán)組合計算預測評分的時間。借鑒文獻[4]中的實驗設計，在測試中將最近鄰居的數(shù)量設置為80。在配置為CPU I5，內(nèi)存8 GB的臺式電腦上，測試上述方法完成單次推薦所需時間的均值、標準差、最大值以及最小值如表2和表3所示。

表3 線下方法完成單次推薦所需時間Table 3 Run time for offline methods to complete single recommendation ms

通過表2、3可以得到，無論是線上推薦方法還是線下推薦方法，均需要大量的時間來搜索最近鄰居。當系統(tǒng)中的用戶數(shù)和項目數(shù)較大時，尋找鄰居所需時間顯著增長。線下推薦的方法，由于預先計算了用戶（項目）間的相似性，在進行推薦時，可以跳過該步驟，直接進行預測評分計算與推薦，從而獲得遠高于線上方法執(zhí)行效率。

表2 線上方法完成單次推薦所需時間Table 2 Run time for online methods to complete single recommendation ms

另一方面，由于線下方法采用定時批量更新數(shù)據(jù)的方式，因此無法實時獲取用戶或項目的最新信息，這會導致其預測準確性低于線上方法。關于這一現(xiàn)象本文將在4.2節(jié)做進一步的分析。綜上所述，實驗結(jié)果表明非常有必要為線上推薦方法設計一種高效的搜尋鄰居的方法，以提高整個模型的運行效率。

2.2 鄰居利用率的統(tǒng)計

基于鄰居的協(xié)同過濾算法中，選擇鄰居的主要依據(jù)是相似性度量的結(jié)果。在預測評分時，預測公式對鄰居的可用性往往是有一定要求的。在公式（3）所示的基于鄰居用戶的預測計算中要求rv,i存在，即要求鄰居用戶必須評論過目標項目。同樣的，在公式（4）所示的基于鄰居項目的預測計算中要求ru,j存在，即要求目標用戶必須評論過鄰居項目。然而，在選擇鄰居時并未考慮這些要求，且由于數(shù)據(jù)集的稀疏性，在實際應用中，往往存在相當多的鄰居用戶（項目）并不滿足預測公式的要求。這些鄰居無法應用到預測公式中，從而造成鄰居利用率很低的現(xiàn)象。為了驗證該觀點，在數(shù)據(jù)集Movielens100k與Movielens1M上，采用公式（3）和公式（4）所示的預測方法，統(tǒng)計鄰居的利用率情況。測試結(jié)果如圖1所示。通過觀察可以發(fā)現(xiàn)，在分別設置鄰居數(shù)大小為20至100的條件下，UBCF與IBCF的鄰居利用率均低于10%，這意味著鄰居集中的大多數(shù)成員均未在計算預測值的過程中發(fā)揮作用。由此可見，即使能夠構(gòu)建與目標用戶（項目）的相似性很高的鄰居集，也會因為鄰居利用率低而降低了預測的可靠性與準確性。因此，有必要設計一種新的搜尋鄰居的方法，以提升鄰居的利用率。

圖1 UBCF和IBCF的鄰居利用率Fig.1 Neighbor utilization of UBCF and IBCF

3 搜尋最近鄰居的方法

上述引導性實驗的結(jié)果表明，推薦模型中常采用的“先計算全部相似性，再根據(jù)相似性程度搜尋最近鄰居集”的方法不僅耗時，而且還由于沒有考慮預測方法的要求，容易造成鄰居的利用率低。為此，本文結(jié)合相似性度量和預測方法的約束條件，提出一種新的搜尋最近鄰居的方法。該方法在提升鄰居利用率的同時，也顯著降低了計算的規(guī)模，有效提高了推薦模型的執(zhí)行效率。

3.1 適用于UBCF的最近鄰居選擇方法

在UBCF模型中，以公式（1）和公式（3）作為相似性度量和預測值計算的公式，歸納總結(jié)的約束條件如下：

（1）由公式（3）可知，對于目標用戶u與目標項目i，若rv,i不存在，則預測計算不可行。因此只有評價過項目i的用戶v才能被選作用戶u的鄰居。

（2）由公式（1）可知，對于任意兩用戶u與v，若Iu?Iv=?，則sim(u,v)計算不可行。因此必須與u有共同評分項的用戶v才能被選作用戶u的鄰居?；谏鲜黾s束條件，提出適用于UBCF的最近鄰居用戶搜尋方法如下：

步驟1構(gòu)建項目的用戶評分列表。根據(jù)用戶項目評分矩陣，為每個項目構(gòu)造相應的用戶評分列表ListU。對于項目i，其對應的用戶評分列表為ListU(i)={(uk,ruk,i)|uk∈Ui}，其中二元組(uk,ruk,i)表示用戶uk和它對項目i的評分ruk,i。在實際操作中，將評分矩陣中評論過項目i的所有用戶和他們對i的評分組織到一起，即得到ListU(i)。

步驟2篩選滿足預測計算要求的用戶集合。假設當前任務是預測目標用戶u對目標項目i的評分。根據(jù)約束條件（1）可知只有評論過項目i的用戶才可能作為用戶u的鄰居。因此，從ListU(i)中提取出所有的用戶構(gòu)建用戶集合UA。

步驟3根據(jù)約束條件（2），從用戶項目評分矩陣中篩選出用戶u評論過的項目集合Iu。然后，根據(jù)Iu，獲得列表集合LU={ListU(i)|i∈Iu}。從LU中挑選出所有的用戶構(gòu)建用戶集合UB。

步驟4將集合UA與集合UB的交集UC作為用戶u的備選鄰居集。計算用戶u與UC中各用戶的相似性，根據(jù)相似性值的大小確定最終的鄰居用戶集。

現(xiàn)通過一個示例說明上述搜尋鄰居的過程。假設評分矩陣中有7個用戶(u1,u2,…,u6,u)和6個項目(i1,i2,…,i6)。根據(jù)評分矩陣構(gòu)造項目的用戶評分列表如圖2所示，目標用戶u的評分向量為[4，?，3，?，2，?]，需要預測用戶u對目標項目i2的評分。根據(jù)ListU(i2)得集合UA為{u1,u2,u4}。用戶u評論過的項目集合Iu為{i1,i3,i5}，由此得到集合LU為{ListU(i1),ListU(i3),ListU(i5)}，從而得到UB為{u2,u3,u4,u6,u}。集合UA與集合UB的交集UC為{u2,u4}。所以，為用戶u尋找最近鄰居時，只需計算u與u2和u與u4間的用戶相似性。相較于傳統(tǒng)方法，本文方法不需要計算u與u1、u3、u5、u6之間的相似性，極大提高了推薦模型的執(zhí)行效率。

圖2 最近鄰居用戶搜尋示例Fig.2 Example of searching nearest neighbor user

3.2 適用于IBCF的最近鄰居選擇方法

在IBCF模型中，以公式（2）和公式（4）作為相似性度量和預測值計算的公式，歸納總結(jié)的約束條件如下：

（1）由公式（4）可知，對于目標用戶u與目標項目i，若ru,j不存在，則預測計算不可行。因此只有被用戶u評價過的項目j才能被選作項目i的鄰居。

（2）由公式（2）可知，對于任意兩項目i與j，若Ui?Uj=?，則sim(i,j)計算不可行。因此必須與項目i有公共的評分用戶的項目j才能被選作項目i的鄰居。

基于上述約束條件，提出適用于IBCF的最近鄰居用戶搜尋方法如下：

步驟1構(gòu)建用戶的項目評分列表。根據(jù)用戶項目評分矩陣，為每個用戶構(gòu)造相應的項目評分列表ListI。對于用戶u，其對應的項目評分列表為ListI(u)={(ik,ru,ik)|ik∈Iu}，其中二元組(ik,ru,ik)表示項目ik和用戶u對它的評分ru,ik。在實際操作中，將評分矩陣中用戶u評論過的所有項目和用戶u對這些項目的評分組織到一起，即得到ListI(u)。

步驟2篩選滿足預測計算要求的項目集合。假設當前任務是預測目標用戶u對目標項目i的評分。根據(jù)約束條件（1）可知只有被用戶u評論過的項目才可能是項目i的鄰居。因此，從ListI(u)中提取出所有的項目構(gòu)建項目集合IA。

步驟3根據(jù)約束條件（2），從用戶項目評分矩陣中篩選出評價過項目i的用戶集合Ui。根據(jù)Ui，獲得列表集合LI={ListI(u)|u∈Ui}。從LI中挑選出所有的項目構(gòu)建項目集合IB。

步驟4將集合IA與集合IB的交集IC作為項目i的備選鄰居集。計算項目i與IC中各項目的相似性，根據(jù)相似性值的大小確定最終的鄰居項目集。

此處同樣通過一個示例來說明算法的工作過程。假設評分矩陣中有6個用戶(u1,u2,…,u6)和7個項目(i1,i2,…,i6,i)。根據(jù)評分矩陣構(gòu)造用戶的項目評分列表如圖3所示，目標項目i的評分向量為[3，?，2，?，5，?]，需要預測用戶u2對項目i的評分。根據(jù)ListI(u2)得集合IA為{i2,i3,i5}。評論過i的用戶集合Ui為{u1,u3,u5}，根據(jù)LI={ListI(u1),ListI(u3),ListI(u5)}可得IB為{i1,i2,i4,i5,i}，進而得到IC為{i2,i5}。所以此例中，找尋鄰居集合只需計算i與i2和i與i5間的用戶相似性，同樣極大提高了推薦模型的執(zhí)行效率。

圖3 最近鄰居項目搜尋示例Fig.3 Example of searching nearest neighbor item

3.3 算法分析

首先，本文所提方法具有高效性與高準確性。該方法的原理是利用相似性測量方法與預測方法中所隱含的約束條件對潛在鄰居進行篩選，僅對那些對預測評分值產(chǎn)生影響的用戶或項目才進行相似性計算。具體的，以預測用戶u對項目i的過程為例，在基于用戶的協(xié)同過濾算法中，由PCC的理論計算公式可知，兩用戶間存在共同評分項時才能計算其相似性，即用戶u的鄰居只能在評論過Iu中的項目的用戶集合UB中選擇。通過訪問事先構(gòu)建的項目的用戶評分表可以很容易獲得該用戶集合。此外，通過公式（3）易知，用戶u的鄰居必須評論過項目i，這樣才能保證rv,i的存在。故用戶u的鄰居應在評論過項目i的用戶集合UA中選擇。該用戶集合也可以通過訪問事先構(gòu)建的項目的用戶表輕易獲得。將用戶集合UA與UB做交集即可獲得到用戶u的備選鄰居集合UC。在基于項目的協(xié)同過濾算法中也存在類似約束條件，故本文類似地構(gòu)造了用戶的項目評分列表，用于獲得集合Ui中各用戶所評論過的項目集合IB以及用戶u評論過的項目集合IA，將這兩項目集合做交集即可獲得項目i的備選鄰居集合IC。本文所提方法在縮小鄰居搜尋范圍同時也顯著性地提升了鄰居的利用率，從而保證其高效性與高準確性。此外，雖然為每個項目（用戶）構(gòu)建相應的用戶評分表（項目評分表）需要消耗一定時間，但是在實際應用中該操作是可以依據(jù)用戶項目評分矩陣事先構(gòu)造的。

其次，本文所提算法具有經(jīng)濟性。上述最近鄰居用戶搜尋方法中，項目（用戶）的用戶評分表（項目評分表）僅僅只是更改了評分矩陣中數(shù)據(jù)組織方式，采用另外一種方式關聯(lián)了基本數(shù)據(jù)之間的聯(lián)系，但并未添加新的數(shù)據(jù)信息，因此在系統(tǒng)的實現(xiàn)中可以通過在評分矩陣添加指針的方式來指明基本數(shù)據(jù)之間的關系，無需為用戶評分列表再分配新的存儲空間，從而保證了本文搜索算法的經(jīng)濟性。

最后，本文方法具有實時性。當評分矩陣中出現(xiàn)數(shù)據(jù)更新時，只需要相應地更新用戶評分列表即可，在實現(xiàn)中主要體現(xiàn)為數(shù)據(jù)指針的增刪與修改，不會帶來新的計算，因此可以有效保證本文搜索算法的實時性，此外本文所提方法的高效性也保證了算法的實時性。

4 算法的實驗結(jié)果與分析

4.1 數(shù)據(jù)集與評價指標

采用公開數(shù)據(jù)集Movielens100k、Movielens1M作為算法測試的數(shù)據(jù)集。表4列舉了兩個數(shù)據(jù)集的詳細信息。對于每個數(shù)據(jù)集，隨機選取80%的記錄作為訓練集，剩下的記錄作為測試集。評價推薦系統(tǒng)的指標有多種，主要可以分為三類：預測的準確性、推薦的準確性、計算的有效性[13]。平均絕對誤差（MAE）與均方根誤差（RMSE）是評價算法預測準確性的常用指標。其定義如下[20]：

表4 實驗數(shù)據(jù)集的詳細信息Table 4 Detailed description of experiment datasets

其中，ru,i是用戶u對項目i的實際評分，pu,i是用戶u對項目i的預測評分值，n為預測次數(shù)。

F1值作為Precision和Recall的調(diào)和平均值，常被用于評價算法的推薦準確性。其定義如下[21-22]：

此外，計算有效性的評價指標為有效預測數(shù)，它表示在所有需要預測的數(shù)據(jù)中，模型可以成功計算出預測結(jié)果的數(shù)量。

4.2 結(jié)果分析

將第3章提出的鄰居選擇方法分別融入UBCF和IBCF模型中，將得到的新模型命名為UBCF_prop和IBCF_prop。在相同的數(shù)據(jù)集上對UBCF_prop和IBCF_prop進行測試，并將實驗結(jié)果與第2章中的結(jié)果進行對比，以驗證本文所提出的鄰居選擇方法的有效性。

（1）效率分析

為了說明本文所提方法對算法效率的影響，首先將傳統(tǒng)搜尋最近鄰居方法的時間復雜度與本文所提方法的時間復雜度進行對比。假設數(shù)據(jù)集中共有m個用戶，n個項目，待預測記錄數(shù)為l。UBCF_online在搜尋鄰居時需要計算某一用戶與其余m-1個用戶間的相似性，且該過程需重復l次，故UBCF_online的時間復雜度為O(lm)。假設平均每個項目的UA中所包含的用戶數(shù)為s1，平均每個項目的UB中所包含的用戶數(shù)為s2，UA與UB的交集UC中所包含的用戶數(shù)的平均值為s。故UBCF_prop的時間復雜度為O(ls)。類似的，易知IBCF_online的時間復雜度為O(ln)。假設平均每個用戶的IA中所包含的項目數(shù)為r1，平均每個用戶的IB中所包含的用戶數(shù)為r2，IA與IB的交集IC中所包含的用戶數(shù)的平均值為r，易知IBCF_prop的時間復雜度為O(lr)。由于s與r遠遠小于m與n，故UBCF_prop的時間復雜度O(ls)遠遠低于UBCF_online的時間復雜度O(lm)，IBCF_prop的時間復雜度O(lr)遠遠小于IBCF_online的時間復雜度O(ln)。

在與第2章相同的數(shù)據(jù)集和運行環(huán)境下，測試UBCF_prop和IBCF_prop完成單次線上推薦所需的時間。所得結(jié)果如表5所示。比較表5與表2中的數(shù)據(jù)，在采用本文所提出的鄰居搜尋方法后，模型的運行效率得到顯著提高。在數(shù)據(jù)集Movielens100k與Movilens1M上，UBCF_prop完成單次線上推薦所需時間的均值分別為3.12 ms與26.21 ms，而UBCF_online在這兩個數(shù)據(jù)集上完成單次線上推薦所需時間的均值分別為67.01 ms與836.96 ms。UBCF_prop完成推薦所需時間遠小于UBCF_online。類似的，在數(shù)據(jù)集Movielens100k與Movilens1M上，IBCF_prop完成單次線上推薦所需時間的均值分別為21.81 ms與109.06 ms，而IBCF_online所需時間的均值分別為538.38 ms與11 110.63 ms。IBCF_prop的運行速度同樣遠快于IBCF_online。上述比較結(jié)果說明，本文算法可以根據(jù)歷史記錄迅速提供實時推薦，彌補傳統(tǒng)算法線上推薦方法耗時的缺陷。

比較表5和表3中的實驗結(jié)果，UBCF_prop和IBCF_prop的運行效率與離線方法UBCF_offline和IBCF_offline之間仍存在顯著的差距。但正如前文所述，線下推薦的方式未考慮數(shù)據(jù)更新對推薦質(zhì)量的影響，且其推薦質(zhì)量也會隨著未更新數(shù)據(jù)的增加而變差。

表5 UBCF_prop、IBCF_prop完成單次線上推薦所需時間Table 5 Run time for UBCF_prop and IBCF_prop to complete single recommendation ms

（2）數(shù)據(jù)更新的影響分析

為說明數(shù)據(jù)實時更新對預測準確性的影響，進行如下的實驗測試：對數(shù)據(jù)集Movielens100k重新進行劃分。根據(jù)數(shù)據(jù)產(chǎn)生的時間戳，提取出最新的10%的數(shù)據(jù)作為測試集，其余的數(shù)據(jù)作為訓練集。這樣劃分的目的是為了測試算法對最新數(shù)據(jù)的預測是否準確。同時，為了考慮數(shù)據(jù)更新情況對預測的影響，在訓練集中，根據(jù)數(shù)據(jù)產(chǎn)生的時間戳，刪除每個用戶2%的最新的評分數(shù)據(jù)。這樣可以將余下的數(shù)據(jù)視為有2%最新數(shù)據(jù)未更新的數(shù)據(jù)集。在此數(shù)據(jù)集上測試UBCF_offline和IBCF_offline的MAE和RMSE。采取同樣的方式，以2%為步長，繼續(xù)刪除最新的評分數(shù)據(jù)，再次對UBCF_offline和IBCF_offline進行測試，重復此過程，直至10%的最新數(shù)據(jù)被刪除為止。對UBCF_offline和IBCF_offline的測試結(jié)果如圖4所示。

同時，為了對比在線算法和線下算法之間的差異，對UBCF_online、IBCF_online、UBCF_prop和IBCF_prop進行測試。由于在線算法是在實際中實時使用最新的數(shù)據(jù)，所以在此處的測試中不對訓練集中的最新數(shù)據(jù)進行任何刪除。測試結(jié)果同樣列于圖4。

由于UBCF_online、IBCF_online、UBCF_prop和IBCF_prop為線上預測方法，不存在更新數(shù)據(jù)的問題，它們以全部測試數(shù)據(jù)作為基礎，展開對10%最新數(shù)據(jù)構(gòu)成的測試集進行預測。由于沒有數(shù)據(jù)更新的問題，因此得到的測試結(jié)果也不會隨數(shù)據(jù)未更新率的變化而變化，所以在圖4中表示為水平直線。從圖4（a）中可得，UBCF_online和IBCF_online的MAE值 分 別 為0.95和1.07。UBCF_offline和IBCF_offline的MAE值變化趨勢是隨著未更新數(shù)據(jù)率的增加而增大。由圖中可以看出，UBCF_online和IBCF_online的MAE值均略微優(yōu)于UBCF_offline和IBCF_offline。這說明實時更新數(shù)據(jù)對預測最新的評分有積極的影響作用。從圖4（a）中還可以看到，UBCF_prop，IBCF_prop的MAE值分別為0.87和0.79，分別明顯優(yōu)于UBCF_online、UBCF_offline和IBCF_online、IBCF_offline。主要的原因是UBCF_prop和IBCF_prop不僅能有效使用所有最新的數(shù)據(jù)展開預測，而且還由于采用了本文提出的鄰居搜索算法，有效提升了鄰居的利用率，保證了預測計算的全面性，因此獲得了更好的MAE值。在圖4（b）中，UBCF_offline和IBCF_offline的RMSE值雖有波動，但整體趨勢是隨著未更新數(shù)據(jù)率的增加而增大。同樣的，UBCF_online和IBCF_online的RMSE值均略微優(yōu)于UBCF_offline和IBCF_offline，而UBCF_prop和IBCF_prop的RMSE值則分別明顯優(yōu)于UBCF_online、UBCF_offline和IBCF_online、IBCF_offline。綜上所述，本文提出的算法不受數(shù)據(jù)更新的影響，且更好地利用了鄰居數(shù)據(jù)集的信息，具有更好的預測準確性。

圖4 預測準確性隨未更新數(shù)據(jù)率的變化情況Fig.4 Prediction accuracy versus un-update data

（3）推薦質(zhì)量分析

由于本文主要是依據(jù)相似性計算和預測計算的約束條件提出的鄰居搜索方法，因此搜索得到的鄰居均可用于模型的預測計算中，有效提高了推薦模型的推薦質(zhì)量。為驗證本文搜索方法對推薦質(zhì)量的提升，在Movielens100k和Movielens1M數(shù)據(jù)集上，測試并比較UBCF_prop、IBCF_prop與UBCF_online、IBCF_online的推薦結(jié)果。

①MAE和RMSE

圖5和圖6為UBCF_prop、IBCF_prop、UBCF_online和IBCF_online算法在Movielens100k和Movielens1M數(shù)據(jù)集上測試得到的MAE和RMSE。在這兩個數(shù)據(jù)集上，UBCF_prop的MAE最佳值分別為0.75和0.71，遠低于UBCF_online的MAE的最佳值0.85和0.93。同樣的，IBCF_prop的MAE最佳值分別為0.76和0.69，遠低于IBCF_online的MAE最佳值0.95和0.92。各方法在RMSE方面的表現(xiàn)與MAE類似，UBCF_prop與IBCF_prop的RMSE最佳值均遠低于UBCF_online與IBCF_online的RMSE的最佳值。總體說來，采用本文提出的最近鄰居搜索方法后，推薦模型的MAE和RMSE比原模型提升了10%~38%，模型的預測準確性得到進一步的提高。

圖5 MAE的結(jié)果比較Fig.5 Comparison of MAE results

圖6 RMSE的結(jié)果比較Fig.6 Comparison of RMSE results

②F1值

F1值的測試結(jié)題如圖7所示。在Movielens100k數(shù)據(jù)集中，UBCF_prop與UBCF_online的F1值間的差距隨著鄰居數(shù)的增加而減??；IBCF_prop的F1值始終明顯高于IBCF_online的F1值。在Movielens1M數(shù)據(jù)集中，UBCF_prop的F1值始終優(yōu)于UBCF_online的F1值；鄰居數(shù)較低時，IBCF_prop的F1值明顯高于IBCF_online的F1值，在鄰居數(shù)為100時，二者的F1值十分接近。整體而言，UBCF_prop與IBCF_prop的F1值優(yōu)于UBCF_online與IBCF_online的F1值，推薦準確性提升幅度大約在1%~15%的范圍。上述實驗結(jié)果表明，采用本文提出的最近鄰居搜索方法后，推薦模型的推薦準確性比原模型仍有一定的程度的提高。

圖7 F1值的結(jié)果比較Fig.7 Comparison of F1 value results

③有效預測數(shù)

在數(shù)據(jù)集Movielens100k與Movielens1M中，待預測的記錄數(shù)分別為20 000條和202 451條。各算法的有效預測數(shù)測試結(jié)果如圖8所示。從圖中可以看出，UBCF_prop與IBCF_prop的有效預測數(shù)都遠遠超過了UBCF_online與IBCF_online的有效預測數(shù)。

圖8 有效預測數(shù)的比較Fig.8 Comparison of number of valid prediction

5 結(jié)語

針對協(xié)同過濾模型中存在的尋找鄰居耗時和鄰居利用率低的問題，本文深入分析了用戶（項目）相似性計算以及預測評分值產(chǎn)生過程中存在的約束條件，以此為基礎，提出了一種新的最近鄰居搜索方法。該方法將相似性計算和預測計算中的約束條件轉(zhuǎn)化為對數(shù)據(jù)的篩選條件，從而有效地縮小了搜尋最近鄰居的范圍，極大地提高了協(xié)同過濾模型的運行效率。同時，該方法還提高了協(xié)同過濾模型對鄰居的利用率，提高了推薦結(jié)果的質(zhì)量。在公開數(shù)據(jù)集上的測試結(jié)果表明，采用本文所提出的鄰居搜索方法后，協(xié)同過濾模型在運行效率和推薦準確性方面均有明顯提高，這也說明了本文方法具有很好的應用潛力與價值。