楊 娟，屈傳慧

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

改進(jìn)K均值聚類算法

楊 娟，屈傳慧

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

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

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

0 引 言

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

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

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

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

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

2 改進(jìn)K均值聚類

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

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

改進(jìn)后的K均值算法流程如圖1所示。

3 仿真分析

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

4 結(jié)束語

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

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

[2] 謝崇寶，袁宏源.最優(yōu)分類的模糊劃分聚類改進(jìn)方法[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].計算機(jī)工程與應(yīng)用，2010，46(27)：120-123.

[5] 武佳薇，李雄飛，孫濤，等.鄰域平衡密度聚類算法[J].計算機(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] 胡偉.改進(jìn)的層次K均值聚類算法[J].計算機(jī)應(yīng)用研究，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