一種新型有向加權協同過濾算法的推薦技術研究?

彭康華 姚江梅 黃裕鋒

（廣東工程職業技術學院信息工程學院 廣州 510520）

1 引言

在大數據和“互聯網+”時代，某些用戶數據仍然以指數級的不斷飚升，也更加多樣化、復雜化，面對海量的網絡資源和學習資源，評分矩陣更加稀疏，使得誤差偏大，可信度較差［1～3］。因此，協同過濾算法仍需大力發展和不斷改進、完善，基于傳統的協同過濾算法，修正創新為有向加權協同過濾算法的網絡資源個性化推薦技術［4～5］。在目前的協同過濾算法中，一方面是先建立已知評分矩陣，通過已知矩陣去對填充或計算未知評分項，達到增大數據密度，降低矩陣稀疏性的目的，以提升推薦算法的可信度。其二是從另一個不同的角度出發，基于非填充的訓練集，使評分矩陣的原始數據不予改變，對結果的相似度給予修正，從而降低數據稀疏性，增加準確性［6～8］。研究方案專注于第二種方法來進行有向加權相似度協同過濾算法修正改進和研究。

2 基于重合因子相似度校正法

相關系數皮爾遜（Pearson Correlation）建立在相關性方法計算上，能夠用于分析幾個方向用戶評價趨勢一致性問題。以用戶（u）與評價（e）為例，分析Pearson Correlation系數計算公式，見式（1）。其中，Su，e為 u、e的交集，Rui、Rei為 u、e對評價 i的分值，Rˉu、Rˉe為平均值。由式（1）計算的用戶相似度評分，取決于它們評分的相似度。如果為稀疏集，不同用戶間有一致評分的概率不大。最終得到的數據更是隨意或偶然的，能得到感興趣的個性化推薦結果不可靠。這時，須對上述的相似度問題實行修正，以期應對評價的稀疏情況［9～11］。

一些研究者認為，個性化推薦重要的是重合因子（Overlap Factor），簡稱OF，其描述的是不同用戶評價數量二次方，再除以不同用戶所評價項目數。見式（2）。

式（2）中，| Su|、| Se|描述的是不同用戶評價項目數；|Su∩Se|描述的是不同用戶共同評價項目數。

利用上述Overlap Factor對相似度進行修正，即是對個性化推薦系統的全部用戶的相似度修正。通過上述修正后，可以得到加權相似度，稱為Weighted Similarity，見式（3）。

從式（3）得知，Overlap Factor與不同用戶共同評價項目數的二次方有正相關關系，與用戶各自評分項目數有反比相關性。由上述修正的相似度為基礎，使得Overlap Factor的適應性大大增強，可以應用于不同范圍、不同稀疏集和不同分類系統分配的個性化推薦系統［12～13］。

個性化推薦算法輸入主要是用戶-項目的評價矩陣R(u,e)：

式（4）中，行為用戶有u位，列為需評價項目e，構成u×e矩陣，第u行、e列R(u,e)取值是u在e上的評價等級。等級常用0～5的整數來計數，表達的是推薦程度。這樣的評價結果雖然直觀易懂，但有一些問題。見表1用戶-項目評價矩陣。

表1 用戶-項目R(u,e)評價矩陣表

通過上述式（3）的計算，可以計算得到用戶u1及 u2的 Overlap Factor。

接下來是計算u1及u3的Overlap Factor。

上述公式通過Overlap Factor對相似度進行修正，可以計算得到u1、u2間的Sim（u1，u2）重新計算后的值是1/3，u1、u3的Sim（u1，u3）計算后得到1/4。結合我們的現實生活來看，這有悖于常理，原因主要是u1、u2的Sim值是在2個共同評分項目計算的，u1、u3的Sim值是在3個共同評分項目計算的結果，可以看出Sim（u1，u3）比Sim（u1，u2）可信度更高，所以Sim（u1，u3）的修正強度應不大于Sim（u1，u2）的修正力度。為什么會有這一現象，通過分析發現，Overlap Factor與用戶各自評分項目數有反比例的關系，用戶u之間非重合的評分數據對相關因子的影響非常重要。因此，本文闡述了對相關因子進行再修正和改進，以期使用降低用戶u間的非重合評分數據的響應，獲得更為準確的Overlap Factor。

