于娜娜，王中杰（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海201804）

?

基于Spark的協(xié)同過濾算法的研究

于娜娜，王中杰
（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海201804）

摘 要：隨著互聯(lián)網(wǎng)的普及，人們從海量的信息中搜索出自己所需要的信息無疑變得非常困難。推薦系統(tǒng)能夠通過分析用戶的興趣和行為而智能地向用戶推薦所需信息，因而得到人們的青睞，并激發(fā)了各界人士對它的研究興趣。基于ALS的協(xié)同過濾推薦算法是推薦系統(tǒng)中比較常用的一種通過矩陣分解技術(shù)進(jìn)行推薦的算法，它通過綜合大量的用戶評分?jǐn)?shù)據(jù)進(jìn)行計算，并存儲計算過程中產(chǎn)生的龐大特征矩陣，如果在單節(jié)點上運行可能會遇到計算速度的瓶頸。SPark是一種新型的分布式大數(shù)據(jù)通用計算平臺，具有優(yōu)異的計算性能，本文主要對現(xiàn)有的基于ALS的協(xié)同過濾算法和SPark進(jìn)行了研究，實現(xiàn)了基于ALS的協(xié)同過濾算法在SPark上的并行化運行，并且通過實驗與HadooP對比證明了該算法在SPark上運行的快速性。

關(guān)鍵詞：推薦系統(tǒng)；協(xié)同過濾；矩陣分解；ALS；SPark

1　引 言

隨著互聯(lián)網(wǎng)的普及和互聯(lián)網(wǎng)用戶數(shù)量的迅猛增長，互聯(lián)網(wǎng)上的信息呈現(xiàn)爆炸式的增長。雖然海量的信息為滿足互聯(lián)網(wǎng)用戶紛繁復(fù)雜的信息需求帶來了前所未有的機(jī)遇，但是也對信息處理技術(shù)提出嚴(yán)峻的挑戰(zhàn)［1］，用戶無法從海量的信息中快速準(zhǔn)確地搜索到自己所需要的信息。在這種背景下，推薦系統(tǒng)應(yīng)運而生，推薦系統(tǒng)通過收集和分析用戶的各種信息來學(xué)習(xí)用戶的興趣和行為模式，來為用戶推薦他所需要的服務(wù)［1～3］。協(xié)同過濾是推薦技術(shù)中運用最成功和最廣泛的技術(shù)之一，主要分三類：基于用戶（User-based）的協(xié)同過濾，基于項目（Item-based）的協(xié)同過濾和基于模型（Model-based）的協(xié)同過濾。本文主要研究基于模型的協(xié)同過濾。

基于模型的協(xié)同過濾是一個典型的機(jī)器學(xué)習(xí)的問題，主要是基于樣本的用戶喜好信息，訓(xùn)練一個推薦模型，然后根據(jù)實時的用戶喜好信息進(jìn)行預(yù)測，計算推薦，核心在于如何將用戶實時或者近期的喜好信息反饋給訓(xùn)練好的模型，從而提高推薦的準(zhǔn)確度［4］。該算法性能的優(yōu)劣關(guān)鍵在于好的模型建立與否，因為好的模型相對原始數(shù)據(jù)集而言小得多卻能挖掘出用戶和項目之間更多的潛在關(guān)系，在一定程度上不僅有效緩解了推薦算法的實時性問題，同時有效解決了用戶ˉ項目評分矩陣的稀疏性問題，在推薦性能上更優(yōu)［5］。當(dāng)前，基于模型的協(xié)同過濾算法主要包括概率相關(guān)模型、線性回歸、聚類等數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)方面的模型［6］。本文主要介紹的基于ALS矩陣分解算法就屬于基于隱語義模型（Latent Factor Model）的協(xié)同過濾推薦算法。在這個模型里，用戶和商品通過一組隱性因子進(jìn)行表達(dá)，并且這些因子也用來預(yù)測缺失的元素，那么學(xué)習(xí)這些潛在因子的方法本文用的便是交替最小二乘法ALS。

