遲玉良 祝永志

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

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

DOI：10.11907/rjdk.172903

中圖分類號：

文獻標識碼：A 文章編號：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 引言

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

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

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

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

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

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

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

2 混合推薦

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

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

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

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

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

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

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

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

2.3 混合方法

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

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

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

3 實驗與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻：

[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] 文俊浩，舒珊.一種改進相似性度量的協(xié)同過濾推薦算法[J].計算機科學，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é)同過濾系統(tǒng)項目冷啟動的混合推薦算法[J].計算機工程，2008，34（23）：11-13.

[8] 郁雪，李敏強.一種有效緩解數(shù)據(jù)稀疏性的混合協(xié)同過濾算法[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ò)和標簽的混合推薦算法[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.

（責任編輯：黃 健）