王竹婷

（合肥學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

一種基于動(dòng)態(tài)權(quán)值的改進(jìn)協(xié)同過(guò)濾算法研究

王竹婷

（合肥學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

協(xié)同過(guò)濾是個(gè)性化推薦系統(tǒng)中使用最為廣泛的一種推薦算法之一，分為基于用戶和基于項(xiàng)目?jī)煞N協(xié)同過(guò)濾算法.本文提出的改進(jìn)算法將兩種方法相結(jié)合使用，首先改進(jìn)了傳統(tǒng)的相似度度量方法，再分別利用用戶和項(xiàng)目之間的相似度值預(yù)測(cè)未評(píng)分項(xiàng)目值，并將兩種預(yù)測(cè)結(jié)果加權(quán)平均，根據(jù)用戶近鄰數(shù)和項(xiàng)目近鄰數(shù)動(dòng)態(tài)確定加權(quán)系數(shù).實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的協(xié)同過(guò)濾算法可以提高推薦質(zhì)量.

協(xié)同過(guò)濾;個(gè)性化推薦系統(tǒng);相似度

1 引言

個(gè)性化推薦系統(tǒng)就是通過(guò)記錄用戶相關(guān)的網(wǎng)上歷史行為信息，包括網(wǎng)站的訪問(wèn)次數(shù)，網(wǎng)頁(yè)瀏覽時(shí)間的長(zhǎng)短，有無(wú)購(gòu)買(mǎi)行為、評(píng)分多少等，利用這些歷史信息，提取關(guān)鍵數(shù)據(jù)，建立用戶興趣模型，并根據(jù)用戶興趣模型預(yù)測(cè)用戶可能感興趣的信息資源，再推薦給用戶使用的個(gè)性化服務(wù)系統(tǒng).目前國(guó)內(nèi)外大型門(mén)戶網(wǎng)站和電子商務(wù)平臺(tái)都不同程度的使用推薦系統(tǒng)為用戶進(jìn)行推薦服務(wù)，該系統(tǒng)一方面可以幫助用戶快速、準(zhǔn)確地找到所需資源，而無(wú)需耗費(fèi)大量的時(shí)間對(duì)海量的信息進(jìn)行篩選；另一方面可以幫助網(wǎng)絡(luò)商家在線推銷(xiāo)自己的產(chǎn)品.

推薦系統(tǒng)根據(jù)推薦算法的不同，可以分為基于內(nèi)容的推薦[1]，基于關(guān)聯(lián)規(guī)則的推薦[2]，協(xié)同過(guò)濾推薦[3]和混合推薦算法[4].其中協(xié)同過(guò)濾算法是目前為止應(yīng)用于推薦系統(tǒng)的最成功的算法.協(xié)同過(guò)濾算法又分為基于用戶的協(xié)同過(guò)濾算法和基于項(xiàng)目的協(xié)同過(guò)濾算法兩種，兩種方法各具優(yōu)勢(shì)，基于用戶的算法可以實(shí)現(xiàn)跨類(lèi)型的推薦，但受數(shù)據(jù)稀疏性影響較大；基于項(xiàng)目的算法受數(shù)據(jù)稀疏性影響較小，但無(wú)法進(jìn)行跨類(lèi)型的推薦.本文首先改進(jìn)了傳統(tǒng)的用戶和項(xiàng)目之間的相似性度量方法，采用加權(quán)平均將兩種算法的預(yù)測(cè)結(jié)果相結(jié)合，并通過(guò)用戶近鄰數(shù)和項(xiàng)目近鄰數(shù)動(dòng)態(tài)調(diào)整加權(quán)系數(shù).

2 問(wèn)題描述及傳統(tǒng)的相似性度量方法

