基于歸一化方法的協同過濾推薦算法

陳小輝,高 燕,劉漢燁

（榆林學院 信息工程學院，陜西 榆林 719000）

隨著計算機網絡技術迅速發展，越來越多的人類活動依賴于互聯網，人們可以通過網絡購買各類商品，獲取生活資訊，尋求合作和協助等等，但是面對海量的互聯網信息，普通用戶越來越難以及時獲取有效的信息，在這種情況下能夠提供高效的個性化的信息推薦顯得尤為重要[1]。協同過濾推薦算法是目前應用最成功的推薦算法之一，在許多領域得到了廣泛的推廣。

協同過濾（Collaborative Filtering，CF)是根據用戶的興趣愛好、歷史數據尋找與用戶在這些方面有一定相似性的鄰居，并且根據鄰居的一些行為或評價數據對用戶進行推薦。與基于內容的推薦系統不同，協同過濾推薦算法僅僅是依據用戶對項目的評價尋找評價相似的若干鄰居，而忽略數據詳細內容，一般也不提取項目的文本特征向量，因為一般情況下如果不同用戶對一些項目給出的評價相近，那么這些用戶對其他項目的評價也會相似[2]。協同過濾推薦算法一般分為兩類：基于內存的協同過濾(Memory-based CF)和基于模型的協同過濾(Model-based CF)。基于內存的協同過濾算法是目前應用最廣泛的推薦方法，又可以進一步分為基于用戶的協同過濾推薦和基于項目（item）的協同過濾推薦以及綜合考慮用戶和項目的推薦技術。基于用戶推薦算法是依據鄰居用戶對某個項目的評分來預測當前用戶對該項目的評分，基于項目的推薦算法則根據鄰居項目的評分值來預測當前項目的評分[3]。

對于協同過濾推薦算法來說，核心是計算用戶或項目之間的相似度，而在傳統的相似度計算過程中，往往不能妥善處理用戶評分向量（或項目評分向量）之間的向量空間長度差異，而且往往忽略鄰居用戶共有的評分項目（或多個用戶對鄰居項目的評分）的數值差異或者是嚴重弱化數值差異，為了解決這一問題，筆者提出了一種基于歸一化方法的協同過濾推薦算法(NDCF)，該方法在計算相似度之前首先將用戶對每一項目的評分值歸一化到一個統一的值域范圍，然后采用基于用戶的協同過濾推薦算法對歸一化后的不同向量空間中的用戶向量進行相似性度量形成最近鄰居，并產生歸一化的項目評分預測，最后再根據當前用戶在其他項目上的評分完成項目最終的評分預測，并進行推薦。

1 傳統的協同過濾推薦原理

協同過濾推薦方法中最流行應用最為廣泛的是基于內存的推薦算法，其實現原理最為直觀。以經典的基于用戶(User-based)的協同過濾推薦算法為例，它的基本思路是通過尋找與當前用戶相似度最高的k個鄰居，然后依據鄰居對某個項目的評分來預測當前用戶對該項目的評分[4]。這種推薦算法可分為3個實現步驟：數據定義、用戶相似度計算和項目評分預測與推薦。

1.1 數據定義

數據定義實際就是定義用戶評分矩陣R，R是一個n*m的矩陣，n和m分別代表矩陣中的用戶數和項目數。矩陣中的元素值代表用戶對項目的評價值，包括顯式評分和隱式評分兩種，顯式評分一般指用戶直接對項目的評價值，隱式評分則是根據用戶的瀏覽行為如瀏覽頻率、時間、購買等間接推測出的數值[5]。矩陣的用戶向量（水平向量）代表特定用戶對項目的評價值，項目向量（垂直向量）代表某個具體項目得到的用戶的評價值。如果存在用戶ux對項目iy的評分rxy，則評分矩陣R中有R[x,y] = rxy，用戶評分矩陣R如式(1)所示。

1.2 相似度計算

