吳佳婧, 賀嘉楠, 王越群, 董立巖

(1. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 哈爾濱 150001； 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

0 引 言

隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展, 人類(lèi)社會(huì)已經(jīng)逐步進(jìn)入到電子信息時(shí)代。電子信息技術(shù)雖然改變了人們的生活方式, 提高了人們的工作效率, 但同時(shí)也給人們帶來(lái)了新的問(wèn)題。隨著信息量的飛速增長(zhǎng), 使人們?cè)谛畔z索過(guò)程中很難找到正在需要的信息。推薦系統(tǒng)可以在一定程度上解決信息過(guò)載的問(wèn)題, 因?yàn)槠鋵?shí)用性, 推薦系統(tǒng)被國(guó)內(nèi)外大多數(shù)的電子商務(wù)平臺(tái)所青睞。因此對(duì)推薦系統(tǒng)的研究和改進(jìn)得到了越來(lái)越多研究者的關(guān)注, 而推薦算法則是推薦系統(tǒng)的核心。根據(jù)推薦的生成方式, 推薦算法大致可以分為基于內(nèi)容的推薦系統(tǒng)以及基于協(xié)同過(guò)濾的推薦系統(tǒng)。

協(xié)同過(guò)濾[1]推薦算法主要根據(jù)用戶或項(xiàng)目的相似度進(jìn)行推薦, 其首要條件是需要找到目標(biāo)用戶[2]的相似用戶或目標(biāo)用戶喜好項(xiàng)目的近鄰項(xiàng)目, 進(jìn)而可以為目標(biāo)用戶推薦其興趣值較高的未產(chǎn)生評(píng)分行為的項(xiàng)目[3,4]。由此可見(jiàn)用戶間相似性的計(jì)算以及項(xiàng)目間相似性的計(jì)算對(duì)推薦系統(tǒng)的推薦準(zhǔn)確率起到了重要的作用。對(duì)于傳統(tǒng)的相似性計(jì)算[5,6]并沒(méi)有考慮用戶以及項(xiàng)目自身的屬性, 僅僅將用戶項(xiàng)目評(píng)分矩陣[7-9]作為唯一的參考因素。

傳統(tǒng)的相似性計(jì)算過(guò)程中只關(guān)注于用戶項(xiàng)目評(píng)分矩陣, 而忽略了用戶或項(xiàng)目本身的屬性特征, 筆者將項(xiàng)目自身的屬性標(biāo)簽[10]結(jié)合到相似性計(jì)算公式中, 給出了基于權(quán)重調(diào)節(jié)的矩陣補(bǔ)全協(xié)同過(guò)濾推薦算法。

1 基于權(quán)重調(diào)節(jié)的矩陣補(bǔ)全協(xié)同過(guò)濾

1.1 算法思想

項(xiàng)目的標(biāo)簽不只有一種, 可以有很多種類(lèi), 對(duì)于一部電影而言, 既可以屬于喜劇, 也可以屬于情感類(lèi)型, 所以在進(jìn)行相似度計(jì)算時(shí), 需要考慮每個(gè)項(xiàng)目的所有標(biāo)簽類(lèi)別[11,12], 項(xiàng)目的標(biāo)簽重合度與項(xiàng)目的相似性成正比。

如表1所示, 《女兒國(guó)》和《前任3》都屬于喜劇、 愛(ài)情類(lèi)型, 與《紅海行動(dòng)》類(lèi)型相比, 這兩部電影的類(lèi)型更為相似, 因此可以斷定這兩部電影的相似度更高。

表1 基于項(xiàng)目屬性的協(xié)同過(guò)濾推薦算法基本原理

定義1 項(xiàng)目屬性值Ii,x表示項(xiàng)目i是否具有屬性x。如果項(xiàng)目i具有屬性x, 則項(xiàng)目屬性值Ii,x的值為1, 如果項(xiàng)目i不具有屬性x, 則Ii,x置為0。

定義2Ci,j表示項(xiàng)目i與項(xiàng)目j之間的屬性差異度, 即項(xiàng)目i和項(xiàng)目j所具有的不同屬性個(gè)數(shù)?？赏ㄟ^(guò)項(xiàng)目i中的每個(gè)屬性值減去項(xiàng)目j中與之對(duì)應(yīng)的每個(gè)屬性值獲得。計(jì)算方法如下

其中n值由項(xiàng)目屬性種類(lèi)個(gè)數(shù)決定。項(xiàng)目差異度Ci,j的值與項(xiàng)目之間的相同屬性標(biāo)簽個(gè)數(shù)成反比。項(xiàng)目差異度的值越小, 代表兩個(gè)項(xiàng)目之間相同的屬性標(biāo)簽

表2 項(xiàng)目屬性統(tǒng)計(jì)表

越多, 進(jìn)而可以推測(cè)出兩個(gè)項(xiàng)目越相似。因此可以得出項(xiàng)目差異度與項(xiàng)目之間的相似性成反比。

