協(xié)同過濾推薦系統(tǒng)中數(shù)據(jù)稀疏問題的解決

摘 要：介紹了現(xiàn)有協(xié)同過濾推薦的幾種主要算法。它們對(duì)數(shù)據(jù)稀疏性問題都有一定的緩和作用。通過在數(shù)據(jù)集MovieLens上的實(shí)驗(yàn)，分析了各個(gè)算法在不同稀疏度下的推薦質(zhì)量，為針對(duì)不同數(shù)據(jù)稀疏度的系統(tǒng)實(shí)現(xiàn)提供了可靠依據(jù)。

關(guān)鍵詞：電子商務(wù)； 推薦系統(tǒng)； 協(xié)同過濾； 數(shù)據(jù)稀疏； 相似性

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0094-04

隨著信息技術(shù)的發(fā)展和信息資源的膨脹，對(duì)于用戶來說，尋找自己感興趣的商品信息已經(jīng)成為一件困難且昂貴的事情。因此，電子商務(wù)的推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)是電子商務(wù)個(gè)性化服務(wù)的重要組成部分。個(gè)性化推薦系統(tǒng)包括熱銷商品推薦、新品推薦、相關(guān)產(chǎn)品推薦和與用戶群同興趣推薦等。目前，許多電子商務(wù)網(wǎng)站都已經(jīng)使用了推薦系統(tǒng)，如Amazon、 CDNow、 Drugstore 和 Moviefinder 等。推薦系統(tǒng)利用數(shù)據(jù)挖掘技術(shù)在電子商務(wù)網(wǎng)站中幫助顧客訪問感興趣的產(chǎn)品信息并產(chǎn)生推薦。這些系統(tǒng)對(duì)擴(kuò)大銷售量，增加交叉銷售額，提高顧客忠誠度等方面都有較大貢獻(xiàn)。本文主要討論與用戶群同興趣推薦。在該領(lǐng)域最成功的技術(shù)是協(xié)同過濾推薦技術(shù)。

協(xié)同過濾技術(shù)主要是利用目標(biāo)用戶對(duì)產(chǎn)品的歷史評(píng)價(jià)與其他用戶相匹配，以預(yù)測用戶對(duì)未評(píng)價(jià)產(chǎn)品的評(píng)價(jià)，從而產(chǎn)生高效的推薦。在預(yù)測目標(biāo)用戶對(duì)某產(chǎn)品的評(píng)價(jià)前，首先需要根據(jù)該用戶的歷史評(píng)分和反饋信息，選擇目標(biāo)用戶的最近鄰居集，即與目標(biāo)用戶興趣相似的用戶集合（圖1）。在選定最近鄰居之后，根據(jù)鄰居對(duì)某些產(chǎn)品的評(píng)分對(duì)目標(biāo)用戶的評(píng)分進(jìn)行預(yù)測，產(chǎn)生推薦。

圖1 最近鄰居的選擇

雖然協(xié)同過濾技術(shù)得到了廣泛應(yīng)用，但是它仍然存在一些弊端。主要有數(shù)據(jù)稀疏性問題、系統(tǒng)可擴(kuò)展性問題和同義詞問題。本文主要討論數(shù)據(jù)稀疏性問題。

1 協(xié)同過濾推薦技術(shù)與數(shù)據(jù)稀疏性

協(xié)同過濾推薦技術(shù)是目前推薦系統(tǒng)中最成功的技術(shù)；它基于一個(gè)假設(shè)。如果用戶對(duì)一些產(chǎn)品的評(píng)分比較相似，則對(duì)其他產(chǎn)品的評(píng)分也比較相似［1］。

傳統(tǒng)的協(xié)同過濾推薦技術(shù)，主要是通過尋找與目標(biāo)用戶興趣愛好相似的用戶，并根據(jù)其喜愛的產(chǎn)品，對(duì)目標(biāo)用戶喜愛的產(chǎn)品進(jìn)行預(yù)測，產(chǎn)生推薦。例如，對(duì)一個(gè)電影網(wǎng)站的某個(gè)用戶推薦電影，首先尋找與目標(biāo)用戶喜愛相同電影的用戶群，即最近鄰居集；然后，將鄰居用戶喜愛且目標(biāo)用戶未知的電影按特定的方法推薦給目標(biāo)用戶。

