李曉瑜，俞麗穎，雷 航，唐雪飛,2

?

一種K-means改進(jìn)算法的并行化實(shí)現(xiàn)與應(yīng)用

李曉瑜1，俞麗穎1，雷 航1，唐雪飛1,2

(1. 電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054；2. 成都康賽信息技術(shù)有限公司 成都 610054)

隨著數(shù)據(jù)的爆炸式增長，聚類研究作為大數(shù)據(jù)的核心問題之一，正面臨計算復(fù)雜度高和計算能力不足等諸多問題。提出了一種基于Hadoop的分布式改進(jìn)K-means算法，該算法通過引入Canopy算法初始化K-means算法的聚類中心，克服傳統(tǒng)K-means算法因初始中心點(diǎn)的不確定性，易陷入局部最優(yōu)解的問題。本算法在Canopy(罩蓋)中完成K-means聚類，并在Canopy間完成簇的合并，聚類效果穩(wěn)定，迭代次數(shù)少。同時，結(jié)合MapReduce分布式計算模型，給出改進(jìn)后算法的并行化設(shè)計方法和策略，進(jìn)一步通過改進(jìn)相似度度量方法，將該方法用于文本聚類中。實(shí)驗(yàn)結(jié)果證明該算法具有良好的準(zhǔn)確率和擴(kuò)展性。

canopy算法; Hadoop; MapReduce; 并行K-means; 文本聚類

隨著計算機(jī)和存儲技術(shù)的快速發(fā)展，在商業(yè)、社會、工程和醫(yī)學(xué)等各方面都會產(chǎn)生大規(guī)模的數(shù)據(jù)，人們開始關(guān)注如何對大規(guī)模的海量數(shù)據(jù)進(jìn)行分析和科學(xué)研究，進(jìn)而輔助商業(yè)決策和企業(yè)管理，高效地發(fā)現(xiàn)隱藏在數(shù)據(jù)中的有用知識。因此，對海量數(shù)據(jù)的挖掘得到了廣泛的研究和關(guān)注。

聚類分析是數(shù)據(jù)挖掘領(lǐng)域最重要的研究方向之一?！拔镆灶惥?、人以群分”，聚類算法是將物理或抽象的對象分成相似對象集合的過程。簇是數(shù)據(jù)對象的集合，同一簇中的對象彼此相似，而與其他簇中的對象相異[1-2]。與其他數(shù)據(jù)挖掘方法相比，聚類不需要先驗(yàn)知識，就可以完成數(shù)據(jù)的分類。聚類算法可以分為基于劃分的、密度的、模型的等多種類型[3]。

在基于劃分的聚類算法中，K-means算法被廣泛使用，它具有算法數(shù)學(xué)思想簡單、收斂速度快且易于實(shí)現(xiàn)等多種優(yōu)點(diǎn)[4]，但存在需要事先制定聚類個數(shù)，以及由于中心點(diǎn)選擇的隨機(jī)性而易陷入局部最優(yōu)解的問題。隨著數(shù)據(jù)量的增大，傳統(tǒng)的K-means算法在對海量數(shù)據(jù)集進(jìn)行分析時，已經(jīng)很難滿足現(xiàn)實(shí)需要。針對傳統(tǒng)K-means算法的缺點(diǎn)，已有很多學(xué)者在K-means的基礎(chǔ)上提出了改進(jìn)措施。文獻(xiàn)[5]針對初始聚類中心選擇的問題，提出了一種基于最優(yōu)劃分的聚類中心選擇算法，該算法通過對數(shù)據(jù)集進(jìn)行初始劃分，確定K-means的初始中心，提高了聚類的準(zhǔn)確度，但算法的遞歸次數(shù)會隨數(shù)據(jù)樣本維度的的增加而激增，因此導(dǎo)致算法實(shí)時性降低。文獻(xiàn)[6]提出了一種通過采樣和K-means預(yù)聚類，構(gòu)造相交子簇的加權(quán)連通圖，進(jìn)而合并子簇得到最終聚類結(jié)果的改進(jìn)K-means算法，該算法提高了K-means算法局部聚類的精度，但由于其缺乏對樣本空間的整體把握，聚類效果仍有待提高。文獻(xiàn)[7]提出使用Canopy算法優(yōu)化K-means算法，進(jìn)一步優(yōu)化了初始中心的選擇問題，但Canopy算法初始閾值大小的確定一般靠人工選取，因此效果并不穩(wěn)定。此外，文獻(xiàn)[8]采用AP聚類算法[9]來確定可取的最大值；文獻(xiàn)[3]提出采用最大最小距離法來選取初始聚類中心。基于以上算法本文以傳統(tǒng)的K-means聚類算法為基礎(chǔ)，探討了如何在MapReduce分布式框架下，快速、準(zhǔn)確、高效地進(jìn)行聚類，提出了一種針對海量數(shù)據(jù)挖掘的分布式聚類算法：即通過Canopy算法初始化來選擇K-means中心點(diǎn)，使待聚類的每個點(diǎn)在其所屬Canopy中進(jìn)行聚類，重新計算中心點(diǎn)，同時進(jìn)行鄰近Canopy的合并，反復(fù)以上過程直至收斂。并通過使用余弦相似度算法，將方法用于文本聚類中。

