一種改進(jìn)的組合推薦算法研究

王子政　姚衛(wèi)東（北京信息控制研究所，北京　100048）

一種改進(jìn)的組合推薦算法研究

王子政姚衛(wèi)東
（北京信息控制研究所，北京100048）

推薦系統(tǒng)是解決目前信息過(guò)載問(wèn)題的有效工具和方法，而在各種推薦算法中，協(xié)同過(guò)濾推薦算法的應(yīng)用最為廣泛。但是，基于協(xié)同過(guò)濾的推薦算法存在稀疏矩陣的問(wèn)題，即：當(dāng)矩陣過(guò)于稀疏時(shí)，其推薦結(jié)果誤差較大。針對(duì)這一問(wèn)題，提出了一種基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法，并通過(guò)實(shí)驗(yàn)的方式與傳統(tǒng)的協(xié)同過(guò)濾推薦算法進(jìn)行了比較。實(shí)驗(yàn)數(shù)據(jù)表明，這種組合推薦算法具有較高的效率。

推薦系統(tǒng)，協(xié)同過(guò)濾，內(nèi)容，組合推薦

引　言

隨著互聯(lián)網(wǎng)及信息技術(shù)的飛速發(fā)展，信息過(guò)載問(wèn)題越來(lái)越突出，獲取有用信息變得越來(lái)越困難。為了能夠準(zhǔn)確地找到所需的信息，人們需要付出更多的時(shí)間和精力。而推薦系統(tǒng)的出現(xiàn)，有效地緩解了這一問(wèn)題。基于用戶的協(xié)同過(guò)濾推薦算法在推薦系統(tǒng)中應(yīng)用最為廣泛，這種推薦算法基于用戶—項(xiàng)目（user-item）矩陣進(jìn)行計(jì)算，但是其前提是用戶項(xiàng)目矩陣能夠提供足夠的信息。對(duì)于稀疏矩陣，采用這種推薦算法則會(huì)造成推薦質(zhì)量下降、推薦結(jié)果誤差較大等問(wèn)題。

本文針對(duì)協(xié)同過(guò)濾推薦算法中存在的矩陣稀疏的問(wèn)題，提出了一種基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法，并將其與現(xiàn)有的協(xié)同過(guò)濾推薦算法進(jìn)行了比較，以驗(yàn)證該組合推薦算法的可行性。

1　基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法模型

本文將基于內(nèi)容和協(xié)同過(guò)濾的組合推薦算法分為降低矩陣稀疏度模塊，以及TopN鄰居推薦模塊等兩個(gè)子模塊單獨(dú)進(jìn)行討論。

（1）降低矩陣稀疏度模塊：為了降低矩陣的稀疏程度，合理增加用戶—項(xiàng)目矩陣中的非零值，采用基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，將未評(píng)價(jià)項(xiàng)目的評(píng)分值計(jì)算出來(lái)，填充到用戶—項(xiàng)目矩陣中。

（2）相似鄰居推薦模塊：采用基于用戶的協(xié)同過(guò)濾推薦算法，將用戶的喜好信息預(yù)測(cè)出來(lái)，對(duì)項(xiàng)目的預(yù)測(cè)值進(jìn)行排序，選取TopN個(gè)資源，形成推薦集合。

1.1降低矩陣稀疏度子模塊算法流程設(shè)計(jì)

為了降低矩陣的稀疏度，同時(shí)增強(qiáng)其稠密性，直觀上必須增加用戶對(duì)項(xiàng)目的評(píng)價(jià)信息，但是在用戶—項(xiàng)目評(píng)分矩陣中可以利用的歷史信息是非常有限的。在評(píng)分矩陣中，歷史數(shù)據(jù)越豐富，利用協(xié)同過(guò)濾推薦算法進(jìn)行計(jì)算的結(jié)果就越精確，推薦效果也就越好。在有限的評(píng)分信息條件下，本文提出了采用基于項(xiàng)目的協(xié)同過(guò)濾推薦算法來(lái)增強(qiáng)矩陣稠密性的方法。算法過(guò)程設(shè)計(jì)如下：

輸入（INPUT）：用戶—項(xiàng)目矩陣Rm×n，待推薦項(xiàng)目數(shù)量NI，鄰居個(gè)數(shù)N。

輸出（OUTPUT）：一個(gè)稀疏程度降低的用戶—項(xiàng)目矩陣R’m×n。