項(xiàng)目屬性如表2所示, 假設(shè)具有A、B、C 3個(gè)項(xiàng)目, 并給出S1到S5等5個(gè)屬性。每個(gè)項(xiàng)目都具有其相應(yīng)的屬性值?？梢酝ㄟ^(guò)項(xiàng)目屬性統(tǒng)計(jì)表獲得項(xiàng)目A、B、C之間的屬性差異度。

3個(gè)項(xiàng)目之間的項(xiàng)目屬性差異度CA,B、CA,C、CB,C可由式(1)計(jì)算

CA,B=|1-1|+|0-1|+|1-0|+|1-1|+|0-1|=3

CA,C=|1-1|+|0-1|+|1-1|+|1-1|+|0-0|=1

CB,C=|1-1|+|1-1|+|0-1|+|1-1|+|1-0|=2

由計(jì)算可知CA,C

圖1 指數(shù)函數(shù)y=e-x的圖像Fig.1 The image of the exponential function

由于項(xiàng)目屬性差異度與項(xiàng)目之間的相似性有相關(guān)性, 所以將項(xiàng)目屬性差異度應(yīng)用到計(jì)算相似度的person相關(guān)系數(shù)[8]中。由于項(xiàng)目屬性差異度的取值均為大于等于0的整數(shù), 所以需要對(duì)權(quán)值進(jìn)行修正, 故引入指數(shù)函數(shù)y=e-x, 由指數(shù)函數(shù)圖像(見(jiàn)圖1)可知, 當(dāng)自變量取值為非負(fù)時(shí), 函數(shù)的值域區(qū)間為0～1。

將項(xiàng)目屬性差異度與指數(shù)函數(shù)相結(jié)合, 作為屬性差異度的指數(shù)函數(shù), 并在計(jì)算兩個(gè)項(xiàng)目的相似度時(shí), 引入屬性差異度的指數(shù)函數(shù)y=e-Ci,j, 并將差異度指數(shù)函數(shù)融入到person相關(guān)系數(shù)中, 進(jìn)行相似度計(jì)算的優(yōu)化。改進(jìn)后的person相關(guān)系數(shù)公式如下

1.2 算法流程

步驟1 獲得目標(biāo)用戶u的已評(píng)分項(xiàng)目集合IRated, 通過(guò)與所有項(xiàng)目集進(jìn)行差運(yùn)算, 獲得目標(biāo)用戶u的未評(píng)分但將要進(jìn)行評(píng)分的項(xiàng)目集合IunRated。為目標(biāo)

表3 項(xiàng)目用戶統(tǒng)計(jì)表

用戶u所推薦的項(xiàng)目將在IunRated中產(chǎn)生, 所以IunRated也是目標(biāo)項(xiàng)目集合。

步驟2 在評(píng)分矩陣中查詢對(duì)IunRated項(xiàng)目集合中的項(xiàng)目進(jìn)行評(píng)分過(guò)的用戶集合與對(duì)IRated項(xiàng)目集合中的項(xiàng)目進(jìn)行評(píng)分過(guò)的用戶集合, 二者求并集, 形成用戶集合U, 如表3所示。

步驟3 利用

即改進(jìn)的person相關(guān)系數(shù)進(jìn)行相似度計(jì)算, 主要計(jì)算目標(biāo)用戶的目標(biāo)項(xiàng)目j(j∈IunRated)與目標(biāo)用戶已評(píng)分項(xiàng)目i(i∈IRated)之間的相似度。

步驟4 獲得未評(píng)分項(xiàng)目j與已評(píng)分項(xiàng)目i的相似度后, 進(jìn)行為評(píng)分項(xiàng)目j的評(píng)分預(yù)測(cè), 評(píng)分預(yù)測(cè)公式如下

Ru,j=Ru,iSsim(i,j)

(4)

所示。通過(guò)式(4)可以為目標(biāo)用戶進(jìn)行未評(píng)分項(xiàng)目的評(píng)分矩陣補(bǔ)全。

步驟5 通過(guò)步驟4獲取目標(biāo)用戶的目標(biāo)項(xiàng)目集中所有項(xiàng)目的預(yù)測(cè)評(píng)分, 將評(píng)分按照由大致小的順序進(jìn)行排列。

步驟6 從步驟5中的項(xiàng)目集合序列中, 選取TopK個(gè)項(xiàng)目作為推薦結(jié)果, 推送給目標(biāo)用戶。

2 算法實(shí)現(xiàn)

基于權(quán)重調(diào)節(jié)的矩陣補(bǔ)全協(xié)同過(guò)濾算法。

輸入： 用戶評(píng)分矩陣Rmn, 分類(lèi)差距矩陣Cnn, 目標(biāo)用戶u, 目標(biāo)用戶未評(píng)分項(xiàng)目k。

