協同過濾推薦算法的改進與研究

孫華艷，李業麗，字云飛，韓 旭

(北京印刷學院 信息工程學院，北京 102600)

0 引 言

伴隨著互聯網的迅速發展，智能化、個性化的服務成為電商產業極大的需求，如何通過存儲有海量數據的自媒體為用戶提供個性化的推薦成為了智能網絡研究的熱點。研究人員提出了以協同過濾推薦算法為主流的多種推薦算法，相比其他算法，協同過濾推薦算法的易實現性和可擴展性使其在電商和自媒體等領域應用廣泛。但隨著互聯網數據呈幾何級數增長、數據內容復雜度不斷提高，協同過濾技術也面臨著兩個瓶頸問題[1-5]：數據的稀疏性和可擴展性。

數據稀疏性問題是推薦系統面臨的主要問題，也是導致系統推薦質量下降的主要原因[6]。目前，對該問題的解決分為兩類，一類為矩陣填充技術，另一類為矩陣降維技術[6-8]。矩陣填充技術比較理想的方法有BP神經網絡、Naive Bayesian分類方法、基于內容的預測[9-10]。矩陣降維技術比較典型的方法是奇異值分解(singular value decomposition，SVD)技術[11-12]。針對個性化推薦過程中最近鄰準確性的不足，文中提出了基于因果聚類分析的協同過濾推薦算法和基于模糊相似關系的協同過濾推薦算法。前者利用因果聚類對收集的信息進行分析研究，找出其內在聯系，實現個性化的精準推薦。后者通過最大樹法及確定最佳閾值λ以更加合理、精準地計算最近鄰[13-14]。最后將算法應用于美食推薦系統中進行驗證[15]。

1 傳統的協同過濾推薦算法

協同過濾(collaborative filtering，CF)推薦算法[16-18]是通過對用戶—項目之間的評價、分享、轉存等數據的分析，找出基于用戶或項目的相似度，實現精準化推薦。協同過濾推薦算法分為：(1)基于用戶的協同過濾推薦算法(user-based collaborative filtering)，通過用戶搜索，對喜歡產品的評價、收藏等數據信息度量有相同行為的用戶之間的關系來實現產品的推薦。(2)基于項目的協同過濾推薦算法(item-based collaborative filtering)，通過不同用戶對于不同產品的評價及喜好程度來度量產品之間的緊密程度，從而實現產品的推薦。

1.1 協同過濾推薦算法的實現

(1)收集用戶—項目數據；

(2)計算用戶—項目的相似度，找出最近鄰或相似度最高的N個用戶或項目；

(3)把N個相似度最高的用戶或項目推薦給對應的項目或用戶。

1.2 相關度評價計算

計算相似度之后尋找最近鄰，令Zum為最近鄰，對項目的s預測評分的計算為：

(2)

(3)

其中，Ts為項目總和；muw為u對產品w的評價值。

(2)余弦相似度(cosine similarity)：通過兩個或以上用戶對不低于兩個產品的評分來計算兩用戶之間的興趣相似度。設用戶x和y對產品的評價數組數據為x和y，相似度計算如下：

(4)

2 基于因果聚類的協同過濾推薦算法

事物本身的因果關系就存在著相似性，也就是可以通過對以往的經驗和數據尋找事物存在的規律。例如：用戶a因為喜歡《python數據挖掘》，所以他也可能喜歡《數據挖掘算法》，它們之間存在著這種因果關系。同理對于a和b兩個用戶，因為他們之間有共同喜愛的一門課程，那么他們之間也有可能存在共同喜愛的另外一門課程。本節基于因果聚類的協同過濾推薦算法，將以更加精細和準確的關聯計算來實現項目的精準可靠推薦。引入項目和用戶的因果關系計算相似性更進一步提高度量相似度。

2.1 因果模糊聚類

因果模糊聚類[19-20]的核心是擇近原則。設對要分析處理的項目集α，每個項目存在的特征值為(x1,x2,…,xn)，然后對特征值的因果模糊聚類和模式識別判定、預測它們的歸屬性，從而實現更好的推薦。

2.2 因果模糊聚類實現過程

(1)特征模糊集的建立。

