摘要：針對協(xié)同過濾中存在的稀疏性問題，提出改進(jìn)方法——BAS算法。該算法結(jié)合貝葉斯度量方法和奇異值降維分解方法，利用傳統(tǒng)的基于奇異值分解獲得活躍用戶的鄰居，通過改進(jìn)后的相似性度量方法得出預(yù)測值。對改進(jìn)后的算法進(jìn)行理論分析和實驗對比。結(jié)果表明，該方法在所用數(shù)據(jù)集上能夠有效緩解數(shù)據(jù)稀疏性問題，并且改善推薦精度的準(zhǔn)確性，在一定程度上提高了推薦引擎的推薦質(zhì)量。

關(guān)鍵詞關(guān)鍵詞：推薦引擎；協(xié)同過濾算法；數(shù)據(jù)稀疏；奇異值分解

DOIDOI：10.11907/rjdk.104179

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2015）002007404

作者簡介作者簡介：蘇楊茜（1988-），女，廣西南寧人，中南民族大學(xué)計算機(jī)科學(xué)學(xué)院碩士研究生，研究方向為軟件工程與復(fù)雜網(wǎng)絡(luò)。

0引言

協(xié)同過濾（Collaborative Filtering ，CF）是目前推薦引擎中應(yīng)用最廣泛的個性化推薦技術(shù)之一。其通過研究用戶歷史行為，分析用戶興趣（或項目屬性），為用戶建立模型，依據(jù)活躍用戶對項目的評價，來尋找與活躍用戶興趣相同的用戶組，然后用該用戶組中評價比較高的一組項目序列為活躍用戶作出相關(guān)推薦＼[12＼]。

現(xiàn)有協(xié)同過濾算法分為基于用戶的協(xié)同過濾、基于項目的協(xié)同過濾和基于模型的協(xié)同過濾＼[3＼]?；谟脩舻膮f(xié)同過濾是向用戶推薦與其興趣相似的其他用戶喜歡的物品，依據(jù)的是用戶之間的相似度；基于項目的協(xié)同過濾是向用戶推薦與其先前喜歡的項目相似的項目，依據(jù)的是項目之間的相似度；基于模型的協(xié)同過濾則依據(jù)已有的部分成熟算法建立模型，然后為用戶進(jìn)行推薦，常見的有聚類、關(guān)聯(lián)規(guī)則、貝葉斯網(wǎng)絡(luò)等。

1協(xié)同過濾中的數(shù)據(jù)稀疏性問題及解決方法

協(xié)同過濾算法推薦需利用用戶對項目資源的評價信息矩陣。如果用戶對項目資源的評價不夠多，則無法產(chǎn)生精確的推薦，導(dǎo)致用戶體驗不佳，這就是協(xié)同過濾算法中存在的數(shù)據(jù)稀疏性問題。信息矩陣的數(shù)據(jù)稀疏性本質(zhì)上是由高維數(shù)據(jù)引起的，是協(xié)同過濾算法的經(jīng)典問題。現(xiàn)有解決數(shù)據(jù)稀疏性方法主要有聚類分析＼[4， 5＼]、奇異值分解等。

2改進(jìn)的BAS（Bayes After SVD）算法

協(xié)同過濾技術(shù)的關(guān)鍵是找到最優(yōu)鄰居集合，要解決計算信息矩陣稀疏性問題，可以從兩個方面著手：①尋找一個更為精確的相似性度量方法，在同等稀疏程度情況下，得到更好的鄰居集合；②對計算信息矩陣進(jìn)行降維處理，并填補(bǔ)計算信息矩陣中的缺失項，使其成為一個稠密的計算信息矩陣，為協(xié)同過濾后的計算提供更多的數(shù)據(jù)源，從而提高推薦質(zhì)量。

2.1主要技術(shù)

（1）貝葉斯（Bayes）度量。

sim（i，j）=F（i·j）F（i）（F（j））α（1）

F（i）是對項目i感興趣的用戶數(shù)目。α為懲罰因子，取值0～1，在實際應(yīng)用中以物品的熱度來進(jìn)行度量。對熱銷用品，與其有關(guān)聯(lián)的物品越多，則α越接近1。需要注意的是，當(dāng)α=0時，則變成了傳統(tǒng)的貝葉斯公式；當(dāng)α=1時，則所有物品都影響物品間相似度。

（2）奇異值分解（SVD）。計算矩陣R代表用戶的評分行為，其中R[u][i]表示用戶u對項目i的評分。首先將計算矩陣R分解為兩個低維相乘矩陣。

R=PTQ（2）

其中，P∈Rf×m和Q∈Rf×n是兩個降維后的矩陣。

用戶u對項目i的評價預(yù)測值R（u，i）=rui，可通過下式計算：

