劉 飛，唐雅娟，劉 瑤

（汕頭大學(xué) 電子工程系，廣東 汕頭515063）

K-means聚類算法中聚類個(gè)數(shù)的方法研究

劉 飛，唐雅娟，劉 瑤

（汕頭大學(xué) 電子工程系，廣東 汕頭515063）

在數(shù)據(jù)挖掘算法中，K均值聚類算法是一種比較常見(jiàn)的無(wú)監(jiān)督學(xué)習(xí)方法，簇間數(shù)據(jù)對(duì)象越相異，簇內(nèi)數(shù)據(jù)對(duì)象越相似，說(shuō)明該聚類效果越好。然而，簇個(gè)數(shù)的選取通常是由有經(jīng)驗(yàn)的用戶預(yù)先進(jìn)行設(shè)定的參數(shù)。本文提出了一種能夠自動(dòng)確定聚類個(gè)數(shù)，采用SSE和簇的個(gè)數(shù)進(jìn)行度量，提出了一種聚類個(gè)數(shù)自適應(yīng)的聚類方法（簡(jiǎn)稱：SKKM）。通過(guò)UCI數(shù)據(jù)和仿真數(shù)據(jù)對(duì)象的實(shí)驗(yàn)，對(duì)SKKM算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法可以快速的找到數(shù)據(jù)對(duì)象中聚類個(gè)數(shù)，提高了算法的性能。

K-means算法；聚類個(gè)數(shù)；初始聚類中心；數(shù)據(jù)挖掘；K-means算法改進(jìn)

近年來(lái)，隨著科學(xué)技術(shù)的發(fā)展，特別是云計(jì)算、物聯(lián)網(wǎng)等新興應(yīng)用的興起，我們的社會(huì)正從信息時(shí)代步入數(shù)據(jù)時(shí)代。數(shù)據(jù)挖掘就是從大量的、不完整的、有噪聲的數(shù)據(jù)中通過(guò)數(shù)據(jù)清洗、數(shù)據(jù)挖掘、知識(shí)表示等過(guò)程挖掘出數(shù)據(jù)隱藏的信息。目前，數(shù)據(jù)挖掘已經(jīng)廣泛的應(yīng)用在電信、銀行、氣象等行業(yè)。其中，聚類算法是數(shù)據(jù)挖掘中比較常見(jiàn)的一種方法，并且廣泛的應(yīng)用在多個(gè)領(lǐng)域[1]。K均值算法通常是由有經(jīng)驗(yàn)的用戶對(duì)簇個(gè)數(shù)K進(jìn)行預(yù)先設(shè)定，K值設(shè)定的不正確將會(huì)導(dǎo)致聚類效果不佳[2]。因此，本文提出了一種SKKM聚類算法，可以對(duì)K值大小進(jìn)行確定。

文獻(xiàn)[3]中提出了基于劃分的聚類算法，該方法對(duì)簇的個(gè)數(shù)并不是自動(dòng)的獲取，而是通過(guò)有經(jīng)驗(yàn)的用戶進(jìn)行設(shè)定?，F(xiàn)有的自動(dòng)確定簇個(gè)數(shù)的聚類方法通常需要給出一些參數(shù)，然后再確定簇的個(gè)數(shù)。如：Iterative Self organizing Data Analysis Techniques Algorithm[4]，該方法在實(shí)踐中需要過(guò)多的對(duì)參數(shù)進(jìn)行設(shè)定，并且很難應(yīng)用在高維數(shù)據(jù)中。李永森[5]等人提出將同一個(gè)類內(nèi)部的聚類和不同類之間的距離構(gòu)建距離代價(jià)函數(shù)，并且對(duì)距離代價(jià)函數(shù)取值來(lái)獲得獲得最優(yōu)K值。文獻(xiàn)[6]提出了一種非監(jiān)督的學(xué)習(xí)方法，通過(guò)試探的方法來(lái)確定聚類個(gè)數(shù)，但是該方法實(shí)踐性不高。文獻(xiàn)[7]將K-means方法與基于密度的DBSCAN方法相結(jié)合，通過(guò)密度準(zhǔn)則來(lái)選擇最佳K值大小。但是為了更快速的確定簇的個(gè)數(shù)，我們提出了一種可以自動(dòng)確定聚類個(gè)數(shù)的聚類方法。

