融合巴氏系數的加權Slope One算法

劉金梅，舒遠仲，張尚田，唐小敏，劉文祥

(南昌航空大學 信息工程學院，江西 南昌 330063)

0 引 言

傳統的推薦算法主要有基于內容的算法、基于知識的算法、協同過濾算法和混合算法[1]。協同過濾算法應用最廣泛，主要包括基于用戶和基于物品的協同過濾[2]。slope one算法[3-4]是一種基于物品協同過濾算法，它簡潔、容易實現、執行效率高，主要依據項目評分差值預測，當面對龐大的數據集時，無法較好地處理稀疏數據。因此，許多學者對其進行了改進，如：劉毓等人[5]考慮到評分用戶數量對預測結果存在影響，提出一種加權slope one算法，該算法提高了預測精度；向小東等人[6]利用項目偏差對未評分的數據進行填充，再使用協同過濾算法；由于加權slope one算法未考慮用戶與用戶或項目與項目自身關系，王潘潘等人[7]將協同過濾算法與加權slope one算法相結合，通過用戶相似度尋找與目標用戶最相近的K個鄰居，根據鄰居對項目的評分進行預測；李桃迎等人[8]不僅考慮了用戶相似度還考慮到用戶興趣變化，用遺忘函數與鄰居相似度改進加權Slope one算法，進一步提高了精確度；文獻[9-10]考慮項目相似性對結果的影響，根據不確定K近鄰矩陣中的項目相似性，動態選擇每個項目的鄰域，然后計算鄰域中的項目評分偏差，最后再用線性模型進行預測；陶志勇等人[11]通過用戶與項目屬性改進相似度，引入用戶屬性-項目類型偏好權重因子，利用天牛須搜索算法調整興趣度預測；Zhao等人對上述三人的算法進行了融合，考慮用戶和項目相似度并將其都作為權重因子融合到加權slope one算法[12]。

上述改進算法中，相似度的度量都依賴共同評分。當數據稀疏時，皮爾遜相關系數計算性能較差；Jaccard系數僅考慮兩者是否有共同特性，不能衡量具體評分數值差異。Bobadilia等人[12]通過獲取奇異性信息，提出奇異性相似度測量，相比傳統的相似度測量，提高了預測質量，但在數據稀疏時，計算的相似度較差。

因此，該文對相似度計算方法進行改進，提出一種融合巴氏系數的相似度計算方法。首先用Jaccard相似度計算全局相似度，Pearson相關系數計算用戶局部相似度，其次用巴氏系數優化用戶局部相似度，然后再引入參數α將兩者融合獲取最終的用戶相似度，參數α的引入可以更好地衡量各個相似度在最終相似度中所占的比重。由于要對未知項目進行預測，所以再根據相似度排序選擇前K個用戶作為目標用戶的近鄰，再計算近鄰用戶對項目的評分偏差，最后結合目標用戶的評分用加權slope one算法進行評分預測，由于項目相似度對預測也存在影響，因此用巴氏系數計算項目相似度并將其作為權重對預測評分進行改進。

1 幾種slope one算法

1.1 slope one算法

slope one算法是一種線性模型，即f(x)=ax+b，可由項目x的值預測出f(x)，b為項目間評分差異值。如表1所示，預測U3對A的評分。

表1 用戶對項目的評分

slope one算法的工作流程如下：

(1)計算偏差。

項目之間的偏差計算如下：

(1)

其中，ui、uj表示用戶u對項目i、j的評分；Sji(X)表示評價項目i、j的用戶集合；NumV(Sji(X))表示用戶數量。

(2)預測。

根據步驟1計算出的評分偏差，再加上用戶u對項目的評分預測出目標項目j的評分，公式如下：

(2)

其中，Num(Rj)表示所有用戶評過分的項目集合。

1.2 Weighted slope one算法

slope one算法僅考慮評分，未考慮評分用戶數量對偏差計算的影響。對同一個項目評分用戶數量越多，計算的偏差越精確，因此為平衡每個用戶對評分的影響，進行加權處理，改進后的公式如下：

(3)

2 改進的加權slope one算法

2.1 相似度計算方法分析

傳統相似度計算方法[13-14]有余弦相似度、修正余弦相似度、皮爾遜相關系數、Jaccard相似度。

設m個用戶U={U1,U2,…,Um}和n個項目I={I1,I2,…,In}組成的用戶-項目評分矩陣，用戶Ui對項目Ij的評分用Rij表示，具體如表2所示。

表2 用戶-項目評分

(1)余弦相似度。

余弦相似度(cosine similarity)用向量夾角的余弦值表示個體間差異。

設兩個用戶u、v，Iuv為用戶所有評分的項目集，Rui、Rvi為用戶u、v對項目i的評分，則兩個用戶間的余弦相似度的計算公式如下：

(4)

(2)修正余弦相似度。

由于余弦相似度未考慮評分數值對結果的影響，所以產生了修正余弦相似度(adjusted cosine similarity)，本質是在計算時減去用戶評分的平均值。計算公式如下所示：

