融入項目相關性的加權Slope One算法研究*

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

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

1 引言

信息技術和網絡互連的快速發展，帶來信息量的激增，人們正步入信息過載的時代[1]。目前，個性化推薦技術被業界認為是解決信息過載問題的首選方案，它根據使用者的歷史交互數據開展數據的分析與挖掘，將用戶可能感興趣而又未獲取的產品、信息等推薦給用戶[2]。近年來，個性化推薦技術已經被廣泛應用在電影、視頻、論文、駕駛路線和位置等與信息相關的服務領域。

目前，眾多的個性化推薦方法中，協同過濾推薦是應用較為成功的推薦方法，分為基于用戶的協同過濾推薦和基于項目的協同過濾推薦[3]。Slope One算法作為應用廣泛的基于項目的協同過濾推薦算法，是由Lemire等人于2005年提出的。該算法易于實現，推薦準確度較高[4]。但該算法在實現時，將所有項目平等對待，未對項目的相關性加以考量，并且在數據集稀疏時推薦效果不佳。文獻[4]中同時也提到了加權Slope One算法，該算法將同時被評分的兩個項目的用戶數量作為加權值，但是同樣缺乏對項目相關性的考量，推薦效果不甚理想。針對Slope One算法的不足，眾多學者從不同視角進行了改進，如：Xiao等人將Slope One算法與基于內容的推薦算法相結合，但此算法在數據稀疏時的推薦效果不理想[5]。Wang等人提出將機器學習的相關算法應用于Slope One算法參數的學習計算中，再預測推薦[6]。孫麗梅等人提出了基于動態k近鄰的Slope One算法，采用用戶相似度的k近鄰方法篩選用戶評分數據，提高了推薦準確性[7]。但是，上述方法均沒有從項目類型上入手，減少無關項目對預測結果的不良影響。因此，本文在傳統Slope One算法中加入了項目類型相關性計算及項目篩選策略，提出了一種融入項目相關性的加權Slope One算法，使算法的推薦效率和推薦準確率均得到了一定程度的改善。最后經實驗對比分析，本文所提算法切實可行，與當前應用較廣的Slope One算法相比具有更優的推薦效率和準確率。

2 相關工作

2.1 Slope One算法介紹及不足分析

Slope One算法本質上是基于項目的協同過濾推薦算法，該算法認為在項目和項目之間、評分和用戶自身之間存在著一種線性關系。Slope One算法是采用公式f(x)=x+b來預測評分的。b代表著項目間的平均評分偏差，x表示評分值。

假設S={,,…,}為用戶對項目X、Y的評分向量集，S中的每一個數值對表示一個用戶分別對項目X和項目Y的實際評分。在計算項目Y對項目X的評分差估計值時，可以使用最小二乘法來實現[8]，計算公式如式（1）：

計算出評分差估計值b后，采用如上所提的線性關系，根據目標用戶給出的項目X的評分和b來對項目Y的預測評分進行估算。

Slope One算法對預測評分計算的一般流程如下：

（1）生成用戶集合U：在用戶-項目評分矩陣中，將所有對目標項目做過評分的用戶篩選出來形成用戶集合U。

（2）生成項目集合P：首先找出已被目標用戶給出評分的項目，若該項目也同時被其他用戶給出評分，則該項目將被加入到算法計算所需的項目集合P中。

（3）預測項目評分[8]：篩選出U、P之后，就可以提取Slope One算法需要的評分數據，即U與P交叉處的評分數據。多項目條件下，用戶u預測項目j的評分表示為P(u)j，計算公式如式（2）、式（3）所示：

其中，devj,i表示項目j相對項目i的評分偏差；Uj,i表示項目i和項目j有共同評分的用戶集合；ru,i和ru,j分別表示用戶u對項目i、j的評分；Ij表示與目標項目j同時被評分的項目集合；card()表示相應集合中包含元素的數量。

Slope One同其他推薦算法一樣，在預測完項目評分之后采用Top-N方式生成推薦列表。

通過對Slope One算法計算方式的分析，可總結出該算法有如下兩點不足：

（1）該算法僅僅考慮了當前用戶的評分項目與目標項目之間的平均評分偏差，再求加權平均值計算得出。由于沒有考慮項目間的相關性，因此算法在對預測評分進行計算過程中，極有可能將與目標項目在性質上完全不相關的項目納入項目集合中，計算結果就會有較大的偏差。

（2）文獻[9-10]研究的結果表明，該算法在數據集較為稠密時，預測精度較高，但當數據集相對稀疏時，該算法在推薦效果上的優勢并不明顯。

基于上述兩種不足導致該算法推薦的結果準確度不理想，本文算法將圍繞以上兩方面的不足開展研究與改進工作。

2.2 項目相似度計算方法介紹及不足分析

