基于hadoop數(shù)據(jù)挖掘算法研究-碩士研究生論文答辯ppt

1、基于Hadoop數(shù)據(jù)挖掘算法研究,導(dǎo)師：王靜宇 學(xué)生：盧勝宇,Cloud Computing,1,2,3,課題的背景,基于Hadoop平臺的Canopy-Kmeans并行算法,課題總結(jié),Cloud Computing,4,實驗與結(jié)果分析,相關(guān)概念,Cloud Computing,課題背景,聚類算法及其分類Kmeans算法Canopy算法HadoopMapReduce,Cloud Computing,聚類算法及其分類,聚類是對點

2、進行考察并按照某種距離測度將它們聚成多個“簇”的過程。聚類的目標(biāo)是使得同一簇內(nèi)的點之間距離比較短，而不同簇中點之間距離較大。,課題背景,Cloud Computing,課題背景,,聚類主要包括以下幾個過程：數(shù)據(jù)準(zhǔn)備、特征選擇、提出、特征提取、聚類、聚類結(jié)果驗證。動態(tài)的聚類過程步驟如下所示：,Cloud Computing,課題背景,Canopy 算法是 McCallum提出的一種簡單、快速、但不太準(zhǔn)確的聚類方法，是專門應(yīng)對高維海量數(shù)據(jù)

3、源的一種新型聚類算法。算法的思路是：首先在計算數(shù)據(jù)樣本距離時采用算法復(fù)雜度低的距離度量(metric distance)，把樣本數(shù)據(jù)集劃分為一些部分重疊的子集，這種子集稱之為華蓋(canopies)。然后，在傳統(tǒng)聚類中，比如 k 均值，應(yīng)用復(fù)雜度高的度量距離，進一步計算，從而使得高維海量數(shù)據(jù)源聚類難題易于實現(xiàn)。,K-Means算法是由 MacQueen 提出來的，該算法思想簡單，實現(xiàn)相對容易，在多個學(xué)科里面都有廣泛應(yīng)用。它是聚類算法中最

4、常見的劃分方法，所謂的劃分方法就是給定一個包含 n 個數(shù)據(jù)對象的數(shù)據(jù)集，將數(shù)據(jù)集劃分為 k 個子集，其中每個子集均代表一個聚類，同一聚類中的對象相似度較高，而不同聚類中的對象相似度較小。,Cloud Computing,Hadoop平臺,Hadoop是Apache旗下開源的分布式計算框架,可編寫以及可運行分布式應(yīng)用來處理大規(guī)模數(shù)據(jù)。Hadoop框架最核心組成部分就是HDFS(Hadoop Distributed File System)

5、和MapReduce。,課題背景,Cloud Computing,課題背景,,MapReduce是一種編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運算。概念Map（映射）和Reduce（歸約），是它們的主要思想，都是從函數(shù)式編程語言里借來的，還有從矢量編程語言里借來的特性。它極大地方便了編程人員在不會分布式并行編程的情況下，將自己的程序運行在分布式系統(tǒng)上。 當(dāng)前的軟件實現(xiàn)是指定一個Map（映射）函數(shù)，用來把一組鍵值對映射成一組新的鍵值

6、對，指定并發(fā)的Reduce（歸約）函數(shù)，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。,MapReduce,為什么選擇基于Hadoop平臺的Canopy-Kmeans并行算法？,Cloud Computing,課題背景,Cloud Computing,1.隨著大數(shù)據(jù)時代的到來,同時硬件的提升也越來越困難,導(dǎo)致現(xiàn)在我們在單機下處理大規(guī)模數(shù)據(jù)遇到了前所未有的阻力和難度。2.傳統(tǒng)的K-means算法在處理海量數(shù)據(jù)時效率低下、聚類質(zhì)量差等

7、弊端日益顯露出來，其時間復(fù)雜度較高且處理數(shù)據(jù)的能力存在局限性也尤為突出。3.基于Hadoop平臺的CK-means并行算法，該算法采用canopy算法改善K-means算法在確定初始聚類中心的盲目性，采用并行計算框架對算法并行擴展，使之能夠適應(yīng)對海量數(shù)據(jù)處理。,課題背景,1,2,3,課題的背景,基于Hadoop平臺的Canopy-Kmeans并行算法,課題總結(jié),Cloud Computing,4,實驗與結(jié)果分析,Cloud Compu

