王全民，胡德程

(北京工業(yè)大學(xué)信息學(xué)部，北京100022)

1 引言

K-means[1]算法(K-means algorithm)是一種無監(jiān)督聚類算法，主要是解決無標(biāo)簽數(shù)據(jù)聚類問題。如信息檢索、文本挖掘等各個(gè)領(lǐng)域都有廣泛應(yīng)用。隨著信息時(shí)代的到來，各領(lǐng)域的數(shù)據(jù)在速度、體積以及多樣性都急劇上升，普通的數(shù)據(jù)規(guī)模達(dá)到了TB級(jí)甚至PB級(jí)。在海量數(shù)據(jù)背景下，對(duì)K-means算法性能要求也越來越高，故傳統(tǒng)K-means算法越來越難適應(yīng)海量數(shù)據(jù)。針對(duì)標(biāo)準(zhǔn)K-means算法依賴初始K個(gè)質(zhì)心點(diǎn)，若選擇的初始中心點(diǎn)不恰當(dāng)以及更新中心點(diǎn)的冗余計(jì)算，往往會(huì)得到不理想的全局最優(yōu)中心點(diǎn)和執(zhí)行效率。

如何優(yōu)化初始聚類中心點(diǎn)[2]的選擇，提升K均值法的收斂速度和準(zhǔn)確率是本文的主要研究方向。文獻(xiàn)[3]通過將粒子群優(yōu)化PSO與K均值法結(jié)合，采用PSO來得到初始聚類質(zhì)心，以此提高K均值法的全局搜索能力。文獻(xiàn)[4]利用近鄰圖來完成K-means算法的初始中心點(diǎn)的選擇，避免隨機(jī)選擇初始點(diǎn)而帶來的局部最優(yōu)解問題。文獻(xiàn)[5]利用hash抽樣函數(shù)和MapReduce[6]計(jì)算框架來處理數(shù)據(jù)聚類，提高K均值算法的執(zhí)行效率。本文使用最大距離算法優(yōu)化初始中心點(diǎn)的選取，采用形態(tài)學(xué)相似距離提高準(zhǔn)確率，網(wǎng)格空間減少冗余計(jì)算。

本文在Spark[7]并行計(jì)算框架下對(duì)K-means算法進(jìn)行優(yōu)化和實(shí)現(xiàn)，提高對(duì)海量數(shù)據(jù)的處理能力。采用的數(shù)據(jù)集是UCI網(wǎng)站上的glass，abalone，Aggregation，實(shí)現(xiàn)SMGK-means算法來驗(yàn)證其準(zhǔn)確性，有效性以及加速性。

2 相關(guān)研究

2.1 Spark計(jì)算框架

本文選擇Spark實(shí)現(xiàn)SMGK-means算法而非MapReduce即MR[8]，主要是Spark擴(kuò)展了MR計(jì)算模型，具有MR的優(yōu)點(diǎn)；與MR相比SparkJob[9]計(jì)算的中間結(jié)果RDD[10]可保存在節(jié)點(diǎn)內(nèi)存中，無需從HDFS或者磁盤上讀取數(shù)據(jù)，故Spark能很好地適用于迭代式的MR算法。Spark的系統(tǒng)架構(gòu)如圖1所示。

圖1 Spark并行框架結(jié)構(gòu)

Spark處理數(shù)據(jù)比MR快的原因如下。首先，Spark是基于內(nèi)存迭代式計(jì)算；其次，Spark的數(shù)據(jù)結(jié)構(gòu)是分布式數(shù)據(jù)集RDD[10](Resilient Distributed Dataset)，RDD將數(shù)據(jù)存儲(chǔ)在節(jié)點(diǎn)executor內(nèi)存中，通過劃分分區(qū)優(yōu)化數(shù)據(jù)分布。最后，Spark的DAG計(jì)算模型和惰性求值。Spark的算子操作分為兩種即Transformation和Action，調(diào)用Transformation操作時(shí)如Map，flatMap，并不會(huì)立即執(zhí)行，而在內(nèi)部記錄操作，形成DAG計(jì)算模型，當(dāng)遇到Action操作時(shí)，會(huì)立即執(zhí)行相應(yīng)的Transformation操作。Spark Job的邏輯執(zhí)行如圖2所示。