根據(jù)SSE[8]度量的性質(zhì)，我們提出了基于SSE的SKKM聚類算法。該方法通過(guò)劃分算法來(lái)分配數(shù)據(jù)點(diǎn)的結(jié)果，在最終的結(jié)果中利用SK來(lái)確定最佳聚類個(gè)數(shù)。即使沒(méi)有經(jīng)驗(yàn)的用戶，也可以自動(dòng)確定聚類個(gè)數(shù)，在實(shí)踐中更容易使用[9]，并且在對(duì)UCI中的數(shù)據(jù)集和仿真數(shù)據(jù)的實(shí)驗(yàn)中證明了SKKM算法的有效性。

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

SKKM算法是本文提出的一種自動(dòng)確定聚類個(gè)數(shù)的方法，為了使讀者可以更好的了解SKKM算法，我們首先介紹劃分聚類方法和SK指標(biāo)。

1.1 劃分聚類方法

K-means算法是將數(shù)據(jù)集劃分為K個(gè)簇的方法。簇的個(gè)數(shù)K是用戶自己預(yù)先設(shè)定，并且簇的中心點(diǎn)是通過(guò)簇的質(zhì)心來(lái)進(jìn)行描述[10-11]。算法在調(diào)用的過(guò)程中會(huì)用到歐式距離和質(zhì)心的概念[12]，現(xiàn)在我們先來(lái)看下歐式距離和質(zhì)心的定義。

定義 1 設(shè)向量 ai=（ai1，ai2，…，aim）和bj=（bj1，bj2，…，bjm）分別表示兩個(gè)數(shù)據(jù)向量，那么本文說(shuō)的歐式距離定義為：

其中n代表該數(shù)據(jù)集的維數(shù)。

定義2對(duì)于同一個(gè)簇中，該簇的質(zhì)心定義如下：

其|T|j是該簇的數(shù)據(jù)個(gè)數(shù)，Pj為該簇的數(shù)據(jù)對(duì)象。

K-means聚類算法是以K為參數(shù)，將數(shù)據(jù)集N個(gè)對(duì)象劃分為K個(gè)數(shù)據(jù)簇，計(jì)算簇的質(zhì)心，直到準(zhǔn)則函數(shù)收斂[13]。從而保證簇內(nèi)數(shù)據(jù)對(duì)象相似度高，簇間數(shù)據(jù)對(duì)象相似度低。

1.2 SK指標(biāo)

SSE算法是一種用于度量聚類效果的指標(biāo)。誤差平方和越小，表示越接近與它們的質(zhì)心，聚類效果相應(yīng)的也就越好。由于SSE是對(duì)誤差去了平方，因此更加注重遠(yuǎn)離質(zhì)心的點(diǎn)。其實(shí)有一種有效的方法可以降低SSE的值，但這種方法是增加簇的個(gè)數(shù)來(lái)降低SSE大小，而聚類算法的目標(biāo)是保持聚類數(shù)目在不變的情況下，來(lái)提高簇的個(gè)數(shù)，故該方法并不能有效的保證簇內(nèi)對(duì)象相似，簇間對(duì)象相異[14]。而本文提出的SK指標(biāo)，是將SSE的值和K值相結(jié)合，找到相對(duì)應(yīng)的最佳K值，來(lái)達(dá)到聚類的目的。

定義3 SSE的公式定義如式（3）所示：

其中Ci表示第i類數(shù)據(jù)對(duì)象的集合。ci是簇Ci的質(zhì)心，K表示該數(shù)據(jù)集可以劃分為K個(gè)簇的集合，dist是歐幾里德空間里2個(gè)空間對(duì)象之間的歐式距離。

定義4 SK的公式定義如式（4）所示：

其中，k=2，3，…，10。

通過(guò)計(jì)算SK的大小，來(lái)反推出最佳簇類個(gè)數(shù)的選取。SK越小，說(shuō)明聚類效果越好，并且對(duì)應(yīng)的K值即為最佳的簇類個(gè)數(shù)，而不是通過(guò)有經(jīng)驗(yàn)的用戶憑借自己的經(jīng)驗(yàn)來(lái)設(shè)置K值大小。因此，一般的用戶也可以設(shè)置K值大小，從而提高了該算法的性能。

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

