聚類概要與基于MapReduce的簡單實現(xiàn)

聚類:概要與基于MapReduce的簡單實現(xiàn)

翻譯:周敏coderplay@本文檔歸暨南大學計算機系opentalk組版權(quán)所有遵循CreativeCommonsAttribution2.5協(xié)議摘要聚類概念聚類算法矩離量度分層vs.劃分K-Means聚類算法復(fù)雜度Canopy聚類用K-Means和Canopy聚類算法對大數(shù)據(jù)集進行Mapreduce并行化什么是聚類?聚類Google新聞醫(yī)院記錄科學圖像生物學家探索DNA的組合,

天文圖像分析市場研究市場與產(chǎn)品定位社會網(wǎng)絡(luò)分析知識發(fā)現(xiàn)網(wǎng)頁搜索引擎…其它...集合中兩元素之間的相似度可以通過以下方法來計算：歐幾里德(Euclidean)距離曼哈坦(Manhattan)距離切比雪夫(Chebyshev)距離點積空間或其它自定義的距離量度…距離量度算法分類層次聚類劃分聚類其它層次聚類凝聚或分裂一個聚類同時把數(shù)據(jù)集分配到所有簇中.劃分聚類劃分聚類同時把數(shù)據(jù)集分配到所有簇中.K-Means聚類

非常簡單的劃分聚類選擇簇的數(shù)目k選擇k個點作為初始的聚類中心然后…K-Means聚類do{ 計算對象與各個聚類中心的距離

將對象劃分到距離最近的簇

重新計算每個新簇的均值}while(聚類中心不再變化)但是!計算復(fù)雜度非常高:

k*n*O(距離量度)*num(迭代次數(shù))

更糟的是,必須向各Mapper節(jié)點發(fā)送大量數(shù)據(jù).

因為帶寬和內(nèi)存原因,這是不可能做到的.此外以下三方面會形成大數(shù)據(jù)集:數(shù)據(jù)集中元素數(shù)目非常多.每個元素的特性很多.簇的數(shù)目非常多總結(jié)—聚類的計算量會非常龐大,即使你分布它.Canopy聚類為并行化聚類進行初始準備工作.用非常輕量的距離量度把數(shù)據(jù)劃分到重疊的區(qū)域中。高效精確Canopy聚類While(沒有未標記的數(shù)據(jù)點){

選擇一個沒有強標記的數(shù)據(jù)點p 把p看作一個新canopyc的中心

離p的距離在T1之內(nèi)的所有點都認為在c中,給這些點都作上弱標記

離p的距離在一個更小范圍T2(T1>T2)的所有點,都作上強標記}canopy聚類之后…繼續(xù)層次或劃分聚類,與傳統(tǒng)作法沒區(qū)別.位于不同canopy的對象,它們之間的距離看作無限大.MapReduce實現(xiàn)：

問題–用Canopy聚類,K-Means聚類,歐幾里德距離量度,高效劃分一個大數(shù)據(jù)集(比如…

有用戶投票的影片庫!)到指定數(shù)目個簇中.距離量度Canopy的距離量度($)K-Means的距離量度($$$)

步驟!讀取數(shù)據(jù),形成可以使用的格式(MR)獲取Canopy中心(MR)把數(shù)據(jù)點分配到各Canopy中(MR)獲取K-Means聚類中心K-Means算法(MR)迭代!數(shù)據(jù)傳遞這不是件有趣的事，但必須得做.選擇canopy中心把數(shù)據(jù)分配到Canopy中K-MeansMapElbow準則選擇簇數(shù)目,過濾對新增