基于Spark平臺(tái)ALS模型推薦算法的研究

吳青洋 程旭 鄧程鵬 丁浩軒 張宏 鄭志偉

摘要：針對(duì)推薦系統(tǒng)的可擴(kuò)性問題，該文比較了基于Hadoop實(shí)現(xiàn)ALS模型推薦算法與基于Spark平臺(tái)實(shí)現(xiàn)ALS模型推薦算法的性能，通過在GroupLens網(wǎng)站提供的MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，Spark平臺(tái)的計(jì)算性能更強(qiáng)。針對(duì)推薦系統(tǒng)的數(shù)據(jù)稀疏性問題，該文采用了ALS模型推薦算法。最后在Spark平臺(tái)上使用Scala編程語言，對(duì)不同參數(shù)下的ALS模型進(jìn)行訓(xùn)練，并在校驗(yàn)集中驗(yàn)證，獲取了最佳參數(shù)下的模型。

關(guān)鍵詞：MapReduce；Spark：ALS模型推薦算法：矩陣分解：迭代最小二乘法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）23-0033-04

1 概述

推薦系統(tǒng)是目前使用最廣泛的機(jī)器學(xué)習(xí)技術(shù)[1]之一。由于它在個(gè)性化推薦方面效果顯著，因此引起了越來越多學(xué)者的關(guān)注。隨著互聯(lián)網(wǎng)的快速發(fā)展，推薦系統(tǒng)正面臨處理海量數(shù)據(jù)的問題。

推薦系統(tǒng)旨在給用戶推薦他們可能感興趣的物品。它主要通過分析用戶的行為信息數(shù)據(jù)來預(yù)測(cè)用戶對(duì)某些物品的喜好。個(gè)性化推薦技術(shù)主要分為三類：基于內(nèi)容的推薦，基于協(xié)同過濾的推薦，基于混合的推薦[2]。

該文使用推薦效果較好的協(xié)同過濾算法。協(xié)同過濾算法的關(guān)鍵是計(jì)算用戶的相似度（或物品的相似度）。隨著用戶和物品數(shù)量的線性增長，推薦系統(tǒng)的計(jì)算量增大，性能降低。此時(shí)需要額外的計(jì)算能力，即推薦系統(tǒng)的可擴(kuò)展性問題，也是協(xié)同過濾算法面臨的難題之一[3]。

文獻(xiàn)[4-5]使用Hadoop并行化協(xié)同過濾算法致力于解決計(jì)算復(fù)雜度和可擴(kuò)展性問題。然而，如果數(shù)據(jù)量劇增的時(shí)候，這種基于MapReduce方式缺乏良好的可擴(kuò)展性和計(jì)算效率。

該文提出了基于Spark平臺(tái)的解決方案。我們使用兩個(gè)集群計(jì)算框架比較基于ALS模型推薦算法：基于Hadoop的MapReduce和基于Spark的內(nèi)存計(jì)算RDD?；贖adoop平臺(tái)使用Mahout實(shí)現(xiàn)ALS模型推薦算法[6-7]?；赟park平臺(tái)使用Scala編程語言實(shí)現(xiàn)ALS模型推薦算法。

由于用戶和項(xiàng)目數(shù)量不斷增加，用戶項(xiàng)目評(píng)分矩陣往往十分龐大，此外評(píng)分矩陣通常是稀疏的，因此可以考慮采用低維度矩陣擬合評(píng)分矩陣。矩陣分解法是利用兩個(gè)低維度的矩陣來描述評(píng)分矩陣，從而達(dá)到降維的目的[8]。該文采用的是容易并行化的最小二乘法ALS（Alternating-Least-Squares）[9]。

2 MapReduce

MapReduce是分布式編程的一種模式，用于處理集群中的海量數(shù)據(jù)，其中的每臺(tái)計(jì)算機(jī)被稱為一個(gè)節(jié)點(diǎn)，該模式是由谷歌公司在2004年提出的[10]，其主要特點(diǎn)是通過并行編程解決處理海量數(shù)據(jù)的問題。MapReduce主要思想是”Map（映射）"和"Reduce（歸約）”，它們都是來自函數(shù)式編程語言和矢量編程語言。它極大地方便了編程人員在不會(huì)分布式并行編程的情況下，將自己的程序運(yùn)行在分布式系統(tǒng)上。

