黃永鋒，覃羅春

（東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

一種有效緩解協(xié)同過(guò)濾推薦評(píng)價(jià)數(shù)據(jù)稀疏問(wèn)題的算法

黃永鋒，覃羅春

（東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

在采用協(xié)同過(guò)濾算法構(gòu)建個(gè)性化推薦的系統(tǒng)中，經(jīng)常面臨用戶評(píng)價(jià)數(shù)據(jù)稀疏問(wèn)題，這將嚴(yán)重降低個(gè)性化推薦的準(zhǔn)確度.針對(duì)此問(wèn)題，提出了一種混合加權(quán)預(yù)測(cè)填充算法，從用戶訪問(wèn)的資源特征以及該資源在整個(gè)用戶群體中被訪問(wèn)的熱度出發(fā)，對(duì)用戶訪過(guò)的但未給出評(píng)價(jià)的數(shù)據(jù)進(jìn)行預(yù)測(cè)并填充，從而降低了由于用戶評(píng)價(jià)數(shù)據(jù)缺失所造成的評(píng)價(jià)矩陣稀疏程度，提高推薦準(zhǔn)確度.在MoiveLense數(shù)據(jù)集上的試驗(yàn)結(jié)果表明，該算法能夠明顯地提高推薦準(zhǔn)確度.

個(gè)性化推薦；協(xié)同過(guò)濾；數(shù)據(jù)稀疏；預(yù)測(cè)填充；資源特征

在互聯(lián)網(wǎng)服務(wù)供應(yīng)商提供海量信息時(shí)，通過(guò)個(gè)性化推薦能夠更快、更準(zhǔn)確地為用戶找到可能感興趣的信息資源，提供更加智能的服務(wù)，從而有效地提高用戶的忠誠(chéng)度，擴(kuò)大品牌影響力，提高企業(yè)銷售.個(gè)性化推薦目前廣泛地應(yīng)于互聯(lián)網(wǎng)各個(gè)領(lǐng)域，如電子商務(wù)、數(shù)字圖書館、網(wǎng)絡(luò)廣告定向投放、網(wǎng)絡(luò)新聞?dòng)喼频龋?］.而基于協(xié)同過(guò)濾的個(gè)性化推薦是迄今為止使用最為廣泛也是最受歡迎的個(gè)性化推薦算法之一［2－3］.

協(xié)同過(guò)濾是利用擁有共同興趣偏好的群體來(lái)為用戶推薦感興趣資源的一種過(guò)濾算法，該算法假設(shè)推薦系統(tǒng)有m個(gè)用戶的集合U＝ ｛u1，u2，…，um｝以及n個(gè)資源的集合I＝ ｛i1，i2，…，in｝.對(duì)于推薦系統(tǒng)中的每一位用戶ui∈U，記錄ui訪問(wèn)過(guò)的資源集合Iui＝ ｛iui，1，iui，2，…，iui，n｜iui，n∈I｝，Iui?I，并且用戶ui對(duì)集合Iui中的某些或者全部訪問(wèn)過(guò)的資源給出表達(dá)其對(duì)這些資源偏好的反饋信息，推薦系統(tǒng)記錄用戶對(duì)訪問(wèn)過(guò)資源的評(píng)價(jià)信息，構(gòu)成推薦系統(tǒng)的用戶 －資源評(píng)價(jià)矩陣.對(duì)于每一個(gè)需要給出個(gè)性化推薦資源的用戶ua，稱之為活動(dòng)用戶.協(xié)同過(guò)濾算法通過(guò)以下兩個(gè)過(guò)程為活動(dòng)用戶推薦其可能最感興趣的N個(gè)資源：

（1）預(yù)測(cè)：預(yù)測(cè)一個(gè)數(shù)值Puaij，該值表示活動(dòng)用戶ua對(duì)未曾訪問(wèn)過(guò)的資源ij的偏好程度，其中ij?Iua；

（2）推薦：推薦產(chǎn)生N個(gè)資源的集合Iua，r，Iua，r∈I，Iua，r∩Iua＝ ?，將這N個(gè)用戶最感興趣并且是用戶未曾訪問(wèn)過(guò)資源推薦給用戶ua.