下面以向用戶推薦電影為例，具體介紹推薦過程。假設(shè)若兩個(gè)用戶喜愛相同電影的數(shù)目越多，這兩個(gè)用戶就越相似。首先要尋找目標(biāo)用戶的最近鄰居集。目前，大多數(shù)的協(xié)同過濾推薦系統(tǒng)是通過相似性計(jì)算來得到最近鄰居集的。因此，為了衡量用戶之間的相似性，首先將用戶和電影信息進(jìn)行整理，得到用戶—電影矩陣A（i， j）（表1）。

表1 用戶—電影矩陣

其中，n行代表n個(gè)用戶；m列代表m個(gè)電影；元素Rij代表用戶i對(duì)電影j的評(píng)分。評(píng)分代表了用戶對(duì)電影的喜愛程度。衡量兩個(gè)用戶i與j之間相似性時(shí)，首先得到用戶i與j的所有評(píng)分電影和評(píng)分?jǐn)?shù)據(jù)；然后用不同的方法計(jì)算得到兩個(gè)用戶之間的相似性。下面介紹幾種相似性的計(jì)算方法。

計(jì)算相似性比較成熟的算法主要有：

最后，根據(jù)預(yù)測評(píng)分的大小，對(duì)電影進(jìn)行推薦。

由以上推薦過程容易看出，用戶的評(píng)分信息對(duì)相似性的確定至關(guān)重要。因此，用戶評(píng)分?jǐn)?shù)據(jù)稀疏，造成用戶相似性計(jì)算誤差大，用戶評(píng)分預(yù)測的準(zhǔn)確性降低。例如，一個(gè)出售書籍的商務(wù)網(wǎng)站，擁有兩百萬書籍，然而每個(gè)用戶評(píng)價(jià)的書籍大多不超過100本。這樣，得到的用戶—書籍矩陣則是一個(gè)稀疏矩陣。顯然，基于這樣的稀疏矩陣計(jì)算得來的用戶相似性是不準(zhǔn)確的。因此，隨著用戶和產(chǎn)品數(shù)量的增加，數(shù)據(jù)的稀疏程度增加，系統(tǒng)推薦質(zhì)量則急劇下降。 

數(shù)據(jù)稀疏問題嚴(yán)重制約著協(xié)同過濾推薦系統(tǒng)的發(fā)展。對(duì)于大型商務(wù)網(wǎng)站來說，由于產(chǎn)品和用戶數(shù)量都很龐大，用戶評(píng)分產(chǎn)品一般不超過產(chǎn)品總數(shù)的1％［2］，兩個(gè)用戶共同評(píng)分的 產(chǎn)品更是少之又少，解決數(shù)據(jù)稀疏問題是提高推薦質(zhì)量的關(guān)鍵。

2 幾種主要的協(xié)同過濾算法

為了提高推薦質(zhì)量，許多研究人員都試圖緩和數(shù)據(jù)稀疏問題。他們從不同的角度對(duì)用戶和產(chǎn)品信息進(jìn)行分析、處理，降低數(shù)據(jù)的稀疏程度。這些算法各有利弊。

2．1 基于項(xiàng)目的協(xié)同過濾推薦算法

傳統(tǒng)的協(xié)同過濾推薦算法是通過計(jì)算用戶之間的相似性，尋找與目標(biāo)用戶興趣相似的一組用戶，作為目標(biāo)用戶的最近鄰居。然而，由于數(shù)據(jù)的極端稀疏性，兩個(gè)用戶共同評(píng)分的產(chǎn)品非常少，得到用戶之間的相似性很有可能為0。因此，出現(xiàn)了基于項(xiàng)目的協(xié)同過濾推薦技術(shù)。

