周泓宇，梁剛，楊進（.四川大學(xué)計算機學(xué)院，成都　60065；.樂山師范學(xué)院計算機科學(xué)學(xué)院，樂山　64000）

協(xié)同過濾推薦算法比較研究

周泓宇1，梁剛1，楊進2
（1.四川大學(xué)計算機學(xué)院，成都610065；2.樂山師范學(xué)院計算機科學(xué)學(xué)院，樂山614000）

0　引言

隨著信息技術(shù)的發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)規(guī)模急劇擴大，大數(shù)據(jù)滿足用戶對信息需求的同時，帶來了信息過載的問題——用戶難以從海量數(shù)據(jù)中快速找到有用的信息[1]。推薦系統(tǒng)從用戶的角度出發(fā)，根據(jù)用戶的需求偏好、行為記錄等，挖掘出用戶可能感興趣的信息，并主動推薦給用戶。

協(xié)同過濾是推薦系統(tǒng)中采用的最為廣泛最為重要的技術(shù)之一[2]，其基本思想是具有相似行為的用戶對項目的需求也是相似的[3]。協(xié)同過濾算法只關(guān)注用戶的歷史行為，不受項目具體屬性的限制；并且能夠與社會網(wǎng)絡(luò)相結(jié)合，具有較好的推薦精度。其主要類型分為基于內(nèi)存的協(xié)同過濾、基于模型的協(xié)同過濾以及組合協(xié)同過濾。本文首先介紹三種類型的協(xié)同過濾算法，以其中基于用戶（項目）的協(xié)同過濾算法、基于矩陣分解的協(xié)同過濾算法以及基于線性回歸的集成策略為例進行詳細闡述，然后給出對比實驗結(jié)果和分析，最后是全文總結(jié)。

1　基于用戶（項目）的協(xié)同過濾算法

基于內(nèi)存的協(xié)同過濾算法包括基于用戶的方法和基于項目的方法，大致分為三個步驟：①基于用戶-項目評分矩陣，計算用戶（項目）之間的相似性；②通過相似度的逆序，選取最相似的前K個用戶（項目）作為鄰居；③根據(jù)鄰居的評分，對目標用戶（項目）未評分的項進行預(yù)測。下面以基于用戶的協(xié)同過濾算法為例進行詳細說明。

定義一個給定的用戶集U和項目集S，用戶對項目的評分表示為一個m×n的矩陣R，如表1所示。R（i，j）表示用戶i對項目j的評分，代表用戶對項目的偏好。如MovieLens數(shù)據(jù)集中用1~5分表示用戶的喜愛程度；若R（i，j）=0則表示用戶i未對項目j打分。

表1　用戶-項目m×n階評分矩陣R

首先基于用戶-項目評分矩陣計算用戶之間的相似度，常用的相似度算法包括余弦相似度算法、修正的余弦相似度算法和Pearson相關(guān)相似度算法。本文采用余弦相似度算法，把用戶的評分看作一個n維的評分向量，第k維的值表示對項目k的評分，設(shè)用戶u與用戶v的評分向量分別表示為向量u和v，則用戶u和用戶v之間的相似度為：

選取與用戶u相似度最大的k個用戶作為鄰居G （u），依據(jù)這k個鄰居對目標項目j的評分，加權(quán)預(yù)測用戶u對項目j的評分Pu，j，如公式（2）所示。其中，表示用戶i評分的均值，Ri，j表示用戶i對項目j的評分。

基于項目的方法與基于用戶的方法相似，通過計算兩兩項目的相似性得到目標項目的鄰居，并通過項目鄰居的評分預(yù)測用戶對目標項目的評分。兩種基于內(nèi)存的協(xié)同過濾算法適用于不同的推薦環(huán)境，例如在電子商務(wù)中，項目的個數(shù)遠小于用戶的個數(shù)，且項目內(nèi)容相比用戶變動更少，因此基于項目的推薦方法有更優(yōu)的時間復(fù)雜度和實時性；而在微博、新聞等方面的推薦則與之相反，使用基于用戶的方法更好一些。

