基于Spark的ItemBased推薦算法性能優化

廖 彬，張 陶，國冰磊，于 炯，張旭光，劉 炎

(1.新疆財經大學 統計與信息學院，烏魯木齊 830012； 2.新疆醫科大學 醫學工程技術學院，烏魯木齊 830011；3.新疆大學 信息科學與工程學院，烏魯木齊 830008； 4.清華大學 軟件學院，北京 100084) (*通信作者電子郵箱liaobin665@163.com)

基于Spark的ItemBased推薦算法性能優化

廖 彬1*，張 陶2,3，國冰磊3，于 炯3，張旭光1，劉 炎4

(1.新疆財經大學 統計與信息學院，烏魯木齊 830012； 2.新疆醫科大學 醫學工程技術學院，烏魯木齊 830011；3.新疆大學 信息科學與工程學院，烏魯木齊 830008； 4.清華大學 軟件學院，北京 100084) (*通信作者電子郵箱liaobin665@163.com)

MapReduce計算場景下，復雜的大數據挖掘類算法通常需要多個MapReduce作業協作完成，但多個作業之間嚴重的冗余磁盤讀寫及重復的資源申請操作，使得算法的性能嚴重降低。為提高ItemBased推薦算法的計算效率，首先對MapReduce平臺下ItemBased協同過濾算法存在的性能問題進行了分析；在此基礎上利用Spark迭代計算及內存計算上的優勢提高算法的執行效率，并實現了基于Spark平臺的ItemBased推薦算法。實驗結果表明：當集群節點規模分別為10與20時，算法在Spark中的運行時間分別只有MapReduce中的25.6%及30.8%，Spark平臺下的算法相比MapReduce平臺，執行效率整體提高3倍以上。

協同過濾；MapReduce；Spark算法；性能優化；有向非循環圖

0 引言

據互聯網數據中心(Internet Data Center)發布的報告顯示，2015年全球產生的數據量達到近10 ZB，而2020年全球產生的數據量將達到40 ZB[1]。數據的產生過程在經歷被動和主動兩種產生過程后，發展到了自動產生階段，標志著大數據時代的來臨。數據從簡單的處理對象開始轉變為一種基礎性資源，如何更好地管理和利用大數據已經成為普遍關注的話題，大數據的規模效應給數據存儲、管理以及數據分析帶來了極大的挑戰[2]，進而高效率低成本的大數據處理技術成為學術界及工業界的研究熱點。推薦算法作為大數據挖掘類算法中最常見的一種，由于可以快速地在海量信息中篩選并過濾出用戶可能最感興趣的內容，在幫助用戶獲取有效信息的同時實現信息提供商與用戶之間的雙贏，得到了快速的發展，而協同過濾推薦(Collaborative Filtering Recommendation)是其中最經典的推薦算法。

自2003年Google發表論文公開分布式存儲系統GFS(Google File System)[3]及分布式數據處理模型MapReduce[4-5]以來，由于MapReduce具有可擴展性(Scalable)、低成本(Economical)、高效性(Efficient)及可靠性(Reliable)等優點[6]，使其成為諸多大數據計算系統(如：Hadoop、Spark、Pig、Hive、Hbase和Dryad等)最通用的并行計算框架(MapReduce生態系統如圖1[7]所示)。MapReduce與以往的并行計算模式相比，最大的區別是它“移動計算”而非“移動數據”的理念，即將任務調度到離數據最近的節點，因為這樣可以最小化大數據作業計算過程中數據的網絡傳輸量，而這正是MapReduce發展如此壯大的根本原因。

圖1 MapReduce生態系統[7]

