基于泛化能力的K-均值最佳聚類數確定方法

張 雄，趙禮峰

(南京郵電大學 理學院，江蘇 南京 210023)

基于泛化能力的K-均值最佳聚類數確定方法

張 雄，趙禮峰

(南京郵電大學 理學院，江蘇 南京 210023)

針對K-均值聚類算法需要事先確定聚類數，而人為設定聚類數存在極大主觀性的缺點，提出了一種基于泛化能力的最佳聚類數確定方法。該方法認為：一個好的聚類結果，應該對未知的樣本有著良好的泛化能力。其通過設計一種泛化能力指標(GA)來評價得到的聚類模型對未知樣本的分類能力，泛化能力指標的值越大，則聚類模型的效果越好，以泛化能力最優的聚類模型所對應的K值作為最佳聚類數。為了測試所提出方法的穩定性和有效性，分別基于真實數據集Iris以及人造數據集對基于泛化能力的最佳聚類數確定方法進行了實驗驗證，均能準確找到數據集最佳聚類數。實驗結果表明，該方法能夠簡單、高效地獲得最佳聚類數，且對數據集的聚類效果良好。

K-均值；最佳聚類數；泛化能力；非監督學習

0 引 言

聚類分析[1]也稱無教師學習或無指導學習，它是在沒有訓練目標的情況下將樣本劃分為若干簇的方法，其目的是建立一種歸類方法，將一批樣本或變量，按照它們在特征上的疏密程度進行分類，使得組內樣品的相似度達到最大，而組間的差異也達到最大。到目前為止，還沒有一種具體的聚類算法可以適用于解釋各種不同類型數據組成的多樣化結構數據集。聚類方法大致可分為以下幾種：劃分式聚類算法、層次聚類算法、基于密度的聚類算法、基于網格的聚類算法和基于模型的聚類算法[2]。其中，K-均值聚類[3]是劃分式聚類算法中最常用的算法之一，近年來，許多學者對它進行了研究和改進，使得K-均值聚類算法逐漸形成了一個較為完善的聚類體系。但是，K-均值算法依然存在缺點：無法事先確定聚類數目。不根據數據本身來確定k值的主觀性較強，由于缺乏數據支持，從而導致聚類的效果不佳。

為了更加科學地確定聚類數，從而減小聚類數的選取對聚類效果的影響，周世兵等[4]提出了一種新的聚類有效性指標—BWP指標。該指標通過計算聚類結果中某一個樣本點的最小類間距離與類內距離之和比上最小類間距離與類內距離之差，從而反映出聚類結構的類內緊密性和類間分離性，根據BWP指標的大小來選取最佳聚類數。李芳等[5]提出了一種針對大數據集的K-均值改進算法，將最小生成樹算法應用在初始的k個聚類中心，通過合并相似度最大的聚類中心以減小k值，直到評判函數收斂，最終得到較優聚類數的聚類結果。李龍龍等[6]提出了一種新型模糊半監督加權聚類算法，采用4種模糊聚類有效性評價算法依次對不同聚類數下的聚類結果進行分析，最終通過不同聚類評價結果的對比分析得到實驗數據的最佳聚類數。

但是，目前對于K-均值聚類算法的改進[7-12]大多是基于聚類分析中的最大最小距離，即認為一個好的聚類結果應該盡可能地反映數據集的內在結構，使得類內距離盡可能小，類間距離盡可能大。但是，這種基于聚類結構方法的缺點也很明顯，由于需要計算每個樣本點之間的距離，在處理高維海量數據時，計算量太大，導致效率低下。

針對上述問題，從不同于聚類結構的另一個角度(泛化能力)來對聚類結果的有效性進行評價。基于有指導學習的思想，亦即一個好的聚類結果，還應能對未知的樣品進行預測，并且預測結果與未知樣品自身的聚類可以做到很好的擬合，這種對未知樣品的類別進行準確預測的能力被稱為聚類結果的泛化能力。在此基礎上，提出了一種最佳聚類數確定方法。

1 相關知識

1.1K-均值聚類算法