圖2 Spark Job的邏輯執(zhí)行圖

2.2 K-means算法

傳統(tǒng)K均值法是無監(jiān)督聚類算法，輸入樣本中只有特征而沒有標(biāo)簽，從待聚類的原始Dataset中隨機(jī)選取K個(gè)數(shù)據(jù)點(diǎn)作為初始聚類質(zhì)心，隨后按照特定的度量標(biāo)準(zhǔn)計(jì)算非質(zhì)心點(diǎn)到聚類質(zhì)心的距離，進(jìn)行聚類劃分。最后計(jì)算每個(gè)聚類的數(shù)據(jù)點(diǎn)到質(zhì)心的平均距離，并依此調(diào)整質(zhì)心，經(jīng)過多次迭代計(jì)算，每個(gè)類簇中的樣本點(diǎn)相似度較高，類簇間的相似度較低。

傳統(tǒng)K-means算法過程如下：

輸入：待聚類初始Dataset，聚類中心的初始質(zhì)心個(gè)數(shù)K。

輸出：聚類結(jié)果即K個(gè)類簇。

具體的算法步驟：

步驟1：從待聚類的初始Dataset中隨機(jī)選擇K個(gè)樣本點(diǎn)作為初始聚類質(zhì)心。

步驟2：計(jì)算非中心點(diǎn)到聚類中心的距離，將其分配到與自己最近的中心點(diǎn)。

步驟3：當(dāng)所有點(diǎn)都?xì)w類完畢后，調(diào)整中心點(diǎn)：把中心點(diǎn)重新設(shè)置成該類別中所有數(shù)據(jù)點(diǎn)的中心位置，將每個(gè)類簇中的距離平均值作為新的聚類質(zhì)心。

步驟4：根據(jù)每個(gè)非中心點(diǎn)到質(zhì)心點(diǎn)的相似度(這里指距離越短相似度越大)對(duì)數(shù)據(jù)集進(jìn)行重新聚類。

步驟5：重復(fù)步驟3，步驟4，直到類簇不再變化，或者達(dá)到設(shè)定的迭代次數(shù)即可結(jié)束算法。

傳統(tǒng)K-means算法的主要缺點(diǎn)：時(shí)間復(fù)雜度為O(nkm)，其中n為原始數(shù)據(jù)集的個(gè)數(shù)，K為聚類中心個(gè)數(shù)，m為迭代次數(shù)。傳統(tǒng)K-means算法時(shí)間復(fù)雜度高，隨迭代次數(shù)m、類簇?cái)?shù)k值、初始數(shù)據(jù)集的增加而增大，因此傳統(tǒng)K-means算法在處理海量數(shù)據(jù)時(shí)綜合性能較低。另外K均值算法過于依賴初始聚類中心點(diǎn)的選取，選擇不同的初始聚類中心點(diǎn)，其最后的聚類結(jié)果也相差較大。

2.3 K-means++算法

因?yàn)闃?biāo)準(zhǔn)的K-means分類結(jié)果會(huì)受到初始質(zhì)心點(diǎn)的選取而產(chǎn)生差異，因此提出對(duì)傳統(tǒng)K-means算法進(jìn)行優(yōu)化即K-means++算法，K-means++聚類算法主要是對(duì)初始質(zhì)心點(diǎn)的選取進(jìn)行改進(jìn)，主要優(yōu)化方法是初始的聚類質(zhì)心之間的距離要盡量大，這樣可以保證樣本點(diǎn)會(huì)盡可能的分配到聚類中心中。

K-means++算法雖然能增加聚類準(zhǔn)確率，但是沒有減少冗余計(jì)算，而且在選取初始中心點(diǎn)增加額外計(jì)算以及第n個(gè)聚類質(zhì)心的選擇依賴于前n個(gè)聚類質(zhì)心。

3 SMGK-means算法及在Spark上的并行化實(shí)現(xiàn)