傳統(tǒng)的協(xié)同過(guò)濾算法一般分三個(gè)步驟：首先，從用戶網(wǎng)上行為數(shù)據(jù)庫(kù)中提取關(guān)鍵數(shù)據(jù)，構(gòu)建用戶-評(píng)分矩陣；接下來(lái)，利用用戶-評(píng)分矩陣中的用戶評(píng)分信息，計(jì)算用戶與用戶之間項(xiàng)目與項(xiàng)目之間的相似度；最后利用相似度信息預(yù)測(cè)用戶未評(píng)分項(xiàng)目的評(píng)分情況，從而選擇評(píng)分高的項(xiàng)目為目標(biāo)用戶進(jìn)行推薦.因此，相似度度量方法是協(xié)同過(guò)濾推薦算法中非常關(guān)鍵的技術(shù)，其直接決定了推薦系統(tǒng)的推薦質(zhì)量.

2.1 用戶-項(xiàng)目矩陣的構(gòu)建

用戶-項(xiàng)目矩陣是一個(gè)m*n階的二維矩陣，m是用戶數(shù)，U={u1，u2，…，um}為用戶集合，n是項(xiàng)目數(shù)，I={i1，i2，…，in}為項(xiàng)目集合，矩陣中第i行第j列元素Rij表示第i個(gè)用戶對(duì)第j的項(xiàng)目的評(píng)分值，矩陣R（m,n）具體形式如表1所示.Rij的值越高表示用戶i對(duì)項(xiàng)目j越感興趣.

表1 用戶-項(xiàng)目評(píng)分矩陣

2.2 傳統(tǒng)的相似度度量方法

協(xié)同過(guò)濾算法根據(jù)相似度度量對(duì)象的不同分為基于用戶和基于項(xiàng)目的兩種.基于用戶的算法是根據(jù)不同用戶的共同評(píng)分項(xiàng)目，計(jì)算出用戶與用戶之間的相似程度，再找到與目標(biāo)用戶相似度較高的用戶群體預(yù)測(cè)項(xiàng)目評(píng)分實(shí)施推薦；基于項(xiàng)目的算法則通過(guò)評(píng)分過(guò)共同項(xiàng)目的不同用戶群體的評(píng)分值，計(jì)算項(xiàng)目與項(xiàng)目之間的相似度，再通過(guò)目標(biāo)用戶已評(píng)分項(xiàng)目與未評(píng)分項(xiàng)目之間的相似度預(yù)測(cè)評(píng)分值.基于用戶和基于項(xiàng)目的相似度計(jì)算都有三種基本方法，余弦相似性、修正的余弦相似性和Pearson相關(guān)系數(shù)，文獻(xiàn)[5]通過(guò)實(shí)驗(yàn)證明在三種相似性度量方法中Pearson相關(guān)系數(shù)可以更好的推算出用戶或項(xiàng)目之間的相似程度，本文也選用Pearson項(xiàng)目系數(shù)作為相似度計(jì)算方法.

2.2.1 用戶的相似度

用戶的相似度表示不同的用戶之間在興趣愛(ài)好上相似的程度，其計(jì)算公式如下：

公式（1）中，sim（i，a）表示用戶i和用戶a之間的相似性，Nai表示用戶a和用戶i共同評(píng)分過(guò)的項(xiàng)目集分別表示用戶i和用戶a的平均評(píng)分值.該公式通過(guò)兩用戶共同評(píng)分過(guò)的項(xiàng)目評(píng)分值，計(jì)算兩者之間的相似度.

2.2.2 項(xiàng)目的相似性

項(xiàng)目之間的相似性表示用戶對(duì)兩個(gè)不同項(xiàng)目同時(shí)發(fā)生興趣的程度，計(jì)算公式如下：

公式（2）中，sim(i,j)表示項(xiàng)目i和項(xiàng)目j之間的相似性，Uij表示共同評(píng)分過(guò)項(xiàng)目i和項(xiàng)目j的用戶集是用戶u的平均評(píng)分值.該公式通過(guò)評(píng)分過(guò)相同項(xiàng)目的不同用戶的評(píng)分值，計(jì)算項(xiàng)目之間的相似度.