3 基于有向加權重合因子的相似度修正方法

3.1 有向重合因子

根據上述提出的基于重合因子的相似度修正方法描述，重合因子修正有一定的缺陷和不足，因此，本文分析研究出重合因子的改進方法。以減少用戶u間非重合推薦值于重合因子的影響，文中對重合因子進行了概念更新，定義為兩用戶u間共同推薦值的數目正相關，與目標用戶u推薦值的數量反向相關。假設用戶u、e的推薦值的集是Su、Se，這樣，u、e間以改進形式表現重合因子見式（7）（式中用戶u是目標用戶）：

可以推導出重合因子改進方式中，用戶u、e間的重合因子取值有2個，分別為 OF（u，e）、OF（e，u），重合因子的值并非對等。原因在于通過改進后，重合因子既與推薦值交集有相關性，也與目標用戶的選擇有相關性。選擇的目標用戶有異，結果也會不一致。所以，重合因子的改進方式定義為有向重合因子（Directional Overlap Factor，DOF），見式（8）。

有向重合因子和用戶u間一起推薦值的數目有正相關性，與目標用戶u推薦值的數目有反相關性，這里討論某一指定目標用戶u，它的推薦值數目不變，其余用戶u與目標用戶u間的有向重合因子的值，依賴于該用戶u與目標用戶u推薦值的交集結果，以此來減少非重合推薦值的影響，這樣，有向重合因子的改正方法更趨于完善。

所以，按式（8），對R(u,e)矩陣進行更新和計算，得出用戶u1與用戶u2間有向重合因子，見式（9）。（其中u1是目標用戶）

在相同的方式下，計算用戶u1、u3間有向重合因子，見式（10）。（其中 u1是目標用戶）

假設以有向重合因子為基礎，對相似度進行修正，得到用戶u1、u2間的相似度sim(u1,u2)，其值改變為原值的33.33%，用戶u1、u3間的相似度sim(u1,u3)改變為原值的50%。用戶u1、u2間相似度sim在兩個共同推薦值的基礎上計算得到，以此類推，用戶u1、u3間相似度sim為三個共同推薦值的基礎上計算得到，以此，可以得出結論，sim(u1,u3)的可信度大于sim(u1,u2)，也正是如此，對sim(u1,u3)的修正值要小于sim(u1,u2)。由以上描述可知，有向重合因子改進方式比重合因子修正方式對推薦值的計算更為客觀和接近實際。

3.2 有向加權相似度

由上述計算可知，有向重合因子計算方法與選擇的用戶u有相關性，選擇的用戶u有異，計算得到的結論也相異。以有向重合因子來對相似度sim實行改進后，相似度sim同時也成了有向值，也就是說，2用戶u間的相似度sim值也與目標用戶u的取值相關。利用有向重合因子改進后的相似度sim為有向加權相似度（Directional Weighted Similarity），以任一用戶u、v，用戶間的有向加權相似度見式（11）。（其中用戶u為目標用戶）

有向加權相似度Sim執行見圖1。

圖1 有向加權相似度執行示意圖

從有向加權相似度執行示意圖可知，Sim′(u,e)和Sim′(e,u)的值可能相異，也可能等于，但都能被正確計算，既不會有歧義，也沒有對后面的計算產生不利因素。當要求得當前u及其它用戶間的有向加權相似度的時候，由公式sim'(u,x):{x∈[1,m]且x≠u}可計算結果，u的近鄰集求解可使用sim'(u,x)來比較求得，無須再求sim'(u,x)、sim'(x,u)取值。

4 引入創新的有向加權相似度的協同過濾算法

這一節將討論稀疏數據集，稀疏數據集推薦數量往往缺乏必要數據，得到的相似度不是很準確，并往往有隨機性，不一定能精確反映用戶的實際興趣愛好［14～15］。為了使推薦結果更精確，利用上述得到的基于有向重合因子的相似度改進方法，對皮爾遜相關系數做一定的修正，生成有創新性質的有向加權相似度，進而構建創新的網絡資源個性化推薦技術，見圖2。