rui=∑fpufqif（3）

其中，puf=P（u，f），qif=Q（i，f）。矩陣分解思想為利用最小化RMSE思想，直接通過訓(xùn)練集中所觀察的數(shù)據(jù)對P、Q矩陣進(jìn)行學(xué)習(xí)。在利用RMSE作為評測指標(biāo)時，加入防止過擬合項λ（‖pu‖2+‖qi‖2），其中λ是正則化參數(shù)，從而得到損失函數(shù)。

C（p，q）=∑（u，i）∈Train（rui-∑Ff=1pufqif）2+λ（‖pu‖2+‖qi‖2（4）

2.2算法過程

首先采用SVD方法預(yù)測未打分的評分預(yù)測值，得到一個稠密的計算矩陣；然后，利用填補(bǔ)后的計算矩陣，配合加入懲罰因子的貝葉斯公式，采用獲取最優(yōu)鄰居集合的方法，求取實際未評分的項目的預(yù)測值，該方法稱為BAS（Bayes After SVD）算法。BAS算法流程如下：①獲取用戶項目信息矩陣，將計算矩陣R規(guī)范為Rn；②利用SVD對信息矩陣進(jìn)行降維處理，同時進(jìn)行缺失項填充；③選中一個用戶，利用修正后的貝葉斯公式求得活躍用戶與其他用戶的相似度；④依照與活躍用戶的相似性度量大小進(jìn)行排序，選擇前N個用戶作為活躍用戶的最優(yōu)鄰居；⑤求出每個活躍用戶i對未評分項目j的預(yù)測值。

3算法實現(xiàn)與實驗分析

3.1評價指標(biāo)

（1）均方根誤差（RMSE）和平均絕對誤差（MAE）。評分預(yù)測的準(zhǔn)確度一般通過均方根誤差（RMSE）和平均絕對誤差（MAE）計算。對于測試集中的一個用戶u和項目i，令rui是用戶u對項目i的實際評分，而r'ui是推薦引擎計算出的預(yù)測評分，則：

RMSE=∑u，i∈T（rui-rui）2|T|（5）

MAE采用絕對值計算預(yù)測誤差，定義為：

MAE=∑u，i∈T|（rui-rui）||T|（6）

（2）Top N推薦。Top N推薦的預(yù)測準(zhǔn)確率通常通過準(zhǔn)確率（precision）/召回率（recall）來進(jìn)行度量。

令R（u）表示用戶u推薦N個物品，而T（u）是用戶在測試集上的行為列表，則推薦結(jié)果的召回率為：

Recall=∑u∈U|R（u）∩T（u）|∑u∈U|T（u）|（7）

推薦結(jié)果的準(zhǔn)確率為：

Precision=∑u∈U|R（u）∩T（u）|∑u∈U|R（u）|（8）

（3）覆蓋率（Coverage）。該指標(biāo)描述一個推薦引擎對項目長尾的發(fā)覺能力。最直觀的描述為推薦引擎能夠推薦出來的項目占總項目集合的比例。假設(shè)系統(tǒng)的用戶集合為U，推薦引擎向每個用戶推薦一個長度為N的項目列表R（u）。則推薦引擎的覆蓋率可定義為：

Coverage=|∪u∈UR（u）||I|（9）

為更細(xì)致地描述推薦引擎挖掘長尾的能力，需要統(tǒng)計推薦列表中不用項目出現(xiàn)次數(shù)的分布。可以參考信息論中的信息熵：

H=-∑ni=1p（i）logp（i）（10）

其中，p（i）是項目i的流行度除以所有項目流行度之和。

3.2數(shù)據(jù)集說明

為評估不同算法的推薦效果，使用以下公開數(shù)據(jù)集：

（1）MovieLens數(shù)據(jù)集。該數(shù)據(jù)集（http：//www.grouplens.org/node/73）包含3個不同版本，本次實驗選用中等大小的數(shù)據(jù)集。該數(shù)據(jù)集包含約100萬條評分，涵蓋了6 000多個用戶對4 000多部電影的評分情況，用戶可以對電影評5個不同等級的分?jǐn)?shù)（1-5分），并且每位用戶至少曾為20部電影作過評價。

（2）Jester數(shù)據(jù)集。該數(shù)據(jù)集是加州大學(xué)伯克利分校發(fā)布的一個關(guān)于笑話的數(shù)據(jù)集（http：//www.ieor.berkeley.edu/～goldberg/jesterdata/），包含約410萬記錄，收集了73 421個用戶對100個笑話的評分（評分范圍從-10～10）。該數(shù)據(jù)集分為3個部分，本次實驗采用了第三部分，該部分為24 938個用戶的評分，且打分項目數(shù)目在15～35之間。