開發(fā)人員的任務(wù)是實(shí)現(xiàn)以下兩個(gè)步驟（見圖1 MapReduce的工作流程）：

1）map函數(shù)將輸入數(shù)據(jù)切分為（鍵，值）對(duì)組表示的片段，根據(jù)特定的記錄，產(chǎn)生零個(gè)或多個(gè)中間對(duì)。MapReduce組織相關(guān)的所有中間值相同的中間鍵k。接下來，值轉(zhuǎn)移到reduce（）函數(shù)。

2）reduce函數(shù)處理中間鍵K和與K對(duì)應(yīng)的一組值，然后將這組值進(jìn)行合并。每次調(diào)用Reduce函數(shù)通常返回一個(gè)值，但它也可以返回零個(gè)或多個(gè)值。

MapReduce能夠有效地分配集群的資源來執(zhí)行任務(wù)，解決了并行化編程的復(fù)雜性問題，但它缺少編程的靈活性：一個(gè)程序只能由map的和reduce函數(shù)組成，計(jì)算的每個(gè)階段僅當(dāng)其前一功能的各實(shí)例的結(jié)束后才能開始。執(zhí)行復(fù)雜的操作，唯一的辦法就是執(zhí)行若干個(gè)MapReduce，輸出數(shù)據(jù)的記錄在磁盤上，然后再傳給下一個(gè)任務(wù)。

在已經(jīng)實(shí)現(xiàn)MapReduce的若干個(gè)實(shí)施方案中，Apache Hadoop的技術(shù)是最成功的，尤其在商業(yè)用途方面[11-12]。

3 協(xié)同過濾

協(xié)同過濾算法在推薦系統(tǒng)中廣泛使用[13-15]。協(xié)同過濾算法分為基于鄰域的推薦算法和基于模型的推薦算法。該文采用的是基于ALS模型推薦算法，算法原理如下：假設(shè)用戶-物品評(píng)分矩陣為R，由矩陣奇異值分解原理可知，矩陣R可以分解為幾個(gè)矩陣相乘的形式，如公式（1）：

4.1 Hadoop解決方案

基于Hadoop平臺(tái)的Mahout[6]在機(jī)器學(xué)習(xí)領(lǐng)域?qū)崿F(xiàn)了算法的并行化，Mahout包含聚類、分類、推薦過濾、頻繁子項(xiàng)挖掘等算法的實(shí)現(xiàn)。

ALS模型推薦算法的并行化是通過執(zhí)行連續(xù)的MapReduce任務(wù)來實(shí)現(xiàn)的，在程序的實(shí)現(xiàn)過程中，中間數(shù)據(jù)被不斷地寫入磁盤，然后再從磁盤讀取相關(guān)數(shù)據(jù)，這種方式對(duì)系統(tǒng)的開銷很大。

4.2 Apache Spark

2012年4月加州大學(xué)伯克利分校的AMPLab 發(fā)表的文章中提出了彈性分布式數(shù)據(jù)集（簡稱RDD）的概念，Spark就是基于RDD實(shí)現(xiàn)的，Spark平臺(tái)開發(fā)者的目的是消除MapReduce范式的局限性。Spark類似Hadoop的MapReduce范式，也是一個(gè)開源的分布式計(jì)算平臺(tái)[11]，而且Spark與HDFS是完全兼容的[16]。

RDD本質(zhì)上是一個(gè)只讀的分區(qū)記錄集合，這意味著一個(gè)特定元素集合可以在集群節(jié)點(diǎn)間被共享。此外，RDD還具有以下特征：

1）只能由操作其RDD集或從文件系統(tǒng)讀取數(shù)據(jù)時(shí)被創(chuàng)建；

2）為了有效地實(shí)現(xiàn)容錯(cuò)，RDD提供了一種高度受限的共享內(nèi)存，即RDD是只讀的；

3）中間結(jié)果的操作可以存儲(chǔ)在內(nèi)存中，計(jì)算迭代算法更快。

5 實(shí)驗(yàn)研究

1）對(duì)比spark與MapReduce 計(jì)算平臺(tái)性能的差異