協同過濾推薦本質是基于近鄰的搜索方法，其實現核心是對用戶或項目間的相似性的度量。常用的計算相似性方法主要有向量空間相似性度量方法（VSS）和皮爾森相似性度量方法（PCC）兩種。向量空間相似性度量方法是把用戶對項目的評分看作是一個n維向量，用戶間的相似性是通過計算兩個用戶向量之間的余弦夾角來決定[6]。用戶u和v之間的相似度SIM(u, v)計算如式（2）所示，式中Iuv表示用戶u和用戶v共同評分的項目集合。

皮爾森相似性度量方法是用來衡量變量的線性關系，是在向量空間相似性度量方法的基礎上考慮了用戶評分的數值差異，使用用戶評分的偏差作為評分值參與計算，用戶u和v的相似度SIM(u, v)計算如式（3）所示，其中代表用戶u和用戶v對各自已評分項目的平均評分，Iuv代表用戶u與用戶v共同評分項目的集合。

1.3 項目評分預測與推薦

使用式(2)或式(3)計算得到任意兩兩用戶之間的相似值以后，對于特定的目標用戶，可以得到與其相似度最大的N個鄰居用戶，需要進行預測的目標用戶的某一未評分項目，可以按照一定的計算方法根據這些鄰居對該項目的評分來得到，為提高預測準確度需要考慮到不同用戶的評分尺度的不同，計算時候需要考慮用戶對所有項目的平均評分，可利用公式(4)進行評分的預測，式中 表示用戶u對項目i的評分用戶u和用戶v對各自已評分項目的平均評分，N(u)代表目標用戶u的鄰居用戶集。在計算得到當前用戶對于未評分項目的預測評分后，可以根據評分值對這些未評分項目排序，然后選擇評分最高的若干項目進行推薦。

2 基于歸一化方法的協同過濾推薦

2.1 傳統協同過濾推薦算法的不足

傳統的基于內存的協同過濾推薦因為其算法簡單實用在較多領域得到了應用，但是仍然存在較多問題。特別是在相似度計算過程中，VSS算法和PCC算法都是基于用戶對項目評價的數值進行直接統計去計算相似度，而沒有考慮用戶向量的差異與評分的數值大小[7]。例如圖1，對于一個簡單的用戶評價矩陣，它包含5個用戶和5個評分項目，用戶對每一個項目的評分值在1和6之間。

圖1 用戶項目評分矩陣Fig.1 Scoring matrix of users and items

如果要預測用戶u2對于項目i5的評分，采用VSS和PCC相似度算法可以得到Sim(u1，u2)的值為0.954 8和0.660 3，得到Sim(u2，u3)的值為 0.865 3 和 0.492 6，顯然 Sim(u1，u2)＞Sim(u2，u3)根據這個計算結果，u1與u2的相似度比u2與u3的相似度大。而從圖1可以看出u1的評分區間是[1,6]，而u2和u3的評分區間是[1,4]，所以u1與u2的相似度應當比u2與u3的相似度小，在計算u2對i5的評分時候應當參照的鄰居是u3對i5的評分而不是u1。這個矛盾是因為皮爾森算法不能對處于不同向量空間的用戶向量的評分風格差異進行有效處理，而向量空間算法則只關注用戶向量之間的空間夾角，會忽略用戶向量間的長度差異因此有必要尋找更合理有效的，符合實際情況的相似度計算方法從而改善推薦性能。

2.2 基于歸一化方法的相似性度量方法

為了克服傳統協同過濾推薦算法的不足，筆者嘗試在傳統算法中引入歸一化數據處理過程。在形成用戶評分矩陣以后，首先將所有用戶的項目評分值歸一到統一的值域空間，該處理過程假設任一用戶向量對所有項目的評分不能全部相等。在實現過程中，對于評分矩陣R的每個行向量，使用該用戶的最高評分值和最低評分值來歸一化每一個項目評分，最后項目評分值位于區間[0,1]，歸一化處理后用戶u對項目i的評分 r'ui計算方法見式(5)。

