• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      K—Means聚類算法在MapReduce框架下的實現(xiàn)

      2017-01-21 14:51:17楊健兵
      軟件導(dǎo)刊 2016年12期
      關(guān)鍵詞:聚類算法數(shù)據(jù)挖掘

      楊健兵

      摘 要:MapReduce是一種編程模型,這種編程模型編程簡單,不必關(guān)心底層實現(xiàn)細節(jié),可用于大規(guī)模數(shù)據(jù)集的并行計算。K-Means是一種簡單、基本的數(shù)據(jù)挖掘聚類方法,它將對象組織成多個互斥的組或簇。針對K-Means的特點,給出了MapReduce編程模型下K-Means的實現(xiàn)方法。實驗結(jié)果表明,MapReduce編程模型下的K-Means算法部署在Hadoop集群上運行具有較好的性能。

      關(guān)鍵詞:K-Means;MapReduce;數(shù)據(jù)挖掘;聚類算法

      DOIDOI:10.11907/rjdk.162043

      中圖分類號:TP311

      文獻標識碼:A文章編號:1672-7800(2016)012-0030-03

      0 引言

      伴隨著計算機技術(shù)的不斷進步和互聯(lián)網(wǎng)技術(shù)在各領(lǐng)域的深入發(fā)展,海量數(shù)據(jù)在各行業(yè)中不斷產(chǎn)生。由于傳統(tǒng)的數(shù)據(jù)挖掘算法往往運行在一臺普通的計算機上,但面對大量的數(shù)據(jù)尤其是海量數(shù)據(jù)時,傳統(tǒng)的計算機在計算能力、處理速度、存儲容量、帶寬速度等多個方面往往表現(xiàn)出力不從心。面對這些問題,云計算提出使得這些問題迎刃而解。云計算是基于網(wǎng)絡(luò)平臺上的一種計算模型,可以在多臺計算機上同時平行運行。它的模型可以由一系列普通計算機加上網(wǎng)絡(luò)組成,對計算機硬件要求相對較低,但其性能可達到普通計算機的若干倍以上。這種計算模型為數(shù)據(jù)挖掘領(lǐng)域開辟了一條新路徑。

      MapReduce模型[1]是美國谷歌公司提出的一種分布式并行編程模型,其主要功能是可以利用大量計算機處理海量的數(shù)據(jù)。對于MapReduce這種編程模型,Map和Reduce是其主要思想,通過Map和Reduce,編程人員可以在不通曉分布式并行編程的情況下,將自己的程序運行在分布式系統(tǒng)上。通過Apache開源社區(qū)Hadoop項目[2],程序設(shè)計人員實現(xiàn)了該模型,使得該模型進行分布式并行計算成為可能。

      根據(jù)文獻記載,多種數(shù)據(jù)挖掘算法已經(jīng)在云計算編程模型MapReduce上實現(xiàn)。冀素琴等[3]提出了基于MapReduce的K-Means聚類集成,謝雪蓮等[4]提出了基于云計算的并行K-Means聚類算法研究,黃斌等[5]提出了基于MapReduce 的數(shù)據(jù)挖掘平臺設(shè)計與實現(xiàn),毛典輝等[6]提出了基于MapReduce的Canopy-Kmeans改進算法。本文結(jié)合各自算法的思想與MapReduce 的運行機理,提出K-Means聚類算法在MapReduce框架下的實現(xiàn)。在MapReduce框架下,K-Means聚類算法的使用范圍由單機擴展到云計算平臺,在面對海量數(shù)據(jù)時,極大地減少了K-Means聚類算法的運行時間,顯著地提高了運行效率。

      1 MapReduce編程模型

      MapReduce編程模型采用分治法的思想,在主節(jié)點管理下,MapReduce編程模型將海量的數(shù)據(jù)分發(fā)給各分節(jié)點共同完成,各節(jié)點對中間結(jié)果進行分類、排序、整合并得到最終結(jié)果。簡言之,MapReduce就是任務(wù)分解與結(jié)果匯總。

      1.1 MapRedue集群結(jié)構(gòu)

      MapReduce任務(wù)需由幾個部分協(xié)作完成。它主要有4個部分組成:Client客戶端、JobTracker、TaskTracker以及分布式文件系統(tǒng)。

      1.2 MapReduce執(zhí)行過程

      在Hadoop中,有兩個機器角色用來執(zhí)行MapReduce任務(wù),一個是JobTracker,另一個是TaskTracker。JobTracker的作用是執(zhí)行調(diào)度工作,在Hadoop集群中有且只有一個,TaskTracker的作用是執(zhí)行任務(wù),在Hadoop集群中有若干個。圖1描述了MapReduce的運行機制,在數(shù)據(jù)輸入階段,輸入文件按照一定的標準進行分片;在Map階段,在JobTracker的統(tǒng)一調(diào)度下,多個TaskTracker完成Map運算任務(wù)并生成中間結(jié)果;在Shuffle階段完成中間計算結(jié)果的排序和分類;在Reduce階段,在JobTracker統(tǒng)一調(diào)度下,多個TaskTracke完成Reduce任務(wù);Reduce任務(wù)完成后通知JobTracker以產(chǎn)生最后的輸出結(jié)果。

      2 K-Means聚類算法實現(xiàn)

      2.1 K-Means聚類算法

      K-Means算法是很典型的基于距離的聚類算法,它將對象組織成多個互斥的組或簇,一般采用歐式距離作為評價指標,即認為兩個對象的距離越近,其相似度就越大。假設(shè)數(shù)據(jù)集D包含n個歐式空間中的對象。聚類的目的是將D的對象分配到k個簇C1,…,Ck中,使得對于1≤i,j≤k,Ci∈D且Ci∩Cj=¢。聚類劃分以簇內(nèi)高相似性和簇間低相似性為目標。

      設(shè)p是空間中的點,表示給定的數(shù)據(jù)對象;ci是簇Ci的中心,其中p和ci都是多維數(shù)據(jù)。對象p∈Ci與該簇的代表ci之差用dist(p,ci)度量,其中dist(x,y)是兩個點x和y之間的歐式距離。簇Ci的質(zhì)量可以用簇內(nèi)變差度量,它是Ci中所有對象與中心ci之間的誤差平方和,定義為:

      E是數(shù)據(jù)集中所有對象的誤差平方和。

      根據(jù)給定的公式,K-Means算法的具體實現(xiàn)過程如下:在初始化過程中,在數(shù)據(jù)集中任意選擇k個對象,每個對象代表該簇的中心點,對于其余的每個對象,根據(jù)它們與各簇中心的距離,將該對象劃分到最近的簇。然后對于k個簇,重新計算其均值。更新后的均值作為該簇新的簇中心。迭代繼續(xù),直到分配穩(wěn)定。圖2為K-Means聚類算法的串行計算流程。

      K-mean均值的算法復(fù)雜度為O(nkt),其中n是對象總數(shù),k是用戶指定的簇數(shù),t為迭代次數(shù)。通常情況下k<

      2.2 算法實現(xiàn)

      K-Means聚類算法在MapReduce模型下處理的基本思路如下:對K-Means的串行計算過程執(zhí)行MapReduce計算,Map階段完成每個記錄到簇中心點距離的計算,并標記到每個記錄所屬的類別;在Reduce階段,根據(jù)Map函數(shù)得到的結(jié)果進行分類排序即可計算出新的聚類中心,供下一輪Map使用,如果本輪Reduce得到的聚類中心與上輪相比變化小于給定的閾值則算法結(jié)束,反之進行新一輪的MapReduce過程。

      2.2.1 Map函數(shù)設(shè)計

      Map階段的主要任務(wù)是通過計算每個記錄到簇中心點距離,并將該記錄標記所屬的簇。在進行Map計算之前,MapReduce會根據(jù)輸入文件計算輸入數(shù)據(jù)片分片,每個數(shù)據(jù)片針對一個Map任務(wù),輸入數(shù)據(jù)片存儲的并非數(shù)據(jù)本身,而是,key為行號,value為該記錄行的內(nèi)容。Map函數(shù)對輸入的每個記錄行計算其到所有簇中心的距離,并根據(jù)最小距離將該記錄標示到最近的簇中心,并作出新類別標記。輸出中間結(jié)果以對的形式展現(xiàn)。

      2.2.2 Reduce函數(shù)設(shè)計

      在Reduce階段,根據(jù)Map函數(shù)得到的中間結(jié)果將相同類別的數(shù)據(jù)組成一個簇,并計算出新的聚類中心,供下一輪Map使用。輸入數(shù)據(jù)以(key, value)對的形式展示,key為聚類所屬類別,value為該簇中記錄向量,所有key相同的數(shù)據(jù)送給一個Reduce任務(wù),累計計算key相同數(shù)據(jù)的均值,得到新的聚類中心。輸出結(jié)果,其中key為聚類類別,value是均值。Map和Reduce處理過程如圖3所示。

      2.3 算法時間復(fù)雜度分析

      在MapReduce框架下處理K-Means聚類算法,數(shù)據(jù)預(yù)處理階段,通過Hadoop平臺下的分布式文件系統(tǒng),把要處理的數(shù)據(jù)先存儲在其中,然后將數(shù)據(jù)根據(jù)分塊原則分別存儲在不同的節(jié)點上。在Map計算階段,通過將相應(yīng)的數(shù)據(jù)塊分配給Map任務(wù)進行計算。如果每個節(jié)點完成p個Map任務(wù),那么其時間復(fù)雜度為O(nkt/p)。這樣可大大提高計算效率和計算速度,節(jié)省算法運行時間。

      3 實驗結(jié)果

      通過實驗,對K-Means聚類方法在MapReduce框架下的實現(xiàn)效果進行了展示和評估。

      3.1 實驗環(huán)境

      該實驗在南京工業(yè)大學(xué)云平臺上進行,平臺由一系列IBM服務(wù)構(gòu)建。其中管理節(jié)點1個,計算機節(jié)點16個,網(wǎng)絡(luò)采用萬兆網(wǎng)絡(luò),操作系統(tǒng)采用RedHat Linux。在硬件配置上,每一個節(jié)點的CPU 采用Intel Xeon 2.0GCPU,8G內(nèi)存,100G硬盤,軟件配置Hadoop 。

      3.2 實驗結(jié)果

      單個樣本為15個整數(shù),分別生成106(54M)、107(540M)、108(5400M)個樣本作為數(shù)據(jù)集。K-Means算法的實驗結(jié)果如圖4、圖5、圖6所示。

      從圖4可看出,并行運行時間遠遠地大于單擊運行時間。這是由于MapReduce進行并行計算之初,其初始化過程需要一定的時間,耗費一定的機器性能。同時由于該文件只有54M,只需要分配給一個Map任務(wù)去執(zhí)行。因此對于數(shù)據(jù)量比較少的數(shù)據(jù),單機運行的效率反而高、時間耗費反而少。

      從圖5可看出,隨著數(shù)據(jù)量的增多,MapReduce的優(yōu)勢慢慢地凸顯出來。根據(jù)理論計算,540兆數(shù)據(jù)可以分為9個分片,通過分析,如果節(jié)點數(shù)量比較少的時候,MapReduce的優(yōu)勢不但不夠明顯,反而還不如單機K-Means計算,但是隨著節(jié)點逐漸增多,MapReduce的計算優(yōu)勢逐漸顯露起來,并且計算時間逐漸減少。但是當節(jié)點超過5個時,節(jié)點數(shù)目已經(jīng)飽和,所以運行時間基本保持不變。

      從圖6可看出,當數(shù)據(jù)量非常大時,MapReduce的絕對優(yōu)勢一覽無遺,并且隨著集群中節(jié)點數(shù)量的增加,運行時間逐漸減少。當節(jié)點到達一定數(shù)目時,MapReduce運行算法達到它的極限值,該任務(wù)的運行時間達到最小。

      4 結(jié)語

      隨著互聯(lián)網(wǎng)業(yè)務(wù)的不斷發(fā)展,每天都有大量的數(shù)據(jù)產(chǎn)生,對于產(chǎn)生的數(shù)據(jù)用數(shù)據(jù)挖掘的方法對它進行分析并提取有益的信息已經(jīng)成為大家關(guān)注的重點。在源源不斷的數(shù)據(jù)產(chǎn)生以后,可以在MapReduce框架下采用K-Means方法對這些數(shù)據(jù)進行聚類。

      本文提出了面對大量數(shù)據(jù)時如何使用MapReduce框架去處理這些數(shù)據(jù)的基本思路。實驗表明,該解決方法在處理大量數(shù)據(jù)時可以極大地提高運行速度和效率。

      參考文獻:

      [1] DEAN J,GHEMAWAT S.MapReduce simplified data processing on large cluster[J].Communication of the ACM,2006,51(1):107-113.

      [2] APACHE HADOOP. Hadoop[EB/OL].http://hadoop.apache.org.

      [3] 冀素琴,石洪波.面向海量數(shù)據(jù)的K-Means聚類優(yōu)化算法[J].計算工程與應(yīng)用,2014,50(14):143-147.

      [4] 謝雪蓮,李蘭友.基于云計算的并行K-Means聚類算法研究[J].計算機測量與控制,2014,22(5):1510-1512.

      [5] 黃斌,許舒人,蒲衛(wèi).基于MapReduce 的數(shù)據(jù)挖掘平臺設(shè)計與實現(xiàn)[J].計算機工程與設(shè)計,2013(2):495-501.

      (責(zé)任編輯:孫 娟)

      猜你喜歡
      聚類算法數(shù)據(jù)挖掘
      探討人工智能與數(shù)據(jù)挖掘發(fā)展趨勢
      基于并行計算的大數(shù)據(jù)挖掘在電網(wǎng)中的應(yīng)用
      電力與能源(2017年6期)2017-05-14 06:19:37
      數(shù)據(jù)挖掘算法性能優(yōu)化的研究與應(yīng)用
      基于K?均值與AGNES聚類算法的校園網(wǎng)行為分析系統(tǒng)研究
      基于改進的K_means算法在圖像分割中的應(yīng)用
      大規(guī)模風(fēng)電場集中接入對電力系統(tǒng)小干擾穩(wěn)定的影響分析
      科技視界(2016年8期)2016-04-05 18:39:39
      一種基于Hadoop的大數(shù)據(jù)挖掘云服務(wù)及應(yīng)用
      基于GPGPU的離散數(shù)據(jù)挖掘研究
      泰顺县| 花莲市| 青田县| 班玛县| 涟水县| 来宾市| 册亨县| 仪陇县| 离岛区| 承德县| 宽城| 容城县| 闻喜县| 肥东县| 永城市| 老河口市| 旬邑县| 沧源| 龙胜| 吴旗县| 湄潭县| 开远市| 双峰县| 大悟县| 会同县| 于都县| 阿巴嘎旗| 古交市| 南乐县| 从化市| 石楼县| 峨眉山市| 鄂伦春自治旗| 玉门市| 罗山县| 无极县| 新昌县| 丘北县| 玉田县| 兴仁县| 宁波市|