An Improved parallel K-means Clustering Algorithm with MapReduce and Hadoop.pdf

1、數(shù)據(jù)聚類在在一些應(yīng)用中已經(jīng)得到廣泛使用，如數(shù)據(jù)挖掘、文檔檢索、圖像分割、模式分類。新興的信息技術(shù)的進步，使得對超大規(guī)模的數(shù)據(jù)進行聚類成為一個挑戰(zhàn)性的任務(wù)。
　　k-means算法是其中最著名的聚類算法，常用于各種各樣的問題。然而，在處理大數(shù)據(jù)時，k-means算法的性能不夠理想。MapReduce是一個最受歡迎的云計算并行框架，可有效處理大數(shù)據(jù)，基于MapReduce的k-means聚類算法便成為學者們關(guān)注的一個焦點。本文基于Ma

2、pReduce提出了一種并行式 k-means聚類算法，以提高算法性能。已有的并行k-means算法計算復(fù)雜度高，存在一些缺陷。本文先列舉了一些提高性能的并列 k-means算法，然后再提出一種更為有效的k-means改進算法。通過對影響算法性能的各因素進行深入研究，進而改進k-means算法。
　　距離度量可用來衡量簇的相似性。標準并行k-means使用歐幾里德距離度量，但是歐幾里得距離有時準確性不高,為了解決這個缺點,提出了距

3、離測量策略來并行k-means算法。基于某種策略，選擇最好的距離測量，使得傳統(tǒng)的并行k-means算法能取得更好的精度。產(chǎn)生集群的質(zhì)量嚴重依賴于初始質(zhì)心的選擇。聚類的質(zhì)量很大程度取決于初始質(zhì)心的選擇。隨機選擇初始質(zhì)心可以使我們花費很多的時間，而且得不到好的質(zhì)量，因為數(shù)據(jù)集收集時總是存在異常值，所以k-means算法對離群值非常敏感。若能刪除離群值,仔細選擇初始質(zhì)心，并行 k-means算法將獲得更好的處理時間和更好的質(zhì)量。傳統(tǒng)并行 k-

4、means在每個迭代中需計算每個數(shù)據(jù)對象和所有集群中心之間的距離,使得聚類的效率不高。本文提出了一種改進的并行k-means算法以解決上述問題,在每次迭代過程中需要一個簡單的數(shù)據(jù)結(jié)構(gòu)來存儲一些信息,用于下一次迭代。改進后的方法避免了重復(fù)性地計算每個數(shù)據(jù)對象到簇中心的距離以節(jié)省運行時間。本文改進的基于MapReduce并行 k-means聚類算法通過節(jié)省運行時間改善了傳統(tǒng)算法的性能,降低了迭代次數(shù),加快了處理速度。實驗結(jié)果表明,改進的基于