在此背景下，隨著MapReduce計算框架的不斷發展壯大，已有的推薦算法大多基于MapReduce框架實現，但MapReduce計算場景下，復雜的大數據挖掘類算法通常需要多個MapReduce作業協作完成，但多個作業之間嚴重的冗余磁盤讀寫及重復的資源申請操作，使得算法的計算及能耗等效率嚴重降低[8-10]。而協同過濾推薦算法則屬于典型的大數據挖掘類算法，所以本文以基于物品(ItemBased)的協同過濾算法為例，研究提高算法性能的優化方法。本文作了如下幾個方面的工作：首先，對基于MapReduce的ItemBased協同過濾算法實現及性能缺陷進行了分析；其次，在性能缺陷分析的基礎上，提出基于Spark平臺重寫算法，進而提高ItemBased推薦算法的性能；最后，通過實驗驗證了算法優化效果的有效性。

1 相關研究

由于應用領域及場景的不同，最常見的協同過濾算法[11]有基于用戶、物品及混合協同過濾3種，除此之外還有基于內容的協同過濾[12-13]、基于規則的協同過濾[14-15]、基于人口統計信息的協同過濾[16-17]、基于網絡結構的協同過濾[18-19]及混合過濾[20]等。已有的推薦算法研究工作主要目的都是以提高算法在特定應用領域的推薦質量為首要目標，主要評價指標有準確率(Precision)、召回率(Recall)、F值(F-Measure)、E值(E-Measure)、平均正確率(Average Precision)等。很少工作關注到算法的計算效率、算法執行環境等方面，但在算法處理數據量的爆炸式增長及分布式計算模型MapReduce逐漸普及的背景下，推薦算法從單機模型逐漸向MapReduce發展，并且算法的執行效率也逐漸受到學術界及工業界的重視。

文獻[21-22]將基于用戶(User-Based)的協同過濾算法移植到Hadoop平臺，以提高算法并行計算的能力，并通過修改作業map及reduce子任務的數量，達到提高MapReduce模型下算法計算效率的目的。Schelter等[23]面對用戶數據量快速增長的問題，開發了基于MapReduce的近鄰(Similarity-based neighborhood)協同過濾算法，并通過7億Yahoo音樂數據的實驗證明了算法在效率上的提升。文獻[24]將MinHash聚類、概率潛在語義索引(Probabilistic Latent Semantic Indexing, PLSI)及Covisitation計數技術引入到Google news的協同過濾算法中，有效地提高了算法的性能。文獻[25]開發并實現了MapReduce平臺下基于物品(ItemBased)協同過濾算法，將算法的計算步驟切分為Map及Reduce子任務，并通過數據本地化策略最小化通信成本，大大提高了Hadoop中算法的執行效率。但是，不管是UserBased還是ItemBased協同過濾算法，MapReduce環境下的計算任務都需要多個作業協作完成，作業之間難免存在冗余的I/O及資源重復申請操作，算法效率上還存在著較大的優化空間。所以，本文與以往工作不同的是：在分析基于MapReduce的ItemBase協同過濾算法性能缺陷的基礎上，利用Spark在迭代計算和內存計算上的優勢，提高算法的執行效率。

2 基于MapReduce的ItemBased推薦算法分析

選擇ItemBased的協同過濾算法為研究對象主要原因是：為了讓相似度矩陣計算規模最小化，ItemBased算法更加適用于用戶數據量比物品數據量大的場景，而UserBased則適用于用戶數比物品數小的場景。除此之外，相對于其他協同過濾算法，item與item之間的相似度比較穩定，適合離線計算，能夠實現定期更新的功能，這使得ItemBased協同過濾算法的應用場景相比其他推薦算法更為廣泛。

ItemBased算法假設能夠引起用戶興趣的item必定與其評分高的item相似。算法首先計算用戶對物品的喜好程度，然后根據用戶的喜好計算item之間的相似度，最后找出與每個item最相似的前N個item。其中，相似性計算包含3個步驟:1)統計每個item的好評用戶數;2)item好評鍵值對統計，即統計任意兩個有關聯item的相同好評用戶數;3)item相似性計算(可采用Jaccard系數作為計算兩個item的相似性方法)，即計算任意兩個有關聯item的相似度。而找出最相似的前N個item步驟中，首先需要對item相似性歸一化，再進行相似性評分整合，最后得出每個item相似性最高的前N個item。MapReduce的ItemBased推薦算法，其最經典的實現代碼是Mahout中的RecommenderJob類，其源碼在org.apache.mahout.cf.taste.hadoop.item包下，其主要參數及意義如表1所示。

