遲玉良 祝永志

摘 要：協(xié)同過(guò)濾算法是當(dāng)今推薦系統(tǒng)普遍使用的一種推薦算法。面對(duì)單機(jī)模型已逐漸承受不了大數(shù)據(jù)給推薦系統(tǒng)帶來(lái)的負(fù)荷問(wèn)題，提出基于Spark平臺(tái)的一種項(xiàng)目相似度與ALS相結(jié)合的協(xié)同過(guò)濾推薦算法。它基于Spark分布式并行計(jì)算框架，可提高預(yù)測(cè)計(jì)算效率，減少系統(tǒng)響應(yīng)時(shí)間。同時(shí)使用“基于項(xiàng)目相似度的協(xié)同過(guò)濾”與“交替最小二乘的協(xié)同過(guò)濾（ALS）”相結(jié)合的一種混合推薦方法，可提高系統(tǒng)推薦精度。通過(guò)在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法在算法融合與推薦精度上有著很好的效果。

關(guān)鍵詞：項(xiàng)目相似度；ALS；協(xié)同過(guò)濾；混合推薦；Spark

DOI：10.11907/rjdk.172903

中圖分類(lèi)號(hào)：

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）006-0081-04

Abstract：Collaborative filtering algorithm is a recommended algorithm commonly used in today′s recommended systems. In this paper， a collaborative filtering recommendation algorithm based on Spark platform is proposed， which is a kind of project similarity degree and ALS. In this paper， we propose a cooperative filtering algorithm based on Spark platform. It is based on spark distributed parallel computing framework to improve the efficiency of forecasting and reduce system response time. Collaborative filtering based on project similarity and alternating least squares of cooperative filtering （ALS） are used to improve the accuracy recommended by the system. Through the experiment results of the MovieLens dataset， it is concluded that the algorithm has a considerable effect on the algorithm fusion and recommendation accuracy.

Key Words：item similarity； ALS； collaborative filtering； hybrid recommender； Spark

0 引言

當(dāng)今，互聯(lián)網(wǎng)技術(shù)發(fā)展迅速，信息量出現(xiàn)爆炸式增長(zhǎng)，對(duì)海量數(shù)據(jù)進(jìn)行存取并挖掘出其中隱藏的知識(shí)與價(jià)值一直是學(xué)術(shù)界和商業(yè)界研究的重點(diǎn)[1]。為了滿足用戶的個(gè)性化需求，推薦系統(tǒng)應(yīng)運(yùn)而生。一個(gè)優(yōu)秀的推薦系統(tǒng)[2]能預(yù)測(cè)出不同用戶偏好條件下需要的信息，相比于傳統(tǒng)的搜索引擎技術(shù)，有著更好的用戶體驗(yàn)。據(jù)統(tǒng)計(jì)，Amazon的商品推薦為其帶來(lái)了35%的額外銷(xiāo)售額?；趨f(xié)同過(guò)濾的推薦算法[3]無(wú)疑是使用最廣泛的算法，其通過(guò)對(duì)已有的部分?jǐn)?shù)據(jù)構(gòu)建預(yù)測(cè)模型，計(jì)算其用戶或項(xiàng)目的相互關(guān)系[4]，預(yù)測(cè)未知用戶的偏好并提供個(gè)性化推薦服務(wù)。其算法也可分為基于用戶的推薦算法[5]和基于項(xiàng)目的推薦算法[6]?；谟脩舻膮f(xié)同過(guò)濾推薦算法主要通過(guò)計(jì)算不同用戶之間的相似度，將與目標(biāo)用戶相似性較高的用戶對(duì)商品的評(píng)價(jià)信息作為參考，推薦給目標(biāo)用戶；基于項(xiàng)目的協(xié)同過(guò)濾推薦算法則是通過(guò)尋找項(xiàng)目之間的相似性進(jìn)行推薦。兩種算法都有其適用的場(chǎng)合與缺點(diǎn)，如基于用戶的推薦算法有冷啟動(dòng)[7]問(wèn)題，基于項(xiàng)目的推薦算法不適合項(xiàng)目信息頻繁變動(dòng)或數(shù)據(jù)增長(zhǎng)量很大的情形，同時(shí)兩種算法都存在數(shù)據(jù)稀疏性問(wèn)題[8]。如今，采用混合推薦算法[9]可以起到取長(zhǎng)補(bǔ)短、提高推薦準(zhǔn)確度的效果。文獻(xiàn)[10]提出的結(jié)合用戶偏好和標(biāo)簽的混合算法提高了推薦命中率。本文提出的混合推薦算法針對(duì)電影推薦系統(tǒng)目前遇到的問(wèn)題，采用ALS算法[11]和基于項(xiàng)目相似度融合的思想，并在Spark平臺(tái)上加以實(shí)現(xiàn)，目的是提高算法計(jì)算效率并提升預(yù)測(cè)精度。