輸出：u對(duì)k的預(yù)測(cè)評(píng)分score。

1 ratsimTotal←0

2 simTotal←0

3 fori←1∶n4 if (Rui!=0)//用戶u對(duì)項(xiàng)目i有評(píng)分

5Vi←?,Vk←?

>6 forj←1∶m

7 if (Rji!=0&&Rjk!=0)//用戶j對(duì)項(xiàng)目i、 項(xiàng)目k均有評(píng)分

8Vi←Vi∪{Rji}

9Vk←Vk∪{Rjk}

10 end if

11 end for

12 similarity←sim(Vi,Vk)·eCki

13 simTotal←simTotal+similarity

14 ratSimTotal←ratSimTotal+similarity*Rui15 end if

16 end for

17 score←ratSimTotal/simTotal

18 return score

3 實(shí)驗(yàn)結(jié)果與分析

3.1 前期準(zhǔn)備

該實(shí)驗(yàn)采用的數(shù)據(jù)集來(lái)自MovieLens ml-1M數(shù)據(jù)集, 由6 040個(gè)用戶以及3 900個(gè)電影組成, 并包含用戶對(duì)這些電影的評(píng)分記錄, 每個(gè)評(píng)分包括用戶評(píng)分的時(shí)間并以Timestamp形式表示, 其中評(píng)分是由5個(gè)等級(jí)構(gòu)成, 分?jǐn)?shù)越高代表用戶對(duì)電影的喜愛(ài)程度越高。

以上數(shù)據(jù)記錄在3張信息表中, user表記錄了用戶的信息, movies表記錄了電影信息, ratings表記錄了評(píng)分信息。

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)1 在同一個(gè)數(shù)據(jù)集下, 比較添加了項(xiàng)目屬性因素的協(xié)同過(guò)濾算法與傳統(tǒng)協(xié)同過(guò)濾算法之間平均絕對(duì)值偏差MAE[13,14]的值, 測(cè)試改進(jìn)的算法是否在推薦精度上有所提高。結(jié)果如圖2所示。

實(shí)驗(yàn)結(jié)果表明, 在傳統(tǒng)協(xié)同過(guò)濾算法中, 考慮項(xiàng)目屬性分類(lèi)因素, 將項(xiàng)目屬性差異度指數(shù)函數(shù)融入到person相關(guān)系數(shù)中后獲得的基于項(xiàng)目的(Item-based)協(xié)同過(guò)濾算法, 其平均值絕對(duì)誤差值更小, 由此可以推斷, 改進(jìn)的算法在推薦精度上有較大的提高。

實(shí)驗(yàn)2 在同一個(gè)數(shù)據(jù)集下, 比較添加了項(xiàng)目屬性因素的協(xié)同過(guò)濾算法與傳統(tǒng)協(xié)同過(guò)濾算法之間準(zhǔn)確率Precision, 測(cè)試改進(jìn)的算法是否在推薦準(zhǔn)確率上有所提高, 得到如圖3所示的實(shí)驗(yàn)結(jié)果。

圖2 項(xiàng)目屬性分類(lèi)對(duì)Item-based 圖3 項(xiàng)目屬性分類(lèi)對(duì)Item-based 協(xié)同過(guò)濾MAE的影響 協(xié)同過(guò)濾命中率的影響 Fig.2 The item properties classified influence Fig.3 The item properties classified influence of Item-based CF on the MAE of Item-based CF on the hit rate

由圖3可知, 改進(jìn)的基于項(xiàng)目推薦的協(xié)同過(guò)濾算法, 在命中率上有很大的提高, 由原60%的命中率提升到80%。實(shí)驗(yàn)結(jié)果表明, 結(jié)合了項(xiàng)目屬性分類(lèi)的基于項(xiàng)目的(Item-based)協(xié)同過(guò)濾算法, 可以提高推薦的準(zhǔn)確率, 證明改進(jìn)的算法具有一定的優(yōu)勢(shì)。

4 結(jié) 語(yǔ)

筆者針對(duì)傳統(tǒng)的協(xié)同過(guò)濾算法進(jìn)行了改進(jìn), 在傳統(tǒng)的協(xié)同過(guò)濾算法上, 考慮了項(xiàng)目屬性分類(lèi)的因素。算法改進(jìn)主要體現(xiàn)在算法的相似度計(jì)算上。通過(guò)構(gòu)建項(xiàng)目屬性統(tǒng)計(jì)表, 對(duì)項(xiàng)目評(píng)分矩陣進(jìn)行權(quán)重調(diào)節(jié), 并將項(xiàng)目屬性差異度以指數(shù)函數(shù)的形式作為改進(jìn)的person相關(guān)系數(shù)的計(jì)算參數(shù)。通過(guò)實(shí)驗(yàn)證明了改進(jìn)算法的有效性, 在提升推薦準(zhǔn)確度上有很大的突破。