3.1 改進(jìn)K-means算法措施

通過形態(tài)學(xué)相似距離，最大距離距離準(zhǔn)則以及建立聚類中心與數(shù)據(jù)點(diǎn)的位置關(guān)系來優(yōu)化標(biāo)準(zhǔn)K-means算法。

3.1.1 形態(tài)學(xué)相似距離MSD

相似度測量標(biāo)準(zhǔn)一般由明可夫斯基距離推導(dǎo)出，主要應(yīng)用有歐氏距離，曼哈頓距離。

定義1：明可夫斯基距離

(1)

其中(1)式中：Yqi為向量q的第i個(gè)屬性值，Xji是向量j的第i個(gè)屬性值，m為向量維度，|Xji-Yqi|表示點(diǎn)與點(diǎn)再屬性i上的距離。當(dāng)p=2時(shí)，表示歐氏距離；p=1時(shí)表示曼哈頓距離。

定義2：形態(tài)學(xué)相似距離MSD(morphological similarity distance)

DMSD=(2-ASD/SAD)×ED

(2)

(3)

其中(2)式中：SAD表示曼哈頓距離，ED表示歐氏距離。(3)式表示兩個(gè)向量屬性差值之和的絕對(duì)值，Xji是向量j的第i個(gè)屬性值，Yqi為向量q的第i個(gè)屬性值m表示特征維度。表1表示了向量間的距離計(jì)算示例。

表1 向量間的距離計(jì)算

可以看出，若SAD/ASD=1，即ASD距離等于曼哈頓距離時(shí)，MSD距離就是歐式距離。

3.1.2 最大距離準(zhǔn)則選擇初始質(zhì)心點(diǎn)

Max-distinece算法是由最大最小距離算法改進(jìn)而來，根據(jù)其最大距離原則選取初始的聚類質(zhì)心。

算法過程如下：

步驟1：從數(shù)據(jù)集中任意選取靠近邊界點(diǎn)(不是邊界點(diǎn))，作為聚類質(zhì)心C1，同時(shí)記C為聚類中心集合

步驟2：選擇聚類質(zhì)心C1最遠(yuǎn)的數(shù)據(jù)點(diǎn)作為第2個(gè)聚類質(zhì)心C2；

步驟3：計(jì)算其它數(shù)據(jù)點(diǎn)與C1，C2之間的距離，并且計(jì)算出它們中的最小值，即式(1)、(2)

dxy=‖nx-ny‖，y=1，2

(4)

dx=min[dx1，dx2]，x=1，2，…n

(5)

步驟4：如果(θ為規(guī)定的參數(shù))

dl=maxx[min[dx1，dx2] ]>θ*‖n1-n2‖

(6)

則相應(yīng)的樣本nl作為第3個(gè)聚類中心C3，然后繼續(xù)判斷next聚類質(zhì)心；

步驟5：如果存在k(k！=K)個(gè)聚類中心，計(jì)算各個(gè)樣本點(diǎn)到聚類質(zhì)心的距離dxy，并計(jì)算出：

dl=maxx[min[dxy，dxz] ]>θ*‖ny-nz‖

(7)

其中y！=z且y，z∈C

步驟6：已經(jīng)求出K個(gè)初始聚類中心點(diǎn)，將其保存記為C

3.1.3 數(shù)據(jù)集的空間位置信息減少冗余計(jì)算

為減少K-means算法冗余計(jì)算量，引入數(shù)據(jù)點(diǎn)與聚類中心的空間位置關(guān)系[11]，基本做法是，對(duì)于初始數(shù)據(jù)集中的任意點(diǎn)，若能知道它與K個(gè)類簇質(zhì)心的空間位置關(guān)系，就可能判斷出離它最近的聚類質(zhì)心是哪一個(gè)，這樣就無需執(zhí)行k次計(jì)算，只需將數(shù)據(jù)點(diǎn)分配到相應(yīng)的類簇中去。

