一種基于Hadoop平臺下的K-means算法

1、一種基于Hadoop平臺的聚類-K-means算法的并行實(shí)現(xiàn)導(dǎo)師：黃萍姓名：陳濤 范金蘭班級：2008計(jì)算機(jī)科學(xué)與技術(shù)（3）班打開目錄Hodoop平臺簡介與平臺搭建研究背景及意義K-means聚類算法分析K-means聚類算法并行原理分析基于MapReduse的K-means具體實(shí)現(xiàn)思想目 錄打開目錄Hodoop平臺簡介與平臺搭建研究背景及意義K-means聚類算法分析K-means聚類算法并行原理分析基于MapReduse的K-means具體實(shí)現(xiàn)思想目 錄Hodoop平臺簡介與平臺搭建研究背景及意義K-means聚類算法分析K-means聚類算法并行原理分析基于MapReduse的K-mea

2、ns具體實(shí)現(xiàn)思想目 錄打開目錄研究背景及意義 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中,提取隱含在其中未知的、有潛在應(yīng)用價值的信息或模式的過程.計(jì)算機(jī)技術(shù)的迅猛發(fā)展以及網(wǎng)絡(luò)的普及,使人們有更多機(jī)會使用便捷的方法與外界進(jìn)行信息交流.可是,數(shù)據(jù)大量的涌入,增加了我們獲取有用信息的難度. 打開目錄研究背景及意義 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中,提取隱含在其中未知的、有潛在應(yīng)用價值的信息或模式的過程.計(jì)算機(jī)技術(shù)的迅猛發(fā)展以及網(wǎng)絡(luò)的普及,使人們有更多機(jī)會使用便捷的方法與外界進(jìn)行信息交流.可是,數(shù)據(jù)大量的涌入,增加了我們獲取有用信息的難度. 打開目錄Had

3、oop平臺簡介Hadoop 的簡介 Hadoop是一個分布式系統(tǒng)基礎(chǔ)架構(gòu)。由Apache基金會開發(fā)。用戶可以在不了解分布式底層細(xì)節(jié)的情況下，開發(fā)分布式程序。充分利用集群的威力高速運(yùn)算和存儲。也可以說Hadoop是以分散存儲和并行計(jì)算為基礎(chǔ)的云計(jì)算平臺，利用低成本的PC設(shè)備組成大型集群，構(gòu)建下一代高性能的海量數(shù)據(jù)分布式計(jì)算平臺。 hadoop的核心主要包含：HDFS 和 MapReduce HDFS是分布式文件系統(tǒng)，用于分布式存儲海量數(shù)據(jù)。MapReduce是分布式數(shù)據(jù)處理模型，本質(zhì)是并行處理。 打開目錄Hadoop平臺簡介Hadoop 的簡介 Hadoop是一個分布式系統(tǒng)基礎(chǔ)架構(gòu)。由Apach

4、e基金會開發(fā)。用戶可以在不了解分布式底層細(xì)節(jié)的情況下，開發(fā)分布式程序。充分利用集群的威力高速運(yùn)算和存儲。也可以說Hadoop是以分散存儲和并行計(jì)算為基礎(chǔ)的云計(jì)算平臺，利用低成本的PC設(shè)備組成大型集群，構(gòu)建下一代高性能的海量數(shù)據(jù)分布式計(jì)算平臺。 hadoop的核心主要包含：HDFS 和 MapReduce HDFS是分布式文件系統(tǒng)，用于分布式存儲海量數(shù)據(jù)。MapReduce是分布式數(shù)據(jù)處理模型，本質(zhì)是并行處理。 打開目錄Hadoop平臺簡介Hadoop 的簡介 Hadoop 框架可在單一的 Linux 平臺上使用（開發(fā)和調(diào)試時），但是使用存放在機(jī)架上的商業(yè)服務(wù)器才能發(fā)揮它的力量。這些機(jī)架組成一個