(5)

(3)皮爾遜相關系數。

皮爾遜相關系數(Pearson correlation coefficient，PC)用來衡量兩個變量間的相關程度，取值在[-1，+1]之間。計算公式如下：

Simpcc(u,v)=

(6)

(4)Jaccard相似度。

Jaccard相似度僅考慮個體間是否具有共同特征，沒有考慮評分數值大小，具體公式如下：

(7)

其中，Iu、Iv分別表示用戶u、v對項目評分的集合。

(5)巴氏系數。

巴氏系數(Bhattacharyya coefficient，BC)[15-17]在信號、圖像以及模式識別等領域使用較多，可以用來測量樣本間的相關性。設p1(x)和p2(x)為同一離散區間X上的兩個概率，則計算公式如下：

(8)

其中，p1(x)、p2(x)是評分矩陣中的已知評分數據，Pu、Pv分別表示用戶u和用戶v的評分，則用戶u和用戶v的巴氏系數相似度計算公式如下：

(9)

設用戶u對項目的評分為u=(2,3,0,1,1,4)T，用戶v對項目的評分為v=(1,0,3,2,1,5)T，評分范圍為0～5分，則用戶u和用戶v使用巴氏系數計算的相似度為：

0+0=0.8

(10)

通過對上述相似度計算方法的分析，發現皮爾遜相關系數在數據稀疏時計算性能較差；Jaccard相似性雖然計算了全局相似度，但是僅考慮項目間的共同特征，沒有考慮評分數值大小；而余弦和修正余弦相似度都依賴共同評分；巴氏系數不僅可以在數據稀疏時計算相似度，而且可以分析用戶關聯性。因此，下面將用巴氏系數來改進相似度。

2.2 相似度計算方法改進

由2.1節分析可知，當共同評分很少或者沒有時，傳統相似度計算性能較差，因此該文利用巴氏系數優化皮爾遜相關系數，并與Jaccard相似性進行融合得到最終用戶相似度。

首先，用皮爾遜相關系數計算用戶局部相似度，當數據較少時計算的性能較差，所以用巴氏系數分析用戶相關性，將作為影響因子加入到局部相似度中得出用戶新的局部相似度。公式如下：

Simloc(u,v)=Simpcc(u,v)BC(u,v)

(11)

其次，用Jaccard相似性計算全局相似度，將優化的局部相似度和全局相似度進行融合，設置參數α，參數α用來凸顯不同相似度在最終相似度中的權重。公式如下：

Sim(u,v)=αSimjac(u,v)+(1-α)Simloc(u,v)

(12)

上述兩式經處理獲得最終的用戶相似度，公式如下：

Simpcc(u,v)=αSimjac(u,v)+

(1-α)BC(u,v)2Simpcc(u,v)

(13)

2.3 預測評分的改進

根據2.2節計算出的用戶相似度，先降序排列后根據順序挑選前K個用戶放入鄰居集合S(K)中；再從鄰居集合中篩選出評價過目標項目的鄰居用戶，計算出目標項目與鄰居用戶評過分項目的評分偏差Devji；最后通過偏差與目標用戶的評分用加權slope one算法預測，公式如下：

(14)

由于式(14)中僅僅考慮了用戶評分對預測結果的影響，未考慮項目本身對其的影響，因此，在評分預測時又考慮項目相似度。對于項目相似度計算，該文使用巴氏系數。首先計算所有的項目相似度；然后找出鄰居集合S(K)中前K個鄰居所評分的項目集合；再計算目標項目j與鄰居項目i之間的相似度BC(i,j)；最后將所得的項目相似度作為權重因子，加入到式(14)中得出最終的預測評分。公式如下：

(15)

將項目相似度作為權重因子加入到預測公式中，一方面可以削弱項目相似度低對預測結果的影響，項目相似度高被忽略的現象；另一方面考慮用戶和項目相似度，可以使結果更準確。

2.4 算法流程

輸入：用戶-項目評分矩陣R，參數α、鄰居數K。

輸出：目標用戶u對項目i的預測評分。

算法步驟如下：

步驟1：創建用戶-項目評分矩陣R，并根據給定的數據集填充矩陣R。

步驟2：根據評分矩陣R，利用式(6)計算用戶局部相似度，式(7)計算用戶全局相似度。

步驟3：利用巴氏系數(式(9))分析用戶相關性，計算項目間相似度。

步驟4：用步驟3計算出的巴氏系數優化式(6)的局部相似度，并與式(7)的全局相似度相融合，設置參數α線性融合得到最終的用戶相似度。

步驟5：根據步驟4得到的最終用戶相似度，將相似度進行降序排列再選擇前K個作為用戶鄰居，放入鄰居集合S(K)中。

步驟6：由步驟5的鄰居集合S(K)，根據最近鄰居用戶對未知項目的評分來預測目標用戶對項目的評分，最后再將步驟3中的項目相似度加入到式(14)中，最后使用式(15)預測出最終目標用戶對項目的評分。

