基于項目聚類和評分預測的協同過濾推薦算法研究

[摘 要] 協同過濾算法是目前個性化推薦系統中應用最成功的推薦算法之一。目前協同過濾構建的用戶-項目矩陣，一般是按用戶對所有項目的評分構建，卻沒有考慮項目之間的分類情況，導致尋找的鄰居集合可能不是最近鄰居集合。針對此問題，本文提出基于項目聚類和評分預測的協同過濾推薦算法，該算法首先按商品聚類，將大矩陣按聚類的商品來進行子矩陣的計算，在子矩陣里進行興趣度的測量，最后將在所有區域相似用戶的推薦項目合并，成為該用戶的最后推薦結果。實驗證明新算法能夠提高協同過濾推薦系統的推薦質量。

[關鍵詞] 聚類;協同過濾;鄰居用戶

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2010 . 11 . 042

[中圖分類號]F724.6;TP311 [文獻標識碼]A [文章編號]1673 - 0194(2010)11- 0111 - 03

1引言

個性化推薦系統中應用最成功的算法之一是最近鄰居協同過濾算法。協同過濾算法主要有基于用戶的和基于項目的兩種算法[1]。其基本思想是:通過計算目標用戶與各個基本用戶對項目評分之間的相似性，搜索目標用戶的最近鄰居，然后由最近鄰居的評分數據向目標用戶產生推薦，即目標用戶對未評分項目的評分可以通過最近鄰居對該項目評分的加權平均值進行逼近，從而產生推薦[2]。

目前協同過濾構建的用戶-項目矩陣，一般是按用戶對所有項目的評分構建，卻沒有考慮項目之間的分類情況，導致尋找的鄰居集合可能不是最近鄰居集合。針對此問題，本文提出了基于項目聚類和評分預測的協同過濾推薦算法，該算法首先按商品聚類，將大矩陣按聚類的商品來進行子矩陣的計算，在子矩陣里進行興趣度的測量，最后將在所有區域相似用戶的推薦項目合并，成為該用戶的最后推薦結果。利用實驗數據集對傳統算法和本文提出的基于聚類和項目預測的協同過濾算法的精確度進行了比較。

2基于項目聚類和評分預測的協同過濾推薦算法

2.1 問題分析

協同過濾主要的難點在于查找用戶的最近鄰，這一步驟是整個過程中的關鍵，而要找到最好的鄰居，就得有效地構建好用戶-項目評分矩陣。由于一方面客戶商品評分數據少以及客戶不能準確評分，另一方面隨著客戶、商品的不斷增長，導致用戶評分數據極端稀疏，結果是不能對某些客戶進行推薦從而影響了推薦的精度。

Badnul[3]提出采用維度約簡技術(Dimensionality Reduction)，利用一種單一值分解技術來約簡推薦系統中顧客-商品矩陣數據的維數。Mobasher[4]提出通過對稀疏數據的關聯可以提高推薦質量。吳良杰 等[5]提出基于 Web 使用挖掘和 Web內容挖掘的推薦系統。由于用戶評分數據本來就非常稀少，而根據最近鄰的計算公式，構建的矩陣商品項必須是用戶共同評分過的，這樣導致矩陣會更加稀疏。鄧愛林[6]提出基于項評分預測的協同過濾，為了有效解決用戶評分數據極端稀疏這種傳統相似性度量方法存在的問題，提出在計算用戶 i 和用戶 j 之間的相似性時，首先計算用戶 i和用戶 j 評分過的項集合的并集 Ui j，設用戶 i 評分過的項集合用 Ia表示，用戶j評分過的項集合用Ib表示，則Ui j = Ia∪Ib。

用戶i和用戶j在項集合中未評分的項通過用戶對相似項的評分預測出來，然后在商品集合上計算用戶 i 和用戶 j 之間的相似性。這種方法不僅能有效解決相關相似性度量方法中用戶共同評分數據比較少的情況，而且可以有效解決余弦相似性度量方法和修正的余弦相似性度量方法中對所有未評分商品的評分均相同的問題(均為 0)，使得計算出來的目標用戶的最近鄰居比較準確，從而有效提高推薦算法的推薦質量。

翁頌舜、劉美如[7]提出了基于產品特征的協同過濾推薦，提出構建產品檔案，并根據用戶對各類商品的購買量以及平均購買金額來進行探測用戶對某類商品的潛在的喜好程度。

但是，上面算法的改進還有以下不足:由于協同過濾構建的用戶-項目矩陣，一般是按用戶對所有項目的評分構建，有可能出現以下情況，參見表1。

對于表1的例子，如果按圖書類來搜索最近鄰的話，則 User5 的最近鄰應該是 User1，則他對于 Video4 的評分應該是 2，而按影碟類來搜索最近鄰，則 User5的最近鄰應為 User2，誠然，User2 應該比 User1 更相似于 User5，所以 User5 對 Video4的最可能評分是 1，而不是2。

2.2 改進的協同過濾推薦算法

高鳳榮[8]提出按商品聚類，將大矩陣按聚類的商品來進行子矩陣的計算。考慮用戶多興趣度的可能性，用戶往往對自己感興趣的項目非常關注，而對其他項目則毫不在意。因此，可以從這方面來考慮，將項目劃分成不同類別，用戶在同一類別的項目中比較相似性不僅比在不同種類的項目中比較要準確，而且也可以降低數據的高維性。最后計算出用戶在每一部分項目中的興趣度，依據一定的啟發規則，合并每一類的推薦結果作為用戶的最終推薦。