表1 ItemBased推薦算法主要參數

通過對ItemBased推薦算法在Hadoop中的運行過程監控及日志分析，發現執行一次算法總共包含12個MapReduce作業，根據不同MapReduce作業的功能，可分解為如下10個計算步驟，每個MapReduce作業所對應的計算步驟及功能如表2。

表2 算法MapReduce作業分解及其功能

即使將MapReduce Job1(MR Job1)、MapReduce Job11等這樣的非核心的計算步驟去掉，最精簡的ItemBased推薦算法也至少需要7個MapReduce作業才能完成計算。如圖2所示為精簡后的MapReduce作業與HDFS(Hadoop Distributed File System)文件系統的調用關系。

根據MapReduce計算模型的原理，每個MapReduce作業會被切分為多個map及reduce任務。其中map任務執行過程中需要將數據從HDFS中讀取進來，當map任務計算完畢后，通過Shuffle與Sort操作將〈key,value〉鍵值對發送給對應的reduce任務，reduce階段以〈key,Iterator〈value〉〉作為數據輸入，計算完畢后將處理結果寫入到HDFS中。由于MapReduce作業之間相互獨立，即每個MapReduce作業都要進行輸入數據的讀取及將計算結果寫入HDFS的操作。由于ItemBased推薦算法總共包含12個MapReduce作業，意味著算法執行過程中需要進行總共24次的HDFS讀取及寫入操作。這些重復的數據讀寫操作耗費集群資源的同時，嚴重降低了算法的執行的效率；并且，由于磁盤I/O資源是集群計算性能的瓶頸，高頻次的I/O資源申請及釋放容易產生資源競爭，導致map與reduce任務之間容易出現等待現象，進而不同程度上進一步降低了算法的執行效率。

通過以上分析發現MapReduce環境下的ItemBased算法性能優化并不能單從優化算法本身入手，MapReduce作業之間的獨立性所帶來的重復I/O操作是導致算法的計算效率低下的根本原因。

圖2 MapReduce作業與HDFS的調用關系

3 基于Spark的ItemBased推薦算法

第2章分析了ItemBased推薦算法在MapReduce平臺下效率低下是由于MapReduce作業之間的獨立性及資源的不合理利用造成，Spark相比MapReduce主要有以下兩方面的優勢。

1)Spark能夠將計算過程中產生的中間數據緩存到內存，與MapReduce相比，迭代計算效率更高。這是由于Spark的RDD(Resilient Distributed Dataset)能夠直接cache到內存中。Action或Transformation算子對RDD數據集的計算結果緩存到內存中，使得下一個算子的輸入數據直接從內存中讀取，相比MapReduce省去了大量的重復磁盤I/O操作。

2)Spark實現推薦算法業務邏輯比MapReduce更簡單靈活。這是由于MapReduce只提供map與reduce兩種基本操作，而Spark則提供包含Transfromation及Action兩類操作集。其中，Transfromation中包含map、filter、flatMap、sample、groupByKey、reduceByKey、union、join、cogroup、mapValues、sort和partionBy等操作；Action中擁有count、collect、reduce、lookup和save等操作。除此之外，Spark能夠將這些算子之間的業務邏輯(計算流程)通過有向非循環圖(Directed Acyclic Graph, DAG)模型進行組織調度。

由于目前Spark MLlib中已有的推薦算法只有ALS(Alternating Least Squares)一種，并沒有ItemBased推薦算法。所以，本文對Spark平臺下基于Scala語言對算法進行了實現。算法核心主要包含以下3個部分。

