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

劉 飛，唐雅娟，劉 瑤

（汕頭大學 電子工程系，廣東 汕頭515063）

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

劉 飛，唐雅娟，劉 瑤

（汕頭大學 電子工程系，廣東 汕頭515063）

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

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

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

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

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

1 改進的K-means算法

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

1.1 劃分聚類方法

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

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

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

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

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

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

1.2 SK指標

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

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

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

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

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

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

1.3 改進的K-means算法

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

1.3.1 算法描述

該算法具體描述如下：

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

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

Step3計算SK的取值。先計算誤差平方和，再通過K值的大小來計算SK值。

Step4重復1-3的步驟，直到K取值值遍歷完畢。本實驗進行100次，求平均SK值大小。

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

1.3.2 算法分析

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

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

2 實驗結(jié)果與分析

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

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

2.1 自動確定聚類個數(shù)的實驗環(huán)境

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

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

表1 實驗數(shù)據(jù)集信息

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

2.2 自動確定聚類個數(shù)驗證

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

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

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

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

3 結(jié)束語

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

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

[2]朱燁行，李艷玲，崔夢天，et al.Clustering Algorithm CARDBK Improved from K-means Algorithm[J].計算機科學， 2015，42（3）:201-205.

[3]郝洪星，朱玉全，陳耿，等.基于劃分和層次的混合動態(tài)聚類算法[J].計算機應用研究，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]周愛武，陳寶樓，王琰.K-means算法的優(yōu)化與改進[J].計算機技術與發(fā)展，2012（10）：101-104.

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

[7]王千，王成，馮振元，等.K-means聚類算法研究綜述[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]潘盛輝.移動終端百度地圖偏移修正方法的研究[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稿件編號：201608213

國家自然科學基金面上項目（61471228）；廣東省重大科技計劃項目（2015B020233018）

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