融合影響因子的加權(quán)協(xié)同過濾算法

高全力，高 嶺，楊建鋒，王 海，任 杰，張 洋

(西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，西安 710127)

1 概述

隨著網(wǎng)絡(luò)的急劇擴(kuò)張，網(wǎng)絡(luò)上的資源呈現(xiàn)幾何性的增長，包括音頻、視頻、新聞等充斥著整個網(wǎng)絡(luò)。這帶來了兩方面的困擾，一方面是從用戶的角度，從海量的資源中找到自己真正感興趣的資源越來越困難;另一方面是從網(wǎng)絡(luò)服務(wù)提供商的角度，由于用戶留給推薦系統(tǒng)有價值的信息非常少，為不同的用戶準(zhǔn)確地推薦資源也越來越困難。因此，對于高質(zhì)量推薦系統(tǒng)的需求也就越來越大。

許多研究人員提出了各種推薦算法的思路及其具體的實施方案，例如基于內(nèi)容過濾的推薦算法［1］、適應(yīng)性推薦算法［2］、基于項目的推薦算法［3］等。其中，協(xié)同過濾算法是目前最成功的推薦算法之一，在電影、歌曲、圖書等領(lǐng)域都有廣泛的應(yīng)用，其中在電子商務(wù)推薦系統(tǒng)中的成功應(yīng)用［4］使其受到廣泛關(guān)注。盡管協(xié)同過濾算法非常成功和受歡迎，但它仍有2 個局限性:數(shù)據(jù)稀疏性和冷啟動問題。數(shù)據(jù)稀疏性指的是在一個龐大的用戶空間里只有很少的用戶對項目進(jìn)行評分，這樣也就導(dǎo)致了在計算相似度時，所能依賴的信息較少，降低了相似度計算的可信度［5］。冷啟動問題分為用戶冷啟動問題與項目冷啟動問題，指的是對于新加入系統(tǒng)的用戶或項目系統(tǒng)很難做出高質(zhì)量的推薦［6］。為了解決這2 個問題，文獻(xiàn)［7］等通過分析基于內(nèi)容的推薦算法與協(xié)同過濾推薦算法的優(yōu)缺點，提出了將兩者相融合的推薦算法;文獻(xiàn)［4］借鑒社會網(wǎng)絡(luò)中人與人之間的信任評價方法，提出一種基于信任機(jī)制的協(xié)同過濾推薦算法，提高了推薦質(zhì)量;文獻(xiàn)［8］通過將聯(lián)合聚類與協(xié)同過濾算法相結(jié)合，采用聚類技術(shù)解決數(shù)據(jù)稀疏性;文獻(xiàn)［9］通過降低矩陣維數(shù)來解決數(shù)據(jù)稀疏的問題。然而，研究人員在關(guān)注于這2 個問題時，卻忽視了另一個重要的問題——相似度的計算算法。單純地使用基于用戶或者基于項目或者僅僅將兩者簡單結(jié)合的相似度算法［3-10］，具有很大的局限性。首先由于數(shù)據(jù)集的潛在的稀疏性，可能導(dǎo)致算法計算出的相似性數(shù)值差別非常小，進(jìn)而無法找出真正的相似用戶或相似項目。其次沒有充分考慮，對任意2 個用戶共同評分過的項目個數(shù)與任意2 個項目間共同評分的用戶個數(shù)對相似性計算的影響。

針對上述問題，本文提出種基于影響因子的相似度計算方法。從用戶與項目2 種角度來解決相似度的計算問題，把用戶間共同評分項目的個數(shù)與項目間共同評分用戶的個數(shù)作為影響因子來修正相似度的計算，并根據(jù)2 種相似度計算方法，分別提出了不同的預(yù)測評分計算算法。為平滑預(yù)測評分，將基于用戶的預(yù)測評分與基于項目的預(yù)測評分進(jìn)行加權(quán)，得到最終預(yù)測評分。

2 問題描述

在協(xié)同過濾算法中，首先應(yīng)根據(jù)歷史數(shù)據(jù)庫建立一個user-item 評分矩陣，矩陣中的各個數(shù)值即表示用戶對相應(yīng)項目的評分值，如表1 所示。

表1 user-item 評分矩陣S(m，n)

其中，表1 共有m 行n 列，分別代表m 個用戶與n 個項目;Smn表示用戶Um對于項目In的評分值。