5、 Hadoop 集群。它通過集群拓?fù)渲R決定如何在整個集群中分配作業(yè)和文件。Hadoop 假定節(jié)點(diǎn)可能失敗，因此采用本機(jī)方法處理單個計(jì)算機(jī)甚至所有機(jī)架的失敗。簡單的hadoop集群簡化視圖如下圖所示。 打開目錄Hadoop平臺簡介Hadoop 的簡介 Hadoop 框架可在單一的 Linux 平臺上使用（開發(fā)和調(diào)試時），但是使用存放在機(jī)架上的商業(yè)服務(wù)器才能發(fā)揮它的力量。這些機(jī)架組成一個 Hadoop 集群。它通過集群拓?fù)渲R決定如何在整個集群中分配作業(yè)和文件。Hadoop 假定節(jié)點(diǎn)可能失敗，因此采用本機(jī)方法處理單個計(jì)算機(jī)甚至所有機(jī)架的失敗。簡單的hadoop集群簡化視圖如下圖所示。 打開目錄H

6、adoop平臺簡介Hadoop 的簡介 Hadoop 框架可在單一的 Linux 平臺上使用（開發(fā)和調(diào)試時），但是使用存放在機(jī)架上的商業(yè)服務(wù)器才能發(fā)揮它的力量。這些機(jī)架組成一個 Hadoop 集群。它通過集群拓?fù)渲R決定如何在整個集群中分配作業(yè)和文件。Hadoop 假定節(jié)點(diǎn)可能失敗，因此采用本機(jī)方法處理單個計(jì)算機(jī)甚至所有機(jī)架的失敗。簡單的hadoop集群簡化視圖如下圖所示。 ClientNameNodeDataNodeDataNodeDataNodeDataNodeTCP/IP Networking打開目錄Hadoop平臺簡介Hadoop 的簡介 Hadoop 框架可在單一的 Linux 平臺

7、上使用（開發(fā)和調(diào)試時），但是使用存放在機(jī)架上的商業(yè)服務(wù)器才能發(fā)揮它的力量。這些機(jī)架組成一個 Hadoop 集群。它通過集群拓?fù)渲R決定如何在整個集群中分配作業(yè)和文件。Hadoop 假定節(jié)點(diǎn)可能失敗，因此采用本機(jī)方法處理單個計(jì)算機(jī)甚至所有機(jī)架的失敗。簡單的hadoop集群簡化視圖如下圖所示。 ClientNameNodeDataNodeDataNodeDataNodeDataNodeTCP/IP Networking打開目錄Hadoop平臺簡介Hadoop的運(yùn)行模式1.單機(jī)模式2.偽分布式模式一個機(jī)器即當(dāng)namenode又當(dāng)datanode,或者說即是jobtracker,又是tasktrack

8、er。沒有所謂的在多臺機(jī)器上進(jìn)行真正的分布式計(jì)算，故稱為偽分布式。 3.完全分布式模式 本文的實(shí)驗(yàn)將會分別在單機(jī)模式和完全分布式模式進(jìn)行操作。打開目錄Hadoop平臺簡介Hadoop的運(yùn)行模式1.單機(jī)模式2.偽分布式模式一個機(jī)器即當(dāng)namenode又當(dāng)datanode,或者說即是jobtracker,又是tasktracker。沒有所謂的在多臺機(jī)器上進(jìn)行真正的分布式計(jì)算，故稱為偽分布式。 3.完全分布式模式 本文的實(shí)驗(yàn)將會分別在單機(jī)模式和完全分布式模式進(jìn)行操作。打開目錄Hadoop平臺簡介Hadoop的運(yùn)行模式1.單機(jī)模式2.偽分布式模式一個機(jī)器即當(dāng)namenode又當(dāng)datanode,或者說

9、即是jobtracker,又是tasktracker。沒有所謂的在多臺機(jī)器上進(jìn)行真正的分布式計(jì)算，故稱為偽分布式。 3.完全分布式模式 本文的實(shí)驗(yàn)將會分別在單機(jī)模式和完全分布式模式進(jìn)行操作。流程圖ClientNameNodeDataNodeDataNodeDataNodeDataNodeTCP/IP Networking打開目錄Hadoop平臺簡介Hadoop的運(yùn)行模式1.單機(jī)模式2.偽分布式模式一個機(jī)器即當(dāng)namenode又當(dāng)datanode,或者說即是jobtracker,又是tasktracker。沒有所謂的在多臺機(jī)器上進(jìn)行真正的分布式計(jì)算，故稱為偽分布式。 3.完全分布式模式 本文的實(shí)