為了比較Spark與Hadoop MapReduce性能上差異，該文統(tǒng)計(jì)在MovieLens數(shù)據(jù)集為100萬條記錄數(shù)上，二者實(shí)現(xiàn)ALS模型推薦算法所消耗時(shí)間。為了減小實(shí)驗(yàn)誤差，所有實(shí)驗(yàn)均進(jìn)行三次，取三次結(jié)果的平均值作為最終結(jié)果。

2）基于Spark平臺(tái)ALS模型推薦算法并行化實(shí)現(xiàn)指標(biāo)統(tǒng)計(jì)

該文基于Spark平臺(tái)ALS模型推薦算法并行化實(shí)現(xiàn)中，對(duì)推薦系統(tǒng)相關(guān)評(píng)測(cè)指標(biāo)進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)基于ALS推薦算法在不同的屬性個(gè)數(shù)、正則化參數(shù)、迭代次數(shù)下RMSE的大小。實(shí)驗(yàn)中訓(xùn)練集占數(shù)據(jù)量60%，校驗(yàn)集占數(shù)量20%，評(píng)測(cè)集占數(shù)據(jù)20%。所有實(shí)驗(yàn)均進(jìn)行三次，取三次結(jié)果的平均值作為最終結(jié)果。

5.1 實(shí)驗(yàn)數(shù)據(jù)

該實(shí)驗(yàn)數(shù)據(jù)集是由GroupLe小組提供的MovieLens數(shù)據(jù)集，其主要包括3個(gè)種類的數(shù)據(jù)集，大小分別為100k， 1M， 10M，分別記錄了10萬條、100萬條、1000萬條用戶評(píng)分記錄。100萬條記錄里面主要有四個(gè)文件：movies.dat， ratings.dat， users.dat， README，其中users.dat記錄所有用戶相關(guān)信息；ratings.dat記錄用戶一電影的評(píng)分信息及時(shí)間戳；movies.dat記錄電影相關(guān)信息，包括電影名、類型、年份等。該文主要采用100萬條記錄作為實(shí)驗(yàn)數(shù)據(jù)集，它包括了6060多名用戶對(duì)4000多部電影評(píng)分的記錄。

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

所有實(shí)驗(yàn)在包括一個(gè)MasterNode主節(jié)點(diǎn)和兩個(gè)DataNodes（從節(jié)點(diǎn)）的集群上運(yùn)行，每個(gè)節(jié)點(diǎn)都配備了Intel（R）Core（TM） i5-4590處理器（3.30 Ghz）和8GB的RAM。實(shí)驗(yàn)運(yùn)行在版本為2.20的Hadoop（Mahout的版本為0.9），版本為2.10.04的Scala和版本為1.0的Spark。

5.3 實(shí)驗(yàn)結(jié)果

圖2顯示了通過基于Hadoop的Mahout中ParallelALSFactorizationJob類（并行化ALS）和基于Spark平臺(tái)通過Scala語言編寫的程序來計(jì)算ALS模型訓(xùn)練所消耗時(shí)間的研究結(jié)果。實(shí)驗(yàn)處理的數(shù)據(jù)集由MovieLens100萬的記錄組成，ParallelALSFactorizationJob執(zhí)行計(jì)算的平均時(shí)間為1221.89秒，基于Spark平臺(tái)實(shí)現(xiàn)的平均時(shí)間為73.72秒，由結(jié)果可知Spark性能提升非常明顯，而且迭代次數(shù)越多兩者之間的區(qū)別越明顯。

從表1可以看出不同參數(shù)下的RMSE值，其中ranks表示屬性個(gè)數(shù)，lambda表示正則化參數(shù)，表1的數(shù)據(jù)可以轉(zhuǎn)化為圖3中直方圖形式。從圖3中我們可以看出，不同的參數(shù)值對(duì)于最終訓(xùn)練出的模型影響非常大，一般來說，在同一屬性個(gè)數(shù)及正則化參數(shù)下，迭代次數(shù)越多，RMSE值越小，正則化參數(shù)對(duì)于RMSE的值影響更大，當(dāng)正則化參數(shù)為10，迭代次數(shù)為35，屬性個(gè)數(shù)為10時(shí)，RMSE達(dá)到最小值0.880424。

5.4 實(shí)驗(yàn)總結(jié)

