基于MapReduce的K-Means算法設計與實現(xiàn)

1、基于MapReduce的K-Means算法的設計與實現(xiàn)導師：李天瑞教授1概要研究背景基于MapReduce的K-Means算法設計實驗結(jié)果和分析K-Means簡介研究背景大數(shù)據(jù)時代的來臨數(shù)據(jù)呈現(xiàn)爆炸性增長傳統(tǒng)的平臺無法滿足需求亟需新的平臺云計算的出現(xiàn)天才般的MapReduce計算框架開源的Hadoop平臺聚類算法和大數(shù)據(jù)數(shù)據(jù)越大，聚類效果越好3K-Means簡介輸入：聚類個數(shù)K，以及包含N個數(shù)據(jù)待聚類數(shù)據(jù)集輸出：聚類中心不再變化的K個聚類中心算法過程：從從數(shù)據(jù)集中隨機選取K個數(shù)據(jù)作為中心測量所有數(shù)據(jù)到每個中心的距離，并把它歸到最近的中心的類重新計算已經(jīng)得到的各個類的中心迭代23步直至新的中心與

2、原中心的距離小于指定閾值，算法結(jié)束4K-Means算法流程圖5K-Means示例6基于MapReduce的K-Means算法設計算法設計偽代碼Map偽代碼Partion偽代碼Reduce偽代碼OutputFormat偽代碼7算法設計job：計算新的聚類中心Map：輸入：輸出：Reduce：輸入：輸出：迭代job，直至相連兩次的聚類中心小于閾值8流程圖9Map偽代碼public void map(Object key, Text value,OutputCollector output, Reporter reporter) String line = value.toString().trim

3、();int sort = 0;/聚類類別double minDis = Double.MAX_VALUE;for (int i = 1; i =K; i+) double tmpDis = calDis(i, line);/數(shù)據(jù)和類i間的距離if (tmpDis minDis) sort = i;minDis = tmpDis;output.collect(new IntWritable(sort), value);10Partition偽代碼 public class KeyPartition implements Partitioner Overridepublic int getPar

4、tition(K key, V value, int n) / TODO Auto-generated method stubreturn Math.abs(key.hashCode()%n;Overridepublic void configure(JobConf arg0) / TODO Auto-generated method stub11Reduce偽代碼public void reduce(IntWritable key, Iterator values,OutputCollector output, Reporter reporter) int rows = 0, i = 0;/

5、rows表示數(shù)據(jù)條數(shù)double records = new doubleCOLS;/COLS為全局變量，表示屬性的個數(shù)while (values.hasNext() rows+;String tmp = values.next().toString();StringTokenizer itr = new StringTokenizer(tmp);i = 0;while (itr.hasMoreTokens() & i COLS) recordsi+ += Double.parseDouble(itr.nextToken();String line = ;for (i = 0; i COLS;

6、 i+) line += recordsi/rows+ t;output.collect(key, new Text(line);12OutputFormat偽代碼public class extendsMultipleTextOutputFormat /使輸出文件名為類型K的值，本例為1、2、3Overrideprotected String generate(K key, V value,String name) return key.toString();Overrideprotected K generateActualKey(K key, V value) return null;13實驗結(jié)果和分析開發(fā)環(huán)境實驗數(shù)據(jù)運行結(jié)果結(jié)果分析14開發(fā)環(huán)境 Red Hat Linux操作系統(tǒng)Hadoop開源軟件，版本Hadoop-1.0.3節(jié)點數(shù)目：10節(jié)點配置：4個CPU，16核，內(nèi)存12GJDK1.7.0Eclipse-SDK-4.2.1-linux-gtk15實驗數(shù)據(jù)數(shù)據(jù)集295個數(shù)據(jù)100個屬性選取了3個聚類中心16運行結(jié)果迭代前后的中心間的距離迭代次數(shù)距離10.416281752617621720.226