一種雙向聚類協同過濾推薦算法研究

范奧哲 何利力

摘 要：針對傳統協同過濾推薦算法在大數據環境下存在數據稀疏性及計算復雜性等問題，提出一種雙向聚類協同過濾推薦算法。該算法首先從用戶維度和項目維度兩個方向分別進行屬性聚類，然后在目標用戶和目標項目所在類簇中分別使用改進后的相似度計算方法進行協同過濾推薦，最后通過平衡因子綜合預測評分并形成最終推薦列表。在MovieLens公開數據集上進行實驗，結果表明，該算法（DCF）相比傳統協同過濾推薦算法（TCF）、基于用戶聚類的協同過濾推薦算法（UCF）以及基于項目聚類的協同過濾推薦算法（ICF），在平均絕對誤差上分別降低了16%、8.1%、7.5%，有效提高了推薦精度。

關鍵詞：協同過濾推薦算法;數據稀疏性;聚類;推薦系統

DOI：10. 11907/rjdk. 191963 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）005-0078-05

0 引言

隨著互聯網技術的快速發展，各種信息呈爆炸式增長，人類進入信息超載時代。面對海量信息，如何從中找到自己想要的內容成為一個亟需解決的問題。目前人們可通過搜索引擎尋找自己感興趣的內容，從一定程度上解決了信息超載問題，但搜索引擎仍不能完全滿足人們的個性化需求，存在較大局限性，因此推薦系統[1]應運而生。推薦系統作為一種有效的信息過濾手段，是解決信息超載問題及實現個性化推薦的重要方式。

推薦系統的核心內容是推薦算法，常用推薦算法有基于協同過濾的推薦算法、基于內容的推薦算法與混合推薦算法[2-3]。其中協同過濾（Collaborative-Filtering，CF）推薦算法應用最為廣泛，根據用戶歷史行為信息即可完成推薦。協同過濾推薦算法根據對象不同可分為兩類：基于用戶或基于項目的協同過濾[4]。其中，基于用戶的協同過濾是通過尋找目標用戶的相似用戶，將相似用戶的相關喜好推薦給目標用戶;基于項目的協同過濾是通過計算項目間的相似度，將相似項目推薦給喜歡當前項目的用戶[5]。其共同特點是計算用戶或項目之間的相似度，因此相似度計算在協同過濾推薦中起著至關重要的作用。但是隨著大數據時代的到來，傳統協同過濾推薦算法難以解決大數據環境帶來的數據稀疏性、計算復雜性等問題[6]。

針對以上問題，研究人員提出了一系列解決方案。例如，胡朝舉[7]、許智宏等[8]將基于用戶的模糊聚類應用到協同過濾推薦算法中，將用戶劃分到不同用戶簇中，使同一簇中用戶相似度最高，并在同一簇中進行協同過濾推薦。聚類的引入降低了數據稀疏性和計算復雜性，并提高了推薦精度;張林等[9]將基于項目的聚類思想引入協同過濾推薦算法中，充分挖掘用戶對項目類的興趣度以及項目在類中的權重關系，提高了推薦效果。然而，以上基于聚類的協同過濾推薦算法都只考慮了用戶屬性或項目屬性單方面聚類對推薦的影響，而沒有同時考慮用戶屬性和項目屬性雙向聚類對推薦結果的影響。還有一些學者為提高推薦精度，將研究方向放在對相似度的改進上。如任看看等[10]對Jaccard相似性進行改進，在相似度計算中充分考慮共同評分項與所有評分項之間的關系，以及用戶評分差異對相似度計算的影響，最終得到較為精確的推薦結果;孟俊才等[11]在相似度計算中提出平均分懲罰機制和共同評分項懲罰機制，對缺失的項目評分進行計算，提高了推薦準確性。但在傳統相似度計算方法中，通常只考慮評分值或評分項單方面對相似度計算造成的影響，該方式顯然是片面的，無法準確描述出其之間的相似關系。因此，本文首先對用戶屬性和項目屬性分別進行聚類分析，然后在相應類簇中使用改進后的相似度計算方法對二者分別進行預測評分，最后通過平衡因子綜合預測評分，并形成最終推薦列表。實驗結果表明，該算法降低了數據稀疏性和計算復雜性，并提高了推薦精度。

