改進K均值聚類算法

楊 娟，屈傳慧

(西安電子科技大學，陜西 西安 710071)

改進K均值聚類算法

楊 娟，屈傳慧

(西安電子科技大學，陜西 西安 710071)

K均值聚類算法因需給定聚類中心數(shù)，使得聚類結(jié)果受初始化中心數(shù)的影響很大。介紹了K均值聚類法的概念，并引入層次聚類的概念，采用先分解后合并的思想對K均值法進行了改進，對改進后算法進行了仿真驗證。

K均值；聚類算法；分解合并

0 引 言

聚類，就是將樣本分配到不同類的過程[1]。聚類的基礎(chǔ)為樣本之間的相異性，聚類即尋找樣本之間的相似度對樣本進行劃分。

目前，常用的聚類方法包括：劃分聚類、層次聚類、密度聚類等。劃分聚類就是對給定的數(shù)據(jù)集，采用分裂法構(gòu)造K個分組，每個分組就代表一個聚類，且每一個分組至少包含一個數(shù)據(jù)紀錄，每個分組互不相交，即每一個數(shù)據(jù)紀錄屬于且僅屬于一個分組，常見的算法如K 均值算法、CLARANS算法等[2]。層次聚類就是對給定的數(shù)據(jù)集進行層次分解或者合并，直到所有的記錄組成1個分組或者某個條件滿足為止，具體又可分為合并(自底向上)和分解(自頂向下)2種方案，常見的算法有BIRCH算法、CURE算法等[3-4]。密度聚類基于密度，它克服了基于距離的算法只能發(fā)現(xiàn)超球形聚類的缺點，該方法的基本思想就是只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去，其代表算法有 DBSCAN算法、OPTICS 算法等[5]。在眾多的聚類方法中，K均值方法是一種最經(jīng)典的也是應用最廣泛的聚類方法[6-7]，該方法對超球形和凸狀數(shù)據(jù)有很好的聚類效果。但是，由于經(jīng)典K均值算法必須在聚類前就設置聚類的個數(shù)K，最后所得到的聚類結(jié)果會受到初始選擇的聚類個數(shù)的影響。若聚類個數(shù)選擇得過小，可能導致同一類內(nèi)的有些樣本差別過大，若聚類個數(shù)選擇得過多，可能導致不同類間的樣本差別過小，都達不到有效聚類的目的。因此，如何選擇合適的聚類個數(shù)一直是聚類問題中討論的熱點問題[8]。

本文基于K均值法，引入層次聚類的思想，對K均值法進行了改進，改善了K值的取值矛盾問題，使得改進后的算法受初始聚類個數(shù)的影響變小，有助于得到更好的聚類效果，且相比其它層次K均值聚類算法，本算法實現(xiàn)簡單。

1 經(jīng)典K-均值聚類

K均值算法能夠使聚類域中的所有樣品到聚類中心距離平方和最小。其原理為：先取K個初始聚類中心，計算每個樣品到這K個中心的距離，找出最小距離，把樣品歸入最近的聚類中心，修改中心點的值為本類所有樣品的均值，再計算各個樣品到新的聚類中心的距離，重新歸類，修改新的中心點，直到新的聚類中心和上一次聚類中心差距很小時結(jié)束。此算法結(jié)果受到聚類中心的個數(shù)和聚類中心初次選擇影響，也受到樣品的幾個性質(zhì)及排列次序的影響。如果樣品的幾何性質(zhì)表明它們能形成幾塊孤立的區(qū)域，則算法一般可以收斂。

2 改進K均值聚類

