劉 燕

(山西大學(xué) 商務(wù)學(xué)院， 太原 030031)

引言

聚類是將物理或抽象的對(duì)象分成相似對(duì)象集合的過(guò)程，簇是數(shù)據(jù)對(duì)象的集合，同一簇中的對(duì)象特征相似，而與其它簇中的對(duì)象卻彼此相異[1]。聚類分析在數(shù)據(jù)挖掘、模式識(shí)別、文本分析、圖形處理、市場(chǎng)研究等諸多領(lǐng)域應(yīng)用廣泛。作為一種獲得廣泛應(yīng)用的經(jīng)典聚類劃分算法，K-means算法具有算法數(shù)學(xué)思想清晰且易于實(shí)現(xiàn)、收斂速度快等優(yōu)勢(shì)[2]，但是需要事先指定初始聚類中心的個(gè)數(shù)k值，而且由于中心點(diǎn)選取的隨機(jī)性而容易陷入局部最優(yōu)解。

隨著數(shù)據(jù)庫(kù)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，生成的數(shù)據(jù)呈海量增長(zhǎng)，傳統(tǒng)的聚類算法很難滿足時(shí)下的數(shù)據(jù)分析處理需求。2004年，Google公司研發(fā)了一個(gè)稱為Hadoop的開(kāi)源MapReduce并行計(jì)算框架和系統(tǒng)，給大數(shù)據(jù)并行處理帶來(lái)了重大的影響，現(xiàn)已成為迄今為止易于使用、廣為接受的業(yè)界主流大數(shù)據(jù)并行處理技術(shù)。因此，許多學(xué)者運(yùn)用MapReduce模型陸續(xù)展開(kāi)了有關(guān)海量數(shù)據(jù)的聚類研究。江小平等人[3]提出了一種基于MapReduce的并行K-means聚類算法，該算法的執(zhí)行效率較高，但由于K-means算法在收斂前需要進(jìn)行多次迭代計(jì)算，不斷地重啟計(jì)算任務(wù)及讀取原始數(shù)據(jù)集，因此造成更多的I/O開(kāi)銷。毛典輝[4]提出的基于MapReduce的Canopy-Kmeans改進(jìn)算法，采用最大最小原則對(duì)該算法進(jìn)行改進(jìn)。虞倩倩等人[5]提出了基于MapReduce的ACO-Kmeans并行聚類算法，針對(duì)K-means聚類算法處理海量數(shù)據(jù)時(shí)存在的內(nèi)存不足等問(wèn)題，研究了利用MapReduce實(shí)現(xiàn)K-means聚類算法的并行化。

綜上這些算法很好地解決了傳統(tǒng)K-means算法處理海量數(shù)據(jù)的一些不足，但是仍存在聚類效果不穩(wěn)定、準(zhǔn)確率不高，也未能充分考慮算法執(zhí)行過(guò)程中的計(jì)算量以及通信代價(jià)等問(wèn)題。為此，本文擬基于MapReduce模型，采用抽樣技術(shù)和最大最小距離法，設(shè)計(jì)提出一種高效的并行K-means算法。通過(guò)在UCI標(biāo)準(zhǔn)數(shù)據(jù)集地行實(shí)驗(yàn)，最終結(jié)果表明該算法的收斂速度、聚類精度，以及在處理海量數(shù)據(jù)時(shí)的并行性能都得到了提高。

1 相關(guān)理論

1.1 傳統(tǒng)的K-means聚類算法

設(shè)數(shù)據(jù)集X={x1,x2,…,xn}，其中xi表示一個(gè)數(shù)據(jù)對(duì)象，通常采用歐式距離作為判斷2個(gè)數(shù)據(jù)對(duì)象之間相似性的依據(jù)。任意2個(gè)數(shù)據(jù)對(duì)象間的歐式距離為：

(1)

其中，m為數(shù)據(jù)集的屬性維數(shù)，xir，xjr為數(shù)據(jù)對(duì)象xi和xj的第r個(gè)屬性值。距離越小相似性越大，相反則相似性越小。

傳統(tǒng)K-means算法的設(shè)計(jì)流程可描述如下[6]。

(1)針對(duì)數(shù)據(jù)集X={x1,x2,…,xn}，指定聚類個(gè)數(shù)為k，并隨機(jī)選取k個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心{c1,c2,…,ck}。

(2)根據(jù)公式(1)計(jì)算每個(gè)數(shù)據(jù)對(duì)象xi到k個(gè)聚類中心的歐式距離，并把數(shù)據(jù)對(duì)象xi劃分到與之距離最近的聚類中心所屬的聚類中。