1 相關(guān)背景

1.1 并行計算理論

并行計算是指同時使用多種計算資源解決計算問題的過程。其目的是快速解決大型且復(fù)雜的計算問題。其首要任務(wù)是將一個應(yīng)用分解成多個子任務(wù)，將其分配給不同的處理器，同時各個處理器之間相互協(xié)同，并行地執(zhí)行子任務(wù)，最后將所有子任務(wù)的結(jié)果合并形成整體的計算任務(wù)結(jié)果，從而達(dá)到加速求解的目的。

Hadoop是Apache軟件基金會旗下的一個開源分布式計算平臺，以Hadoop分布式文件系統(tǒng)(HDFS)和MapReduce(Google MapReduce的開源實(shí)現(xiàn))為核心的Hadoop，為用戶提供了系統(tǒng)底層細(xì)節(jié)透明的分布式基礎(chǔ)框架[10]。MapReduce是一種用于處理海量數(shù)據(jù)的編程模型，它將并行處理海量數(shù)據(jù)的過程抽象成為“Map(映射)”和“Reduce(化簡)”兩個步驟[11]。Map任務(wù)將輸入的文件轉(zhuǎn)換成一個key-value對序列，Reduce將Map輸出的鍵值對序列以某種方式進(jìn)行合并和匯總，同時，Reduce輸出的key-value對會按照key位進(jìn)行排序。MapReduce的處理流程如圖1所示。MapReduce還提供Combine函數(shù)，Combine函數(shù)在Map結(jié)束后于本地進(jìn)行結(jié)果合并，相當(dāng)于本地的Reduce，可以大大減少網(wǎng)絡(luò)I/O操作的消耗。通過MapReduce提供的接口，使得開發(fā)人員大大減少了并行化開發(fā)的工作量，可以高效地利用分布式資源，而不需要分布式計算的開發(fā)經(jīng)驗(yàn)[12]，實(shí)現(xiàn)該框架下的應(yīng)用程序可以運(yùn)行在大規(guī)模集群，而且集群對應(yīng)用程序是透明的，具有很好的容錯機(jī)制，能夠可靠地并行處理大規(guī)模數(shù)據(jù)。

1.2 聚類算法

聚類是數(shù)據(jù)挖掘中的重要算法之一，它的目的是在無先驗(yàn)知識的條件下，按照數(shù)據(jù)集中數(shù)據(jù)本身的特點(diǎn)和差異，把一個數(shù)據(jù)集分割成若干個不同的類或簇，使得在同一個類中的數(shù)據(jù)對象的差異性盡可能小，而處于不同類中的數(shù)據(jù)對象的差異性盡可能的大。即可將聚類定義為：若數(shù)據(jù)集中有個數(shù)據(jù)點(diǎn)，其中，聚類的最終目的就是把數(shù)據(jù)集分為個類，使得(其中，為噪聲)且()。需要說明的是，在模糊聚類中，每個數(shù)據(jù)點(diǎn)可能會屬于多個類，因此類間可能會存在交集。