然后以評分矩陣為基礎(chǔ)，采用基于用戶或基于項目的余弦相似度、修正的余弦相似度［1］或者相關(guān)相似度［11］來計算用戶間或者項目間的相似度的值。并將其作為用戶間或項目間的最終相似度。根據(jù)相似度的值找出最近鄰用戶或最近鄰項目，以此為基礎(chǔ)通過評分算法計算出預(yù)測評分。最后根據(jù)預(yù)測評分的排序序列進(jìn)行推薦。

在余弦相似度計算方法中，對于用戶沒有做出評分的項目評分全部置為0 分，在用戶空間非常大且數(shù)據(jù)非常稀疏的情況下，這種假設(shè)會極大地影響相似度的計算［12］。在相關(guān)相似度的計算方法中，雖然在未評分項目的處理上，采取了一些措施來緩解其帶來的影響(在計算用戶相似性是采用用戶間共同評分的項目作為參評對象)，并且通過減去用戶對所有項目評分的平均評分來修正不同用戶存在的評分偏見。但是這種做法在數(shù)據(jù)稀疏性的情況下，仍不能有效地計算出實際的相似度［13］。

3 本文算法

在本文的算法中，從用戶與項目2 種角度來解決相似度的計算問題，將基于用戶間共同評分項目與項目間共同評分用戶的影響因子，與修正的余弦相似度的乘積計算用戶間及項目間的相似度。并根據(jù)2 種相似度計算方法，分別提出不同的預(yù)測評分計算算法，即融合影響因子的用戶協(xié)同過濾算法(Fused Impact Factor of User Based Collaborative Filtering，IFUBCF)、融合影響因子的項目協(xié)同過濾算法(Fused Impact Factor of Item Based Collaborative Filtering，IFIBCF)、融合影響因子的加權(quán)協(xié)同過濾算法(Weighted Collaborative Filtering Based Impact Factor，IFBWCF)。

3.1 融合影響因子的用戶協(xié)同過濾算法

用戶的相似度表示用戶間興趣的重合程度，相似度的計算是協(xié)同過濾算法較為關(guān)鍵的環(huán)節(jié)。選擇當(dāng)前用戶a 與任意用戶b，用戶a 與用戶b 已評分的項目集合分別為Ia與Ib，其評分項目集合的并集Iab=Ia∪Ib。在Iab上，用修正的余弦相似度［11］計算用戶a 與用戶b 的相似度公式如下:

其中，sai表示用戶a 對于項目i 的評分;sbi表示用戶b 對于項目i 的評分表示項目i 的平均被評分值。由于僅僅根據(jù)式(1)得出的相似度的值，有可能會產(chǎn)生一些不準(zhǔn)確的情況［13］。例如，2 個用戶共同評分的項目較多，但是根據(jù)式(1)所得出的相似度的值卻有可能較低。并且用戶間共同評分項目的個數(shù)，是反映用戶行為及興趣重合程度的重要因素。因此，在計算相似度時應(yīng)充分考慮其對相似度值的影響。所以本文用基于用戶間的共同評分項目的個數(shù)的影響因子來修正相似度的計算，影響因子βu的計算公式如下:

其中，cab表示用戶a 和用戶b 之間共同評分過的項目的個數(shù);αu是為了避免式中分母為0 導(dǎo)致無意義或者βu的值為0 導(dǎo)致式(1)中計算出的相似度為0而添加的常數(shù)參數(shù);c—u 表示其他任2 個用戶共同評分過的項目個數(shù)的平均值。由于當(dāng)用戶空間非常大時的值可能會趨于非常小，進(jìn)而導(dǎo)致βu的值過大，從而使得式(1)中計算的相似度對最終相似度值的影響過低。所以，需要根據(jù)不同的數(shù)據(jù)集調(diào)整αu，以修正影響因子的取值。

因此，相似度的最終計算公式為:

為了得到用戶a 對于未評分項P 的預(yù)測評分，首先根據(jù)式(3)中計算的相似度的值，得到其他用戶與用戶a 的相似度序列，找出用戶a 的k 鄰近用戶。根據(jù)k 鄰近用戶與當(dāng)前用戶的相似度與未評分項目P(P∈Iab)被評分的平均值，通過公式計算出未評分項目P 相對于當(dāng)前用戶a 的預(yù)測評分Sa(因為a 為任意用戶，為體現(xiàn)一般性，用Susr代替Sa)，即IFUBCF 算法，計算公式如下:

