姜書浩,張立毅,周 娜
(1.天津大學(xué)電氣自動(dòng)化與信息工程學(xué)院,天津 300072; 2.天津商業(yè)大學(xué)信息工程學(xué)院,天津 300134)
推薦系統(tǒng)在過去的十年中已經(jīng)成為強(qiáng)大的工具,用戶通過它可以根據(jù)自己的偏好瀏覽海量信息[1],同時(shí)有效地提高了使用的滿意度和忠誠度。個(gè)性化推薦系統(tǒng)目的是為用戶推薦可能感興趣的信息或物品(如音樂、電影、書籍等),并且已經(jīng)廣泛地應(yīng)用于電子商務(wù)、社交、新聞以及電子學(xué)習(xí)等領(lǐng)域[2]。
推薦系統(tǒng)最常用的2種方法是基于內(nèi)容的推薦和協(xié)同過濾推薦?;趦?nèi)容推薦根據(jù)用戶已經(jīng)評分的項(xiàng)目內(nèi)容推斷出用戶的個(gè)人偏好信息,并根據(jù)對項(xiàng)目的特征描述和用戶偏好特征向用戶推薦可能感興趣的項(xiàng)目[3],因此基于內(nèi)容的推薦依賴于對項(xiàng)目和用戶的描述性數(shù)據(jù)。而協(xié)同過濾推薦不依賴于項(xiàng)目的顯示特征描述,它根據(jù)與其興趣相似的用戶已評分項(xiàng)目來預(yù)測用戶的偏好。近些年來協(xié)同過濾技術(shù)得到了更加廣泛的應(yīng)用,但是仍然存在稀疏性、可擴(kuò)展性以及過度擬合等問題。
首先,協(xié)同過濾技術(shù)最大的特點(diǎn)在于它僅僅依據(jù)用戶對項(xiàng)目的評分,完全獨(dú)立于所推薦項(xiàng)目的具體類別。所以采用協(xié)同過濾技術(shù)進(jìn)行推薦的項(xiàng)目往往是分值較高的項(xiàng)目,而內(nèi)容可能與用戶期望獲得的推薦大相徑庭。例如,向某個(gè)特定用戶推薦劇情類電影,結(jié)果計(jì)算出k個(gè)評分最相似的電影,但類型可能完全不同。也就是說,協(xié)同過濾技術(shù)中的相似度計(jì)算僅僅依賴于用戶對項(xiàng)目的評分,而預(yù)測項(xiàng)目內(nèi)容可能與已評分項(xiàng)目毫無關(guān)聯(lián)。
其次,傳統(tǒng)的協(xié)同過濾方法假設(shè)用戶偏好是固定不變的,忽略了用戶興趣隨時(shí)間的變化。例如,一位電子商務(wù)專業(yè)的本科生在高中時(shí)對歷史書的評價(jià)很高,但是隨著他進(jìn)入大學(xué)后對歷史書的評價(jià)可能有很大的變化。因此,大多數(shù)研究工作中對新數(shù)據(jù)的分析要比相對陳舊的數(shù)據(jù)分析更為重要[4],當(dāng)然,僅僅考慮最新的數(shù)據(jù)也不能對用戶偏好進(jìn)行完整的描述。
本文主要通過引入項(xiàng)目類別信息來改進(jìn)現(xiàn)有的協(xié)同過濾算法,并根據(jù)時(shí)間為每個(gè)項(xiàng)目評分設(shè)定不同的權(quán)重值,反映用戶偏好隨時(shí)間的變化。該算法使用與預(yù)測項(xiàng)目類別相關(guān)的項(xiàng)目計(jì)算相似性值,以產(chǎn)生更好地反映真實(shí)偏好的近鄰集合。同時(shí)算法還設(shè)定了2個(gè)權(quán)重計(jì)算的原則:如果歷史的評分?jǐn)?shù)據(jù)不是周期性的,那么用戶最近的數(shù)據(jù)值比早期的數(shù)據(jù)值權(quán)重更高;用戶早期感興趣的項(xiàng)目評分分值的權(quán)重適當(dāng)減弱,而近期和周期的評分分值權(quán)重適當(dāng)提高。
協(xié)同過濾算法目前是個(gè)性化推薦使用最廣泛的方法,很多優(yōu)化和改進(jìn)的算法被用來解決個(gè)性化推薦中的稀疏性、可擴(kuò)展性以及運(yùn)算復(fù)雜度等問題[5-8]。Chakraborty[9]采用k-中心點(diǎn)對用戶和項(xiàng)目進(jìn)行聚類,來解決計(jì)算復(fù)雜度的問題。Yang等[10]提出了一種基于項(xiàng)目聚類預(yù)測的協(xié)同過濾方法,提高了推薦算法的可擴(kuò)展性。Acilar等[11]提出了一種基于人工免疫網(wǎng)絡(luò)算法的協(xié)同過濾模型,解決了稀疏性和可擴(kuò)展性的問題。上述的研究在進(jìn)行相似性計(jì)算時(shí)考慮了項(xiàng)目類別帶來的影響,但是忽視了時(shí)間因素對協(xié)同過濾的影響。
在協(xié)同過濾算法中,相似性計(jì)算是影響推薦質(zhì)量的一個(gè)關(guān)鍵因素,它可以對系統(tǒng)的整體性能和推薦結(jié)果產(chǎn)生重大影響[12]。用戶偏好的相似性計(jì)算是生成最近鄰的最重要的方法,但是用戶的偏好會(huì)隨時(shí)間的變化而變化,因此對用戶進(jìn)行相似性計(jì)算時(shí)應(yīng)該考慮時(shí)間因素的影響。一些研究在用戶偏好的計(jì)算中考慮了時(shí)間因素的影響[13-15],另外一些研究通過動(dòng)態(tài)的方法預(yù)測用戶的偏好變化。Liu等[16]通過關(guān)鍵詞查詢圖來表達(dá)用戶的動(dòng)態(tài)搜索,采用非線性逐步遺忘協(xié)同過濾算法,顯示了用戶的偏好隨時(shí)間的動(dòng)態(tài)變化。Xiong等[17]建立用戶-項(xiàng)目-時(shí)間三維向量,利用向量分解的方式研究用戶行為的動(dòng)態(tài)變化。Huang等[18]提出了一種加入時(shí)間衰減序列模式的新的協(xié)同推薦方法來準(zhǔn)確地模擬和預(yù)測客戶的購買模式。Koren[19]通過將時(shí)間序列分段聚類,將每個(gè)分類作為一個(gè)隱狀態(tài)得到狀態(tài)轉(zhuǎn)移概率矩陣,建立關(guān)于分段的隱馬爾科夫模型,對用戶的未來行為狀態(tài)進(jìn)行預(yù)測。Jeon等[20]提出了一種自適應(yīng)的用戶分析方法,該方法根據(jù)用戶的喜好隨著時(shí)間推移和區(qū)域變化動(dòng)態(tài)的更新策略。
用戶偏好相似性計(jì)算的依據(jù)是用戶對不同項(xiàng)目的評分,但是用戶在不同時(shí)間階段的評分對于用戶當(dāng)前偏好狀態(tài)的影響權(quán)重也應(yīng)各不相同。涉及時(shí)間因素的評價(jià)分為3種:近期評分、早期評分和周期性評分。上述研究成果關(guān)于時(shí)間的影響研究都是片面的,本文提出的基于用戶偏好動(dòng)態(tài)變化的協(xié)同過濾推薦算法,在基于項(xiàng)目類別的基礎(chǔ)上,對3種時(shí)間因素相關(guān)的評分對個(gè)性化推薦的影響進(jìn)行了深入研究。
協(xié)同過濾方法分為基于模型的協(xié)同過濾和基于記憶的協(xié)同過濾這2種方式?;谀P偷乃惴ㄊ紫韧ㄟ^構(gòu)建用戶評分模型來提供項(xiàng)目推薦。模型可以用貝葉斯網(wǎng)絡(luò)、聚類以及基于規(guī)則方法等建立[21]?;谟洃浀膮f(xié)同過濾算法利用整個(gè)用戶項(xiàng)目數(shù)據(jù)集來生成預(yù)測,分為基于用戶的方法和基于項(xiàng)目的方法。
協(xié)同過濾系統(tǒng)的目標(biāo)是提高用戶的推薦質(zhì)量。目前的協(xié)同過濾系統(tǒng)的主要依據(jù)用戶顯式或隱式的數(shù)據(jù),并基于用戶(項(xiàng)目)的最近鄰預(yù)測用戶的偏好。然而,現(xiàn)實(shí)世界中的用戶興趣隨時(shí)間的動(dòng)態(tài)變化將導(dǎo)致系統(tǒng)偏離用戶需求。本文提出一種改進(jìn)的基于項(xiàng)目的協(xié)同過濾算法,其前提假設(shè)是用戶的興趣并不是固定不變的,它隨著時(shí)間的變化而變化。該算法將項(xiàng)目評分時(shí)間引入權(quán)重函數(shù),每個(gè)分值的權(quán)重根據(jù)時(shí)間確定,時(shí)間較遠(yuǎn)的評分?jǐn)?shù)據(jù)權(quán)重較低,時(shí)間較新的評分和周期性的評分權(quán)重較高。
建立項(xiàng)目評分矩陣用于發(fā)現(xiàn)項(xiàng)目之間的相似性。任何物品如書籍、視頻等內(nèi)容計(jì)算機(jī)都很難自動(dòng)進(jìn)行分析,算法首先基于項(xiàng)目的屬性對項(xiàng)目進(jìn)行分類。例如,在電影分類中,根據(jù)每部電影的內(nèi)容類型可以將電影分為動(dòng)作、戲劇、喜劇、動(dòng)畫等類型。通過這種方式將項(xiàng)目和用戶分成子矩陣,每個(gè)子矩陣是由屬于類型g和至少對該類型電影進(jìn)行過一次評分的用戶組成,稱之為類型g的子矩陣:
其中,ng是屬于類別g的項(xiàng)目的數(shù)目,mg是至少評價(jià)了一個(gè)類別g的項(xiàng)目的用戶數(shù)目,Ru,i是用戶u對項(xiàng)目i的評分。
最近鄰集的產(chǎn)生最重要的是計(jì)算項(xiàng)目之間的相似性。該算法相似性的計(jì)算是基于與預(yù)測項(xiàng)目種類相關(guān)的項(xiàng)目,不是所有項(xiàng)目。子矩陣Ag(g=1,…,G)中,使用皮爾森相關(guān)系數(shù)計(jì)算項(xiàng)目i和項(xiàng)目j(i=j,j=1,…,ng)之間的相似性權(quán)重,如公式(1)[21]:
(1)
在計(jì)算項(xiàng)目i與類別g中每一個(gè)項(xiàng)目的相似性權(quán)重之后,用戶u對未評分項(xiàng)目i的預(yù)測評分可以通過公式(2)計(jì)算得出。
(2)
(3)
其中,α為時(shí)間權(quán)重,計(jì)算公式為式(4);β為重要性權(quán)重,計(jì)算公式為式(6);γ為評分率權(quán)重,計(jì)算公式為式(7)。將3個(gè)權(quán)重值α、β和γ相結(jié)合為權(quán)重函數(shù)。當(dāng)α=1,β=1和γ=1時(shí),f(u,i)的計(jì)算結(jié)果為1,所以權(quán)重函數(shù)的取值范圍為[0,1],Ru(td)表示用戶u在td時(shí)間的評分。
(4)
時(shí)間權(quán)重α是一種具有指數(shù)形式的單調(diào)遞減函數(shù),用來表示用戶興趣隨時(shí)間的變化。α∈[0,1],Itr為用戶2次連續(xù)評分之間的平均間隔時(shí)間,其中t由公式(5)計(jì)算得出。
(5)
式(5)中,t0表示用戶最后一次評分的時(shí)間,td表示用戶u對子矩陣Ag的項(xiàng)目最后評分時(shí)間。
(6)
重要性權(quán)重β表示類別g對于用戶u的重要性,β∈[0,1]。Sug為用戶u對屬于Ag的項(xiàng)目的評分之和,Su為用戶u的評分總和。
(7)
評分率權(quán)重γ∈[0,1],其中Nug表示用戶u對屬于Ag且評過分的項(xiàng)目的數(shù)目;Nu表示用戶u評分過的項(xiàng)目的總數(shù)。
用戶的偏好會(huì)隨著時(shí)間而變化。一個(gè)很久以前對某個(gè)項(xiàng)目或者內(nèi)容感興趣的用戶現(xiàn)在可能對同一個(gè)項(xiàng)目毫不在意,因?yàn)樗呐d趣偏好已經(jīng)轉(zhuǎn)移到別的項(xiàng)目上去了。在用戶的興趣不斷變化的背景下,較近的時(shí)間段的評分通常比較早期時(shí)間的評分更能反映用戶當(dāng)前的興趣偏好,也更加重要。當(dāng)前時(shí)間與最后一次評價(jià)同一類別項(xiàng)目的時(shí)間之間的間隔就顯得非常重要了,因此引入權(quán)重函數(shù),換句話說,就是衡量屬于目標(biāo)類別的項(xiàng)目有多長時(shí)間沒有被評分了。該值很小也就是時(shí)間很短,表明用戶對這樣的項(xiàng)目還是有很大的興趣,當(dāng)然,在某些環(huán)境下或者因?yàn)槟承┰?,用戶因?yàn)殚L時(shí)間不使用該網(wǎng)站(系統(tǒng))造成這樣的情況,這并不意味著用戶對這些項(xiàng)目失去了興趣,僅僅是因?yàn)橛脩暨@段時(shí)間沒有評價(jià)過該項(xiàng)目而已。
另一方面,人們通常有不同的習(xí)慣。有些用戶對電影更感興趣,所以經(jīng)?;〞r(shí)間看電影,而其他人可能很長時(shí)間才看一場電影。例如,2個(gè)用戶,第一個(gè)每天看好幾部電影,而第二個(gè)每個(gè)月才看一部電影。在這種情況下,對于第一個(gè)用戶來說一個(gè)月前看到的電影已經(jīng)是非常久遠(yuǎn)的了,對于第二個(gè)用戶來說時(shí)間是最近的。也就是說,周期長度是每個(gè)人的相對值,因此公式(5)中需要將(t0-td)值除以目標(biāo)用戶連續(xù)2次評分之間平均時(shí)間間隔。
此外,最近被評分的項(xiàng)目并不一定意味著用戶對其有特殊偏好,也有可能是用戶最近對其進(jìn)行了低評。區(qū)分一個(gè)項(xiàng)目最近被用戶評分還是低評,權(quán)重函數(shù)計(jì)算時(shí)考慮了最后一次評分的分值(Ru(td))。例如,僅考慮時(shí)間權(quán)重α作為權(quán)重函數(shù),不考慮β與γ的值,假設(shè)項(xiàng)目i和項(xiàng)目j在t=1時(shí)的評分分別是0和5,則對應(yīng)的權(quán)重函數(shù)分別是0.367和0.846,可以看出評分值對權(quán)重函數(shù)的結(jié)果有較大的影響,也就意味著權(quán)重函數(shù)能正確反映評分值的高低。
根據(jù)上述研究,可以看出時(shí)間權(quán)重增加了用戶近期行為的影響,降低了用戶歷史偏好行為的影響,同時(shí)考慮了用戶的偏好特征(Ru(td))和行為習(xí)慣((t0-td)的平均評價(jià)周期)。有些用戶的偏好是有周期性的,因此如果有人長期不評價(jià)某一類別的項(xiàng)目,并不一定意味著他不會(huì)再去選擇這類項(xiàng)目。重要性權(quán)重和評分率權(quán)重都考慮了用戶周期性偏好的問題。
為了處理用戶偏好隨時(shí)間變化的情況,本文引入一種新的不依賴于任何閾值的權(quán)重函數(shù),同時(shí)考慮α、β和γ,也就是通過公式(3)計(jì)算權(quán)重函數(shù)。
輸入:用戶項(xiàng)目矩陣A,時(shí)間戳矩陣B和項(xiàng)目類別集C。
輸出:預(yù)測用戶項(xiàng)目矩陣P。
算法過程:
1)將矩陣A根據(jù)項(xiàng)目類別C劃分為g次矩陣Ag(g=1,…,G)。
2)根據(jù)公式(1)計(jì)算生成目標(biāo)項(xiàng)目子矩陣Ag的近鄰集合。
3)根據(jù)公式(3)和矩陣B計(jì)算目標(biāo)項(xiàng)目的權(quán)重函數(shù)。
4)根據(jù)公式(2)計(jì)算預(yù)測用戶項(xiàng)目矩陣P。
5)回歸預(yù)測用戶項(xiàng)目矩陣P。
實(shí)驗(yàn)采用的數(shù)據(jù)集是公開的數(shù)據(jù)集MovieLens的子集。MovieLens數(shù)據(jù)集包含943個(gè)用戶對1682部電影的100000個(gè)評分?jǐn)?shù)據(jù),評分的范圍為1~5,用戶集是隨機(jī)選擇至少為20部電影評過分的用戶。將數(shù)據(jù)子集劃分為80%的訓(xùn)練集和20%的測試集。
電影信息包含在電影文件中,類型主要分為:動(dòng)作、冒險(xiǎn)、動(dòng)畫、兒童、喜劇、犯罪、紀(jì)錄片、戲劇、幻想、黑色電影、恐怖、音樂、神秘、浪漫、科幻、驚悚片、戰(zhàn)爭和西部。
平均絕對誤差(MAE)是一種被廣泛使用的度量方法,它通過比較測試數(shù)據(jù)集中對用戶推薦項(xiàng)目的預(yù)測分值與實(shí)際用戶評分的誤差情況來反映推薦的準(zhǔn)確性[22-24]。MAE首先計(jì)算N個(gè)相應(yīng)的評分預(yù)測對的絕對誤差,然后計(jì)算平均值。MAE越低,推薦系統(tǒng)預(yù)測用戶評分的準(zhǔn)確性就越高。
1)類別因素在皮爾森相關(guān)度量中的影響。
在第一個(gè)實(shí)驗(yàn)中,在相似性計(jì)算中采用皮爾森相關(guān)系數(shù)與考慮項(xiàng)目類別因素這2種方法進(jìn)行比較,結(jié)果如圖1所示。顯然,采用考慮類別因素計(jì)算相似性可以有效提高協(xié)同過濾的預(yù)測準(zhǔn)確性。傳統(tǒng)的協(xié)同過濾使用所有鄰居項(xiàng)目,其中包括內(nèi)容上與目標(biāo)項(xiàng)目毫無關(guān)系的項(xiàng)目,而本文提出的方法僅僅考慮與預(yù)測項(xiàng)目種類相關(guān)的項(xiàng)目。類別屬性的引入意味著預(yù)測的基礎(chǔ)是相似性計(jì)算僅考慮內(nèi)容相似的鄰居的評分。
圖1 皮爾森相關(guān)系數(shù)與考慮項(xiàng)目類別因素的MAE對比
2)時(shí)間權(quán)重對準(zhǔn)確性的影響。
實(shí)驗(yàn)中,對采用時(shí)間權(quán)重與無時(shí)間權(quán)重的協(xié)同過濾算法進(jìn)行比較,結(jié)果如圖2所示,系統(tǒng)的預(yù)測準(zhǔn)確性隨著時(shí)間權(quán)重參數(shù)個(gè)數(shù)的增加而逐步提高。當(dāng)相似性值大于等于0.4,且權(quán)重函數(shù)僅考慮評分時(shí)間的遠(yuǎn)近問題,此時(shí)權(quán)重函數(shù)為公式(8),通過對歷史數(shù)據(jù)降低權(quán)重來減少歷史偏好的影響,提高了預(yù)測準(zhǔn)確性。原因是用戶的興趣隨著時(shí)間的推移而變化,最近的項(xiàng)目評分在預(yù)測當(dāng)前用戶的偏好項(xiàng)目方面可能起到更重要的作用,而早期的評分?jǐn)?shù)據(jù)對最終推薦的貢獻(xiàn)度相對較小。
f(u,i)=e-(t0-td)
(8)
如果最后一次評分項(xiàng)目的類別與目標(biāo)項(xiàng)目類別相同,則權(quán)重函數(shù)為公式(9),預(yù)測準(zhǔn)確率進(jìn)一步提高,因?yàn)樽罱u分的項(xiàng)目如果得分較高的話,這說明用戶目前對這類項(xiàng)目有很高的興趣偏好。
(9)
雖然前面介紹了評價(jià)時(shí)間(t0-td)對系統(tǒng)推薦質(zhì)量的影響,但是這一指標(biāo)具有個(gè)體差異性,所以有必要通過評分的平均時(shí)間間隔來考慮每個(gè)用戶的行為習(xí)慣。此時(shí)權(quán)重函數(shù)為公式(10),其中t由公式(5)計(jì)算得出,從圖2可以看出,通過引入評價(jià)時(shí)間和平均評價(jià)周期后,在不同相似性值的情況下,MAE值均顯著低于傳統(tǒng)方法。
圖2 權(quán)重函數(shù)不同情況下與傳統(tǒng)協(xié)同過濾的MAE對比
f(u,i)=e-t
(10)
最后,從圖2中可以看出,如果權(quán)重函數(shù)采用時(shí)間權(quán)重α,系統(tǒng)的預(yù)測準(zhǔn)確性會(huì)進(jìn)一步提高,這是因?yàn)槿绻脩糇罱脑u價(jià)是積極的,時(shí)間權(quán)重函數(shù)將增加對用戶最近行為的考量。
3)重要性權(quán)重和評分率權(quán)重對預(yù)測準(zhǔn)確性的影響。
實(shí)驗(yàn)中將重要性權(quán)重和評分率權(quán)重的方法與無權(quán)重的方法進(jìn)行比較,結(jié)果如表1所示,當(dāng)相似性值高于0.4時(shí),單獨(dú)考慮2種權(quán)重方法的MAE值均優(yōu)于無權(quán)重函數(shù)的協(xié)同過濾的MAE值。原因是相同的,就是這2個(gè)加權(quán)函數(shù)為用戶經(jīng)常評價(jià)的項(xiàng)目提供了更多的推薦機(jī)會(huì)。
表1 3種方式的MAE對比
相似性值協(xié)同過濾重要性權(quán)重α評分率權(quán)重β00.8161.8121.7970.10.8211.7651.7010.20.8391.6491.5940.30.9621.4821.4650.41.2431.1881.1630.51.5020.9360.8920.61.9620.6680.6340.72.4680.4810.4700.82.7610.3900.389
4)與經(jīng)典的基于項(xiàng)目的協(xié)同過濾算法比較。
表2中顯示了傳統(tǒng)協(xié)同過濾、時(shí)間權(quán)重、重要性權(quán)重、評分率權(quán)重以及完整權(quán)重參數(shù)共5種情況下MAE的最佳結(jié)果。實(shí)驗(yàn)還比較了完整權(quán)重函數(shù)的協(xié)同過濾算法與經(jīng)典的基于項(xiàng)目的協(xié)同過濾算法。圖3顯示了完整權(quán)重與傳統(tǒng)協(xié)同過濾的推薦方法的比較,從相似值大于等于0.4開始,相對于經(jīng)典的協(xié)同過濾能夠給出更高的推薦準(zhǔn)確度、更低的MAE值。融合了3個(gè)權(quán)重函數(shù)組合的推薦算法增加了用戶最近時(shí)期個(gè)人偏好的推薦權(quán)重,更真實(shí)地反映用戶當(dāng)前的興趣并滿足用戶的推薦需求。
表2 權(quán)函數(shù)中各參數(shù)最佳MAE結(jié)果的比較
傳統(tǒng)協(xié)同過濾f(u, i)=αf(u, i)=βf(u, i)=γf(u, i)=(α+β)2×γ0.8160.4810.390.3890.36
圖3 傳統(tǒng)協(xié)同過濾與完整權(quán)重函數(shù)的MAE對比
協(xié)同過濾算法在以往的研究中已經(jīng)通過各種各樣的算法得到改進(jìn)和優(yōu)化。本文在基于項(xiàng)目的協(xié)同過濾框架下,引入了一種不依賴于任何閾值的新的簡單加權(quán)函數(shù),考慮了項(xiàng)目類別因素和用戶興趣隨時(shí)間的變化,建立基于用戶偏好動(dòng)態(tài)變化的協(xié)同過濾推薦模型。通過實(shí)驗(yàn)驗(yàn)證,考慮用戶的行為習(xí)慣和周期性需求,新算法在推薦準(zhǔn)確性方面明顯優(yōu)于傳統(tǒng)的協(xié)同過濾算法。
近年來,時(shí)間信息在協(xié)同過濾中占有越來越重要的地位,而用戶偏好中的時(shí)間效應(yīng)在推薦中起著越來越重要的作用。本文只考慮了時(shí)間因素對于推薦準(zhǔn)確性的影響,下一步工作將重點(diǎn)研究時(shí)間因素對于推薦多樣性的影響。