王萬良，屠海龍，朱炎亮，趙燕偉，鮑 毅

1(浙江工業(yè)大學 計算機科學與技術學院，杭州 310023) 2(杭州赫智電子科技有限公司，杭州 310026)

1 引 言

隨著互聯(lián)網的普及和電子商務的快速發(fā)展，用戶和產品數(shù)量呈指數(shù)式增長，信息過載問題愈發(fā)嚴重.在大數(shù)據的背景下，信息的冗余使得搜索技術已經無法完全滿足用戶的個性化需求，推薦算法應運而生，如今推薦算法被廣泛運用于電子商務、在線廣告、社交媒體等各個領域[1].協(xié)同過濾算法是目前應用最廣泛的個性化推薦算法之一[2].協(xié)同過濾的基本思想為：通過用戶對于項目的歷史評分矩陣，在兩個維度上計算鄰近關系進行預測計算，如在用戶維度找到與目標用戶歷史評分行為最相似的鄰居用戶，根據鄰居用戶的歷史評分高低產生推薦項目.

隨著推薦場景中用戶和項目的數(shù)目不斷增大，推薦算法的輸入評分矩陣增大，但是由于用戶能夠接觸到的項目有限以及大多用戶沒有對項目進行評分的習慣等原因，用戶對于項目的評分數(shù)量很少，導致了推薦系統(tǒng)中的評分數(shù)據稀疏性問題[3].針對稀疏性問題通常可使用降維和填充的方法解決.Pirasteh等通過運用用戶和項目的內容信息對評分數(shù)據進行填充[4].鄧愛林等利用項目聚類后進行協(xié)同過濾推薦，降低了矩陣維度[5].Wang 等首先對用戶已經評分的數(shù)據進行聚類，然后結合Slope One算法來對未評分數(shù)據進行預測填充[6].另外，許多學者提出基于降維技術的稀疏性問題解決方法，如PCA[7]、SVD[8]、非負矩陣分解[9，10].

以上算法在一定程度上緩解了數(shù)據稀疏性的問題，但是算法的計算復雜度較高，在數(shù)據龐大和更新速度較快的情況下，不能很好地解決實時推薦的問題.在實時性問題的解決方面，Lemire等人提出了Slope One算法[11]，該算法易于實現(xiàn)和維護，準確度較高，在實時推薦上具有較大優(yōu)勢.但是，Slope One算法沒有考慮項目之間和用戶之間的差異.賀懷清等人利用資源分配的思想度量用戶之間的相似度[12]，但該模型沒有考慮項目之間的差異對預測結果的影響，并且用戶相似度計算方法存在不對稱情況.張玉連等人則利用機器學習的方法衡量項目之間的相似度[13]，該方法將基于模型的方法結合Slope One，利用梯度下降計算項目之間相似度，動態(tài)調節(jié)評分.但該方法求解過程需要多次迭代計算，計算復雜度較高.基于以上分析，本文希望在保持Slope One算法較低計算復雜度的情況下，提高其準確度，提出一種融合巴氏系數(shù)的用戶聚類Slope One推薦算法(BCUC Slope One Algorithm).巴氏系數(shù)在稀疏數(shù)據下既能保證良好計算效果，并且計算簡單，故引入其作為項目相似度計算方法，能夠在數(shù)據稀疏條件下將項目差異考慮到模型中，算法還在用戶聚類時充分分析了用戶評分習慣對準確度的影響.算法基本思想如下：

1)Slope One算法對用戶評分數(shù)據采用了一致性的分析，影響推薦準確度，提出一種改進的Slope One算法；

2)在用戶維度，通過分析用戶評分習慣，對用戶評分數(shù)據進行預處理，消除評分奇異性對推薦預測的影響，再對用戶進行聚類降低用戶維度上的差異；

3)在項目維度，Slope One算法對系統(tǒng)中的所有項目采用一致性的權重對待，通過加入一種在數(shù)據稀疏條件下的相似度計算方法—巴氏系數(shù)，考慮項目之間的差異，提高推薦準確度.

2 相關工作

2.1 問題描述