基于項(xiàng)目的協(xié)同過濾推薦算法［1，3，4］，從產(chǎn)品角度進(jìn)行分析，尋找與目標(biāo)產(chǎn)品相似的產(chǎn)品集合，然后進(jìn)行預(yù)測和推薦。它基于一個(gè)假設(shè)，即用戶對(duì)與其感興趣產(chǎn)品相似的產(chǎn)品也感興趣。由于項(xiàng)目間的相似性相對(duì)穩(wěn)定，而通常項(xiàng)目的數(shù)量比用戶數(shù)量少，這樣可以減少計(jì)算量，降低數(shù)據(jù)稀疏性。

算法步驟：

(1)通過相似性算法，計(jì)算列向量的余弦相似性，即產(chǎn)品向量的相似性。

(2)選擇相似性最高且沒有被目標(biāo)用戶評(píng)價(jià)過的前M個(gè)產(chǎn)品，作為產(chǎn)品的鄰居集合Mp。

(3)對(duì)鄰居集合中產(chǎn)品的評(píng)分進(jìn)行加權(quán)求和，得到目標(biāo)用戶對(duì)目標(biāo)產(chǎn)品的預(yù)測評(píng)分

2．2 降低矩陣維數(shù)的技術(shù)

降低矩陣維數(shù)的技術(shù)可對(duì)原始稀疏數(shù)據(jù)直接進(jìn)行數(shù)據(jù)處理，降低數(shù)據(jù)稀疏性。主要算法有單值分解、聚類等。

2．2．1 單值分解

單值分解算法利用矩陣的單值分解原理，對(duì)用戶—產(chǎn)品矩陣進(jìn)行分解，從而降低矩陣的維數(shù)，抽取出主要信息［2，5］。

算法步驟：

(1)使用每個(gè)產(chǎn)品的平均評(píng)分——列平均值——填充矩陣中的未評(píng)分項(xiàng)。

(2)利用用戶的平均評(píng)分——行平均值——進(jìn)行標(biāo)準(zhǔn)化，產(chǎn)生矩陣R。

(3)對(duì)R進(jìn)行單值分解，得到

(6)根據(jù)同一產(chǎn)品被鄰居評(píng)分的頻繁程度產(chǎn)生推薦。

從算法步驟可以看出，通過單值分解得到的較低維的UkS1/2k矩陣比原始用戶—產(chǎn)品稠密，并且抽取出了所有用戶信息。在這個(gè)矩陣上進(jìn)行相似性計(jì)算，可以減少計(jì)算量，提高在線推薦速度，并且提高推薦質(zhì)量。實(shí)驗(yàn)表明，該算法在分解矩陣過程中，不可避免數(shù)據(jù)遺失。當(dāng)原始矩陣極度稀疏時(shí)，單值分解算法試驗(yàn)結(jié)果并不理想。算法需要較大的計(jì)算量，較少的存儲(chǔ)空間。

2．2．2 聚類

單值分解通過矩陣運(yùn)算降低數(shù)據(jù)稀疏性，聚類［6－9］則是通過一些聚類算法將產(chǎn)品或用戶聚成若干具有共同性質(zhì)的類；然后在小的聚類數(shù)據(jù)中產(chǎn)生推薦。

(1)取前K個(gè)用戶作為K個(gè)獨(dú)立的聚類質(zhì)心；剩余的每個(gè)用戶與其最近質(zhì)心進(jìn)行比較。

(2)在形成聚類質(zhì)心的基礎(chǔ)上，重新計(jì)算聚類的質(zhì)心。

(3)聚類內(nèi)部的成員關(guān)系被重新估算。重復(fù)(1)－(3)，直到產(chǎn)生的K個(gè)聚類不再變化。

(4)在目標(biāo)用戶所在的類中進(jìn)行用戶相似性計(jì)算，主要運(yùn)用第一部分中的相關(guān)相似性方法計(jì)算，得到最近鄰居集合。

