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

張 雄，趙禮峰

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

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

張 雄，趙禮峰

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

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

K-均值；最佳聚類數(shù)；泛化能力；非監(jiān)督學習

0 引 言

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

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

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

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

1 相關(guān)知識

1.1K-均值聚類算法

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

算法流程如下：

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

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

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

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

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

1.2最佳聚類數(shù)確定方法

傳統(tǒng)的聚類數(shù)確定，是通過聚類有效性指標來評價不同k值下聚類結(jié)果的優(yōu)劣，從而選出最優(yōu)的聚類數(shù)。

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

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

(1)CH指標。

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

(1)

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

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

(2)DB指標。

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

(2)

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

可以看出，DB越小，表示類與類之間的相似度越低，從而對應(yīng)的聚類結(jié)果越優(yōu)。

(3)Wint指標。

(3)

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

1.3泛化能力

泛化能力[14]常見于人工神經(jīng)網(wǎng)絡(luò)，是用來評價一個分類器性能的指標。所謂泛化能力，是指從訓練樣本數(shù)據(jù)得到的模型，能夠很好地適用于測試樣本數(shù)據(jù)，訓練集上訓練的模型在多大程度上能夠?qū)π碌膶嵗A(yù)測出正確輸出稱為泛化能力(Generalization Ability，GA)。

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

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

(4)

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

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

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

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

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

不同于傳統(tǒng)的聚類有效性指標，GA指標不是從聚類結(jié)果的結(jié)構(gòu)來評價聚類效果，而是應(yīng)用人工神經(jīng)網(wǎng)絡(luò)中的泛化能力來衡量聚類的有效性，GA指數(shù)越大，說明該聚類泛化能力越高，聚類效果越佳。然而該指標不適用于聚類數(shù)為1的聚類，此時GA指數(shù)為1，雖然達到了最大，但此時的聚類本身是沒有意義的。

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

3 數(shù)值實例

利用R語言編程環(huán)境實現(xiàn)算法，為檢測所提方法的有效性和穩(wěn)定性，分別對人工數(shù)據(jù)集和真實數(shù)據(jù)集進行仿真實驗。

3.1人工數(shù)據(jù)集

利用R軟件生成人工數(shù)據(jù)集dataset，dataset由三個簇共900個二維點構(gòu)成，該數(shù)據(jù)集數(shù)據(jù)構(gòu)成如表1所示。

表1 dataset的數(shù)據(jù)構(gòu)成

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

圖1 dataset的分布

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

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

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

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

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

3.2真實數(shù)據(jù)集

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

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

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

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

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

4 方法評價與改進

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[7] 張忠平，王愛杰，柴旭光.簡單有效的確定聚類數(shù)目算法[J].計算機工程與應(yīng)用,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] 賈瑞玉，宋建林.基于聚類中心優(yōu)化的k-means最佳聚類數(shù)確定方法[J].微電子學與計算機，2016,33(5):62-66.

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

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

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

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

[14] 魏海坤，徐嗣鑫，宋文忠.神經(jīng)網(wǎng)絡(luò)的泛化理論和泛化方法[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">網(wǎng)絡(luò)出版時間

時間：2017-07-05

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

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

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