陳小輝,高 燕,劉漢燁
(榆林學(xué)院 信息工程學(xué)院,陜西 榆林 719000)
隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)迅速發(fā)展,越來(lái)越多的人類(lèi)活動(dòng)依賴(lài)于互聯(lián)網(wǎng),人們可以通過(guò)網(wǎng)絡(luò)購(gòu)買(mǎi)各類(lèi)商品,獲取生活資訊,尋求合作和協(xié)助等等,但是面對(duì)海量的互聯(lián)網(wǎng)信息,普通用戶(hù)越來(lái)越難以及時(shí)獲取有效的信息,在這種情況下能夠提供高效的個(gè)性化的信息推薦顯得尤為重要[1]。協(xié)同過(guò)濾推薦算法是目前應(yīng)用最成功的推薦算法之一,在許多領(lǐng)域得到了廣泛的推廣。
協(xié)同過(guò)濾(Collaborative Filtering,CF)是根據(jù)用戶(hù)的興趣愛(ài)好、歷史數(shù)據(jù)尋找與用戶(hù)在這些方面有一定相似性的鄰居,并且根據(jù)鄰居的一些行為或評(píng)價(jià)數(shù)據(jù)對(duì)用戶(hù)進(jìn)行推薦。與基于內(nèi)容的推薦系統(tǒng)不同,協(xié)同過(guò)濾推薦算法僅僅是依據(jù)用戶(hù)對(duì)項(xiàng)目的評(píng)價(jià)尋找評(píng)價(jià)相似的若干鄰居,而忽略數(shù)據(jù)詳細(xì)內(nèi)容,一般也不提取項(xiàng)目的文本特征向量,因?yàn)橐话闱闆r下如果不同用戶(hù)對(duì)一些項(xiàng)目給出的評(píng)價(jià)相近,那么這些用戶(hù)對(duì)其他項(xiàng)目的評(píng)價(jià)也會(huì)相似[2]。協(xié)同過(guò)濾推薦算法一般分為兩類(lèi):基于內(nèi)存的協(xié)同過(guò)濾(Memory-based CF)和基于模型的協(xié)同過(guò)濾(Model-based CF)?;趦?nèi)存的協(xié)同過(guò)濾算法是目前應(yīng)用最廣泛的推薦方法,又可以進(jìn)一步分為基于用戶(hù)的協(xié)同過(guò)濾推薦和基于項(xiàng)目(item)的協(xié)同過(guò)濾推薦以及綜合考慮用戶(hù)和項(xiàng)目的推薦技術(shù)?;谟脩?hù)推薦算法是依據(jù)鄰居用戶(hù)對(duì)某個(gè)項(xiàng)目的評(píng)分來(lái)預(yù)測(cè)當(dāng)前用戶(hù)對(duì)該項(xiàng)目的評(píng)分,基于項(xiàng)目的推薦算法則根據(jù)鄰居項(xiàng)目的評(píng)分值來(lái)預(yù)測(cè)當(dāng)前項(xiàng)目的評(píng)分[3]。
對(duì)于協(xié)同過(guò)濾推薦算法來(lái)說(shuō),核心是計(jì)算用戶(hù)或項(xiàng)目之間的相似度,而在傳統(tǒng)的相似度計(jì)算過(guò)程中,往往不能妥善處理用戶(hù)評(píng)分向量(或項(xiàng)目評(píng)分向量)之間的向量空間長(zhǎng)度差異,而且往往忽略鄰居用戶(hù)共有的評(píng)分項(xiàng)目(或多個(gè)用戶(hù)對(duì)鄰居項(xiàng)目的評(píng)分)的數(shù)值差異或者是嚴(yán)重弱化數(shù)值差異,為了解決這一問(wèn)題,筆者提出了一種基于歸一化方法的協(xié)同過(guò)濾推薦算法(NDCF),該方法在計(jì)算相似度之前首先將用戶(hù)對(duì)每一項(xiàng)目的評(píng)分值歸一化到一個(gè)統(tǒng)一的值域范圍,然后采用基于用戶(hù)的協(xié)同過(guò)濾推薦算法對(duì)歸一化后的不同向量空間中的用戶(hù)向量進(jìn)行相似性度量形成最近鄰居,并產(chǎn)生歸一化的項(xiàng)目評(píng)分預(yù)測(cè),最后再根據(jù)當(dāng)前用戶(hù)在其他項(xiàng)目上的評(píng)分完成項(xiàng)目最終的評(píng)分預(yù)測(cè),并進(jìn)行推薦。
協(xié)同過(guò)濾推薦方法中最流行應(yīng)用最為廣泛的是基于內(nèi)存的推薦算法,其實(shí)現(xiàn)原理最為直觀。以經(jīng)典的基于用戶(hù)(User-based)的協(xié)同過(guò)濾推薦算法為例,它的基本思路是通過(guò)尋找與當(dāng)前用戶(hù)相似度最高的k個(gè)鄰居,然后依據(jù)鄰居對(duì)某個(gè)項(xiàng)目的評(píng)分來(lái)預(yù)測(cè)當(dāng)前用戶(hù)對(duì)該項(xiàng)目的評(píng)分[4]。這種推薦算法可分為3個(gè)實(shí)現(xiàn)步驟:數(shù)據(jù)定義、用戶(hù)相似度計(jì)算和項(xiàng)目評(píng)分預(yù)測(cè)與推薦。
數(shù)據(jù)定義實(shí)際就是定義用戶(hù)評(píng)分矩陣R,R是一個(gè)n*m的矩陣,n和m分別代表矩陣中的用戶(hù)數(shù)和項(xiàng)目數(shù)。矩陣中的元素值代表用戶(hù)對(duì)項(xiàng)目的評(píng)價(jià)值,包括顯式評(píng)分和隱式評(píng)分兩種,顯式評(píng)分一般指用戶(hù)直接對(duì)項(xiàng)目的評(píng)價(jià)值,隱式評(píng)分則是根據(jù)用戶(hù)的瀏覽行為如瀏覽頻率、時(shí)間、購(gòu)買(mǎi)等間接推測(cè)出的數(shù)值[5]。矩陣的用戶(hù)向量(水平向量)代表特定用戶(hù)對(duì)項(xiàng)目的評(píng)價(jià)值,項(xiàng)目向量(垂直向量)代表某個(gè)具體項(xiàng)目得到的用戶(hù)的評(píng)價(jià)值。如果存在用戶(hù)ux對(duì)項(xiàng)目iy的評(píng)分rxy,則評(píng)分矩陣R中有R[x,y] = rxy,用戶(hù)評(píng)分矩陣R如式(1)所示。
協(xié)同過(guò)濾推薦本質(zhì)是基于近鄰的搜索方法,其實(shí)現(xiàn)核心是對(duì)用戶(hù)或項(xiàng)目間的相似性的度量。常用的計(jì)算相似性方法主要有向量空間相似性度量方法(VSS)和皮爾森相似性度量方法(PCC)兩種。向量空間相似性度量方法是把用戶(hù)對(duì)項(xiàng)目的評(píng)分看作是一個(gè)n維向量,用戶(hù)間的相似性是通過(guò)計(jì)算兩個(gè)用戶(hù)向量之間的余弦?jiàn)A角來(lái)決定[6]。用戶(hù)u和v之間的相似度SIM(u, v)計(jì)算如式(2)所示,式中Iuv表示用戶(hù)u和用戶(hù)v共同評(píng)分的項(xiàng)目集合。
皮爾森相似性度量方法是用來(lái)衡量變量的線性關(guān)系,是在向量空間相似性度量方法的基礎(chǔ)上考慮了用戶(hù)評(píng)分的數(shù)值差異,使用用戶(hù)評(píng)分的偏差作為評(píng)分值參與計(jì)算,用戶(hù)u和v的相似度SIM(u, v)計(jì)算如式(3)所示,其中代表用戶(hù)u和用戶(hù)v對(duì)各自已評(píng)分項(xiàng)目的平均評(píng)分,Iuv代表用戶(hù)u與用戶(hù)v共同評(píng)分項(xiàng)目的集合。
使用式(2)或式(3)計(jì)算得到任意兩兩用戶(hù)之間的相似值以后,對(duì)于特定的目標(biāo)用戶(hù),可以得到與其相似度最大的N個(gè)鄰居用戶(hù),需要進(jìn)行預(yù)測(cè)的目標(biāo)用戶(hù)的某一未評(píng)分項(xiàng)目,可以按照一定的計(jì)算方法根據(jù)這些鄰居對(duì)該項(xiàng)目的評(píng)分來(lái)得到,為提高預(yù)測(cè)準(zhǔn)確度需要考慮到不同用戶(hù)的評(píng)分尺度的不同,計(jì)算時(shí)候需要考慮用戶(hù)對(duì)所有項(xiàng)目的平均評(píng)分,可利用公式(4)進(jìn)行評(píng)分的預(yù)測(cè),式中 表示用戶(hù)u對(duì)項(xiàng)目i的評(píng)分用戶(hù)u和用戶(hù)v對(duì)各自已評(píng)分項(xiàng)目的平均評(píng)分,N(u)代表目標(biāo)用戶(hù)u的鄰居用戶(hù)集。在計(jì)算得到當(dāng)前用戶(hù)對(duì)于未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分后,可以根據(jù)評(píng)分值對(duì)這些未評(píng)分項(xiàng)目排序,然后選擇評(píng)分最高的若干項(xiàng)目進(jìn)行推薦。
傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾推薦因?yàn)槠渌惴ê?jiǎn)單實(shí)用在較多領(lǐng)域得到了應(yīng)用,但是仍然存在較多問(wèn)題。特別是在相似度計(jì)算過(guò)程中,VSS算法和PCC算法都是基于用戶(hù)對(duì)項(xiàng)目評(píng)價(jià)的數(shù)值進(jìn)行直接統(tǒng)計(jì)去計(jì)算相似度,而沒(méi)有考慮用戶(hù)向量的差異與評(píng)分的數(shù)值大小[7]。例如圖1,對(duì)于一個(gè)簡(jiǎn)單的用戶(hù)評(píng)價(jià)矩陣,它包含5個(gè)用戶(hù)和5個(gè)評(píng)分項(xiàng)目,用戶(hù)對(duì)每一個(gè)項(xiàng)目的評(píng)分值在1和6之間。
圖1 用戶(hù)項(xiàng)目評(píng)分矩陣Fig.1 Scoring matrix of users and items
如果要預(yù)測(cè)用戶(hù)u2對(duì)于項(xiàng)目i5的評(píng)分,采用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ù)這個(gè)計(jì)算結(jié)果,u1與u2的相似度比u2與u3的相似度大。而從圖1可以看出u1的評(píng)分區(qū)間是[1,6],而u2和u3的評(píng)分區(qū)間是[1,4],所以u(píng)1與u2的相似度應(yīng)當(dāng)比u2與u3的相似度小,在計(jì)算u2對(duì)i5的評(píng)分時(shí)候應(yīng)當(dāng)參照的鄰居是u3對(duì)i5的評(píng)分而不是u1。這個(gè)矛盾是因?yàn)槠柹惴ú荒軐?duì)處于不同向量空間的用戶(hù)向量的評(píng)分風(fēng)格差異進(jìn)行有效處理,而向量空間算法則只關(guān)注用戶(hù)向量之間的空間夾角,會(huì)忽略用戶(hù)向量間的長(zhǎng)度差異因此有必要尋找更合理有效的,符合實(shí)際情況的相似度計(jì)算方法從而改善推薦性能。
為了克服傳統(tǒng)協(xié)同過(guò)濾推薦算法的不足,筆者嘗試在傳統(tǒng)算法中引入歸一化數(shù)據(jù)處理過(guò)程。在形成用戶(hù)評(píng)分矩陣以后,首先將所有用戶(hù)的項(xiàng)目評(píng)分值歸一到統(tǒng)一的值域空間,該處理過(guò)程假設(shè)任一用戶(hù)向量對(duì)所有項(xiàng)目的評(píng)分不能全部相等。在實(shí)現(xiàn)過(guò)程中,對(duì)于評(píng)分矩陣R的每個(gè)行向量,使用該用戶(hù)的最高評(píng)分值和最低評(píng)分值來(lái)歸一化每一個(gè)項(xiàng)目評(píng)分,最后項(xiàng)目評(píng)分值位于區(qū)間[0,1],歸一化處理后用戶(hù)u對(duì)項(xiàng)目i的評(píng)分 r'ui計(jì)算方法見(jiàn)式(5)。
根據(jù)式(6)計(jì)算得到的Sim(u,v)∈[0,1],值越大則用戶(hù)u和用戶(hù)v越相似,當(dāng)?shù)扔?時(shí)表示兩個(gè)用戶(hù)完全不同,取1時(shí)表示兩個(gè)用戶(hù)相同。對(duì)于圖1中用戶(hù)評(píng)分矩陣數(shù)據(jù)計(jì)算可得Sim(u1,u2)和Sim(u2,u3)的值分別為0.791 5和0.855 7,則該相似性結(jié)果與事實(shí)相符。特殊情況當(dāng)某個(gè)用戶(hù)對(duì)所有項(xiàng)目的評(píng)分都完全一樣的時(shí)候,會(huì)出現(xiàn)零除數(shù)的情況,但是由于所有的項(xiàng)目會(huì)涉及到推薦系統(tǒng)的各種商品、服務(wù),有效用戶(hù)的評(píng)分不會(huì)全部相同,所以可以忽略該情況。
為度量被評(píng)分的項(xiàng)目之間的相似性,可通過(guò)對(duì)原始評(píng)分矩陣R的每個(gè)項(xiàng)目的所有評(píng)分值(每一列)進(jìn)行歸一化處理,同樣歸一處理后矩陣中每列的值都在區(qū)間[0,1]上,式(7)給出了度量項(xiàng)目i和j之間相似度Sim(i,j)的計(jì)算方法,式中Uij表示對(duì)項(xiàng)目i和項(xiàng)目j都做出了評(píng)價(jià)的用戶(hù)集合,|Uij|表示集合中用戶(hù)的個(gè)數(shù),rimin和rimax表示用戶(hù)對(duì)項(xiàng)目i的最小和最大評(píng)分值,rjmin和rjmax表示用戶(hù)對(duì)項(xiàng)目j的最小和最大評(píng)分值。
特殊情況當(dāng)所有用戶(hù)對(duì)某個(gè)項(xiàng)目的評(píng)分都完全一樣的時(shí)候,會(huì)出現(xiàn)零除數(shù)的情況,但是由于對(duì)單個(gè)項(xiàng)目的評(píng)分會(huì)涉及到推薦系統(tǒng)的各類(lèi)用戶(hù),評(píng)分在現(xiàn)實(shí)情況下不會(huì)全部相同,所以可以忽略該情況。
基于2.2節(jié)提出的相似性度量算法,本節(jié)給出一種新的基于內(nèi)存的協(xié)同過(guò)濾方法,當(dāng)需要預(yù)測(cè)用戶(hù)u對(duì)項(xiàng)目i的未知評(píng)分值時(shí),該方法會(huì)根據(jù)用戶(hù)的原始評(píng)分尺度來(lái)進(jìn)行預(yù)測(cè)。在基于用戶(hù)的項(xiàng)目評(píng)分值預(yù)測(cè)中用戶(hù)u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分可以通過(guò)式(8)計(jì)算,式中U表示與用戶(hù)u相似度最高的同時(shí)對(duì)項(xiàng)目i進(jìn)行了評(píng)分的k個(gè)用戶(hù)的集合。
為了驗(yàn)證算法的有效性,采用Group Lens研究小組提供的Movielens 電影評(píng)分公開(kāi)數(shù)據(jù)集(http://www.grouplens.org)對(duì)算法進(jìn)行驗(yàn)證和評(píng)估。該數(shù)據(jù)集采集于一個(gè)電影推薦網(wǎng)站,包含了943位用戶(hù)對(duì)1 682部電影的100 000個(gè)評(píng)分,用戶(hù)評(píng)分矩陣的稀疏度為93.7%。實(shí)驗(yàn)中從原始評(píng)分矩陣中隨機(jī)修改一部分評(píng)分項(xiàng)目,形成了10個(gè)數(shù)據(jù)密度分別為2%,4%,6%,8%,10%,12%,14%,16%,18%和20%的稀疏矩陣,使用稀疏度較高(數(shù)據(jù)密度較低)的原因是實(shí)際中的評(píng)分矩陣通常非常稀疏。
為了檢驗(yàn)項(xiàng)目評(píng)分的預(yù)測(cè)準(zhǔn)確度,使用被廣泛采用平均絕對(duì)誤差(Mean Absolute Error,MAE)來(lái)衡量預(yù)測(cè)的有效性。MAE是預(yù)測(cè)值與真實(shí)值之間的絕對(duì)偏差的平均值,式(10)給出了MAE的計(jì)算方法,式中rui是指用戶(hù)u對(duì)項(xiàng)目i的實(shí)際是指預(yù)測(cè)得到的用戶(hù)u對(duì)項(xiàng)目i的評(píng)分值,N是被預(yù)測(cè)值的數(shù)量,MAE值越低,則說(shuō)明預(yù)測(cè)的準(zhǔn)確度越高。
為了比對(duì)歸一化處理協(xié)同過(guò)濾算法的有效性,采用了5種傳統(tǒng)協(xié)同過(guò)濾方法與基于用戶(hù)的歸一化協(xié)同過(guò)濾推薦算法(NDCF)進(jìn)行了對(duì)比實(shí)驗(yàn):基于用戶(hù)的平均數(shù)法(UMEAN),該方法在計(jì)算未知項(xiàng)目的評(píng)分時(shí),使用用戶(hù)對(duì)所有項(xiàng)目的評(píng)分均值表示;基于項(xiàng)目的平均數(shù)法(IMEAN),該方法在計(jì)算未知用戶(hù)評(píng)分時(shí),使用所有對(duì)當(dāng)前項(xiàng)目評(píng)分用戶(hù)的評(píng)分均值;使用PCC的基于用戶(hù)的協(xié)同過(guò)濾(UPCC);使用PCC的基于項(xiàng)目的協(xié)同過(guò)濾(IPCC);混合使用UPCC和IPCC實(shí)現(xiàn)的一種協(xié)同過(guò)濾方法(WSRec)。實(shí)驗(yàn)采用五折交叉驗(yàn)證方法,對(duì)于10個(gè)稀疏矩陣中的每個(gè)評(píng)分矩陣,將用戶(hù)評(píng)分記錄按照4 : 1的比例劃分為訓(xùn)練集和測(cè)試集,而且分別進(jìn)行了5次劃分,分別依據(jù)訓(xùn)練集中數(shù)據(jù)來(lái)預(yù)測(cè)計(jì)算測(cè)試集中數(shù)據(jù)并計(jì)算相應(yīng)MAE值,最后統(tǒng)計(jì)得出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時(shí)性能比對(duì)圖Fig.2 Performance comparison chart of 10 neighbors
圖3 鄰居數(shù)為50時(shí)性能比對(duì)Fig.3 Performance comparison chart of 50 neighbors
從實(shí)驗(yàn)結(jié)果比對(duì)中可以看出,基于歸一化方法的協(xié)同過(guò)濾推薦(NDCF)的MAE值明顯優(yōu)于其他傳統(tǒng)推薦算法,但是隨著用戶(hù)評(píng)分矩陣密度的增長(zhǎng)NRCF相對(duì)于其他方法的MAE值變化不大,分析原因是優(yōu)于評(píng)分矩陣越稀疏,用戶(hù)向量的維度就越趨于多樣,這導(dǎo)致NDCF在地密度評(píng)分矩陣上相比于其他方法擁有越好的性能。由于現(xiàn)實(shí)環(huán)境下的協(xié)同推薦系統(tǒng)中有效的用戶(hù)評(píng)分矩陣一般都會(huì)非常稀疏。同時(shí)我們也觀察到和其他推薦算法一樣,隨著鄰居規(guī)模K值的增加MAE值在下降。圖4描述了取評(píng)分矩陣密度density=0.1,鄰居規(guī)模K從10增大到50對(duì)NDCF算法MAE值的影響,說(shuō)明鄰居數(shù)越多NDCF的預(yù)測(cè)精度越好,但是當(dāng)K值增到到40到50之間時(shí),MAE曲線已經(jīng)趨于平緩,如果K值進(jìn)一步增大會(huì)逐漸使噪聲鄰居增加,影響預(yù)測(cè)的準(zhǔn)確性。總體來(lái)看相對(duì)于其他推薦方法,基于歸一化方法的協(xié)同過(guò)濾推薦方法能夠適應(yīng)更寬泛的數(shù)據(jù)稀疏度,評(píng)分預(yù)測(cè)的性能也明顯提高。
針對(duì)傳統(tǒng)的協(xié)同過(guò)濾推薦算法的不足,本文提出了一種基于歸一化方法的協(xié)同過(guò)濾推薦算法(NDCF),用于解決個(gè)性化的項(xiàng)目評(píng)分的預(yù)測(cè)和推薦問(wèn)題。所提出的NDCF方法中包含了一種新的用戶(hù)(項(xiàng)目)相似度計(jì)算方法,能夠更加準(zhǔn)確地找到相似的鄰居用戶(hù)或鄰居項(xiàng)目,進(jìn)而提高預(yù)測(cè)及推薦的性能。實(shí)驗(yàn)結(jié)果顯示與傳統(tǒng)推薦算法相比,NDCF方法能夠明顯提高評(píng)分預(yù)測(cè)的性能。
圖4 鄰居數(shù)對(duì)MAE值的影響Fig.4 Influence of neighbor number on MAE value
[1] 李聰,梁昌勇,馬麗.基于領(lǐng)域最近鄰的協(xié)同過(guò)濾推薦算法[J].計(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),康建初,李鶴松.面向場(chǎng)景的協(xié)同過(guò)濾推薦算法[J].系統(tǒng)仿真學(xué)報(bào), 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.