協(xié)同過(guò)濾個(gè)性化推薦通常分為兩種［4］，即基于用戶的以及基于項(xiàng)的.由于具有非常好的擴(kuò)展性，基于項(xiàng)的協(xié)同過(guò)濾被更多地用來(lái)構(gòu)建個(gè)性化推薦系統(tǒng).全球最大的電子商務(wù)網(wǎng)站Amazon就采用了基于項(xiàng)的協(xié)同過(guò)濾構(gòu)建其個(gè)性化推薦系統(tǒng).

但是，無(wú)論采用基于項(xiàng)的還是基于用戶的協(xié)同過(guò)濾算法，其推薦準(zhǔn)確度都會(huì)依賴于用戶－資源評(píng)價(jià)矩陣的稀疏程度，評(píng)價(jià)矩陣越稀疏則推薦準(zhǔn)確度越低［5］.現(xiàn)有的緩解用戶－資源評(píng)價(jià)矩陣稀疏問(wèn)題的方法，如基于資源特征預(yù)測(cè)填充算法和基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法都存在一些弊端.本文針對(duì)上述算法存在的弊端，提出了一種混合加權(quán)預(yù)測(cè)填充算法，該算法以資源訪問(wèn)熱度為加權(quán)量，將基于資源特征和基于資源訪問(wèn)熱度兩種算法融合起來(lái)，汲取每一種算法的優(yōu)點(diǎn)，同時(shí)有效地規(guī)避每一種算法的不足，對(duì)用戶訪問(wèn)過(guò)但是未給出評(píng)價(jià)值的資源的評(píng)分進(jìn)行預(yù)測(cè)，并用預(yù)測(cè)值填充未評(píng)價(jià)值，以降低用戶－資源評(píng)價(jià)矩陣稀疏程度，提高推薦準(zhǔn)確度.

1 混合加權(quán)預(yù)測(cè)填充算法

1.1 現(xiàn)有預(yù)測(cè)填充算法的不足

基于資源特征的預(yù)測(cè)填充算法根據(jù)人們通常會(huì)對(duì)具有較高相似性的資源給出較為相似的評(píng)價(jià)值，通過(guò)提取資源在某些特征上的相似度，將最為相似的一些資源的評(píng)價(jià)值通過(guò)調(diào)和加權(quán)后，作為用戶訪問(wèn)過(guò)但未給出的評(píng)價(jià)值.該算法可以有效地降低用戶－資源評(píng)價(jià)矩陣稀疏程度［6］，但也存在下述一些缺陷.

（1）未考慮整個(gè)用戶群體對(duì)資源的評(píng)價(jià)值對(duì)該用戶產(chǎn)生的主觀影響，用戶對(duì)訪問(wèn)過(guò)的資源給出的評(píng)價(jià)值不僅受用戶自身對(duì)資源的偏好所決定，還受系統(tǒng)中用戶群體對(duì)資源的評(píng)價(jià)影響，而基于資源特征的預(yù)測(cè)填充算法只考慮了用戶對(duì)資源的自身偏好因素，未能考慮用戶群體的影響因素.

（2）依賴于用戶自身對(duì)其他資源的訪問(wèn)并給出的評(píng)價(jià)值，基于資源特征預(yù)測(cè)填充算法未給出評(píng)價(jià)值的目標(biāo)資源與目標(biāo)用戶訪問(wèn)過(guò)并且給出評(píng)價(jià)值的資源的相似度，當(dāng)用戶訪問(wèn)過(guò)并且給出的評(píng)價(jià)值較少的情況，該算法預(yù)測(cè)出來(lái)的評(píng)價(jià)值會(huì)嚴(yán)重地偏離用戶可能給出的真實(shí)評(píng)價(jià)值.