在目前的協(xié)同過濾研究中，大多是單節(jié)點進(jìn)行實驗和調(diào)試的。但隨著大數(shù)據(jù)時代的到來，推薦系統(tǒng)需要存儲的用戶數(shù)據(jù)和物品數(shù)據(jù)迅速增長，在單節(jié)點上計算并實現(xiàn)這些算法變得非常慢，使得推薦無法實時進(jìn)行，推薦周期很長，更新和反饋很慢將會導(dǎo)致用戶體驗不好，無法滿足用戶興趣的變化，因此需要對這些算法進(jìn)行并行計算，提高算法計算效率，加速推薦結(jié)果的產(chǎn)生，適應(yīng)用戶興趣的變化，同時也會推動大數(shù)據(jù)協(xié)同過濾算法的學(xué)術(shù)研究和實踐應(yīng)用。

目前的數(shù)據(jù)并行處理平臺有兩種，即HadooP 和SPark。由于HadooP的MaPReduce每次計算都要從磁盤讀或?qū)憯?shù)據(jù)，同時整個計算模型需要網(wǎng)絡(luò)傳輸，這就導(dǎo)致了HadooP越來越不能忍受的高延遲性。SPark，這種新型的分布式大數(shù)據(jù)計算平臺的出現(xiàn)正解決了此困境，基于RDD（彈性分布式數(shù)據(jù)集），它的Job中間輸出和結(jié)果可保存在內(nèi)存中，減少了訪問硬盤I/O次數(shù)，可以有較高的運算速度。因此本文著重研究基于ALS的協(xié)同過濾算法在SPark上的實現(xiàn)問題。

2　Spark平臺

2.1Spark平臺部署

2.1.1環(huán)境說明

本文搭建的SPark集群采用的是實驗室的三臺普通PC，包括1個Master節(jié)點和2個Slave節(jié)點，三個節(jié)點均為Ubuntu14.10系統(tǒng)，節(jié)點之間局域網(wǎng)連接。具體情況如表1所示。

表1　節(jié)點具體說明Tab.1 The details of th ree nodes

2.1.2軟件安裝

JavaJDK用的是jdk -7u75 -linux-i586.gz，hadooP版本為hadooP -2.6.0.tar.gz，安裝過程中最重要的一點就是配置SSH實現(xiàn)無密碼遠(yuǎn)程登陸與管理。搭建好HadooP集群之后，在此基礎(chǔ)上進(jìn)行SPark的安裝，其版本為SPark1.2.0，開發(fā)環(huán)境IntelliJIDEA 14.0.3，對應(yīng)的Scala為scala-sdk -2.10.4。所有軟件在三臺機(jī)器上安裝并配置好后即可啟動SPark分布式集群。

2.2Spark集群的特點

APache SPark官方的定義是［7］：SPark是一個通用的大規(guī)模數(shù)據(jù)快速處理引擎?？梢院唵蔚乩斫鉃镾Park就是一個大數(shù)據(jù)分布式處理框架。SPark具有以下優(yōu)勢：快速性，SPark基于內(nèi)存的計算速度比HadooP MaP Reduce快很多。易用性，提供多語言編程，簡潔的函數(shù)式編程語言Scala能快速實現(xiàn)應(yīng)用。通用性，提供了一個強(qiáng)大的技術(shù)堆棧，如機(jī)器學(xué)習(xí)工具M(jìn)Llib，圖計算工具GraPhX，實時流處理工具SPark Streaming等，尤其是MLlib使得原本復(fù)雜的機(jī)器學(xué)習(xí)在理解和使用上變的靈活而簡易。本文的協(xié)同過濾算法即是基于MLlib實現(xiàn)的。

RDD（Resilient Distributed Datasets）是SPark的核心，是分布于各個計算節(jié)點存儲于內(nèi)存中的數(shù)據(jù)對象集合，可以讓用戶在執(zhí)行多個查詢時顯式地將數(shù)據(jù)緩存在內(nèi)存中，在后續(xù)的查詢過程中能夠重用這些數(shù)據(jù)集，從而提供了低延遲性。RDD具有很好的容錯機(jī)制，它能記住構(gòu)建它的操作圖，記錄如何從其他RDD轉(zhuǎn)換而來（即Lineage），當(dāng)執(zhí)行任務(wù)的數(shù)據(jù)節(jié)點出現(xiàn)故障，可以通過操作圖獲得之前執(zhí)行的操作而恢復(fù)丟失的分區(qū)即重建丟失的數(shù)據(jù)。RDD只能通過在其他RDD執(zhí)行確定的轉(zhuǎn)換操作而創(chuàng)建，與大多數(shù)的分布式數(shù)據(jù)集采用的需付出高昂成本代價的數(shù)據(jù)檢查點的容錯性實現(xiàn)方式不同，RDD只包含如何從其他RDD衍生所必需的信息，不需要檢查點操作就可以重構(gòu)丟失的數(shù)據(jù)分區(qū)。