運(yùn)算流程（PROCESS）：對(duì)于每個(gè)未被所有用戶評(píng)價(jià)過(guò)的項(xiàng)目i，都執(zhí)行下面的操作：（1）首先計(jì)算項(xiàng)目i與其它項(xiàng)目之間的相似度，并選出與其相似度最高的前N個(gè)項(xiàng)目作為其鄰居項(xiàng)目。（2）根據(jù)項(xiàng)目i已經(jīng)存在的用戶評(píng)分信息，利用（1）中得到的N個(gè)鄰居項(xiàng)目信息，對(duì)i中的評(píng)分信息進(jìn)行計(jì)算預(yù)測(cè)。按照預(yù)測(cè)值大小進(jìn)行排序，選擇前NI個(gè)項(xiàng)目值作為其推薦評(píng)價(jià)集合。（3）將（2）中得到的項(xiàng)目預(yù)測(cè)值填入原用戶—項(xiàng)目矩陣Rm×n中，形成一個(gè)新的用戶—項(xiàng)目矩陣R’m×n。至此，完成降低矩陣稀疏程度子模塊算法的設(shè)計(jì)。

1.2相似鄰居推薦子模塊算法流程設(shè)計(jì)

經(jīng)過(guò)降低矩陣的稀疏程度處理之后，得到一個(gè)更加稠密的用戶—項(xiàng)目矩陣R’m×n。在此之上，采用基于用戶的協(xié)同過(guò)濾推薦算法，對(duì)于m個(gè)用戶中的每個(gè)用戶，產(chǎn)生其相應(yīng)的推薦結(jié)果集合。算法設(shè)計(jì)如下：

輸入（INPUT）：一個(gè)經(jīng)過(guò)降低稀疏處理之后的矩陣R’m×n，鄰居用戶數(shù)量UN，推薦項(xiàng)目的數(shù)量IN。

輸出（OUTPUT）：推薦項(xiàng)目的集合RS。

運(yùn)算過(guò)程（PROCESS）：對(duì)于每個(gè)被推薦的目標(biāo)用戶u，都執(zhí)行以下操作：（1）計(jì)算目標(biāo)用戶u與其它用戶之間的相似度，并選擇與其相似度最高的前UN個(gè)作為其相似鄰居用戶。（2）根據(jù)用戶u已經(jīng)存在的評(píng)價(jià)信息和（1）中得到的相似鄰居用戶信息，對(duì)未評(píng)價(jià)過(guò)的項(xiàng)目進(jìn)行預(yù)測(cè)。（3）對(duì)所有未評(píng)價(jià)過(guò)的項(xiàng)目的預(yù)測(cè)評(píng)分值進(jìn)行排序，選取評(píng)分值最高的前IN個(gè)項(xiàng)目進(jìn)行形成用戶u的推薦集合。至此，完成TopN鄰居推薦子模塊算法的設(shè)計(jì)。

1.3算法整體流程設(shè)計(jì)

以上對(duì)推薦算法模塊的兩個(gè)子模塊進(jìn)行了分析和設(shè)計(jì)，下面介紹組合推薦算法的整體思路和步驟。按照算法設(shè)計(jì)的總體思路及其運(yùn)行步驟，從算法的輸入、輸出和運(yùn)算流程等三個(gè)方面進(jìn)行介紹。

算法具體流程如下：

輸入（INPUT）：（1）用戶—項(xiàng)目矩陣Rm×n，其中包含m個(gè)用戶、n個(gè)項(xiàng)目，矩陣中每個(gè)元素ri， j表示用戶i對(duì)項(xiàng)目j的評(píng)分信息；（2）用戶相似性閾值Usim；（3）項(xiàng)目相似性閾值Isim；（4）矩陣極大稀疏度NP；（4）矩陣可計(jì)算稀疏度MP（NP>MP）；（5）鄰居數(shù)目閾值NH；（6）推薦項(xiàng)目數(shù)量N；（7）預(yù)測(cè)評(píng)分閾值RV。

輸出（OUTPUT）：RS。

2　實(shí)驗(yàn)設(shè)計(jì)

2.1實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)數(shù)據(jù)采用明尼蘇達(dá)大學(xué)公開的數(shù)據(jù)集，此數(shù)據(jù)集由GroupLens項(xiàng)目組負(fù)責(zé)收集整理，可以從互聯(lián)網(wǎng)站http:// grouplens.org/datasets/movielens/下載。網(wǎng)站中提供了不同大小的數(shù)據(jù)集合，為了實(shí)驗(yàn)方便，下載了100kB的數(shù)據(jù)集并進(jìn)行算法的驗(yàn)證。在100kB的數(shù)據(jù)集合中包含943個(gè)用戶、1682個(gè)項(xiàng)目（電影）。在不影響實(shí)驗(yàn)結(jié)果的前提下，為了計(jì)算方便，從全部數(shù)據(jù)集中選取78720條記錄作為所有實(shí)驗(yàn)的數(shù)據(jù)集，其中包含400個(gè)用戶和1361個(gè)項(xiàng)目（電影），也即在用戶—項(xiàng)目評(píng)分矩陣Rm×n中，m=400，n=1361。矩陣Rm×n的稀疏度Sparsity=1-78720÷（400×1361）=0.8554。