推薦算法輸入數(shù)據為用戶(觀眾)對項目(電影)的確切的反饋評分數(shù)據，與觀看記錄、查詢記錄等隱式數(shù)據不同的是，評分數(shù)據直接表達了用戶對項目的喜愛程度.定義用一個矩陣R(m×n)表示用戶的反饋評分，m為用戶的個數(shù)，n表示項目的個數(shù).Ru，i表示用戶u對項目i的評分.Ru，i∈[1，2，3，4，5]，數(shù)值越大表示用戶對項目的評分越高，對項目的喜愛程度越大.用戶評分矩陣如表1所示.

表1 評分矩陣Table 1 Rating matrix

圖1 Slope One基本模型Fig.1 Slope One model

該矩陣通常為一個稀疏矩陣，矩陣中用戶對項目沒有作出評分的位置用0表示.推薦算法的本質就是補全該評分矩陣，預測目標用戶對其未評分的項目的可能評分，將預測值最高的項目推薦給目標用戶.

2.2 Slope One算法

Slope One推薦算法是一種基于項目的協(xié)同過濾算法，本質上是一個一元的線性預測模型[11]，f(x)表示目標用戶對項目的預測評分，x表示目標用戶對項目的評分，b為評分偏差.基本模型如圖1.用戶A對項目I和項目J 的評分分別為1 和1.5，用戶B對項目I的評分為2，用戶B對J 的評分可以用對項目I的評分加上用戶A對項目I，J的差值表示.用戶B稱為目標用戶，項目J稱為目標項目.在已知的評分數(shù)據中有很多像(i，j)這樣的項目對，將最后計算得到的平均值作為預測值.

2.3 Slope One算法具體實現(xiàn)

2.3.1 Slope One算法

Slope One算法可以分為計算評分偏差和預測兩個過程：

用戶對項目j，k的評分偏差：

(1)

Sj，k(U)表示對項目j，k都進行了評分的用戶U的集合.

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

(2)

N(·)表示集合的數(shù)目，Ritem表示目標用戶的已經評分的項目集合.

2.3.2 Weighted Slope One算法

考慮到不同的項目對(i，j)被共同評分的次數(shù)不同，不能采用相同的權值進行簡單的計算.在傳統(tǒng)Slope One算法基礎上加上共同評分次數(shù)作為計算權重.改進的Weighted Slope One算法的預測部分如下：

(3)

3 融合巴氏系數(shù)的用戶聚類Slope One算法

根據以上問題描述和Slope One算法的介紹分析，Slope One算法因其實現(xiàn)簡單，在在線推薦和動態(tài)分析方面具有較大優(yōu)勢，但在計算過程中對所有的項目采取了一致性的對待，沒有體現(xiàn)出項目之間差異性對推薦的影響，相對于其他基于項目的協(xié)同過濾算法推薦準確度有所降低.本文提出一種融合巴氏系數(shù)的用戶聚類Slope One算法(BCUC Slope One Algorithm)，在保證其在線推薦能力的前提下提高預測準確度.

3.1 相似度計算

在推薦算法中，尤其是在協(xié)同過濾算法中，相似性的計算是最重要的步驟之一，針對不同的推薦場景和推薦算法，不同的相似性度量方法也表現(xiàn)出不同的效果.Pearson相關系數(shù)和余弦相似性是應用最廣泛的相似性度量方法.

3.1.1 Pearson 相關系數(shù)

Pearson相關系數(shù)的計算方式如下：

(4)

Pearson相關系數(shù)計算的是對象之間的線性相關性，在基于用戶的協(xié)同過濾中運用廣泛.如公式所示，每一個用戶對所有項目的評分向量作為用戶特征，計算結果在區(qū)間[-1，+1].Pearson相關系數(shù)計算的是兩個用戶對項目評分的趨勢差異，對用戶評分大小并不敏感，如u1=[1，2，3，4]，u2=[3，4，6，7]，u3=[4，5，6，7]，直覺上u3和u2更為相似，但是Pearson的計算結果為u1和u3更加相似.另外，Pearson相關系數(shù)計算的是共同評分項目下的趨勢差異，由于評分矩陣的稀疏性，共同評分項目太少甚至沒有而影響相似度的計算.而且只對部分評分內容進行了計算，只考慮到了評分數(shù)據中的局部信息.