2.3Spark的工作流程

在SPark中，數(shù)據(jù)集的劃分和任務(wù)調(diào)度都是系統(tǒng)自動完成的，其工作流程如圖1所示。

SPark程序在運行時，首先會創(chuàng)建SParkContext來作為任務(wù)調(diào)度的總?cè)肟?，在其初始化工作環(huán)境過程中會創(chuàng)建DAGScheduler（進(jìn)行Stage調(diào)度）和Task Scheduler（進(jìn)行Task調(diào)度）兩個模塊。DAGScheduler模塊負(fù)責(zé)為每個SParkJob計算具有依賴關(guān)系的多個Stage任務(wù)階段，然后將每個Stage劃分為具體的一組任務(wù)（可以在worker節(jié)點上并行執(zhí)行的tasks），并以TaskSet的形式提交給TaskScheduler模塊來執(zhí)行。

圖1　Spark工作流程Fig.1 W ork ing Process of Spark

3　基于ALS的協(xié)同過濾算法

基于矩陣分解模型的協(xié)同過濾推薦算法主要有：SVD（奇異值分解）和ALS。實際上，矩陣分解模型與前面提到的隱語義模型是一個意思，即通過降維的方式將評分矩陣補(bǔ)全。早期的SVD首先通過加權(quán)平均值等方法對用戶評分矩陣R中的空缺元素補(bǔ)全得到矩陣R?，然后利用數(shù)學(xué)中的SVD對R?進(jìn)行分解。Simon、Korean［8］等人也提出新的SVD++模型，然而這種方法的計算復(fù)雜度非常高，很難在實際的推薦系統(tǒng)中應(yīng)用［9］。隨著Netflix Prize比賽的進(jìn)行，先后出現(xiàn)了一些高效的矩陣分解算法，其中Zhou等［10］人提出的基于交替最小二乘法（ALS）的協(xié)同過濾算法是一個強(qiáng)大的矩陣分解算法，能很好的擴(kuò)展到分布式計算以及解決數(shù)據(jù)稀疏問題。下面以用戶與電影評分矩陣為例來講述基于ALS協(xié)同過濾算法的原理［11］。

為了防止過擬合，給上式添加二階正則化項，即為：

如果已知V，可以使用嶺回歸（Ridge Regression）預(yù)測U的每一行，反之亦可。因此，固定V矩陣，對Ui求導(dǎo)，得到下面求解Ui.的公式

在上式中，Ri.表示用戶i對電影的評分向量，Vui表示由用戶i評價過的電影的特征向量組成的特征矩陣。nui表示用戶i評價過的電影數(shù)量。同理，固定U矩陣，得到下面求解Vj.的公式

在上式中，R.j表示給電影j評過分的用戶的評分向量，Umj表示由為電影j評過分的用戶的特征向量組成的特征矩陣。nmj表示為電影j評過分的用戶數(shù)量。I為一個d×d的單位矩陣。

基于交替最小二乘法（ALS）的協(xié)同過濾算法，即是交替調(diào)用公式（4）、（5）更新計算U，V。直到計算出的結(jié)果收斂或者迭代的次數(shù)達(dá)到最大值，然后結(jié)束計算。最終求出逼近矩陣X，使用X進(jìn)行電影的推薦。

在SPark上實現(xiàn)算法時，首先將原始的數(shù)據(jù)集存放在分布式文件系統(tǒng)HDFS上，然后讀取HDFS上的數(shù)據(jù)，并將其轉(zhuǎn)化為壓縮矩陣，根據(jù)轉(zhuǎn)化后的矩陣數(shù)據(jù)創(chuàng)建RDD，將每次迭代產(chǎn)生的中間數(shù)據(jù)U和V，以及數(shù)據(jù)集緩存（cache）到內(nèi)存中［12］。

4　實驗結(jié)果分析

4.1實驗數(shù)據(jù)集

由于搜集滿足條件的數(shù)據(jù)集不是很方便，所以本文采用了網(wǎng)上公開的MovieLens的數(shù)據(jù)集［13］，在這里選用的是100K（10萬條），1M（約100萬條）和從100K中隨機(jī)抽取的1萬條這三組的數(shù)據(jù)進(jìn)行實驗，分別隨機(jī)取數(shù)據(jù)集中的80%作為訓(xùn)練集，20%作為測試集。