其中，m 為k 鄰近用戶中對于未評分項目P 有評分的用戶的個數(shù)，顯然1≤m≤k，Im即為此m 個用戶空間即為用戶i 對于項目P 的評分為用戶i 平均評分值為項目的P 的平均評分。則基于用戶相似度的預(yù)測評分即體現(xiàn)為:k 鄰近用戶對于未評分項的評分與該用戶評分均值偏差的和，與其相對于當(dāng)前用戶相似度的乘積對于未評分項平均評分的影響。

3.2 融合影響因子的項目協(xié)同過濾算法

項目的相似度表示項目間的相似程度，對任意項目i 評過分的用戶集合為Ui，對項目j 評過分的用戶集合為Uj，其評分用戶并集Uij=Ui∪Uj。在Uij上用基于項目的修正余弦相似度［11］來計算項目i 與項目j 之間的相似度，公式如下:

其中，cij表示對項目i 和項目j 共同評分用戶的個數(shù)表示其他任意2 個項目間共同評分用戶個數(shù)的平均值;αi為修正β 的常數(shù)參數(shù)。其最終相似度計算公式如下:

根據(jù)式(7)所得出的相似度序列，計算出項目P的k 鄰近項目，從而得出用戶a 對于未評分項目P的預(yù)測評分(因為P 為任意項目，為體現(xiàn)一般性，用Sitem來代替Sp)，即IFIBCF 算法，計算公式如下:

3.3 加權(quán)的協(xié)同過濾算法

用戶與項目作為影響整個推薦系統(tǒng)推薦質(zhì)量的2 個重要因素，單獨選擇其中一個作為預(yù)測評分的主要基準(zhǔn)，是不合理的［14］。因此，本文將2 種算法結(jié)合起來，通過引入加權(quán)系數(shù)，平滑2 種情況下的預(yù)測評分，使預(yù)測評分更加合理與精確。具體做法是，將基于用戶的k 鄰近用戶中對于未評分項有評分的個數(shù)m 與基于項目的k 鄰近項目中相對于當(dāng)前用戶被評分項目的個數(shù)n 做為加權(quán)系數(shù)，得出基于影響因子的加權(quán)協(xié)同過濾算法IFBWCF，即:

其中，Susr表示根據(jù)IFUBCF 算法計算出的預(yù)測分值;Sitem表示根據(jù)IFIBCF 算法計算出的預(yù)測分值。根據(jù)式(9)計算出當(dāng)前用戶對于未評分項目的最終預(yù)測評分，根據(jù)TopN 算法為當(dāng)前用戶推薦得分最高的N 個項目。

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

實驗所采用的PC 機(jī)的配置為Intel(R)Core(TM)i5 2.8 GHz CPU，4 GB 內(nèi)存，操作系統(tǒng)為Windows XP，算法使用Matlab 實現(xiàn)。

4.1 數(shù)據(jù)集與實驗方案

本文中所做實驗采用的數(shù)據(jù)集為MovieLens 數(shù)據(jù)集，此數(shù)據(jù)集是常用的基于Web 的衡量推薦算法質(zhì)量的數(shù)據(jù)集。對每個電影采取5 分制的評分策略。本文選取的是其公開的一部分?jǐn)?shù)據(jù)，包括943 個用戶對于1 682 部電影的100 000 條評分記錄。其中，每個用戶都至少對20 部電影進(jìn)行了評分。分?jǐn)?shù)的數(shù)值越高表示用戶對于這部電影的喜愛程度越高。為緩解采用單一數(shù)據(jù)集導(dǎo)致的實驗結(jié)果缺乏說服力，本文采用All But One 算法對數(shù)據(jù)集進(jìn)行處理。并將數(shù)據(jù)集分為訓(xùn)練集與測試集兩部分，在最近鄰居k 值的選取對推薦結(jié)果的影響上，將本文算法與多類屬概率潛在語義的協(xié)同過濾算法PLSA(Probabilistic Latent Semantic Analysis)［9］相對比。

4.2 算法的評價標(biāo)準(zhǔn)