10、驗(yàn)將會分別在單機(jī)模式和完全分布式模式進(jìn)行操作。流程圖ClientNameNodeDataNodeDataNodeDataNodeDataNodeTCP/IP Networking打開目錄Hadoop平臺搭建準(zhǔn)備工作（1）下載vm虛擬機(jī)并進(jìn)行安裝；（2）Redhat Linux 9.0的安裝； 新建虛擬機(jī)，加載Redhat Linux 9.0系統(tǒng)的iso鏡像文件，并在虛擬機(jī)下安裝 linux系統(tǒng)。（3）linux系統(tǒng)的簡單設(shè)置； 對linux系統(tǒng)進(jìn)行簡單的網(wǎng)絡(luò)設(shè)置，使其接入Internet。（4）JDK的安裝 下載jdk安裝文件jdk-6u30-linux-i586.bin，在終端下進(jìn)入jdk-

11、6u30-linux-i586.bin文件所在目錄，執(zhí)行命令./jdk-6u30-linux-i586.bin 一直按回車。之后在該目錄下生成jdk-1.6.0目錄。（5）hadoop的安裝 在linux系統(tǒng)中，下載hadoop-0.21.0.tar.gz,j解壓到/home文件夾下。打開目錄Hadoop平臺搭建準(zhǔn)備工作（1）下載vm虛擬機(jī)并進(jìn)行安裝；（2）Redhat Linux 9.0的安裝； 新建虛擬機(jī)，加載Redhat Linux 9.0系統(tǒng)的iso鏡像文件，并在虛擬機(jī)下安裝 linux系統(tǒng)。（3）linux系統(tǒng)的簡單設(shè)置； 對linux系統(tǒng)進(jìn)行簡單的網(wǎng)絡(luò)設(shè)置，使其接入Internet

12、。（4）JDK的安裝 下載jdk安裝文件jdk-6u30-linux-i586.bin，在終端下進(jìn)入jdk-6u30-linux-i586.bin文件所在目錄，執(zhí)行命令./jdk-6u30-linux-i586.bin 一直按回車。之后在該目錄下生成jdk-1.6.0目錄。（5）hadoop的安裝 在linux系統(tǒng)中，下載hadoop-0.21.0.tar.gz,j解壓到/home文件夾下。打開目錄Hadoop平臺簡介與平臺搭建配置工作（1）配置JDK環(huán)境變量 PATH環(huán)境變量 CLASSPATH環(huán)境變量 JAVA_HOME環(huán)境變量（2）配置hadoop 單機(jī)模式配置： 修改hadoop-en

13、v.sh 。本機(jī)器上解壓路徑是/home/hadoop-0.21.0，進(jìn)入剛才所解壓的文件夾，修改之(需要root權(quán)限)。cd hadoop-0.21.0gedit conf/hadoop-env.sh 設(shè)置xml文件，需要設(shè)置conf文件夾下的三個文件core-site.xml, hdfs-site.xml, mapred-site.xml打開目錄Hadoop平臺簡介與平臺搭建配置工作（1）配置JDK環(huán)境變量 PATH環(huán)境變量 CLASSPATH環(huán)境變量 JAVA_HOME環(huán)境變量（2）配置hadoop 單機(jī)模式配置： 修改hadoop-env.sh 。本機(jī)器上解壓路徑是/home/hado

14、op-0.21.0，進(jìn)入剛才所解壓的文件夾，修改之(需要root權(quán)限)。cd hadoop-0.21.0gedit conf/hadoop-env.sh 設(shè)置xml文件，需要設(shè)置conf文件夾下的三個文件core-site.xml, hdfs-site.xml, mapred-site.xml打開目錄Hadoop平臺簡介與平臺搭建完全分布式模式的配置：首先，要兩臺機(jī)配置節(jié)點(diǎn)將master機(jī)密鑰復(fù)制大slave機(jī)上3.運(yùn)行hadoop（1）格式化分布式文件系統(tǒng)： $bin/hadoop namenode format (2)啟動hadoop：$bin/start-all.sh配置工作打開目錄Ha

15、doop平臺簡介與平臺搭建完全分布式模式的配置：首先，要兩臺機(jī)配置節(jié)點(diǎn)將master機(jī)密鑰復(fù)制大slave機(jī)上3.運(yùn)行hadoop（1）格式化分布式文件系統(tǒng)： $bin/hadoop namenode format (2)啟動hadoop：$bin/start-all.sh配置工作打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離

