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

一種改進的組合推薦算法研究

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

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

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

引　言

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

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

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

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

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

（2）相似鄰居推薦模塊：采用基于用戶的協(xié)同過濾推薦算法，將用戶的喜好信息預測出來，對項目的預測值進行排序，選取TopN個資源，形成推薦集合。

1.1降低矩陣稀疏度子模塊算法流程設計

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

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

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

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

1.2相似鄰居推薦子模塊算法流程設計

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

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

輸出（OUTPUT）：推薦項目的集合RS。

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

1.3算法整體流程設計

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

算法具體流程如下：

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

輸出（OUTPUT）：RS。

2　實驗設計

2.1實驗數(shù)據(jù)與評價標準

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

在評價推薦系統(tǒng)的準確度時，有關文獻提出，用平均絕對偏差（Mean Absolute Error，MAE）來衡量推薦系統(tǒng)的預測值與實際值之間的偏差。MAE是一個在統(tǒng)計領域經(jīng)常使用的準確性評價指標，其核心思想就是計算預測值與實際值之間的偏差，偏差值越小則說明實驗值與實際值之間的差距越小，也就說明實驗值更加接近實際值，實驗算法的效率更高。MAE的計算由下式定義：

其中，pi表示預測值，qi表示實際評分值。N代表預測項目的個數(shù)。

2.2實驗過程與結果分析

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

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

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

3　結束語

本文中提出的基于內(nèi)容和協(xié)調(diào)過濾的組合推薦算法在一定程度上綜合了兩種算法的優(yōu)點，發(fā)揮了各自的優(yōu)勢，降低了矩陣的稀疏程度，提高了推薦質(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張丙奇. 基于領域知識的個性化推薦算法研究［J］. 計算機工程， 2005， 31（21）: 7～9

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