如何建立數(shù)據(jù)集與聚類中心的空間位置信息，以三維數(shù)據(jù)為例，對(duì)于一個(gè)在空間直角坐標(biāo)系任意數(shù)據(jù)點(diǎn)s(x，y，z)，假設(shè)x所在維度最大值為maxx，最小值為minx，網(wǎng)格在這一維上所劃的分段數(shù)為xNum。假設(shè)y所在維度最大值為maxy，最小值為miny，網(wǎng)格在這一維上所劃的分段數(shù)為yNum。假設(shè)z所在維度最大值為maxz，最小值為minz，網(wǎng)格在這一維上所劃的分段數(shù)為zNum。根據(jù)數(shù)據(jù)集中點(diǎn)的坐標(biāo)，可以按照式(8)，(9)，(10)快速定位點(diǎn)s的網(wǎng)格位置(x′，y′，z′)

(8)

(9)

(10)

其中α為正的小數(shù)。

由上述數(shù)據(jù)點(diǎn)s所在網(wǎng)格與k個(gè)聚類質(zhì)心的關(guān)系即可確定點(diǎn)s與類簇的關(guān)系，即點(diǎn)s所可能歸屬的聚類質(zhì)心有哪些。那么就可以有效地減少點(diǎn)s與聚類質(zhì)心之間的計(jì)算量。

3.2 肘部法則確定K值

對(duì)于肘部法則[12]確定類簇個(gè)數(shù)K而言，其中誤差平方和SSE和距離度量標(biāo)準(zhǔn)如下

(11)

其中x，y表示不同的兩個(gè)樣本，n表示樣本的維度即特征數(shù)量

(12)

針對(duì)大規(guī)模數(shù)據(jù)可以利用肘部法則來確定類簇?cái)?shù)K。肘部法則的計(jì)算思想是代價(jià)函數(shù)，代價(jià)函數(shù)是取類簇?cái)?shù)為k時(shí)所求的SSE，若類簇內(nèi)部的數(shù)據(jù)點(diǎn)之間越緊湊則SSE越小，反之，若內(nèi)部的數(shù)據(jù)點(diǎn)之間越分散則SSE越大。在選擇類簇個(gè)數(shù)而言，肘部法則會(huì)把不同k值聚類所得到的SSE畫成關(guān)系圖。隨著k值的增大，SSE值就會(huì)越來越小，每個(gè)類簇中所包含的樣本數(shù)會(huì)減少，數(shù)據(jù)點(diǎn)離其聚類質(zhì)心會(huì)更近。但是，隨著k值的增加，誤差平方和SSE值下降的幅度就會(huì)變得緩慢。在k值上升過程中，SSE下降幅度最快位置所對(duì)應(yīng)的值就是肘部。

3.3 算法改進(jìn)步驟

在上述2.2節(jié)和2.3節(jié)中分析了K均值法和K-means++的主要缺點(diǎn)，下面對(duì)如何選擇初始中心點(diǎn)，減少冗余計(jì)算量以及并行化提出了解決辦法。首先此文中的測量距離據(jù)使用形態(tài)學(xué)相似距離MSD。優(yōu)化算法的步驟如下：設(shè)原始數(shù)據(jù)集Dataset={x1，x2，x3，…，xn}，并且xi屬于Rd，其中n為原始數(shù)據(jù)集的個(gè)數(shù)，xi表示為d維向量。先預(yù)設(shè)K值范圍如[n1，n2]，依此取n1與n2之間的整數(shù)K；對(duì)于所取的每一個(gè)K值，首先根據(jù)Max-distance距離算法選擇K個(gè)初始中心點(diǎn)；然后利用數(shù)據(jù)點(diǎn)與K個(gè)類簇中心的位置關(guān)系將數(shù)據(jù)點(diǎn)歸屬到與其最近的中心中，其次更新K個(gè)類簇中心和網(wǎng)格空間信息，重復(fù)此過程，直到簇類中心不再變化或者達(dá)到規(guī)定的迭代次數(shù)；最后處理得到對(duì)應(yīng)K值的SSE，然后在直角坐標(biāo)系中繪制K-SSE關(guān)系圖，此圖類似于手肘的形狀，此時(shí)這個(gè)拐點(diǎn)所對(duì)應(yīng)的k值就是數(shù)據(jù)集的實(shí)際聚類數(shù)即最優(yōu)K值。

