協(xié)同過濾算法改進(jìn)及研究

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

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

DOIDOI：10.11907/rjdk.104179

中圖分類號(hào)：TP312

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

作者簡(jiǎn)介作者簡(jiǎn)介：蘇楊茜（1988-），女，廣西南寧人，中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，研究方向?yàn)檐浖こ膛c復(fù)雜網(wǎng)絡(luò)。

0引言

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

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

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

協(xié)同過濾算法推薦需利用用戶對(duì)項(xiàng)目資源的評(píng)價(jià)信息矩陣。如果用戶對(duì)項(xiàng)目資源的評(píng)價(jià)不夠多，則無法產(chǎn)生精確的推薦，導(dǎo)致用戶體驗(yàn)不佳，這就是協(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ì)算信息矩陣稀疏性問題，可以從兩個(gè)方面著手：①尋找一個(gè)更為精確的相似性度量方法，在同等稀疏程度情況下，得到更好的鄰居集合；②對(duì)計(jì)算信息矩陣進(jìn)行降維處理，并填補(bǔ)計(jì)算信息矩陣中的缺失項(xiàng)，使其成為一個(gè)稠密的計(jì)算信息矩陣，為協(xié)同過濾后的計(jì)算提供更多的數(shù)據(jù)源，從而提高推薦質(zhì)量。

2.1主要技術(shù)

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

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

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

（2）奇異值分解（SVD）。計(jì)算矩陣R代表用戶的評(píng)分行為，其中R[u][i]表示用戶u對(duì)項(xiàng)目i的評(píng)分。首先將計(jì)算矩陣R分解為兩個(gè)低維相乘矩陣。

R=PTQ（2）

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

用戶u對(duì)項(xiàng)目i的評(píng)價(jià)預(yù)測(cè)值R（u，i）=rui，可通過下式計(jì)算：

rui=∑fpufqif（3）

其中，puf=P（u，f），qif=Q（i，f）。矩陣分解思想為利用最小化RMSE思想，直接通過訓(xùn)練集中所觀察的數(shù)據(jù)對(duì)P、Q矩陣進(jìn)行學(xué)習(xí)。在利用RMSE作為評(píng)測(cè)指標(biāo)時(shí)，加入防止過擬合項(xiàng)λ（‖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ù)測(cè)未打分的評(píng)分預(yù)測(cè)值，得到一個(gè)稠密的計(jì)算矩陣；然后，利用填補(bǔ)后的計(jì)算矩陣，配合加入懲罰因子的貝葉斯公式，采用獲取最優(yōu)鄰居集合的方法，求取實(shí)際未評(píng)分的項(xiàng)目的預(yù)測(cè)值，該方法稱為BAS（Bayes After SVD）算法。BAS算法流程如下：①獲取用戶項(xiàng)目信息矩陣，將計(jì)算矩陣R規(guī)范為Rn；②利用SVD對(duì)信息矩陣進(jìn)行降維處理，同時(shí)進(jìn)行缺失項(xiàng)填充；③選中一個(gè)用戶，利用修正后的貝葉斯公式求得活躍用戶與其他用戶的相似度；④依照與活躍用戶的相似性度量大小進(jìn)行排序，選擇前N個(gè)用戶作為活躍用戶的最優(yōu)鄰居；⑤求出每個(gè)活躍用戶i對(duì)未評(píng)分項(xiàng)目j的預(yù)測(cè)值。

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

3.1評(píng)價(jià)指標(biāo)

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

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

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

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

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

令R（u）表示用戶u推薦N個(gè)物品，而T（u）是用戶在測(cè)試集上的行為列表，則推薦結(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)描述一個(gè)推薦引擎對(duì)項(xiàng)目長尾的發(fā)覺能力。最直觀的描述為推薦引擎能夠推薦出來的項(xiàng)目占總項(xiàng)目集合的比例。假設(shè)系統(tǒng)的用戶集合為U，推薦引擎向每個(gè)用戶推薦一個(gè)長度為N的項(xiàng)目列表R（u）。則推薦引擎的覆蓋率可定義為：

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

為更細(xì)致地描述推薦引擎挖掘長尾的能力，需要統(tǒng)計(jì)推薦列表中不用項(xiàng)目出現(xiàn)次數(shù)的分布?？梢詤⒖夹畔⒄撝械男畔㈧兀?/p>

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

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

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

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

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

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

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

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

3.3實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)語

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

標(biāo)用戶相似性較高的鄰居對(duì)產(chǎn)品的評(píng)價(jià)來預(yù)測(cè)目標(biāo)用戶

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

過濾算法需解決的關(guān)鍵問題。本文主要針對(duì)協(xié)同過濾中數(shù)據(jù)稀疏性問題導(dǎo)致推薦效果不理想，用戶體驗(yàn)不佳問題，提出一種混合推薦的BAS算法。利用公開實(shí)驗(yàn)數(shù)據(jù)集MovieLens和Jester進(jìn)行試驗(yàn)，實(shí)驗(yà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 個(gè)性化信息服務(wù)研究綜述＼[J＼]. 計(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ì)算機(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ì)算機(jī)應(yīng)用， 2012， 32（2）： 395398.

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

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

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