K-means算法是聚類算法中使用最為廣泛的算法之一，其用到的數(shù)學(xué)思想簡單，但效率高，且在對“圓形-球形”性質(zhì)集合進(jìn)行分類時，可以達(dá)到良好的聚類結(jié)果。傳統(tǒng)K-means算法的執(zhí)行過程如下所述[13]：

3) 根據(jù)前一步的結(jié)果，計算同一個類中所有樣本點(diǎn)的各維平均值，作為新一輪聚類的個中心；

4) 再重復(fù)上述過程繼續(xù)聚類，直至收斂。

簡單地說，K-means聚類的目的，就是使得式(1)最小化：

其中，

(2)

K-means算法簡單高效，但其缺點(diǎn)也十分明顯。首先，聚類的數(shù)目依賴于值設(shè)定，而在實(shí)際中，值一般是難以界定的，而值的指定決定了聚類的結(jié)果。其次，初始聚類中心是隨機(jī)選擇的，使得最終的聚類結(jié)果依賴于初始中心點(diǎn)的選擇，導(dǎo)致結(jié)果的不穩(wěn)定性[14]。同時，在標(biāo)準(zhǔn)K-means算法中，許多距離計算是冗余的，因此當(dāng)計算量很大時，算法的時間開銷也非常大。

Canopy[15]算法也是一種聚類方法，主要用于海量高維數(shù)據(jù)的聚類。Canopy可以粗略地將數(shù)據(jù)劃分成若干個重疊子集，即Canopy(罩蓋)。每個子集作為一個類簇，其一般使用一種代價低的相似性度量方法，以加快聚類的速度[16]。因此，Canopy聚類一般用于其他聚類算法的初始化操作。Canopy算法中，Canopy(罩蓋)的形成需要指定兩個距離閾值，、(>)。首先，在數(shù)據(jù)集中選擇一個點(diǎn)作為初始中心點(diǎn)加入到Canopy(罩蓋)中心列表中。對數(shù)據(jù)集中任意一個點(diǎn)()，若與()的距離均大于，則將作為一個新的Canopy(罩蓋)中心加入到中；若距離小于，則將加入以為中心的罩蓋中；若與的距離小于，將與強(qiáng)關(guān)聯(lián)，不再能作為其他罩蓋的中心，因此將其從數(shù)據(jù)集中刪去；反復(fù)以上過程，直至數(shù)據(jù)集為空[17]。Canopy聚類允許有重疊子集，增加了算法的容錯性和消除孤立點(diǎn)作用；同時，由于只需在罩蓋內(nèi)進(jìn)行精確聚類，從而避免了對所有點(diǎn)精確聚類帶來的計算量大的問題。

2 改進(jìn)的Canopy-K-means算法

2.1 算法思想

傳統(tǒng)的K-means算法由于初始聚類中心選擇的隨機(jī)性，算法結(jié)果隨著中心點(diǎn)選擇的不同而改變，導(dǎo)致結(jié)果的不穩(wěn)定性，可能會造成局部最優(yōu)值的問題[18]。針對中心點(diǎn)選擇的問題，將Canopy算法作為傳統(tǒng)K-means算法的初始化操作，快速地找出相對準(zhǔn)確的聚類中心。本文將每一次Canopy形成的重疊子集稱為罩蓋，而每次K-means聚類形成的不重疊子集稱為簇。在Canopy算法初始化過程中生成的重疊罩蓋，使得數(shù)據(jù)集中的每一個點(diǎn)都至少屬于一個罩蓋中，因此，在進(jìn)行K-means聚類的過程中，本文算法將不再考慮每個點(diǎn)到所有中心的距離，而只需計算點(diǎn)到其所屬罩蓋中心的距離，簡而言之，K-means算法將在每個罩蓋中進(jìn)行，而隨著K-means算法的迭代，每個罩蓋中心也將不斷變化，直至收斂。具體執(zhí)行流程如圖2所示。

由圖2可知，改進(jìn)后的Canopy-K-means算法首先通過Canopy算法形成相互重疊的罩蓋，再進(jìn)行K-means迭代，最后產(chǎn)出聚類結(jié)果。具體分為6步：

