錢 刃，吳 云，孔廣黔

(貴州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025)

1 概 述

在互聯(lián)網(wǎng)高速發(fā)展的當(dāng)代，互聯(lián)網(wǎng)為每個人帶來的信息量也在高速增長，人們面對海量信息時很難從其中提取出對自己最有用的信息，就如在電商網(wǎng)站中用戶面對海量商品，很難選擇出最適合自己的商品，這樣既浪費(fèi)了用戶的時間，也使得網(wǎng)站的利益受損。為了使電商網(wǎng)站更好地銷售物品，方便用戶，推薦系統(tǒng)在各大電商網(wǎng)站得到了應(yīng)用，其中協(xié)同過濾算法是廣泛應(yīng)用的一種推薦算法。

協(xié)同過濾算法由Goldberg等提出[1],研究者將該算法應(yīng)用在一個文檔過濾系統(tǒng)中，系統(tǒng)要求用戶對文檔評分，其他用戶瀏覽時可以輸入查詢語句來過濾自己需要的文檔。之后協(xié)同過濾算法被GroupLens用于新聞推薦[2]，極大地促進(jìn)了協(xié)同過濾算法的發(fā)展，也迅速推動了協(xié)同過濾算法在Internet上的應(yīng)用及其相關(guān)研究。

協(xié)同過濾擁有如下優(yōu)勢：

(1)算法可以推薦任何資源，而不僅限于文本或者網(wǎng)站等。這是因為協(xié)同過濾算法需要考慮的只是用戶間對物品的評價，而無需關(guān)注資源的特性，這使得協(xié)同過濾算法的適用范圍變得十分寬廣，可以為用戶推薦任何資源。

(2)模型簡單，易于實現(xiàn)，各大網(wǎng)站可以方便地使用協(xié)同過濾算法來實現(xiàn)推薦，而不需要為此付出過高的代價。

(3)對用戶的推薦具有新穎性，不在是根據(jù)用戶歷史來重復(fù)推薦一個類別或幾個類別的物品。協(xié)同過濾算法因為是從相似用戶中尋找物品進(jìn)行推薦，所以算法可能會為用戶推薦該用戶歷史上從未接觸到的物品，并且該物品也符合用戶的喜好。這樣可以挖掘出更多的推薦項，不僅對用戶友好，而且有利于挖掘長尾物品[3]。

協(xié)同過濾算法在現(xiàn)階段的主要問題是稀疏性問題。由于網(wǎng)站特別是大型網(wǎng)站擁有大量的用戶和物品數(shù)量，而絕大多數(shù)用戶只會對極少的一些物品進(jìn)行評價，因此評分矩陣非常稀疏，在這種稀疏矩陣中，協(xié)同過濾算法很難準(zhǔn)確地找到相似用戶或者找到的相似用戶的評分稀少，最終使得推薦效率低下。

為了解決協(xié)同過濾算法由于稀疏性帶來的性能低下問題，提出了融合稀疏度加權(quán)的協(xié)同過濾算法。首先，對稀疏矩陣的稀疏度進(jìn)行計算評估；然后，在尋找相似用戶階段通過用戶密度與矩陣稀疏度對兩兩用戶間進(jìn)行稀疏度加權(quán)，這樣尋找的相似用戶更加準(zhǔn)確。

2 已有算法分析

目前，為了解決協(xié)同過濾算法中的稀疏度問題，研究人員提出了許多解決方法，大致分為三類：填充類、降維類和改進(jìn)相似度計算類。