目前對項目相似度的研究大多集中在項目評分上的相似度或項目的評價信息作為切入點來計算相似度，而沒有從項目類型等項目本質信息來衡量。目前常用的項目相似度計算方法及不足分析如下：

（1）根據購買次數計算

兩個不同項目被同一用戶購買的次數越多，它們就越相似[11]。項目j和項目i之間的相似度計算如式（4）所示：

這種方法在計算屬性相似度的時候，計算過程非常繁瑣。

（3）多層次計算

此方法首先基于共同用戶集計算第1級相似度，然后逐步融入其他維度因素[13]，計算過程如下：

基于共同用戶集的第1級相似度計算。設項目i、j的用戶集分別為Usr(i)、Usr(j)，則使用式（6）計算項目i、項目j的相似度：

其中，Ti表示項目i總共被購買的次數；Tj表示項目j總共被購買的次數；Ti∪Tj表示項目i和項目j被同一用戶購買的次數。這種方法帶有一定的偶然性，不適合用在預測評分的系統中。

（2）根據項目屬性

在該計算方法中，項目之間的相似度使用項目屬性相似度來衡量[12]。項目有很多屬性，因此每個項目可以表示為一個t維向量，每個維度對應當前項目的一個屬性特征。aig表示項目i的第g個屬性，利用相關公式確定每個屬性在最終推薦中所占不同的權重wk，然后加權得到兩個項目屬性的相似度。那么項目i和項目j之間的相似度可以表示為式（5）：

融入活躍度的第2級相似度計算。用戶u的活躍度通過其評分項目數量RNum(u)來表示，則第2級相似度計算如式（7）：

融入時效的第3級相似度計算。設用戶u對項目i和項目j的評分時間分別為Timeui和Timeuj，則第3級相似度計算如式（8）：

以上給出的多級相似度計算雖然能夠從不同角度分析項目之間的相似性，但是算法的實現過程中需要進行大量的計算，并且算法效率較傳統算法并沒有較大提高，其時間復雜度為O(mlgm)，m為全部項目數。

3 融入項目相關性的加權Slope One算法

針對Slope One算法中存在的不足，本文提出了項目相關性的計算方法，從項目類型上入手，減少無關項目對預測結果的影響。結合Slope One算法計算平均評分差值的特點，對用戶-項目矩陣進行篩選操作，目的是得到一個局部數據稠密的用戶-項目矩陣，并且項目間評分差值較為穩定。最后將項目類型相關性計算和項目篩選策略融合到推薦算法中，形成融入項目類型相關性的加權Slope One算法。

3.1 項目相關性的計算

該步驟是進行數據預處理的過程，根據項目數據集的相關數據計算出項目之間的相關性，得到一個類型相關性的表格，然后就可以根據計算結果和目標項目的類型進行篩選。這樣既可以過濾掉無關項目的干擾，又可以減少用戶-項目矩陣的局部相似度。

3.1.1 項目相關性的定義

本文提出的計算方法是利用項目已有的相關數據來計算項目之間的相關性。項目類型a和b之間的相關性表示為g_corr(a,b)，計算如式（9）所示：

在式（9）中，項目類型之間的相關性g_corr(a,b)是由g_prob(a,b)和g_weight(a,b)來計算。項目類型共同出現的概率矩陣表示為g_prob(a,b)，這個概率矩陣是不對稱的。項目類型評分相似度矩陣表示為g_weight(a,b)，是由皮爾遜相關系數計算的一個對稱矩陣。ω表示兩者權重，由反復實驗得到最優取值。

3.1.2 項目類型共同出現概率的計算

在推薦系統的項目數據中，每個項目都至少有一個所屬類型，有些項目甚至有4到5個所屬類型。比如電影數據中，《海豚灣》的所屬類型為紀錄片，而《拯救大兵瑞恩》屬于劇情片、動作片、歷史片和戰爭片。

在興趣相似度中，如果兩個用戶共同感興趣的物品越多，則說明這兩個用戶的相似度越高。借鑒該思想，如果兩個類型同時被一個項目所屬的情況數量很多，那么可以認為這兩個類型是有一定關系的，即相關度高。本文就是根據這種思想來衡量兩個項目類型是否具有關系。在本文提出的計算方法里，項目類型共同出現的概率用條件概率來計算，計算公式如式（10）：

式（10）中Ia表示項目類型屬于類型a，Ia∩b表示項目類型既屬于類型a又屬于類型b。例如：A影片屬于類型 1、2、3，B 影片屬于類型 3、4、5，則g_prob(a,b)=1/3。

3.1.3 項目類型評分相似度計算

類型權重公式如式（11）所示，這是一個皮爾遜相關系數的變形，用來計算屬于類型a和類型b項目評分之間的評分相關性。

其中，pnti(a,b)表示項目i的點數；s*,i表示項目i的平均得分；sˉa和sˉb表示類型為a和類型為b的項目的平均分。

