融合影響因子的加權協同過濾算法

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

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

1 概述

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

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

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

2 問題描述

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

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

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

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

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

3 本文算法

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

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

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

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

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

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

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

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

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

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

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

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

3.3 加權的協同過濾算法

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

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

4 實驗結果與分析

實驗所采用的PC 機的配置為Intel(R)Core(TM)i5 2.8 GHz CPU，4 GB 內存，操作系統為Windows XP，算法使用Matlab 實現。

4.1 數據集與實驗方案

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

4.2 算法的評價標準

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

4.3 算法的復雜度分析

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

4.4 參數的取值分析

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

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

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

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

圖4 最近鄰居數為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 越好。分析可得，當α 取1 時，3 種算法的總體MAE 值較小，也即3 種算法在此時預測評分最準確。因此，本文對算法進行評價性測試時，α 統一為1。

4.5 算法分析

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

圖5 各協同過濾算法的對比

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

5 結束語

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

［1］胡福華，鄭小林，干紅華.基于相似度傳遞的協同過濾算法［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］夏小伍，王衛平.基于信任模型的協同過濾推薦算法［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］侯翠琴，焦李成，張文革.一種壓縮稀疏用戶評分矩陣的協同過濾算法［J］.西安電子科技大學學報，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］汪 靜，印 鑒，鄭利榮，等.基于共同評分和相似性權重的協同過濾推薦算法［J］.計算機科學，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.