基于hadoop和mahout的asucf算法并行化研究

《基于hadoop和mahout的asucf算法并行化研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于Hadoop和Mahout的ASUCF算法并行化研究1弓I言(Introduction)互聯(lián)網(wǎng)時(shí)代，網(wǎng)絡(luò)資源紛雜，信息過載，個(gè)性化推薦成為緩解用戶在網(wǎng)絡(luò)中的信息迷茫問題的重要途徑［1］。在多項(xiàng)目、多領(lǐng)域的推薦中，因不依賴用戶或項(xiàng)目內(nèi)容，具有較好通用性的協(xié)同過濾算法［2］成為較為成功的推薦技術(shù)，其改進(jìn)因而也受到廣泛關(guān)注。然而，改進(jìn)的算法通常是以犧牲計(jì)算效率換取計(jì)算準(zhǔn)確度的提升。隨著大數(shù)據(jù)時(shí)代的來臨，解決計(jì)算效率的問題也迫在眉睫。由于單機(jī)模式的計(jì)算能力有限，而分布式計(jì)算具有多資源、可擴(kuò)展、高效計(jì)算等優(yōu)勢，所

2、以用分布式計(jì)算實(shí)現(xiàn)高效的CF算法，既能提高推薦準(zhǔn)確度，又能保證計(jì)算效率。目前主要使用云計(jì)算平臺(tái)Hadoop實(shí)現(xiàn)算法的并行化，如文獻(xiàn)［3-8］等是通過將算法移植至Hadoop,以得到高計(jì)算性能的算法。本文將基于平均相似度的協(xié)同過濾推薦算法(AverageSimilarityofUser-ItemCollaborativeFiltering,簡稱ASUCF)與開源分布式平臺(tái)Hadoop結(jié)合，改寫Mahout屮Item-basedCF分布式實(shí)現(xiàn)，研究ASUCF算法的并行化，探索其MapReducei±程設(shè)計(jì)，并通

3、過在不同規(guī)模的數(shù)據(jù)集上實(shí)驗(yàn)，比較單節(jié)點(diǎn)計(jì)算與多節(jié)點(diǎn)計(jì)算在計(jì)算效率上的差別，證明并行化后的ASUCF算法在計(jì)算效率上的優(yōu)勢，更能適應(yīng)大數(shù)據(jù)環(huán)境。2Hadoop平臺(tái)及ASUCF算法并行化分析(HadoopandanalysisofASUCFinparallel)21ASUCF算法概述文獻(xiàn)[9]詳細(xì)描述了ASUCF算法，并通過實(shí)驗(yàn)證明推薦準(zhǔn)確度的提高，在此對其簡單描述，為后續(xù)的并行化分析作鋪墊。ASUCF為避免矩陣預(yù)處理帶來的偏差，改進(jìn)的算法回歸到最原始的評(píng)分矩陣，從用戶行為分析、項(xiàng)目行為分析，引入平均相似度，將

4、計(jì)算預(yù)測評(píng)分分解成用戶角度的預(yù)測和項(xiàng)目角度的預(yù)測兩部分，綜合兩部分后得到最終的用戶對項(xiàng)目的預(yù)測評(píng)分。用戶的項(xiàng)目平均相似度和項(xiàng)目的用戶平均相似度計(jì)算分別如式⑴和式(2),和分別表示用戶已評(píng)分項(xiàng)冃的集合，對項(xiàng)冃已評(píng)分的用戶集合:IAS(c)=UAS(/)=Vsim(c■w)工sim(/17)C

5、c..(1)⑵綜合用戶、項(xiàng)目兩方面，弓I入U(xiǎn)AS、IAS,則目標(biāo)用戶對目標(biāo)項(xiàng)目的預(yù)測評(píng)分如式(3)所示。2.2Hadoop簡介Hadoop起源于Apache公司的Lucene和Nutch項(xiàng)冃[10],是谷歌云計(jì)算理論的J

6、ava語言實(shí)現(xiàn)。2006年，實(shí)現(xiàn)分布式文件系統(tǒng)和MapReduce的部分從Lucene和Nutch中分離出來，成為新項(xiàng)目Hadoop[11]0對應(yīng)GFS實(shí)現(xiàn)的HDFS、并行計(jì)算模型MapReduce是Hadoop中最核心的部分。HDFS是Hadoop中的文件管理系統(tǒng)，采用主從結(jié)構(gòu)，一個(gè)集群中包括一個(gè)主控服務(wù)器，即冃錄節(jié)點(diǎn)NameNode,用于索引DataNode、負(fù)責(zé)系統(tǒng)內(nèi)文件命名空間操作、數(shù)據(jù)塊和DataNode之間的映射關(guān)系等；以及多個(gè)塊服務(wù)器，即數(shù)據(jù)節(jié)點(diǎn)DataNode,用于數(shù)據(jù)物理存儲(chǔ)，文件通常被劃

7、分成若干個(gè)數(shù)據(jù)塊，儲(chǔ)存在不同的DataNode中[12]。MapReduce是一種可靠、高效的并行編程模型和計(jì)算框架，借助于HDFS等分布式技術(shù)，能夠處理各類PB數(shù)量級(jí)的大數(shù)據(jù)[13],其構(gòu)成部分主要有一個(gè)主控服務(wù)JobTracker,若干個(gè)從服務(wù)TaskTracker,分布式文件系統(tǒng)HDFS,以及客戶端Client[14],它們的主要功能分別是:(1)JobTracker：將作業(yè)劃分成若干個(gè)任務(wù)，分發(fā)給多個(gè)TaskTracker,管理任務(wù)的執(zhí)行以及輸出反饋。(2)TaskTracker：完成若干個(gè)Map、

8、Reduce任務(wù)，并向JobTracker實(shí)時(shí)反饋執(zhí)行情況。(3)HDFS：數(shù)據(jù)、相關(guān)信息的保存及管理。(4)客戶端Client：Map和Reduce程序的編寫，作業(yè)的提交。MapReduce通過分解任務(wù)、合并結(jié)果的分而治之思想實(shí)現(xiàn)可分解、可并行處理大數(shù)據(jù)集上的并行計(jì)算。MapReduce的任務(wù)執(zhí)行過程由Map和Reduce兩階段構(gòu)成，每次Map和Reduce的輸入和輸岀均是鍵值對vkey,value〉的形式，通過對相同key鍵值對的若干次歸類整理,調(diào)用用戶自定義的Map和Reduce函數(shù)，得到最終輸岀結(jié)果

9、。2.3ASUCF算法分析要實(shí)現(xiàn)算法的并行性，首先需要分析出算法中的可并行計(jì)算部分，以及并行計(jì)算部分與串行計(jì)算之間的關(guān)系。為方便表述，設(shè)：7im(iJhUASQ)⑴—工&陽cm)?US(c)XR,-&)通過對改進(jìn)算法ASUCF的分析，將每次推薦的計(jì)算分解為：UAS、IAS、、，其中又可分解為兩兩用戶的相似度計(jì)算和目標(biāo)預(yù)測評(píng)分的計(jì)算；又可分解為冃標(biāo)區(qū)域內(nèi)兩兩項(xiàng)冃的相似度計(jì)算和冃標(biāo)預(yù)測評(píng)分的計(jì)算。UAS、IAS之間不