4.2結(jié)果分析

4.2.1準(zhǔn)確度

該算法是一個典型的基于評分的用戶-商品推薦算法，推薦結(jié)果的準(zhǔn)確度必是推薦中的核心問題，我們一般采用均方根誤差（RMSE）來評價評分預(yù)測的準(zhǔn)確度。誤差越小，意味著準(zhǔn)確度越高。其公式為：

在式（6）中，rui表示用戶u對電影i的實際評分，是通過推薦算法預(yù)測的評分。該部分選用的是100K數(shù)據(jù)集。

在上述ALS算法中，我們知道需要設(shè)置一些訓(xùn)練參數(shù)，參數(shù)選擇的好壞直接決定了模型的好壞。ALS訓(xùn)練算法中最重要的參數(shù)是正則化常數(shù)λ和迭代次數(shù)。當(dāng)兩個參數(shù)取值不同時，實驗結(jié)果如表2所示。由圖可以看出，正則化常數(shù)對結(jié)果影響非常大，迭代次數(shù)影響稍小。通過不斷地嘗試，找到最佳模型參數(shù)取值。當(dāng)然，其他的模型參數(shù)如矩陣因子排名，特征值個數(shù)對結(jié)果也有影響，還有待研究。

4.2.2快速性

快速性是推薦系統(tǒng)中至關(guān)重要的問題，它決定了一個算法能否根據(jù)用戶興趣和喜好的變化實時的推薦相關(guān)物品，我們分別采用1W、10W和100W條數(shù)據(jù)對HadooP和SPark的快速性分別進(jìn)行了分析，如圖2所示。

表2　參數(shù)影響Tab.2 Effects of param eters

圖2　快速性比較Fig.2 The com parison of rapid ity

由圖2可以看出，當(dāng)數(shù)據(jù)量很小時，HadooP 與SPark的運行時間差別不大，當(dāng)數(shù)據(jù)量越大，SPark的基于內(nèi)存計算的優(yōu)勢越能夠體現(xiàn)出來，而且當(dāng)數(shù)據(jù)量增大時，SPark的運行時間增加得比較緩慢，HadooP增加得比較快速，可以想象，當(dāng)數(shù)據(jù)量非常大時，HadooP運行將會非常慢，從而不能夠及時地向用戶推薦當(dāng)下喜歡的物品。

5　結(jié)束語

本文主要是研究了基于ALS的協(xié)同過濾推薦算法在SPark平臺上的實現(xiàn)，通過實驗表明，SPark作為新一代數(shù)據(jù)并行處理平臺，在運行時間和運行準(zhǔn)確度上都有良好的表現(xiàn)，能夠有效地處理大數(shù)據(jù)的運算問題，而且數(shù)據(jù)量越大，這種優(yōu)勢越明顯。但SPark作為新出現(xiàn)的并行數(shù)據(jù)處理平臺，后續(xù)還有很多工作要做，如（1）對SPark平臺工作原理深入研究，在任務(wù)調(diào)度方面進(jìn)行優(yōu)化，達(dá)到負(fù)載均衡，提高運算速度。（2）ALS模型訓(xùn)練參數(shù)的選擇，尋求一種智能算法，能幫我們自動的選擇最優(yōu)的參數(shù)，而不是手工嘗試。（3）增加SPark集群節(jié)點數(shù)目，在故障性和擴(kuò)展性方面進(jìn)行研究。

參考文獻(xiàn)：

［1］ Ricci F，Rokach L，ShaPira B，et al.Recommender system handbook［M］.［S.l.］：SPringer，2011.

［2］ 李改，李磊.基于矩陣分解的協(xié)同過濾算法［J］.計算機(jī)工程與應(yīng)用，2011，47（30）：4 -7.

LIGai，LILei.The collaborative filtering algorithm based on matrix decomPosition［J］.ComPuter Engineering and APPlications，2011，47（30）：4 -7.

［3］ 劉青文.基于協(xié)同過濾的推薦算法研究［D］.中國科學(xué)技術(shù)大學(xué)，2013.

LIU Qingwen.Research of recommendation algorith -mbased on collaborative filtering［D］.University of Science and Technology of China，2013.

［4］ 王家林.大數(shù)據(jù)SPark企業(yè)級實戰(zhàn)［C］.北京：電子工業(yè)出版社，2015，431 -450.