8、ting,算法的基本思想,CK-means算法是對K-means算法的一種優(yōu)化，算法的思想為：采用基于余弦距離度量方式的canopy聚類算法對數(shù)據(jù)集初始中心點進行優(yōu)化，canopy聚類算法利用MapReduce計算模式實現(xiàn)并行計算運行，經(jīng)過Map和Reduce階段得到全局的canopy中心集合，在對數(shù)據(jù)集進行精確聚類之前，還需要利用上面獲取的全局canopy中心集合對數(shù)據(jù)集進行粗糙聚類，生成多個互相重疊的canopy聚類集合，這一系列的

9、工作為下一步K-means精確聚類奠定基礎(chǔ)。,算法流程,Canopy中心點生成,得到穩(wěn)定的聚類,結(jié)束,Canopy粗糙聚類生成,中心點標(biāo)注,新中心點生成,聚類結(jié)果生成,開始,,,,,,,,Cloud Computing,,,Cloud Computing,Canopy—Kmeans算法并行實現(xiàn),根據(jù)前面的Canopy_Kmeans算法并行流程圖，我們將整個過程設(shè)計成了兩個MapReduce階段，第一階段執(zhí)行Canopy算法,第二階段

10、執(zhí)行Kmeans算法。,第一階段Canopy算法的MapReduce實現(xiàn),實現(xiàn)Canopy算法包括三個MR，即三個Job，可以描述為下面2個步驟：（1）Job1：將輸入數(shù)據(jù)處理為Canopy算法可以使用的輸入格式。（2）Job2：每個Mapper針對自己的輸入執(zhí)行Canopy聚類，輸出每個Canopy的中心向量。（3）Job2:每個Reducer接收Mapper的中心向量，并加以整合以計算最后的Canopy的中心向量。（4）Jo

11、b3：根據(jù)Job2的中心向量來對原始數(shù)據(jù)進行分類。,,Cloud Computing,第二階段Kmeans算法的MapReduce實現(xiàn),Kmeans算法利用上一階段的生成的簇中心向量列表，對數(shù)據(jù)對象集合進行劃分其主要的MapReduce編程模型包括了Map、Combine和Reduce三個階段。,Map階段,輸入依然是各個數(shù)據(jù)塊集合，輸入格式為,,,Combine階段,,Combine函數(shù)用于合并Map結(jié)果中相同的key2的鍵值對，輸入

12、是Map的輸出m，key3依然還是簇類向量標(biāo)識符，value3為相同key3的所有向量組合和這些向量的數(shù)目。,,Reduce階段,,處理屬于同一簇的所有數(shù)據(jù)對象向量，并重新生成新的簇類中心向量，其輸入輸出均是鍵值對形式，輸入信息是各個子節(jié)點的combine結(jié)果，輸出信息是簇類標(biāo)識符和新的簇類中,,1,2,3,課題的背景,基于Hadoop平臺的Canopy-Kmeans并行算法,課題總結(jié),Cloud Computing,4,實驗與結(jié)果分析

13、,,Cloud Computing,實驗平臺的搭建,由于實驗條件有限，本實驗平臺集群共4臺計算機，搭建4個節(jié)點，服務(wù)器的配置如下表所示：,服務(wù)器的網(wǎng)絡(luò)配置如下,操作系統(tǒng)：CentOS 6JDK 版本：1.7Hadoop版本：2.5.2Mahout版本：0.10.1,Cloud Computing,軟件環(huán)境,搭建Hadoop集群，Hadoop部署情況：,,Cloud Computing,啟動集群和Mahout,Web UI查看集群是