3 實驗結果與分析

3.1 數據集

采用MovieLens數據集進行測試(https://grouplens.org/datasets/movielens/)，其中用戶個數943，電影為1 682部，總共評分數為100 000條，評分范圍為1～5分，數據的稀疏程度為0.063。數據集劃分比例為8∶2，用五折交叉法來進行實驗。

3.2 評價指標

文中算法的預測質量由平均絕對誤差(mean absolute error，MAE)和均方根誤差(root mean square error，RMSE)來衡量，公式如下：

(16)

(17)

其中，Pi為預測評分，Ti為測試集中的實際評分，N為測試集中評分的總數。

3.3 結果分析與比較

3.3.1 確定參數α、K的值

在改進相似度時，用巴氏系數優化皮爾遜相關系數獲得用戶局部相似度，用Jaccard相似性計算用戶全局相似度，最后在相似度融合時，使用參數α來組合優化的用戶局部相似度和用戶全局相似度。參數α用來凸顯不同相似度在最終相似度中的權重，將參數α設置為[0.1,1]，步長為0.1，選擇的鄰居數K為[10,60]，步長為10。為排除實驗結果的偶然性，將6組不同鄰居下的值取平均，分析α以及K的變化對MAE和RMSE的影響，實驗結果如圖1和圖2所示。

圖1 不同參數α對MAE的影響

圖2 不同參數α對RMSE的影響

從圖1和圖2可以看出，MAE和RMSE的值隨參數α增大而變化，當參數α取值為0.5時，MAE和RMSE均達到最小值，說明此時的效果最佳。因此，在用戶相似度改進算法中，在局部相似度和全局相似度融合時，將參數α設置為0.5。

在改進的算法中，鄰居數量不同也會影響預測結果，因此，該文選取不同的鄰居數量進行測試(K=10,40,80,120,160,200,240,280,320)，每一個K進行5次實驗，再對其取平均值作為最終結果。繪制鄰居數量K與MAE和RMSE的關系圖，如圖3和圖4所示。

圖3 鄰居數量K與MAE的關系

圖4 鄰居數量K與RMSE的關系

從圖3和圖4可以看出，隨著鄰居數量K的增多，MAE和RMSE均先減小后慢慢趨于穩定。因為在鄰居數量較少時可用來分析的數據較少，此時產生的誤差就偏大；隨著鄰居數量的不斷增多，可利用的數據越來越多，誤差逐漸減小直至最后達到某一數值趨于穩定。從圖中可以看出，當鄰居數K=200時，誤差最小，此時預測評分愈加接近真實值。因此，實驗選取鄰居數量為200進行研究，不僅可以保證良好的預測結果，同時又能夠降低計算復雜度。

3.3.2 改進預測公式的算法對比

預測公式的不同，實驗結果也會存在差異。該文利用巴氏系數計算項目相似度，將其加入到原始加權slope one預測公式中，將改進后的預測公式與未加入權重因子的未改進預測公式作對比，結果如圖5和圖6所示。

從圖5和圖6可以明顯看出，改進預測公式的MAE和RMSE值均比未改進預測公式的值小，說明用巴氏系數改進預測公式在某種程度上可以提高預測精度。

圖5 不同預測公式的MAE值

圖6 不同預測公式的RMSE值

3.3.3 改進算法與其他算法的對比

利用巴氏系數可以在稀疏數據情況下仍然能夠計算相似度，提出用巴氏系數優化皮爾遜相關系數，并與Jaccard相關系數相融合得到一種新的相似度計算方法。通過3.3.1節可知，在相似度融合時，參數α取0.5時可以獲得最優用戶相似度；在鄰居數量K為200情況下，預測結果愈加接近真實值，誤差較小，因此，將參數α設置為0.5，鄰居數量K設置為200進行實驗。將改進的算法(BCWSOA)與文獻[18]中基于加權slope one和用戶協同過濾的推薦算法(CF_WSOA)、Weighted slope one算法、slope one算法和基于用戶的協同過濾算法(UCF)進行比較，衡量指標為MAE和RMSE，實驗結果如圖7和圖8所示。

圖7 不同算法的MAE值

圖8 不同算法的RMSE值

從圖7和圖8可以看出，當參數α為0.5，鄰居數K為200時，改進算法BCWSOA的MAE和RMSE值相比于其他幾種算法均有所減小，預測準確性有所提高。

4 結束語

該文融合巴氏系數改進相似度的計算方法，解決了用戶共同評分很少或者沒有的問題。考慮了項目相似度對預測的影響，用巴氏系數計算相似度改進加權slope one算法。與基于加權slope one和用戶協同過濾的推薦算法(CF_WSOA)、Weighted slope one算法、slope one算法和基于用戶的協同過濾算法(UCF)進行比較，融合巴氏系數的加權slope one算法在預測精確度上均有所提高。