2) 數(shù)據(jù)點(diǎn)劃分。在生成Canopy之后，由于數(shù)據(jù)集中每個數(shù)據(jù)點(diǎn)至少屬于一個Canopy(罩蓋)，而屬于不同罩蓋的點(diǎn)一定不屬于同一個簇。因此，在計算新中心前，每個點(diǎn)已經(jīng)明確屬于某一個或幾個罩蓋中，從而不需要再計算每個點(diǎn)與每個中心點(diǎn)的距離，而只需計算其和其所屬罩蓋中心點(diǎn)的距離，并將其歸入到其距離最近的罩蓋中心點(diǎn)所屬的Canopy(罩蓋)中，形成相互不重疊的簇，減少了計算量。即對于任意點(diǎn)，假設(shè)是其所屬Canopy中心集合，若與其所屬的某一個Canopy的中心點(diǎn)距離最小，則將劃到所屬的Canopy中，并將其從其他Canopy中刪除。

3) 計算K-means中心。利用上一步生成的簇，計算每個簇的新中心點(diǎn)，即求平均的標(biāo)準(zhǔn)K-means算法。

4) 合并K-means中心。由于前期采用了Canopy算法生成初始中心，而初始半徑主要靠人工確定，如果初始半徑選擇過小，可能會出現(xiàn)中心點(diǎn)較多，或是在進(jìn)行K-means聚類之后，新的中心點(diǎn)比較靠近的情況，因此在新中心點(diǎn)產(chǎn)生之后，對新中心進(jìn)行檢查，將距離較近的中心點(diǎn)進(jìn)行合并，其對應(yīng)所處的簇也相應(yīng)合并，并計算合并后的新中心，從而產(chǎn)生一次迭代的最終K中心點(diǎn)，以避免人工確定半徑帶來的聚類效果不穩(wěn)定的問題。

5) 形成新簇，產(chǎn)生新的重疊罩蓋，并迭代。計算合并后K中心落在上一步產(chǎn)生的哪些Canopy(罩蓋)中，將這些Canopy(罩蓋)的中心點(diǎn)替換為新的K中心，形成新的重疊Canopy(罩蓋)。該步驟和步驟4)就是合并產(chǎn)生新Canopy的過程。從步驟2)開始，重復(fù)以上步驟，直至算法收斂。

6) 形成聚類結(jié)果。在迭代結(jié)束之后，得到最終的罩蓋，由于算法已經(jīng)收斂，此時，只需將屬于多個罩蓋中的點(diǎn)歸入到其距離最近的中心點(diǎn)所在Canopy(罩蓋)中，形成不重疊的最終簇，完成聚類。

2.2 基于MapReduce改進(jìn)的Canopy-K-means算法的并行化設(shè)計

由上面的分析可知，本算法主要由3個階段組成，即Canopy初始化階段、K-means迭代聚類階段，以及聚類結(jié)果產(chǎn)生階段。

1) Canopy初始化階段

在基于MapReduce的并行化算法中，Canopy初始化階段有分為兩個步驟：Canopy中心點(diǎn)的產(chǎn)生和Canopy的形成，分別對應(yīng)于兩個Job，分別為Job1和Job2，兩個Job的執(zhí)行流程及Map和Reduce過程實(shí)現(xiàn)如圖3所示。

Job1中Map函數(shù)產(chǎn)生局部數(shù)據(jù)集的Canopy中心，Reduce階段收集局部中心點(diǎn)，并執(zhí)行與Map階段同樣的操作，合并局部中心點(diǎn)集，最后得到全局中心點(diǎn)集，并以形式存放在本地，MapReduce過程可表示為：

Map：

Job2在Map階段，每個Map節(jié)點(diǎn)加載Job1產(chǎn)生的全局Canopy中心，遍歷子集中的所有數(shù)據(jù)點(diǎn)，判斷其與Canopy中心的距離，將其加入與其距離小于1的Canopy，Reduce階段負(fù)責(zé)整理各個Map產(chǎn)生的結(jié)果，產(chǎn)生Canopy，以<數(shù)據(jù)ID：數(shù)據(jù)各維值，所屬Canopy列表(Canopy中心各維值)>的key-value對形式存儲，MapReduce過程可表示為：