SKKM算法只能對(duì)聚類個(gè)數(shù)在10個(gè)以下的數(shù)據(jù)對(duì)象進(jìn)行聚類，并且能夠自動(dòng)的確定聚類個(gè)數(shù)，而不是由有經(jīng)驗(yàn)的用戶進(jìn)行預(yù)先定義。前面已經(jīng)詳細(xì)的介紹了劃分算法和SK指標(biāo)的定義，在劃分算法的基礎(chǔ)上，尋找SK指標(biāo)的最小值，來(lái)確定最佳K值的大小。

1.3.1 算法描述

該算法具體描述如下：

Step1從樣本中隨機(jī)的選擇K個(gè)數(shù)據(jù)為初始簇類中心點(diǎn)。且K的取值為2到10的整數(shù)值。

Step2通過(guò)劃分算法對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，直到質(zhì)心大小不再變化。

Step3計(jì)算SK的取值。先計(jì)算誤差平方和，再通過(guò)K值的大小來(lái)計(jì)算SK值。

Step4重復(fù)1-3的步驟，直到K取值值遍歷完畢。本實(shí)驗(yàn)進(jìn)行100次，求平均SK值大小。

Step5選出最小的SK值，其對(duì)應(yīng)的K值即為最佳聚類個(gè)數(shù)，輸出結(jié)果。

1.3.2 算法分析

SKKM算法是在劃分聚類算法的基礎(chǔ)上，對(duì)SK值進(jìn)行求解，找到相對(duì)應(yīng)的最佳K值。首先隨機(jī)選擇K個(gè)點(diǎn)作為初始聚類中心，然后求解各個(gè)點(diǎn)到初始聚類中心的距離，選擇距離最近的點(diǎn)相對(duì)應(yīng)的簇即為該簇的數(shù)據(jù)集。重新計(jì)算質(zhì)心，直至質(zhì)心位置不再發(fā)生變化，即數(shù)據(jù)集歸類完畢。我們用誤差平方和的大小來(lái)評(píng)判聚類效果，并使用SK的值來(lái)找到最佳K值。在這個(gè)過(guò)程中，迭代的次數(shù)，和數(shù)據(jù)集誤差平方和值的求解是整個(gè)程序中主要的開(kāi)銷時(shí)間，抽樣時(shí)間少，使用效率高。

綜上，SKKM算法可以以非常小的時(shí)間為代價(jià)，自動(dòng)獲取聚類個(gè)數(shù)，提高算法的性能。

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

為了驗(yàn)證SKKM聚類算法的性能，本實(shí)驗(yàn)使用的是UCI數(shù)據(jù)庫(kù)的Iris和Glass數(shù)據(jù)[15]，并且用二維數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)[16]。UCI數(shù)據(jù)庫(kù)是專門用來(lái)支持?jǐn)?shù)據(jù)挖掘算法和機(jī)器學(xué)習(xí)的常用數(shù)據(jù)庫(kù)。仿真數(shù)據(jù)1和仿真數(shù)據(jù)2分布于二維的平面上，如圖1（a）和圖1（c）所示，簇的個(gè)數(shù)分別為 4個(gè)簇和3個(gè)簇。因此，K值的選取是衡量該算法優(yōu)劣的一項(xiàng)重要指標(biāo)，并且通過(guò)UCI數(shù)據(jù)和仿真數(shù)據(jù)驗(yàn)證該算法的有效性。這4個(gè)數(shù)據(jù)集分別運(yùn)行100次，求SK的平均值來(lái)找到最佳K值。

圖1（a）是仿真數(shù)據(jù)對(duì)象1的二維分布圖，通過(guò)我們的經(jīng)驗(yàn)可以將其分為4類，并且用4種不同的形狀將其顯示出來(lái)，如圖1（b）。圖1（c）是仿真數(shù)據(jù)對(duì)象2的二維分布圖，通過(guò)我們的經(jīng)驗(yàn)可以把這些數(shù)據(jù)對(duì)象分為3類，并且用3種不同的形狀將其直觀的顯示出來(lái)，如圖2（d）。所以K值可以通過(guò)有經(jīng)驗(yàn)的用戶進(jìn)行預(yù)先設(shè)定，然而高維的數(shù)據(jù)集并不能進(jìn)行可視化，如何讓機(jī)器自己找出最佳K值，是本篇論文的重點(diǎn)，也是難點(diǎn)。為了證明K值能夠自動(dòng)確定最佳聚類個(gè)數(shù)，我們用表1中的數(shù)據(jù)進(jìn)行驗(yàn)證。

2.1 自動(dòng)確定聚類個(gè)數(shù)的實(shí)驗(yàn)環(huán)境