1 傳統協同過濾推薦算法

傳統協同過濾推薦算法[12]是指根據數據集構建用戶—項目評分矩陣，計算目標用戶與其他用戶之間的相似度，并根據相似度尋找最近鄰居集合，最終為目標用戶預測評分產生推薦列表的過程。其實現過程可分為如下3個步驟：

1.1 用戶—項目評分矩陣構建

根據用戶對項目的評分信息能夠構建出用戶—項目評分矩陣[Rm×n]，如表1所示。其中m行、n列分別表示用戶數和項目數，矩陣值[Rm×n]表示某個用戶對某項目的評分值，評分值通常與評分項目類別有關。例如在電影推薦中，評分值通常用整數表示，范圍是1～5分，當沒有評分信息時用0填充。

1.2 尋找最近鄰居

尋找最近鄰居是指通過計算用戶或項目之間的相似度，選取與目標用戶相似度最大的N個用戶作為目標用戶的最近鄰居。其中相似度計算是協同過濾算法最核心的內容，目前廣泛使用的相似度計算方法有余弦相似性、Jaccard相似性、Pearson相似性，其中最常用的是Jaccard相似性和Pearson相似性[13]。

Jaccard相似性：Jaccard相似性通常表示為樣本集合中公共部分在所有樣本集合中所占比重，在推薦算法中兩個用戶的相似度計算公式如式（1）所示。

1.3 預測評分產生推薦

根據前面得到鄰居用戶對目標項目的評分，預測目標用戶對該項目的評分值，產生最終推薦列表。其計算公式如式（3）所示。

其中，[Pu，i]表示目標用戶[u]對項目[i]的預測評分值，[Ru]、[Rv]表示用戶[u]、[v]對項目的平均評分值，[Rv，i]表示目標用戶[u]最近鄰居集中用戶[v]對項目[i]的評分，[N]表示目標用戶最近鄰居的用戶個數。

通過以上對傳統協同過濾推薦算法的分析可知，相似度計算在推薦過程中起著至關重要的作用，并且傳統協同過濾推薦算法中并沒有考慮用戶屬性和項目屬性聚類對相似度計算的影響。因此，本文提出一種基于用戶屬性和項目屬性雙向聚類及改進相似度計算的協同過濾推薦算法。

2 雙向聚類協同過濾推薦算法

2.1 基于用戶與項目的屬性聚類

在大數據背景下，由于用戶對項目的評分數據過少，導致用戶—項目評分矩陣過于稀疏，從而影響了用戶或項目相似度計算的精確度。同時隨著用戶和項目規模的不斷擴大，其計算復雜度也在不斷增加，對于具有m個用戶、n個項目的用戶—項目評分矩陣而言，傳統協同過濾推薦算法的時間復雜度為[O（n*m*m）][14]。因此，為了降低數據稀疏性與計算復雜性，利用聚類技術對原始數據進行聚類預處理是優化推薦結果的常用策略之一。通過聚類技術將用戶和項目根據屬性信息分別聚類到若干個類簇中，使得同一類簇中的用戶或項目相似度最高，而不同類簇中的相似度最低，從而將最近鄰居選擇縮小到對應類簇中，降低相似度計算的復雜性。

針對用戶屬性和項目屬性，在進行聚類前，需要對數據進行標準化處理。例如在用戶屬性中考慮年齡、性別、職業等，將年齡定義為數值類型表示，性別用0或1分別表示女性或男性，職業定義為標稱型數據，使用數值標號的形式進行標準化[15]。通過該形式的預處理，可得到用戶屬性表達形式為User={23，1，11}，即年齡為23歲從事軟件開發的男性。同理可得項目屬性標準化處理后的表達形式。