16、,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前

17、一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類

18、結(jié)果.開始結(jié)束輸入聚類個數(shù)k,n初始化k個聚類中心分配各個數(shù)據(jù)對象到距離最近的類中重新計(jì)算各個聚類的中心輸入聚類的結(jié)果是否收斂否是打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2

19、),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.開始結(jié)束輸入聚類個數(shù)k,n初始化k個聚類中心分配各個數(shù)據(jù)對象到距離最近的類中重新計(jì)算各個聚類的中心輸入聚類的結(jié)果是否收斂否是流程圖數(shù)據(jù)分布最終結(jié)果第一次迭代打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)

20、與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出

21、聚類結(jié)果.流程圖數(shù)據(jù)分布最終結(jié)果第一次迭代打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.打開目錄K-means聚類算法分析 K-means

22、算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.流程圖數(shù)據(jù)分布最終結(jié)果第一次迭代打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的

23、數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.打開目錄K-means聚類算法分析 K-means算法的核心思想是把n個數(shù)據(jù)對象劃分為k個聚類,使每個聚類中的數(shù)據(jù)點(diǎn)到該聚類中心的平方和最小,算法處理過程： 輸入：聚類個數(shù)k,包含n個數(shù)據(jù)對象的數(shù)據(jù)集.

24、輸出：k個聚類.(1)從n個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心.(2)分別計(jì)算每個對象到各個聚類中心的距離,把對象分配到距離最近的聚類中.(3)所有對象分配完成后,重新計(jì)算k個聚類的中心.(4)與前一次計(jì)算得到的k個聚類中心比較,如果聚類中心發(fā)生變化,轉(zhuǎn)(2),否則轉(zhuǎn)(5).(5)輸出聚類結(jié)果.流程圖數(shù)據(jù)分布最終結(jié)果第一次迭代打開目錄K-means聚類并行原理分析 設(shè)分布式系統(tǒng)中有p個站點(diǎn),從中任意選定一個站點(diǎn)Sm為主站點(diǎn),其余p-1個站點(diǎn)為從站點(diǎn).首先在主站點(diǎn)隨機(jī)產(chǎn)生k個聚簇中心作為全局初始聚簇中心,并將其廣播給所有從站點(diǎn)；各站點(diǎn)根據(jù)這些中心確認(rèn)本站數(shù)據(jù)對象所屬聚簇,并通過公式得到

25、局部聚簇中心,同時,從站點(diǎn)將本站點(diǎn)的局部聚簇中心點(diǎn)及相應(yīng)簇的數(shù)據(jù)對象總數(shù)傳送給主站點(diǎn)；主站點(diǎn)根據(jù)這些聚簇信息計(jì)算全局聚簇中心.迭代上述過程,直到全局判別函數(shù)E值穩(wěn)定,也即全局聚簇中心穩(wěn)定 打開目錄K-means聚類并行原理分析 設(shè)分布式系統(tǒng)中有p個站點(diǎn),從中任意選定一個站點(diǎn)Sm為主站點(diǎn),其余p-1個站點(diǎn)為從站點(diǎn).首先在主站點(diǎn)隨機(jī)產(chǎn)生k個聚簇中心作為全局初始聚簇中心,并將其廣播給所有從站點(diǎn)；各站點(diǎn)根據(jù)這些中心確認(rèn)本站數(shù)據(jù)對象所屬聚簇,并通過公式得到局部聚簇中心,同時,從站點(diǎn)將本站點(diǎn)的局部聚簇中心點(diǎn)及相應(yīng)簇的數(shù)據(jù)對象總數(shù)傳送給主站點(diǎn)；主站點(diǎn)根據(jù)這些聚簇信息計(jì)算全局聚簇中心.迭代上述過程,直到全局判