2.3 傳統(tǒng)相似性度量算法的缺陷

基于用戶的算法，重點(diǎn)在于目標(biāo)用戶和其他用戶之間的相似性度量方法，當(dāng)兩個(gè)用戶共同評(píng)分的項(xiàng)目較多，評(píng)分相似的時(shí)候，說(shuō)明兩者的興趣愛(ài)好相似，通過(guò)傳統(tǒng)的計(jì)算方法也可以得出兩者相似度較高，以此數(shù)據(jù)作為項(xiàng)目預(yù)測(cè)依據(jù)，結(jié)果較為準(zhǔn)確；但在實(shí)際應(yīng)用中，一個(gè)推薦系統(tǒng)可能要推薦成千上萬(wàn)個(gè)項(xiàng)目，而一個(gè)用戶評(píng)分過(guò)的項(xiàng)目量不足1%，兩個(gè)用戶共同評(píng)分過(guò)的項(xiàng)目數(shù)量就更稀少，很多情況下，只有一到兩個(gè)共同評(píng)分的項(xiàng)目，而且如果這個(gè)兩個(gè)評(píng)分相近的話，傳統(tǒng)的計(jì)算方法相似度非常高，甚至有可能為1，這樣的運(yùn)算結(jié)果表明，兩者之間的興趣愛(ài)好非常接近，但實(shí)際情況并非如此.基于項(xiàng)目的相似性也存在類(lèi)似的問(wèn)題，當(dāng)共同評(píng)給兩個(gè)項(xiàng)目的評(píng)分用戶過(guò)少時(shí)，相似度的計(jì)算極為不準(zhǔn)確.

2.4 相似性度量方法的改進(jìn)

由于傳統(tǒng)的基于用戶和基于項(xiàng)目的兩種相似性度量方法在共同評(píng)分的數(shù)據(jù)極為稀少或有著共同評(píng)分項(xiàng)目的用戶極為稀少的時(shí)候，計(jì)算出來(lái)的相似度值與實(shí)際情況存在較大的誤差，為避免此類(lèi)問(wèn)題發(fā)生，本文提出在計(jì)算相似度時(shí)設(shè)定兩個(gè)閾值，并采用分段函數(shù)進(jìn)行計(jì)算.

2.4.1 改進(jìn)的基于用戶的相似性度量

在計(jì)算用戶i和用戶a之間的相似性時(shí)，首先找出兩個(gè)用戶共同評(píng)分過(guò)的項(xiàng)目集Nai，計(jì)算Nai中的項(xiàng)目個(gè)數(shù)NumNai，設(shè)置好閾值μ1，將NumNai的值與μ1做比較，若小于μ1，則i和a的相似度值為0，如果大于或等于μ1，使用原有的相似度值.

2.4.2 改進(jìn)的基于項(xiàng)目的相似性度量

在計(jì)算項(xiàng)目i與項(xiàng)目j之間的相似度時(shí)，采用同樣的改進(jìn)措施，先找出共同評(píng)分過(guò)項(xiàng)目i和項(xiàng)目j的用戶集合Uij，計(jì)算Uij中用戶的個(gè)數(shù)NumUij，同樣設(shè)定閾值μ2，當(dāng)兩個(gè)項(xiàng)目共同評(píng)分過(guò)的用戶數(shù)量NumUij小于μ2時(shí)，則兩個(gè)項(xiàng)目的相似度為0，如果NumUij大于或等于μ2，則保持原有相似度值不變.

3 協(xié)同過(guò)濾算法預(yù)測(cè)評(píng)分值

3.1 基于用戶的評(píng)分值預(yù)測(cè)