2　基于矩陣分解的協(xié)同過濾算法

基于模型的協(xié)同過濾算法通過對數(shù)據(jù)集的訓(xùn)練完成對系統(tǒng)復(fù)雜模式的識別，并基于學(xué)習(xí)模型對協(xié)同過濾任務(wù)做出智能預(yù)測，包括基于概率的算法、樸素貝葉斯算法、聚類算法和基于矩陣分解的算法等，其中基于矩陣分解的算法常用于對基于評分的推薦環(huán)境[4]。基于矩陣分解的推薦算法是將原本高維度的評分矩陣RM×N分解成兩個低維度矩陣PM×D與QD×N的乘積，可將PM×D、QD×N分別看作用戶和項目的隱含特征矩陣，其中D表示隱含特征個數(shù)[5]。通過多次迭代訓(xùn)練，使得PM×DQD×N不斷地逼近評分矩陣RM×N，最后得到最終的P、Q矩陣（P× Q≈R），以此來對未評分的項進行預(yù)測。下面以基礎(chǔ)的矩陣分解推薦算法為例進行說明。

為使得P×Q≈R，需求P×Q到R的最近距離，即使整個模型的損失最小，如式（3）所示，其中K為所有已評分項。

其中，t為迭代次數(shù)，α為迭代步長。通過多次迭代得到最終的P、Q矩陣，具體算法如下：

基于矩陣分解的推薦算法關(guān)注整個評分矩陣的損失程度，更注重全局性，且空間復(fù)雜度較低。

3　基于線性回歸的集成策略

基于線性回歸的集成策略是將多個弱學(xué)習(xí)器通過某種線性組合，獲得比單個弱學(xué)習(xí)器效果更好的強學(xué)習(xí)器的過程，線性系數(shù)由回歸分析確定。將上述基于用戶的方法、基于項目的方法和基于矩陣分解的方法看作三個弱學(xué)習(xí)器，分別表示為hu（X）、hs（X）和hv（X），強學(xué)習(xí)器Hw（X）如式（6）所示。

其中，w0，w1，w2，w3為線性系數(shù)。便于標記，令h0（X）=1，h（X）=[h0（X），hu（X），hs（X），hv（X）]，W=[w0，w1，w2，w3]T，則Hw（X）=h（X）×W。定義實際評分列向量為R（X），整個訓(xùn)練集上的誤差平方和如式（7）所示。

為了使誤差平方和J（W）最小，本文采用最小二乘估計法，即：

4　實驗結(jié)果與分析

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

本實驗采用MovieLens100K數(shù)據(jù)集，其中包含了943位用戶對1682個項目的100K個評分，并將該數(shù)據(jù)集的80%作為訓(xùn)練集，剩下20%為測試集。采用平均絕對誤差MAE（Mean Absolute Error）作為指標，衡量推薦算法的優(yōu)劣。設(shè)預(yù)測的用戶評分集合為{p1，p2，…，pC}，對應(yīng)的實際用戶評分集合為{r1，r2，…，rC}，則平均絕對誤差MAE定義如式（9）所示。

4.2實驗步驟

為了說明鄰居數(shù)K對基于用戶的協(xié)同過濾算法UBCF和基于項目的協(xié)同過濾算法IBCF的影響，選取K值從5到35進行測試，如圖1所示。從圖1中可看出，基于用戶的方法和基于項目的方法分別在K取30和K取15時達到最優(yōu)效果，且前者的誤差普遍大于后者。

圖1　UBCF和IBCF的MAE指標

為了說明隱含特征個數(shù)D對基于矩陣分解的協(xié)同過濾算法MFCF的影響，分別選取10個，20個，30個，50個進行測試，如圖2所示。從圖2中可看出，在當(dāng)前數(shù)據(jù)集下，MAE值隨著D的增加而增加，D取10時，效果最佳。