26、別函數(shù)E值穩(wěn)定,也即全局聚簇中心穩(wěn)定 打開目錄K-means聚類并行原理分析 設(shè)分布式系統(tǒng)中有p個站點(diǎn),從中任意選定一個站點(diǎn)Sm為主站點(diǎn),其余p-1個站點(diǎn)為從站點(diǎn).首先在主站點(diǎn)隨機(jī)產(chǎn)生k個聚簇中心作為全局初始聚簇中心,并將其廣播給所有從站點(diǎn)；各站點(diǎn)根據(jù)這些中心確認(rèn)本站數(shù)據(jù)對象所屬聚簇,并通過公式得到局部聚簇中心,同時,從站點(diǎn)將本站點(diǎn)的局部聚簇中心點(diǎn)及相應(yīng)簇的數(shù)據(jù)對象總數(shù)傳送給主站點(diǎn)；主站點(diǎn)根據(jù)這些聚簇信息計(jì)算全局聚簇中心.迭代上述過程,直到全局判別函數(shù)E值穩(wěn)定,也即全局聚簇中心穩(wěn)定 打開目錄K-means聚類并行原理分析 設(shè)分布式系統(tǒng)中有p個站點(diǎn),從中任意選定一個站點(diǎn)Sm為主站點(diǎn),其余p-1個

27、站點(diǎn)為從站點(diǎn).首先在主站點(diǎn)隨機(jī)產(chǎn)生k個聚簇中心作為全局初始聚簇中心,并將其廣播給所有從站點(diǎn)；各站點(diǎn)根據(jù)這些中心確認(rèn)本站數(shù)據(jù)對象所屬聚簇,并通過公式得到局部聚簇中心,同時,從站點(diǎn)將本站點(diǎn)的局部聚簇中心點(diǎn)及相應(yīng)簇的數(shù)據(jù)對象總數(shù)傳送給主站點(diǎn)；主站點(diǎn)根據(jù)這些聚簇信息計(jì)算全局聚簇中心.迭代上述過程,直到全局判別函數(shù)E值穩(wěn)定,也即全局聚簇中心穩(wěn)定 打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 在進(jìn)行K-Means聚類中，在處理每一個數(shù)據(jù)點(diǎn)時只需要知道：各個cluster 的中心不需要知道關(guān)于其他數(shù)據(jù)點(diǎn)的任何信息所以，如果涉及到全局信息，只需要知道關(guān)于各個cluster center

28、的信息即可打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 在進(jìn)行K-Means聚類中，在處理每一個數(shù)據(jù)點(diǎn)時只需要知道：各個cluster 的中心不需要知道關(guān)于其他數(shù)據(jù)點(diǎn)的任何信息所以，如果涉及到全局信息，只需要知道關(guān)于各個cluster center的信息即可打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 將所有的數(shù)據(jù)分布到不同的node 上，每個node只對自己的數(shù)據(jù)進(jìn)行計(jì)算每個node能夠讀取上一次迭代生成的cluster centers，并計(jì)算自己的各個數(shù)據(jù)點(diǎn)應(yīng)該屬于哪一個cluster每個node在一次迭代中根據(jù)自己的數(shù)據(jù)點(diǎn)計(jì)算新的clust

29、er centers綜合每個節(jié)點(diǎn)計(jì)算出的cluster centers，計(jì)算出最終的實(shí)際cluster centers打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 將所有的數(shù)據(jù)分布到不同的node 上，每個node只對自己的數(shù)據(jù)進(jìn)行計(jì)算每個node能夠讀取上一次迭代生成的cluster centers，并計(jì)算自己的各個數(shù)據(jù)點(diǎn)應(yīng)該屬于哪一個cluster每個node在一次迭代中根據(jù)自己的數(shù)據(jù)點(diǎn)計(jì)算新的cluster centers綜合每個節(jié)點(diǎn)計(jì)算出的cluster centers，計(jì)算出最終的實(shí)際cluster centers打開目錄基于Mapreduce的K-means

30、并行算法的具體實(shí)現(xiàn)思想 每一個節(jié)點(diǎn)需要訪問如下的全局文件當(dāng)前的迭代計(jì)數(shù)cluster idcluster center屬于該cluster center的數(shù)據(jù)點(diǎn)的個數(shù)這是唯一的全局文件打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 每一個節(jié)點(diǎn)需要訪問如下的全局文件當(dāng)前的迭代計(jì)數(shù)cluster idcluster center屬于該cluster center的數(shù)據(jù)點(diǎn)的個數(shù)這是唯一的全局文件打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 令 k = 3，欲生成 cluster-0 和 cluster-1選取x1(1,2),x2(2,2),x3(2,5)