定義用戶計算矩陣中未評分條目所占的百分比作為稀疏密度來度量采用數(shù)據(jù)集的稀疏特性，比如MovieLens數(shù)據(jù)集的稀疏密度約為：

1-1 000 000/（6 000*4 000）=0.958 3

3.3實驗分析

本次實驗中采用MovieLens數(shù)據(jù)集和Jester數(shù)據(jù)集進(jìn)行試驗。

3.3.1數(shù)據(jù)稀疏性對推薦結(jié)果的影響

大多使用推薦引擎的網(wǎng)站，尤其是一些大型的電子商務(wù)網(wǎng)站，比如淘寶、京東商城等，用戶真正接觸的物品信息數(shù)量以及進(jìn)行評價的信息常常達(dá)不到物品信息總量的1%，這就導(dǎo)致了計算信息矩陣的極端稀疏，容易導(dǎo)致推薦質(zhì)量令用戶不滿意，或者用戶體驗不佳。

通過實驗來比較常規(guī)協(xié)同過濾（采用余弦相關(guān)性和加入懲罰因子的貝葉斯公式）在MovieLens與Jester兩個數(shù)據(jù)集中不同稀疏密度下的推薦效果。選取MovieLens數(shù)據(jù)集和Jester數(shù)據(jù)集中各兩組數(shù)據(jù)集作對比，結(jié)果分別如表1、表2所示。其中： MI15為MovieLens數(shù)據(jù)集中前1 500個用戶的評分；MII15為MovieLens數(shù)據(jù)集中前1 500個用戶中評分?jǐn)?shù)目小于30的評分；JI15為Jester數(shù)據(jù)集中前1 500個用戶的評分；JII15為Jester數(shù)據(jù)集中前1 500個用戶中評分?jǐn)?shù)目小于30的評分。對每個數(shù)據(jù)集根據(jù)實驗需要將其劃分為訓(xùn)練集和測試集，且二者比例約為4∶1。

從表1、表2可以看出，當(dāng)數(shù)據(jù)比較稀疏（即當(dāng)選定MII15和 JII15兩個數(shù)據(jù)集）時，SVD與常規(guī)的協(xié)同過濾方法（不論是采用加入懲罰因子的貝葉斯方法還是余弦相似度）推薦結(jié)果類似，唯一不同的是隨著數(shù)據(jù)集稀疏密度的變化，相較與其它兩種算法，SVD算法預(yù)測結(jié)果變化幅度比較小，即其對數(shù)據(jù)稀疏的敏感程度要優(yōu)于常規(guī)的協(xié)同過濾方法。隨著抽取子數(shù)據(jù)集系數(shù)密度越來越大，推薦引擎的推薦效果越好，但當(dāng)數(shù)據(jù)子集比較稠密時，可以看出常規(guī)的協(xié)同過濾方法（特別是采用加入懲罰因子的貝葉斯方法）比SVD算法要好。實驗證明數(shù)據(jù)集的稀疏性是影響推薦引擎效果的重要因素。

3.3.2針對選定數(shù)據(jù)集，選定適當(dāng)?shù)膋值

對于MovieLens數(shù)據(jù)集，從用戶評分?jǐn)?shù)據(jù)中選擇評分?jǐn)?shù)目小于40的用戶，得到數(shù)據(jù)集包括約200多個用戶和1 200多部電影，然后將數(shù)據(jù)集隨機(jī)劃分為訓(xùn)練集與測試集，訓(xùn)練集和測試集的比例為4∶1。

對于Jester數(shù)據(jù)集，直接選取用戶評分項目從15～35的用戶，得到數(shù)據(jù)集包括約24 900個用戶的評分，將數(shù)據(jù)集隨機(jī)分成訓(xùn)練集與測試集，二者之間的比例約為4∶1。

在基于SVD分解的模型中，矩陣最終維數(shù)k是關(guān)鍵參數(shù)，如果k過大，則失去了SVD分解的意義，如果k過小，則不能很好反映原有矩陣的信息特性，故首先需要確定參數(shù)k，然后再采用本文提出的BAS算法。

從圖1中可以看出，當(dāng)k=25時，平均絕對誤差（MAE）最小，所以對于該數(shù)據(jù)集，維數(shù)k=25是最佳的，在采用BAS算法實驗中，針對MovieLens數(shù)據(jù)集，選取k=25。從圖2中可以看出，針對Jester數(shù)據(jù)集，當(dāng)k=8時，平均絕對誤差（MAE）最小，所以對于Jester數(shù)據(jù)集，維數(shù)k=8是最佳的，在采用BAS算法的實驗中，針對Jester數(shù)據(jù)集，選取k=8。

3.3.3在選定的數(shù)據(jù)集上進(jìn)行不同算法的推薦