圖2　MFCF的MAE指標

為了直觀地比較基于線性回歸的集成算法LICF與單個學(xué)習(xí)器算法的優(yōu)劣，選取每個學(xué)習(xí)器的最優(yōu)效果，即分別選擇UBCF（K=30）、IBCF（K=15）和MBCF （D=10）作為弱學(xué)習(xí)器，并與集成后的強學(xué)習(xí)器作比較，如圖3所示。從圖中可看出，LICF算法的效果明顯優(yōu)于每個弱學(xué)習(xí)器。

圖3　四種算法MAE指標的比較情況

5　結(jié)語

本文就三類協(xié)同過濾算法，針對性地對其中基于用戶（項目）、基于矩陣分解和基于線性回歸集成的方法進行了闡述和比較，然后利用MovieLens的電影評分數(shù)據(jù)對幾種算法的推薦效果進行了驗證。實驗結(jié)果表明，基于線性回歸的集成策略比其他單一的協(xié)同過濾算法效果好一些。組合推薦的優(yōu)勢明顯，然而單個推薦算法的選擇和組合策略的方式都是多樣化的，如何找到最優(yōu)的方案還有待進一步解決。

[1]柯良文，王靖.基于用戶特征遷移的協(xié)同過濾推薦[J].計算機工程，2015，41（1）:37-43.

[2]王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應(yīng)用，2012，48（7）:66-76.

[3]Candillier L,Meyer F,Boulle M.Comparing State-of-the-Art Collaborative Filtering Systems[J].Machine Learning and Data Mining in Pattern Recognition，2007，11（4）：548-562.

[4]Vucetic S,Obradovic Z.Collaborative Filtering Using a Regression-Based Approach[J].Knowledge and Information Systems，2005，7 （1）:1-22.

[5]王鵬.基于矩陣分解的推薦系統(tǒng)算法研究[D].北京：北京交通大學(xué).

Recommender System;Collaborative Filtering;Linear Regression;Matrix Factorization

Comparable Research on Collaborative Filtering Recommendation Algorithms

ZHOU Hong-yu1，LIANG Gang1，YANG Jin2
（1.College of Computer Science,，Sichuan University，Chengdu 610065；2.College of Computer Science,，Leshan Normal University，Leshan 614000）

1007-1423（2016）07-0016-04

10.3969/j.issn.1007-1423.2016.07.004

周泓宇（1990-），男，碩士，研究方向為機器學(xué)習(xí)

梁剛（1976-），男，博士，講師，研究方向為機器學(xué)習(xí)、智能計算、網(wǎng)絡(luò)安全

楊進（1980-），男，博士，教授，研究方向為機器學(xué)習(xí)

2016-01-15

2016-02-20

推薦系統(tǒng)被廣泛用于電子商務(wù)、視頻網(wǎng)站、新聞小說推薦等各個領(lǐng)域，旨在向用戶提供其可能感興趣的信息。協(xié)同過濾是推薦系統(tǒng)的主流技術(shù)，分為基于內(nèi)存的協(xié)同過濾、基于模型的協(xié)同過濾以及組合協(xié)同過濾。以其中基于用戶（項目）、基于矩陣分解以及基于線性回歸集成策略的協(xié)同過濾算法為例進行說明比較，然后通過MovieLens的數(shù)據(jù)集進行實驗對比。

推薦系統(tǒng)；協(xié)同過濾；線性回歸；矩陣分解

四川省科技廳項目（No.2014JY0036）、四川省教育廳創(chuàng)新團隊基金（No.13TD0014）

Recommender system designed to provide users with information that may be of interest is widely used in E-Commerce,video websites, news and novels recommendation,etc.Collaborative filtering is the main technology of recommender system,is divided into three classes: collaborative filtering based on memory,collaborative filtering based on the model and hybrid recommendation.Compares the algorithms of user(item)based,matrix factor based and linear regression in integration strategy as an example and gets the result through experimen-tal comparison with the dataset of MovieLens system.