在評(píng)價(jià)推薦系統(tǒng)的準(zhǔn)確度時(shí)，有關(guān)文獻(xiàn)提出，用平均絕對(duì)偏差（Mean Absolute Error，MAE）來(lái)衡量推薦系統(tǒng)的預(yù)測(cè)值與實(shí)際值之間的偏差。MAE是一個(gè)在統(tǒng)計(jì)領(lǐng)域經(jīng)常使用的準(zhǔn)確性評(píng)價(jià)指標(biāo)，其核心思想就是計(jì)算預(yù)測(cè)值與實(shí)際值之間的偏差，偏差值越小則說(shuō)明實(shí)驗(yàn)值與實(shí)際值之間的差距越小，也就說(shuō)明實(shí)驗(yàn)值更加接近實(shí)際值，實(shí)驗(yàn)算法的效率更高。MAE的計(jì)算由下式定義：

其中，pi表示預(yù)測(cè)值，qi表示實(shí)際評(píng)分值。N代表預(yù)測(cè)項(xiàng)目的個(gè)數(shù)。

2.2實(shí)驗(yàn)過(guò)程與結(jié)果分析

為了驗(yàn)證本文設(shè)計(jì)的組合推薦算法的推薦效果，對(duì)各種算法進(jìn)行了對(duì)比。本實(shí)驗(yàn)中，分別對(duì)比了“改進(jìn)的組合推薦算法”、“基于用戶的協(xié)同過(guò)濾推薦算法”、“基于項(xiàng)目的協(xié)同過(guò)濾推薦算法”等三種算法的MAE值大小，以對(duì)推薦算法的有效性進(jìn)行驗(yàn)證。為了消除稀疏程度對(duì)推薦結(jié)果的影響，本文選取實(shí)驗(yàn)集中75%的數(shù)據(jù)進(jìn)行預(yù)測(cè)計(jì)算，剩余的25%留作與預(yù)測(cè)結(jié)果結(jié)合計(jì)算平均絕對(duì)偏差MAE。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　改進(jìn)的組合推薦算法與傳統(tǒng)協(xié)同過(guò)濾推薦算法比對(duì)

從圖1中可以看到，無(wú)論鄰居數(shù)目如何變化，“改進(jìn)的組合推薦算法”都較傳統(tǒng)的協(xié)同過(guò)濾推薦算法具有更優(yōu)的推薦準(zhǔn)確度，從算法思路上來(lái)看，對(duì)于稀疏程度極大的矩陣，并不直接使用基于協(xié)同過(guò)濾的推薦算法，而是采用基于內(nèi)容的推薦算法，此時(shí)由于矩陣的稀疏度較大，相應(yīng)的記錄較少，在使用基于內(nèi)容的推薦算法時(shí)能夠獲得更高的推薦效率。另外，對(duì)于稀疏的矩陣，采用了基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，首先進(jìn)行了降低稀疏度處理，增強(qiáng)矩陣的稠密度，以便能夠使用協(xié)同過(guò)濾推薦算法進(jìn)行預(yù)測(cè)計(jì)算。

3　結(jié)束語(yǔ)

本文中提出的基于內(nèi)容和協(xié)調(diào)過(guò)濾的組合推薦算法在一定程度上綜合了兩種算法的優(yōu)點(diǎn)，發(fā)揮了各自的優(yōu)勢(shì)，降低了矩陣的稀疏程度，提高了推薦質(zhì)量。與傳統(tǒng)的、單一的推薦算法相比，該組合推薦算法的推薦質(zhì)量明顯提升。

1Bawden D， Holtham C， Courtney N. Courtney N. Perspectives on information overload［J］. Aslib Proceedings， 1999，51（8）: 249

2Schafer J B，Konstan J A， Riedl J. E-Commerce Recommendation Applications［J］. Data Mining and Knowledge Discovery， 2001， 5（1～2）: 115～153

3Jonathan L.， Herlocker， JosePh A， et al. Evaluating Collaborative Filtering Recommender Systems［J］. ACM Transactionson InformationSystems， 2004， 22（1）: 5～53

4張丙奇. 基于領(lǐng)域知識(shí)的個(gè)性化推薦算法研究［J］. 計(jì)算機(jī)工程， 2005， 31（21）: 7～9

1009-8119（2015）12（1）-0046-02