WANG Jialin.The enterPrise actual combat of big data SPark［C］.Beijing：Publishing House of Electronics Industry，2015，431 -450.

［5］ 王全民，苗雨，何明，鄭爽.基于矩陣分解的協(xié)同過濾算法的并行化研究［J］.計算機(jī)技術(shù)與發(fā)展，2015，25 （2）：55 -59.

WANG Quanmin，MIAO Yu，HE Ming，ZHENG Shuang. Parallelize research of collaborative filtering algorithm based on matrix factorization［J］.ComPuter Technology and DeveloPment，2015，25（2）：55 -59.

［6］ 劉希偉.基于協(xié)同過濾的大數(shù)據(jù)挖掘分析方法研究［D］.浙江工業(yè)大學(xué)，2014.

LIU Xiwei.Research on big datamining analysismethod based on collaborative filtering［D］.Zhejiang University of Technology，2014.

［7］ httP：∥sPark.aPache.org/

［8］ Pan R，Zhou Y，Cao B，et al.One-class collaborative filtering［C］∥Data M ining，2008.ICDM?08.Eighth IEEE International Conference.IEEE，2008：502 -511.

［9］ 劉強(qiáng).協(xié)同過濾推薦系統(tǒng)中的關(guān)鍵算法研究［D］.浙江大學(xué)，2013.

LIU Qiang. Research on the key algorithm in collaborative filtering recommendation system［D］. Zhejiang University，2013.

［10］ Zhou Yunhong，W ilkinson D，Schreiber R，et al.Large-scale Parallel collaborative filtering for the netflix Prize ［C］∥Proc of the 4 th international conference on algorthmic asPects in information and management. Shanghai：SPringer，2008：337 -348.

［11］ httP：∥www2.research.att.com/～volinsky/PaPers/ ieeecomPuter.Pdf

［12］ 高彥杰.SPark大數(shù)據(jù)處理，技術(shù)、應(yīng)用與性能優(yōu)化［C］.北京：機(jī)械工業(yè)出版社，2015，215 -237.

GAOYanjie.The Processing of SPark big data，technology，aPPlication and Performance oPtim ization［C］. Beijing：China Machine Press，2015，215 -237.

［13］ httP：∥grouPlens.org/datasets/movielens/

［14］ Y.Koren.Factorization Meets the Neighborhood：a Multifaceted Collaborative Filtering Model. In Proceedings of the 14 th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining，ACM，2008：426 -434.

［15］ 孫遠(yuǎn)帥.基于大數(shù)據(jù)的推薦算法研究［D］.廈門大學(xué)，2014.

SUN Yuanshuai.Recommendation A lgorithms in the big data Era［D］.Xiamen University，2014.

于娜娜 女（1990 -），山東曲阜人，碩士生，主要研究方向為控制理論與控制工程，分布式計算等。

王中杰 女（1971 -），遼寧葫蘆島人、博士、教授，主要研究方向為智能系統(tǒng)、優(yōu)化理論與技術(shù)、大數(shù)據(jù)應(yīng)用。

Research on Collaborative Filtering Algorithm Based onSpark

YU Nana，WANG Zhongjie
（Tongji University，College of Electronic and Information，Shanghai201804，China）

Abstrac t：W ith the PoPularity of the Internet，it undoubtedly becomes very difficult for PeoPle to search the information they need from the vast amounts of information.Recommendation system can recommend related information to users intelligently through the analysis of the interests and behaviors of users. Therefore，it got the favor of PeoPle and insPired researchers' interests in study.The collaborative filtering recommendation algorithm based on ALS is one of a relatively common algorithm by matrix factorization technique from recommendation systems.Because it combines a lot of ratings data to calculate and store characteristic matrix in the Process of calculation，itmay encounter the bottleneck of com Putation sPeed if it runs on a single node.SPark is a new kind of distributed comPuting Platform in the big data era and it has excellent comPuting Performance.In this PaPer，firstly，we make research on the existing collaborative filtering algorithm based on ALS and the big data distributed com Puting Platform of SPark.Then，I realize Parallel oPeration of the algorithm on SPark.Finally，I Prove the quickness of the collaborative filtering recommendation algorithm runs on SPark by exPeriment comPared w ith HadooP.

Key words：recommendation system；collaborative filtering；matrix factorization；alternating least squares；sPark

中圖分類號：391

文獻(xiàn)標(biāo)識碼：A