3.4 基于Spark的SMGK-means算法的并行實(shí)現(xiàn)

為了能有效地提高K-means算法的并行計(jì)算能力，本文提出了基于Spark的SMGK-means算法，主要是圍繞ShuffleMapTask和ResultTask兩個(gè)任務(wù)進(jìn)行的。算法流程圖如圖3所示。

圖3 基于Spark的SMGK-means算法

在每次迭代計(jì)算過程中，先對(duì)每個(gè)RDD分區(qū)進(jìn)行mapPartitions操作，mapPartitions與map操作不同，是針對(duì)RDD中每個(gè)分區(qū)的迭代器，每次處理分區(qū)中的所有數(shù)據(jù)，且執(zhí)行一次，提高了計(jì)算效率。之后對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類。通過數(shù)據(jù)坐標(biāo)得到的對(duì)應(yīng)網(wǎng)格，利用類簇和網(wǎng)格的關(guān)系確定數(shù)據(jù)點(diǎn)可能歸屬的類簇，最后從可能的聚類質(zhì)心中查找最近的類簇，以此來減少冗余的計(jì)算。將所有點(diǎn)分配完成后，再將不同executor中的簇類中心進(jìn)行reduceByKey操作匯總，得到新的K個(gè)聚類質(zhì)心，同時(shí)對(duì)網(wǎng)格和類簇的空間關(guān)系進(jìn)行更新。迭代結(jié)束后，通過肘部法則來確定最終的k值和類簇結(jié)果。

SMGK-means算法流程大致可以劃分為以下數(shù)據(jù)分區(qū)，聚合和驗(yàn)證三個(gè)階段。其算法代碼如圖4所示。

圖4 程序代碼

改進(jìn)策略的要點(diǎn)如下：先使用MSD替換傳統(tǒng)的距離度量如歐式距離，然后利用最大距離準(zhǔn)則選擇最優(yōu)的初始中心點(diǎn)，提高K-means算法的全局搜索能力。其次使用網(wǎng)格結(jié)構(gòu)保存數(shù)據(jù)點(diǎn)與聚類中心的空間位置關(guān)系，得到數(shù)據(jù)點(diǎn)所歸屬的可能類簇。最后利用Spark框架中的廣播變量，把K個(gè)中心點(diǎn)所組成的集合廣播到集群中每個(gè)節(jié)點(diǎn)的executor進(jìn)程中，然后進(jìn)行相應(yīng)的算子操作，從而減少數(shù)據(jù)點(diǎn)在節(jié)點(diǎn)中的移動(dòng)次數(shù)。通過以上改進(jìn)策略能很好得提高算法的效率和性能。

3.5 每個(gè)K值下SMGK-means算法時(shí)間復(fù)雜度分析

改進(jìn)的算法時(shí)間復(fù)雜度得到明顯的降低，如果合理的選擇網(wǎng)格劃分寬度，能在很大程度上保證絕大多數(shù)網(wǎng)格都只會(huì)屬于一個(gè)聚類中心，只有少量網(wǎng)格的可能歸屬類簇為兩個(gè)及以上。因此對(duì)于大多數(shù)的數(shù)據(jù)點(diǎn)都只需執(zhí)行一次距離計(jì)算，而非K次。若排除選取初始聚類質(zhì)心所消耗的時(shí)間，SMGK-means算法的時(shí)間復(fù)雜度為O(nm)，其中n為數(shù)據(jù)點(diǎn)個(gè)數(shù)，m為迭代次數(shù)。

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

本文基于Spark分布式集群實(shí)現(xiàn)SMGK-means算法，實(shí)驗(yàn)環(huán)境由五臺(tái)虛擬機(jī)組成，其中包括一臺(tái)master主節(jié)點(diǎn)，負(fù)責(zé)driver程序的運(yùn)行和管理，剩下四臺(tái)work從節(jié)點(diǎn)作為執(zhí)行節(jié)點(diǎn)。