正如前面所說，一個項目可以對應很多類型。一個項目對應的類型越少，對應類型間的相關性越高。因此，pnti是根據一個項目所屬類型的總數不同來給定的。計算公式如式（12）所示。

其中，類型權重等式有兩個目標類型，pnti計算公式中的分子是2，Gi表示項目i所屬類型的集合，|Gi|是項目i所屬的類型的總數。

3.2 項目的篩選策略

本文以用戶-項目矩陣中的評分數據為基礎，利用項目固有的類型信息，提出以下項目類型篩選策略用以挖掘出用戶最喜歡和最不喜歡的項目作為算法預測評分過程中參與計算的項目。

項目的類型集合G={g1,g2,…,gn}。當Rui=5時，認為用戶u喜歡項目i。此時，項目i對應的項目類型gc被標記為用戶u的喜歡項目類型。某個用戶可能多次對同一個喜歡的項目類型進行標記，對標記次數進行累加，形成用戶喜歡的項目矩陣。同理，當Ruj=1時，認為用戶u不喜歡項目j。此時，項目j對應的項目類型gd被標記為用戶u的不喜歡項目類型。對標記次數進行累加，形成用戶不喜歡的項目矩陣。

表1中列出了用戶u1至u5對項目i1至i7的評分矩陣。將其分開表示成兩個矩陣，一個為保留用戶評分為5的，一個為保留用戶評分為1的，同時將其他評分值重置為0，操作結果如表2和表3所示。

Table 1 User-item scoring matrix表1 用戶-項目評分矩陣

Table 2 User favorite item matrix表2 用戶喜歡的項目矩陣

項目-類型矩陣如表4所示，項目i屬于類型g就記為1，否則記為0。

Table 3 User dislike item matrix表3 用戶不喜歡的項目矩陣

表2和表3分別根據表4中的項目類型對應累加后形成的結果如表5和表6所示。

Table 5 Summary of user favorite item type表5 用戶喜歡項目類型匯總

Table 6 Summary of user dislike item type表6 用戶不喜歡項目類型匯總

從表5和表6中可知用戶最喜歡的項目類型為g2，最不喜歡的項目類型為g3。那么這兩個已篩選出來的類型所對應的項目納入到最后預測評分的用戶-項目矩陣中。

3.3 算法描述

根據上述思想，算法流程描述如下：

輸入：用戶-項目評分矩陣Rm×n，項目-類型矩陣Gn×s，目標用戶u，待評分項目i。

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

步驟1利用矩陣Rm×n，使用常用的相似度計算方法計算出用戶相似度LEsim(xu,xv)，選取Top-K形成目標用戶u的近鄰用戶集合Su，并根據Su形成相似用戶-項目矩陣R1k×n。

步驟2利用矩陣Gn×s和Rm×n，根據本文所提出的項目類型相關性計算公式（9）計算出待評分項目i的類型與其他類型的相關程度，選取Top-K形成集合G1={g1,g2,…,gk}。

步驟3利用矩陣R1k×n，挖掘出目標用戶u最喜歡的和最不喜歡的項目類型，組成集合G2={g1i,gdis}。

步驟4在矩陣R1k×n，剔除不屬于G1∪G2的項目，形成局部數據比較密集的矩陣R2k×c。

步驟5利用矩陣R2k×c，根據加權Slope One算法計算出目標用戶u對目標項目i的預測評分，產生Top-N推薦。

改進算法通過步驟1至步驟4的操作將大小為m×n原始用戶-項目評分矩陣進行預處理，在預處理過程中根據項目類型相關性的計算選擇Top-K個相關類型，并按照項目篩選策略形成局部數據比較密集的用戶-項目評分矩陣R2k×c，k?m且c?n。這樣可以在Slope One算法復雜度保持不變的情況下，通過大幅度降低輸入數據規模的方法來提高算法的執行效率。雖然數據預處理部分會使整個算法的時間復雜度略有增加，但該部分可采用離線的方式處理，因而不會影響Slope One算法的實時性。

4 實驗分析

4.1 實驗數據集與評價標準

本文實驗環境配置如下：OS Win 7，CPU i5-4460、3.20 GHz，內存2 GB或以上，硬盤空間50 GB以上。本文算法采用Java語言實現，使用了Apache Mahout開源框架下提供的原生Slope One算法，在此之前用本文算法對數據集進行了過濾篩選處理。

本文使用數據集MovieLens（http://files.grouplens.org/datasets/movielens/）中的部分數據來評估本文所提出的推薦算法的性能。選取的數據集包括用戶數量為943、項目（電影）數為1682、用戶-項目評分矩陣中包含100000條記錄，其中每個注冊用戶要求至少完成20部電影的評分，給出的評分采用5個等級，即范圍為{1，2，3，4，5}，評分數值越大，則表示該用戶對該項目越喜歡。該用戶-項目評分矩陣的稀疏度為0.93695。

