任彩霞
(北京郵電大學(xué)理學(xué)院,北京 100876)
一種改進(jìn)的緩解推薦系統(tǒng)物品冷啟動(dòng)的方法
任彩霞
(北京郵電大學(xué)理學(xué)院,北京100876)
信息爆炸的時(shí)代,推薦系統(tǒng)越來(lái)越成為網(wǎng)民的依賴,它有效的解決了信息過(guò)載的問(wèn)題,但是卻沒(méi)有解決推薦系統(tǒng)的冷啟動(dòng)問(wèn)題。為了緩解新項(xiàng)目的冷啟動(dòng)問(wèn)題,結(jié)合基于物品的協(xié)同過(guò)濾算法與決策樹(shù)思想,這篇文章在孫等人的算法上做了改進(jìn),把算法的第一步替換為用顯示的信任網(wǎng)絡(luò)對(duì)用戶做劃分的方法。顯示的信任網(wǎng)絡(luò),可以對(duì)用戶做了更細(xì)致的分類,把信任網(wǎng)絡(luò)添加到算法中,原算法便被改進(jìn)為基于信任網(wǎng)絡(luò)的推薦系統(tǒng)。改進(jìn)后的算法不僅滿足了一大部分用戶的偏好與需求,而且使得系統(tǒng)用戶更加依賴推薦系統(tǒng)。實(shí)驗(yàn)表明,利用顯示的信任網(wǎng)絡(luò)對(duì)新項(xiàng)目的推薦,其推薦結(jié)果的準(zhǔn)確性比原算法高,推薦的結(jié)果也更加穩(wěn)定。在評(píng)分個(gè)數(shù)分別為0,5,10的情況下,平均絕對(duì)誤差比原算法的低了16.7%,21.6%,31.7%。
推薦系統(tǒng);協(xié)同過(guò)濾;決策樹(shù);信任網(wǎng)絡(luò);物品冷啟動(dòng)
本文著錄格式:任彩霞. 一種改進(jìn)的緩解推薦系統(tǒng)物品冷啟動(dòng)的方法. 軟件,2016,37(8):11-15
隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展,人們逐漸從信息匱乏的時(shí)代都入了信息過(guò)載的時(shí)代。對(duì)于消費(fèi)者來(lái)說(shuō),如何從大量信息中提取到自己的興趣愛(ài)好是一件非常困難的事情,對(duì)于商家來(lái)說(shuō),如何給用戶推薦用戶需要的物品,從而提高自己的利潤(rùn),也是一件困難的事情。為了處理兩者的并行困難,推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)的出現(xiàn),既方便了用戶挖掘?qū)ψ约河袃r(jià)值的信息,又使得推薦系統(tǒng)的提供者挖掘了自己的商業(yè)價(jià)值,從而實(shí)現(xiàn)了用戶與商家的雙贏。推薦系統(tǒng)的概念提出之后,在web端、大型電子商務(wù)網(wǎng)站[1]上得到了充分的應(yīng)用。亞馬遜前科學(xué)家Greg Linden在他的博客里曾經(jīng)說(shuō)過(guò),亞馬遜每年的收入至少有35%的銷售來(lái)自推薦系統(tǒng)。而使得亞馬遜如此成功的原因,還有一個(gè)是利用精巧的算法充分挖掘了用戶的潛質(zhì)[1,2,3,4]。推薦系統(tǒng)的算法,總體來(lái)說(shuō)有四大類:協(xié)同過(guò)濾、基于內(nèi)容的推薦、基于知識(shí)的推薦與混合推薦算法,其中,協(xié)同過(guò)濾推薦是用處最廣的算法[5,6]。
推薦系統(tǒng)需要根據(jù)用戶的歷史行為和興趣預(yù)測(cè)用戶未來(lái)的行為和興趣,因此大量的用戶行為數(shù)據(jù)就稱為推薦系統(tǒng)的重要組成部分和先決條件[11]。但是在實(shí)際應(yīng)用中,用戶一只會(huì)評(píng)價(jià)(或購(gòu)買)少數(shù)物品,所以可使用的評(píng)分?jǐn)?shù)據(jù)就很少,這樣就會(huì)使得評(píng)分矩陣非常稀疏。另一種極端情況是,物品是新添加到推薦系統(tǒng)中的,這樣除了物品本身的屬性,不會(huì)再有任何關(guān)于物品的評(píng)分信息,這樣就使得推薦系統(tǒng)很難把一個(gè)新物品推薦給可能會(huì)喜歡他的用戶;或者用戶是在一個(gè)網(wǎng)站中新注冊(cè)的,推薦系統(tǒng)沒(méi)有任何關(guān)于該新用戶的信息,除非從一開(kāi)始推薦系統(tǒng)就引導(dǎo)該用戶選擇了自己喜歡的標(biāo)簽并且記錄了下來(lái)[8]。以上說(shuō)的這幾種情況都屬于推薦系統(tǒng)的冷啟動(dòng)問(wèn)題,也被稱為數(shù)據(jù)稀疏問(wèn)題。到現(xiàn)在為止,沒(méi)有一個(gè)真正可以解決冷啟動(dòng)的算法,學(xué)者們只能盡力去緩解它[2]。
在孫等人[7]的論文中,該算法在一定程度上緩解了推薦系統(tǒng)中新物品或者評(píng)分個(gè)數(shù)為極少數(shù)物品的冷啟動(dòng)問(wèn)題。算法的思想為:首先基于奇異值分解的方法分解了該矩陣,并且對(duì)分解過(guò)的矩陣做物品聚類,如此聚類的結(jié)果被假定為相似的物品被相似的用戶所喜歡;其次,利用物品本身的內(nèi)容信息和聚類結(jié)果構(gòu)造出決策樹(shù),最后再以此推斷新物品和聚類物品之間的相似程度,從而決定是否可以把該物品推薦給未對(duì)該物品評(píng)分過(guò)的用戶。該算法一共有四個(gè)步驟:聚類,構(gòu)建決策樹(shù),物品聚類與評(píng)分預(yù)測(cè)。
決策樹(shù)的形成,是利用了信息熵[7,9]的原理。該原理是把最不確定的因素排在樹(shù)根的位置。相同的計(jì)算方式,把不確定因素低的放在子節(jié)點(diǎn)的位置,如此計(jì)算便得到葉子節(jié)點(diǎn)與固有節(jié)點(diǎn)。此時(shí),決策樹(shù)已經(jīng)形成,所有的葉子節(jié)點(diǎn)與固有節(jié)點(diǎn)都對(duì)應(yīng)一類興趣愛(ài)好相似的用戶以及符合該類用戶喜好的物品。決策樹(shù)形成之后,孫等人用了新的方式計(jì)算了物品的最后得分,傳統(tǒng)的預(yù)測(cè)評(píng)分,在數(shù)據(jù)構(gòu)成規(guī)模時(shí)推薦效果時(shí)很明顯的。而在冷啟動(dòng)物品中,這些卻不能作為評(píng)判標(biāo)準(zhǔn)。由此,孫等人采用了加權(quán)的方式,結(jié)合了某一聚類物品中活躍用戶的平均評(píng)分和利用原始方法得到的物品的預(yù)測(cè)評(píng)分,并且用因子β調(diào)節(jié)兩者的權(quán)重,從而消除了極端情況下評(píng)分個(gè)數(shù)過(guò)少的顧慮。
孫等人的算法在一定程度上解決了推薦系統(tǒng)中物品上新的問(wèn)題,相比于隨機(jī)推薦、熱門推薦取得了很好的效果,然而在評(píng)分個(gè)數(shù)增多時(shí),平均絕誤差卻逐漸變大。該問(wèn)題的出現(xiàn)有兩個(gè)原因:1)第一步聚類過(guò)程粗糙,2)用一個(gè)活躍用戶代替一類相似的用戶。從問(wèn)題出發(fā),本篇文章修正了算法的第一步,采用信任的網(wǎng)絡(luò)系統(tǒng)[5,10],把推薦系統(tǒng)中非常相似的用戶劃分為一類,非常相似的用戶喜歡的物品也是相似的,這就給所有的用戶做了更細(xì)致的劃分。在基于信任的網(wǎng)絡(luò)中,我們假設(shè)信息是對(duì)稱的,那么重新聚類得到的用戶之間相似度很高,這樣解決了只用活躍用戶的平均評(píng)分帶來(lái)的喜好偏差問(wèn)題,推薦系統(tǒng)可以給每一個(gè)用戶推薦他喜歡的物品。實(shí)驗(yàn)結(jié)果表明,本篇文章提出的算法是有效的。
本篇文章安排如下:第1部分介紹本篇文章完整的算法,第二部分介紹算法的仿真實(shí)驗(yàn),第三部分是對(duì)本文的總結(jié)。
2.1基于物品的協(xié)同過(guò)濾推薦
傳統(tǒng)的基于物品的協(xié)同過(guò)濾,是假定一個(gè)推薦系統(tǒng)中有兩個(gè)集合,用戶集合U與物品集合I,U=每一個(gè)用戶都有評(píng)分的物品,大部分的物品都被用戶評(píng)分過(guò),把物品與用戶一一對(duì)應(yīng),便得到物品-用戶()IU-矩陣,如下表:
表1 I-U矩陣Tab.1 I-U matrix
基于物品的協(xié)同過(guò)濾算法分為兩步,第一步是計(jì)算得出物品與物品之間的相似度,該相似度被稱為“權(quán)重”。計(jì)算相似度的方法有多種,本文采用的是Pearson相似度度量,該方法的優(yōu)勢(shì)在于計(jì)算相似度之前,消除由于平均值不同而造成的差異,相應(yīng)的,相似度度量的取值在-1和1之間。Pearson方法的計(jì)算方式如下:
其中,sim( a, b)是物品之間的相似度,ru,a代表用戶u對(duì)物品a的評(píng)分,ru,b代表用戶u對(duì)物品b的評(píng)分,代表用戶對(duì)評(píng)分物品的平均評(píng)分。
該方法的第二步是利用第一步得出的權(quán)重通過(guò)加權(quán)計(jì)算得出用戶對(duì)未評(píng)分過(guò)物品的預(yù)測(cè)評(píng)分,計(jì)算方式如下:
其中,pred( u, p)是用戶u對(duì)物品p的預(yù)測(cè)評(píng)分,sim( i, p)代表已評(píng)分物品與預(yù)測(cè)物品之間的相似度。
2.2用戶的相似度
給定評(píng)分矩陣IU-,用戶m和用戶n之間的相似度與基于物品的相似度計(jì)算相似,公式如下:
本文的算法是利用顯示的信任網(wǎng)絡(luò)做了處理,把特別相似的用戶歸為一類,從而給該類相似的用戶推薦相似的物品。一旦有新物品,用決策樹(shù)過(guò)濾之后,該新物品會(huì)被分配到屬于它自己的類別當(dāng)中,該類別對(duì)應(yīng)一類喜好很相似的用戶,從而推薦的結(jié)果會(huì)更準(zhǔn)確。在基于信任網(wǎng)絡(luò)的推薦系統(tǒng)中,假定sim( a, b)≥0.8(該閾值是在相似度處于0-1之間時(shí)計(jì)算所得),用戶是特別相似的,那么由此可以對(duì)已經(jīng)有的相似矩陣用0-1來(lái)處理,假定信任度量因子為t,那么:
由此,便把所有的用戶按照相似程度重新做了劃分。當(dāng)相似度大于0.6,信任度為1,反之,信任度為0。利用顯示網(wǎng)絡(luò)重新劃分,可以構(gòu)成以每一個(gè)用戶為中心,與該用戶相似度大于等于0.6為半徑的用戶的一類群體。如果給該用戶推薦喜歡的物品,那么該類用戶由于相似度比較大,獲得的同樣推薦結(jié)果準(zhǔn)確度會(huì)更高。
2.3算法模型
1)對(duì)用戶群體的劃分。用顯示的信任網(wǎng)絡(luò)把用戶群體做一個(gè)劃分,非常相似的用戶為一類?;谏鲜?-1化處理,該步驟把以一個(gè)用戶為中心,信任因子為1的用戶作為一類。由此聚類的每一類用戶具有非常相似的喜好。
2)決策樹(shù)的建立。某一個(gè)決策樹(shù)的模型如圖1所示:
在數(shù)據(jù)集中,我們利用電影的種類作為屬性,結(jié)合由第一步計(jì)算得出的用戶的種類,構(gòu)建了決策樹(shù)。決策樹(shù)每一個(gè)節(jié)點(diǎn)的構(gòu)建,利用信息熵的原理,選擇最不確定的因素作為根節(jié)點(diǎn)。子節(jié)點(diǎn)的計(jì)算方式與根節(jié)點(diǎn)的計(jì)算方式相同。由此得到所有特征的不同的信息熵,從而構(gòu)建成了決策樹(shù)。固有節(jié)點(diǎn)和根節(jié)點(diǎn)則代表某一類物品(電影),該類電影擁有從該決策樹(shù)根到此節(jié)點(diǎn)的所有種類特征。每一類物品對(duì)應(yīng)一類喜歡該類物品的用戶,這樣,就建立起來(lái)物品特征,物品分類與喜好用戶之間的對(duì)應(yīng)關(guān)系。
3)新的物品的分類。由上述兩步計(jì)算得到結(jié)果之后,新的物品就可以利用事先定好的決策樹(shù)尋找到該類物品的分類。找到該分類之后,可以對(duì)應(yīng)到喜歡他的一類用戶,那么推薦系統(tǒng)便可以選擇給該類用戶推薦該新物品。
4)由于系統(tǒng)解決的是物品的冷啟動(dòng)問(wèn)題,難免會(huì)遇到極端的情況,比如物品的評(píng)分個(gè)數(shù)為0。這種情況下,系統(tǒng)是無(wú)法利用用戶的行為給新的物品做預(yù)測(cè)評(píng)分的,所以我們?cè)陬A(yù)測(cè)方面做了修正,計(jì)算的方法如下:
圖1 決策樹(shù)模型Fig.1 example of a decision tree
3.1數(shù)據(jù)集和度量
我們使用的實(shí)驗(yàn)數(shù)據(jù)集是來(lái)自Movielens,該網(wǎng)站存儲(chǔ)了大量的電影信息,包括電影的類別,注冊(cè)用戶的個(gè)數(shù)以及用戶對(duì)他看過(guò)電影的評(píng)分。電影的類別包括19種類型(動(dòng)作、冒險(xiǎn)、動(dòng)畫、喜劇等),網(wǎng)站用戶數(shù)量為943,且用戶對(duì)電影的評(píng)分都是1-5之間。實(shí)驗(yàn)數(shù)據(jù)集被分為訓(xùn)練集和測(cè)試集,我們隨機(jī)選取了95%的訓(xùn)練集與5%的測(cè)試集,以保證選取的物品是新的物品或者評(píng)分個(gè)數(shù)小于等于10個(gè)。我們隨機(jī)劃分?jǐn)?shù)據(jù)集,把算法重復(fù)實(shí)驗(yàn)了100次。我們利用平均絕對(duì)誤差(MAE)來(lái)度量試驗(yàn)結(jié)果,MAE越小,說(shuō)明實(shí)驗(yàn)的準(zhǔn)確度越高。MAE的計(jì)算方式如下:
其中n是活躍代表用戶的所有評(píng)分的個(gè)數(shù),,aip是算法得出的預(yù)測(cè)評(píng)分,,air是物品的實(shí)際評(píng)分。MAE越小,說(shuō)明實(shí)驗(yàn)的準(zhǔn)確度越高。
3.2實(shí)驗(yàn)結(jié)果
在孫等人的實(shí)驗(yàn)結(jié)果中,可以看出:隨著β的變化,平均絕對(duì)誤差(MAE)也在改變,在給定評(píng)分個(gè)數(shù)為0的情況下,MAE不斷減小,說(shuō)明方法起到了一定的效果;當(dāng)評(píng)分個(gè)數(shù)為5的時(shí)候,雖然MAE的整體趨勢(shì)也在減小,可到了0.8β=之后,MAE卻不斷上升;當(dāng)評(píng)分個(gè)數(shù)為10的時(shí)候,MAE整體是漸漸增長(zhǎng)的,說(shuō)明方法在評(píng)分個(gè)數(shù)不斷增加的時(shí)候,算法出現(xiàn)了一定的問(wèn)題。原因是在最終評(píng)分當(dāng)中,相似的一類用戶只采用了一個(gè)活躍用戶的平均評(píng)分,這一類用戶的相似度不高,所以不可以用該用戶完全代表其他的用戶。本篇文章的算法是保證相似度很高的情況下,用一個(gè)中心用戶代替與之相似的用戶,這樣給出的推薦會(huì)更為準(zhǔn)確。
改進(jìn)算法是為了在原算法的基礎(chǔ)上更進(jìn)一步的緩解物品的冷啟動(dòng)問(wèn)題。由于原有的算法出現(xiàn)的問(wèn)題有(1)聚類過(guò)程粗糙(2)用一個(gè)活躍用戶代替了一類用戶,我們把相似度滿足一定條件的用戶聚為一類,解決了聚類過(guò)程粗糙的問(wèn)題,而由于條件苛刻,滿足條件的一類用戶很少,該類用戶的中心用戶作為活躍用戶,解決了第二個(gè)問(wèn)題。以下實(shí)驗(yàn)數(shù)據(jù)證明了在評(píng)分個(gè)數(shù)為0,5,10的情況下,改進(jìn)后的算法得到的結(jié)果。
1)評(píng)分個(gè)數(shù)為0的MAE比較。如圖2所示,評(píng)分個(gè)數(shù)為0時(shí),說(shuō)明物品是全新的,系統(tǒng)內(nèi)除了該物品本身的信息,沒(méi)有任何用戶對(duì)它的評(píng)價(jià)。推薦系統(tǒng)唯一能做的就是利用該物品的內(nèi)容信息來(lái)直接做判斷。改進(jìn)后的算法和孫等人的算法相比,誤差降低了16.7%。
圖2 評(píng)分個(gè)數(shù)為0的比較Fig.2 given 0 rating
2)評(píng)分個(gè)數(shù)為5的MAE比較。如圖3所示,評(píng)分個(gè)數(shù)為5時(shí),說(shuō)明已經(jīng)有一些用戶對(duì)某一個(gè)冷啟動(dòng)的物品做了評(píng)價(jià)。由于用戶分類比較精確,所以在預(yù)測(cè)評(píng)分時(shí),活躍用戶的評(píng)分便消除了一部分由于用戶評(píng)價(jià)差異造成的評(píng)分不準(zhǔn)確性,改進(jìn)后的評(píng)分絕對(duì)誤差比原算法少了26.7%。
圖3 評(píng)分個(gè)數(shù)為5的比較Fig.3 given 5 rating
3)評(píng)分個(gè)數(shù)為10的MAE比較。如圖4所示,評(píng)分個(gè)數(shù)為10時(shí),進(jìn)一步發(fā)揮了加入信任的網(wǎng)絡(luò)時(shí)的優(yōu)勢(shì),因?yàn)橛脩舴诸惖木珳?zhǔn)性,所以用戶對(duì)物品的評(píng)分更加準(zhǔn)確,結(jié)合物品的分類,我們可以更加準(zhǔn)確的推測(cè)到用戶喜歡的物品。改進(jìn)后的評(píng)分絕對(duì)誤差比原算法降低了31.6%,比評(píng)分個(gè)數(shù)為5時(shí)更加準(zhǔn)確。
圖4 評(píng)分個(gè)數(shù)為10的比較Fig.4 given 10 rating
從實(shí)驗(yàn)數(shù)據(jù)可以看出,在評(píng)分個(gè)數(shù)為不同數(shù)值的情況下,總體的MAE程遞減趨勢(shì),而且當(dāng)調(diào)節(jié)因子β上升時(shí),MAE并無(wú)上升。在評(píng)分個(gè)數(shù)為0的情況下,是一直呈現(xiàn)遞減趨勢(shì),遞減了16.7%;在評(píng)分個(gè)數(shù)為5和10的情況下,遞減速度減緩,但并無(wú)出現(xiàn)突然增高的情況,遞減幅度分別為26.7%與31.6%,說(shuō)明該方法是有效的。按照常理來(lái)推斷,在評(píng)分個(gè)數(shù)越來(lái)越多的情況下,得到的結(jié)果也必然會(huì)更加準(zhǔn)確。
本篇文章是基于孫等人的算法上做了一些修正,改變了第一步聚類的思路,并且經(jīng)實(shí)驗(yàn)證明改進(jìn)后的算法有效。結(jié)合使用了基于信任的網(wǎng)絡(luò)與決策樹(shù),平均絕對(duì)誤差進(jìn)一步減小。采用了基于信任網(wǎng)絡(luò)的算法,雖然用戶類別的劃分使得推薦結(jié)果更加準(zhǔn)確,卻帶來(lái)了一定的問(wèn)題。滿足條件的用戶是少數(shù)的,這就使得劃分的類別偏多,給推薦系統(tǒng)的內(nèi)存與計(jì)算帶來(lái)了性能問(wèn)題。用戶的喜好在不同的時(shí)間段也可能是有區(qū)別的,這就需要推薦系統(tǒng)在一段時(shí)間后更新用戶之間的相似度,物品之間的相似度,從而提高推薦的準(zhǔn)確度。關(guān)于此類型的問(wèn)題,在后期的研究中我們會(huì)進(jìn)一步研究。
本篇文章由國(guó)家自然科學(xué)基金委員會(huì)(編號(hào):61300181, 61502044)贊助與支持。
[1] 張華. 基于數(shù)據(jù)挖掘技術(shù)的電子商務(wù)旅游線路推薦系統(tǒng)[J].軟件, 2013, 34(3): 57-58.
[2] 程陳. 大數(shù)據(jù)挖掘分析[J]. 軟件, 2014, 35(4): 130-131.
[3] 卓廣平. 數(shù)據(jù)挖掘開(kāi)發(fā)及應(yīng)用研究[J]. 軟件, 2015, 36(5): 81-83.
[4] 史尤昭. 數(shù)據(jù)挖掘技術(shù)研究與應(yīng)用[J]. 軟件, 2015, 36(11): 38-42.
[5] Jannach Dietmar. Recommender Systems: An Introduction [M]. 1st edition Cambridge, England: CUP, 2010.
[6] V Faridani, MV Jahan, M Jalali. Combining Trust in Collaborative Filtering to Mitigate Data Sparsity and Cold- Start Problems [D]. 4th Internatioal Conference on Computer and Knowledge and Engineering (ICCKE), 2013.
[7] SUN D T, LUO Z G, ZHANG F H. A Novel Approach for Collaborative Filtering to Alleviate the New Item Cold-Start Problem [A]. 11th International Symposium on Comunications and Information Technologies(ISCIT), 2011: 402-406.
[8] S KIM, SM Choi, YS Han, et al. Analyzing Item Features for Cold-Start Problems in Recommendation Systems [D]. Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), 2014.
[9] SUN D T, LUO Z G, ZHANG F H. Survey of Cold- start Problem in Collaborative Filtering Recommender System [J]. Computer and Modernization, 2012, 1(201): 59-63.
[10] XIANG Liang. Recommender Systems: In Action [M]. 1st ed. Beijing, China: Posts and Telecom Press, 2012.
[11] 楊澤民. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[J]. 軟件, 2013, 34(11): 71-72.
Improved Algorithm of Alleviating Item Cold Starting
REN Cai-xia, ZHU Ping
(Beijing University of Posts and Telecommunications School of Science, Beijing 100876, China)
With the information bursting on the internet and the whole world, recommendation system is playing a much more important role on the internet. Recommendation system has solved the overload information, however, it hasn’t solved the cold starting problem yet. In order to alleviate the item cold starting problem, we add an obvious trusted network based on the collaborative filtering and the decision tree. Our experiments have proved that the new item recommendation, which we recommend by the trusting system, is much more accurate compared to the original algorithm. When the rating number is 0, MAE is 16.7% lower than original algorithm. What’s more, the trusted recommendation system, not only satisfied most of the users’ interests, but also makes them rely on it more than before.
Recommendation system; Collaborative filtering; Decision tree; Trusted network; Item cold starting
TP311
A
10.3969/j.issn.1003-6970.2016.08.003
國(guó)家自然科學(xué)基金(61300181, 61502044)
任彩霞(1991-),女,北京郵電大學(xué)碩士研究生,主要研究方向?yàn)閿?shù)據(jù)挖掘。
通訊聯(lián)系人: 任彩霞,碩士研究生,主要研究方向:密碼學(xué)、數(shù)據(jù)挖掘、人工智能.