動態分配聚類中心的改進K均值聚類算法

程艷云，周 鵬

(南京郵電大學 自動化學院，江蘇 南京 210023)

動態分配聚類中心的改進K均值聚類算法

程艷云，周 鵬

(南京郵電大學 自動化學院，江蘇 南京 210023)

K均值算法(KMEANS)是一種應用廣泛的經典聚類算法，但其有兩個缺陷，即對初始聚類中心敏感及需要人工確定聚類的個數，因而聚類結果的準確率較低。針對K均值聚類算法現存的兩個缺陷，為提高算法的精確性與穩定性，以及改善聚類性能，提出了一種改進的K均值算法。該算法通過定義的平均類間最大相似度指標值來確定最佳的K值，將所有數據點中密度較高的點作為備選聚類中心，將備選點中密度最大的兩個點作為聚類中心進行初步聚類計算并更新當前聚類中心。當計算得到的平均類間最大相似度現值小于前次計算值，則依據相對距離原則從備選點中動態選擇下一個聚類中心；否則，將當前的聚類中心作為最佳初始聚類中心進行K均值聚類計算。實驗結果表明，改進后的算法不僅能夠有效地提高聚類計算的精確性與穩定性，而且還能縮短聚類計算時間，具有一定的技術優勢和應用前景。

KMEANS算法；動態聚類中心；相對距離；高密度點

0 引 言

聚類分析是數據挖掘領域的一個重要分支，是一種無監督的學習方式。聚類分析的主要應用領域有機器學習、模式識別、文本挖掘、圖像分割及模式分類等[1]。人們根據不同領域的需求研究出了不同的聚類方法。主要分為基于層次的、基于網格的、基于密度的、基于劃分的聚類算法[2]。其中，使用最廣泛的是基于劃分的聚類算法。基于劃分的聚類算法大多是基于數據的距離估計，通過計算數據點與聚類中心之間的距離將數據點分配到最近的聚類中心所在的類中[3]。按這個思想，發展出了不同的聚類算法，最受歡迎的是KMEANS算法。KMEANS算法收斂速度快、算法簡單、能有效處理大數據集[4]。但它有兩個主要的缺點：手動確定聚類個數和初始聚類中心選擇的隨機性[5]。

針對KMEANS算法主要從兩方面進行改進：獲得最佳聚類中心和獲得最佳聚類個數[6-7]。對于初始聚類中心的改進，文獻[8]提出了最大最小距離的算法，選擇相互距離最遠的K個數據對象作為初始聚類中心。文獻[9]提出了基于密度的改進算法，將密度最大的K個點作為初始聚類中心。這些算法從不同程度上解決了初始聚類中心的隨機選擇性，一定程度上提高了聚類的精確性，但并沒有從根本上解決算法極易陷入局部最優解的問題。對于聚類個數的改進，目前的方法大多是人為定義一些指標用于判斷是否達到最佳聚類個數。文獻[10]提出了一種確定最佳聚類個數的方法，比較K取所有可能值下的聚類結果，獲得最佳聚類個數。該方法可以確定最佳的聚類個數，但當K值變化范圍很大時，需要花費大量的時間和精力。文獻[11]提出了一種基于距離最大化的K值自動生成算法。該方法一定程度上可以確定最佳的聚類個數，但若初始聚類中心選擇到那些異常點時，算法的精度將大幅下降。除此之外，還有一些改進方法，如KMEANS算法與遺傳算法相結合[12-13]、KMEANS算法與蟻群算法相結合[14]等等。

文中在分析已有改進算法的基礎上，提出一種新的改進算法。該算法通過迭代能自動獲得最佳的聚類個數，同時動態分配下一個聚類中心以獲得當前狀態下的最佳聚類中心。對于同一數據集，該算法有確定的聚類中心，所以它的聚類結果較穩定。

1 KMEANS算法

在基于劃分式的聚類算法中，類被視為一種具有相似性質的點簇。數據集中的點被劃分到不同的簇，是由它們到給定聚類中心的距離決定的。有幾種基于劃分式的聚類算法，如：KMEANS算法、KMEDOIDS算法、CLARANS算法。最常用的是KMEANS算法，其基本思想是，首先從數據集中隨機選擇K個數據對象作為初始聚類中心，將余下的數據對象依據它們與這些聚類中心的相似度(距離)分配到相應的類中。然后計算每個類新的聚類中心，不斷重復這一過程，直到評價函數收斂。一般采用簇內誤差平方和作為評價函數，其定義為：