設所有項目集為α，對于α的聚類通過三元結構(X,Y,φ)處理，所以X=(X1×X2×…×Xn)是n元Descartes累乘，Y為非空冪集，φ為X到Y的映射，如：φ:X1×X2×…×Xn→Y。

同時記zt=(xt,yt)，通過模糊等價計算出對應的最佳聚類(z1,z2,…,zm)=(T1,T2,…,Tm)，特征模糊集Vi={xt1,xt2,…,xtki}(i=1,2,…,m)，其中(xts,yts)為項目Ti的最佳聚類，Vi是Ti的特征軸投影。計算：

(5)

(6)

對于x=(x1,x2,…,xn)屬于項目的特征值，令

(7)

其中，i,j=1,2,…,m為特征取值的范圍；(ω1,ω2,…,ωn)為一組確定的權重。

令Wi={yt1,yt2,…,ytki}，其中i=1,2,…,m，(xts,yts)=zts屬于項目最佳聚類Ti，Wi是Ti的預測相似軸投影，計算：

(8)

建立因果模糊聚類A∈X,對應項目的分類(T1,T2,…,Tm)為：

(2)進行因果聚類的判定。

若s期特征的狀態為確定特征值xs∈X，則xs與{P1,P2,…,Pm}為最大隸屬度原則，Aj=max(A1(u0),A2(u0),…,An(u0))。

若s期特征的狀態為模糊集Bs∈X,則Bs與{P1,P2,…,Pm}通過擇近原則。

最后，選取Pi0，同時對應的Ii0為項目集α與s期的因果聚類的模糊判定值(i0∈{1,2,…,m})。

該方法通過計算某項目影響推薦效果的n個因素，計算并構造相應的三角模糊數，最后根據最大隸屬度原則或擇近原則進行模糊預測，從而找出影響最終推薦的可能性最大的因素及特征值，再根據這一影響因素實現精準、個性化的推薦。

步驟1：對于項目的原始特征及數據，進行標注化處理，標定值的大小表示兩個特征之間的相似度；

步驟2：通過計算將項目原始特征數據轉化成模糊矩陣R；

步驟3：將模糊矩陣R進行模糊聚類分析，并且計算出最佳聚類；

步驟4：根據各聚類的特征函數及權值，構建三角模糊數，從而選取最佳特征值，實現精準、個性化推薦。

2.3 最近鄰的取值

算法最后通過對項目的評價、分享、收藏等原始數據值最高的特征進行計算及分析處理，最佳特征為一個取值空間的中間值，所以以中間值為中心的不超過兩端取值范圍為最佳特征數。

3 基于模糊相似關系的協同過濾推薦算法

用戶在網上有目標的搜索是一種顯性需求，然而顯性需求的信息數據背后隱藏著隱性需求，這就是個性化推薦的核心。起初，網站極少的用戶共同評價數據，很難準確地獲得最近鄰。例如，兩個非常喜歡計算機科學的用戶由于不存在共同評價數據，其相似度計算結果為零。而與他們不是同一類的書籍愛好者由于存在評價數據，相似度反而高于零。這就是網站對于新用戶評價項目的第一評價以及數據稀疏性問題，僅以共同評價數據判斷相似級別顯然不精準。文中通過結合項目所屬分類來計算用戶的相似程度，這是由于用戶對于統一屬性的項目會有相似的喜好程度。

用戶喜歡的項目類可能擁有多個特征，而它們之間又可能存在著特征重疊或相通性，所以可以通過模糊相似關系的直接聚類法求其項目之間的緊密程度，也就是相似度。基于模糊相似關系的協同過濾推薦算法就是通過求其最大樹法尋找最近鄰，從而實現個性化精準推薦。

基于模糊相似關系的協同過濾推薦算法[21]是通過對項目的標定得到模糊矩陣R，然后根據相似矩陣R得到一棵權重樹，通過最佳閾值λ確定法對相似矩陣進行截集，應用直接聚類求出相似性，獲得最佳聚類，最后對用戶進行精準的個性化產品推薦。

3.1 相似關系的協同過濾推薦算法的實現過程

(1)項目特征值的標定。

從項目ui和uj中選取最具有特征性的m個特征值，分別為ui=(xi1,xi2,…,xim)、uj=(xj1,xj2,…,xjm)，然后計算得到項目模糊相似矩陣。