1)數據輸入模型構建。

ItemBased推薦算法輸入數據格式為：(userID,itemID,ratingScore)意義分別為用戶ID、物品ID和評分值。構造用戶數據輸入模型核心代碼如下：

def UserData ( sc:SparkContext,input:String,split:String):(RDD[(String,String,Double)])={ val u_rdd1=sc.textFile(input,10)

val u_rdd2=u_rdd1.map(line=>{ val fileds=line.split("split") (fileds(0),fileds(1),fileds(2).toDouble) }) u_rdd2

}

2)相似度矩陣模型構建及計算。

可將相似度計算的輸入數據抽象的表示為兩個關系模式：Features(id,feature)和Relationship(id,fid)。其中Features表示每個對象(如用戶、文本、商品等)所具有的特征信息；而Relationship表示Features中的對象之間存在的關系。相似度計算的流程是：首先，通過Relationship表中的關系對(id,fid)，關聯到Features表中id及fid中所對應的feature字段的值(即〈f1,f2,…,fn〉的值)；其次，將兩組feature的值作為輸入參數，交給相似度計算函數SC(Similarity Calculation)進行計算。最后，將每次SC函數計算結果輸出到結果表中。可根據具體的應用場景不同而選擇不同的相似度計算函數，常用的相似度計算函數SC有Cosine Correlation函數、Spearman Rank Correlation函數、Pearson Correlation函數及歐氏距離相似度函數等。本文采用歐氏相似度函數，其中輸入參數u_rdd表示用戶評分表，輸出參數u_rdd9表示相似矩陣，數據格式為：(itemID1,itemID2,相似度)。其核心代碼EuclideanDistanceSimilarity如下：

def EuclideanDistanceSimilarity( u_rdd:RDD[(String,String,Double)]):(RDD[(String,String,Double)])={ val u_rdd2=u_rdd.map(f=>(f._1,(f._2,f._3))).sortByKey()

u_rdd2.cache

val u_rdd3=u_rdd2.join(u_rdd2)

val u_rdd4=u_rdd3.map(f=>((f._2._1._1,f._2._2._1), (f._2._1._2,f._2._2._2))) val u_rdd5=u_rdd4.map(f=>(f._1,(f._2._1-f._2._2)* (f._2._1-f._2._2))).reduceByKey(_+_) val u_rdd6=u_rdd4.map(f=>(f._1,1)).reduceByKey(_+_)

val u_rdd7=u_rdd5.filter(f=>f._1._1!=f._1._2)

val u_rdd8=u_rdd7.join(u_rdd6)

val u_rdd9=u_rdd8.map(f=>(f._1._1,f._1._2,f._2._2/ (1+sqrt(f._2._1)))) u_rdd9

}

3)推薦算法模型構建及業務實現。

在構建用戶輸入模型及相似度計算模型的基礎上，推薦模型根據物品相似矩陣以及用戶對物品的評分表，計算用戶的推薦列表。其中，輸入參數items_similar表示物品相似矩陣，user_perf表示用戶評分表，r_number表示推薦個數；而輸出參數rdd7表示用戶推薦列表，格式為：(userID,itemID,ratingScore)。其核心代碼Recommend如下。

def Recommend ( items_similar:RDD[(String,String,Double)],user_perf:RDD[(String,String,Double)],r_number:Int):(RDD[(String,String,Double)])={ val rdd2=items_similar.map(f=>(f._2,(f._1,f._3))). join(user_perf.map(f=>(f._2,(f._1,f._3)))) val rdd3=rdd2.map(f=>((f._2._2._1,f._2._1._1), f._2._2._2*f._2._1._2)) val rdd4=rdd3.reduceByKey((x,y)=>x+y). map(f=>(f._1._1,(f._1._2,f._2))) val rdd5=rdd4.groupByKey()

val rdd6=rdd5.map(f=>{ val i2=f._2.toBuffer val i2_2=i2.sortBy(_._2) if (i2_2.length>r_number)i2_2.remove(0,(i2_2. length-r_number))(f._1,i2_2.toIterable) })

val rdd7=rdd6.flatMap(f=>{ val id2=f._2 for (w<-id2)yield(f._1,w._1,w._2) })

rdd7

}

