叢洪杰，龔 安，李華昱，帥訓(xùn)波

(1.中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580； 2.中國(guó)石油勘探開發(fā)研究院 計(jì)算機(jī)應(yīng)用技術(shù)研究所，北京 100083)

0 引 言

互聯(lián)網(wǎng)和移動(dòng)互聯(lián)網(wǎng)的蓬勃發(fā)展，帶來了信息快速增長(zhǎng)，在海量數(shù)據(jù)中獲取對(duì)自己有價(jià)值的信息更加困難，個(gè)性化推薦算法成為解決這一問題最有效的技術(shù)之一[1]。在個(gè)性化推薦算法中，協(xié)同過濾推薦在工業(yè)界和學(xué)術(shù)界都取得了很大的成功[2]。

隨著大數(shù)據(jù)時(shí)代的來臨，協(xié)同過濾的弊端也越發(fā)突出，包括數(shù)據(jù)稀疏性、冷啟動(dòng)、可擴(kuò)展性差、小規(guī)模數(shù)據(jù)離線處理算法無法應(yīng)用到大規(guī)模數(shù)據(jù)處理等[3]。針對(duì)這些問題，學(xué)者們提出了許多解決辦法。鄧愛林等[4]為減小數(shù)據(jù)稀疏性帶來的推薦精度低的問題，提出了一種基于項(xiàng)目評(píng)分預(yù)測(cè)填充空缺值的方法，然后采用一種新穎的相似性度量獲得目標(biāo)用戶更加準(zhǔn)確的最近鄰居，使得推薦質(zhì)量有所提升。Melville P等[5]在緩解評(píng)分?jǐn)?shù)據(jù)的稀疏性方面，則采用基于內(nèi)容的方法預(yù)填充用戶評(píng)分矩陣中的未評(píng)分項(xiàng)，從而提高推薦精度。

韋素云等[6]考慮了項(xiàng)目類別和興趣度等因素，提出一種改進(jìn)的協(xié)同過濾推薦算法。該算法首先計(jì)算項(xiàng)目之間的類別距，然后結(jié)合項(xiàng)目類別信息，考慮不同項(xiàng)目之間的相關(guān)程度，構(gòu)造出項(xiàng)目類別相似性矩陣，衡量項(xiàng)目間相似性的標(biāo)準(zhǔn)采用改進(jìn)的條件概率的方法。孟祥武等[7]提出大數(shù)據(jù)時(shí)代的推薦系統(tǒng)，充分利用豐富的用戶反饋、社會(huì)化網(wǎng)絡(luò)等信息進(jìn)一步提高推薦系統(tǒng)的性能和用戶滿意度。國(guó)琳等[8]提出通過構(gòu)建和分析用戶興趣分布曲線以發(fā)現(xiàn)興趣領(lǐng)域?qū)＜?，并甄別狀態(tài)不正常的偽專家。

王立才等[9]提出上下文感知的推薦系統(tǒng)，利用上下文信息，改善推薦系統(tǒng)的推薦精確度和用戶滿意度，從面向過程的角度論述了上下文感知推薦系統(tǒng)的研究進(jìn)展和難點(diǎn)。劉平峰等[10]提出用戶興趣圖譜，建立興趣領(lǐng)域本體，集成興趣圖譜的動(dòng)態(tài)性，實(shí)現(xiàn)用戶興趣匹配與定位，進(jìn)而提高推薦系統(tǒng)的精度。Pessemier T D等[11]提出個(gè)性化的混合推薦模型，該模型更多考慮了用戶的偏好、約束限制和用戶反饋等因素，使得推薦個(gè)人旅行線路更加符合用戶興趣。Oh J等[12]提出一種個(gè)性化流行趨勢(shì)匹配算法，計(jì)算目標(biāo)用戶的個(gè)性化趨勢(shì)，匹配用戶興趣偏好，提升預(yù)測(cè)評(píng)分，產(chǎn)生更加精準(zhǔn)的推薦列表。

以上所述研究雖然對(duì)推薦算法做出了改進(jìn)，并且取得了不錯(cuò)的效果，但對(duì)于項(xiàng)目類別和用戶興趣沒有加以充分挖掘利用。對(duì)此，文中算法引入用戶興趣分布預(yù)測(cè)填充評(píng)分矩陣空缺值，緩解數(shù)據(jù)稀疏性，改進(jìn)相似性度量方法計(jì)算項(xiàng)目相似性，以減小預(yù)測(cè)評(píng)分的誤差。

1 項(xiàng)目分類

1.1 評(píng)分矩陣

基于項(xiàng)目的協(xié)同過濾算法中，計(jì)算項(xiàng)目的相似性是關(guān)鍵步驟。項(xiàng)目類別數(shù)據(jù)和用戶評(píng)分?jǐn)?shù)據(jù)為文中推薦算法的基礎(chǔ)數(shù)據(jù)，由此可構(gòu)建項(xiàng)目類別分布矩陣、用戶興趣分布矩陣和用戶評(píng)分矩陣。

(1)項(xiàng)目類別分布矩陣。