根據式（6）計算得到的Sim(u,v)∈[0,1]，值越大則用戶u和用戶v越相似，當等于0時表示兩個用戶完全不同，取1時表示兩個用戶相同。對于圖1中用戶評分矩陣數據計算可得Sim(u1，u2)和Sim(u2，u3)的值分別為0.791 5和0.855 7，則該相似性結果與事實相符。特殊情況當某個用戶對所有項目的評分都完全一樣的時候，會出現零除數的情況，但是由于所有的項目會涉及到推薦系統的各種商品、服務，有效用戶的評分不會全部相同，所以可以忽略該情況。

為度量被評分的項目之間的相似性，可通過對原始評分矩陣R的每個項目的所有評分值（每一列）進行歸一化處理，同樣歸一處理后矩陣中每列的值都在區間[0，1]上，式（7）給出了度量項目i和j之間相似度Sim(i,j)的計算方法，式中Uij表示對項目i和項目j都做出了評價的用戶集合，|Uij|表示集合中用戶的個數，rimin和rimax表示用戶對項目i的最小和最大評分值，rjmin和rjmax表示用戶對項目j的最小和最大評分值。

特殊情況當所有用戶對某個項目的評分都完全一樣的時候，會出現零除數的情況，但是由于對單個項目的評分會涉及到推薦系統的各類用戶，評分在現實情況下不會全部相同，所以可以忽略該情況。

2.3 基于歸一化方法的項目評分預測和推薦

基于2.2節提出的相似性度量算法，本節給出一種新的基于內存的協同過濾方法,當需要預測用戶u對項目i的未知評分值時，該方法會根據用戶的原始評分尺度來進行預測。在基于用戶的項目評分值預測中用戶u對項目i的預測評分可以通過式（8）計算，式中U表示與用戶u相似度最高的同時對項目i進行了評分的k個用戶的集合。

3 實驗與分析

3.1 實驗數據集

為了驗證算法的有效性，采用Group Lens研究小組提供的Movielens 電影評分公開數據集（http://www.grouplens.org）對算法進行驗證和評估。該數據集采集于一個電影推薦網站，包含了943位用戶對1 682部電影的100 000個評分，用戶評分矩陣的稀疏度為93.7%。實驗中從原始評分矩陣中隨機修改一部分評分項目，形成了10個數據密度分別為2%，4%，6%，8%，10%，12%，14%，16%，18%和20%的稀疏矩陣，使用稀疏度較高（數據密度較低）的原因是實際中的評分矩陣通常非常稀疏。

3.2 評價標準

為了檢驗項目評分的預測準確度，使用被廣泛采用平均絕對誤差（Mean Absolute Error，MAE)來衡量預測的有效性。MAE是預測值與真實值之間的絕對偏差的平均值，式（10）給出了MAE的計算方法，式中rui是指用戶u對項目i的實際是指預測得到的用戶u對項目i的評分值，N是被預測值的數量，MAE值越低，則說明預測的準確度越高。

3.3 實驗方案

為了比對歸一化處理協同過濾算法的有效性，采用了5種傳統協同過濾方法與基于用戶的歸一化協同過濾推薦算法（NDCF）進行了對比實驗：基于用戶的平均數法（UMEAN)，該方法在計算未知項目的評分時，使用用戶對所有項目的評分均值表示；基于項目的平均數法(IMEAN)，該方法在計算未知用戶評分時，使用所有對當前項目評分用戶的評分均值；使用PCC的基于用戶的協同過濾（UPCC）；使用PCC的基于項目的協同過濾（IPCC）；混合使用UPCC和IPCC實現的一種協同過濾方法（WSRec）。實驗采用五折交叉驗證方法，對于10個稀疏矩陣中的每個評分矩陣，將用戶評分記錄按照4 : 1的比例劃分為訓練集和測試集，而且分別進行了5次劃分，分別依據訓練集中數據來預測計算測試集中數據并計算相應MAE值，最后統計得出5次實驗的平均MAE值。實驗中鄰居規模數k分別取10,20,30,40和50，圖2～圖3給出了鄰居規模為10和50情況下的實驗結果。