(5)對(duì)最近鄰居的評(píng)分?jǐn)?shù)據(jù)進(jìn)行加權(quán)處理：

(6)預(yù)測產(chǎn)生后，根據(jù)預(yù)測評(píng)分的高低對(duì)目標(biāo)用戶進(jìn)行推薦。

2．3 基于內(nèi)容的協(xié)同過濾算法

2．1、2．2節(jié)中介紹的算法都是建立在用戶對(duì)產(chǎn)品評(píng)分的基礎(chǔ)上，在一定程度上都緩和了數(shù)據(jù)稀疏帶來的問題。基于產(chǎn)品內(nèi)容的協(xié)同過濾算法［11］與前面介紹的幾種算法的不同之處，是考慮到了產(chǎn)品本身的信息。由于增加了信息量，可以有效提高推薦質(zhì)量。

單純的基于產(chǎn)品內(nèi)容的算法，根據(jù)單個(gè)用戶已評(píng)價(jià)產(chǎn)品的內(nèi)容信息，如電影的導(dǎo)演、演員、類型等，建立用戶興趣模型，進(jìn)而產(chǎn)生推薦。這樣的算法存在一些弊端：①由于通常獲得的只是產(chǎn)品的部分信息，其他一些未知信息很有可能影響用戶的行為，這就造成了推薦的不準(zhǔn)確。②用戶的喜好通常是多樣的，而單個(gè)用戶評(píng)分的產(chǎn)品數(shù)量卻非常少。這樣就使推薦局限于特定類型的產(chǎn)品上。

基于內(nèi)容的協(xié)同過濾技術(shù)則不同。目前這方面的算法主要有線性結(jié)合型和連續(xù)結(jié)合型兩個(gè)類型，如圖2、3所示。

線性結(jié)合型算法步驟：

(1)通過歷史評(píng)價(jià)的產(chǎn)品內(nèi)容信息，建立用戶興趣模型。

(2)比較用戶模型，得到基于內(nèi)容的用戶相似性。

(3)根據(jù)用戶—產(chǎn)品評(píng)分矩陣，得到基于評(píng)分的用戶相似性。

(4)將兩個(gè)相似性進(jìn)行線性組合，得到用戶相似性。

(5)根據(jù)相似性，得到目標(biāo)用戶的最近鄰居集。

(6)通過鄰居集對(duì)目標(biāo)用戶進(jìn)行評(píng)分預(yù)測和推薦。這個(gè)過程可以用2.1、2.2節(jié)介紹的算法進(jìn)行。

連續(xù)結(jié)合型算法步驟：

(1)通過歷史評(píng)價(jià)的產(chǎn)品內(nèi)容信息，建立用戶興趣模型。

(2)根據(jù)每個(gè)用戶興趣模型的相互比較，獲得目標(biāo)用戶的最近鄰居集。

(3)將符合目標(biāo)用戶或其鄰居興趣模型的產(chǎn)品推薦給目標(biāo)用戶。

以上兩種算法混合了協(xié)同過濾算法和基于內(nèi)容的推薦算法，緩和了傳統(tǒng)協(xié)同過濾算法沒有考慮產(chǎn)品本身信息的缺陷，也解決了基于內(nèi)容的推薦算法中單個(gè)用戶信息稀少的問題。然而，產(chǎn)品信息的獲取和存儲(chǔ)，是一個(gè)困難且昂貴的問題。

3 實(shí)驗(yàn)結(jié)果及其分析

3．1 數(shù)據(jù)集

