融合巴氏系數(shù)的加權(quán)Slope One算法

劉金梅，舒遠(yuǎn)仲，張尚田，唐小敏，劉文祥

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

0 引 言

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

上述改進(jìn)算法中，相似度的度量都依賴共同評(píng)分。當(dāng)數(shù)據(jù)稀疏時(shí)，皮爾遜相關(guān)系數(shù)計(jì)算性能較差；Jaccard系數(shù)僅考慮兩者是否有共同特性，不能衡量具體評(píng)分?jǐn)?shù)值差異。Bobadilia等人[12]通過獲取奇異性信息，提出奇異性相似度測(cè)量，相比傳統(tǒng)的相似度測(cè)量，提高了預(yù)測(cè)質(zhì)量，但在數(shù)據(jù)稀疏時(shí)，計(jì)算的相似度較差。

因此，該文對(duì)相似度計(jì)算方法進(jìn)行改進(jìn)，提出一種融合巴氏系數(shù)的相似度計(jì)算方法。首先用Jaccard相似度計(jì)算全局相似度，Pearson相關(guān)系數(shù)計(jì)算用戶局部相似度，其次用巴氏系數(shù)優(yōu)化用戶局部相似度，然后再引入?yún)?shù)α將兩者融合獲取最終的用戶相似度，參數(shù)α的引入可以更好地衡量各個(gè)相似度在最終相似度中所占的比重。由于要對(duì)未知項(xiàng)目進(jìn)行預(yù)測(cè)，所以再根據(jù)相似度排序選擇前K個(gè)用戶作為目標(biāo)用戶的近鄰，再計(jì)算近鄰用戶對(duì)項(xiàng)目的評(píng)分偏差，最后結(jié)合目標(biāo)用戶的評(píng)分用加權(quán)slope one算法進(jìn)行評(píng)分預(yù)測(cè)，由于項(xiàng)目相似度對(duì)預(yù)測(cè)也存在影響，因此用巴氏系數(shù)計(jì)算項(xiàng)目相似度并將其作為權(quán)重對(duì)預(yù)測(cè)評(píng)分進(jìn)行改進(jìn)。

1 幾種slope one算法

1.1 slope one算法

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

表1 用戶對(duì)項(xiàng)目的評(píng)分

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

(1)計(jì)算偏差。

項(xiàng)目之間的偏差計(jì)算如下：

(1)

其中，ui、uj表示用戶u對(duì)項(xiàng)目i、j的評(píng)分；Sji(X)表示評(píng)價(jià)項(xiàng)目i、j的用戶集合；NumV(Sji(X))表示用戶數(shù)量。

(2)預(yù)測(cè)。

根據(jù)步驟1計(jì)算出的評(píng)分偏差，再加上用戶u對(duì)項(xiàng)目的評(píng)分預(yù)測(cè)出目標(biāo)項(xiàng)目j的評(píng)分，公式如下：

(2)

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

1.2 Weighted slope one算法

slope one算法僅考慮評(píng)分，未考慮評(píng)分用戶數(shù)量對(duì)偏差計(jì)算的影響。對(duì)同一個(gè)項(xiàng)目評(píng)分用戶數(shù)量越多，計(jì)算的偏差越精確，因此為平衡每個(gè)用戶對(duì)評(píng)分的影響，進(jìn)行加權(quán)處理，改進(jìn)后的公式如下：

(3)

2 改進(jìn)的加權(quán)slope one算法

2.1 相似度計(jì)算方法分析

傳統(tǒng)相似度計(jì)算方法[13-14]有余弦相似度、修正余弦相似度、皮爾遜相關(guān)系數(shù)、Jaccard相似度。

設(shè)m個(gè)用戶U={U1,U2,…,Um}和n個(gè)項(xiàng)目I={I1,I2,…,In}組成的用戶-項(xiàng)目評(píng)分矩陣，用戶Ui對(duì)項(xiàng)目Ij的評(píng)分用Rij表示，具體如表2所示。

表2 用戶-項(xiàng)目評(píng)分

(1)余弦相似度。

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

設(shè)兩個(gè)用戶u、v，Iuv為用戶所有評(píng)分的項(xiàng)目集，Rui、Rvi為用戶u、v對(duì)項(xiàng)目i的評(píng)分，則兩個(gè)用戶間的余弦相似度的計(jì)算公式如下：

(4)

(2)修正余弦相似度。

由于余弦相似度未考慮評(píng)分?jǐn)?shù)值對(duì)結(jié)果的影響，所以產(chǎn)生了修正余弦相似度(adjusted cosine similarity)，本質(zhì)是在計(jì)算時(shí)減去用戶評(píng)分的平均值。計(jì)算公式如下所示：

(5)

(3)皮爾遜相關(guān)系數(shù)。

皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient，PC)用來衡量?jī)蓚€(gè)變量間的相關(guān)程度，取值在[-1，+1]之間。計(jì)算公式如下：

Simpcc(u,v)=

(6)

(4)Jaccard相似度。

Jaccard相似度僅考慮個(gè)體間是否具有共同特征，沒有考慮評(píng)分?jǐn)?shù)值大小，具體公式如下：

(7)

其中，Iu、Iv分別表示用戶u、v對(duì)項(xiàng)目評(píng)分的集合。

(5)巴氏系數(shù)。

巴氏系數(shù)(Bhattacharyya coefficient，BC)[15-17]在信號(hào)、圖像以及模式識(shí)別等領(lǐng)域使用較多，可以用來測(cè)量樣本間的相關(guān)性。設(shè)p1(x)和p2(x)為同一離散區(qū)間X上的兩個(gè)概率，則計(jì)算公式如下：

(8)

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

(9)

