一種新型有向加權(quán)協(xié)同過濾算法的推薦技術(shù)研究?

彭康華 姚江梅 黃裕鋒

（廣東工程職業(yè)技術(shù)學(xué)院信息工程學(xué)院 廣州 510520）

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于有向加權(quán)重合因子的相似度修正方法

3.1 有向重合因子

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

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

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

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

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

假設(shè)以有向重合因子為基礎(chǔ)，對相似度進(jìn)行修正，得到用戶u1、u2間的相似度sim(u1,u2)，其值改變?yōu)樵档?3.33%，用戶u1、u3間的相似度sim(u1,u3)改變?yōu)樵档?0%。用戶u1、u2間相似度sim在兩個共同推薦值的基礎(chǔ)上計算得到，以此類推，用戶u1、u3間相似度sim為三個共同推薦值的基礎(chǔ)上計算得到，以此，可以得出結(jié)論，sim(u1,u3)的可信度大于sim(u1,u2)，也正是如此，對sim(u1,u3)的修正值要小于sim(u1,u2)。由以上描述可知，有向重合因子改進(jìn)方式比重合因子修正方式對推薦值的計算更為客觀和接近實際。

3.2 有向加權(quán)相似度

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

有向加權(quán)相似度Sim執(zhí)行見圖1。

圖1 有向加權(quán)相似度執(zhí)行示意圖

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

4 引入創(chuàng)新的有向加權(quán)相似度的協(xié)同過濾算法

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

圖2 新型的有向加權(quán)相似度的協(xié)同過濾算法示意圖

基于創(chuàng)新的有向加權(quán)相似度的協(xié)同過濾改進(jìn)算法執(zhí)行步驟如下：

第一步，預(yù)處理數(shù)據(jù)

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

第二步，統(tǒng)計用戶評價量及平均值

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

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

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

第四步，有向加權(quán)相似度的計算

根據(jù)式（3）～（5），可以對任一用戶間有向重合因子進(jìn)行計算，對上述的有向重合因子相似度改進(jìn)，得到有向加權(quán)相似度，其結(jié)論存貯進(jìn)二維數(shù)組Sim[j][i]。改進(jìn)后變?yōu)橛邢蛳嗨贫?，就用戶ui、uj而言，因為有向性，Sim[i][j]與Sim[j][i]因為有向，故并不是對等的，因此，其存儲位置等不可變換。

第五步，最近鄰的選擇

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

第六步，預(yù)測安排

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

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

第七步，誤差統(tǒng)計

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

5 實驗設(shè)計與論證

5.1 實驗數(shù)據(jù)集說明

對上述的創(chuàng)新有向加權(quán)相似度協(xié)同過濾算法展開試驗與論證，設(shè)計4種相異稀疏度的數(shù)據(jù)集，包括MovieLens數(shù)據(jù)集、EachMovie數(shù)據(jù)集、Epinions數(shù)據(jù)集及Jester Joke數(shù)據(jù)集，進(jìn)行試驗實證，并分析算法的可靠性。4個數(shù)據(jù)集的詳細(xì)介紹及預(yù)處理方式請參閱相關(guān)文獻(xiàn)。

5.2 算法比較

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

1）傳統(tǒng)方法的協(xié)同過濾推薦算法（Collaborative Filtering，CF）；

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

3）基于加權(quán)相似度的協(xié)同過濾算法（Weighted Similarity Based Collaborative Filtering，WSCF）。

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

5.3 選擇評分指標(biāo)

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

式中，M表達(dá)的是預(yù)測評價數(shù)，Vi是第i條預(yù)測評價值，Si是第i條預(yù)測評價值對應(yīng)的實際值。mae描述的是精度，代表用戶真實評分與期望值的差值，是一個定量的指標(biāo)。

5.4 實驗結(jié)果

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

MovieLens數(shù)據(jù)集實驗結(jié)果如圖3所示。

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

EachMovie數(shù)據(jù)集實驗結(jié)果如圖4所示。

圖4 EachMovie數(shù)據(jù)集圖

Epinions數(shù)據(jù)集實驗結(jié)果如圖5所示。

圖5 Epinions數(shù)據(jù)集圖

Jester Joke數(shù)據(jù)集實驗結(jié)果如圖6所示。

圖6 Jester Joke數(shù)據(jù)集圖

5.5 實驗結(jié)果分析

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

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

圖7 實驗結(jié)果對照圖

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

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

6 結(jié)語

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