K-均值算法是一種典型的劃分聚類方法，其思想是在給定聚類數k時，通過最小化組內誤差平方和來得到每一個樣本點的分類。

算法流程如下：

(1)確定聚類數k，并從n個樣本點中任意選擇k個點作為初始聚類中心；

(2)計算其余點與k個聚類中心間的距離，根據距離的大小將它們分配給其最相似的中心所在的類別；

(3)采用均值法重新計算每個新類的聚類中心；

(4)不斷重復步驟2和步驟3，直到所有樣本點的分類不再改變或類中心不再改變。

由于不需要計算任意兩個樣本點之間的距離，因此K-均值聚類往往用于大規模的數據，并且比其他聚類方法的收斂速度更快。然而，K-均值聚類容易受到初始聚類中心的影響，不適用于非凸的數據集；其次，聚類數的確定也是聚類分析中一個非常重要的問題，它對聚類的有效性和聚類結果的解釋都有直接的影響；另外，在高維數據集的聚類中，聚類變量的選擇也是一個重要的問題，維數過高會使空間中的點變得稀疏，從而使距離失效。

1.2最佳聚類數確定方法

傳統的聚類數確定，是通過聚類有效性指標來評價不同k值下聚類結果的優劣，從而選出最優的聚類數。

常用的聚類有效性指標[13]包括Calinski-Harabasz(CH)、Davies-Bouldin(DB)、Weighted inter-intra(Wint)、Krzanowski-Lai(KL)、Hartigan(Hart)、In-Group Proportion(IGP)等。其中，IGP是基于數據集統計信息的指標，而其他指標全都是局域數據集樣本集合機構的指標，他們不依賴外部的參考標準，只依據數據集本身的統計特征對聚類結果進行評估，并根據結果的優劣選取最佳聚類數。

下面對最常用的CH、DB和Wint指標進行介紹。

(1)CH指標。

CH指標通過類內離差矩陣描述緊密度，類間離差矩陣描述分離度，指標定義為：

(1)

其中，n表示聚類數目；k表示當前的類；trB(k)表示類間離差矩陣的跡；trW(k)表示類內離差矩陣的跡。

可以看出，CH越大，類自身越緊密，類與類之間越分散，即得到更優的聚類結果。

(2)DB指標。

DB指標是基于樣本的類內散度與各聚類中心的間距的方法，其定義為：

(2)

其中，k為聚類數目；wi為Ci類中的所有樣本到聚類中心的平均距離；wj為類Cj中的所有樣本到類Cj中心的平均距離；Cij為類Ci和Cj中心之間的距離。

可以看出，DB越小，表示類與類之間的相似度越低，從而對應的聚類結果越優。

(3)Wint指標。

(3)

其中，intra(i)表示類內相似度；inter(i,j)表示類間相似度。

1.3泛化能力

泛化能力[14]常見于人工神經網絡，是用來評價一個分類器性能的指標。所謂泛化能力，是指從訓練樣本數據得到的模型，能夠很好地適用于測試樣本數據，訓練集上訓練的模型在多大程度上能夠對新的實例預測出正確輸出稱為泛化能力(Generalization Ability，GA)。

2 基于泛化能力評價指標的最佳聚類數確定方法

基于泛化能力的最佳聚類數確定方法是通過分類的思想來解決聚類問題，將無指導的聚類與有指導的學習結合起來，通過對不同k值得到的聚類結果泛化能力的比較得出最優聚類數，將聚類泛化能力的評價指標定義為GA，其公式為：

(4)

GA指標的具體計算方法如下：

(1)將給定的數據集進行隨機拆分，分為訓練集tr和測試集te；

(2)分別對訓練集和測試集進行K-均值聚類，聚類數都為k，分別得到訓練集的聚類結果tr1和測試集的聚類結果te1；

(3)應用分類方法，對步驟2中得到的tr1進行學習，并根據學習到的判別函數對測試集中的樣本進行判別，判別結果為te2；

(4)比較te1和te2中對應樣本的類別，計算te1和te2中類別相同的樣本個數n占測試集樣本總數Nte的比例，取值區間為[0，1]。

