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

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　基于線(xiàn)性回歸的集成策略

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

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

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

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

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

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

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

為了直觀地比較基于線(xiàn)性回歸的集成算法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é)語(yǔ)

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

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

[2]王國(guó)霞，劉賀平.個(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)站、新聞小說(shuō)推薦等各個(gè)領(lǐng)域，旨在向用戶(hù)提供其可能感興趣的信息。協(xié)同過(guò)濾是推薦系統(tǒng)的主流技術(shù)，分為基于內(nèi)存的協(xié)同過(guò)濾、基于模型的協(xié)同過(guò)濾以及組合協(xié)同過(guò)濾。以其中基于用戶(hù)（項(xiàng)目）、基于矩陣分解以及基于線(xiàn)性回歸集成策略的協(xié)同過(guò)濾算法為例進(jìn)行說(shuō)明比較，然后通過(guò)MovieLens的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比。

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

四川省科技廳項(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.