圖2 鄰居數為10時性能比對圖Fig.2 Performance comparison chart of 10 neighbors

圖3 鄰居數為50時性能比對Fig.3 Performance comparison chart of 50 neighbors

從實驗結果比對中可以看出，基于歸一化方法的協同過濾推薦（NDCF）的MAE值明顯優于其他傳統推薦算法，但是隨著用戶評分矩陣密度的增長NRCF相對于其他方法的MAE值變化不大，分析原因是優于評分矩陣越稀疏，用戶向量的維度就越趨于多樣，這導致NDCF在地密度評分矩陣上相比于其他方法擁有越好的性能。由于現實環境下的協同推薦系統中有效的用戶評分矩陣一般都會非常稀疏。同時我們也觀察到和其他推薦算法一樣，隨著鄰居規模K值的增加MAE值在下降。圖4描述了取評分矩陣密度density=0.1，鄰居規模K從10增大到50對NDCF算法MAE值的影響，說明鄰居數越多NDCF的預測精度越好，但是當K值增到到40到50之間時，MAE曲線已經趨于平緩，如果K值進一步增大會逐漸使噪聲鄰居增加，影響預測的準確性。總體來看相對于其他推薦方法，基于歸一化方法的協同過濾推薦方法能夠適應更寬泛的數據稀疏度，評分預測的性能也明顯提高。

4 結束語

針對傳統的協同過濾推薦算法的不足，本文提出了一種基于歸一化方法的協同過濾推薦算法（NDCF），用于解決個性化的項目評分的預測和推薦問題。所提出的NDCF方法中包含了一種新的用戶（項目）相似度計算方法，能夠更加準確地找到相似的鄰居用戶或鄰居項目，進而提高預測及推薦的性能。實驗結果顯示與傳統推薦算法相比，NDCF方法能夠明顯提高評分預測的性能。

圖4 鄰居數對MAE值的影響Fig.4 Influence of neighbor number on MAE value

[1] 李聰，梁昌勇，馬麗．基于領域最近鄰的協同過濾推薦算法[J]．計算機研究與發展，2008,45(9): 1532-1538.LI Cong, LIANG Chang-yong , MA Li. A collaborative filtering recommendation algorithm based on domain nearest neighbor[J]. Journal of Computer Research and Development,2008,45(9): 1532-1538.

[2] 張光衛，康建初，李鶴松．面向場景的協同過濾推薦算法[J].系統仿真學報, 2006，18(22)：595-601.ZHANG Guang-wei, KANG Jian-chu, LI He-song. context based collaborative filtering recommendation algorithm [J].Journal of System Simulation, 2006，18(22)：595-601.

[3] Sun H, Zheng Z，Chen J, et al. NE.CF: A Novel collaborative collaborative filtering method for service recommendatioii[C]//2011 IEEE International Conference on Web Services (ICWS), 2011:702-703.

[4] ZHAO Zhi-Dan , SHANG Ming-Sheng . user-based collaborativefiltering recommendation algorithms on Hadoop[J]. Third International Conference on Knowledge Discovery and Data Mining, 2010:478-481.

[5] Salakhutdinov R, Mnih A, Hinton G. Restricted Boltzmann machines for collaborative filtering[C]// Proceedings of the 24th international conference on Machine learning, 2007: 791-798.

[6]Banerjee S, Ramanathan K. Collaborative filtering on skewed datasets[C]//Proceedings of the 17th international conference on World Wide Web, 2008:1135-1136.

[7] Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and Data Mining, 2008: 426-434.

[8] Sun H, Peng Y, Chen J, et al. A new similarity measure based on adjusted euclidean distance for memory-based collaborative filtering[J]. Journal of Software, 2011, 6(6): 993-1000.