3.1.2 余弦距離

余弦距離，顧名思義，計算的兩個向量夾角的余弦值.以項目之間的相似性為例，項目特征為各個用戶對它的評分向量，計算方法如公式(5).

(5)

Ui，j表示對項目i，j評分的用戶集合.

由于余弦計算的是向量之間的夾角，僅僅考慮了項目向量維度上的相似性，而忽視了用戶之間評分值的大小問題.所以提出了修正的余弦距離，計算方法如公式(6).

(6)

與Pearson相關系數(shù)存在同樣的問題是，余弦距離考慮的也是共同評分項目的評分值，由于矩陣的稀疏性而丟失了很多信息.

3.1.3 巴氏系數(shù)(Bhattacharyya coefficient)

巴氏系數(shù)被廣泛應用于信號處理，圖像處理，模式識別等領域[14-16]，計算的是兩個概率分布之間的相似性.令p1(x)和p2(x)分別為同一定義域上的兩個概率分布，巴氏系數(shù)計算兩個概率分布之間的相似性如公式(7)(8).

概率分布連續(xù)情況下：

(7)

概率分布離散情況下：

(8)

基于以上分析，Slope One算法中并沒有考慮到項目之間的相似性差異，沒有將項目的相似度加入權重的計算.而由于矩陣的稀疏度和計算的復雜度等方面的考慮，常規(guī)的一些相似性度量方法并不適合Slope One算法中，所以提出引入巴氏系數(shù)作為Slope One的權重計算.

3.2 融合巴氏系數(shù)的Slope One算法

使用巴氏系數(shù)計算項目之間相似度，巴氏系數(shù)計算簡單，計算復雜度較低，不影響Slope One算法 的在線推薦和動態(tài)更新能力.利用巴氏系數(shù)的離散計算方式，將評分的范圍作為離散變量的取值范圍，用戶對項目的評分值的個數(shù)作為每個變量的概率，巴氏系數(shù)中的概率分布表示為pi=[pi，1，pi，2，pi，3，pi，4，pi，5]，其中pi，1表示用戶i已經作出的評分中分值為1的概率.

(9)

pi，r表示對項目i評分值為r的概率分布，D∈[1，2，3，4，5]

(10)

預測公式：

(11)

巴氏系數(shù)計算相似度過程中考慮了所有的評分數(shù)據而非共同評分數(shù)據，降低了在稀疏性條件下造成的相似性計算偏差[17].例如兩個項目向量Ri=[1，0，1，0，1，0]和Rj=[0，1，0，1，0，1]，分別表示各個對項目i，j的評分值，評分分值大小取值為[1，2，3].在直覺上判斷i，j兩個項目的相似度顯然是非常高的，因為所有對項目i 和j評過分的用戶對兩者的評分值均為1.但是由于兩個項目被同一用戶評分的次數(shù)為0，所以利用Pearson相關系數(shù)和余弦距離計算的相似度為0，而利用巴氏系數(shù)計算兩者的相似度為1.顯然在共同評分次數(shù)較少的情況下，巴氏系數(shù)計算相似度更為準確.在計算復雜度方面，巴氏系數(shù)的項目評分向量維度大大減小，由原來的m維(用戶數(shù)量)變成5維，從而在計算效率上相較于其他相似性度量方法高很多，對Slope One的在線推薦和動態(tài)更新方面的能力影響較小.

3.3 考慮評分習慣的用戶聚類

經過前面改進的Slope One算法，融合了項目相似度，改變了傳統(tǒng)Slope One中的一致性權重.但是巴氏系數(shù)在計算項目相似度時只計算了用戶對項目評分值的次數(shù)，而沒有考慮用戶偏好之間的差異.提出使用聚類方法針對用戶的歷史評分數(shù)據將偏好相似的用戶劃分為同一類，增加使用巴氏系數(shù)計算項目相似性的準確度.