（3）資源的特征準(zhǔn)確識(shí)別并提取困難，系統(tǒng)中的資源具有大量的特征，如何抽取資源合理的特征子集作為計(jì)算資源之間的相似度是該算法面臨的一個(gè)難題.若抽取的特征過(guò)多，則會(huì)嚴(yán)重影響算法的效率，但是提取的特征數(shù)量比較少，則無(wú)法表現(xiàn)該類資源在特征上的識(shí)別度，造成無(wú)法準(zhǔn)確地計(jì)算資源之間的相似度，并對(duì)最終的預(yù)測(cè)準(zhǔn)確度造成嚴(yán)重的影響.

基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法則是從整個(gè)用戶群體出發(fā)，依據(jù)資源在整個(gè)用戶群體中的受歡迎程度預(yù)測(cè)影響目標(biāo)用戶對(duì)該資源的偏好程度.該算法通過(guò)統(tǒng)計(jì)待預(yù)測(cè)填充資源在整個(gè)群體的訪問(wèn)評(píng)價(jià)情況，然后將均值加權(quán)修正，計(jì)算該資源的待預(yù)測(cè)評(píng)價(jià)值［7］.但是基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法存在一個(gè)較為明顯的缺陷，即無(wú)法滿足目標(biāo)用戶的特殊偏好，群體用戶都喜歡的資源，該目標(biāo)用戶不一定會(huì)喜歡，而群體用戶不喜歡的資源，目標(biāo)用戶卻可能非常喜歡.

1.2 引入資源訪問(wèn)熱度的混合加權(quán)預(yù)測(cè)填充算法

現(xiàn)有的基于資源特征以及基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法，雖然能有效地降低用戶評(píng)價(jià)矩陣的稀疏度，但兩種算法都存在明顯的缺陷.因此考慮引入一種加權(quán)因子，將上述兩種算法結(jié)合起來(lái)，以融合兩種算法的優(yōu)點(diǎn)，同時(shí)降低單獨(dú)一種算法的缺陷.

在協(xié)同過(guò)濾個(gè)性化推薦系統(tǒng)中，用戶群體訪問(wèn)資源集合后給出的評(píng)價(jià)值會(huì)形成一個(gè)用戶－資源評(píng)價(jià)矩陣，如表1所示.

表1 用戶－資源評(píng)價(jià)矩陣Table 1 User－item rating matrix

表1中 ?表示用戶未曾訪問(wèn)某個(gè)資源，或者目標(biāo)用戶u訪問(wèn)過(guò)資源i但是未給出評(píng)價(jià)值.資源i為待預(yù)測(cè)評(píng)價(jià)值的資源，簡(jiǎn)稱為目標(biāo)資源，定義資源i的訪問(wèn)熱度為該資源在整個(gè)群體中被訪問(wèn)次數(shù)在整個(gè)用戶群體中所占的比例，如式（1）所示.

其中：Pd表示目標(biāo)資源i的訪問(wèn)熱度；rui，d表示每個(gè)用戶訪問(wèn)目標(biāo)資源的次數(shù)；ui表示推薦系統(tǒng)中的每個(gè)用戶.資源訪問(wèn)熱度可以很好地體現(xiàn)目標(biāo)資源在整個(gè)用戶群體中的訪問(wèn)特征.

為了克服上述基于資源特征以及基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法所面臨的不足，這里引入資源訪問(wèn)熱度作為加權(quán)因子的混合加權(quán)預(yù)測(cè)填充算法，該算法以資源訪問(wèn)熱度為加權(quán)值，因此，將基于資源特征預(yù)測(cè)的評(píng)價(jià)值和基于資源訪問(wèn)熱度預(yù)測(cè)的填充值結(jié)合起來(lái)，最終產(chǎn)生對(duì)目標(biāo)資源的預(yù)測(cè)評(píng)價(jià)值.

設(shè)系統(tǒng)中所有用戶集合為U，資源集合為I，目標(biāo)用戶u存在訪問(wèn)過(guò)但是未給出評(píng)價(jià)值的資源i，V表示用戶u訪問(wèn)過(guò)并且給出評(píng)價(jià)值的資源集合，定義資源特征集合C＝｛c1，c2，…，cm｝.為了計(jì)算目標(biāo)資源i與V中每個(gè)資源在特征集C上的相似度，定義歐幾里得距離為相似度計(jì)算方法，如式（2）所示.