設(shè)用戶u對(duì)項(xiàng)目的評(píng)分為u=(2,3,0,1,1,4)T，用戶v對(duì)項(xiàng)目的評(píng)分為v=(1,0,3,2,1,5)T，評(píng)分范圍為0～5分，則用戶u和用戶v使用巴氏系數(shù)計(jì)算的相似度為：

0+0=0.8

(10)

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

2.2 相似度計(jì)算方法改進(jìn)

由2.1節(jié)分析可知，當(dāng)共同評(píng)分很少或者沒有時(shí)，傳統(tǒng)相似度計(jì)算性能較差，因此該文利用巴氏系數(shù)優(yōu)化皮爾遜相關(guān)系數(shù)，并與Jaccard相似性進(jìn)行融合得到最終用戶相似度。

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

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

(11)

其次，用Jaccard相似性計(jì)算全局相似度，將優(yōu)化的局部相似度和全局相似度進(jìn)行融合，設(shè)置參數(shù)α，參數(shù)α用來凸顯不同相似度在最終相似度中的權(quán)重。公式如下：

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

(12)

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

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

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

(13)

2.3 預(yù)測(cè)評(píng)分的改進(jìn)

根據(jù)2.2節(jié)計(jì)算出的用戶相似度，先降序排列后根據(jù)順序挑選前K個(gè)用戶放入鄰居集合S(K)中；再從鄰居集合中篩選出評(píng)價(jià)過目標(biāo)項(xiàng)目的鄰居用戶，計(jì)算出目標(biāo)項(xiàng)目與鄰居用戶評(píng)過分項(xiàng)目的評(píng)分偏差Devji；最后通過偏差與目標(biāo)用戶的評(píng)分用加權(quán)slope one算法預(yù)測(cè)，公式如下：

(14)

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

(15)

將項(xiàng)目相似度作為權(quán)重因子加入到預(yù)測(cè)公式中，一方面可以削弱項(xiàng)目相似度低對(duì)預(yù)測(cè)結(jié)果的影響，項(xiàng)目相似度高被忽略的現(xiàn)象；另一方面考慮用戶和項(xiàng)目相似度，可以使結(jié)果更準(zhǔn)確。

2.4 算法流程

輸入：用戶-項(xiàng)目評(píng)分矩陣R，參數(shù)α、鄰居數(shù)K。

輸出：目標(biāo)用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分。

算法步驟如下：

步驟1：創(chuàng)建用戶-項(xiàng)目評(píng)分矩陣R，并根據(jù)給定的數(shù)據(jù)集填充矩陣R。

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

步驟3：利用巴氏系數(shù)(式(9))分析用戶相關(guān)性，計(jì)算項(xiàng)目間相似度。

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

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

步驟6：由步驟5的鄰居集合S(K)，根據(jù)最近鄰居用戶對(duì)未知項(xiàng)目的評(píng)分來預(yù)測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分，最后再將步驟3中的項(xiàng)目相似度加入到式(14)中，最后使用式(15)預(yù)測(cè)出最終目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集

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

3.2 評(píng)價(jià)指標(biāo)

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

(16)

(17)

其中，Pi為預(yù)測(cè)評(píng)分，Ti為測(cè)試集中的實(shí)際評(píng)分，N為測(cè)試集中評(píng)分的總數(shù)。

3.3 結(jié)果分析與比較

3.3.1 確定參數(shù)α、K的值

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

圖1 不同參數(shù)α對(duì)MAE的影響

圖2 不同參數(shù)α對(duì)RMSE的影響

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

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

圖3 鄰居數(shù)量K與MAE的關(guān)系

圖4 鄰居數(shù)量K與RMSE的關(guān)系

從圖3和圖4可以看出，隨著鄰居數(shù)量K的增多，MAE和RMSE均先減小后慢慢趨于穩(wěn)定。因?yàn)樵卩従訑?shù)量較少時(shí)可用來分析的數(shù)據(jù)較少，此時(shí)產(chǎn)生的誤差就偏大；隨著鄰居數(shù)量的不斷增多，可利用的數(shù)據(jù)越來越多，誤差逐漸減小直至最后達(dá)到某一數(shù)值趨于穩(wěn)定。從圖中可以看出，當(dāng)鄰居數(shù)K=200時(shí)，誤差最小，此時(shí)預(yù)測(cè)評(píng)分愈加接近真實(shí)值。因此，實(shí)驗(yàn)選取鄰居數(shù)量為200進(jìn)行研究，不僅可以保證良好的預(yù)測(cè)結(jié)果，同時(shí)又能夠降低計(jì)算復(fù)雜度。

3.3.2 改進(jìn)預(yù)測(cè)公式的算法對(duì)比

預(yù)測(cè)公式的不同，實(shí)驗(yàn)結(jié)果也會(huì)存在差異。該文利用巴氏系數(shù)計(jì)算項(xiàng)目相似度，將其加入到原始加權(quán)slope one預(yù)測(cè)公式中，將改進(jìn)后的預(yù)測(cè)公式與未加入權(quán)重因子的未改進(jìn)預(yù)測(cè)公式作對(duì)比，結(jié)果如圖5和圖6所示。

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

圖5 不同預(yù)測(cè)公式的MAE值

圖6 不同預(yù)測(cè)公式的RMSE值

3.3.3 改進(jìn)算法與其他算法的對(duì)比

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

圖7 不同算法的MAE值

圖8 不同算法的RMSE值

從圖7和圖8可以看出，當(dāng)參數(shù)α為0.5，鄰居數(shù)K為200時(shí)，改進(jìn)算法BCWSOA的MAE和RMSE值相比于其他幾種算法均有所減小，預(yù)測(cè)準(zhǔn)確性有所提高。

4 結(jié)束語

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