而用戶評分習慣的不同會對聚類產生一定影響.用戶評分習慣可以理解為用戶對項目喜愛程度的表達，例如，有些用戶對于喜愛的項目會打5分，對于好感度不是那么強的會打3分，我們可以稱之為“樂觀用戶”，而“悲觀用戶”則對項目表現(xiàn)得更加苛刻，在打分過程中很少打出5分，而3分可能就能表示該用戶對于項目的喜愛了.在喜愛程度的表達上，“積極用戶”和“消極用戶”存在很大差異，會影響到用戶聚類的效果.

經過上述分析，為了消除用戶評分習慣影響，提高聚類效果，需要對用戶評分矩陣進行預處理.預處理方法如公式(12)，用戶的平均評分值可以表示用戶的評分習慣，將用戶評分大于自己平均評分值的記作“高評分”，并置為1；小于等于自己平均評分值的為“低評分”，置為-1；用戶未評分項分值仍為0.

(12)

表2 預處理前Table 2 Before the preprocessing

表3 預處理后Table 3 After the preprocessing

預處理具體例子如表2、表3所示：

從表2、表3可以看出，A用戶和B用戶評分值非0項較少，說明A、B用戶評分次數(shù)多，屬于系統(tǒng)的“活躍用戶”.處理前表中A的平均評分比B高，表示A是一個“樂觀用戶”，而B為“悲觀用戶”，經過預處理之后，兩人的評分情況如表2，兩者評分的高低只與自己的評分習慣相關，與評分的取值范圍無關.用戶C的評分習慣與用戶A相似，但是用戶C 的評分次數(shù)不多，屬于系統(tǒng)中的“非活躍用戶”.經過預處理后的矩陣保留了原來矩陣的特征，弱化了絕對分值的影響，消除了用戶評分習慣差異，可以增加聚類效果.

3.4 改進后算法步驟

輸入：用戶評分矩陣 R

輸出：目標用戶預測評分最高的K個項目

1.對用戶評分矩陣根據式(12)進行預處理,根據用戶的評分習慣,使用k-means聚類方法將用戶聚成s類,C={C1,C2…,Cn,…,Cs}

2.在每個用戶聚類Cn中：

1)利用巴氏系數(shù)公式計算每個項目之間的相似度.

2)對聚類中用戶使用改進的Slope One算法， 根據巴氏Slope One算法預測公式(11)計算預測評分.

3.目標用戶預測評分中根據分值大小將前K個項目推薦給用戶.

步驟1中使用k-means算法對預處理之后的評分矩陣進行聚類，k-means算法是一種傳統(tǒng)的聚類算法， 具有低計算復雜度和計算效果較好的優(yōu)點[2].在步驟2中，對每個聚類使用融入了巴氏系數(shù)的Slope One算法.最后在步驟 3 中根據預測評分的大小將前K個項目作為推薦項目.

4 實驗分析

4.1 數(shù)據集

本實驗數(shù)據采用個性化推薦中常用的由美國明尼蘇達大學GroupLens團隊收集整理的MovieLens數(shù)據集[19].數(shù)據集包含943個用戶對1682部電影的100，000 條評分記錄，評分范圍為1到5分，數(shù)值越大說明用戶對電影越喜歡.其中每個用戶有超過20條的評分記錄.數(shù)據集的稀疏度為93.7%.實驗將數(shù)據集按80%/20%隨機劃分成訓練集和測試集，訓練集作為算法的輸入評分矩陣，測試集用于衡量算法的準確度.

4.2 相似度計算復雜度比較

本實驗針對3.1中提到的推薦算法中常用的幾種相似性度量方法和巴氏系數(shù)度量方法進行計算復雜度的比較.進行實驗的相似性度量方法有歐式距離、余弦距離、Pearson相關系數(shù)、修正余弦距離和本文算法中的巴氏系數(shù).在硬件環(huán)境等相同條件下，幾種度量方法在MovieLens的數(shù)據集下進行相似度計算的平均時間的實驗結果如表4所示.

表4 相似度計算時間Table 4 Time of similarity calculation