(1)

其中，K為聚類個數；P為簇i內的數據對象；ci為聚類中心。

聚類中心的更新依照式(2)：

(2)

KMEANS算法的執行步驟如下[15]：

輸入：包含N個數據對象的數據集，聚類的個數K，算法終止條件(或迭代次數)。

輸出：K個簇、評價函數值E、算法運行時間等。

(1)隨機選擇K個數據對象作為初始聚類中心。

(2)計算余下的數據對象到這K個聚類中心之間的距離(相似度)，并將數據對象分配到距離最近的簇中。

(3)根據式(2)重新計算K個簇的聚類中心，并根據式(1)計算相應的評價函數值E。

(4)如果達到最大的迭代次數或相鄰兩次的評價函數值之差小于ε，則算法停止。否則轉步驟(2)。

ε是一個人為定義的數值。當相鄰兩次的評價函數值之差小于ε時，表明算法收斂。

KMEANS算法具有的優點：簡單易實現，運行速率快，能夠處理大型數據集。但KMEANS算法也有許多不便之處。例如：初始聚類中心的隨機選擇導致算法極易陷入局部最優解。同時，算法需要首先確定聚類個數，而這一點是很難做到的。

圖1顯示相同數據集在不同初始聚類中心下的聚類結果。圖2顯示相同數據集在不同聚類數目下的聚類結果。圖中的數據集是人工數據集。很顯然，KMEANS算法的聚類精確度受初始聚類中心和聚類數目的影響很大。

圖1 同一數據集不同初始聚類中心下的聚類結果

2 改進的KMEANS算法

在分析已有改進算法的基礎上提出一種全新的改進算法。該算法通過比較類間平均最大相似度可以自動確定最佳的聚類個數，還能動態調節當前的聚類中心并動態添加下一個聚類中心。該算法將密度度量和距離度量相結合，從高密度的備選點中選擇距離當前更新后的聚類中心相對最遠的點作為新的聚類中心添加到當前聚類中心集合中。這樣做可以使不同類的聚類中心盡可能相互排斥，從而保證了類間的低相似性。同時，從高密度的備選點中選擇下一個聚類中心，這可以保證在同一個類中，聚類中心是一個相對密集區域的點，保證了類內的高相似性。而類間低相似與類內高相似也是對聚類結果好壞的一個評價指標。對于一個數據集，最佳聚類個數一定，使用該算法獲得的聚類中心也是固定的，這保證了算法的穩定性。

圖2 同一數據集在不同聚類個數下的聚類結果

一些相關的概念及公式定義如下：

點密度：點xi的r鄰域內點的個數。

Density(xi)={p∈c|dist(xi,p)≤r}

(3)

其中，xi為類i的聚類中心；r為人為定義的鄰域半徑。

類內距離：類中每個點到聚類中心之間的距離的均值。

(4)

類間距離：不同類的聚類中心之間的距離。

di,j=‖ci-cj‖

(5)

這里數據對象之間的距離均采用歐氏距離進行度量。

平均類間最大相似度(AMS)：每一個類與其他類之間的最大相似度的均值。

(6)

當AMS取得最小值時，說明聚類效果最佳，此時的K就是最佳的聚類個數。

①冰崩和冰滑坡是引起冰湖潰決的主要誘因。應從遙感、GIS和野外調查三個層面及其組合對冰磧湖進行系統監測。冰磧湖潰決參數包括冰磧湖參數、冰磧壩參數、母冰川參數、冰湖盆參數以及它們之間的相互關系。當前有一些經驗方法可以對潰決風險進行定量評估。

改進后算法的執行步驟如下：

輸入：包含N個數據對象的數據集，用于判斷點密度的鄰域半徑r，作為備選初始聚類中心的高密度點個數M，初始的AMS值，算法的終止條件。

輸出：K個簇、評價函數值E、算法運行時間。

(1)計算每個數據點的點密度，并將點密度最大的M個點加入到備選點集D中。

(2)從集合D中選出密度最大的兩個點作為初步聚類中心，并將其從D中刪除。

(3)從集合D中選擇距離前兩個聚類中心最遠的點，作為下一個聚類中心，并將其從D中刪除。

(4)將N個數據點根據以上聚類中心進行一次迭代劃分，并計算AMS值。

(5)如果新獲得的AMS值小于上一次的AMS值，算法繼續，轉步驟(6)。否則，以AMS最小時所對應的聚類中心作為KMEANS算法的初始聚類中心，轉步驟(7)。