1 Spark平臺(tái)推薦架構(gòu)

Spark 是一個(gè)快速和通用的大規(guī)模數(shù)據(jù)處理平臺(tái)，其于2009 年誕生于伯克利大學(xué)AMP Lab，并在2010 年開(kāi)源。發(fā)展至今，Spark 已經(jīng)在流處理、圖計(jì)算、機(jī)器學(xué)習(xí)、結(jié)構(gòu)化數(shù)據(jù)查詢等各個(gè)方面取得了很多成果。國(guó)內(nèi)對(duì)于Spark 的研究主要集中在互聯(lián)網(wǎng)行業(yè)，如阿里巴巴、騰訊、百度、網(wǎng)易、搜狐等公司。Spark 具有基于內(nèi)存的處理模式[12]，在迭代計(jì)算方面的速度遠(yuǎn)遠(yuǎn)優(yōu)于MapReduce[13]。目前國(guó)內(nèi)外有很多公司都利用Spark 平臺(tái)部署推薦系統(tǒng)。

圖1為基于Spark on YARN構(gòu)建的推薦系統(tǒng)架構(gòu)，共分為數(shù)據(jù)存儲(chǔ)層、平臺(tái)計(jì)算層、系統(tǒng)推薦層。

（1） 數(shù)據(jù)存儲(chǔ)層。使用目前應(yīng)用最廣泛的Hadoop平臺(tái)下分布式文件系統(tǒng)HDFS，實(shí)現(xiàn)對(duì)大數(shù)據(jù)集的存儲(chǔ)與讀取。HDFS有著高容錯(cuò)性、適合批處理、成本低等優(yōu)點(diǎn)。

（2） 平臺(tái)計(jì)算層。采用YARN集群下的Spark平臺(tái)，可以與HDFS無(wú)縫結(jié)合，在推薦算法的迭代計(jì)算中具有很大優(yōu)勢(shì)，并且為多種語(yǔ)言開(kāi)發(fā)提供了大量方法庫(kù)和接口。

（3）系統(tǒng)推薦層。主要針對(duì)模型構(gòu)建和算法實(shí)現(xiàn)，對(duì)數(shù)據(jù)集作預(yù)處理并分別傳給基于項(xiàng)目相似度的協(xié)同過(guò)濾算法和基于交替最小二乘的協(xié)同過(guò)濾算法進(jìn)行訓(xùn)練，利用Spark集群同時(shí)進(jìn)行算法計(jì)算得到預(yù)測(cè)結(jié)果，然后將其傳入經(jīng)預(yù)測(cè)驗(yàn)證后的基于權(quán)重的融合算法中，最后得到各用戶對(duì)不同電影的預(yù)測(cè)評(píng)分。

2 混合推薦

2.1 基于項(xiàng)目相似度的協(xié)同過(guò)濾