Map：

Reduce：

2) K-means迭代聚類階段

在K-means迭代聚類階段，在MapReduce框架下可以分為兩個步驟：第一步是利用Canopy中每個點(diǎn)各維度的值，重新計算每個Canopy中心；第二步合并鄰近的新中心，并判斷其屬于哪個Canopy，將屬于該Canopy的點(diǎn)的中心替換成為新的合并后的中心值，形成新的重疊Canopy。因此這一階段也是通過兩個Job完成，分別對應(yīng)于Job3和Job4，兩個Job的執(zhí)行流程及Map和Reduce過程實(shí)現(xiàn)如圖4所示。

Job3中的Map函數(shù)接收J(rèn)ob2產(chǎn)生的<數(shù)據(jù)ID：數(shù)據(jù)各維值，所屬Canopy列表(Canopy中心各維值)>key-value對，計算與每個點(diǎn)距離最近的Canopy中心，將其加入該Canopy中，形成<簇，數(shù)據(jù)ID：數(shù)據(jù)各維值>；Map函數(shù)的輸出在本地通過Combine函數(shù)，實(shí)現(xiàn)同一簇數(shù)據(jù)對象的合并，并統(tǒng)計數(shù)據(jù)的個數(shù)，得到<簇，數(shù)據(jù)點(diǎn)各維和+數(shù)據(jù)個數(shù)>，由于只能輸出key-value對的形式，在實(shí)現(xiàn)中，將數(shù)據(jù)個數(shù)作為各維度和的最后一位加入到value中；Reduce函數(shù)接收個Combine函數(shù)的輸出，進(jìn)行匯總，得到各個簇的所有點(diǎn)各維度之和以及各簇的數(shù)據(jù)點(diǎn)總數(shù)，最終得到每個簇的新中心K，輸出<簇，新K中心各維值>；這里Combine函數(shù)的設(shè)計，有效地完成了局部數(shù)據(jù)的統(tǒng)計，減少了節(jié)點(diǎn)間的通信代價。

Job3的MapReduce過程可表示為：

Map：

Combine：

Reduce：

Job4接收J(rèn)ob3的輸出，首先在各個Map節(jié)點(diǎn)的初始化(Setup)階段，檢查是否有需要合并的K中心，如果有，將其進(jìn)行合并，合并后產(chǎn)生得到的新中心，判斷其屬于那些Canopy中，得到合并后的K中心與原初始的Canopy的對應(yīng)關(guān)系，判斷其是否收斂。在Map階段，將所有數(shù)據(jù)點(diǎn)的所屬的Canopy列表中心替換為合并后的新中心，之后Reduce函數(shù)進(jìn)行匯總，最終形成形如<數(shù)據(jù)ID：數(shù)據(jù)各維值，所屬Canopy列表(合并后的Canopy新中心各維值)>。在Setup時進(jìn)行的收斂判斷中，若收斂，則在Map完成之后直接進(jìn)入Job5以產(chǎn)生最后結(jié)果，若不收斂，則從Job3開始循環(huán)直至收斂。

Job4的MapReduce過程可表示為：

Map：

3) 聚類結(jié)果產(chǎn)生階段

聚類結(jié)果產(chǎn)生階段對應(yīng)于Job5，接收J(rèn)ob4中產(chǎn)生的各個數(shù)據(jù)點(diǎn)與一個或多個穩(wěn)定的K中心對應(yīng)關(guān)系，在Map階段將局部數(shù)據(jù)點(diǎn)歸到與其距離最近的K中心，輸出<數(shù)據(jù)ID：數(shù)據(jù)各維值，所屬簇(最終K中心各維)>，完成聚類，該過程與Job3的map過程類似。

3 改進(jìn)后Canopy-K-means算法的文本聚類

3.1 文本預(yù)處理