圖2 新型的有向加權相似度的協同過濾算法示意圖

基于創新的有向加權相似度的協同過濾改進算法執行步驟如下：

第一步，預處理數據

大數據中，數據集往往是巨大的，這樣需選取一部分用戶和用戶推薦值，形成數據集的子集，以該子集為樣本來進行選取和計算，達到簡化目的和使計算速度得到提升的目的。對選取的數據子集進行用戶和推薦值編碼，用戶標識（user identification，uid）定義為 1～m，項目標識（item identification，iid）定義為1～n。具體做法是將數據集以一定的概率分成訓練集和測試集，其中，訓練集代表已知數據存儲R(u,e)評價矩陣，用于試驗分析、對比和計算。測試集數據則作為未知數據來進行測試、預測，與實際值來對比研究，計算誤差值和評價推薦算法的利弊等。

第二步，統計用戶評價量及平均值

以R(u,e)評價矩陣為基礎計算，某用戶u對各項目評價值作為行向量，對R(u,e)的行進行分析、統計，得到每個用戶u評分項目數，并計算u的平均值。

第三步，計算用戶間相似度

基于皮爾遜相關系數，可以計算隨機2個用戶間u的相似度，存貯在二維數組Sim[][]的對應處。以用戶ui、uj間的相似度為例，將其存貯在Sim[i][j]、Sim[j][i]中，其值的計算依據是皮爾遜相關系數計算公式（3）～（5）。其實，在對皮爾遜相關系數修正前，用戶ui、uj間的相似度是沒有方向的，換言之，Sim[i][j]=Sim[j][i]，在無向數組中，這兩者可以是相等的。

第四步，有向加權相似度的計算

根據式（3）～（5），可以對任一用戶間有向重合因子進行計算，對上述的有向重合因子相似度改進，得到有向加權相似度，其結論存貯進二維數組Sim[j][i]。改進后變為有向相似度，就用戶ui、uj而言，因為有向性，Sim[i][j]與Sim[j][i]因為有向，故并不是對等的，因此，其存儲位置等不可變換。

第五步，最近鄰的選擇

按照數組Sim[][]存儲的用戶u間有向加權相似度，對目標用戶u的最近鄰居進行選擇。如果用戶 ui為目標用戶，即 Sim[i][j]（1≤j≤m ，m為總數，且 j≠i）可作為目標用戶u與其他用戶u的有向加權相似度。根據有向加權相似度值來取出k個與目標u附近的用戶實現編碼。

第六步，預測安排

若u對某項目尚未評分，可通過近鄰的已評分用戶來推算，推算方法見式（12）所示。