本文采用 MovieLens 站點(diǎn)提供的數(shù)據(jù)集(http://mo￣vielens.umn.edu/)。MovieLens 是一個(gè)基于 Web 的研究型推薦系統(tǒng)，用于接收用戶對(duì)電影的評(píng)分，并提供相應(yīng)的電影推薦列表。該站點(diǎn)現(xiàn)在已經(jīng)擁有43 000個(gè)用戶和35 000部電影。隨機(jī)選擇了100 000個(gè)評(píng)分。其中每個(gè)用戶至少對(duì)20部電影進(jìn)行了評(píng)分。

3．2 度量標(biāo)準(zhǔn)

本文采用平均絕對(duì)偏差（Mean Absolute Error，MAE）作為評(píng)價(jià)推薦系統(tǒng)預(yù)測質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)。MAE可以直觀地對(duì)預(yù)測質(zhì)量進(jìn)行度量，是最常用的一種方法。MAE通過計(jì)算預(yù)測的用戶評(píng)分與實(shí)際評(píng)分之間的偏差度量預(yù)測的準(zhǔn)確性；MAE越小，預(yù)測質(zhì)量越高。

3．3 實(shí)驗(yàn)參數(shù)

為了能更好地評(píng)估算法性能，在實(shí)驗(yàn)中根據(jù)各個(gè)算法的特點(diǎn)，對(duì)各個(gè)算法的參數(shù)進(jìn)行了一定的設(shè)置。

在基于項(xiàng)目（Itembased）的算法中，運(yùn)用余弦相似性進(jìn)行相似性計(jì)算，鄰居選擇為30個(gè)。SVD中，同樣運(yùn)用余弦相似性進(jìn)行相似性計(jì)算，并統(tǒng)一將數(shù)據(jù)降維至100維。在聚類算法中，選擇聚類數(shù)K=50。Ucontent 和 Icontent 都是基于內(nèi)容的線性結(jié)合模型算法。其中，Icontent是與基于項(xiàng)目的協(xié)同過濾技術(shù)進(jìn)行線性結(jié)合；Ucontent是與基于用戶的協(xié)同過濾技術(shù)進(jìn)行線性結(jié)合。

3．4 實(shí)驗(yàn)結(jié)果及分析

通過對(duì)上述算法在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)，得到每個(gè)算法在不同數(shù)據(jù)稀疏程度下的MAE值，如圖4所示。

實(shí)驗(yàn)中對(duì)基于項(xiàng)目的協(xié)同過濾算法（Itembased CF）、基于單值分解的協(xié)同過濾算法（SVD）、基于聚類的協(xié)同過濾算法（Cluster CF）和基于內(nèi)容的協(xié)同過濾算法（Contentbased）進(jìn)行了研究。通過數(shù)據(jù)稠密程度為0.2－0.9的變化，研究數(shù)據(jù)稀疏程度對(duì)算法性能的影響。

從圖4中可以看出，隨著數(shù)據(jù)稀疏程度的減小，即數(shù)據(jù)稠密程度的增加，各算法的MAE值都有所降低。這充分說明數(shù)據(jù)稀疏對(duì)算法性能的影響十分嚴(yán)重。

在實(shí)驗(yàn)的五個(gè)算法中，當(dāng)數(shù)據(jù)集稀疏程度小于0.4或大于0.7時(shí)，SVD的MAE值最小，性能也最好。也就是說，SVD能有效減少數(shù)據(jù)稀疏對(duì)系統(tǒng)性能的影響。當(dāng)數(shù)據(jù)稀疏程度在0.4－0.7時(shí)，聚類算法的優(yōu)勢(shì)則較明顯。

4 結(jié)束語

協(xié)同過濾推薦系統(tǒng)已經(jīng)被廣泛應(yīng)用于電子商務(wù)、電子圖書館等眾多領(lǐng)域，隨著用戶和產(chǎn)品數(shù)量的不斷增加，傳統(tǒng)算法的許多缺點(diǎn)逐漸暴露了出來。本文通過對(duì)幾種主要的緩解數(shù)據(jù)稀疏性影響的算法的研究和實(shí)驗(yàn)，對(duì)各種算法在不同數(shù)據(jù)稀疏程度下的算法性能進(jìn)行了評(píng)估，針對(duì)不同稀疏程度數(shù)據(jù)的系統(tǒng)實(shí)現(xiàn)提供了可靠的依據(jù)。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。