由于不同用戶的評(píng)分尺度有所差異，有的用戶喜歡評(píng)高分，也有用戶評(píng)分很苛刻，因而評(píng)分尺度在一定程度上對(duì)項(xiàng)目整體評(píng)分有所影響。所以本文使用改進(jìn)的基于項(xiàng)目相似度的協(xié)同過(guò)濾算法，通過(guò)對(duì)余弦相似度算法[14]的修正，在用戶對(duì)每個(gè)項(xiàng)目評(píng)分的基礎(chǔ)上與該用戶的總體平均打分取差值，從而判定該項(xiàng)目的相對(duì)評(píng)分，以彌補(bǔ)用戶差異問(wèn)題，其中當(dāng)前用戶u∈U，待評(píng)分項(xiàng)目 i∈I，j∈I且i≠j。

如圖2所示，首先計(jì)算項(xiàng)目 i 與 I 中其它所有項(xiàng)目的相似性 sim*（i，j），然后結(jié)合最流行的中心最近鄰選取方法，對(duì)于i∈I構(gòu)建相似性矩陣A-sim*（i，j），按從大到小順序排列，可得到每個(gè)項(xiàng)目與其它所有項(xiàng)目的相似關(guān)系。

在評(píng)分預(yù)測(cè)算法上，選取一定數(shù)量相似度高的項(xiàng)目，過(guò)濾掉噪聲和低關(guān)聯(lián)信息[15]，利用基于項(xiàng)目均值的加權(quán)平均值計(jì)算推薦評(píng)分。其中P-u，i表示用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，KNNI（i） 表示項(xiàng)目i的K最鄰集合，-i和-j分別表示項(xiàng)目i和j的評(píng)分均值。

2.2 基于交替最小二乘的協(xié)同過(guò)濾

交替最小二乘（ALS）通過(guò)矩陣分解觀察用戶給項(xiàng)目的打分，基于評(píng)分矩陣是低秩矩陣，主要思想是找到兩個(gè)低維矩陣 X-（m×k）和矩陣Y-（n×k）近似逼近R-（m×n）。

ALS的具體求解方法是一個(gè)交替迭代計(jì)算過(guò)程，先固定其中一個(gè)矩陣如Y，將損失函數(shù)L-（X，Y）對(duì)x-u求偏導(dǎo)，并令導(dǎo)數(shù)等于0，得到：

如圖3所示，迭代計(jì)算分解矩陣特征值，計(jì)算得到的特征值向量代表用戶對(duì)項(xiàng)目及項(xiàng)目對(duì)用戶的隱式關(guān)系，最后矩陣相乘得到預(yù)測(cè)評(píng)分。

2.3 混合方法

為了結(jié)合基于項(xiàng)目相似度和ALS算法的優(yōu)點(diǎn)并彌補(bǔ)其缺點(diǎn)，本文采用基于權(quán)重的混合方法。如圖4所示，將兩種模型計(jì)算的結(jié)果機(jī)遇比例λ融合，其中 S-（u，i） 代表基于項(xiàng)目相似度的預(yù)測(cè)評(píng)分，A-（u，i） 代表交替最小二乘模型的預(yù)測(cè)評(píng)分。

為驗(yàn)證對(duì)應(yīng)權(quán)值的混合效果，將預(yù)測(cè)結(jié)果和測(cè)試數(shù)據(jù)進(jìn)行比較，計(jì)算其平均絕對(duì)誤差（MAE）值。

MAE作為推薦系統(tǒng)常用的評(píng)估標(biāo)準(zhǔn)，表示推薦系統(tǒng)對(duì)某個(gè)項(xiàng)目的預(yù)測(cè)值與真實(shí)值之間的關(guān)系，能夠很好地反映推薦結(jié)果質(zhì)量。如圖4所示通過(guò)對(duì)比不同權(quán)值計(jì)算得出的MAE值，選取誤差最小的λ作為混合比例，最終得出預(yù)測(cè)結(jié)果。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

本文使用GroupLens 研究小組提供的MovieLens數(shù)據(jù)集，數(shù)據(jù)集版本選擇包含約700位用戶對(duì)9 000部電影評(píng)分的最新版本，評(píng)分?jǐn)?shù)據(jù)約10萬(wàn)條。實(shí)驗(yàn)環(huán)境采用架設(shè)在Macbook上的ubuntu16.04虛擬Hadoop集群，共包含3個(gè)節(jié)點(diǎn)，存儲(chǔ)方式采用HDFS，Spark集群依賴于YARN，編程語(yǔ)言使用Python。

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

