范奧哲 何利力

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

關(guān)鍵詞：協(xié)同過濾推薦算法;數(shù)據(jù)稀疏性;聚類;推薦系統(tǒng)

DOI：10. 11907/rjdk. 191963 開放科學(xué)（資源服務(wù)）標識碼（OSID）：

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

0 引言

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

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

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

1 傳統(tǒng)協(xié)同過濾推薦算法

傳統(tǒng)協(xié)同過濾推薦算法[12]是指根據(jù)數(shù)據(jù)集構(gòu)建用戶—項目評分矩陣，計算目標用戶與其他用戶之間的相似度，并根據(jù)相似度尋找最近鄰居集合，最終為目標用戶預(yù)測評分產(chǎn)生推薦列表的過程。其實現(xiàn)過程可分為如下3個步驟：

1.1 用戶—項目評分矩陣構(gòu)建

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

1.2 尋找最近鄰居

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

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

1.3 預(yù)測評分產(chǎn)生推薦

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

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

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

2 雙向聚類協(xié)同過濾推薦算法

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

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

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

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

2.2 相似度計算方法改進

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

2.3 預(yù)測評分產(chǎn)生推薦

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

其中，[Pu]表示在用戶維度進行K-means聚類后的預(yù)測評分，[Pi]表示在項目維度進行K-means聚類后的預(yù)測評分，[λ（0<λ<1）]為平衡因子，通過上式可得到綜合的預(yù)測評分[P]。該公式具體含義是從用戶和項目兩個方向進行預(yù)測評分，然后加權(quán)求和，通過動態(tài)調(diào)整[λ]的值，以平衡用戶和項目兩個方向?qū)︻A(yù)測評分的影響。通過上式可知，當(dāng)[λ]=1時，變?yōu)閷τ脩艟S度單項聚類的協(xié)同過濾推薦，當(dāng)[λ]=0時，變?yōu)閷椖烤S度單項聚類的協(xié)同過濾推薦。實際應(yīng)用中應(yīng)該動態(tài)調(diào)整[λ]的值，同時考慮兩個維度的預(yù)測值，使綜合預(yù)測評分獲得最優(yōu)解，最終產(chǎn)生精準推薦。

2.4 改進后算法描述

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

3 實驗與分析

3.1 實驗數(shù)據(jù)與評估指標

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

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

3.2 實驗方案與結(jié)果分析

本文通過3個實驗方案驗證提出算法的優(yōu)越性，通過前兩個實驗動態(tài)調(diào)整聚類中心K和平衡因子[λ]，使其達到最佳推薦效果。在最佳參數(shù)條件下，驗證本文算法相比傳統(tǒng)協(xié)同過濾推薦算法的優(yōu)越性。

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

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

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

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

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

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

4 結(jié)語

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

參考文獻：

[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] 黃立威，江碧濤，呂守業(yè)，等. 基于深度學(xué)習(xí)的推薦系統(tǒng)研究綜述[J]. 計算機學(xué)報，2018，41（7）：1619-1647.

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

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

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

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

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

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

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

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

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

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

[13] 黃正. 面向數(shù)據(jù)稀疏的協(xié)同過濾推薦算法研究與優(yōu)化[D]. 廣州：華南理工大學(xué)，2012.

[14] 項亮. 推薦系統(tǒng)實戰(zhàn)[M]. 北京：人民郵電出版社，2012.

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

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

[17] 李榮，李明奇，郭文強. 基于改進相似度的協(xié)同過濾算法研究[J]. ?計算機科學(xué)，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] 翁小蘭，王志堅. 協(xié)同過濾推薦算法研究進展[J]. 計算機工程與應(yīng)用，2018，54（1）：25-31.

（責(zé)任編輯：黃 健）