一般來說，評價一個推薦算法質(zhì)量的標(biāo)準(zhǔn)有統(tǒng)計精度度量方法和決策支持精度度量方法。本文實驗所采用的是屬于統(tǒng)計精度度量方法的平均絕對誤差(Mean Absolute Error，MAE)［11］作為檢驗推薦算法的標(biāo)準(zhǔn)。MAE 通過預(yù)測的用戶評分與實際的用戶評分之間的偏差來度量預(yù)測的準(zhǔn)確性。算法的MAE 越小表明算法的預(yù)測越準(zhǔn)確，意味著算法的推薦質(zhì)量越高。設(shè)預(yù)測用戶評分的集合表示為{p1，p2，…，pN}，對應(yīng)的實際用戶評分集合為{q1，q2，…，qN}，則:

4.3 算法的復(fù)雜度分析

一個算法質(zhì)量的優(yōu)劣將直接影響到算法乃至整個程序的效率，為了檢驗算法性能與改進(jìn)算法，需對算法進(jìn)行復(fù)雜度分析。在本文所描述的3 種算法中，算法的時間復(fù)雜度主要由兩部分組成:計算相似度矩陣與找出k 鄰近用戶或項目并計算預(yù)測評分所需的時間來決定的。假設(shè)某數(shù)據(jù)集中，用戶數(shù)為m，項目數(shù)為n。在IFUBCF 與IFIBCF 算法中，計算相似度矩陣的時間復(fù)雜度分別為O(m2n)與O(mn2)。在IFBWCF 算法中則為O(m2n)+O(mn2)。在IFUBCF 與IFIBCF 算法中，時間復(fù)雜度分別為O(mn2)與O(m2n)。在IFBWCF 中為O(m2n)+O(mn2)。所以，在用戶數(shù)大于項目數(shù)的情況下，3 種算法的時間復(fù)雜度分別為O(m2n)、O(mn2)與O(m2n)，否則分別為O(mn2)、O(m2n)與O(m2n)，與傳統(tǒng)的User-based 協(xié)同過濾算法(O(mn2))和Item-based 協(xié)同過濾算法(O(m2n))基本一致。

4.4 參數(shù)的取值分析

由于本文對于數(shù)據(jù)集采用All but one 算法進(jìn)行處理，即每次評分?jǐn)?shù)據(jù)的隱藏都是隨機(jī)的，相當(dāng)于每次進(jìn)行運算的數(shù)據(jù)集都在變化，這也必然導(dǎo)致根據(jù)評分算法得出的預(yù)測評分的上下浮動。因此，本文對于α 值的選取采用在每個節(jié)點計算5 次，然后取其均值。本次實驗中在選取不同鄰居點數(shù)目情況下，分別使α取0.5，1.0，1.5，2.0，2.5，3.0，3.5，4.0 對3 種算法進(jìn)行測試，以便求出使各算法最優(yōu)的α 值。α 值對3 種算法影響的實驗結(jié)果如圖1～圖4 所示。

圖1 最近鄰居數(shù)為10 時α 對算法的影響

圖2 最近鄰居數(shù)為20 時α 對算法的影響

圖3 最近鄰居數(shù)為30 時α 對算法的影響

圖4 最近鄰居數(shù)為40 時α 對算法的影響

可以看出，隨α 值的增加:圖1 中IFIBCF 算法與IFUBCF 算法呈遞增趨勢，IFWBCF 算法呈遞減趨勢，在1.0 與1.5 處，3 個算法總體MAE 最小;圖2 中IFIBCF 算法呈遞增趨勢，IFUBCF 算法在1.5～2.0 間取得最小值，IFWBCF 算法在2.5 以后逐漸下降;圖3表明3 個算法在1.0～1.5 間總體MAE 最小;圖4 中3個算法都呈遞增趨勢α 值越小，總體MAE 越好。分析可得，當(dāng)α 取1 時，3 種算法的總體MAE 值較小，也即3 種算法在此時預(yù)測評分最準(zhǔn)確。因此，本文對算法進(jìn)行評價性測試時，α 統(tǒng)一為1。

4.5 算法分析

通過對PLSA 算法與本文所給出的3 種算法進(jìn)行試驗對比，從數(shù)據(jù)集中隨機(jī)抽取98 個用戶的評分?jǐn)?shù)據(jù)。對于這些數(shù)據(jù)采用All But One 算法進(jìn)行隱藏處理，然后對這些被隱藏評分的項目進(jìn)行預(yù)測評分。最后計算預(yù)測評分與實際評分的偏差值，通過MAE 的值來度量預(yù)測評分的準(zhǔn)確度。在最近鄰居數(shù)分別選取5，10，15，20，25，30，35，40 時分別運行IFUBCF、IFIBCF、IFBWCF、PLSA 算法，對每個算法在各鄰居點分別運行5 次取其均值。實驗結(jié)果如圖5所示。