將評(píng)分?jǐn)?shù)據(jù)拆分為訓(xùn)練數(shù)據(jù)與測(cè)試數(shù)據(jù)，訓(xùn)練數(shù)據(jù)作為數(shù)據(jù)源導(dǎo)入算法中計(jì)算預(yù)測(cè)評(píng)分，測(cè)試數(shù)據(jù)用于對(duì)預(yù)測(cè)評(píng)分的驗(yàn)證，兩者對(duì)比計(jì)算出的MAE值作為預(yù)測(cè)精準(zhǔn)度。

對(duì)于基于項(xiàng)目相似度的協(xié)同過(guò)濾算法，在不同稀疏度下選取不同數(shù)量的相似鄰居進(jìn)行實(shí)驗(yàn)。其中不同稀疏度可將訓(xùn)練數(shù)據(jù)占總數(shù)據(jù)的比例劃分為[20%， 40%， 60%， 80%]，其余作為測(cè)試數(shù)據(jù)。

實(shí)驗(yàn)結(jié)果如圖5所示，表明在不同稀疏程度下，源數(shù)據(jù)越充分，獲得的預(yù)測(cè)結(jié)果精確度越高，并且不同比例下的MAE值也大致呈等比例。在相鄰項(xiàng)目數(shù)量的選擇上，提高數(shù)量基數(shù)可以提高預(yù)測(cè)準(zhǔn)確度，但隨著鄰居數(shù)量的逐漸增加，提高程度逐漸縮小，同時(shí)對(duì)應(yīng)的數(shù)據(jù)計(jì)算量和運(yùn)行時(shí)間也會(huì)成比例增加。因此，在實(shí)際應(yīng)用中，需要對(duì)數(shù)據(jù)準(zhǔn)確度和計(jì)算時(shí)間進(jìn)行平衡，才能有效提升用戶體驗(yàn)。

對(duì)ALS算法在相同數(shù)據(jù)，且在不同迭代次數(shù)和特征數(shù)量條件下做實(shí)驗(yàn)，源數(shù)據(jù)使用80%作為訓(xùn)練數(shù)據(jù)，其中迭代次數(shù)選擇[5， 10， 15， 20]，特征數(shù)量選擇[4， 8， 12， 16]。

從圖6的結(jié)果看，在迭代次數(shù)增加的情況下，整體MAE值是減小的，并且對(duì)當(dāng)前數(shù)據(jù)最友好的特征數(shù)量是8。

利用訓(xùn)練數(shù)據(jù)所占的不同比例代表不同稀疏度，對(duì)ALS算法做實(shí)驗(yàn)，其中特征數(shù)量選擇8，迭代次數(shù)選擇20。

由圖7可以看出，訓(xùn)練數(shù)據(jù)的量是影響算法精確度的一個(gè)重要因素。在數(shù)據(jù)量較少的情況下，隨著源數(shù)據(jù)增加，算法精確度提升空間較大；在訓(xùn)練數(shù)據(jù)較為充足的情況下，提升數(shù)據(jù)量，MAE誤差值下降的速度會(huì)有所放緩。

考慮將兩個(gè)算法利用融合算法混合，這里選取最近鄰的數(shù)量為100，對(duì)基于項(xiàng)目算法占不同比例下混合的情況做實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖8所示，在混合算法權(quán)值不同的條件下，模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)有較為明顯的差別。訓(xùn)練數(shù)據(jù)較為稀疏時(shí)，基于項(xiàng)目相似度的模型可以更好地解決冷啟動(dòng)問(wèn)題；在源數(shù)據(jù)充足的情況下，ALS算法能更好地提升混合算法的精確度。