K均值算法需設置聚類數(shù)，改進的K均值算法初始化K值時，設置比較大的K值，此處K值具體的設置需根據(jù)所聚類對象來設置，若無法判斷，則只需將其設置很大即可，但此時的計算量也將增大。改進的K均值法采用先分后和的思想，即先將整個數(shù)據(jù)根據(jù)K均值法聚類成設置的K個集合，再利用各集合中心與其相對應的最大聚類半徑確定的圓與其它圓的交疊的比例來確定是否合并，當交疊比例超過門限時，2個聚類結(jié)果合并，更新合并后的聚類結(jié)果，如此往復。直至所有的聚類結(jié)果不滿足合并條件，此時的結(jié)果作為最終的聚類結(jié)果。

交疊比例的計算方法為：計算第i個聚類結(jié)果中的每個元素與第j個聚類中心的歐氏距離，歐氏距離的計算方法:

(1)

第j個聚類結(jié)果的聚類半徑rj的計算方法為：

(2)

式中：i=1,2,…,K；p=1,2,…,n；j=1,2,…,K,i≠j。

當該距離小于第j個聚類半徑，即dipj≥rj時，交疊值加一；否則，不加一。最終計算交疊值與第i個聚類結(jié)果數(shù)據(jù)數(shù)的比值，當比值大于門限時，合并第i個聚類結(jié)果和第j個聚類結(jié)果，作為新的聚類結(jié)果；當比值小于門限時，不合并，此文檔中的門限值取為定值0.5,即當2個聚類結(jié)果有一半以上數(shù)據(jù)交疊時，將兩者合并歸為一類。

改進后的K均值算法流程如圖1所示。

3 仿真分析

圖2為聚類前的數(shù)據(jù)二維平面圖，圖3為K均值法的聚類結(jié)果圖，圖4為改進后的K均值法的聚類結(jié)果圖。由仿真結(jié)果可得：改進后的算法對K均值聚類分離的7類結(jié)果進行了相似合并，最終聚類結(jié)果為3類，聚類效果較好。

4 結(jié)束語

本文對K均值聚類算法進行了改進，改進后的K均值算法對初始化時的聚類數(shù)依賴性小，且算法實現(xiàn)簡單，并對改進后的算法進行了仿真驗證，該聚類算法可用于各種無監(jiān)督聚類應用中，也可以用于電子偵察中的信號分選模塊。

[1] 賀玲，吳玲達，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計算機應用研究，2007，24(1)：10-13.

[2] 謝崇寶，袁宏源.最優(yōu)分類的模糊劃分聚類改進方法[J].系統(tǒng)工程，1997，15(1)：58-63.

[3] CILIBRASI R L，VITANYI P M B.A fast quartet tree heuristic for hierarchical clustering[J].Pattern Recognition，2011，44(3)：662-677.

[4] 李凱，王蘭.層次聚類的簇集成方法研究[J].計算機工程與應用，2010，46(27)：120-123.

[5] 武佳薇，李雄飛，孫濤，等.鄰域平衡密度聚類算法[J].計算機研究與發(fā)展，2010，47(6)：1044-1052.

[6] KANUNGO T，MOUNT D M.A local search approximation algorithm for K-means clustering[J].Computational Geometry，2004，28(2/3)：89-112.

[7] ELKAN C.Using the triangle inequality to accelerate K-means[C]//Proceedings of The 2nd International Conference on Machine Learning.Menlo Park：AAAI Press，2003：147-153.

[8] 胡偉.改進的層次K均值聚類算法[J].計算機應用研究，2013，49(2)：157-159.

ImprovedK-meansClusteringAlgorithm

YANG Juan,QU Chuan-hui

(Xidian University,Xi'an 710071,China)

Because the K-means clustering algorithm need to give the clustering center number,the influence of initial center number on clustering result is great.This paper introduces the concept of K-means clustering algorithm and inducts hierarchical clustering concept,adopts the idea of decomposition before combination to improve the K-means algorithm,simulates and validates the improved algorithm.

K-means;clustering algorithm;decomposition and combination

2017-06-23

TN911.7

A

CN32-1413(2017)06-0091-03

10.16426/j.cnki.jcdzdk.2017.06.020