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

王竹婷

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

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

王竹婷

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

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

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

1 引言

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

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

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

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

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

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

表1 用戶-項目評分矩陣

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

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

2.2.1 用戶的相似度

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

公式（1）中，sim（i，a）表示用戶i和用戶a之間的相似性，Nai表示用戶a和用戶i共同評分過的項目集分別表示用戶i和用戶a的平均評分值.該公式通過兩用戶共同評分過的項目評分值，計算兩者之間的相似度.

2.2.2 項目的相似性

項目之間的相似性表示用戶對兩個不同項目同時發(fā)生興趣的程度，計算公式如下：

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

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

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

2.4 相似性度量方法的改進

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

2.4.1 改進的基于用戶的相似性度量

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

2.4.2 改進的基于項目的相似性度量

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

3 協(xié)同過濾算法預(yù)測評分值

3.1 基于用戶的評分值預(yù)測

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

3.2 基于項目的評分值預(yù)測

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

3.3 改進算法的評分值預(yù)測

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

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

4 實驗仿真

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

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

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

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

5 結(jié)論

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

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

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

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

〔4〕曾春，邢春曉，周立柱.個性化服務(wù)技術(shù)綜述[J].軟件學(xué)報,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é)基金一般項目（14KY11ZR）