表中可以看出，巴氏系數(shù)由于每個向量的維度大大減小，計算的復雜度降低，相對于其他幾種常用的相似性計算方法計算時間明顯降低，其他幾種常用的相似性計算方法的平均計算時間是巴氏系數(shù)的20-80倍左右.所以巴氏系數(shù)在推薦算法動態(tài)更新的要求下優(yōu)勢較大，更加適合應用于在線推薦領域的Slope One算法中相似度的計算.

4.3 準確度評價指標

實驗采用推薦算法較常用的平均絕對誤差(MAE)和均方根誤差(RMSE)做為評價指標.MAE和RMSE 的值越小，代表推薦的質量越高.MAE和RMSE 的公式如下：

(13)

(14)

pi表示推薦算法的預測值，qi表示實際的評分值.N為預測評分的個數(shù).

4.4 實驗結果分析

本文使用k-means聚類方法對用戶評分習慣進行聚類，聚類簇的數(shù)目會對實驗效果產生影響.為了找到最適合的聚類簇數(shù)目k，首先對數(shù)據集進行聚類效果實驗，找出最佳的聚類簇數(shù)目.

圖2 聚類效果Fig.2 Clustering results

在MovieLens數(shù)據集上進行聚類實驗，聚類簇的數(shù)目選取為2到7簇，分別計算在不同簇下的MAE值，實驗結果圖2所示.聚類簇實驗表明，在MovieLens數(shù)據集下，對于消除了評分習慣差異的用戶聚類中，聚類簇選取3或4時效果較好.本文實驗中選取聚類簇數(shù)目為4.

為了驗證本文算法的有效性，針對傳統(tǒng)Slope One算法與本文算法(BCUC Slope One Algorithm)在五組MovieLens數(shù)據集上分別進行了實驗對比，實驗結果見圖3、圖4.兩個算法對評分矩陣中所有未評分項都做了填充預測，MAE和RMSE對測試集中的打分項目與預測結果進行對比計算準確度.實驗結果表明，本文算法在兩個指標上比傳統(tǒng)Slope One都有一定的提高.說明考慮了用戶差異和項目相似性的Slope One算法可以提高推薦準確度.

圖3 平均絕對誤差結果對比Fig．3 MAEresults圖4 均方根誤差結果對比Fig．4 RMSEresults

如下頁表5所示，本文算法在MovieLens 各個數(shù)據集上的平均準確度為MAE：0.738，RMSE：0.938.張玉連等人[13]將機器學習融入加權Slope One算法中，通過梯度下降的方法，迭代求解最優(yōu)參數(shù)，有效提高了Slope One算法的推薦準確度.其提出的多種改進算法的準確度大致為MAE：0.72-0.74，RMSE：0.93-0.95.本文算法雖然在推薦準確度上相較之沒有明顯提高，但是其算法融合了機器學習的方法，在求解過程中需要利用梯度下降法不斷迭代求解，求解結果也會受到下降步長和迭代次數(shù)的影響.而本文算法具有計算實現(xiàn)過程簡便，解釋性強，計算復雜度低的優(yōu)勢.

表5 本文算法在整個數(shù)據集上的平均指標Table 5 Average accuracy of the algorithm in the data set

5 結束語

針對目前Slope One算法沒有考慮項目相似性的差異和用戶評分習慣的偏差，采用了一致性權重計算，導致個性化推薦的準確度低的問題.本文通過加入一種新的相似性度量方法——巴氏系數(shù)，作為項目相似性的計算方法.巴氏系數(shù)對比其他常見的相似度計算方法，在計算復雜度上的優(yōu)勢較大，降低對Slope One算法在線推薦能力的影響.而且，巴氏系數(shù)能夠較好解決在稀疏性問題下的相似度計算.本文又通過聚類的方法，將消除了評分習慣差異的用戶進行聚類，降低了用戶偏好差異對Slope One算法的影響.最后實驗表明，本文提出的算法相對傳統(tǒng)Slope One算法，保證低復雜度的前提下，在推薦準確度上也有所提高.

[1] Park D H，Kim H K，Choi I Y，et al.A literature review and classification of recommender systems research[J].Expert Systems with Applications An International Journal(ESWA)，2012，39(11)：10059-10072.

[2] Ricci F，Rokach L，Shapira B，et al.Recommender systems handbook [M].Springer，2011.