其中：sim（i，j）Euclidean表示資源i和j的特征相似度；ri，，k，rj，k分別表示資源i和j在特征集C上的相應(yīng)取值.在資源特征向量的相似度基礎(chǔ)上，可以通過(guò)調(diào)和加權(quán)方法得到基于資源特征的預(yù)測(cè)評(píng)價(jià)填充值［8］，如式（3）所示.

其中：si表示對(duì)第i個(gè)資源的評(píng)價(jià)值；sim（d，si）表示待預(yù)測(cè)填充的資源d與資源i在特征上的相似度；N為目標(biāo)用戶訪問(wèn)過(guò)并且給出評(píng)價(jià)值的資源數(shù)量.由式（4）可以得到基于資源訪問(wèn)熱度的預(yù)測(cè)填充值.

其中：表示待預(yù)測(cè)資源在整個(gè)群體中被訪問(wèn)過(guò)并且給出評(píng)價(jià)值的均值.在得到基于資源特征預(yù)測(cè)評(píng)價(jià)值和基于資源訪問(wèn)熱度預(yù)測(cè)評(píng)價(jià)值的基礎(chǔ)上，引入資源訪問(wèn)熱度加權(quán)因子，由式（5）可以得到最終的混合加權(quán)預(yù)測(cè)評(píng)價(jià)值.

將最終得到的預(yù)測(cè)值Rd替換目標(biāo)用戶u對(duì)資源i的評(píng)價(jià)值.

1.3 算法描述

根據(jù)上述分析，可以得到基于資源特征和基于資源訪問(wèn)熱度的混合加權(quán)預(yù)測(cè)填充算法，具體描述如下：

2 試驗(yàn)結(jié)果及分析

2.1 試驗(yàn)數(shù)據(jù)集

本文使用GroupLens提供的MovieLense系統(tǒng)上的10kbytes數(shù)據(jù)集作為評(píng)價(jià)算法效果的試驗(yàn)數(shù)據(jù)集［9］，該數(shù)據(jù)集由943個(gè)用戶、1 682部電影、共100 000條訪問(wèn)評(píng)價(jià)記錄組成.每個(gè)訪問(wèn)記錄由4個(gè)字段組成（uid，mid，rt，dt），其中uid表示用戶標(biāo)識(shí)符，mid表示電影標(biāo)識(shí)符，rt表示用戶uid對(duì)電影mid的評(píng)價(jià)值，其值范圍為［1，5］，dt表示Unix時(shí)間戳.抽取每部電影的發(fā)行日期、電影類型、發(fā)行國(guó)家、發(fā)行語(yǔ)言等信息作為每一部電影的特征向量.

本文把100 000記錄分為訓(xùn)練集和測(cè)試集，其中隨機(jī)將每個(gè)用戶訪問(wèn)的15條記錄單獨(dú)保存起來(lái)作為測(cè)試集，剩下的記錄作為訓(xùn)練集，用來(lái)檢驗(yàn)采用混合加權(quán)算法對(duì)推薦質(zhì)量的提升程度.

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

用信息檢索領(lǐng)域評(píng)估系統(tǒng)效果的準(zhǔn)確度作為評(píng)價(jià)標(biāo)準(zhǔn)［10］，如式（6）所示.

其中：H為推薦命中的數(shù)量；N為推薦的數(shù)量.

2.3 試驗(yàn)結(jié)果和分析

為了比較基于資源特征預(yù)測(cè)填充的和無(wú)預(yù)測(cè)填充的基于項(xiàng)的協(xié)同過(guò)濾算法，在不同的用戶－資源評(píng)價(jià)矩陣稀疏程度下的推薦準(zhǔn)確度，本文采用矩陣稀疏度來(lái)衡量用戶－資源評(píng)價(jià)稀疏程度，如式（7）所示.