傳統基于用戶或基于項目聚類的協同過濾推薦算法，僅從某個方向進行單向聚類，在一定程度上降低了數據稀疏性對相似度計算的影響，但這種考慮是不夠全面的。為了解決這一問題，本文提出基于雙向的屬性聚類分析，分別從用戶維度和項目維度兩個方向進行屬性聚類，然后分別進行協同過濾推薦，從而進一步提高推薦精準度。本文采用使用廣泛且計算簡單的K-means聚類算法，分別從用戶和項目兩個維度進行聚類。K-means聚類[15]基本思想是首先在數據源中選擇K個點作為初始聚類中心，然后計算數據源中其它點到所有初始聚類中心的距離，將距離近的用戶劃分到對應簇中，計算簇中所有元素平均值作為當前簇新的聚類中心，如此迭代，直到所有簇的聚類中心不再變化，輸出聚類后的結果。該算法時間復雜度為[O（m*k*t）]，其中m代表數據源中的元素個數，k代表聚類中心個數，t代表迭代次數[15]。基于用戶的K-means聚類算法流程如圖1所示，同理可得基于項目的K-means聚類。

2.2 相似度計算方法改進

由于相似度計算在推薦算法中的核心地位，其計算準確性將直接影響推薦質量。傳統Pearson相似性是根據兩個用戶共同評分項目的集合計算不同用戶之間的差異[16-17]，在計算兩個用戶相似度時忽略了平均值差異，并且沒有考慮用戶對一些相同項目評分所占比重對相似度計算的影響，從而影響了最終推薦結果。例如用戶A、B共同購買了10件商品，但他們沒有給出相似評分，用戶A、C共同購買了3件商品，但他們給出了相同或相似評分。通過Pearson相似性計算，A、B之間的相似度小于A、C之間的相似度，而事實上A、B的相似度明顯大于A、C的相似度，在需求比較嚴謹的情況下應該避免此類問題產生。傳統Jaccard相似性主要根據用戶共同評分項目在所有評分項目中所占比重計算相似度，并沒有考慮用戶實際評分值對相似度計算的影響。

2.3 預測評分產生推薦

通過改進相似度計算，得到目標用戶的最近鄰居集合，并據此預測目標用戶對未評分項的評分，最后進行個性化推薦。利用上述改進的相似度計算方法，本文將綜合用戶和項目兩個維度的協同過濾，在兩個方向進行預測評分，然后通過平衡因子綜合預測評分，形成最終推薦列表，如式（6）所示。

其中，[Pu]表示在用戶維度進行K-means聚類后的預測評分，[Pi]表示在項目維度進行K-means聚類后的預測評分，[λ（0<λ<1）]為平衡因子，通過上式可得到綜合的預測評分[P]。該公式具體含義是從用戶和項目兩個方向進行預測評分，然后加權求和，通過動態調整[λ]的值，以平衡用戶和項目兩個方向對預測評分的影響。通過上式可知，當[λ]=1時，變為對用戶維度單項聚類的協同過濾推薦，當[λ]=0時，變為對項目維度單項聚類的協同過濾推薦。實際應用中應該動態調整[λ]的值，同時考慮兩個維度的預測值，使綜合預測評分獲得最優解，最終產生精準推薦。

2.4 改進后算法描述

本文提出一種基于雙向聚類的協同過濾推薦算法，具體過程如下：首先通過用戶歷史行為數據構建用戶—項目評分矩陣，其次從用戶和項目兩個維度分別使用K-means聚類算法進行用戶聚類和項目聚類，然后使用改進的相似度計算方法分別計算兩個維度的預測評分，最后通過平衡因子動態調整綜合預測評分，并產生推薦列表。具體推薦流程如圖2所示。