(3)計(jì)算每一個(gè)類簇中所有數(shù)據(jù)對(duì)象的平均值作為新的聚類中心。

(4)重復(fù)執(zhí)行步驟(2)和步驟(3)進(jìn)行下一輪聚類，直到各個(gè)聚類中心在某個(gè)精度范圍內(nèi)不再變化或者達(dá)到最大迭代次數(shù)為止，算法結(jié)束。

1.2 隨機(jī)抽樣

在統(tǒng)計(jì)學(xué)中，簡(jiǎn)單隨機(jī)采樣是各類抽樣方法的基礎(chǔ)，但在大規(guī)模的抽樣調(diào)查中卻很少被單獨(dú)采用，而在數(shù)據(jù)挖掘技術(shù)中，因其呈現(xiàn)的總體確定性，這一限制也隨即被消除。

由統(tǒng)計(jì)學(xué)的大數(shù)定律、中心極限定律、貝努利大數(shù)定律等可得到如下結(jié)論[7]，不論總體服從何種分布，只要其數(shù)學(xué)期望和方差存在，從中抽取容量為n的樣本，這個(gè)樣本的和或平均數(shù)將作為隨機(jī)變量，當(dāng)n充分大時(shí)，趨于正態(tài)分布，則可得隨機(jī)抽樣樣本容量n的數(shù)學(xué)公式為：

(2)

其中，N為數(shù)據(jù)集總量；t為概率度；δ為標(biāo)準(zhǔn)差；ε為誤差限制。通常，隨機(jī)采樣時(shí)采用置信度為0.95，概率度為1.96。

1.3 最大最小距離法

最大最小距離法以歐式距離為基礎(chǔ)，采取以最大距離原則選取新的聚類中心，以最小距離原則進(jìn)行模式歸類。因此避免了K-means算法初值選取時(shí)可能出現(xiàn)的聚類中心過(guò)于鄰近的情況[8]，而且可以智能確定初始聚類中心的個(gè)數(shù)，提高了劃分初始數(shù)據(jù)集的效率。算法運(yùn)行各步驟可詳述如下。

(1)有n個(gè)對(duì)象，Sn={X1,X2,…,Xn}。

(2)任取一個(gè)數(shù)據(jù)對(duì)象，例如X1，作為第一個(gè)聚類中心，然后找出集合Sn中到第一個(gè)聚類中心距離最遠(yuǎn)的數(shù)據(jù)對(duì)象作為第二個(gè)聚類中心。

(3)對(duì)Sn中剩余的其它數(shù)據(jù)對(duì)象Xi，分別計(jì)算到第一個(gè)、第二個(gè)聚類中心的距離，令其中較小的為DXi。

(4)計(jì)算maxSn={DXi}。若maxSn={DXi}>m×[average(|X2-X1|)]，則取Xi為新的聚類中心。通常取值為m∈[1/2，1)。

(5)重復(fù)執(zhí)行步驟(1)～(4)，直到不產(chǎn)生新的聚類中心為止。

2 基于抽樣和最大最小距離法的并行K-means聚類算法

本算法首先采用抽樣技術(shù)對(duì)原始數(shù)據(jù)集進(jìn)行多次隨機(jī)抽樣，以產(chǎn)生新的數(shù)據(jù)集；然后運(yùn)用MapReduce模型，2次采用最大最小距離法生成最佳的初始聚類中心；最后基于MapReduce模型利用K-means算法進(jìn)行迭代聚類。算法的執(zhí)行過(guò)程可表述如下。

輸入：原始數(shù)據(jù)集D和聚類數(shù)目k，采樣次數(shù)J

(1)計(jì)算原始數(shù)據(jù)集D的平均值和方差，并根據(jù)公式(2)確定抽樣樣本量。

(2)對(duì)原始數(shù)據(jù)集D進(jìn)行J次隨機(jī)抽樣。

(3)初始聚類中心運(yùn)算

① Map1階段：對(duì)每個(gè)抽樣樣本運(yùn)用最大最小距離法生成若干的初始聚類中心集合。

② Reduce1階段：將這些初始聚類中心集合匯總后再次運(yùn)用最大最小距離法，從而得到最佳的k個(gè)初始聚類中心。

(4)新的聚類中心運(yùn)算

① Map2階段：計(jì)算每個(gè)初始聚類中心的歐式距離并重新標(biāo)記所屬類別。

② Reduce2階段：依據(jù)中間結(jié)果再次計(jì)算新的聚類中心。

