于娜娜,王中杰(同濟(jì)大學(xué)電子與信息工程學(xué)院,上海201804)
?
基于Spark的協(xié)同過(guò)濾算法的研究
于娜娜,王中杰
(同濟(jì)大學(xué)電子與信息工程學(xué)院,上海201804)
摘 要:隨著互聯(lián)網(wǎng)的普及,人們從海量的信息中搜索出自己所需要的信息無(wú)疑變得非常困難。推薦系統(tǒng)能夠通過(guò)分析用戶的興趣和行為而智能地向用戶推薦所需信息,因而得到人們的青睞,并激發(fā)了各界人士對(duì)它的研究興趣?;贏LS的協(xié)同過(guò)濾推薦算法是推薦系統(tǒng)中比較常用的一種通過(guò)矩陣分解技術(shù)進(jìn)行推薦的算法,它通過(guò)綜合大量的用戶評(píng)分?jǐn)?shù)據(jù)進(jìn)行計(jì)算,并存儲(chǔ)計(jì)算過(guò)程中產(chǎn)生的龐大特征矩陣,如果在單節(jié)點(diǎn)上運(yùn)行可能會(huì)遇到計(jì)算速度的瓶頸。SPark是一種新型的分布式大數(shù)據(jù)通用計(jì)算平臺(tái),具有優(yōu)異的計(jì)算性能,本文主要對(duì)現(xiàn)有的基于ALS的協(xié)同過(guò)濾算法和SPark進(jìn)行了研究,實(shí)現(xiàn)了基于ALS的協(xié)同過(guò)濾算法在SPark上的并行化運(yùn)行,并且通過(guò)實(shí)驗(yàn)與HadooP對(duì)比證明了該算法在SPark上運(yùn)行的快速性。
關(guān)鍵詞:推薦系統(tǒng);協(xié)同過(guò)濾;矩陣分解;ALS;SPark
隨著互聯(lián)網(wǎng)的普及和互聯(lián)網(wǎng)用戶數(shù)量的迅猛增長(zhǎng),互聯(lián)網(wǎng)上的信息呈現(xiàn)爆炸式的增長(zhǎng)。雖然海量的信息為滿足互聯(lián)網(wǎng)用戶紛繁復(fù)雜的信息需求帶來(lái)了前所未有的機(jī)遇,但是也對(duì)信息處理技術(shù)提出嚴(yán)峻的挑戰(zhàn)[1],用戶無(wú)法從海量的信息中快速準(zhǔn)確地搜索到自己所需要的信息。在這種背景下,推薦系統(tǒng)應(yīng)運(yùn)而生,推薦系統(tǒng)通過(guò)收集和分析用戶的各種信息來(lái)學(xué)習(xí)用戶的興趣和行為模式,來(lái)為用戶推薦他所需要的服務(wù)[1~3]。協(xié)同過(guò)濾是推薦技術(shù)中運(yùn)用最成功和最廣泛的技術(shù)之一,主要分三類:基于用戶(User-based)的協(xié)同過(guò)濾,基于項(xiàng)目(Item-based)的協(xié)同過(guò)濾和基于模型(Model-based)的協(xié)同過(guò)濾。本文主要研究基于模型的協(xié)同過(guò)濾。
基于模型的協(xié)同過(guò)濾是一個(gè)典型的機(jī)器學(xué)習(xí)的問(wèn)題,主要是基于樣本的用戶喜好信息,訓(xùn)練一個(gè)推薦模型,然后根據(jù)實(shí)時(shí)的用戶喜好信息進(jìn)行預(yù)測(cè),計(jì)算推薦,核心在于如何將用戶實(shí)時(shí)或者近期的喜好信息反饋給訓(xùn)練好的模型,從而提高推薦的準(zhǔn)確度[4]。該算法性能的優(yōu)劣關(guān)鍵在于好的模型建立與否,因?yàn)楹玫哪P拖鄬?duì)原始數(shù)據(jù)集而言小得多卻能挖掘出用戶和項(xiàng)目之間更多的潛在關(guān)系,在一定程度上不僅有效緩解了推薦算法的實(shí)時(shí)性問(wèn)題,同時(shí)有效解決了用戶ˉ項(xiàng)目評(píng)分矩陣的稀疏性問(wèn)題,在推薦性能上更優(yōu)[5]。當(dāng)前,基于模型的協(xié)同過(guò)濾算法主要包括概率相關(guān)模型、線性回歸、聚類等數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)方面的模型[6]。本文主要介紹的基于ALS矩陣分解算法就屬于基于隱語(yǔ)義模型(Latent Factor Model)的協(xié)同過(guò)濾推薦算法。在這個(gè)模型里,用戶和商品通過(guò)一組隱性因子進(jìn)行表達(dá),并且這些因子也用來(lái)預(yù)測(cè)缺失的元素,那么學(xué)習(xí)這些潛在因子的方法本文用的便是交替最小二乘法ALS。
在目前的協(xié)同過(guò)濾研究中,大多是單節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)和調(diào)試的。但隨著大數(shù)據(jù)時(shí)代的到來(lái),推薦系統(tǒng)需要存儲(chǔ)的用戶數(shù)據(jù)和物品數(shù)據(jù)迅速增長(zhǎng),在單節(jié)點(diǎn)上計(jì)算并實(shí)現(xiàn)這些算法變得非常慢,使得推薦無(wú)法實(shí)時(shí)進(jìn)行,推薦周期很長(zhǎng),更新和反饋很慢將會(huì)導(dǎo)致用戶體驗(yàn)不好,無(wú)法滿足用戶興趣的變化,因此需要對(duì)這些算法進(jìn)行并行計(jì)算,提高算法計(jì)算效率,加速推薦結(jié)果的產(chǎn)生,適應(yīng)用戶興趣的變化,同時(shí)也會(huì)推動(dòng)大數(shù)據(jù)協(xié)同過(guò)濾算法的學(xué)術(shù)研究和實(shí)踐應(yīng)用。
目前的數(shù)據(jù)并行處理平臺(tái)有兩種,即HadooP 和SPark。由于HadooP的MaPReduce每次計(jì)算都要從磁盤(pán)讀或?qū)憯?shù)據(jù),同時(shí)整個(gè)計(jì)算模型需要網(wǎng)絡(luò)傳輸,這就導(dǎo)致了HadooP越來(lái)越不能忍受的高延遲性。SPark,這種新型的分布式大數(shù)據(jù)計(jì)算平臺(tái)的出現(xiàn)正解決了此困境,基于RDD(彈性分布式數(shù)據(jù)集),它的Job中間輸出和結(jié)果可保存在內(nèi)存中,減少了訪問(wèn)硬盤(pán)I/O次數(shù),可以有較高的運(yùn)算速度。因此本文著重研究基于ALS的協(xié)同過(guò)濾算法在SPark上的實(shí)現(xiàn)問(wèn)題。
2.1Spark平臺(tái)部署
2.1.1環(huán)境說(shuō)明
本文搭建的SPark集群采用的是實(shí)驗(yàn)室的三臺(tái)普通PC,包括1個(gè)Master節(jié)點(diǎn)和2個(gè)Slave節(jié)點(diǎn),三個(gè)節(jié)點(diǎn)均為Ubuntu14.10系統(tǒng),節(jié)點(diǎn)之間局域網(wǎng)連接。具體情況如表1所示。
表1 節(jié)點(diǎn)具體說(shuō)明Tab.1 The details of th ree nodes
2.1.2軟件安裝
JavaJDK用的是jdk -7u75 -linux-i586.gz,hadooP版本為hadooP -2.6.0.tar.gz,安裝過(guò)程中最重要的一點(diǎn)就是配置SSH實(shí)現(xiàn)無(wú)密碼遠(yuǎn)程登陸與管理。搭建好HadooP集群之后,在此基礎(chǔ)上進(jìn)行SPark的安裝,其版本為SPark1.2.0,開(kāi)發(fā)環(huán)境IntelliJIDEA 14.0.3,對(duì)應(yīng)的Scala為scala-sdk -2.10.4。所有軟件在三臺(tái)機(jī)器上安裝并配置好后即可啟動(dòng)SPark分布式集群。
2.2Spark集群的特點(diǎn)
APache SPark官方的定義是[7]:SPark是一個(gè)通用的大規(guī)模數(shù)據(jù)快速處理引擎??梢院?jiǎn)單地理解為SPark就是一個(gè)大數(shù)據(jù)分布式處理框架。SPark具有以下優(yōu)勢(shì):快速性,SPark基于內(nèi)存的計(jì)算速度比HadooP MaP Reduce快很多。易用性,提供多語(yǔ)言編程,簡(jiǎn)潔的函數(shù)式編程語(yǔ)言Scala能快速實(shí)現(xiàn)應(yīng)用。通用性,提供了一個(gè)強(qiáng)大的技術(shù)堆棧,如機(jī)器學(xué)習(xí)工具M(jìn)Llib,圖計(jì)算工具GraPhX,實(shí)時(shí)流處理工具SPark Streaming等,尤其是MLlib使得原本復(fù)雜的機(jī)器學(xué)習(xí)在理解和使用上變的靈活而簡(jiǎn)易。本文的協(xié)同過(guò)濾算法即是基于MLlib實(shí)現(xiàn)的。
RDD(Resilient Distributed Datasets)是SPark的核心,是分布于各個(gè)計(jì)算節(jié)點(diǎn)存儲(chǔ)于內(nèi)存中的數(shù)據(jù)對(duì)象集合,可以讓用戶在執(zhí)行多個(gè)查詢時(shí)顯式地將數(shù)據(jù)緩存在內(nèi)存中,在后續(xù)的查詢過(guò)程中能夠重用這些數(shù)據(jù)集,從而提供了低延遲性。RDD具有很好的容錯(cuò)機(jī)制,它能記住構(gòu)建它的操作圖,記錄如何從其他RDD轉(zhuǎn)換而來(lái)(即Lineage),當(dāng)執(zhí)行任務(wù)的數(shù)據(jù)節(jié)點(diǎn)出現(xiàn)故障,可以通過(guò)操作圖獲得之前執(zhí)行的操作而恢復(fù)丟失的分區(qū)即重建丟失的數(shù)據(jù)。RDD只能通過(guò)在其他RDD執(zhí)行確定的轉(zhuǎn)換操作而創(chuàng)建,與大多數(shù)的分布式數(shù)據(jù)集采用的需付出高昂成本代價(jià)的數(shù)據(jù)檢查點(diǎn)的容錯(cuò)性實(shí)現(xiàn)方式不同,RDD只包含如何從其他RDD衍生所必需的信息,不需要檢查點(diǎn)操作就可以重構(gòu)丟失的數(shù)據(jù)分區(qū)。
2.3Spark的工作流程
在SPark中,數(shù)據(jù)集的劃分和任務(wù)調(diào)度都是系統(tǒng)自動(dòng)完成的,其工作流程如圖1所示。
SPark程序在運(yùn)行時(shí),首先會(huì)創(chuàng)建SParkContext來(lái)作為任務(wù)調(diào)度的總?cè)肟?,在其初始化工作環(huán)境過(guò)程中會(huì)創(chuàng)建DAGScheduler(進(jìn)行Stage調(diào)度)和Task Scheduler(進(jìn)行Task調(diào)度)兩個(gè)模塊。DAGScheduler模塊負(fù)責(zé)為每個(gè)SParkJob計(jì)算具有依賴關(guān)系的多個(gè)Stage任務(wù)階段,然后將每個(gè)Stage劃分為具體的一組任務(wù)(可以在worker節(jié)點(diǎn)上并行執(zhí)行的tasks),并以TaskSet的形式提交給TaskScheduler模塊來(lái)執(zhí)行。
圖1 Spark工作流程Fig.1 W ork ing Process of Spark
基于矩陣分解模型的協(xié)同過(guò)濾推薦算法主要有:SVD(奇異值分解)和ALS。實(shí)際上,矩陣分解模型與前面提到的隱語(yǔ)義模型是一個(gè)意思,即通過(guò)降維的方式將評(píng)分矩陣補(bǔ)全。早期的SVD首先通過(guò)加權(quán)平均值等方法對(duì)用戶評(píng)分矩陣R中的空缺元素補(bǔ)全得到矩陣R?,然后利用數(shù)學(xué)中的SVD對(duì)R?進(jìn)行分解。Simon、Korean[8]等人也提出新的SVD++模型,然而這種方法的計(jì)算復(fù)雜度非常高,很難在實(shí)際的推薦系統(tǒng)中應(yīng)用[9]。隨著Netflix Prize比賽的進(jìn)行,先后出現(xiàn)了一些高效的矩陣分解算法,其中Zhou等[10]人提出的基于交替最小二乘法(ALS)的協(xié)同過(guò)濾算法是一個(gè)強(qiáng)大的矩陣分解算法,能很好的擴(kuò)展到分布式計(jì)算以及解決數(shù)據(jù)稀疏問(wèn)題。下面以用戶與電影評(píng)分矩陣為例來(lái)講述基于ALS協(xié)同過(guò)濾算法的原理[11]。
為了防止過(guò)擬合,給上式添加二階正則化項(xiàng),即為:
如果已知V,可以使用嶺回歸(Ridge Regression)預(yù)測(cè)U的每一行,反之亦可。因此,固定V矩陣,對(duì)Ui求導(dǎo),得到下面求解Ui.的公式
在上式中,Ri.表示用戶i對(duì)電影的評(píng)分向量,Vui表示由用戶i評(píng)價(jià)過(guò)的電影的特征向量組成的特征矩陣。nui表示用戶i評(píng)價(jià)過(guò)的電影數(shù)量。同理,固定U矩陣,得到下面求解Vj.的公式
在上式中,R.j表示給電影j評(píng)過(guò)分的用戶的評(píng)分向量,Umj表示由為電影j評(píng)過(guò)分的用戶的特征向量組成的特征矩陣。nmj表示為電影j評(píng)過(guò)分的用戶數(shù)量。I為一個(gè)d×d的單位矩陣。
基于交替最小二乘法(ALS)的協(xié)同過(guò)濾算法,即是交替調(diào)用公式(4)、(5)更新計(jì)算U,V。直到計(jì)算出的結(jié)果收斂或者迭代的次數(shù)達(dá)到最大值,然后結(jié)束計(jì)算。最終求出逼近矩陣X,使用X進(jìn)行電影的推薦。
在SPark上實(shí)現(xiàn)算法時(shí),首先將原始的數(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.1實(shí)驗(yàn)數(shù)據(jù)集
由于搜集滿足條件的數(shù)據(jù)集不是很方便,所以本文采用了網(wǎng)上公開(kāi)的MovieLens的數(shù)據(jù)集[13],在這里選用的是100K(10萬(wàn)條),1M(約100萬(wàn)條)和從100K中隨機(jī)抽取的1萬(wàn)條這三組的數(shù)據(jù)進(jìn)行實(shí)驗(yàn),分別隨機(jī)取數(shù)據(jù)集中的80%作為訓(xùn)練集,20%作為測(cè)試集。
4.2結(jié)果分析
4.2.1準(zhǔn)確度
該算法是一個(gè)典型的基于評(píng)分的用戶-商品推薦算法,推薦結(jié)果的準(zhǔn)確度必是推薦中的核心問(wèn)題,我們一般采用均方根誤差(RMSE)來(lái)評(píng)價(jià)評(píng)分預(yù)測(cè)的準(zhǔn)確度。誤差越小,意味著準(zhǔn)確度越高。其公式為:
在式(6)中,rui表示用戶u對(duì)電影i的實(shí)際評(píng)分,是通過(guò)推薦算法預(yù)測(cè)的評(píng)分。該部分選用的是100K數(shù)據(jù)集。
在上述ALS算法中,我們知道需要設(shè)置一些訓(xùn)練參數(shù),參數(shù)選擇的好壞直接決定了模型的好壞。ALS訓(xùn)練算法中最重要的參數(shù)是正則化常數(shù)λ和迭代次數(shù)。當(dāng)兩個(gè)參數(shù)取值不同時(shí),實(shí)驗(yàn)結(jié)果如表2所示。由圖可以看出,正則化常數(shù)對(duì)結(jié)果影響非常大,迭代次數(shù)影響稍小。通過(guò)不斷地嘗試,找到最佳模型參數(shù)取值。當(dāng)然,其他的模型參數(shù)如矩陣因子排名,特征值個(gè)數(shù)對(duì)結(jié)果也有影響,還有待研究。
4.2.2快速性
快速性是推薦系統(tǒng)中至關(guān)重要的問(wèn)題,它決定了一個(gè)算法能否根據(jù)用戶興趣和喜好的變化實(shí)時(shí)的推薦相關(guān)物品,我們分別采用1W、10W和100W條數(shù)據(jù)對(duì)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ù)量很小時(shí),HadooP 與SPark的運(yùn)行時(shí)間差別不大,當(dāng)數(shù)據(jù)量越大,SPark的基于內(nèi)存計(jì)算的優(yōu)勢(shì)越能夠體現(xiàn)出來(lái),而且當(dāng)數(shù)據(jù)量增大時(shí),SPark的運(yùn)行時(shí)間增加得比較緩慢,HadooP增加得比較快速,可以想象,當(dāng)數(shù)據(jù)量非常大時(shí),HadooP運(yùn)行將會(huì)非常慢,從而不能夠及時(shí)地向用戶推薦當(dāng)下喜歡的物品。
本文主要是研究了基于ALS的協(xié)同過(guò)濾推薦算法在SPark平臺(tái)上的實(shí)現(xiàn),通過(guò)實(shí)驗(yàn)表明,SPark作為新一代數(shù)據(jù)并行處理平臺(tái),在運(yùn)行時(shí)間和運(yùn)行準(zhǔn)確度上都有良好的表現(xiàn),能夠有效地處理大數(shù)據(jù)的運(yùn)算問(wèn)題,而且數(shù)據(jù)量越大,這種優(yōu)勢(shì)越明顯。但SPark作為新出現(xiàn)的并行數(shù)據(jù)處理平臺(tái),后續(xù)還有很多工作要做,如(1)對(duì)SPark平臺(tái)工作原理深入研究,在任務(wù)調(diào)度方面進(jìn)行優(yōu)化,達(dá)到負(fù)載均衡,提高運(yùn)算速度。(2)ALS模型訓(xùn)練參數(shù)的選擇,尋求一種智能算法,能幫我們自動(dòng)的選擇最優(yōu)的參數(shù),而不是手工嘗試。(3)增加SPark集群節(jié)點(diǎn)數(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é)同過(guò)濾算法[J].計(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é)同過(guò)濾的推薦算法研究[D].中國(guó)科學(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è)級(jí)實(shí)戰(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é)同過(guò)濾算法的并行化研究[J].計(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é)同過(guò)濾的大數(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é)同過(guò)濾推薦系統(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].廈門(mén)大學(xué),2014.
SUN Yuanshuai.Recommendation A lgorithms in the big data Era[D].Xiamen University,2014.
于娜娜 女(1990 -),山東曲阜人,碩士生,主要研究方向?yàn)榭刂评碚撆c控制工程,分布式計(jì)算等。
王中杰 女(1971 -),遼寧葫蘆島人、博士、教授,主要研究方向?yàn)橹悄芟到y(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
中圖分類號(hào):391
文獻(xiàn)標(biāo)識(shí)碼:A