基于用戶的評(píng)分值預(yù)測(cè)算法，要根據(jù)用戶之間的相似性值，找到與目標(biāo)用戶相似程度較高的最近鄰居用戶集，本文設(shè)置最近臨用戶的相似度閾值為η，當(dāng)目標(biāo)用戶與某用戶的相似度大于或等于η時(shí)，則該用戶為目標(biāo)用戶的最近鄰居.找到最近鄰居集合后，根據(jù)公式（5）計(jì)算出用戶對(duì)未評(píng)分項(xiàng)的評(píng)分值.公式（5）中puser（a,y）表示用戶a對(duì)未評(píng)分項(xiàng)目y的預(yù)測(cè)評(píng)分值，NUa為用戶a的最近鄰居集.

3.2 基于項(xiàng)目的評(píng)分值預(yù)測(cè)

基于項(xiàng)目的評(píng)分值預(yù)測(cè)算法，先設(shè)置項(xiàng)目之間的相似度值θ，尋找與目標(biāo)項(xiàng)目相似度大于或等于θ的作為其最近鄰居集集合，再利用公式（6）預(yù)測(cè)評(píng)分值.公式（6）中pitem（a,y）表示用戶a對(duì)項(xiàng)目y的預(yù)測(cè)評(píng)分值，NIy為項(xiàng)目y的最近鄰居集合，為項(xiàng)目y用戶給出的平均評(píng)分值.

3.3 改進(jìn)算法的評(píng)分值預(yù)測(cè)

本文在第二部分改進(jìn)了基于用戶和項(xiàng)目的相似性度量方法，改進(jìn)后的算法雖然保證了相似度的計(jì)算更加準(zhǔn)確，但最近鄰集合的選擇條件更加苛刻，無(wú)論是用戶的最近鄰集合還是項(xiàng)目的最近鄰集合的規(guī)模都大大縮小了，容易對(duì)評(píng)分值的預(yù)測(cè)產(chǎn)生負(fù)面影響，為盡量減弱最近鄰集合縮小而產(chǎn)生的負(fù)面影響，本文采用動(dòng)態(tài)的權(quán)重系數(shù)將基于用戶和基于項(xiàng)目的評(píng)分值預(yù)測(cè)算法相結(jié)合.

公式（7）為用戶未評(píng)分項(xiàng)目最終預(yù)測(cè)值的計(jì)算方法，其中NumNUa表示用戶a的最近鄰居數(shù)量，NumUIy表示項(xiàng)目y的最近鄰居數(shù)量，p(a,y)為用戶a對(duì)項(xiàng)目y的最終評(píng)分值預(yù)測(cè)結(jié)果，按照這種方法，當(dāng)用戶a的最近鄰集合規(guī)模越大時(shí)，puser(a,y)所占比重越大；當(dāng)項(xiàng)目y的最近鄰集合規(guī)模越大時(shí)，pitem(a,y)所占比重越大.

4 實(shí)驗(yàn)仿真

筆者用c語(yǔ)言分別對(duì)基于用戶的協(xié)同過(guò)濾算法、基于項(xiàng)目的協(xié)同過(guò)濾算法、以及本文提出的改進(jìn)算法編程實(shí)現(xiàn)，采用GroupLens項(xiàng)目研究組收集的MovieLens數(shù)據(jù)集進(jìn)行測(cè)試.該數(shù)據(jù)集包括943名用戶對(duì)1682部電影的100,000項(xiàng)評(píng)分?jǐn)?shù)據(jù)，評(píng)分值的取值范圍為1-5；每位用戶至少有20個(gè)評(píng)分項(xiàng)；除訓(xùn)練集和測(cè)試集外還包括簡(jiǎn)單的用戶信息描述，如年齡、性別、職業(yè)等.實(shí)驗(yàn)中只用到訓(xùn)練集和測(cè)試集數(shù)據(jù)，用訓(xùn)練集數(shù)據(jù)產(chǎn)生預(yù)測(cè)評(píng)分，比較其與測(cè)試集數(shù)據(jù)的接近程度.

