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

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

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

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

0　引言

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

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

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

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

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

表1　用戶-項(xiàng)目m×n階評(píng)分矩陣R

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

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

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

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

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

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

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

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

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

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

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

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

4　實(shí)驗(yàn)結(jié)果與分析

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

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

4.2實(shí)驗(yàn)步驟

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

圖1　UBCF和IBCF的MAE指標(biāo)

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

圖2　MFCF的MAE指標(biāo)

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

圖3　四種算法MAE指標(biāo)的比較情況

5　結(jié)語

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

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

[2]王國霞，劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(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-），男，碩士，研究方向?yàn)闄C(jī)器學(xué)習(xí)

梁剛（1976-），男，博士，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)、智能計(jì)算、網(wǎng)絡(luò)安全

楊進(jìn)（1980-），男，博士，教授，研究方向?yàn)闄C(jī)器學(xué)習(xí)

2016-01-15

2016-02-20

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

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

四川省科技廳項(xiàng)目（No.2014JY0036）、四川省教育廳創(chuàng)新團(tuán)隊(duì)基金（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.