利用本文提出的改進(jìn)Canopy-K-means算法進(jìn)行文本聚類，采用文本向量空間模型VSM對文本進(jìn)行預(yù)處理。即給定文本集，表示每個文本向量，且。其中表示從所有文本中提取的特征詞集合，表示文本中包含各個特征詞所對應(yīng)的權(quán)重。向量權(quán)重的計算采用統(tǒng)計方法TF-IDF(term frequency-inverse document frequency)[3]來計算：

3.2 文本距離計算

本文算法使用兩個點(diǎn)之間的距離作為衡量兩個點(diǎn)是否相似的標(biāo)準(zhǔn)。而在文本聚類中通常是使用兩個文本向量間夾角的余弦值，即余弦相似度，來衡量兩個文檔的相似程度。而由于兩個文本之間，向量夾角余弦值越大，相似度越大，說明其距離越小，也就是相似度和距離成反比，因此構(gòu)造式(4)來定義兩個文本、之間的距離。

式中，

(5)

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及預(yù)處理

實(shí)驗(yàn)采用UCI Machine Learning Repository[20]機(jī)器學(xué)習(xí)數(shù)據(jù)集中的Iris和Wine數(shù)據(jù)集，其中，Iris數(shù)據(jù)集共有150個樣本，每個樣本4個屬性，共分為3類；Wine數(shù)據(jù)集共178個樣本，每個樣本13個屬性，分為3類。文本聚類方面，選用搜狗實(shí)驗(yàn)室文本分類語料庫[21]中選取財經(jīng)、體育、旅游、教育4個類別的中文新聞文檔各1 000篇。另外，為了對算法的擴(kuò)展性進(jìn)行驗(yàn)證，將Iris數(shù)據(jù)集構(gòu)造成維度60維，行數(shù)為100萬行(0.25 G)、300萬行(0.6 G)、500萬行(1.1 G)、900萬行(2 G)的更大規(guī)模數(shù)據(jù)集。

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)在由4臺Ubuntu14.04平臺下搭建的Hadoop集群下完成，由1臺作為namenode，3臺作為datanode，其配置均為2 GB內(nèi)存，80 G硬盤，Hadoop版本為1.2.1。

1) 算法準(zhǔn)確度

利用Iris數(shù)據(jù)集、wine數(shù)據(jù)集對算法聚類準(zhǔn)確性進(jìn)行檢驗(yàn)，實(shí)驗(yàn)一共進(jìn)行20次，結(jié)果為這20次的平均值。在傳統(tǒng)K-means過程中，由于每次選擇的初始中心不同，聚類效果不穩(wěn)定，迭代次數(shù)較多，而本文算法由于優(yōu)化了中心的選擇，因此結(jié)果十分穩(wěn)定。由表1可知，本文算法的正確率高于傳統(tǒng)K-means算法，而誤差平方和以及迭代次數(shù)比K-means算法更低，說明本文算法聚類結(jié)果的類內(nèi)相似度更高且收斂速度更快。

表1 數(shù)據(jù)集測試結(jié)果

在利用本文算法進(jìn)行文本聚類時，采用前文中提到的通過文本間余弦相似度來計算距離的方法來衡量文本間的距離，在不同的單詞提取率下比較本文算法與傳統(tǒng)K-means算法在文本聚類上的準(zhǔn)確率(precision)、召回率(recall)和度量值[22]，如表2所示。

可以看到，本文算法可以很好地應(yīng)用到文本聚類中。

表2 文本聚類測試結(jié)果

2) 算法擴(kuò)展性

為了分析算法在Hadoop框架下并行執(zhí)行的性能，需要計算算法執(zhí)行的加速比。對同一個計算任務(wù)，并行算法的加速比等于單機(jī)執(zhí)行時間除以并行執(zhí)行時間的值。加速比是用來衡量程序執(zhí)行并行化的重要指標(biāo)[13,15]。算法加速比曲線如圖4所示，由圖4可知，本文算法在并行化后有良好的加速比，并隨著數(shù)據(jù)集的增大效果更佳明顯。

5 結(jié)束語