利用實驗中所用的數(shù)據(jù)集確定k值，圖3和圖4分別為選定的MovieLens數(shù)據(jù)集和Jester數(shù)據(jù)集上不同算法的預(yù)測結(jié)果。

從圖3可以看出，BAS算法比樸素貝葉斯及SVD算法得到的推薦效果都要好，但當(dāng)鄰居數(shù)目超過20時，BAS方法的結(jié)果和樸素貝葉斯方法（即常規(guī)協(xié)同過濾方法）的結(jié)果趨于相交，所以當(dāng)鄰居數(shù)目超過一定數(shù)量時，BAS方法的優(yōu)越性不明顯，考慮到現(xiàn)實中用戶只對為其推薦的前幾條信息感興趣，所以20個鄰居在選定數(shù)據(jù)集下是可以接受的。同時以上結(jié)果也可以從另一個方面反映MAE可以比較好地評價推薦引擎結(jié)果推薦的準(zhǔn)確性。

圖4Jester數(shù)據(jù)集下不同算法的預(yù)測結(jié)果比較

協(xié)同過濾所需的計算信息矩陣經(jīng)過奇異值分解處理后，原始的計算信息矩陣維度減小了，使得原本高維模型的計算轉(zhuǎn)換成了指定維度下的矩陣運(yùn)算，有效縮減了原有問題的規(guī)模。實驗表明，奇異值分解應(yīng)用于協(xié)同過濾時，尤其是應(yīng)用于數(shù)據(jù)稀疏度比較高的信息矩陣計算時，能有效提高推薦引擎的推薦精度，雖然矩陣的奇異值分解計算量比較大，但可以離線進(jìn)行，從而彌補(bǔ)運(yùn)算量大帶來的損耗。從實驗結(jié)果看出，BAS方法的推薦質(zhì)量與其它常見的方法相比有一定的提高。

4結(jié)語

個性化推薦中協(xié)同過濾應(yīng)用廣泛。其主要思想是利用用戶的歷史信息計算用戶之間的相似性＼[6，7＼]，利用與目

標(biāo)用戶相似性較高的鄰居對產(chǎn)品的評價來預(yù)測目標(biāo)用戶

對特定產(chǎn)品的喜好程度。計算矩陣稀疏性的問題是協(xié)同

過濾算法需解決的關(guān)鍵問題。本文主要針對協(xié)同過濾中數(shù)據(jù)稀疏性問題導(dǎo)致推薦效果不理想，用戶體驗不佳問題，提出一種混合推薦的BAS算法。利用公開實驗數(shù)據(jù)集MovieLens和Jester進(jìn)行試驗，實驗結(jié)果表明本文提出的BAS方和現(xiàn)有的解決方法相比，能夠一定程度的緩解數(shù)據(jù)稀疏性問題，提高推薦引擎的推薦精度。

參考文獻(xiàn)參考文獻(xiàn)：

＼[1＼]DANIEL BILLSUS ， MICHAEL J. Pazzani， Learning collaborative information filters＼[C＼]. Proceedings of the Fifteenth International Conference on Machine Learning，1998：4654.

＼[2＼]李勇， 徐振寧， 張維明. Internet 個性化信息服務(wù)研究綜述＼[J＼]. 計算機(jī)工程與應(yīng)用， 2002， 38（19）： 183188.

＼[3＼]曹一鳴. 協(xié)同過濾推薦瓶頸問題綜述＼[J＼]. 軟件， 2012，33（12）： 315321.

＼[4＼]SHI K，K ALI. GetJar mobile application recommendations with very sparse datasets＼[C＼]. Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining，2012：204212.

＼[5＼]李華， 張宇， 孫俊華. 基于用戶模糊聚類的協(xié)同過濾推薦研究＼[J＼]. 計算機(jī)科學(xué)， 2012. 39（12）：8386.

＼[6＼]KIM W. Inference of recommendation information on the internet using improved FAM＼[J＼]. Future Generation Computer Systems， 2004， 20（2）： 265273.

＼[7＼]楊陽， 向陽， 熊磊. 基于矩陣分解與用戶近鄰模型的協(xié)同過濾推薦算法＼[J＼]. 計算機(jī)應(yīng)用， 2012， 32（2）： 395398.

＼[8＼]熊忠陽， 劉芹， 張玉芳. 結(jié)合項目分類和云模型的協(xié)同過濾推薦算法＼[J＼]. 計算機(jī)應(yīng)用研究， 2012， 29（10）： 36603664.

＼[9＼]黃國言. 基于項目屬性的用戶聚類協(xié)同過濾推薦算法＼[J＼].計算機(jī)工程與設(shè)計， 2010（5）： 10381041.

責(zé)任編輯（責(zé)任編輯：陳福時）