融合似然比相似度的協同過濾推薦算法研究

王嶸冰，徐紅艷，馮 勇，郭 浩

(遼寧大學 信息學院，沈陽 110036)

1 引 言

互聯網技術的飛速發展，人們在享受豐富的網絡資源和服務的同時也不得不忍受信息過載的困擾．個性化推薦系統被認為是當前解決信息過載問題的有效方法[1].協同過濾推薦是目前應為最為廣泛的推薦方法，分為基于用戶的協同過濾推薦和基于項目的協同過濾推薦，該方法的核心步驟是通過計算用戶與用戶之間或者項目和項目之間的相似度得分來對未來用戶的首選項進行預測[2].

在基于用戶的協同過濾推薦系統中，推薦算法依賴于用戶相似度的計算，因此對用戶相似度計算方法的改進就成了提高推薦算法準確度的有效途徑之一[3].皮爾遜相關系數、余弦相似度、Jaccard系數及巴氏距離等都是目前廣泛使用的計算相似度的方法，其實用性已得到驗證，但局限性也逐漸暴露出來，特別是在數據稀疏的情況下無法準確衡量用戶的相似度，這在很大程度上影響了推薦算法的準確度[4].

2 相關工作

2.1 傳統相似度計算方法

對于用戶相似度計算方法的研究，目前使用的計算方法均依據待測兩個向量的距離，如果兩個向量的差距很小，則意味著這兩個向量很相似[5].對于用戶相似度計算來說，基本思路是首先找到兩個用戶u，v共同評分項目的評分向量Vu，Vv，然后通過計算向量間的相似度作為用戶u，v間的相似度[6].

2.2 傳統方法不足分析

雖然傳統計算方法在協同過濾推薦算法中取得了很大的成功，但仍然存在著一些局限之處，其中最突出的就是在數據稀疏的狀況下其結果容易出現過分放大或縮小，甚至無法計算的情況[7，8].例如，矩陣的稀疏程度為90%，這意味著可參與計算的評分數據只有10%，假設每個用戶平均評分數據有5個，則在這種情況下每個用戶可用于相似度計算的評分數據只有0.5個，這就導致在很多情況下用戶之間的相似度是無法計算的或者計算不準確[9].下面簡要分析傳統相似度計算方法的不足與局限之處：

1)當所處理數據集的稀疏程度較高時，由于用戶之間共同評過分的項目數量不足，這必然會導致在用戶相似度計算上的不準確.

2)在用戶之間共同評過分項目的數量只有1個的情況下，Jaccard相關系數盡管是可以計算出相關結果的，但結果很難令人信服；而余弦相似度在該情況下的計算結果顯示總為1.

3)當兩個用戶的評分向量在每個維度上的取值都是相同的情況下，例如{1，1，1}，{2，2，2}和{5，5，5}，皮爾遜相關系數由于減去評分平均值之后其計算公式的分母為0，所以出現無法計算的情況；而余弦相似度的計算結果顯示總為1[10].

4)在不同取值的情況下，皮爾遜相關系數與余弦相似度計算的結果往往會出現很大偏差.例如，當兩個用戶評分向量分別為{1，0，5}和{5，4，3}時，由皮爾遜相關系數計算出來代表相似度的值是很大的，但從現實情況來看兩個用戶的相似度很低；相反地，當兩個用戶評分向量依次為{4，5，3}和{5，4，5}時，由皮爾遜相關系數計算出來的代表相似度的值是很小的，但從現實情況看來兩個用戶的相似度很高；當用戶u、v、w的評分向量分別為{2，2，2}、{5，5，5}、{1，2，2}時，肉眼觀察顯然用戶u和w很相似，但根據余弦相似度計算顯示，結果卻表明u與v更相似[11].

3 似然比相似度

3.1 計算思想

融合似然比的思想是受到在遺傳圖譜計算中廣泛使用的LOD值和社區檢測中得出的模塊化概念的啟發[12].在這兩種情況下，相似度的概念是基于假設存在某種潛在數據結構，在此假設之上現有的(即已評分的、未缺失的)數據在這樣數據結構上的分布中取得某個值的概率與此數據在概率隨機試驗中出現的概率的比值.在遺傳圖譜的計算中，LOD值表示兩個遺傳位點連鎖的概率與不連鎖的概率的比值的常用對數值[13].紐曼[13]在社區結構領域引入了這種概念：如果社交網絡頂點之間的邊是隨機生成的，一個社區結構包含了比預期更多的邊緣，也就是包括了更多的類簇.這些想法延伸到推薦系統領域，可以有效彌補傳統計算方法的不足，藉此提出了似然比相似度.

3.2 似然比相似度定義

根據上面所介紹的LOD值的相關思想，本文給出似然比相似度的定義如下：