不同于傳統的聚類有效性指標，GA指標不是從聚類結果的結構來評價聚類效果，而是應用人工神經網絡中的泛化能力來衡量聚類的有效性，GA指數越大，說明該聚類泛化能力越高，聚類效果越佳。然而該指標不適用于聚類數為1的聚類，此時GA指數為1，雖然達到了最大，但此時的聚類本身是沒有意義的。

另外，在實際聚類中，聚類數不應過多，否則對于聚類結果將難以解釋，因此對于有限的可選聚類數，可以采用窮舉法得到。通過計算不同聚類數下的GA指數，選擇最大的GA指數對應的聚類數作為整體數據集的最佳聚類數，并對原始數據整體進行聚類，得到最優的聚類結果。

3 數值實例

利用R語言編程環境實現算法，為檢測所提方法的有效性和穩定性，分別對人工數據集和真實數據集進行仿真實驗。

3.1人工數據集

利用R軟件生成人工數據集dataset，dataset由三個簇共900個二維點構成，該數據集數據構成如表1所示。

表1 dataset的數據構成

dataset的分布情況如圖1所示。

圖1 dataset的分布

根據GA指標的計算流程，將這900個樣本隨機分為兩部分，一部分作為測試集，一部分作為訓練集，其比例為3∶7。通過以上步驟，將數據集分為兩部分，其中train為訓練集，有637個樣本，test為測試集，有263個樣本。分別對測試集和訓練集進行K-均值聚類，k值的選取采用窮舉法，即k=2，3，4，5，依次進行聚類。

之后根據訓練集的聚類結果對測試集進行分類，將得到的分類結果與之前的聚類結果進行對比，求出不同k值下的GA指數，結果如表2所示。

表2 不同k值下的GA指數(dataset)

通過表2可以看到，當k為3時，GA指數達到最大，因此對于dataset，最佳聚類數為3，此時聚類模型具有更強的泛化能力，是該數據集最佳的聚類模型。

接下來對dataset的所有數據進行k值為3的K-均值聚類，得到的三個聚類中心分別為：(1.86，1.98)，(3.12，20.04)，(14.84，25.37)，與生成dataset時設定的三個簇中心很接近，且所有樣本點的聚類結果都與原始類別吻合，說明聚類效果很好。

3.2真實數據集

數值實例所用數據是R軟件中自帶的iris數據集，該數據集由不同種類鳶尾花的150個樣本數據構成，每個樣本有4個變量，分別為：Sepal.Length(花萼長度)、Sepal.Width(花萼寬度)、Petal.Length(花瓣長度)、Petal.Width(花瓣寬度)。通過iris數據集的四個自變量對150個樣本進行聚類。接下來，對這150個樣本進行基于泛化能力的聚類分析，并確定最佳聚類數。

首先，還是對iris數據集進行劃分，隨機選取其中的44個樣本作為測試集，剩下的106個樣本作為訓練集，然后計算不同k值下的GA指數。k值采用窮舉法，分別選取2、3、4、5，最后得到的結果如表3所示。

表3 不同k值下的GA指數(iris)

通過表3可以看到，當k=3時，測試集中的44個樣本全都被正確地分到了三類中，GA指數達到最大1，說明此時的聚類模型泛化能力最高，聚類效果最理想，由此可以判斷iris數據集的最佳聚類數為3。而當k取2，4，5時，都存在一定的誤判，這樣的聚類結果的泛化能力不夠高，不是該數據集最優的聚類模型。

接下來對iris數據集進行k值為3的K-均值聚類，將聚類結果與原始樣本所屬類別進行比較，發現在所有的150個樣本中，有136個樣本被準確分類了。對于前兩種花的分類結果比較理想，而第三種花的誤判較高，后兩類之間存在小范圍的重疊，這可能與數據量的大小有關，過小的數據量導致聚類算法不能更加有效地學習到各類的特征，從而導致聚類結果的誤判。

4 方法評價與改進

不同于現有的基于聚類結構的最佳聚類數確定方法，所提方法為最佳聚類數的確定提供了一條新的思路，同時在一定程度上解決了現有方法計算復雜效率低下的缺點，具有較好的應用價值。另外，該方法不僅僅適用于K-均值聚類，對于其他需要提前確定聚類數的聚類算法，都可以通過該方法來提前確定最佳聚類數。