實驗的評價指標：平均絕對誤差（mean absolute error，MAE）和均方根誤差（root mean squared error，RMSE）[14-15]。根據它們的值來驗證本文所提算法預測結果的優勢。

MAE計算如式（13）所示：

若將用戶u表示為Uu，項目i表示為Ii，則在式（13）中，rui表示Uu對Ii的評分真實值，preui表示Uu對Ii評分的預測值。|T|表示測試集T中元素的個數。對于計算結果，MAE值越小，說明預測評分與實際評分越接近，預測結果就越準確。

RMSE計算如式（14）所示：

同理，RMSE值越小，表明算法預測值與評分真實值越接近，預測效果越好。

4.2 參數ω的最優值確定

參數ω表示式（9）中g_prob(a,b)和g_weight(a,b)所占權重的比例。使用基于項目的協同過濾算法進行實驗，選取相似項目類型的數量為3，選取ω為不同值進行多次實驗，得到使算法效果達到最好的參數值。比重參數ω對MAE值和RMSE值的影響如圖1和圖2所示。

Fig.1 Effect of parameterωon MAE圖1 參數ω對MAE值的影響

Fig.2 Effect of parameterωon RMSE圖2 參數ω對RMSE值的影響

如圖1、圖2所示，經過多次實驗，得出ω=0.5時式（9）的實驗效果最好，因此本文實驗中取ω為0.5。根據此實驗結果，可以預先計算出系統中項目類型的相關性，表7計算出了MovieLens數據集中部分項目類型的相關性。

Table 7 Item relevance of MovieLens data set(part)表7 MovieLens數據集部分項目類型相關性

4.3 算法準確度對比實驗

為了驗證本文所提出算法具有較高的準確度，設置如下對比實驗：在MovieLens數據集中，分別使用融合用戶相似度和項目相似度的加權Slope One算法（簡稱算法1）[16]和基于用戶多屬性和興趣的加權Slope One算法（簡稱算法2）[17]進行實驗，根據實驗運行的結果來計算MAE和RMSE的值。在實驗過程中，選取當前目標用戶的近鄰用戶集大小分別為5，10，20,…，160，進行多次實驗，以排除偶然因素。3種推薦算法預測準確度的比較如圖3和圖4所示。

Fig.3 MAE contrast of 3 recommended algorithms圖3 3種推薦算法運行結果MAE值對比

Fig.4 RMSE contrast of 3 recommended algorithms圖4 3種推薦算法運行結果RMSE值對比

從圖3、圖4可以看出，本文算法在整體表現上優于算法1和算法2。本文算法MAE和RMSE值呈現先下降后上升趨勢的原因：隨著近鄰用戶集由5增至20的過程中，與目標用戶相似的用戶越來越多，因此預測準確度會提高，隨著近鄰用戶集繼續增加，并不是很相似的用戶也被納入其中，這就必然會導致預測準確度下降。

4.4 稀疏數據集中的性能對比實驗

為了檢驗在不同稀疏程度的數據集下本文算法的預測性能，設置實驗數據：在原始的MovieLens數據集（其稀疏度為0.93695）中刪除部分數據，使其稀疏度達到0.99。將3種算法應用到該稀疏數據集中，預測準確度的比較如圖5、圖6所示。

Fig.5 MAE contrast of 3 recommended algorithms(sparse data set)圖5 3種算法在稀疏數據集上MAE值對比

Fig.6 RMSE contrast of 3 recommended algorithms(sparse data set)圖6 3種算法在稀疏數據集上RMSE值對比

根據圖5、圖6可以看出，在不同稀疏程度的數據集上，實驗結果所呈現的整體趨勢是一致的，每個算法在稀疏度較小的數據集上所得的MAE和RMSE值都要小，并且在稀疏程度較大的數據集上兩種對比算法所呈現的差距變大，這說明本文算法在數據稀疏的情況下表現依舊良好。

5 結束語

本文針對加權Slope One算法中沒有考慮項目相關性的不足，提出了在加權Slope One算法中融合項目類型相關性及項目篩選策略，給出了項目類型相關性的計算方法以及適應Slope One算法特點的項目篩選方案，排除了無關項目對推薦的干擾，并對算法的處理流程進行了改進。最后通過實驗驗證了本文算法在預測準確度、處理稀疏數據集等方面均有優勢。隨著網絡互連的飛速發展，推薦算法中使用的用戶數和項目數將呈指數增長，從而導致算法運行速度較慢，且過度耗費內存資源。未來可以考慮將一些優化性能較高的機器學習方法與本文改進的推薦算法相融合，在提高算法預測準確度的同時改善算法的時空效率。