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

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

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

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

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