融合稀疏度加權(quán)的協(xié)同過濾算法研究

錢 刃，吳 云，孔廣黔

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

1 概 述

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

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

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

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

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

(3)對(duì)用戶的推薦具有新穎性，不在是根據(jù)用戶歷史來重復(fù)推薦一個(gè)類別或幾個(gè)類別的物品。協(xié)同過濾算法因?yàn)槭菑南嗨朴脩糁袑ふ椅锲愤M(jìn)行推薦，所以算法可能會(huì)為用戶推薦該用戶歷史上從未接觸到的物品，并且該物品也符合用戶的喜好。這樣可以挖掘出更多的推薦項(xiàng)，不僅對(duì)用戶友好，而且有利于挖掘長(zhǎng)尾物品[3]。

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

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

2 已有算法分析

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

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

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

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

3 模型定義

3.1 稀疏度加權(quán)

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

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

(1)

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

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

(2)

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

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

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

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

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

(1)余弦距離。

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

(3)

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

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

(4)

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

(5)

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

sim(i,j)=

(6)

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

具體算法步驟如下：

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

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)環(huán)境與步驟

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

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

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

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

4.3 實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)

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

(7)

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

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

(8)

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

4.4 實(shí)驗(yàn)結(jié)果的比較與分析

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

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

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

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

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

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

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

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

5 結(jié)束語

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