基于MapReduce的CLOPE并行聚類算法

王玉平，郝楊楊，黃有方

(1.上海海事大學(xué)信息化辦公室， 上海201306; 2.上海海事大學(xué)物流研究中心， 上海201306)

?

基于MapReduce的CLOPE并行聚類算法

王玉平1，郝楊楊2，黃有方2

(1.上海海事大學(xué)信息化辦公室， 上海201306; 2.上海海事大學(xué)物流研究中心， 上海201306)

事務(wù)型數(shù)據(jù)的CLOPE聚類算法在運行速度、內(nèi)存開銷和聚類效果方面表現(xiàn)優(yōu)異，但隨著數(shù)據(jù)量飛速增長，其運行時間也隨之急劇變長甚至無法使用。為此，利用Hadoop框架下的YARN資源管理系統(tǒng)，對CLOPE算法進(jìn)行改進(jìn)，提出基于MapReduce架構(gòu)的CLOPE并行聚類算法。該算法由兩個階段組成，第一階段執(zhí)行Map操作，Hadoop架構(gòu)對數(shù)據(jù)集分片并行并運行CLOPE算法聚類成小聚簇;第二階段執(zhí)行Reduce操作，通過多次迭代把各個小聚簇聚合成大聚簇。實驗結(jié)果證明：分析1 000條20 000個屬性的亞馬遜數(shù)據(jù)記錄，MapReduce-CLOPE算法耗時穩(wěn)定在22 s，而CLOPE算法耗時在50～60 s。隨著數(shù)據(jù)量的增大，CLOPE算法無法計算而MapReduce-CLOPE算法耗時基本穩(wěn)定。因此，MapReduce-CLOPE算法在計算時間方面要顯著地優(yōu)于CLOPE算法，且計算時間受數(shù)據(jù)量大小的影響較小，而在聚類質(zhì)量方面與CLOPE算法相近。

數(shù)據(jù)挖掘;CLOPE;MapReduce;聚類算法;Hadoop

0 引 言

聚類是數(shù)據(jù)挖掘領(lǐng)域中的一種工具，它的作用是把數(shù)據(jù)對象集劃分成多個組或簇的過程，使得簇內(nèi)的對象具有很高的相似性，但又與其他簇中的對象很不相似。作為統(tǒng)計學(xué)的一個分支，聚類分析已經(jīng)被廣泛而深入的研究，成果主要集中在基于距離的聚類分析，如k-均值(k-means)、k-中心點(k-medoids)等方法。基于距離的聚類分析算法簡單直接，擅長處理低維的數(shù)值數(shù)據(jù)。

然而，在現(xiàn)實生活中，存在大量的非數(shù)值型的標(biāo)稱事務(wù)數(shù)據(jù)，比如商場購物數(shù)據(jù)、域名訪問數(shù)據(jù)和Web日志等等。……