項(xiàng)目類別分布矩陣由n×k的矩陣C(n,k)表示，如表1所示，其中n為項(xiàng)目的個(gè)數(shù)，k為項(xiàng)目類別的個(gè)數(shù)。

(2)用戶興趣分布矩陣。

用戶興趣分布矩陣由m×k矩陣D(m,k)表示，見表2，其中m為用戶的數(shù)目，k為用戶興趣種類數(shù)。

表1 項(xiàng)目類別分布矩陣C(n,k)

表2 用戶興趣分布矩陣D(m,k)

(3)用戶評(píng)分矩陣。

用戶評(píng)分矩陣由m×n的矩陣R(m,n)表示，見表3，其中用戶數(shù)目用m表示，項(xiàng)目數(shù)目用n表示，Ri,j表示用戶i對(duì)項(xiàng)目j的評(píng)分。

表3 用戶評(píng)分矩陣R(m,n)

1.2 相似性度量方法

傳統(tǒng)的基于鄰域的協(xié)同過濾算法，度量用戶或項(xiàng)目間的相似性是關(guān)鍵的一步。以下是計(jì)算項(xiàng)目之間相似性主要采用的三種方法：

(1)余弦相似性(cosine similarity)：把項(xiàng)目看作m維用戶的空間向量。設(shè)向量i和向量j分別代表用戶對(duì)項(xiàng)目i和項(xiàng)目j的評(píng)分，則項(xiàng)目i和項(xiàng)目j之間的相似性sim(i,j)定義如下：

(1)

其中，Ru,i、Ru,j分別為用戶u對(duì)項(xiàng)目i和項(xiàng)目j的評(píng)分；U表示用戶對(duì)項(xiàng)目i和項(xiàng)目j都有評(píng)分的用戶集合。

(2)皮爾森系數(shù)(Pearson correlation)。

(2)

(3)修正余弦相似性(adjusted cosine similarity)。

(3)

2 基于項(xiàng)目分類的修正余弦相似性

用戶規(guī)模和項(xiàng)目數(shù)目的增加，使得評(píng)分矩陣的數(shù)據(jù)稀疏性逐漸增加，從而導(dǎo)致預(yù)測(cè)評(píng)分精度低。目前解決辦法就是對(duì)用戶未評(píng)分項(xiàng)進(jìn)行預(yù)填充，固定缺省值是最簡(jiǎn)單且常用的方法之一，該方法可以有效地提高系統(tǒng)的推薦精度。但實(shí)際生活中評(píng)分矩陣中的缺省值顯然不可能都一樣，因此填充固定缺省值的方法沒有從根本上解決數(shù)據(jù)稀疏性問題。文中以用戶興趣分布評(píng)分矩陣求相似用戶，對(duì)空缺值進(jìn)行預(yù)測(cè)填充，減小用戶評(píng)分?jǐn)?shù)據(jù)的稀疏性。

傳統(tǒng)的修正余弦相似性的度量方法是對(duì)用戶的評(píng)分去中心化，通過減去用戶的平均評(píng)分，改善了用戶評(píng)分尺度不同的問題。評(píng)分尺度問題主要由用戶評(píng)分的標(biāo)準(zhǔn)不同而導(dǎo)致，比如評(píng)分區(qū)間為1～5分時(shí)，用戶對(duì)于項(xiàng)目評(píng)分A可能是3分以上喜歡，而B則4分以上才為喜歡。但是上述方法僅僅考慮了用戶評(píng)分尺度問題，對(duì)于項(xiàng)目的類別用戶的評(píng)分標(biāo)準(zhǔn)也是有所不同的，比如用戶對(duì)動(dòng)作類或科幻類的電影更加偏好，那么用戶會(huì)普遍給這一類別的電影更高的評(píng)分。文中提出對(duì)項(xiàng)目進(jìn)行分類，計(jì)算用戶在項(xiàng)目的每種類別中的評(píng)分標(biāo)準(zhǔn)，以此來改進(jìn)計(jì)算項(xiàng)目相似性的過程，以尋找更加準(zhǔn)確的K近鄰。

2.1 用戶興趣分布填充空缺值

基于項(xiàng)目的協(xié)同過濾，主要由計(jì)算項(xiàng)目的相似鄰居，預(yù)測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分和生成推薦列表等過程組成，其中計(jì)算項(xiàng)目的相似鄰居需要用戶對(duì)項(xiàng)目i、j同時(shí)具有評(píng)分。求用戶對(duì)項(xiàng)目i和對(duì)項(xiàng)目j分別有評(píng)分的并集公式表示為：

U=Ui∪Uj

(4)

其中，U表示所有用戶的集合；Ui和Uj分別表示對(duì)項(xiàng)目i和項(xiàng)目j有過評(píng)分的用戶集合。

對(duì)用戶集合中分別對(duì)項(xiàng)目i、j未評(píng)分的項(xiàng)進(jìn)行填充預(yù)測(cè)評(píng)分，定義P{pu,i,pu,j,…}。