31、作為中心點(diǎn) 假定將所有數(shù)據(jù)分布到2個節(jié)點(diǎn) node-0 和 node-1 上,即Cluster-0Cluster-1打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 令 k = 3，欲生成 cluster-0 和 cluster-1選取x1(1,2),x2(2,2),x3(2,5)作為中心點(diǎn) 假定將所有數(shù)據(jù)分布到2個節(jié)點(diǎn) node-0 和 node-1 上,即Cluster-0Cluster-1打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 在開始之前，首先創(chuàng)建一個如前所述的全局文件迭代次數(shù)0Cluster idcluster中心# of data p

32、oints assignedcluster-0 x1(1,2)0cluster-1x2(2,2)0cluster-2x3(2,5)0打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 在開始之前，首先創(chuàng)建一個如前所述的全局文件迭代次數(shù)0Cluster idcluster中心# of data points assignedcluster-0 x1(1,2)0cluster-1x2(2,2)0cluster-2x3(2,5)0打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map階段每個節(jié)點(diǎn)讀取全局文件，以獲得上一輪迭代生成的cluster centers

33、等信息計(jì)算自己的每一個數(shù)據(jù)點(diǎn)到各個cluster center的距離為每一個數(shù)據(jù)點(diǎn)，emit打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map階段每個節(jié)點(diǎn)讀取全局文件，以獲得上一輪迭代生成的cluster centers等信息計(jì)算自己的每一個數(shù)據(jù)點(diǎn)到各個cluster center的距離為每一個數(shù)據(jù)點(diǎn)，emit打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)

34、算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：所屬節(jié)點(diǎn)數(shù)據(jù)點(diǎn)到各個cluster的距離比較Assigned tocluster-0cluster-1cluster-2node-0 x1近c(diǎn)luster-0 x2近c(diǎn)luster-1x3近c(diǎn)luster-2x4近c(diǎn)luster-2x5近c(diǎn)luster-2x6近c(diǎn)luster-2node-0 x7近c(diǎn)luster-2x8近c(diǎn)luster-2x9近c(diǎn)luster-2x10近c(diǎn)luster-

35、2x11近c(diǎn)luster-2打開目錄打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：所屬節(jié)點(diǎn)數(shù)據(jù)點(diǎn)到各個cluster的距離比較Assigned tocluster-0cluster-1cluster-2node-0 x1近c(diǎn)luster-0 x2近c(diǎn)luster-1x3近c(diǎn)luster-2x4近c(diǎn)luster-2x5近c(diǎn)luster-2x6近c(diǎn)luster-2node-0 x7近c(diǎn)luster-2x8近c(diǎn)luster-2x9近c(diǎn)luster-2x10近c(diǎn)luster-2x11近c(diǎn)l

36、uster-2計(jì)算中心Map迭代基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：node-0輸出：node-1輸出：打開目錄打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Map Iteration1 計(jì)算各個數(shù)據(jù)點(diǎn)到各個cluster的距離，假定是如下的結(jié)果：流程圖數(shù)據(jù)分布node-0輸出：node-1輸出：打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Combine階段利用combiner減少map階段emit的大量數(shù)據(jù)Combiner計(jì)算每

37、一個cluster的center，以及屬于該cluster的數(shù)據(jù)點(diǎn)的個數(shù)然后，為每一個cluster發(fā)射 key-value pair key - cluster id, value -【 # of data points of this cluster ，average value】打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Combine階段利用combiner減少map階段emit的大量數(shù)據(jù)Combiner計(jì)算每一個cluster的center，以及屬于該cluster的數(shù)據(jù)點(diǎn)的個數(shù)然后，為每一個cluster發(fā)射 key-value pair key - cl

38、uster id, value -【 # of data points of this cluster ，average value】打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Combine Iteration1node-0發(fā)射：node-1發(fā)射：打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Combine Iteration1node-0發(fā)射：node-1發(fā)射：打開目錄基于Mapreduce的K-means并行算法的具體實(shí)現(xiàn)思想 Reduce階段每個reducer收到關(guān)于某一個cluster的信息，包括：該cluster 的id該cluster的數(shù)據(jù)點(diǎn)的均值及對應(yīng)于該均值的數(shù)據(jù)點(diǎn)的個數(shù)然后輸出當(dāng)前的迭代計(jì)