硬件配置：每臺(tái)虛擬機(jī)CPU雙核1.8GHz，內(nèi)存2GB，磁盤容量20GB。操作系統(tǒng)是64位的Ubuntu16.04。

軟件配置：每臺(tái)虛擬機(jī)上裝有jdk1.8.0＿191，scala-2.11，hadoop-2.9.1，spark-2.4.3。采用具有面向?qū)ο箫L(fēng)格和函數(shù)式編程特性的Scala語言，同時(shí)為驗(yàn)證SMGK-means算法的有效性，采用Spark ML[13]中標(biāo)準(zhǔn)K-means算法、K-means++算法以及文獻(xiàn)[14]中算法作為對(duì)比試驗(yàn)。測試數(shù)據(jù)集為UCI數(shù)據(jù)集庫中的abalone，Aggregation，glass三種不同量級(jí)的數(shù)據(jù)樣本。為了方便驗(yàn)證實(shí)驗(yàn)，對(duì)相關(guān)數(shù)據(jù)集進(jìn)行預(yù)處理(刪除和增加相應(yīng)的數(shù)據(jù))，處理后數(shù)據(jù)集如表2所示。

表2 數(shù)據(jù)集

針對(duì)上述三種數(shù)據(jù)集，修改數(shù)據(jù)集中每條記錄的聚類中心，然后提取其中的特征另存為train.txt上傳到HDFS上，隨后模型讀取的數(shù)據(jù)就是HDFS上的train.txt。實(shí)驗(yàn)結(jié)束所保存的數(shù)據(jù)也在HDFS上。

1)算法運(yùn)行時(shí)間比較。本文利用執(zhí)行時(shí)間衡量SMGK-means算法執(zhí)行效率。圖5是上述四種算法在不同數(shù)據(jù)集的執(zhí)行時(shí)間，可以看到SMGK-means算法比另外三種算法減少了聚類時(shí)間。因?yàn)镾MGK-means算法采用網(wǎng)格表示數(shù)據(jù)點(diǎn)與聚類質(zhì)心的位置關(guān)系，降低聚類計(jì)算的次數(shù)，提升了收斂速度；同時(shí)利用spark中broadcast將每次更新的中心點(diǎn)廣播到各個(gè)執(zhí)行節(jié)點(diǎn)中，將作業(yè)粒度轉(zhuǎn)變成節(jié)點(diǎn)粒度，執(zhí)行節(jié)點(diǎn)每次從本地內(nèi)存中讀取聚類中心，節(jié)省執(zhí)行節(jié)點(diǎn)間的通信開銷。圖6比較并行環(huán)境下不同數(shù)據(jù)集在不同數(shù)量節(jié)點(diǎn)上使用SMGK-means算法的聚類時(shí)間，體現(xiàn)出隨節(jié)點(diǎn)worker的增加，SMGK-means算法的運(yùn)行時(shí)間逐漸減少，最后趨于平緩。平緩的原因是由于worker間的通信開銷抵消了并行化帶來的增益。

圖5 4個(gè)節(jié)點(diǎn)下各算法的運(yùn)行時(shí)間

圖6 不同節(jié)點(diǎn)個(gè)數(shù)SMGK-means算法所消耗的時(shí)間

2)準(zhǔn)確率對(duì)比。算法準(zhǔn)確率指類簇劃分正確記錄的個(gè)數(shù)與數(shù)據(jù)集中總記錄個(gè)數(shù)的比值。表3給出三種不同的數(shù)據(jù)集在五個(gè)節(jié)點(diǎn)下，SMGK-means算法與K-means、K-means++以及文獻(xiàn)14算法的準(zhǔn)確率。由表3可知本文的SMGK-means算法相比于其它三種算法準(zhǔn)確率有顯著的提高。因?yàn)镾MGK-means算法利用最大距離算法、網(wǎng)格空間結(jié)構(gòu)優(yōu)化了標(biāo)準(zhǔn)K-means算法，提高了全局搜索能力。

表3 SMGK-means與其它三種算法的準(zhǔn)確率