在進(jìn)行需要多次迭代的機(jī)器學(xué)習(xí)算法計(jì)算中，Spark比Hadoop Mapreduce 優(yōu)勢(shì)非常明顯。這主要是因?yàn)镾park是基于內(nèi)存運(yùn)算的，在計(jì)算過程中，中間結(jié)果不落地，直接放在內(nèi)存中，大大提升了系統(tǒng)性能，減少了任務(wù)完成時(shí)間。基于Spark平臺(tái)的ALS模型推薦算法性能相比Hadoop提升了15倍左右，尤其是當(dāng)?shù)螖?shù)為25，性能提升約有20倍，并沒有官網(wǎng)中所說的，性能提升兩個(gè)數(shù)量級(jí)以上，分析原因主要是由于數(shù)據(jù)量比較小。此外，不同的參數(shù)值對(duì)于最終訓(xùn)練出的模型影響非常大，正則化參數(shù)對(duì)于RMSE的值影響更大。

6 結(jié)束語

通過實(shí)驗(yàn)結(jié)果分析可知，基于Spark平臺(tái)的計(jì)算性能突出，很好地解決了推薦系統(tǒng)的可擴(kuò)性問題，使用基于ALS模型推薦算法，很好地解決了推薦系統(tǒng)的數(shù)據(jù)稀疏性問題。Spark平臺(tái)的特點(diǎn)，在大數(shù)據(jù)的世界引起了人們的廣泛關(guān)注，基于RDD的內(nèi)存運(yùn)算，通過將磁盤上費(fèi)時(shí)的讀/寫中間結(jié)果的操作，轉(zhuǎn)化為相關(guān)的RDD操作，使節(jié)點(diǎn)之間工作效率更高。該文的進(jìn)一步工作應(yīng)包括：使用更大的數(shù)據(jù)集進(jìn)行反復(fù)實(shí)驗(yàn)和研究其他類型的數(shù)據(jù)。

參考文獻(xiàn)：

[1] Sammut C， Webb G I. Encyclopedia of Machine Learning[J]. Springer， 2011.

[2] IBM what is big data？ Bringing big data to the enterprise[EB/OL]. http：//www.ibm.com/big-data/us/en/.

[3] Sarwar B，Karypis G， Konstan J， et al. Item-based collabo-rative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM， 2001： 285-295.

[4] Zhao Z D， Shang M S. User-based collaborative-filtering recom-mendation algorithms on Hadoop[C]//Knowledge Discovery and Data Mining， 2010. WKDD10. Third International Conference on. IEEE， 2010： 478-481.

[5] Jiang J， Lu J， Zhang G， et al. Scaling-up item-based collaborative filtering recommendation algorithm based on Hadoop[C]// Services （SERVICES）， 2011. IEEE World Congress on. IEEE， 2011： 490-497.

[6] Owen S， Anil R， Dunning T， et al. Mahout in action[M]. Manning Publications Co， Greenwich， CT， USA， 2011.

[7] Apache mahout documentation[EB/OL]. http：//mahout.apache.org/.

[8] 樊哲. Mahout算法解析與案例實(shí)戰(zhàn)[M]. 北京： 機(jī)械工業(yè)出版社， 2014（6）.

[9] Zhou Y， Wilkinson D， Schreiber R. Large-scale parallel collaborative filtering for the netflix prize[M]// Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg， 2008： 337-348.

[10] Dean J， Ghemawat S. Mapreduce： simplified data processing on large clusters[J]. Communications of the ACM， 2008， 51（1）： 107-113.

[11] Hadoop 1.1.2 documentation[EB/OL].http：//hadoop.apache.org/docs/stable/.

[12] White T. Hadoop： The definitive guide[M]. OReilly Media， Inc， 2012.

[13] Resnick P， Varian H R. Recommender systems[J]. Communications of the ACM， 1997， 40（3）： 56-58.

[14] Tan H， Ye H. A collaborative filtering recommendation algorithm based on item classification[C]//Circuits， Communications and Systems， 2009. PACCS09. Pacific-Asia Conference on. IEEE， 2009： 694-697.

[15] Gong S， Ye H， Tan H. Combining memory-based and model-based collaborative filtering in recommender system[C]//Circuits， Com-munications and Systems， 2009. PACCS09. Pacific-Asia Conference on. IEEE， 2009： 690-693.

[16] Spark documentation[EB/OL]. http：//spark.apache.org/documentation.html.

【通聯(lián)編輯：謝媛媛】