算法在Spark環境中的計算流程，RDD數據集之間的轉化操作及關系，請參見圖3。

4 實驗評價與比較

4.1 實驗環境配置

為了對比算法在MapReduce與Spark平臺下的執行效率，本文利用測試數據生成工具DataFactory生成測試數據8億條。將測試數據生成到數據庫表中后，將數據庫表中的測試數據導出為TXT數據后上傳到HDFS中。HDFS中數據塊的大小設置為16 MB，數據的切分及存儲情況由機架感知的數據塊存儲策略隨機確定。測試數據的格式為(userid，itemid，ratingScore)，其含義表示用戶(userid)對物品(itemid)的評分結果為ratingScore。實驗在2組不同規模集群上進行測試，第1組節點規模為10，第2組節點規模為20。實驗節點的配置參數如表3所示。

表3 總體實驗環境描述

4.2 算法執行效率對比

為了對比算法在MapReduce與Spark平臺下的執行效率，在輸入數據相同的條件下，分別將MapReduce及Spark平臺下的算法在節點為10與20的集群中運行10次，得到的實驗數據如表4所示。其中：在MapReduce 10節點的集群環境下算法運行10次的平均時間為13 226.7 s，在集群節點規模為20時平均時間縮短到7 117.4 s；Spark集群規模為10個節點時平均時間為3 380.5 s，當Spark集群規模擴大到20個節點時平均時間縮短至2 194.4 s。

從表3中數據可以看出，由于算法執行的并行性，無論是MapReduce還是Spark平臺，隨著集群規模的擴大，算法運行時間有所縮短。其中MapReduce集群規模從10節點擴充到20后，算法平均執行時間縮短了6 109.3 s，效率提升了近46.2%；而Spark集群規模的擴大，算法平均執行時間縮短了1 186.1 s，效率提升了35.1%左右。當集群規模都為10節點時，Spark整體上比MapReduce平均執行時間縮短9 846.2 s，Spark算法運行時間只有MapReduce的25.6%；而當集群規模為20時，Spark整體上比MapReduce平均執行時間縮短4 923 s，Spark算法運行時間只有MapReduce的30.8%。

4.3 算法執行效率分析

如圖3所示為算法在Spark環境中的計算流程分析，整個算法在Spark環境中運行分為8個Stage，涉及到18個RDD數據集，圖3描述了RDD數據集之間的轉化關系。將圖3的計算過程與圖2進行對比，可以看出相對于MapReduce平臺，Spark平臺下對算法的執行時間及資源利用效率提升主要有以下3個方面的原因。

1)當RDD緩存到內存時，相比直接從HDFS中讀取數據，效率提高很多。當算法在Spark平臺中執行時，中間數據以RDD的方式緩存在內存中，相對于MapReduce每個作業都需要進行磁盤的讀寫操作，大大地提高了磁盤I/O資源的利用效率。RDD的Cache機制減少磁盤I/O壓力的同時，還能提高數據并行讀取的能力，比如RDD3進行Cache后，RDD4和RDD7都可以同時訪問RDD3的數據，這比MapReduce作業之間重復從HDFS中讀取相同數據的問題,數據訪問效率再次提升。

表4 MapReduce與Spark平臺下的執行時間對比 s

圖3 算法在Spark環境中的計算流程分析

2)Spark作業啟動后會立即申請所需的Executor資源，并且所有Stage的Tasks以線程的方式運行，共用Executors資源。這相對于MapReduce以心跳的方式管理slot資源，Spark申請資源的次數大大減少，導致資源管理效率高于MapReduce。