3 實驗與分析

3.1 實驗數據與評估指標

本文采用美國明尼蘇達大學GroupLens實驗室收集整理的MovieLens公開電影評分數據集，該數據集包含了用戶屬性信息、電影屬性信息、用戶對電影評分信息等。實驗所用評分信息包含943名用戶對1 682部電影產生的100 000條評分記錄，其中每位用戶至少對其中20部電影進行了打分，評分范圍為1～5分，評分越高表示用戶對該電影喜愛程度越高。為驗證本文算法的優越性，將訓練集和測試集比例設為4∶1，進行交叉重復實驗，訓練集用于訓練算法中的相關參數，測試集用于驗證算法準確性。

在推薦系統中評價推薦結果的指標有多種，其中廣泛使用的是平均絕對誤差MAE（Mean AbsoluteError），其是通過計算預測值與實際值之間的平均絕對誤差得到的，平均絕對誤差的值越小，表示推薦結果越好[18-20]。若用戶預測評分集合為[p={p1，p2，？，pn}]，用戶實際評分集合為[q={q1，][q2，？，qn}]，則MAE表達式如式（7）所示。

3.2 實驗方案與結果分析

本文通過3個實驗方案驗證提出算法的優越性，通過前兩個實驗動態調整聚類中心K和平衡因子[λ]，使其達到最佳推薦效果。在最佳參數條件下，驗證本文算法相比傳統協同過濾推薦算法的優越性。

實驗1：在基于用戶或基于項目的K-means聚類協同過濾推薦算法中，選用不同K值產生的聚類效果是不一樣的，最終導致推薦結果也不同。為了驗證不同K值對推薦結果的影響，本文通過實驗動態調整K值，選擇最佳參數。實驗結果如圖3、圖4所示。

通過實驗可以看出，聚類中心K的選擇對推薦結果有著直接影響，過多或過少的聚類數目都會引起MAE值升高。從圖中可以看到，當K=10時，基于用戶聚類的協同過濾推薦達到最佳效果，當K=30時，基于項目聚類的協同過濾推薦達到最佳效果。

實驗2：平衡因子是確定基于用戶和項目雙向聚類預測評分，綜合獲取最終推薦的重要因素。因此，本文選取[λ]為0.1～0.9之間的數值，通過綜合評估獲取最佳參數。實驗中選取的聚類數目分別為K=10和K=30，最終得到的實驗結果如圖5所示。

通過以上實驗可以看到，當[λ]=0.4時MAE值最小，此時協同過濾推薦達到最佳效果，因此將[λ]的值設為0.4。

實驗3：為了驗證雙向聚類協同過濾推薦算法的精準度，將本文算法命名為DCF，與其它3種算法進行對比實驗。3種算法分別為傳統協同過濾推薦算法TCF、基于用戶聚類的改進相似度協同過濾推薦算法UCF、基于項目聚類的改進相似度協同過濾推薦算法ICF，實驗結果如圖6所示。

通過以上實驗可以看出，本文提出算法的MAE值在全局范圍內明顯小于其它3種協同過濾推薦算法，其中傳統協同過濾推薦算法的MAE值最大，而基于用戶或基于項目聚類的改進相似度協同過濾推薦算法MAE值略小，其兩者之間相差不大。在數值方面，基于雙向聚類的協同過濾推薦算法相比傳統協同過濾推薦算法的平均絕對誤差降低了16%，相比基于用戶聚類的協同過濾推薦算法降低了8.1%，相比基于項目聚類的協同過濾推薦算法降低了7.5%，從而證明了本文提出雙向聚類協同過濾推薦算法的準確性。

4 結語