其中：L表示評(píng)價(jià)矩陣稀疏度；rs表示推薦系統(tǒng)中目標(biāo)用戶訪問(wèn)過(guò)某個(gè)資源并且給出的評(píng)價(jià)值；Z表示推薦系統(tǒng)中所有用戶數(shù)量；X表示推薦系統(tǒng)中所有不重復(fù)資源的數(shù)量.L越小表示稀疏程度越高.試驗(yàn)將訓(xùn)練集分別設(shè)置用戶評(píng)價(jià)矩陣稀疏度為0.41%，1.41%，2.41%，3.41%，4.41%，設(shè)計(jì)了 4 組試驗(yàn)，分別采用無(wú)預(yù)測(cè)填充、基于資源訪問(wèn)熱度的預(yù)測(cè)填充、基于資源特征預(yù)測(cè)填充和混合加權(quán)預(yù)測(cè)填充的評(píng)價(jià)矩陣，然后采用傳統(tǒng)的基于項(xiàng)的協(xié)同過(guò)濾算法進(jìn)行推薦，比較4種情況的推薦效果，試驗(yàn)結(jié)果如圖1所示.

圖1 4種推薦準(zhǔn)確度對(duì)比效果Fig.1 Comparison effect of four kinds of recommendation accuracy

從圖1可以看出，無(wú)預(yù)測(cè)填充的基于項(xiàng)的協(xié)同過(guò)濾推薦曲線隨著矩陣稀疏程度不同，推薦準(zhǔn)確度也隨之改變，評(píng)價(jià)矩陣稀疏度越小，則推薦準(zhǔn)確度越低.基于資源訪問(wèn)熱度預(yù)測(cè)填充算法無(wú)法解決用戶特殊偏好問(wèn)題，雖然能夠提高評(píng)價(jià)矩陣稀疏度，但是與無(wú)預(yù)測(cè)填充的基于項(xiàng)的協(xié)同過(guò)濾相比，推薦準(zhǔn)確度未見(jiàn)明顯提高.基于資源特征的預(yù)測(cè)填充算法能夠很好地根據(jù)資源自身的客觀屬性對(duì)稀疏矩陣進(jìn)行預(yù)測(cè)填充，效果比基于資源訪問(wèn)熱度的預(yù)測(cè)填充算法好，但是它只考慮資源本身的客觀屬性，沒(méi)能考慮人類隨眾心里以及整個(gè)用戶群體行為對(duì)個(gè)體行為的影響.混合加權(quán)預(yù)測(cè)填充算法能夠很好地融合基于資源特征和基于資源訪問(wèn)熱度預(yù)測(cè)填充算法的優(yōu)點(diǎn)，并且也可以彌補(bǔ)兩者之間的不足，使得混合加權(quán)預(yù)測(cè)填充得到的推薦準(zhǔn)確度要高于基于資源特征和基于資源訪問(wèn)熱度的推薦準(zhǔn)確度.與此同時(shí)，混合加權(quán)預(yù)測(cè)填充與無(wú)預(yù)測(cè)填充的推薦結(jié)果相比，在不同的評(píng)價(jià)矩陣稀疏程度下，推薦準(zhǔn)確度平均提升39%.因混合加權(quán)預(yù)測(cè)填充算法具有較好的客觀性，可以在一定程度上修正用戶由于心情好壞等主觀情緒對(duì)給出評(píng)價(jià)值的影響，使得預(yù)測(cè)的填充值更加符合用戶真實(shí)的客觀評(píng)價(jià)值，進(jìn)一步地提高最終個(gè)性化推薦的準(zhǔn)確度.特別是在評(píng)價(jià)矩陣嚴(yán)重稀疏的情況，采用混合加權(quán)預(yù)測(cè)填充算法能夠提供很好的初始推薦準(zhǔn)確度，一定程度上緩解了采用協(xié)同過(guò)濾算法構(gòu)建的個(gè)性化推薦中冷啟動(dòng)問(wèn)題.

3 結(jié) 語(yǔ)