填充類方法[4]通過在稀疏矩陣中添加數(shù)據(jù)從而使得矩陣不再稀疏，降低稀疏性對協(xié)同過濾算法的影響。最基本的填充方法是在稀疏矩陣中添加均值或者中位數(shù)等等。例如，李燦等在IALM和填充可信度的協(xié)同過濾算法及其并行化研究[5]中提出利用可擴(kuò)充的拉格朗日乘法對評分矩陣進(jìn)行填充；郝立燕等在基于填充和相似性信任因子的協(xié)同過濾推薦算法[6]中提出通過SOFT-IMPUTE算法[7]對矩陣進(jìn)行填充；Zheng L等提出建立一個興趣強(qiáng)度的時間衰減模型，并以此預(yù)測評分來填充矩陣[8]；康鐘榮提出通過貝葉斯模型預(yù)估評分來填充矩陣[9]。稀疏矩陣在經(jīng)過填充之后的確可以在一定程度上解決稀疏性所帶來的問題，但是填充算法大部分較為復(fù)雜，這樣就使得改進(jìn)后的協(xié)同過濾算法在效率上受到限制，不能為用戶頻繁更新推薦列表。

降維類方法[10]通過對稀疏矩陣進(jìn)行降維達(dá)到緩解矩陣稀疏度的目的。例如，Sarwar B等提出使用SVD算法將原始矩陣M分解成為三個矩陣U，Σ，VT：M≈UΣVT，然后在低階矩陣UΣ1/2上運(yùn)行協(xié)同過濾算法[11]；孫光福等引入用戶與物品間的時序關(guān)系，然后將時序關(guān)系融入到概率矩陣分解算法中，最后將矩陣分解降維[12]。降維類算法雖然降低了矩陣的稀疏度，但是在降維的過程中損失掉了更多相似信息，使算法更加難以找到相似用戶。

改進(jìn)相似度的方法[13]通過改進(jìn)相似度計算使得稀疏性對協(xié)同過濾算法的影響降低。這類方法既避免了填充類方法帶來的代價過大問題，也不像降維類方法那樣降低推薦性能。例如，張光衛(wèi)等提出的基于云模型的相似度計算方法[14]，算法避免使用傳統(tǒng)向量來計算相似度，因此在稀疏矩陣中改進(jìn)了協(xié)同算法的性能；Luo等提出全局相似度和局部相似度[15]，文中分別計算各個用戶間的局部相似度與全局相似度，然后將兩個相似度融合成最終的相似度來尋找相似用戶；Kaleli C等首先將用戶評分信息加入信息熵，然后在計算用戶相似度時加入信息熵來確定差異，衡量每個相似用戶的不確定性，從而改進(jìn)相似度計算公式[16]。在這些研究的基礎(chǔ)上，文中提出了融合稀疏度加權(quán)的協(xié)同過濾算法。算法通過矩陣稀疏度進(jìn)行加權(quán)來改進(jìn)相似度的計算，可以讓稀疏矩陣中的相似信息得到更有效的利用，從而提高協(xié)同過濾算法的性能。

3 模型定義

3.1 稀疏度加權(quán)

在協(xié)同過濾算法中，稀疏性問題嚴(yán)重制約著協(xié)同過濾算法的性能。由于稀疏矩陣中所包含的用戶相似信息十分有限，因此更有效地利用這些信息成為了提高協(xié)同算法性能的關(guān)鍵。對此，文中提出在計算用戶相似度時對稀疏度進(jìn)行加權(quán)。

首先,對稀疏度加權(quán)需要更準(zhǔn)確地計算稀疏度。傳統(tǒng)計算矩陣稀疏度的方法是將矩陣中未評價的評分單元數(shù)比上矩陣總單元數(shù)。然而這樣計算得到的矩陣稀疏度并不能準(zhǔn)確表示矩陣真實的稀疏度。因為影響矩陣稀疏度的因素并不是僅僅包含數(shù)據(jù)本身的稀疏度，它還包括用戶間的關(guān)系密度。關(guān)系密度是指用戶在各個項目上評價的集中程度，如果用戶在各個項目上的評價很分散，就會導(dǎo)致用戶間的關(guān)系密度很低，即原始評分矩陣中所包含的有效相似信息很少，就認(rèn)定矩陣十分稀疏。所以提出一個矩陣稀疏度的計算公式：

(1)

式1表示任意兩個用戶間共同評價的項目與兩個用戶評價項目總數(shù)的比值，在計算出所有比值后取平均值，利用平均值來衡量矩陣的稀疏度。