由表1可以看出，Iris是由150個(gè)數(shù)據(jù)集組成的4維數(shù)據(jù)對(duì)象，聚類個(gè)數(shù)為3。Glass是由214個(gè)數(shù)據(jù)集組成的9維數(shù)據(jù)對(duì)象，聚類個(gè)數(shù)為6。仿真數(shù)據(jù)集1是由80個(gè)數(shù)據(jù)集組成的2維數(shù)據(jù)對(duì)象，聚類個(gè)數(shù)為4。仿真數(shù)據(jù)集2是由140個(gè)數(shù)據(jù)集組成的2維數(shù)據(jù)對(duì)象，聚類個(gè)數(shù)為3。這些數(shù)據(jù)都是在Python中進(jìn)行實(shí)驗(yàn)。接下來(lái)，我們用SKKM聚類算法找出最佳K值的大小。

圖1 仿真數(shù)據(jù)分布圖

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

圖2 仿真數(shù)據(jù)分布圖

2.2 自動(dòng)確定聚類個(gè)數(shù)驗(yàn)證

從表1中我們知道，仿真數(shù)據(jù)集1和仿真數(shù)據(jù)集2的數(shù)據(jù)對(duì)象最佳簇點(diǎn)個(gè)數(shù)分別為4個(gè)簇和3個(gè)簇。我們用文中提出的SKKM算法找出最佳K值，通過(guò)觀察仿真數(shù)據(jù)1的SK分布圖圖2（a）和仿真數(shù)據(jù)2的SK分布圖圖2（b）可以看出，仿真數(shù)據(jù)集1，其SK最小值相對(duì)應(yīng)K值的大小為4，即4為最佳K值，仿真數(shù)據(jù)集2，其SK最小值相對(duì)應(yīng)的K值大小為3，即3為最佳K值。所以，我們提出的SKKM算法可以自適應(yīng)找出最佳K值，與表1中相對(duì)應(yīng)的簇個(gè)數(shù)相符。但是這些數(shù)據(jù)集都是二維的數(shù)據(jù)，現(xiàn)在我們用SKKM算法提到高維中進(jìn)行實(shí)踐，找出最佳K值大小。

從表1中我們知道，Iris數(shù)據(jù)集和Glass數(shù)據(jù)集的數(shù)據(jù)對(duì)象最佳簇點(diǎn)個(gè)數(shù)分別為3個(gè)簇和6個(gè)簇。在這些高位數(shù)據(jù)集中，通過(guò)觀察Iris數(shù)據(jù)集的SK分布圖圖3（a）可以看出，其最小值SK所對(duì)應(yīng)的K值大小為3，即3為最佳K值。Glass數(shù)據(jù)集的SK分布圖圖3（b）可以看出，其最小值SK所對(duì)應(yīng)的K值大小為6，即6為最佳K值。最后，我們通過(guò)SKKM算法，找到了Iris數(shù)據(jù)對(duì)象的最佳K值大小為3，Glass數(shù)據(jù)對(duì)象的最佳K值為6。與簇的個(gè)數(shù)真實(shí)值相等，故SKKM算法行之有效。

SKKM算法通過(guò)對(duì)SK值的選取，找到聚類算法簇的最佳個(gè)數(shù)，而不是人為的對(duì)K值進(jìn)行設(shè)定，與傳統(tǒng)的劃分K-means算法相比，優(yōu)化了預(yù)先設(shè)定K值的缺點(diǎn)，并且通過(guò)實(shí)驗(yàn)證明了SKKM算法對(duì)K值確認(rèn)的有效性。由此可見(jiàn)，SKKM算法可以有效的解決聚類算法中簇個(gè)數(shù)選值的問(wèn)題。但是，SKKM算法在初始中心點(diǎn)的選取問(wèn)題上，異常點(diǎn)對(duì)聚類效果也有一定的影響，不同的初始中心點(diǎn)，最后得出的聚類效果也不一樣，本文是在進(jìn)行100次實(shí)驗(yàn)后，最后根據(jù)平均值來(lái)得出K值大小。

圖3 高維數(shù)據(jù)SSK分布圖

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