定義1.對于兩個分別獨立賦值的用戶評分向量xu= {xu1，xu2，…，xui}和xv= {xv1，xv2，…，xvi}，xui和xvi分別表示用戶u和用戶v對項目的評分，它們的似然比相似度(Likelihood Ratio Similarity，LRS)按照公式(1)方式定義：

(1)

式(1)中的分子表示假設評分向量xu和xv在所定義的簇模型中屬于同一簇的條件下，評分向量xu和xv中的每一對對應評分值取值之差出現的條件概率；分母表示評分向量xu和xv中的每一個值在隨機產生的情況下，每一對評分對應值取值之差出現的概率.

評分向量中每個值的取值只能是離散值V={1，2，…，d}中的一個數字.那么，就可以簡單的計算出xui和xvi在純粹的隨機試驗的條件下，而且都未缺失有值的情況下，xui和xvi差值出現的概率.例如在此條件下xui=xvi，這個概率為1/d2.因為，在上述條件下，在指定的項目i上，兩個用戶的評分差為0的概率為p(|xui-xvi|=0)=d/d2=1/d.同理，可以推出出現其他差值的概率(p|xui-xvi|=δ)，其中δ為1，2，…，d-1.

綜上所述，似然比相似度公式中分母的定義如公式(2)所示：

(2)

其中，bδ=p(|xui-xvi|=δ)，xui和xvi是隨機、獨立產生的.#δ表示差值δ出現的次數.

計算的難點在于如何定義在假設xu和xv屬于同一簇的情況下，xui和xvi取值之差為δ的條件概率.根據LOD值思想和社區檢測中的模塊化概念，在推薦系統中有以下兩個可信的假設：

1)在推薦系統數據中存在著一個潛在的簇結構模型：在推薦系統數據中有很多簇C1,C2,…,Ck，并且每個用戶u都至少屬于一個簇Cc.

2)用戶對同一項目評分差的概率分布是固定在一個簇上的.

將上述假設總結歸納就是相似用戶的評分是相似的.

根據以上合理的假設，定義評分之差|xui-xvi|的概率分布如公式(3)所示：

(3)

為了保證一個合理的概率分布，所以評分差為d-1時計算如公式(4)所示：

(4)

因此，似然比相似度公式中分子的定義如公式(5)所示：

(5)

其中，cδ與#δ參照上文中的定義；如果用戶u對項目i有評分，則xui=rui.

本文強調xu和xv可能會存在很多缺失值，這些缺失值在余弦相似度和皮爾遜相關系數計算時被簡單的看成是0，本文對這些缺失值在計算過程中是不考慮在內的.另一方面，只要1/2>1/d，LRS值會隨著共同評分項目數量的增多而增大，而且一般而言，評分差值對LRS值的作用取決于離散評分值的最大值d.例如，當d=5時，b1>c1；但是當d=10時，b1

綜上所述，可以把LRS值改寫成為如公式(6)：

(6)

其中，log10(cδ/bδ)是在有共同評分的項目i下，評分xui和xvi差的絕對值為δ時對LRS值貢獻的數值.

特別注意的是，似然比相似度的最大值是在兩個評分向量都不缺失數據且完全相同的條件下取得的.但是相似度是按照O(nlog10d)增長的，n代表的是輸入向量的維度，d是此離散評分值的數量.

似然比相似度是負數的情況代表著數據更可能是隨機巧合的相似情況，而不是在本文所陳述的用戶數據簇模型的基礎上出自同一簇的可能性.

3.3 混合相似度

在日常使用中，一般習慣于將相似度與1比較，越接近1，相似度就越高.所以在此對似然比相似度進行歸一化處理.本文使用反正切函數進行歸一化處理，處理如公式(7)所示：

(7)

由于LRS考慮的是一個概率上的相似度，沒有把評分差異納入相似度的計算中，故在此基礎上考慮評分之間差異的相似度，需要加入歐幾里得距離作為另一半相似度.

歐幾里得距離(Euclidean Distance)是一個經常使用的距離上的定義，表示在多維坐標空間中兩個點之間的真實距離，或者是所表示向量的自然長度(即該點到原點的距離).公式定義如(8)所示：

(8)

計算出來的歐幾里德距離是一個大于0的數，為了使其更明顯地體現用戶之間的相似度，可以把它規約到(0，1]之間，就形成了基于歐氏距離的相似度，所以歸一化處理如公式(9)所示：

(9)

綜合前文所述，本文最終使用用戶混合相似度作為最終的用戶相似度的計算公式，定義如公式(10)所示，所占權重比例是將由實驗得到最優值.

LEsim(xu,xv)=φ×Lsim(xu,xv)+(1-φ)×Esim(xu,xv)

(10)

4 實 驗

4.1 實驗環境與評價標準