但是該方法依然存在不足，即對于樣本量較小的數據集，在對特征進行學習時無法更加準確地構建分類器，從而導致GA指標計算結果的精度有所降低，因此該方法更加適用于高維度的海量數據，而這恰恰是現有其他方法存在不足的地方。

5 結束語

針對K-均值算法需要人為設定k值，且現有的k值確定方法都是基于聚類模型結構這一不足，提出了一種基于泛化能力的最佳聚類數確定方法。該方法通過設計出的GA指標來對聚類模型的泛化能力進行評價，并以此作為聚類有效性的評價指標，選擇GA指數最大的k值作為最佳聚類數。對人工生成數據和真實數據的兩次實驗結果表明，該方法可以有效地得到最佳聚類數，從而得到最優的聚類模型。

[1] 孫吉貴，劉 杰，趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[2] 王 實，高 文.數據挖掘中的聚類方法[J].計算機科學,2000,27(4):42-45.

[3] 馮 超.K-means聚類算法的研究[D].大連：大連理工大學，2007.

[4] 周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數確定方法[J].計算機工程與應用，2010,46(16):27-31．

[5] 李 芳.K-means算法的k值自適應優化方法研究[D].合肥：安徽大學，2015.

[6] 李龍龍,何東健,王美麗.模糊半監督加權聚類算法的有效性評價研究[J].計算機技術與發展,2016,26(6):65-68.

[7] 張忠平，王愛杰，柴旭光.簡單有效的確定聚類數目算法[J].計算機工程與應用,2009,45(15):166-168．

[8] Mehar A M,Matawie K,Maeder A.Determining an optimal value of K in K-means clustering[C]//IEEE international conference on bioinformatics and biomedicine.[s.l.]:IEEE,2013:51-55.

[9] 賈瑞玉，宋建林.基于聚類中心優化的k-means最佳聚類數確定方法[J].微電子學與計算機，2016,33(5):62-66.

[10] 王 勇，唐 靖,饒勤菲,等.高效率的K-means最佳聚類數確定算法[J].計算機應用，2014,34(5):1331-1335.

[11] 張 琳，陳 燕，汲 業,等.一種基于密度的K-means算法研究[J].計算機應用研究，2011，28(11):4071-4073．

[12] 李雙虎，王鐵洪.K-means聚類分析算法中一個新的確定聚類個數有效性的指標[J].河北省科學院學報，2003，20(4):199-202．

[13] 宋 媛.聚類分析中確定最佳聚類數的若干問題研究[D].延邊：延邊大學，2013.

[14] 魏海坤，徐嗣鑫，宋文忠.神經網絡的泛化理論和泛化方法[J].自動化學報，2001,27(6)：806-815.

A Method for Determination of Optimal Value inK-means Clustering with Generalization

ZHANG Xiong，ZHAO Li-feng

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Aimed at the defect ofK-means clustering algorithm determining the clustering number in advance which could be defined artificially and is subjective in computations,a method of determining an optimal clustering value with generalization is proposed.It is thought that a good clustering result should have good generalization to the unknown samples.Therefore,a generalization index is designed to evaluate the classification of the unknown samples in the clustering model obtained.The more the value of generalization index,the better the effect of clustering model.TheKvalue corresponded by clustering model with optimal generalization is selected as the optimal clustering value.In order to verify its stability and effectiveness,the experiments are carried out in optimal clustering determining methods based on generalization based on Iris and artificial data set,which indicate that it is simple and efficient to obtain the optimal clustering number,and has the good clustering effect.

K-means clustering;optimal number of clusters;generalization;unsupervised learning

2016-09-07

：2016-12-14 < class="emphasis_bold">網絡出版時間

時間：2017-07-05

國家自然科學基金青年基金項目(61304169)

張 雄(1993-)，男，碩士研究生，研究方向為信息統計與數據挖掘；趙禮峰，教授，碩士生導師，研究方向為圖論及其在通信中的應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1651.054.html

TP301

:A

:1673-629X(2017)09-0031-04

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