3)MapReduce中算法總共需要執行多達12個Job，即使優化后能夠減少到7個，但作業的數量仍然較多。而通過Spark中的DAG編程模型，可以實現將多個MapReduce作業簡化為單個Spark DAG作業。而DAG作業會進一步分解為多個Stage，每個Stage包含多個可并行執行的Task，由于Spark資源管理效率比MapReduce高，使得Spark中的Task并行執行效率比MapReduce更高。

5 結語

大數據的規模效應給數據存儲、管理以及數據分析帶來了極大挑戰，高效率低成本的大數據處理技術成為學術界及工業界的研究熱點。隨著MapReduce生態系統的日趨完善，MapReduce逐漸成為工業與學術屆事實上的海量數據并行處理標準，但MapReduce的優勢在于處理批處理作業。對于具有復雜業務處理邏輯的互聯網數據挖掘類作業，由于這些算法通常需要多個MapReduce作業協作完成，但多個作業之間嚴重的冗余磁盤讀寫及重復的資源申請操作，使得算法的性能較低。在此背景下，本文選擇ItemBased作為研究對象，首先對基于MapReduce的ItemBased協同過濾算法實現及性能缺陷進行了分析；并在此基礎上提出利用Spark在迭代計算和內存計算上的優勢，提高算法的執行效率的方法，進而在Spark平臺下對ItemBased算法進行了實現；最后通過對比實驗，驗證了Spark平臺下算法性能相對MapReduce平臺的優越性，并對算法效率提高的原因進行了分析。

下一步工作主要是在本文的基礎上，研究利用JVM(Java Virtual Machine)參數優化、矩陣計算優化及并行度調優等方法進一步提高算法的計算效率。

References)

[1] The digital universe in 2020: big data, bigger digital shadows, and biggest growth in the far east [EB/OL]. [2017- 03- 15]. http://www.emc.com/collateral/analyst-reports/idc-the-digitaluniverse-in - 2020.pdf.

[2] 孟小峰,慈祥.大數據管理:概念、技術與挑戰[J].計算機研究與發展,2013,50(1):146-149.(MENG X F, CI X. Big data management: concepts, techniques and challenges [J]. Journal of Computer Research and Development, 2013, 50(1): 146-149)

[3] GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system [C]// Proceedings of the 19th ACM Symposium on Operating System Principles. New York: ACM, 2003: 29-43.

[4] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [C]// OSDI 2004: Proceedings of the 2004 Conference on Operating System Design and Implementation. New York: ACM, 2004: 137-150.

[5] 廖彬,張陶,于炯,等.MapReduce能耗建模及優化分析[J].計算機研究與發展,2016,53(9):2107-2131.(LIAO B, ZHANG T, YU J, et al. Energy consumption modeling and optimization analysis for MapReduce [J]. Journal of Computer Research and Development, 2016, 53(9): 2107-2131.)

[6] 廖彬,于炯,張陶,等.基于分布式文件系統HDFS的節能算法[J].計算機學報,2013,36(5):1047-1064.(LIAO B, YU J, ZHANG T, et al. Energy-efficient algorithms for distributed file system HDFS [J]. Chinese Journal of Computers, 2013, 36(5): 1047-1064.)

[7] 張陶,于炯,廖彬,等.基于GraphX的傳球網絡構建及分析研究[J].計算機研究與發展,2016,53(12):2729-2752.(ZHANG T, YU J, LIAO B, et al. The construction and analysis of pass network graph based on GraphX [J]. Journal of Computer Research and Development, 2016, 53(12): 2729-2752.)

[8] 宋杰,劉雪冰,朱志良,等.一種能效優化的MapReduce資源比模型[J].計算機學報,2015,38(1):59-73.(SONG J, LIU X B, ZHU Z L, et al. An energy-efficiency optimized resource ratio model for MapReduce [J]. Chinese Journal of Computers, 2015, 38(1): 59-73.)