在得出矩陣的稀疏度以后，再計算其中任意兩個用戶i,j之間的關(guān)系密度與整個矩陣的稀疏度的比值并歸一化得到稀疏度加權(quán)項：

(2)

如果某兩個用戶之間的關(guān)系密度很大，那么這個權(quán)值就會很大，最終用戶間的相似度計算結(jié)果就能更準(zhǔn)確地表示這兩個用戶的相似度。

3.2 改進(jìn)后的協(xié)同過濾算法

文中在協(xié)同過濾算法中融入上述稀疏度加權(quán)項，從而更有效地利用評分矩陣中的有限信息。

首先建立用戶評分字典Dict_rt與用戶關(guān)系字典dict_rs。Dict_rt的結(jié)構(gòu)為{用戶ID：{物品ID:用戶評分,…},…}，文中將所有原始數(shù)據(jù)結(jié)構(gòu)化存儲在用戶評分字典Dict_rt中。dict_rs的結(jié)構(gòu)為{用戶ID:{用戶ID:關(guān)系密度,…},…}，文中在用戶評分字典Dict_rt的基礎(chǔ)上利用式1得出整個矩陣的稀疏度，然后對所有二元組合的用戶使用式2得到用戶間的關(guān)系密度，將所有關(guān)系密度存儲在字典dict_rs中。

接下來計算用戶相似度，相似度計算方法有許多，其中比較常用的有：

(1)余弦距離。

余弦距離通過計算用戶之間的余弦值來衡量用戶之間的相似性，在評分矩陣中每個用戶被看作一個向量，向量的維度就是物品數(shù)，用戶對各個物品的評分就是用戶向量在相應(yīng)維度上的值，計算公式如下：

(3)

(2)皮爾遜相關(guān)系數(shù)。

通過協(xié)方差與標(biāo)準(zhǔn)差來評判兩個向量的相似性，計算公式如下：

(4)

在計算用戶相似度時，利用融合稀疏度加權(quán)項來改進(jìn)相似度計算公式，因此改進(jìn)后的余弦距離相似度計算公式為：

(5)

改進(jìn)后的皮爾遜相關(guān)系數(shù)相似度計算公式為:

sim(i,j)=

(6)

算法建立用戶相似度字典Dict_s存儲用戶相似度,字典結(jié)構(gòu)為{用戶ID：{用戶ID：相似度,…},…}，利用式5或式6計算用戶相似度，將計算得到的相似度存入用戶相似度字典Dict_s中。對用戶相似度排序后就可以進(jìn)行評分預(yù)測與推薦。

具體算法步驟如下：

(1)根據(jù)式1計算矩陣稀疏度；

(2)根據(jù)式2計算用戶間關(guān)系密度與整個矩陣的稀疏度的比值，并歸一化得到稀疏度加權(quán)項；

(3)使用式5和式6計算各個用戶間的相似度；

(4)找到相似用戶后，預(yù)測評分，進(jìn)行推薦；

(5)計算推薦結(jié)果的準(zhǔn)確率和覆蓋率。

4 實 驗

4.1 數(shù)據(jù)集

實驗使用MovieLens公開數(shù)據(jù)集作為實驗數(shù)據(jù)集，該數(shù)據(jù)集中包含1 000個用戶對3 900部電影的10萬條評分記錄，其中每個用戶的評價記錄在20條以上，用戶評分范圍在1～5之間。

4.2 實驗環(huán)境與步驟

實驗采用的計算機(jī)配置為I5處理器，2 GB內(nèi)存，500 GB硬盤，Win7操作系統(tǒng)，步驟如下：

(1)將數(shù)據(jù)集分為兩部分，一部分作為測試數(shù)據(jù)集，占比為五分之一，剩下的為訓(xùn)練數(shù)據(jù)集。

(2)應(yīng)用文中算法，分別通過式5與式6進(jìn)行改進(jìn)加權(quán)，以推薦準(zhǔn)確率和推薦覆蓋率作為評價標(biāo)準(zhǔn)。