預(yù)測(cè)填充策略，本階段采用用戶興趣分布矩陣作為求最近鄰居的輸入數(shù)據(jù)，通過基于用戶的協(xié)同過濾算法進(jìn)行預(yù)測(cè)評(píng)分。

(5)

其中，Pu,i為預(yù)測(cè)評(píng)分；simD(u,v)為用戶u和用戶v通過用戶興趣分布矩陣求得的相似度；rv,i為相似用戶對(duì)項(xiàng)目i的評(píng)分。

2.2 項(xiàng)目分類修正余弦相似性

sim(i,j)=

(6)

(7)

2.3 算法描述

輸入：用戶的項(xiàng)目評(píng)分矩陣R，項(xiàng)目類別信息，項(xiàng)目集合Items，目標(biāo)用戶集合U，項(xiàng)目鄰居數(shù)目K，推薦列表長(zhǎng)度N

輸出：目標(biāo)用戶u對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分，且生成目標(biāo)用戶u的推薦列表

(1)根據(jù)數(shù)據(jù)集中項(xiàng)目分類信息構(gòu)建項(xiàng)目類別分布矩陣C(n,k)；

(2)根據(jù)項(xiàng)目分類信息和用戶項(xiàng)目評(píng)分矩陣R，計(jì)算用戶興趣分布矩陣D(m,k)；

(4)求用戶對(duì)項(xiàng)目i和項(xiàng)目j分別有評(píng)分的用戶的并集；

(5)對(duì)并集中用戶對(duì)項(xiàng)目i或項(xiàng)目j未評(píng)分項(xiàng)，采用用戶興趣分布的協(xié)同過濾算法進(jìn)行預(yù)填充值；

(6)構(gòu)建用戶項(xiàng)目評(píng)分矩陣，求得項(xiàng)目i和項(xiàng)目j有著共同評(píng)分的用戶集U；

(7)利用基于項(xiàng)目分類的修正余弦相似性來計(jì)算項(xiàng)目之間的相似度，生成相似度最大的k個(gè)項(xiàng)目鄰居；

(8)通過求得的相似鄰居和相似度值來預(yù)測(cè)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分；

(9)通過對(duì)預(yù)測(cè)評(píng)分的排序，推薦top N項(xiàng)目給目標(biāo)用戶。

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

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

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用平均絕對(duì)誤差(mean absolute error，MAE)來評(píng)價(jià)算法的推薦精度[13]。假定目標(biāo)用戶的預(yù)測(cè)評(píng)分集為P{p1,p2,…,pn}，與其對(duì)應(yīng)測(cè)試集中的真實(shí)評(píng)分集為Q{q1,q2,…,qn}，則MAE表示為：

(8)

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

首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，構(gòu)建用戶的興趣分布數(shù)據(jù)以及項(xiàng)目分類數(shù)據(jù)，然后使用Java編程語言對(duì)推薦算法進(jìn)行實(shí)現(xiàn)，分別對(duì)傳統(tǒng)的余弦相似性、修正余弦、改進(jìn)的修正余弦進(jìn)行實(shí)現(xiàn)，對(duì)目標(biāo)用戶和電影進(jìn)行預(yù)測(cè)評(píng)分，評(píng)估推薦精度；最后對(duì)比文中算法與其他兩種算法的推薦精度。

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

為了驗(yàn)證算法的有效性，在使用相同數(shù)據(jù)集規(guī)模及驗(yàn)證方法上，對(duì)傳統(tǒng)協(xié)同過濾算法中使用的余弦相似性、修正余弦相似性的相似性度量方法與文中提出的改進(jìn)修正余弦相似性進(jìn)行實(shí)驗(yàn)對(duì)比。最近鄰居的規(guī)模從10到100遞增，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 推薦算法的MAE值比對(duì)

從圖1可以看出，文中提出的方法隨著最近鄰居的增加MAE值逐漸減小，且低于傳統(tǒng)協(xié)同過濾方法。因?yàn)槲闹蟹椒紤]了項(xiàng)目的類別以及對(duì)于用戶興趣分布的因素，在此基礎(chǔ)上計(jì)算的用戶的最近鄰居相似度更加符合現(xiàn)實(shí)，更加準(zhǔn)確，而通過更加準(zhǔn)確的最近鄰居用戶群體，可以獲得更加符合目標(biāo)用戶的預(yù)測(cè)評(píng)分。所以該算法可以有效提升推薦質(zhì)量，為用戶提供滿意的個(gè)性化推薦列表。

4 結(jié)束語

針對(duì)協(xié)同過濾算法所面臨的數(shù)據(jù)稀疏性、推薦精度低等[14]問題，采用了基于用戶興趣分布方法初步填充評(píng)分矩陣中的未評(píng)分項(xiàng)；在計(jì)算項(xiàng)目相似性階段，提出一種基于項(xiàng)目分類改進(jìn)修正余弦相似性度量方法，即由用戶平均評(píng)分去中心化的方法改為對(duì)用戶興趣類別平均分去中心化，求出最近鄰居并生成推薦列表。實(shí)驗(yàn)結(jié)果表明，該方法具有較小的MAE，在一定程度上提高了推薦質(zhì)量。