计算机科学
計算機科學
계산궤과학
Computer Science
2015年
11期
235-239,265
,共6页
王飞%秦小麟%刘亮%沈尧
王飛%秦小麟%劉亮%瀋堯
왕비%진소린%류량%침요
k-means%MapReduce%计算框架%数据流
k-means%MapReduce%計算框架%數據流
k-means%MapReduce%계산광가%수거류
k-means%MapReduce%Framework%Data stream
k-means算法是一种最常用的基于划分的聚类算法.传统的集中式k-means算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-means算法成为了目前亟需解决的问题.现有分布式k-means算法基于MapReduce计算框架且没有考虑初始聚类中心的影响.由于每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模.在该框架的基础上,提出了一种高效的k-means算法,它采用基于多次采样的初始聚类中心选取方法来实现负载均衡及减少迭代次数.实验结果表明,该算法的可扩展性较好,且效率比现有算法高.
k-means算法是一種最常用的基于劃分的聚類算法.傳統的集中式k-means算法已不能適應噹前呈爆炸式增長的數據規模,設計分佈式k-means算法成為瞭目前亟需解決的問題.現有分佈式k-means算法基于MapReduce計算框架且沒有攷慮初始聚類中心的影響.由于每箇MapReduce任務均需要讀寫分佈式文件繫統,導緻MapReduce不能有效錶達多箇任務之間的依賴關繫,因此提齣瞭一種基于數據流的計算框架,該框架建立在MapReduce之上,將數據處理過程按照數據流圖建模.在該框架的基礎上,提齣瞭一種高效的k-means算法,它採用基于多次採樣的初始聚類中心選取方法來實現負載均衡及減少迭代次數.實驗結果錶明,該算法的可擴展性較好,且效率比現有算法高.
k-means산법시일충최상용적기우화분적취류산법.전통적집중식k-means산법이불능괄응당전정폭작식증장적수거규모,설계분포식k-means산법성위료목전극수해결적문제.현유분포식k-means산법기우MapReduce계산광가차몰유고필초시취류중심적영향.유우매개MapReduce임무균수요독사분포식문건계통,도치MapReduce불능유효표체다개임무지간적의뢰관계,인차제출료일충기우수거류적계산광가,해광가건립재MapReduce지상,장수거처리과정안조수거류도건모.재해광가적기출상,제출료일충고효적k-means산법,타채용기우다차채양적초시취류중심선취방법래실현부재균형급감소질대차수.실험결과표명,해산법적가확전성교호,차효솔비현유산법고.