3)加速比的對(duì)比。算法加速比[15]是衡量程序性能、并行性能的重要指標(biāo)。其定義是同一個(gè)job在并行中與串行中執(zhí)行時(shí)間比值的倒數(shù)，計(jì)算公式為Rate=Js/Jp，其中Js為單機(jī)下的運(yùn)行時(shí)間，Jp為分布式集群下執(zhí)行時(shí)間，Rate越大表示算法在單機(jī)環(huán)境下執(zhí)行時(shí)間越大，在分布式集群下運(yùn)行時(shí)間越小。為驗(yàn)證SMGK-means算法并行性能，實(shí)驗(yàn)依然是基于上述三種不同量級(jí)的數(shù)據(jù)集，圖6給出三種不同數(shù)據(jù)集在不同節(jié)點(diǎn)個(gè)數(shù)下的運(yùn)行時(shí)間。得到SMGK-means算法加速比如圖7所示。從圖7橫向比較得到SMGK-means算法的加速比隨執(zhí)行節(jié)點(diǎn)個(gè)數(shù)增加而增加。但隨著節(jié)點(diǎn)個(gè)數(shù)的增加，其加速比趨于平緩，其原因是節(jié)點(diǎn)之間的通信開銷?？v向比較得在相同節(jié)點(diǎn)個(gè)數(shù)下，隨記錄個(gè)數(shù)的增加，其加速比也隨之增大。

圖7 基于SMGK-means的加速比

4)手肘法確定K值。上述1)2)3)的對(duì)比實(shí)驗(yàn)結(jié)果均是在K最優(yōu)情況下進(jìn)行的，而對(duì)于K值未知的數(shù)據(jù)集利用手肘法確定K值。先預(yù)測最優(yōu)K值范圍，每取K值執(zhí)行一次SMGK-means算法，即可得到類簇內(nèi)的數(shù)據(jù)點(diǎn)到其簇類中心的距離平方和SSE，并繪制K與SSE的關(guān)系圖；然后利用肘部法則確定K值和對(duì)應(yīng)的聚類結(jié)果。圖8表示數(shù)據(jù)集alalone的K與SSE的關(guān)系圖，由圖8可知，隨K值不斷逼近真實(shí)類簇?cái)?shù)時(shí)，SSE的下降趨勢加快，而當(dāng)設(shè)定的K值超過實(shí)際類簇?cái)?shù)時(shí)，SSE下降態(tài)勢會(huì)趨于緩慢。K-SSE的關(guān)系圖中的拐點(diǎn)即為最優(yōu)的K值，與表1數(shù)據(jù)集中alalone的類簇?cái)?shù)相同。

圖8 K與SSE的關(guān)系圖

綜合1)2)3)得到，SMGK-means算法與上述三種算法相比減少了執(zhí)行時(shí)間，且其準(zhǔn)確率平均提高了6.73%；從加速比上分析SMGK-means算法具有良好的并行計(jì)算性能；而對(duì)于無法提前確定K值的數(shù)據(jù)集利用肘部法則也能得到正確的聚類簇?cái)?shù)。故總體而言本文的SMGK-means算法相較于其它三種算法有了較大的提升。

5 結(jié)語

本文針對(duì)標(biāo)準(zhǔn)K-means算法的初始中心點(diǎn)選擇和冗余計(jì)算等問題，提出SMGK-means算法。此算法以MSD為相似度度量標(biāo)準(zhǔn)，利用最大距離算法優(yōu)化初始中心點(diǎn)選取，采用網(wǎng)格數(shù)據(jù)結(jié)構(gòu)保存數(shù)據(jù)點(diǎn)位置關(guān)系，減少冗余計(jì)算。通過手肘法確定最優(yōu)K值。實(shí)驗(yàn)表明SMGK-means算法顯著提高了聚類的準(zhǔn)確率，減少了執(zhí)行時(shí)間，且在分布式集群下有較高的性能。在下一步研究中，筆者準(zhǔn)備提高數(shù)據(jù)集和集群規(guī)模，以此驗(yàn)證SMMK-means算法的魯棒性。