本實(shí)驗(yàn)采用平均絕對(duì)偏差MAE衡量算法的有效性，如公式（8）所示，pij是用戶i對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分，qij是用戶i對(duì)項(xiàng)目j的實(shí)際評(píng)分，Ni是預(yù)測(cè)得到的用戶i的評(píng)分項(xiàng)目數(shù)，MAEi是用戶i預(yù)測(cè)評(píng)分的絕對(duì)偏差，公式（9）中M是用戶個(gè)數(shù)，MAE則是算法在M個(gè)用戶預(yù)測(cè)評(píng)分上的平均絕對(duì)偏差.

實(shí)驗(yàn)采用5組數(shù)據(jù)集進(jìn)行測(cè)試，這5組數(shù)據(jù)的訓(xùn)練集都有80000條評(píng)分記錄，用戶——項(xiàng)目評(píng)分矩陣的數(shù)據(jù)密度為5.04%.測(cè)試結(jié)果如圖1所示，圖中縱坐標(biāo)為平均絕對(duì)偏差MAE，橫坐標(biāo)為5組數(shù)據(jù)集的名稱(chēng).從圖中可以看出，本文所提出的改進(jìn)協(xié)同過(guò)濾算法MAE值最小，算法預(yù)測(cè)評(píng)分值最接近于真實(shí)評(píng)分值.

圖1 三種協(xié)同過(guò)濾算法測(cè)試結(jié)果比較

5 結(jié)論

本文首先分析了傳統(tǒng)的協(xié)同過(guò)濾算法在計(jì)算用戶或項(xiàng)目之間的相似度時(shí)，由于兩用戶共同評(píng)分的項(xiàng)目數(shù)或同時(shí)給兩個(gè)項(xiàng)目共同評(píng)分的用戶數(shù)達(dá)不到一定的數(shù)量導(dǎo)致計(jì)算結(jié)果不準(zhǔn)確，為減少這部分?jǐn)?shù)據(jù)對(duì)計(jì)算結(jié)果造成的負(fù)面影響，本文為用戶和項(xiàng)目的相似度計(jì)算設(shè)置一個(gè)閾值，當(dāng)?shù)陀谶@個(gè)閾值時(shí)用戶或項(xiàng)目的相似度為0，高于該閾值時(shí)再使用Pearson相關(guān)性計(jì)算公式計(jì)算相似度；但另一方面，該閾值的設(shè)置可能會(huì)導(dǎo)致用戶或項(xiàng)目的近鄰數(shù)量減少，降低評(píng)分預(yù)測(cè)值的準(zhǔn)確性.采用將基于用戶和基于項(xiàng)目的評(píng)分預(yù)測(cè)值加權(quán)平均的方法，并通過(guò)用戶近鄰數(shù)量和項(xiàng)目近鄰數(shù)量動(dòng)態(tài)調(diào)整權(quán)重的方法，能夠有效提高預(yù)測(cè)的準(zhǔn)確性.

〔1〕王潔,湯小春.基于社區(qū)網(wǎng)絡(luò)內(nèi)容的個(gè)性化推薦算法研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(4):1248-1250.

〔2〕謝芳,王波.基于關(guān)聯(lián)規(guī)則的個(gè)性化推薦的改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用,2006(26):149-151.

〔3〕羅辛,歐陽(yáng)元新,熊璋,袁滿.通過(guò)相似度支持度優(yōu)化基于K近鄰的協(xié)同過(guò)濾算法[J].計(jì)算機(jī)學(xué)報(bào), 2010(8):1437-1444.

〔4〕曾春，邢春曉，周立柱.個(gè)性化服務(wù)技術(shù)綜述[J].軟件學(xué)報(bào),2002,13(10):1952-1961.

〔5〕Herlocker L J,Konstan A J,Riedl T J. Empirical analysis of design choices in neighborhood -based collaborative filtering algorithms[J].Information Retrieval,2002,5(4): 287-310.

TP301.6

A

1673-260X（2014）10-0028-03

合肥學(xué)院自然科學(xué)基金一般項(xiàng)目（14KY11ZR）