陳小輝,高 燕,劉漢燁

（榆林學(xué)院 信息工程學(xué)院，陜西 榆林 719000）

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

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

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

1 傳統(tǒng)的協(xié)同過濾推薦原理

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

1.1 數(shù)據(jù)定義

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

1.2 相似度計算

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

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

1.3 項(xiàng)目評分預(yù)測與推薦

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

2 基于歸一化方法的協(xié)同過濾推薦

2.1 傳統(tǒng)協(xié)同過濾推薦算法的不足

傳統(tǒng)的基于內(nèi)存的協(xié)同過濾推薦因?yàn)槠渌惴ê唵螌?shí)用在較多領(lǐng)域得到了應(yīng)用，但是仍然存在較多問題。特別是在相似度計算過程中，VSS算法和PCC算法都是基于用戶對項(xiàng)目評價的數(shù)值進(jìn)行直接統(tǒng)計去計算相似度，而沒有考慮用戶向量的差異與評分的數(shù)值大小[7]。例如圖1，對于一個簡單的用戶評價矩陣，它包含5個用戶和5個評分項(xiàng)目，用戶對每一個項(xiàng)目的評分值在1和6之間。

圖1 用戶項(xiàng)目評分矩陣Fig.1 Scoring matrix of users and items

如果要預(yù)測用戶u2對于項(xiàng)目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)根據(jù)這個計算結(jié)果，u1與u2的相似度比u2與u3的相似度大。而從圖1可以看出u1的評分區(qū)間是[1,6]，而u2和u3的評分區(qū)間是[1,4]，所以u1與u2的相似度應(yīng)當(dāng)比u2與u3的相似度小，在計算u2對i5的評分時候應(yīng)當(dāng)參照的鄰居是u3對i5的評分而不是u1。這個矛盾是因?yàn)槠柹惴ú荒軐μ幱诓煌蛄靠臻g的用戶向量的評分風(fēng)格差異進(jìn)行有效處理，而向量空間算法則只關(guān)注用戶向量之間的空間夾角，會忽略用戶向量間的長度差異因此有必要尋找更合理有效的，符合實(shí)際情況的相似度計算方法從而改善推薦性能。

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

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

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

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

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

2.3 基于歸一化方法的項(xiàng)目評分預(yù)測和推薦

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 評價標(biāo)準(zhǔn)

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

3.3 實(shí)驗(yàn)方案

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

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

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

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

4 結(jié)束語

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

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

[1] 李聰，梁昌勇，馬麗．基于領(lǐng)域最近鄰的協(xié)同過濾推薦算法[J]．計算機(jī)研究與發(fā)展，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] 張光衛(wèi)，康建初，李鶴松．面向場景的協(xié)同過濾推薦算法[J].系統(tǒng)仿真學(xué)報, 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.