本文實驗環境配置：Windows7操作系統，CPU i5-4460、3.20GHz，內存2G或以上，可用硬盤空間50G以上.算法采用Java語言編寫，對數據集直接進行文本提取.實驗用到的對比算法為Apache mahout框架所封裝的基本推薦算法.

本文使用數據集MovieLens來評估本文所使用的推薦算法的性能，該數據集包括943位用戶，1682部電影和100000條評分記錄，其中每個注冊用戶必須至少對20部電影進行評分，評分范圍{1，2，3，4，5}，評分數值越大，則表示該用戶對該項目越喜歡.用戶-項目評分矩陣的稀疏度為

1-100000/(943×1682)=0.93695[14].

本文實驗的評價指標：平均絕對誤差MAE(Mean Absolute Error)和均方根誤差RMSE(Root Mean Squared Error)[15]，根據它們的值來驗證本文所提相似度計算方法所得的預測結果的優勢.

MAE計算如公式(11)所示：

(11)

其中，rui表示用戶u對項目i的實際評分，preui表示用戶u對項目i的預測評分.T為測試集，|T|表示測試集中元素的個數.MAE越小，說明預測值與實際值越接近，預測結果就越準確.

RMSE計算如公式(12)所示：

(12)

同樣，RMSE值越小，表示預測值與評分真實值越接近，預測效果越好.

4.2 參數φ的最優值確定

參數φ用來表示似然比相似度和歐幾里得距離相似度在最終混合相似度計算中所占比例，實驗在基于用戶的協同過濾算法中進行，選取φ為不同值，從0到1.0，并調整近鄰用戶集大小N的值進行多次實驗，以排除偶然性，得到使算法效果達到最好的參數值.相似度比例參數φ對MAE值和RMSE值的影響如圖1和圖2所示.

圖1 參數φ對MAE值的影響Fig．1 EffectofparameterφonMAE圖2 參數φ對RMSE值的影響Fig．2 EffectofparameterφonRMSE

4.3 預測準確度對比實驗

為了驗證本文所提相似度計算方法優于現有的相似度計算方法，對比實驗將三種傳統相似度的計算方法皮爾遜相關系數(pearson)、余弦相似度(cosine)、巴氏距離(bhattacharyya)及本文算法(LEsim)應用到同一個基于用戶的協同過濾算法中，通過該算法的預測準確度來衡量相似度計算方法的優劣.在MovieLens數據集中，首先按照各種相似度算法進行近鄰用戶集的篩選，然后根據近鄰用戶集的評分數據進行預測評分，最后計算得出MAE和RMSE值并進行比較.其中，對當前目標用戶的近鄰用戶集中的用戶個數分別選取為5，10，20，…，160，進行多次實驗，以排除偶然因素.各種相似度預測準確度的比較如圖3和圖4所示.

圖3 準確度在MAE值上的對比(原始數據集)Fig．3 AccuracycomparisononMAE(originaldataset)圖4 準確度在RMSE值上的對比(原始數據集)Fig．4 AccuracycomparisononRMSE(originaldataset)

4.4 不同稀疏性對比實驗

為了檢驗在不同稀疏程度的數據集下本文所提出的相似度計算方法的預測性能，本文設置如下對比實驗：從原始MovieLens 數據集刪除部分數據，使其稀疏度達到 0.99，算法預測準確度的比較如圖5和圖6所示.

圖5 準確度在MAE值上的對比(稀疏數據集)Fig．5 AccuracycomparisononMAE(sparsedataset)圖6 準確度在RMSE值上的對比(稀疏數據集)Fig．6 AccuracycomparisononRMSE(sparsedataset)

4.5 實驗結果分析

由圖1、圖2可以看出，在近鄰用戶集大小不變的情況下，在參數取0.7時本文所提的相似度計算方法的效果達到最佳；通過調整近鄰用戶集的大小進行多次實驗排除偶然因素，得到同樣的效果.由圖3、圖4可以看出，總體上由LEsim計算所得到的MAE和RMSE值都比其他三種相似度計算方法要小，也就是說LEsim的表現更優秀，預測更準確.單獨來看每條折線的情況，隨著近鄰用戶集的逐漸增大，MAE和RMSE值都趨于平穩，LEsim的變化趨勢較其他方法來說較為平緩，說明LEsim的表現相對穩定.圖5、圖6說明本文所提方法在數據稀疏的情況下表現依舊良好.

5 結束語

本文介紹了似然比相似度的計算方法，并將它應用于個性化推薦領域中.該方法適合于離散的、稀疏的、高維的數據環境.并且在真實的數據集中通過實驗表明似然比相似度可以很好地衡量用戶之間的相似度，它的性能優于傳統計算方法.未來的研究重點是探索在推薦系統數據中如何設計一個更好的聚類結構模型，以提高協同過濾算法預測準確度.另一個可能的研究方向是開發快速聚類方法，使用似然比相似度，以提高基于用戶的協同過濾推薦算法的可擴展性.