本文以海量數(shù)據(jù)聚類為背景，改進(jìn)了原有傳統(tǒng)K-means算法，克服了其隨機(jī)選擇中心點(diǎn)帶來的結(jié)果不穩(wěn)定問題，提高了聚類結(jié)果的準(zhǔn)確性和穩(wěn)定性，減少了聚類次數(shù)；并利用MapReduce框架給出了算法的并行化設(shè)計。同時結(jié)合實(shí)際文本聚類應(yīng)用場景，給出了本算法在文本聚類方面的應(yīng)用。實(shí)驗(yàn)驗(yàn)證了本文算法具有良好的有效性和擴(kuò)展性。

[1] 孫吉貴, 劉杰, 趙連宇.聚類算法研究[J]. 軟件學(xué)報, 2008, 19(1): 48-61.

SUN Ji-gui, LIU Jie, ZHAO Lian-yu. Clustering algorithm research[J]. Journal of Software, 2008, 19(1): 48-61.

[2] JAIN A K, MURTY M N, FLYNN P J. Data clustering: a review[J]. ACM Computing Surveys (CSUR), 1999, 31(3): 264-323.

[3] 翟東海, 魚江, 高飛, 等. 最大距離法選取初始聚類中心的K-means文本聚類算法的研究[J]. 計算機(jī)應(yīng)用研究, 2014, 31(3): 713-715, 719.

ZHAI Dong-hai, YU Jiang, GAO Fei, et al. K-means text clustering algorithm based on centers selection according to maximum distance[J]. Application Research of Computers, 2014, 31(3): 713-715, 719.

[4] 趙慶. 基于Hadoop平臺下的Canopy-Kmeans高效算法[J]. 電子科技, 2014, 27(2): 29-31.

ZHAO Qing. Efficient algorithm of canopy-kmeans based on Hadoop platform[J]. Electronic Science and Technology, 2014, 27(2): 29-31.

[5] 張健沛, 楊悅, 楊靜, 等. 基于最優(yōu)劃分的K-Means初始聚類中心選取算法[J]. 系統(tǒng)仿真學(xué)報, 2009, 21(9): 2586-2589.

ZHANG Jian-pei, YANG Yue, YANG Jing, et al. Algorithm for initialization of K-means clustering center based on optimized-division[J]. Journal of System Simulation, 2009, 21(9): 2586-2589.

[6] 雷小峰, 謝昆青, 林帆, 等. 一種基于K-means局部最優(yōu)性的高效聚類算法[J]. 軟件學(xué)報, 2008, 19(7): 1683-1692.

LEI Xiao-feng, XIE Kun-qing, LIN Fan, et al. An efficient clustering algorithm based on local optimality of K-means[J]. Journal of Software, 2008, 19(7): 1683-1692.

[7] 邱榮太. 基于Canopy的K-means多核算法[J]. 微計算機(jī)信息, 2012(9): 486-487.

QIU Rong-tai. Canopy for K-means on multi-core[J]. Microcomputer Information, 2012(9): 486-487.

[8] 周世兵, 徐振源, 唐旭清. 新的K-均值算法最佳聚類數(shù)確定方法[J]. 計算機(jī)工程與應(yīng)用, 2010, 46(16): 27-31.

ZHOU Shi-bing, XU Zhen-yuan, TANG Xu-qing. New method for determining optimal number of clusters in K-means clustering algorithm[J]. Computer Engineering and Applications, 2010, 46 (16): 27-31.

[9] FREY B J, DUECK D. Clustering by passing message between data points[J]. Science, 2007, 315: 972-976.

[10] 陸嘉恒. Hadoop實(shí)戰(zhàn)[M]. 2版. 北京: 機(jī)械工業(yè)出版社, 2012.

LU Jia-heng. Hadoop in action[M]. 2nd ed. Beijing: China Machine Press, 2012.

[11] DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[12] 丁智, 林治. MapReduce編程模型、方法及應(yīng)用綜述[J]. 電腦知識與技術(shù), 2014, 10(30): 7060-7064.

DING Zhi, LIN Zhi. Review on MapReduce programming model, method and application[J]. Computer Knowledge and Technology, 2014, 10(30): 7060-7064.

[13] 陳愛平. 基于Hadoop的聚類算法并行化分析及應(yīng)用研究[D]. 成都: 電子科技大學(xué), 2012.