(7)進行KMEANS聚類。

這里進行最后一步聚類的聚類中心是經過K-1次動態分配而獲得的最佳K個聚類中心。它是嚴格按照數據的特點產生的，而不是隨機選擇的，因此可以有效避免聚類結果的波動性。同時，由這種機制產生的最佳聚類中心可以很好地避開離群點(那些誤差很大的點)，因此可以在較大程度上提高聚類的準確性。

3 實 驗

3.1 實驗描述

為驗證文中改進算法的聚類準確性和穩定性，選用UCI數據庫上的Iris、Wine、Seeds、Breast共4組數據作為測試數據。由于傳統的KMEANS聚類算法和改進的最大最小距離聚類算法對初始聚類中心的選擇具有隨機性，故對上述兩種算法取20次實驗結果的均值作為最終的聚類結果。UCI數據庫是一個專門用于測試機器學習、數據挖掘算法的數據庫。庫中的數據都有明確的分類，因此可用UCI數據來檢測聚類算法的準確率。表1是用于測試的4組數據的屬性。

3.2 實驗結果

用隨機選擇初始聚類中心的KMEANS算法和改進的最大最小距離KMEANS算法以及文中改進算法對以上4組測試數據集進行實驗。表2是這4組數據集在不同聚類算法下的聚類準確率。

表1 測試數據集屬性

表2 傳統KMEANS算法與改進算法的準確率 %

由表1及表2可以看出，傳統算法在相同聚類數目下，數據維度越大，聚類結果精確率越低。數據總量對聚類結果的精確率也有影響，但影響程度低于數據維度的影響。此外，聚類數目對聚類精確度的影響也很大。文中提出的動態聚類算法相比傳統的聚類算法和改進的最大最小距離算法而言，能夠不同程度地提高聚類精確度。

表3是4組數據集在這三種聚類算法下的評價函數值(總的誤差)。評價函數是用于判斷一個聚類效果好壞的重要指標。評價函數值越小，聚類效果越好。

表3 傳統KMEANS算法與改進算法的評價函數值

由表3可以看出，最大最小距離算法雖然可以提高聚類算法的精確率，減小誤差值，但該算法具有一定的適用范圍。在Breast數據集上，最大最小距離算法提高了聚類精確率，但誤差值卻比傳統算法要大。相比于前兩種算法，文中算法可以較好地降低誤差值。這也一定程度上說明了文中算法具有一定的優勢。

圖3是4組測試數據集在這三種聚類算法下的聚類時間曲線(單位：s)。

可以看出，最大最小距離算法在Breast數據集上的運行時間要比傳統K均值算法長，說明了最大最小距離算法具有一定適用范圍。文中提出的動態聚類算法相比以上兩種算法，能夠很好地縮短運行時間，提高算法效率。

圖3 三種聚類算法的聚類時間曲線

3.3 實驗分析

綜合以上實驗結果可知，傳統的K均值算法在數據對象增加或數據維度加大的情況下，聚類準確率有所下降。當聚類個數增加時，聚類結果的準確率下降最明顯。改進的最大最小距離算法一定程度上提高了算法的聚類精度，但對于某些數據集，它的運行時間以及評價函數值甚至要超過傳統的K均值聚類算法。這說明改進的最大最小距離聚類算法只適用于某些特定的數據集。文中提出的改進算法在聚類準確率方面具有很大的提高。同時，與前兩種算法相比，很好地降低了聚類時間開銷。從評價函數值指標也可以看出這種算法具有一定的優越性。

4 結束語

文中提出的動態分配聚類中心的聚類算法對聚類結果的準確率有很大的提高。相比于傳統的K均值聚類算法和改進的最大最小距離算法，由于每種數據集的數據對象一定，經過動態分配的初始聚類中心一定，故該算法的聚類結果較穩定。但這種算法需要計算每個數據對象對于給定鄰域內的密度，故隨著數據集中數據對象的增大，其時間復雜度也會隨之增加。當數據對象十分龐大時，如何降低該算法的時間復雜度，將是下一步需要解決的問題之一。

[1]KanungoT,MountDM,NetanyahuNS,etal.AnefficientK-meansclusteringalgorithm:analysisandimplementation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2002,24(7):881-892.

[2] 倪志偉,倪麗萍,劉慧婷,等.動態數據挖掘[M].北京:科學出版社,2010.