(3)實驗結(jié)果取相似用戶的數(shù)量為變量，以10個相似用戶為基礎(chǔ)，以5個相似用戶為梯度增加到50個。計算推薦準(zhǔn)確率與覆蓋率。

4.3 實驗評估標(biāo)準(zhǔn)

準(zhǔn)確率是指在推薦條目中，用戶喜歡的條目數(shù)量與推薦的條目總數(shù)量的比值，其計算公式如下：

(7)

其中，R(u)為向用戶推薦的條目總數(shù)；T(u)為推薦條目中用戶喜歡的條目。

覆蓋率可以反映出算法發(fā)現(xiàn)長尾物品的能力。長尾物品指在物品中用戶較少評價的一些物品，覆蓋率越高，算法發(fā)現(xiàn)長尾物品的能力越強(qiáng)，具體是指在推薦條目中用戶喜歡的條目數(shù)量與所有用戶喜歡的條目數(shù)量之比，計算公式如下：

(8)

其中，R(u)為向用戶推薦的推薦條目總數(shù)；I為整個數(shù)據(jù)集中的物品數(shù)。

4.4 實驗結(jié)果的比較與分析

實驗首先對余弦相似度進(jìn)行加權(quán)改進(jìn)，和傳統(tǒng)協(xié)同過濾算法進(jìn)行比較，以驗證文中算法的有效性，實驗結(jié)果如圖1和圖2所示。

圖1 采用余弦相似度時推薦準(zhǔn)確率的比較

圖2 采用余弦相似度時推薦覆蓋率的比較

從結(jié)果可以看出，改進(jìn)后的協(xié)同過濾算法的準(zhǔn)確率和召回率相對傳統(tǒng)的協(xié)同過濾算法都得到了提高。當(dāng)取得相似用戶增加時，兩種算法的覆蓋率有所降低，這是因為在取得更多用戶之后，得到的推薦列表中的物品將更加集中在熱度很高的物品上，但是改進(jìn)后的協(xié)同過濾算法的召回率依然高于傳統(tǒng)協(xié)同過濾算法。實驗說明經(jīng)過稀疏度加權(quán)之后，算法更有效地利用了原始稀疏矩陣中的信息，使得在計算尋找相似用戶時更加準(zhǔn)確有效。而尋找到相似用戶是協(xié)同過濾算法的核心，協(xié)同過濾算法正是在相似用戶間進(jìn)行推薦。算法保證了尋找到相似用戶的有效性，因此提高了準(zhǔn)確率和覆蓋率。

實驗繼續(xù)對皮爾遜相關(guān)系數(shù)相似度進(jìn)行加權(quán)改進(jìn)，同樣與傳統(tǒng)協(xié)同過濾算法進(jìn)行比較，實驗結(jié)果如圖3和圖4所示。

結(jié)果表明，算法同樣提高了推薦準(zhǔn)確率和覆蓋率，證明通過矩陣稀疏度加權(quán)來尋找相似用戶是行之有效的。通過矩陣稀疏度加權(quán)，使協(xié)同過濾算法在稀疏矩陣中更有效地利用評分信息來找到相似用戶，從而提高了改進(jìn)算法的準(zhǔn)確率和覆蓋率。

圖3 采用皮爾遜相似系數(shù)時推薦準(zhǔn)確率的比較

圖4 采用皮爾遜相似系數(shù)時推薦覆蓋率的比較

5 結(jié)束語

協(xié)同過濾算法的性能受到評分矩陣稀疏度問題的制約，稀疏的評分矩陣導(dǎo)致尋找相似用戶困難或?qū)ふ业降南嗨朴脩舨粶?zhǔn)確，最終影響協(xié)同過濾算法的性能。文中通過矩陣稀疏度加權(quán)來改進(jìn)協(xié)同過濾算法，從而更有效地利用了用戶評價信息，避免了稀疏性帶來的問題，推薦結(jié)果可以更準(zhǔn)確地體現(xiàn)用戶的喜好程度。實驗結(jié)果表明，該算法可以有效提高推薦的準(zhǔn)確率與覆蓋率。