其中，Neighbors(u)描述的是最近鄰集，sim(u,u')描述的是u與近鄰u′的之間相似度。

第七步，誤差統計

按照每個測試數據得分，可以依據前述步驟1～7來預測，以實際值對照預期值來進行誤差計算，對個性化資源推薦評分結果進行優劣比較。

5 實驗設計與論證

5.1 實驗數據集說明

對上述的創新有向加權相似度協同過濾算法展開試驗與論證，設計4種相異稀疏度的數據集，包括MovieLens數據集、EachMovie數據集、Epinions數據集及Jester Joke數據集，進行試驗實證，并分析算法的可靠性。4個數據集的詳細介紹及預處理方式請參閱相關文獻。

5.2 算法比較

本次實驗使用了3種各異的協同過濾算法，與前文闡述的基于有向加權相似度的協同過濾修正方法（Directional Weighted Similarity Based Collaborative Filtering，DWSCF）進行比較，從而驗證上述的修正算法是否具備更好的優越性。用于比較的算法選擇：

1）傳統方法的協同過濾推薦算法（Collaborative Filtering，CF）；

2）基于Jaccard系數修正相似度的協同過濾算法（Jaccard Similarity Based Collaborative Filtering，JSCF）；

3）基于加權相似度的協同過濾算法（Weighted Similarity Based Collaborative Filtering，WSCF）。

其中，Jaccard系數計算方法見式（13）。

5.3 選擇評分指標

本試驗引入了平均絕對誤差來計算上面3種各異協同過濾算法的精度，計算方法如式（14）所示。

式中，M表達的是預測評價數，Vi是第i條預測評價值，Si是第i條預測評價值對應的實際值。mae描述的是精度，代表用戶真實評分與期望值的差值，是一個定量的指標。

5.4 實驗結果

通過一系列的實驗，各個數據集的實驗結果將以系列表格顯示。表格中，最近鄰數量在第一行進行標識，各種算法的種類標識在第一列，表中的數據為平均絕對誤差，它的值是各個算法在指定的最近鄰居中得到。為了使數據更見直觀簡明，圖3～6展示了各個數據集的數據。為了方便比較，將以上數值以折線圖形式進行直觀展示，最近鄰居的數量以橫坐標標識，平均絕對誤差值以縱坐標標識。

MovieLens數據集實驗結果如圖3所示。

其中，mae（mean absolute error）表示絕對平均誤差，nearest neighbors number表示近鄰取樣數，下同。

EachMovie數據集實驗結果如圖4所示。

圖4 EachMovie數據集圖

Epinions數據集實驗結果如圖5所示。

圖5 Epinions數據集圖

Jester Joke數據集實驗結果如圖6所示。

圖6 Jester Joke數據集圖

5.5 實驗結果分析

折線圖展示了四種數據集的實驗結果，描述的是協同過濾算法，由圖可以看出，各個數據集的折線圖趨勢均為從左上到右下，表明最近鄰居用戶量足夠大，其誤差才會足夠小，結果也才會越精確。與傳統協調過濾算法比較，該修正算法誤差值更小，實驗結果更加可信。在各個數據集的實驗結果中，JSCF、WSCF兩種算法圖相對吻合，其中，在Epinions數據集的實驗結果中，兩種算法圖出現交叉，表明在基于Jaccard系數及基于重合因子相似度改進法對比中，對傳統協同過濾算法的影響結果幾乎相同。而DWSCF算法的平均絕對誤差比JSCF、WSCF都要低，從這里可以得到結論，基于有向重合因子相似度改進法比重合因子修正法、Jaccard系數修正法均要好，結果更準確。

各種算法在數據集中的性能對比如圖7所示。

圖7 實驗結果對照圖

根據圖7，通過分析對比，MovieLens數據集中的算法比較，DWSCF＞JSCF≈WSCF＞CF；EachMovie數據集中的算法比較，DWSCF＞JSCF≈WSCF＞CF；Epinions數 據 集 中 算 法 比 較 ，DWSCF＞JSCF≈WSCF＞CF；Jester Joke數 據 集中的算 法 比 較，DWSCF≈JSCF≈WSCF≈CF。其中，Jester Joke數據集，DWSCF對比JSCF、WSCF這兩種算法，效果大概相當，這可能是因為Jester Joke數據集的數據規模和密度比其它數據集都高，而基于有向重合因子相似度改進法更側重于稀疏數據集，在越稀疏的數據集中，獲得更優越的性能，表現更好的效果。

在現實生活和實際中，用戶評價數據往往是非常稀疏的，用戶-項目評價矩陣表現很強的稀疏性，其稀疏度可能都在97%以上，所以，本文研究的基于有向重合因子相似度改進法在現實生活和實際中，可用性非常強，能充分發揮大數據下數據稀疏的適用性和實用性，從而獲得很好的個性化推薦質量，有較好的實際意義。

6 結語

網絡資源個性化推薦以各個用戶共同評價項目為依據，但在大數據和“互聯網+”時代，網絡資源及其豐富，數據集非常稀疏，再加上傳統推薦系統的不確定性，其精度往往得不到保證。作為改進方法，本文研究了創新的有向加權協調過濾推薦技術算法，利用有向重合因子加權后改進相似度算法，實驗證明該方法在極度稀疏的數據集里效果明顯。基于創新有向加權相似度協同過濾算法在解決互聯網+大數據的網絡資源個性化推薦稀疏度問題上，確實起到緩解及優化作用，極大地減少了網絡資源個性化推薦中不利的因素，提高了預測和計算的準確度，因此，網絡資源個性化推薦質量得到很大程度的提高。