(5)經(jīng)過(guò)多次迭代計(jì)算，直至收斂，從而得到最終的聚類結(jié)果。

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

實(shí)驗(yàn)選用Hadoop集群平臺(tái)由一個(gè)master節(jié)點(diǎn)和9個(gè)slavers節(jié)點(diǎn)組成。實(shí)驗(yàn)運(yùn)用的數(shù)據(jù)集均來(lái)自UCI數(shù)據(jù)庫(kù)，各數(shù)據(jù)集信息可詳見(jiàn)表1。通過(guò)一系列實(shí)驗(yàn)，測(cè)試這些數(shù)據(jù)集在Hadoop集群環(huán)境下本文算法和基于MapReduce的K-means并行算法[3]的收斂速度、聚類精度及其并行性能。對(duì)此，將給出研究論述如下。

表1 實(shí)驗(yàn)數(shù)據(jù)集

(1)收斂速度的對(duì)比分析。研究中，為了保證仿真實(shí)驗(yàn)結(jié)果的客觀性，則將2種算法各重復(fù)運(yùn)行10次，測(cè)試每種算法的收斂速度，即各自完成聚類所需要的迭代次數(shù)，對(duì)比結(jié)果可見(jiàn)表2。

表2 收斂速度對(duì)比

從表2中可以看出，本文算法的聚類收斂速度與基于MapReduce的K-means并行算法相比要更快一些。究其原因就在于本文算法運(yùn)用了最大最小距離法對(duì)初值選取進(jìn)行了優(yōu)化，K-means聚類過(guò)程對(duì)初始聚類中心的依賴性有所減小，從而使得該算法聚類時(shí)所需要的迭代次數(shù)明顯減少，收斂速度加快。

(2)聚類精度的對(duì)比分析。聚類精度是指數(shù)據(jù)對(duì)象被置于正確的類簇中的數(shù)據(jù)個(gè)數(shù)與總的數(shù)據(jù)對(duì)象個(gè)數(shù)的比值。2種算法的聚類精度對(duì)比結(jié)果可見(jiàn)表3。從表3中可以看出，本文算法的聚類精度要高于基于MapReduce的K-means并行算法，這也說(shuō)明本文算法對(duì)含噪聲數(shù)據(jù)以及分布異常數(shù)據(jù)的處理能力有所提升，聚類質(zhì)量也更高。

表3 聚類精度對(duì)比

(3)并行性能的對(duì)比分析。加速比是同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間的比率，用來(lái)衡量并行系統(tǒng)或程序并行化的性能和效果[9]。計(jì)算公式為：

Sp=T1/Tp

(3)

其中，T1表示順序執(zhí)行算法(即單一PC機(jī))的執(zhí)行時(shí)間，Tp表示并行算法(即p個(gè)處理器)的執(zhí)行時(shí)間。加速比越大，說(shuō)明并行計(jì)算消耗的相對(duì)時(shí)間越少，并行效率越高。

通過(guò)對(duì)數(shù)據(jù)集1990 US Census Data擴(kuò)充為2倍、4倍、8倍不同大小的數(shù)據(jù)集，分別在不同節(jié)點(diǎn)數(shù)的Hadoop集群平臺(tái)下運(yùn)行本文算法，由此得出加速比的并行性能對(duì)比結(jié)果。

在Hadoop集群平臺(tái)下，本文算法的加速比則如圖1所示。可以看到，隨著節(jié)點(diǎn)數(shù)增加和數(shù)據(jù)量增大，加速比也呈現(xiàn)提升態(tài)勢(shì)。由此分析可得，在處理海量高維數(shù)據(jù)集時(shí)，單機(jī)由于內(nèi)存不足將無(wú)法運(yùn)行，而集群則能有效提高算法的計(jì)算效率，并行性能堪稱優(yōu)良。

圖1 Hadoop集群平臺(tái)的加速比

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)聚類算法處理海量數(shù)據(jù)的一些問(wèn)題與不足，本文將基于MapReduce模型，采用抽樣技術(shù)和最大最小距離法，設(shè)計(jì)提出一種高效的并行K-means算法。通過(guò)在UCI標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明該算法的收斂速度、聚類精度，以及在處理海量數(shù)據(jù)時(shí)的并行性能均在一定程度上獲得了提升。未來(lái)將會(huì)在更多的大數(shù)據(jù)集上展開(kāi)測(cè)試，包括高維數(shù)據(jù)，從而進(jìn)一步驗(yàn)證算法的性能并提供后續(xù)的改進(jìn)與完善。