[3]ChaventM,LechevallierY,BriantO.Monotheticdivisivehierarchicalclusteringmethod[J].ComputationalStatistics&DataAnalysis,2007,52(2):687-701.

[4]SudiptoG,RajeevR,KyuseokS.Cure:anefficientclusteringalgorithmforlargedatabases[J].InformationSystems,1998,26(1):35-58.

[5]XuJinhua,LiuHong.Webusersclusteringanalysisbasedonk-meansalgorithm[C]//IEEE2010internationalconferenceoninformation,networkingandautomation.Kunming,China:IEEE,2010.

[6]LouhichiS,GzaraM,AbdallahHB.Adensitybasedalgorithmfordiscoveringclusterswithvarieddensity[C]//IEEE2014worldcongressoncomputerapplicationandinformationsystems.Hammamet,Tunisia,American:IEEE,2014:1-6.

[7]YedlaM,PathakotaSR,SrinivasaTM.Enhancingk-meansclusteringalgorithmwithimprovedinitialcenter[J].InternationalJournalofComputerScienceandInformationTechnologies,2010,1(2):121-125.

[8] 周 涓,熊忠陽,張玉芳,等.基于最大最小距離法的多中心聚類算法[J].計算機應用,2006,26(6):1425-1427.

[9] 韓凌波,王 強,蔣正鋒,等.一種改進的K-means初始聚類中心選取算法[J].計算機工程與應用,2010,46(17):150-152.

[10] 周世兵,徐振源,唐旭清.K-means算法最佳聚類數確定方法[J].計算機應用,2010,30(8):1995-1998.

[11] 劉鳳芹.K-means聚類算法改進研究[D].濟南:山東師范大學,2013.

[12]GriraN,CrucianuM,BoujemaaN.Activesemisupervisedfuzzyclustering[J].PatternRecognition,2008,41(5):1834-1844.

[13]CristoforD,SimoviciDA.Aninformationtheoreticalapproachtoclusteringcategoricaldatabasesusinggeneticalgorithms[C]//ProcofSIAMICDM.Arlington,American:[s.n.],2002.

[14] 鞏敦衛,蔣余慶,張 勇,等.基于微粒群優化聚類數目的K-均值算法[J].控制理論與應用,2009,26(10):1175-1179.

[15]ZhangZhe,ZhangJunxi,XueHuifeng.ImprovedK-Meansclusteringalgorithm[C]//Congressandsignalprocessing.[s.l.]:[s.n.],2008:169-172.

ImprovedK-means Clustering Algorithm for Dynamic Allocation Cluster Center

CHENG Yan-yun，ZHOU Peng

(School of Automation，Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

KMEANS algorithm is a classical clustering algorithm with popular application.However,there are two defects of it known as sensitivity to initial cluster centers and clustering number needs to determine.Thus,the accuracy of clustering results is rather low.In order to improve its accuracy and stability and ameliorate its clustering performance,an improvedK-meansclusteringalgorithmhasbeenpresentedandacquired.OptimumKvalueisdeterminedfortheimprovedalgorithmbydefiningaveragemaximumsimilarityindexbetweenclasses,andthentwopointswithhighestdensityareselectedasclustercentersforinitialKMEANSclusteringandupdatingthecurrentclustercenteraftertheoneswithhigherdensityhavebeentakenascandidateclusteringcenters.Ifthecurrentvalueofaveragemaximumsimilarityindexbetweenclassesislessthantheformer,thennextclustercenterisdynamicallychosenfromcandidateclustercentersbyprincipleofrelativedistance.Otherwise,thecurrentcenteristakenasoptimumclustercenterforKMEANSclustering.Resultsofexperimentsshowthattheimprovedalgorithmcaneffectivelyboostclusteringaccuracyandstabilityandshortentheclusteringtime.Italsoimpliesbothdefinitetechnicaladvantagesandperspectiveforapplicationoftheimprovedalgorithm.

KMEANS algorithm;dynamic clustering center;relative distance;high density point

2016-04-06

2016-08-17

時間：2017-01-10

江蘇省自然科學基金(BK20140877,BK2014803)

程艷云(1979-)，女，副教授，碩士生導師，從事自動控制原理、網絡優化的教學科研工作；周 鵬(1991-)，男，碩士研究生，研究方向為數據挖掘與智能計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1029.078.html

TP

A

1673-629X(2017)02-0033-04

10.3969/j.issn.1673-629X.2017.02.008