在傳統(tǒng)的K-means算法中，聚類個(gè)數(shù)通常是由有經(jīng)驗(yàn)的用戶進(jìn)行設(shè)定，而不是機(jī)器自身進(jìn)行設(shè)定。并且聚類算法特有的缺點(diǎn)也會(huì)對(duì)聚類的效果造成一定的影響。因此，傳統(tǒng)算法并不能行之有效的在實(shí)踐中進(jìn)行應(yīng)用。實(shí)驗(yàn)表明，文中提出的SKKM算法可以準(zhǔn)確的確定聚類個(gè)數(shù)K的值，而不是人為的進(jìn)行設(shè)定，并且結(jié)果也符合預(yù)想效果。

[1]鄭富蘭，吳瑞.基于用戶特征的Web會(huì)話模式聚類算法[J].計(jì)算機(jī)應(yīng)用與軟件，2014.

[2]朱燁行，李艷玲，崔夢(mèng)天，et al.Clustering Algorithm CARDBK Improved from K-means Algorithm[J].計(jì)算機(jī)科學(xué)， 2015，42（3）:201-205.

[3]郝洪星，朱玉全，陳耿，等.基于劃分和層次的混合動(dòng)態(tài)聚類算法[J].計(jì)算機(jī)應(yīng)用研究，2011（1）:51-53.

[4]Ma Cai-hong， Dai Qin， Liu Shi-Bin.A Hybrid PSO-ISODATA Algorithm forremotesensing image segmentation[J].Ieee Computer Soc.，2012：1371-1375.

[5]周愛(ài)武，陳寶樓，王琰.K-means算法的優(yōu)化與改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012（10）：101-104.

[6]周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計(jì)算機(jī)工程與應(yīng)用， 2012，48（12）:100-111.

[7]王千，王成，馮振元，等.K-means聚類算法研究綜述[J].電子設(shè)計(jì)工程， 2012，20（7）:21-24.

[8]LEE S S，Lin J C.An accelerated K-means clustering algorithm selection and erasure rules[J].Zhejiang University -SCIENCE :Computers Electronics，2012，13（10）:761-768.

[9]Habib u R M，Liew C S，Wah T Y，et al.Mining personal data using smartphones and wearable devices:a survey[J].Sensors， 2015，15（2）:4430-4469.

[10]Tomaev N.Boosting for Vote Learning in High-Dimensional kNN Classification[C]//IEEE International Conference on Data Mining Workshop.IEEE，2014:676-683.

[11]Orakoglu F E， Ekinci C E.Optimization of constitutive parameters of foundation soils K-means clustering analysis[J].Sciences in Cold and Arid Regions，2013，5（5）:0626-0636

[12]潘盛輝.移動(dòng)終端百度地圖偏移修正方法的研究[J].信息通信， 2014（10）：40-42.

[13]?alik K R， ?alik B.Validity index for clusters of different sizes and densities[J].Pattern Recognition Letters， 2011，32（2）:221-234.

[14]Khan S S，Ahmad A.Cluster center initialization algorithm for K-modes clustering [J].Expert SystemswithApplications， 2013，40（18）:7444-7456.

[15]Volker Lohweg.UC Irvine Machine Learning Repository[EB/OL]（2012-8）.

[16]Wang Y F， Yu Z G， AnhV.Fuzzy C-means method with empirical mode decomposition for clustering microarray data.[J].International Journal of Data Mining&Bioinformatics， 2013，7（2）:103-17.

The research method on the clustering number of K-means algorithm

LIU Fei， TANG Ya-juan， LIU Yao
（Department of Electronic Engineering， Shantou University， Shantou 515063， China）

K-means clustering algorithm is a kind of common method of unsupervised learning in data mining.The more different objects are between clusters data，the more similar objects are within cluster data.The phenomenon shows that the cluster effect is better.The selection of cluster number is usually carried out byexperienced users who set parameters.This dissertation proposed a SKKM method in which it determines the number of clusters through adopting SSE and the clustering number.The paper had a verification for SKKM algorithm by UCI data and lots of simulation experiments.The experimental result shows that the improved algorithm can determine the clustering number in the data objects，which achieved a noticeable gain of algorithmic performance.

K-means algorithm； the clustering number； the initial clustering center； data mining；K-means algorithm improvement

TP301

：A

：1674－6236（2017）15-0009-05

2016-08-28稿件編號(hào)：201608213

國(guó)家自然科學(xué)基金面上項(xiàng)目（61471228）；廣東省重大科技計(jì)劃項(xiàng)目（2015B020233018）

劉 飛（1990—），男，湖北黃岡人，碩士。研究方向：數(shù)據(jù)挖掘。