14、否啟動成功，在Master節(jié)點上啟動Firefox瀏覽器，在瀏覽器地址欄輸入http://master:50070/，檢查namenode和datanode是否啟動正常。啟動正常的UI頁面如圖2.10所示：,當(dāng)Hadoop平臺正常啟動后，然后啟動Mahout,,Cloud Computing,實驗過程,,首先要準(zhǔn)備數(shù)據(jù)，本實驗運用的數(shù)據(jù)是在網(wǎng)站：http://archive.ics.uci.edu/ml/databases/synth

15、etic_control/synthetic_control.data中下載相應(yīng)數(shù)據(jù)synthetic_control.data。測試數(shù)據(jù)是由Dr Robert Alcock在1999年利用程序合成的600個樣本的控制圖數(shù)據(jù)。每個樣本包括60個屬性列，一共可以分為6類，分別為：正常（C）、循環(huán)（B）、上升趨勢（E）、下降趨勢（A）、向上移位（D）、向下移位（F）。首先上傳該文本數(shù)據(jù)到HDFS。上傳后在文件系統(tǒng)監(jiān)控界面查看此文件。,,Cl

16、oud Computing,分別執(zhí)行Canopy算法和Kmeans算法,,Cloud Computing,實驗結(jié)果分析,并行算法收斂曲線圖,算法加速比分析,,Cloud Computing,算法可擴展性分析,1,2,3,課題的背景,基于Hadoop平臺的Canopy-Kmeans并行算法,課題總結(jié),Cloud Computing,4,實驗與結(jié)果分析,課題總結(jié)——已完成的工作,針對傳統(tǒng)的串行K-means聚類算法在處理海量數(shù)據(jù)時出現(xiàn)性能及

17、初始聚類中心敏感等問題，提出了一種基于Hadoop平臺的并行CK-means聚類算法，該算法采用Canopy算法和余弦相似度度量來改善K-means算法在確定初始聚類中心的盲目性，采用并行計算框架對算法并行擴展，使之能夠適應(yīng)海量數(shù)據(jù)處理。實驗結(jié)果表明提出的基于Hadoop 平臺的CK-means并行算法具有更好的聚類質(zhì)量，在處理海量數(shù)據(jù)時具有良好的加速比和擴展性。,課題總結(jié)——已完成的工作,本文的主要工作有：,（1）針對傳統(tǒng)的串行K-m

18、eans聚類算法在處理海量數(shù)據(jù)時出現(xiàn)性能及初始聚類中心敏感等問題，提出了一種基于Hadoop平臺的并行CK-means聚類算法。（2）通過利用代價低的余弦相似性度量方式的Canopy算法快速獲取聚類中心作為K-means并行算法的初始聚類中心，加快K-means算法的收斂速度。（3）該算法對原始數(shù)據(jù)使用基于余弦相似度度量方式的Canopy算法進行聚類和覆蓋劃分，使得并行K-means算法進行精確聚類時不需要計算不處于同一個C

19、anopy的點之間的距離，這在很大程度上減少計算量。（4）實驗驗證所提出的CK-means算法的聚類質(zhì)量、加速比和擴展性。,研究進度—存在的問題,雖然在搭建好的Hadoop平臺上對本文提出的一種基于Hadoop平臺的CKmeans算法進行了實驗驗證，但實驗數(shù)據(jù)單一，并且由于條件有限，adoop平臺下處理數(shù)據(jù)的結(jié)點較少，這也造成了該算法在不同量的結(jié)點上得出的結(jié)論，且本實驗沒有在單機模式下也就是看kmeans串行算法進行對比實驗，這也將是

20、論文下一步的工作重點。,課題總結(jié)——下一步改進計劃,（1）繼續(xù)對Hadoop平臺的相關(guān)技術(shù)進行研究，對Hadoop中的HDFS分布式存儲系統(tǒng)與MapReduce編程模式做進一步研究。（2）繼續(xù)完善實驗平臺，由于實驗室結(jié)點有限，以后要盡量選擇多的節(jié)點對本文提出的算法進行并行實驗，并選擇不同數(shù)據(jù)集對本文提出的算法驗證。,期刊論文發(fā)表情況（已見刊）,盧勝宇，王靜宇，張曉琳，高俊峰．基于Hadoop平臺的K-means聚類算法優(yōu)化研究[J]．