圖5 各協(xié)同過濾算法的對比

實驗結(jié)果表明，本文提出的基于影響因子的加權(quán)協(xié)同推薦算法與其他算法相比，具有較小的MAE值，推薦的準(zhǔn)確度較高，能夠獲得更好的推薦質(zhì)量。

5 結(jié)束語

本文從基于用戶與基于項目2 個角度對協(xié)同過濾算法進(jìn)行改進(jìn)，在計算用戶相似性時，考慮了用戶間共同評分項目的個數(shù)對于相似性的影響。在計算項目相似度時，考慮對項目有共同評分的用戶的個數(shù)對于相似度的影響。這種方法增加了相似度計算的合理性，使得對于未評分項的預(yù)測更為準(zhǔn)確。并且在這2 種改進(jìn)算法的基礎(chǔ)上，提出一種基于影響因子的加權(quán)協(xié)同過濾算法，能更加客觀地把2 種情況下的預(yù)測評分綜合起來平滑2 種情況下的得分，使得預(yù)測評分能夠更加接近實際得分值，進(jìn)而獲得更好的推薦質(zhì)量。下一步將研究一種能夠根據(jù)不同用戶的選擇自動修正評分算法的新方法，以進(jìn)一步提高算法的推薦質(zhì)量與智能性。另外，基于海量數(shù)據(jù)的推薦算法優(yōu)化也是今后一個重要的研究方向。

［1］胡福華，鄭小林，干紅華.基于相似度傳遞的協(xié)同過濾算法［J］.計算機(jī)工程，2011，37(10):50-51，54.

［2］Shahab I C，Chen Y S.An Adaptive Recommendation System Without Explicit Acquisition of User Relevance Feedback［J］.Distributed and Parallel Databases，2003，14(2):173-192.

［3］Deshpande M，Karypis G.Item-based Top-n Recommendation Algorithms［J］.ACM Transactions on Information Systems，2004，22(1):143-177.

［4］夏小伍，王衛(wèi)平.基于信任模型的協(xié)同過濾推薦算法［J］.計算機(jī)工程，2011，37(21):26-28.

［5］Papagelis M，Plexousakis D，Kutsuras T.Alleviating the Sparsity Problem of Collaborative Filtering Using Trust Inferences［M］.Berlin，Germany:Springer，2005.

［6］Lam X N，Vu T，Le T D，et al.Addressing Cold-start Problem in Recommendation Systems［C］//Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication.［S.1.］:ACM Press，2008:208-211.

［7］Melville P，Mooney R J，Nagarajan R.Content-boosted Collaborative Filtering for Improve Recommendations［C］//Proceedings of National Conference on Artificial Intelligence.London，UK:MIT Press，2002:187-192.

［8］George T，Merugu S.A Scalable Collaborative Filtering Framework Based on Co-clustering［C］//Proceedings of the 5th IEEE International Conference on Data Mining.Texas，USA:IEEE Press，2005:4.

［9］侯翠琴，焦李成，張文革.一種壓縮稀疏用戶評分矩陣的協(xié)同過濾算法［J］.西安電子科技大學(xué)學(xué)報，2009，36(4):614-618.

［10］Chun Zeng，Xing Chunxiao，Zhou Lizhu.Similarity Measure and Instance Selection for Collaborative Filtering［C］//Proceedings of the 12th International Conference on World Wide Web.Budapest，Hungary:ACM Press，2003:652-658.

［11］汪 靜，印 鑒，鄭利榮，等.基于共同評分和相似性權(quán)重的協(xié)同過濾推薦算法［J］.計算機(jī)科學(xué)，2010，37(2):99-104.

［12］Sarwar B，Karypis G，Konstan J，et al.Item-based Collaborative Filtering Recommendation Algorithms［C］//Proceedings of the 10th International Conference on World Wide Web.USA:ACM Press，2001:285-295.

［13］Massa P，Avesani P.Trust-awareCollaborative Filtering for Recommender Systems ［M］.Berlin，Germany:Springer，2004.

［14］Ghazanfar M，Prugel-Bennett A.NovelSignificance Weighting Schemes for Collaborative Filtering:Generating Improved Recommendations in Sparse Environments［C］//Proceedings of 2010 International Conference on Data Mining.［S.1.］:IEEE Press，2010:215-223.