CHEN Ai-ping. The parallel analysis and application research on clustering algorithm based on Hadoop[D]. Chengdu: University of Electronic Science and Technology of China, 2012.

[14] 韓凌波, 王強(qiáng), 蔣正鋒, 等.一種改進(jìn)的K-Means初始聚類中心選取算法[J]. 計算機(jī)工程與應(yīng)用, 2010, 46(17): 150-152.

HAN Ling-bo, WANG Qiang, JIANG Zheng-feng, et al. Improved K-means initial clustering center selection algorithm[J]. Computer Engineering and Applications, 2010, 46(17): 150-152.

[15] ESTEVES K M, RONG C. Using Mahout for clustering Wikipedia's latest articles: a comparison between K-means and fuzzy c-means in the cloud[C]//Proceedings of the 2011 Third IEEE International Conference Science, Cloud Computing Technology and IEEE Computer Society. Washington, DC, USA: IEEE, 2011: 565-569.

[16] 余長俊, 張燃. 云環(huán)境下基于Canopy聚類的FCM算法研究[J]. 計算機(jī)科學(xué), 2014, 41(11A): 316-319.

YU Chang-jun, ZHANG Ran. Research of FCM algorithm based on canopy clustering algorithm under cloud environment[J]. Computer Science, 2014, 41(11A): 316-319.

[17] MCCALLUM A, NIGAM K, UNGAR I H. Efficient clustering of high-dimensional data sets with application to reference matching[C]//Proceedings of the Sixth ACM SIUKDD International Conference on Knowledge Discovery and Data Mining. [S.l.]: ACM, 2000: 169- 178.

[18] 樊寧. K均值聚類算法在銀行客戶細(xì)分中的研究[J]. 計算機(jī)仿真, 2011, 28(3): 369-372.

FAN Ning. Simulation study on commercial bank custermer segmentation on K-means clustering algorithm[J]. Computer Simulation, 2011, 28(3): 369-372.

[19] 張華平. 自然語言處理與信息檢索共享平臺[EB/OL]. [2015-03-30]. http://www.nlpir.org/.

ZHANG Hua-ping. Natural language processing and information retrieval sharing platform[EB/OL]. [2015- 03-30]. http://www.nlpir.org/.

[20] UCI. UCI Machine learning repository[DB/OL]. [2015-03- 30]. http://archive.ics.uci.edu/ml/.

[21] 搜狗.文本分類語料庫[DB/OL]. [2015-03-30]. http://www. sogou.com/labs/dl/c.html.

Sougou. Text classify lab data[DB/OL]. [2015-03-30]. http:// www.sogou.com/labs/dl/c.html.

[22] YANG Y. An evaluation of statistical approaches to text categorization[J]. Information Retrieval, 1999, 1(1-2): 69- 90.

編 輯 蔣 曉

The Parallel Implementation and Application of an Improved K-means Algorithm

LI Xiao-yu1, YU Li-ying1, LEI Hang1, and TANG Xue-fei1,2

(1.School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 610054; 2. Chengdu COMSYS Information Tech. Co., Ltd Chengdu 610054)

Following with the growth of massive data, clustering research, one of the core problems of big dataisfaced with more and more problems such as high computing complexity and lack of resource. It has proposed an improved parallel K-means algorithm based on Hadoop. To overcomethe problem that the traditional K-means algorithm often has local optimal solution due to the randomness choice of initial center, we introduce Canopy algorithm to initialize clustering center andapply K-means algorithm on canopy. Meanwhile, clusters are merged among canopies. The result is stable and iteration number is less. In addition, the parallel implementation methods and strategies of the improved algorithm are presented, combining with the distributed computing model of MapReduce. And a new method of text clustering is introduced by improving the similarity of measurement. The experiment results indicate the validity and scalability of our method.

canopy algorithm; Hadoop; MapReduce; parallel K-means; text clustering

TP311

A

10.3969/j.issn.1001-0548.2017.01.010

2015-06-03；

2015-12-09

國家科技支撐計劃(2012BAH87F03)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(ZYGX2014J065)

李曉瑜(1984-)，女，博士，主要從事大數(shù)據(jù)分析與應(yīng)用、量子計算和量子信息等方面的研究.