[9] 廖彬,張陶,于炯,等.溫度感知的MapReduce節能任務調度策略[J].通信學報,2016,37(1):61-75.(LIAO B, ZHANG T, YU J, et al. Temperature aware energy-efficient task scheduling strategies for MapReduce [J]. Journal on Communications, 2016, 37(1): 61-75.)

[10] 廖彬,張陶,于炯,等.適應節能與異構環境的MapReduce數據布局策略[J].中山大學學報(自然科學版),2015,54(6):55-66.(LIAO B, ZHANG T, YU J, et al. An energy-efficient and heterogeneous environment adaptive data layout strategy for MapReduce [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(6): 55-66.)

[11] 楊興耀,于炯,吐爾根·依布拉音,等.融合奇異性和擴散過程的協同過濾模型.軟件學報,2013,24(8):1868-1884.(YANG X Y, YU J, IBRAHIM T, et al. Collaborative filtering model fusing singularity and diffusion process [J]. Journal of Software, 2013, 24(8): 1868-1884.)

[12] GHAUTH K I, ABDULLAH N A. Learning materials recommendation using good learners’ ratings and content-based filtering [J]. Educational Technology Research and Development, 2010, 58(6): 711-727.

[13] UDDIN M N, SHRESTHA J, JO G S. Enhanced content-based filtering using diverse collaborative prediction for movie recommendation [C]// Proceedings of the 1st Asian Conference on Intelligent Information and Database Systems. Piscataway, NJ: IEEE, 2009: 132-137.

[14] NGUYEN A T, DENOS N, BERRUT C. Improving new user recommendations with rule-based induction on cold user data [C]// Proceedings of the 2007 ACM Conference on Recommender Systems. New York: ACM, 2007: 121-128.

[15] CHUN J, OH J Y, KWON S, et al. Simulating the effectiveness of using association rules for recommendation systems [C]// Proceedings of the 2005 Systems Modeling and Simulation: Theory and Applications. Berlin: Springer, 2005: 306-314.

[16] QIU L Y, BENBASAT I. A study of demographic embodiments of product recommendation agents in electronic commerce [J]. International Journal of Human-Computer Studies, 2010, 68(10): 669-688.

[17] CHEN T, HE L. Collaborative filtering based on demographic attribute vector [C]// Proceedings of the 2009 ETP International Conference on Future Computer and Communication. Piscataway, NJ: IEEE, 2009: 225-229.

[18] JIA C X, LIU R R, SUN D, et al. A new weighting method in network-based recommendation [J]. Physica A—Statistical Mechanics and Its Applications, 2008, 387(23): 5887-5891.

[19] ZHOUT, REN J, MEDO M, et al. Bipartite network projection and personal recommendation [J]. Physical Review E, 2007, 76(4): 1-7.

[20] LIU Z B, QU W Y, LI H T, et al. A hybrid collaborative filtering recommendation mechanism for P2P networks [J]. Future Generation Computer Systems, 2010, 26(8): 1409-1417.

[21] ZHAO Z D, SHANG M S. User-based collaborative-filtering recommendation algorithms on Hadoop [C]// Proceedings of the 2010 International Conference on Knowledge Discovery and Data Mining. Piscataway, NJ: IEEE, 2010: 478-481.

[22] MA M M, WANG S P. Research of user-based collaborative filtering recommendation algorithm based on Hadoop [C]// Proceedings of the 2015 International Conference on Computer Information Systems and Industrial Applications. Amsterdam: Atlantis Press, 2015: 63-66.

[23] SCHELTER S, BODEN C, MARKL V. Scalable similarity-based neighborhood methods with MapReduce [C]// Proceedings of the 2012 ACM Conference on Recommender Systems. New York: ACM, 2012: 163-170.

[24] DAS A S, DATAR M, GARG A, et al. Google news personalization: scalable online collaborative filtering [C]// Proceedings of the 2007 International Conference on World Wide Web. New York: ACM, 2007: 271-280.

[25] JIANG J, LU J, ZHANG G, et al. Scaling-up item-based collaborative filtering recommendation algorithm based on Hadoop [C]// Proceedings of the 2011 IEEE World Congress on Services. Piscataway, NJ: IEEE, 2011: 490-497.

This work is partially supported by the National Natural Science Foundation of China (61562078, 61262088), the Natural Science Foundation of Xinjiang Uygur Autonomous Region (2016D01B014).

LIAOBin, born in 1986, Ph. D., associate professor. His research interests include green computing, data mining, big data calculation model.

ZHANGTao, born in 1988, Ph. D. candidate. Her research interests include distributed computing, grid computing.

GUOBinglei, born in 1991, Ph. D. candidate. Her research interests include green computing, database system.

YUJiong, born in 1964, Ph. D., professor. His research interests include network security, grid computing, distributed computing.

ZHANGXuguang, born in 1994, M. S. candidate. His research interests include big data computing.

LIUYan, born in 1990, M. S. candidate. His research interests include big data computing.

PerformanceoptimizationofItemBasedrecommendationalgorithmbasedonSpark

LIAO Bin1*, ZHANG Tao2,3, GUO Binglei3, YU Jiong3, ZHANG Xuguang1, LIU Yan4

(1.CollegeofStatisticsandInformation,XinjiangUniversityofFinanceandEconomics,UrumqiXinjiang830012,China;2.CollegeofMedicalEngineeringandTechnology,XinjiangMedicalUniversity,UrumqiXinjiang830011,China;3.SchoolofInformationScienceandEngineering,XinjiangUniversity,UrumqiXinjiang830008,China;4.SchoolofSoftware,TsinghuaUniversity,Beijing100084,China)

Under MapReduce computing scenarios, complex data mining algorithms typically require multiple MapReduce jobs’ collaboration process to compete the task. However, serious redundant disk read and write and repeat resource request operations among multiple MapReduce jobs seriously degrade the performance of the algorithm under MapReduce. To improve the computational efficiency of ItemBased recommendation algorithm, firstly, the performance issues of the ItemBased collaborative filtering algorithm under MapReduce platform were analyzed. Secondly, the execution efficiency of the algorithm was improved by taking advantage of Spark’s performance superiority on iterative computation and memory computing, and the ItemBased collaborative filtering algorithm under Spark platform was implemented. The experimental results show that, when the size of the cluster nodes is 10 and 20, the running time of the algorithm in Spark is only 25.6% and 30.8% of that in MapReduce. The algorithm’s overall computing efficiency of Spark platform improves more than 3 times compared with that of MapReduce platform.

collaborative filtering; MapReduce; Spark algorithm; performance optimization; Directed Acyclic Graph (DAG)

TP393.09

:A

2017- 01- 16;

:2017- 03- 01。

國家自然科學基金資助項目(61562078, 61262088)；新疆維吾爾自治區自然科學基金資助項目(2016D01B014)。

廖彬(1986—)，男，四川內江人，副教授，博士，CCF會員，主要研究方向：綠色計算、數據挖掘、大數據計算模型； 張陶(1988—),女,新疆烏魯木齊人，博士研究生，主要研究方向：分布式計算、網格計算； 國冰磊(1991—)，女，湖北武漢人，博士研究生，主要研究方向:綠色計算、數據庫系統； 于炯(1964—)，男，北京人，教授，博士，主要研究方向:網絡安全、網格計算、分布式計算； 張旭光(1994—),男，河南鄭州人，碩士研究生，主要研究方向：大數據計算； 劉炎(1990—),男，湖北武漢人，碩士研究生，主要研究方向：大數據計算。

1001- 9081(2017)07- 1900- 06

10.11772/j.issn.1001- 9081.2017.07.1900