綜合以上實(shí)驗(yàn)，利用相同的源數(shù)據(jù)對(duì)比，在各推薦算法選用合適參數(shù)的情況下，推薦結(jié)果精度對(duì)比如表1所示。

圖9為其對(duì)比圖，通過(guò)分析可以得出，本文提出的基于項(xiàng)目相似度和ALS結(jié)合的協(xié)同過(guò)濾推薦算法在各種數(shù)據(jù)稀疏程度下都可較好地提高預(yù)測(cè)評(píng)分的準(zhǔn)確性，并且對(duì)混合算法權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整可以有效解決數(shù)據(jù)的冷啟動(dòng)問(wèn)題。

4 結(jié)語(yǔ)

本文首先對(duì)Spark平臺(tái)和建立在Spark平臺(tái)上的推薦框架進(jìn)行了介紹，指出其優(yōu)點(diǎn)和使用的廣泛性；然后對(duì)當(dāng)前流行的基于項(xiàng)目相似度的協(xié)同過(guò)濾算法和交替最小二乘算法進(jìn)行分析，提出使用修正的余弦相似度算法計(jì)算項(xiàng)目相似度，并提出利用權(quán)值將兩種算法進(jìn)行融合的算法；最后，在Spark集群環(huán)境下，利用MovieLens數(shù)據(jù)集對(duì)各算法進(jìn)行實(shí)驗(yàn)，通過(guò)對(duì)比分析證實(shí)了該算法的優(yōu)越性。

參考文獻(xiàn)：

[1] EPPLER M J， MENGIS J. The concept of information overload： a review of literature from organization science， accounting， marketing， MIS， and related disciplines[J]. IEEE Engineering Management Review， 2010，38（1）：3.

[2] BOBADILLA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey[J]. Knowledge-Based Systems， 2013，46（1）：109-132.

[3] YANG X， GUO Y， LIU Y， et al. A survey of collaborative filtering based social recommender systems[J]. Computer Communications， 2014，41（5）：1-10.

[4] 文俊浩，舒珊.一種改進(jìn)相似性度量的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)科學(xué)，2014，41（5）：68-71.

[5] ZHAO Z D， SHANG M. User-based collaborative-filtering recommendation algorithms on Hadoop[C].Third International Conference on Knowledge Discovery and Data Mining，IEEE Computer Society， 2010：478-481.

[6] HU W， YANG F， FENG Z. Item-based collaborative filtering recommendation algorithm based on MapReduce[M]. Multimedia， Communication and Computing Application，2015.

[7] 郭艷紅，鄧貴仕.協(xié)同過(guò)濾系統(tǒng)項(xiàng)目冷啟動(dòng)的混合推薦算法[J].計(jì)算機(jī)工程，2008，34（23）：11-13.

[8] 郁雪，李敏強(qiáng).一種有效緩解數(shù)據(jù)稀疏性的混合協(xié)同過(guò)濾算法[J].計(jì)算機(jī)應(yīng)用，2009，29（6）：1590-1593.

[9] GEUENS S. Factorization machines for hybrid recommendation systems based on behavioral， product， and customer data[C].ACM Conference on Recommender Systems，ACM， 2015：379-382.

[10] 張新猛，蔣盛益，李霞，等.基于網(wǎng)絡(luò)和標(biāo)簽的混合推薦算法[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（1）：119-124.

[11] KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems[J]. Computer， 2009，42（8）：30-37.

[12] ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient distributed datasets： a fault-tolerant abstraction for in-memory cluster computing[C]. Usenix Conference on Networked Systems Design and Implementation. USENIX Association， 2012：2.

[13] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[M]. ACM， 2008.

[14] WANG P. A personalized collaborative recommendation approach based on clustering of customers[J]. Physics Procedia， 2012，24（24）：812-816.

[15] BATES D， KLIEGL R， VASISHTH S， et al. Parsimonious mixed models[J]. Statistics， 2015.

[16] JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks[C].ACM Conference on Recommender Systems，ACM， 2010：135-142.

（責(zé)任編輯：黃 健）