(9)

(2)構造最大樹。

首先，根據第1步對項目特征值的標定得到模糊相似矩陣R，畫出被分類因素為節點，以相似矩陣R的因素rij為權重的一棵最大樹；其次，選取最佳閾值λ；最后，砍斷權重低于λ的枝，得到一幅連通圖，相聯的分支就構成了λ水平上的分類，這就是獲得相似度較高的最佳聚類。

(3)計算最佳閾值λ。

要實現精準、個性化推薦，閾值λ的選取是核心。通過模糊相似矩陣依次取λ的最大樹，再利用最大樹法得到的截集來實現精準、個性化推薦。

聚類圖可以給出各λ對應的分類，形成一種動態聚類。對于閾值λ的選取，由于人為的分類總是帶有主觀性，所以可用F-統計量來選取。

(10)

通過最佳閾值λ確定法計算模糊相似矩陣的方法，可以更精準地把相似度高的特征屬性項目聚為同一種推薦項目，然后運用這一方法對用戶進行精準、個性化的產品推薦。

3.2 最近鄰的取值

4 實驗結果及分析

4.1 數據集合

實驗數據是在合法范圍內，基于Python語言的數據挖掘技術在美團網上抓取的。美團網擁有中國最多的美食信息資源，也是國內最活躍、最權威的外賣網之一。抓取數據中包含對美食的評分(值為1～5，值越大表明用戶喜好度越高)、特征和網絡社交關系等。在美團網上用戶可以對美食進行等級評分、收藏以及給朋友分享推薦，所以美團網的數據對于美食推薦具有很高的參考價值。其中抓取了10萬條評分數據，含有947個用戶對1 678個美食的評判分數，每個用戶不少于對27個美食進行評分。

4.2 數據密度計算

利用用戶對美食的評分值來表達對美食的喜愛程度。

數據密度=100 000/(947×1 678)=0.062 9

(11)

表明數據的稀疏性非常高。

4.3 測試原則

通過對抓取數據隨機抽取70 000條作為實驗訓練集，抽取30 000條作為測試集，分別對傳統過濾推薦算法和基于因果聚類和模糊相似關系的協同過濾推薦算法進行實驗。

4.4 度量標準

文中應用的統計精度測量中的絕對誤差(MAE)是度量推薦結果好壞的最有效方法之一。MAE值越小表明推薦效果越佳。

(12)

其中，m為項目集中評分項的量；pi為對算法預估的評判分數；qi為測試數據的實際分數。

4.5 實驗結果

實驗基于抓取的數據對傳統的協同過濾推薦算法與因果聚類及模糊相似關系的協同過濾推薦算法進行了平均絕對誤差值的比較分析，如圖1所示。最近鄰的數量也將影響推薦的效果，過少將會降低推薦的精準性，過多將極大增加算法的復雜度，實驗中選取最近鄰的數量為10～40。

圖1 3種算法的MAE比較

通過圖1可知，無論選取多大最近鄰數，提出的基于因果聚類及模糊相似關系的協同過濾推薦算法的平均MAE都低于傳統推薦算法，表明該算法具有較高的精準度，對推薦系統精準度的提高有明顯幫助。其中基于因果聚類的協同過濾推薦算法在最近鄰數量低于23左右時，精準度略高于基于模糊相似關系的協同過濾推薦算法。這是因為因果聚類是基于模糊相似關系法中的模糊矩陣加各項目的權重來進行聚類分析推薦，所以它的平均絕對誤差略小。當最近鄰高于23以后，因果聚類法的最終預測值在最大隸屬度或擇近范圍中會擴大，所以精準度趨于不變，而基于模糊相似關系的協同過濾推薦算法的精準度則繼續提高。

5 結束語

各推薦算法中相似度度量法的好壞直接影響了推薦項目或用戶的精準度和個性化。文中提出的基于因果聚類與模糊相似關系的協同過濾推薦算法主要通過增加項目權重的三角模糊數法和計算最大樹及最佳閾值λ確定法來提高相似度的度量。同時，該算法通過對項目或用戶特征值的內外距離計算或加權計算特征模糊集，都能減小稀疏性帶來的負面影響。下一步將結合聚類技術解決協同過濾推薦技術的可擴展性問題。