K-means聚類算法中聚類個數的方法研究

劉 飛，唐雅娟，劉 瑤

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

K-means聚類算法中聚類個數的方法研究

劉 飛，唐雅娟，劉 瑤

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

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

K-means算法；聚類個數；初始聚類中心；數據挖掘；K-means算法改進

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

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

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

1 改進的K-means算法

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

1.1 劃分聚類方法

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

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

其中n代表該數據集的維數。

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

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

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

1.2 SK指標

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

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

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

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

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

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

1.3 改進的K-means算法

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

1.3.1 算法描述

該算法具體描述如下：

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

Step2通過劃分算法對數據對象進行聚類，直到質心大小不再變化。

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

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

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

1.3.2 算法分析

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

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

2 實驗結果與分析

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

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

2.1 自動確定聚類個數的實驗環境

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

圖1 仿真數據分布圖

表1 實驗數據集信息

圖2 仿真數據分布圖

2.2 自動確定聚類個數驗證

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

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

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

圖3 高維數據SSK分布圖

3 結束語

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

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

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

[3]郝洪星，朱玉全，陳耿，等.基于劃分和層次的混合動態聚類算法[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算法的優化與改進[J].計算機技術與發展，2012（10）：101-104.

[6]周濤，陸惠玲.數據挖掘中聚類算法研究進展[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—），男，湖北黃岡人，碩士。研究方向：數據挖掘。