針對傳統協同過濾推薦算法在大數據環境下存在的數據稀疏性、計算復雜性等問題，提出一種基于雙向聚類的協同過濾推薦算法。該算法首先從用戶維度和項目維度兩個方向分別進行屬性聚類，然后利用改進的相似度計算方法分別產生各自的預測評分，通過平衡因子綜合預測評分形成最終推薦列表。最后通過實驗得出，本文提出的推薦算法相比傳統協同過濾推薦算法的平均絕對誤差降低了16%，提高了推薦精度。然而，該算法雖然在很大程度上提高了推薦精度，但仍然存在一定提升空間，后續研究還可以考慮其它聚類算法對推薦結果的影響等。

參考文獻：

[1] SCHAFER J B，KONSTAN J A，RIEDL J. Recommender systems in E-Commerce[C]. In：ACM Conference on Electronic Commerce（EC99），1999：158-166.

[2] 黃立威，江碧濤，呂守業，等. 基于深度學習的推薦系統研究綜述[J]. 計算機學報，2018，41（7）：1619-1647.

[3] 孫輝，馬躍，楊海波，等. 一種相似度改進的用戶聚類協同過濾推薦算法[J]. 小型微型計算機系統，2014，35（9）：1967-1970.

[4] 王鵬，王晶晶，俞能海. 基于核方法的User-Based協同過濾推薦算法[J]. 計算機研究與發展，2013，50（7）：1444-1451.

[5] 關志芳，孟海東. 融合用戶聚類與項目聚類的加權Slope One算法[J]. 控制工程，2018，25（7）：1297-1302.

[6] 楊豐瑞，鄭云俊，張昌. 結合概率矩陣分解的混合型推薦算法[J]. 計算機應用，2018，38（3）：644-649.

[7] 胡朝舉，孫克逆. 基于用戶模糊聚類的個性化推薦研究[J]. 軟件導刊，2018，17（2）：31-34.

[8] 許智宏，田雨，閆文杰，等. 基于模糊聚類和改進混合蛙跳的協同過濾推薦[J]. 計算機應用研究，2018，35（10）：2908-2911.

[9] 張林，王曉東，姚宇. 基于項目聚類和時間因素改進的推薦算法[J]. 計算機應用，2016，36（S2）：235-238.

[10] 任看看，錢雪忠. 協同過濾算法中的用戶相似性度量方法研究[J]. 計算機工程，2015，41（8）：18-22，31.

[11] 孟俊才，李存志. 基于改進相似度計算方法的協同過濾算法[J]. 電子技術與軟件工程，2018（24）：151-152.

[12] 王巧，謝穎華，于世彩. 結合用戶聚類和項目類型的協同過濾算法[J]. 計算機系統應用，2016，25（12）：132-137.

[13] 黃正. 面向數據稀疏的協同過濾推薦算法研究與優化[D]. 廣州：華南理工大學，2012.

[14] 項亮. 推薦系統實戰[M]. 北京：人民郵電出版社，2012.

[15] 申晉祥，鮑美英. 基于用戶聚類與項目劃分的優化推薦算法[J]. 計算機系統應用，2019，28（6）：159-164.

[16] 于金霞，臧利明，王俊峰，等. 一種改進相似度的協同過濾算法[J]. 河南理工大學學報：自然科學版，2019，38（2）：116-121.

[17] 李榮，李明奇，郭文強. 基于改進相似度的協同過濾算法研究[J]. ?計算機科學，2016，43（12）： 206-208，240

[18] WEI Z. Optimization collaborative filtering recommendation algorithm based on ratings consistent[C]. The Institute of Electrical and Electronics Engineers，IEEE Beijing，2016：1055-1058.

[19] PAPAGELIS M，PLEXOUSAKIS D. Qualitative analysis of user- based and item-based prediction algorithms for recommendation agents[J]. Engineering Applications of Artificial Intelligence，2005， 18（7）：781-789.

[20] 翁小蘭，王志堅. 協同過濾推薦算法研究進展[J]. 計算機工程與應用，2018，54（1）：25-31.

（責任編輯：黃 健）