本文針對(duì)在基于項(xiàng)的協(xié)同過(guò)濾推薦算法中，因數(shù)據(jù)稀疏嚴(yán)重降低推薦準(zhǔn)確度的問(wèn)題，將基于資源特征預(yù)測(cè)填充和基于資源訪問(wèn)熱度預(yù)測(cè)填充算法有機(jī)地結(jié)合起來(lái)，形成混合加權(quán)預(yù)測(cè)填充算法.經(jīng)試驗(yàn)表明，該算法能夠有效預(yù)測(cè)用戶訪問(wèn)過(guò)但是未曾評(píng)價(jià)的資源的評(píng)價(jià)值，并采用此值對(duì)缺失值進(jìn)行填充，降低用戶－資源評(píng)價(jià)矩陣的稀疏度，另外，基于協(xié)同過(guò)濾算法構(gòu)建的推薦系統(tǒng)在經(jīng)過(guò)混合加權(quán)預(yù)測(cè)填充算法對(duì)評(píng)價(jià)矩陣進(jìn)行填充后，通常能夠獲得更好的推薦效果.但是該算法的時(shí)間復(fù)雜度高，還可以通過(guò)進(jìn)一步優(yōu)化來(lái)提高算法的效率，并且基于資源特征預(yù)測(cè)依賴資源自身的特征區(qū)分度，如何選擇合適的特征也是下一步需要研究的問(wèn)題.

參 考 文 獻(xiàn)

［1］ADOMAVICIOUS G，TUZHILIN A.Towards the next generation of recommender systems：A survey of the state－ofthe－art and possible extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734－749.

［2］SU X Y，TAGHI M K.A Survey of collaborative filtering techniques［J］.Advances in Artificial Intelligence，2009，Article ID 421425，1－19.

［3］邢春曉，高鳳榮，戰(zhàn)思南，等.適應(yīng)用戶興趣變化的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（2）：296－301.

［4］SARWAR B，KARYPIS G，KONSTAN J，et al.Item－based collaborative filtering recommendation algorithms ［C］／／Proceedings of the 10th International Conference on World Wide Web.Hong Kong，China，2001：285－295.

［5］吳顏，沈潔，顧天竺，等.協(xié)同過(guò)濾推薦系統(tǒng)中數(shù)據(jù)稀疏問(wèn)題的解決［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（6）：94－97.

［6］LIU Z B，WANG H，QU W Y，et al.Sparse matrix prediction filling in collaborative filtering ［C］／／IEEE International Conferece on Scalable Computing and Communications：The Eighth International Conference on Embedded Computing.2009：304－307.

［7］MA H，KING I，LYU M R.Effective missing data prediction for collaborative filtering［C］／／Proceeding of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.2007：39－46.

［8］SEGARAN T.Programming collective intelligence ［M］.Sebastopol：O'Reilly，2009.

［9］Group Lense Research.Project MoiveLense［EB／OL］（2007－05－01）［2011－09－15］.http：／／www.grouplens.org／.

［10］劉建國(guó)，周濤，郭強(qiáng)，等.個(gè)性化推薦系統(tǒng)評(píng)價(jià)方法綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6（3）：1－10.

An Effective Algorithm for Relieving Sparse Data in Collaborative Filtering Recommendation

HUANGYong－feng，QINLuo－chun
（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

Personalized recommendation system based on collaborative filtering often faces the data sparsity which seriously reduces the recommendation accuracy.An efficient hybrid weighted prediction algorithm is presented，which predicts the data visited but not rated by the characteristics and the access frequency，and fills the user－item matrix with the predictions.In this way，the sparsity of the user－item matrix is reduced，and the accuracy of recommendation is improved accordingly.Experimental results on MoiveLense data set clearly indicate that the algorithm can significantly improve the recommendation accuracy.

personalized recommendation；collaborative filtering；data sparsity；prediction filling；item characteristic

TP 274＋.5

A

1671－0444（2013）01－0083－05

2011－10－28

國(guó)家自然科學(xué)基金資助項(xiàng)目（30770589）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（2011D11206）

黃永鋒（1971—），男，山東泰安人，副教授，博士，研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別.E－mail：yfhuang＠dhu.edu.cn