[3] Liu L M，Zhang P X，Lin L，et al.Research of data sparsity based on collaborative filtering algorithm[J].Applied Mechanics & Materials(APMSIT)，2013，462-463：856-860.

[4] Pirasteh P，Jung J J，Hwang D.Item-based collaborative filtering with attribute correlation：a case study on movie recommendation[M].Intelligent Information and Database Systems,Springer International Publishing，2014.

[5] Deng Ai-lin，Zuo Zi-ye，Zhu Yang-yong.Collaborative filtering recommendation algorithm based on item clustering[J].Journal of Chinese Computer Systems，2004，25(9)：1665-1670.

[6] Wang J，Lin K，Li J.A collaborative filtering recommendation algorithm based on user clustering and Slope One scheme[M].International Conference on Computer Science& Education(ICCSE ),2013:1473-1476.

[7] Yu Xue，Li Min-qiang.Collaborative filtering recommendation model based on effective dimension reduction and K-means clustering[J].Application Research of Computers，2009，26(10)：3718-3720.

[8] Wang X，Zhang J.SVD-based privacy preserving data updating in collaborative filtering[J].Lecture Notes in Engineering & Computer Science(LNCS)，2012，2197(1):377-384.

[9] Wang X，Zhang J，Lin P，et al.Incorporating auxiliary information in collaborative filtering data update with privacy preservation[J].International Journal of Advanced Computer Science and Applications(IJACSA)，2014，5(4)：224-235.

[10] Luo X，Zhou M，Xia Y，et al.An efficient Non-negative matrix-factorization-based approach to collaborative filtering for recommender systems[J].IEEE Transactions on Industrial Informatics(IEEE Trans Ind.Informat)，2014，10(2)：1273-1284.

[11] Lemire D，Maclachlan A.Slope one predictors for online rating-based collaborative filtering[C].Computer Science(CS)，2007：21-23.

[12] He Huai-qing，Li Tu-bo，Li Tie-jun.Slope one algorithm improved by resource allocation[J].Journal of Chinese Computer Systems，2015，36(5)：1056-1058.

[13] Zhang Yu-lian，Huan Si-si，Liang Shun-pan.Integrating machine learning into weighted slope one algorithm[J].Journal of Chinese Computer Systems，2016，37(8)：1712-1716.

[14] Nielsen F，Boltz S.The Burbea-rao and bhattacharyya centroids[J].IEEE Transactions on Information Theory(IEEE Trans.Inf.Theory)，2012，57(8)：5455-5466.

[15] Comaniciu D，Ramesh V，Meer P.Real-time tracking of non-rigid objects using mean shift[C].Computer Vision and Pattern Recognition(CVPR)，2000，2：142-149.

[16] Kailath T.The divergence and bhattacharyya distance measures in signal selection[J].Communication Technology IEEE Transactions on(IEEE Trans.Commun.Technol)，1967，15(1)：52-60.

[17] Patra B K，Launonen R，Ollikainen V，et al.A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J].Knowledge-Based Systems，2015，82(2)：163-177.

[18] Xu D，Tian Y.A comprehensive survey of clustering algorithms[J].Annals of Data Science(AODS)，2015，2(2)：165-193.

[19] Harper F M，Konstan J A.The movieLens datasets：history and context[J].ACM Transactions on Interactive Intelligent Systems(TIIS)，2016，5(4)：1-19.

附中文參考文獻：

[5] 鄧愛林，左子葉，朱揚勇.基于項目聚類的協(xié)同過濾推薦算法[J].小型微型計算機系統(tǒng)，2004，25(9)：1665-1670.

[7] 郁 雪，李敏強.一種結合有效降維和K-means聚類的協(xié)同過濾推薦模型[J].計算機應用研究，2009，26(10)：3718-3720.

[12] 賀懷清，李圖波，李鐵軍.資源分配的改進Slope One算法[J].小型微型計算機系統(tǒng)，2015，36(5)：1056-1058.

[13] 張玉連，郇思思，梁順攀.融合機器學習的加權Slope One算法[J].小型微型計算機系統(tǒng)，2016，37(8)：1712-1716.