本文對于協同過濾的改進在于:構建用戶矩陣時，不是所有的項目一起構建，而是將項目分開，構建多個不同的子矩陣，在子矩陣里進行興趣度的測量，最后將在所有區域的相似用戶的推薦項目合并，成為該用戶的最后推薦結果。過程可分為以下3步:一是對商品聚類，按商品所屬類別來進行聚類;二是對用戶聚類，構建用戶特征函數Pi = (V1，V2，…，Vm)，其中i 代表第i個用戶，Vm為第V類產品平均購買金額。將所有用戶的特征函數描述后，可以運用聚類，將有相似愛好的用戶聚到一起;三是將相似度高的用戶、商品進行項目評分預測，這樣構建的矩陣規模能夠達到更小。利用測試的數據集，可以看出這些商品可能屬于多個交叉類別?？梢园此鶎兕悇e來聚類，如表 2 所示。

算法結合基于項目預測以及商品分類的數據，對于矩陣的劃分，運用聚類的方法，將同類的商品劃分到一起，使同類間相似程度最大，類與類之間差異度最大。運用該方法構建分矩陣，在每個分矩陣中，查找最近鄰，然后計算用戶對未評分項目的預計值，重復以上步驟，最后按各分矩陣中預計值由大到小排列，就是對用戶的最終推薦。商家一般很少有用戶對商品直接的評分數據，對 BOL、Joyo、新浪商城、搜狐商城等幾家網站進行調查，發現其網站均沒有該評價數據。因此，本文根據購物記錄來定義評分。

用戶在所有分矩陣中處理好后，對 predictionp (a ，k)按由大到小排列，可以給定一個評分閾值，大于這個值的則全部推薦。如果用戶的在 N 個分矩陣中皆有興趣，總推薦數為 K，則一般取[K/N]以前的數。

3實驗結果

3.1 數據集和度量標準

運用 movielens 測試數據集來對該算法測試。該數據集的下載地址是:http://www.grouplens.org/。該數據集包含著 6 040 個用戶對于 3 900 部電影的 1 000 209個匿名評分記錄，每個用戶至少評價過 20 部電影，評分數字從 1 到 5，值越大表明用戶對此越感興趣。

隨機抽取 10 000 筆記錄，包含 67 位用戶對 2 226 部電影的評分，將該數據集按8 ∶ 2 分開，80%訓練集用，20%留待測試。用平均絕對誤差(MAE)[9-10]衡量算法的預測精度。

式中，pi為預測評分值，qi是用戶實際評分值。

MAE 是測試集中所用用戶對資源的打分實際值與預測值的偏差絕對值的平均。MAE 值越小說明算法推薦的精度越高。

3.2實驗過程和結果

隨機取 10 000 筆記錄中的 8 000 筆記錄。

第一步:先根據電影的所屬類別，將電影聚類成 7 個類別，然后按類別劃分子矩陣，從而得到 7 個矩陣。

第二步:根據上面步驟，構建每一類的用戶-電影評分矩陣，并在每個矩陣中計算用戶之間的相似度。

第三步:根據相似度，預測用戶的未評分數據，并按預測值大小由大到小按順序排列。

第四步:重復第二、第三步，直到找出所有用戶的最近鄰，以及預測出所有未評分項目。

第五步:當所有數據處理好后，可以把計算結果與余下的 2 000 筆測試數據對比，計算 MAE 的值。

用同樣的數據，把實驗結果與用傳統協同過濾計算結果作一個對比，可以得到如圖1所示的結果。

從圖 1 中可看出，采用本文中的方法計算的 MAE 比傳統的方法要小。隨著相似鄰居的增加，MAE 的值在逐漸減小，到一定程度后有上升的趨勢。這主要是由于我們把皮爾遜相關系數按降序排列，鄰居越多，造成預測值也不夠準確的緣故，從而導致 MAE 值后來偏大的趨勢。

4結束語

本文提出的算法與傳統協同過濾算法的最大不同是: 提出首先按商品聚類，將大矩陣按聚類的商品來進行子矩陣的計算，在子矩陣里進行興趣度的測量，最后將在所有區域的相似用戶的推薦項目合并，成為該用戶的最后推薦結果。實驗結果表明，改進的算法顯著地提高了推薦質量。

主要參考文獻

[1] M Deshpande，G Karypis. Item-Based Top-N Recommendation Algorithms[J]. ACM Transaction on Information Systems，2004，22(1):143-177.

[2] 李濤，王建東，葉飛躍.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術，2007，29 (7):1177-1178.

[3] Badnul M Sarwar， George Karypis， Joseph A Konstan，et al. Application of DimensionalityReduction in Recommender System——A Case Study[C] // Proceedings of the Web Mining for E-Commerce Workshop (WebKDD'2000)， 2000.

[4] B Mobasher， H Dai， T Luo. Discovery of Aggregate Usage Profiles for Web Personalization[C] // Proceedings of the Web Mining for E-Commerce Workshop(WebKDD’2000)，2000.

[5] 吳 良 杰 ， 劉 紅 祥 ，等 . 個 性 化 服 務 中 網 頁 推 薦 模 型 的 研 究[J]. 計 算 機 運 用 研究，2005，22(6):83-85.

[6] 鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協同過濾推薦算法[J]. 軟件學報，2003，14(9):1621-1628.

[7] 翁頌舜，劉美如.以產品特征為基礎之探勘與推薦[C] // 2004 電子商務與數位生活研討會，2004:2152-2175.

[8] 高鳳榮，杜小勇，王珊.一種基于稀疏矩陣劃分的個性化推薦算法[J]. 微電子學與計算機，2004，21(2):58-62.

[9] 鄧愛林.電子商務系統關鍵技術研究[D]. 上海:復旦大學，2003.

[10] Sung Hwan Min， Ingoo Han. Optimizing Collaborative Filtering Recommender Systems[M] // J G Carbonell，J Siekmann(Eds). Advances in Web Intelligence. Berlin/Heidelberg:Springer，2005:313-319.