張 雄，趙禮峰

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

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

張 雄，趙禮峰

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

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

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

0 引 言

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

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

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

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

1 相關(guān)知識(shí)

1.1K-均值聚類算法

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

算法流程如下：

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

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

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

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

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

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

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

常用的聚類有效性指標(biāo)[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)計(jì)信息的指標(biāo)，而其他指標(biāo)全都是局域數(shù)據(jù)集樣本集合機(jī)構(gòu)的指標(biāo)，他們不依賴外部的參考標(biāo)準(zhǔn)，只依據(jù)數(shù)據(jù)集本身的統(tǒng)計(jì)特征對(duì)聚類結(jié)果進(jìn)行評(píng)估，并根據(jù)結(jié)果的優(yōu)劣選取最佳聚類數(shù)。

下面對(duì)最常用的CH、DB和Wint指標(biāo)進(jìn)行介紹。

(1)CH指標(biāo)。

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

(1)

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

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

(2)DB指標(biāo)。

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

(2)

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

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

(3)Wint指標(biāo)。

(3)

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

1.3泛化能力

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

2 基于泛化能力評(píng)價(jià)指標(biāo)的最佳聚類數(shù)確定方法

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

(4)

GA指標(biāo)的具體計(jì)算方法如下：

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

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

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

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

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

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

3 數(shù)值實(shí)例

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

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

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

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

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

圖1 dataset的分布

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

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

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

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

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

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

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

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

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

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

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

4 方法評(píng)價(jià)與改進(jìn)

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[7] 張忠平，王愛杰，柴旭光.簡(jiǎn)單有效的確定聚類數(shù)目算法[J].計(jì)算機(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].微電子學(xué)與計(jì)算機(jī)，2016,33(5):62-66.

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

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

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

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

[14] 魏海坤，徐嗣鑫，宋文忠.神經(jīng)網(wǎng)絡(luò)的泛化理論和泛化方法[J].自動(dòng)化學(xué)報(bào)，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ò)出版時(shí)間

時(shí)間：2017-07-05

國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61304169)

張 雄(1993-)，男，碩士研究生，研究方向?yàn)樾畔⒔y(tǒng)計(jì)與數(shù)據(jù)挖掘；趙禮峰，教授，碩士生導(dǎo)師，研究方向?yàn)閳D論及其在通信中的應(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