并行聚類算法在MapReduce上的實(shí)現(xiàn).pdf

1、互聯(lián)網(wǎng)上的數(shù)據(jù)以海量的規(guī)模存在并迅速增長(zhǎng)，從海量的數(shù)據(jù)中挖掘出價(jià)值含量高的信息是技術(shù)上的迫切要求。聚類算法作為一種非監(jiān)督學(xué)習(xí)的方法，是包括數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別、圖像分析等諸多領(lǐng)域數(shù)據(jù)統(tǒng)計(jì)分析的一種常用技術(shù)。傳統(tǒng)的串行式的聚類算法存在著兩個(gè)問(wèn)題，已經(jīng)難以滿足實(shí)際應(yīng)用的需求：一是聚類的速度不快，效率不是很高；二是在面對(duì)規(guī)模比較大的數(shù)據(jù)時(shí)，受制于內(nèi)存容量的限制，往往不能有效地運(yùn)行。
　　 Google提出的MapReduce概

2、念是當(dāng)前比較流行的分布式計(jì)算框架。本文研究?jī)煞N在MapReduce上實(shí)現(xiàn)的聚類算法：并行化譜聚類和并行化AP聚類。分別實(shí)現(xiàn)這兩種算法在10臺(tái)機(jī)器組成的Hadoop集群上分布式計(jì)算。
　　 并行化譜聚類算法的策略是計(jì)算相似矩陣和稀疏化時(shí)按數(shù)據(jù)點(diǎn)標(biāo)識(shí)切分；計(jì)算特征向量時(shí)把拉普拉斯矩陣存到分布式文件系統(tǒng)HDFS上，采用分布式Lanczos運(yùn)算，并行計(jì)算得到特征向量；最后對(duì)特征向量的轉(zhuǎn)置矩陣采用并行K-means聚類得到聚類結(jié)果。通過(guò)對(duì)

3、算法的每一步采用不同的并行策略，使得整個(gè)算法在速度上獲得線性增長(zhǎng)。
　　 并行化AP聚類的策略是先把吸引度矩陣和歸屬度矩陣分布式存儲(chǔ)在HBase上，每次迭代中的吸引度矩陣和歸屬度矩陣的計(jì)算按行分割，使其矩陣值的運(yùn)算按行分布在多臺(tái)機(jī)器上運(yùn)算。隨著機(jī)器的增加，以線性的增長(zhǎng)速度加快算法的運(yùn)算。
　　 通過(guò)在Corel圖像集上做實(shí)驗(yàn)，分析比較兩種并行聚類算法在MapReduce框架上的性能和聚類效果，從而為上面提到的兩個(gè)聚類問(wèn)題