何選森，何 帆，徐 麗，樊躍平

(1. 廣州商學(xué)院信息技術(shù)與工程學(xué)院 廣州 511363；2. 湖南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410082；3. 北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院 北京 海淀區(qū) 100081)

在大數(shù)據(jù)時(shí)代[1]，數(shù)據(jù)分類是數(shù)據(jù)應(yīng)用的基礎(chǔ)，由于無監(jiān)督的分類(unsupervised classification)或聚類(clustering)[2]不需要對(duì)數(shù)據(jù)進(jìn)行訓(xùn)練，因而獲得了廣泛應(yīng)用。聚類是采用多元統(tǒng)計(jì)方法，依據(jù)數(shù)據(jù)間的相似性或距離測(cè)度直接把性質(zhì)相近的數(shù)據(jù)歸為一類，性質(zhì)差異較大的樣本歸屬于不同的類。聚類分析中的聚類結(jié)構(gòu)有3 種：分區(qū)(partitional)聚類、層次(hierarchical)聚類和單個(gè)(individual)集群。層次聚類又分為凝聚層次聚類[3]和分裂層次聚類[4]。常用的聚類法有模糊C 均值聚類[5]、密度基(density-based)聚類[6]以及K-均值(K-Means)類的聚類[7]等。

在無先驗(yàn)知識(shí)情況下對(duì)數(shù)據(jù)分析的關(guān)鍵是找出數(shù)據(jù)中的固有劃分(inherent partitions)，盡管聚類算法可以劃分?jǐn)?shù)據(jù)，但不同算法或同一種算法采用不同的參數(shù)將產(chǎn)生出不同的數(shù)據(jù)劃分或揭示不同的聚類結(jié)構(gòu)(clustering structures)。因此，客觀、定量地評(píng)價(jià)算法的聚類結(jié)果就顯得十分重要。換句話說，由一種聚類算法得到的聚類結(jié)構(gòu)是否有意義，即聚類驗(yàn)證(cluster validation)非常重要。層次聚類是基于鄰近矩陣(proximity matrix)將數(shù)據(jù)組織到層次結(jié)構(gòu)中，其結(jié)果通常用樹狀圖[8]表示。與層次聚類相比，分區(qū)聚類將一組數(shù)據(jù)對(duì)象分配到?jīng)]有任何層次結(jié)構(gòu)的k個(gè)聚類中[9]，而且這個(gè)過程通常伴隨著對(duì)一個(gè)準(zhǔn)則函數(shù)的不斷優(yōu)化。在分區(qū)聚類算法中，應(yīng)用最廣泛的一種準(zhǔn)則函數(shù)是平方誤差和準(zhǔn)則(sum-of-squared-error criterion)[2]。使得平方誤差和為最小的劃分被認(rèn)為是最優(yōu)的，一般稱其為最小方差(minimum variance)劃分[7]。數(shù)據(jù)的聚類是指：在同一類中數(shù)據(jù)對(duì)象具有很高的相似度(similarity)，而不同聚類之間的數(shù)據(jù)則具有較高的相異性(dissimilarity)[10]。顯然，相似性與相異性(或稱距離)可概括為鄰近性，它既可以描述數(shù)據(jù)點(diǎn)之間、數(shù)據(jù)類之間的遠(yuǎn)近關(guān)系，又可以描述數(shù)據(jù)點(diǎn)與數(shù)據(jù)類之間的遠(yuǎn)近關(guān)系。對(duì)于聚類分析，常用的距離是歐幾里得(歐氏)距離，利用歐氏距離形成的聚類對(duì)特征空間中的平移和旋轉(zhuǎn)變換具有不變性[11]。

1 K-均值算法與聚類有效性分析

K-均值屬于分區(qū)聚類的結(jié)構(gòu)，目標(biāo)是將數(shù)據(jù)組織成若干類，并且任一數(shù)據(jù)點(diǎn)只能屬于一個(gè)類而不能同時(shí)屬于多個(gè)類，這就意味著K-均值算法生成的是特定數(shù)量、互不相交、非層次的聚類。K-均值算法通過迭代優(yōu)化步驟，利用最小化平方誤差和準(zhǔn)則來尋求數(shù)據(jù)的最佳劃分，屬于爬山(hill-climbing)類算法的范疇[7]。本質(zhì)上，K-均值就是期望最大化(expectation maximization, EM)算法的經(jīng)典范例。EM 算法的第一步是尋找與聚類相關(guān)的期望點(diǎn)，第二步是利用第一步的知識(shí)改進(jìn)對(duì)聚類的估計(jì)，重復(fù)這兩個(gè)步驟直到算法收斂。

K-均值算法中，數(shù)據(jù)對(duì)象之間采用歐氏距離來度量相異性。設(shè)數(shù)據(jù)集有n個(gè)樣本，它的p維觀測(cè)為：

任意兩個(gè)樣本點(diǎn)xi,xj(i,j=1, 2, ···,n)之間的歐氏距離表示為dij=d(xi,xj)。如果將n個(gè)樣本分成k個(gè)聚類，則選擇全部數(shù)據(jù)之間距離最遠(yuǎn)的兩個(gè)(序號(hào)為i1,i2)樣本作為初始聚類中心(聚點(diǎn))：

然后再確定下一個(gè)聚點(diǎn)(序號(hào)i3)，使得i3與i1,i2距離最小者等于所有其他點(diǎn)與i1,i2較小距離中的最大者：

不斷重復(fù)以上過程，即可確定全部k個(gè)初始聚點(diǎn)。因此，K-均值算法的基本過程可以歸納如下。

1) 設(shè)隨機(jī)選取的k個(gè)初始聚點(diǎn)的集合為：

對(duì)于任意的數(shù)據(jù)點(diǎn)x，對(duì)它的劃分原則為：

即將所有樣本分成不相交的k個(gè)類，得到初始分類：

顯然，K-均值聚類算法的基本思想是將數(shù)據(jù)空間首先隨機(jī)地劃分為事先指定的k個(gè)類，然后通過迭代計(jì)算不斷更新每個(gè)類的質(zhì)心。當(dāng)相鄰兩次迭代計(jì)算的結(jié)果基本相同時(shí)，則算法收斂。盡管K-均值算法被證明是收斂的[12]，然而困擾K-均值聚類的第一個(gè)問題是它的迭代優(yōu)化過程不能保證算法收斂到全局最優(yōu)。由于K-均值算法可以收斂到局部最優(yōu)[7]，不同的初始劃分將導(dǎo)致不同的收斂質(zhì)心。第二個(gè)問題是K-均值算法對(duì)數(shù)據(jù)中的異常值也即野值(outliers)以及噪聲(noise)很敏感[2,7]，在迭代計(jì)算聚點(diǎn)的過程中算法卻是考慮了所有的樣本。即使某個(gè)樣本點(diǎn)離質(zhì)心很遠(yuǎn)，但K-均值算法仍然將該點(diǎn)強(qiáng)行納入最鄰近的類中用于計(jì)算其質(zhì)心，這樣就造成了聚類形狀的扭曲。另外，K-均值類算法要求用戶事先指定聚類數(shù)量，這在實(shí)際中很難做到。聚類數(shù)量是否正確將直接影響聚類效果，確定最優(yōu)的聚類數(shù)量也稱為聚類有效性分析(clustering validity analysis)[13]。因此，在聚類分析中，一個(gè)必不可少的步驟是驗(yàn)證聚類結(jié)果并確保它能正確地反映數(shù)據(jù)的本質(zhì)結(jié)構(gòu)?；诮y(tǒng)計(jì)理論對(duì)算法生成的聚類結(jié)構(gòu)進(jìn)行評(píng)估，強(qiáng)調(diào)以客觀和定量的方式對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)，這就是聚類趨勢(shì)分析(clustering tendency analysis)[14]。

分區(qū)聚類、層次聚類和單個(gè)集群的結(jié)構(gòu)所對(duì)應(yīng)的聚類有效性測(cè)試標(biāo)準(zhǔn)分別為外部的(external)、內(nèi)部的(internal)和相對(duì)的標(biāo)準(zhǔn)(relative criteria)[15]，這3 種標(biāo)準(zhǔn)的適用范圍不同。外部與內(nèi)部標(biāo)準(zhǔn)都涉及到統(tǒng)計(jì)方法和假設(shè)檢驗(yàn)[16]，這將導(dǎo)致計(jì)算開銷增加。而相對(duì)標(biāo)準(zhǔn)則無須進(jìn)行統(tǒng)計(jì)檢驗(yàn)，它致力于比較不同的聚類結(jié)果。因此，相對(duì)標(biāo)準(zhǔn)可用于比較K-均值類算法一系列不同聚類數(shù)量k的聚類效果，以便找出數(shù)據(jù)劃分最適合的k值，這個(gè)問題也被稱為聚類有效性的基本問題(fundamental problem)[17]。

K-均值類算法包括一系列聚類方法，如Kmedoids 算法[18]和K-均值算法，它們的適用范圍和特點(diǎn)各不相同。K-均值的時(shí)間復(fù)雜度為O(nkpT)，其中，n為樣本數(shù)量，k為聚類數(shù)量，p為數(shù)據(jù)維數(shù)，T為算法迭代次數(shù)，由于k,p,T通常都比n小很多，因此K-均值的時(shí)間復(fù)雜度為近似的線性關(guān)系[2,7]，因而它以低計(jì)算復(fù)雜度體現(xiàn)出高效率[18]，但它的聚類結(jié)果很大程度上受數(shù)據(jù)中噪聲與異常值的影響。為了解決K-均值算法的這個(gè)缺陷，Kmedoids 算法以中心點(diǎn)(medoids)作為聚類中心，對(duì)噪聲及異常點(diǎn)處理能力優(yōu)秀且具有較強(qiáng)的魯棒性。然而它的缺點(diǎn)是計(jì)算復(fù)雜度較高，因此學(xué)者們致力于改進(jìn)K-medoids 算法，以期在計(jì)算效率上追趕K-均值算法[18]。在眾多改進(jìn)的K-medoids 方法中，圍繞中心點(diǎn)劃分(partitioning around medoids,PAM)算法[19]被認(rèn)為是最有效的K-medoids 算法之一。但PAM 算法的迭代次數(shù)較多，時(shí)間效率低[19]。在不考慮迭代次數(shù)的情況下，K-medoids 和PAM算法的時(shí)間復(fù)雜度都為O(k(n-k)2)[18]，即為二次函數(shù)。對(duì)于這3 種經(jīng)典的K-均值類聚類算法，僅從時(shí)間開銷的角度來看，K-均值算法的計(jì)算速度是最快的。另外，這3 種算法的共同缺點(diǎn)仍是聚類數(shù)量k作為算法的參數(shù)必須事先指定。聚類數(shù)量k過大或過小的估計(jì)都將嚴(yán)重影響最終的聚類質(zhì)量。過多的聚類數(shù)量造成真正的數(shù)據(jù)聚類結(jié)構(gòu)變得復(fù)雜，使得對(duì)聚類結(jié)果的解釋和分析變得困難，而過少的聚類數(shù)量將損失信息并造成錯(cuò)誤的聚類結(jié)果。

本文主要研究經(jīng)典K-均值聚類算法中最佳聚類數(shù)量的確定問題，因此，其基本的思路為：對(duì)于具體的數(shù)據(jù)集，首先在聚類數(shù)量的可能范圍內(nèi)，采用不同的聚類數(shù)量來運(yùn)行K-均值算法以獲得相應(yīng)的聚類結(jié)果；然后以聚類數(shù)量k為自變量構(gòu)造一種聚類有效性函數(shù)(指標(biāo))對(duì)K-均值的聚類結(jié)果進(jìn)行評(píng)估，通過優(yōu)化聚類有效性函數(shù)來確定最優(yōu)的聚類數(shù)量。

2 聚類有效性評(píng)價(jià)函數(shù)

對(duì)于理想的聚類效果，從相似性角度要求類內(nèi)樣本點(diǎn)之間盡可能相似，同時(shí)類與類之間的樣本點(diǎn)盡可能相異。從距離的角度則要求類內(nèi)樣本點(diǎn)之間距離的代數(shù)和應(yīng)盡量小，而在不同類之間樣本點(diǎn)距離的代數(shù)和應(yīng)盡量大。在整個(gè)數(shù)據(jù)空間中，樣本點(diǎn)與它所在類的聚點(diǎn)之間的距離，要比它與其他類的聚點(diǎn)間的距離都要小。滿足這個(gè)條件的聚類就是有效的數(shù)據(jù)劃分。

對(duì)于全部的n個(gè)數(shù)據(jù)點(diǎn)，其樣本均值(質(zhì)心)為：

在所有的數(shù)據(jù)中，假設(shè)第i個(gè)聚類Ci中有ni個(gè)數(shù)據(jù)對(duì)象，則定義該類的樣本質(zhì)心(中心)為：

從定義1 的表達(dá)式可看出，當(dāng)所有樣本都屬于同一個(gè)類(即聚類數(shù)量k=1)時(shí)，則這個(gè)類的中心就是全體數(shù)據(jù)的質(zhì)心xˉ。在這種情況下，類間質(zhì)心距離之和Dbetw取值為0，即取Dbetw(k)的極小值。隨著聚類數(shù)量k的增加，類間質(zhì)心距離之和函數(shù)Dbetw(k)是遞增的。

定義2 類內(nèi)距離之和 在聚類空間I 上，由每個(gè)類中的各樣本到該類中心的歐氏距離之和為同一類的內(nèi)部距離，而所有k個(gè)聚類的內(nèi)部距離之和則定義為類內(nèi)距離之和：

從定義2 可知，當(dāng)整個(gè)數(shù)據(jù)集的樣本屬于同一個(gè)類(聚類數(shù)量k=1)時(shí)，Dwith就是所有數(shù)據(jù)點(diǎn)與其質(zhì)心xˉ的距離之和，即取Dwith(k)的極大值。隨著聚類數(shù)量k的增加，類內(nèi)距離之和函數(shù)Dwith(k)是遞減的。

定義3 聚類有效性評(píng)價(jià)函數(shù) 在聚類空間I上，基于類間質(zhì)心距離之和Dbetw與類內(nèi)距離之和Dwith，定義一種綜合評(píng)價(jià)函數(shù)(指標(biāo))：

式中，|?|表示取絕對(duì)值。當(dāng)所有數(shù)據(jù)樣本點(diǎn)都屬于同一類(聚類數(shù)量k=1)時(shí)，由于Dbetw(k)=0，則f(k)=1。顯然，隨著聚類數(shù)量k的變化，函數(shù)f(k)的值也發(fā)生相應(yīng)變化，即f(k)是以聚類數(shù)量k為自變量的函數(shù)。對(duì)于K-均值算法，最好的聚類效果意味著聚類數(shù)量k是最優(yōu)的，因此將f(k)稱為聚類有效性評(píng)價(jià)函數(shù)(指標(biāo))。

在統(tǒng)計(jì)學(xué)中，經(jīng)驗(yàn)規(guī)則(empirical rules)[20]常用來預(yù)測(cè)最終的結(jié)果，它也稱為3σ 規(guī)則或68-95-99.7 規(guī)則。經(jīng)驗(yàn)規(guī)則表明：對(duì)于正態(tài)分布，幾乎所有的觀測(cè)數(shù)據(jù)X都將落在平均值E[X]的3 個(gè)標(biāo)準(zhǔn)差σ 之內(nèi)。具體地說，68%的數(shù)據(jù)落在平均值的1 個(gè)σ 之內(nèi)，95%的數(shù)據(jù)落在平均值的2 個(gè)σ 之內(nèi)，99.7%的數(shù)據(jù)落在平均值的3 個(gè)σ 之內(nèi)[21]。在某些情況下，獲取數(shù)據(jù)的分布可能很耗時(shí)，甚至是不可能的，因此正態(tài)概率分布可以作為一種臨時(shí)啟發(fā)式(heuristic)方法，如當(dāng)一家公司正在審查其質(zhì)量控制措施或評(píng)估其風(fēng)險(xiǎn)暴露(risk exposure)時(shí)，風(fēng)險(xiǎn)價(jià)值(value-at-risk)作為常用的風(fēng)險(xiǎn)工具，假設(shè)風(fēng)險(xiǎn)事件的概率服從正態(tài)分布，對(duì)于服從其他分布的觀測(cè)數(shù)據(jù)來說，將經(jīng)驗(yàn)規(guī)則推廣為經(jīng)驗(yàn)貝葉斯規(guī)則(empirical Bayes rules)[22-23]，則可實(shí)現(xiàn)對(duì)具有k類的觀測(cè)數(shù)據(jù)總體進(jìn)行推斷。因此，在計(jì)算出數(shù)據(jù)的均值和標(biāo)準(zhǔn)偏差之后，經(jīng)驗(yàn)規(guī)則可用于粗略地估計(jì)觀測(cè)數(shù)據(jù)總體中所隱含的數(shù)據(jù)類k的數(shù)量范圍。

定理 最佳聚類數(shù)量準(zhǔn)則 在聚類空間I 上，根據(jù)經(jīng)驗(yàn)規(guī)則，可以估計(jì)出聚類數(shù)量k可能的最小值kmin和最大值kmax，因而獲得k的取值范圍[kmin,kmax]。當(dāng)k在[kmin,kmax]變化時(shí)，如果聚類有效性評(píng)價(jià)函數(shù)f(k)獲得最小值，則K-均值算法的聚類效果為最優(yōu)，即對(duì)應(yīng)的最佳聚類數(shù)量k為：

證明：由定義1 可知，類間質(zhì)心距離之和Dbetw(k)是聚類數(shù)量k的單調(diào)增函數(shù)，由定義2 可知，類內(nèi)距離之和Dwith(k)是k的單調(diào)減函數(shù)。因此隨著k取值的變化，由定義3 可知，聚類有效性評(píng)價(jià)函數(shù)f(k)存在極小值，但并不存在有限的極大值。換句話說，函數(shù)f(k)可能取值為無窮大，此時(shí)對(duì)應(yīng)的聚類數(shù)量k是不合理的。

在實(shí)際應(yīng)用中，聚類數(shù)量k只能取正整數(shù)，而且函數(shù)Dbetw(k)和Dwith(k)也都只能取正實(shí)數(shù)值(非負(fù)值)。在k的有限取值范圍[kmin,kmax]內(nèi)，函數(shù)f(k)一定存在有全局的極小值，即最小值。顯然，聚類有效性評(píng)價(jià)函數(shù)的最小值所對(duì)應(yīng)的k值就是數(shù)據(jù)集的最優(yōu)聚類數(shù)量。由定義3 可知，只有當(dāng)Dbetw(k)和Dwith(k)的取值相等或二者非常接近時(shí)，函數(shù)f(k)才能取得最小值。換句話說，通過調(diào)整聚類數(shù)量k的取值使得Dbetw(k)和Dwith(k)達(dá)到最接近的程度，K-均值聚類的效果才是最佳的，此時(shí)對(duì)應(yīng)的聚類數(shù)量k值就使得數(shù)據(jù)的分類達(dá)到最優(yōu)。因此，利用聚類有效性評(píng)價(jià)函數(shù)f(k)作為確定最佳聚類數(shù)量k的準(zhǔn)則，也就是確定f(k)的最小值準(zhǔn)則。

為了找到K-均值算法的最佳聚類數(shù)量k，從可視化的角度，在k值的可能變化范圍[kmin,kmax]內(nèi)，通過繪制聚類有效性評(píng)價(jià)函數(shù)f(k)隨聚類數(shù)量k的變化曲線，直觀地搜尋函數(shù)f(k)的最小值點(diǎn)所對(duì)應(yīng)的聚類數(shù)量k，即為最佳的聚類數(shù)量。

3 驗(yàn)證與分析

為了驗(yàn)證本文提出的聚類有效性評(píng)價(jià)函數(shù)的性能以及由此獲得的最佳聚類數(shù)k是否符合數(shù)據(jù)本身內(nèi)在的分類結(jié)構(gòu)，利用加州大學(xué)歐文分校的機(jī)器學(xué)習(xí)庫(UC Irvine machine learning repository)中的多個(gè)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。

仿真PC 機(jī)的CPU 為：Intel(R) Celeron(R)1007U-1.5 GHz，內(nèi)存4 GB，操作系統(tǒng)為Windows 10，仿真是在MATLAB 9 (R2016a)上運(yùn)行。

對(duì)于數(shù)據(jù)的分類與聚類問題，最常用的UCI數(shù)據(jù)集有Iris、Seeds 和Wind 數(shù)據(jù)集。這3 種數(shù)據(jù)集的數(shù)據(jù)樣本數(shù)量、屬性(特征)數(shù)量以及數(shù)據(jù)真實(shí)的聚類數(shù)量如表1 所示。

表1 3 種UCI 數(shù)據(jù)集的有關(guān)信息

仿真的基本過程為：對(duì)于每一種數(shù)據(jù)集，根據(jù)經(jīng)驗(yàn)規(guī)則估計(jì)數(shù)據(jù)的可能聚類數(shù)量范圍[kmin,kmax]。在這個(gè)范圍內(nèi)的每個(gè)k值，首先分別運(yùn)行K-均值算法一次，并計(jì)算相對(duì)應(yīng)的聚類有效性評(píng)價(jià)函數(shù)f(k)。然后多次運(yùn)行K-均值算法以觀察函數(shù)f(k)的變化趨勢(shì)，從而對(duì)聚類有效性評(píng)價(jià)指標(biāo)f(k)的平均性能進(jìn)行測(cè)試。

3.1 數(shù)據(jù)集Iris 的仿真

鳶尾花Iris 數(shù)據(jù)集記錄了3 種花setosa、versicolor 和virginica 的4 種屬性，即萼片長(zhǎng)(sepal length)表示為x1、萼片寬(sepal width)表示為x2、花瓣長(zhǎng)(petal length)表示為x3、花瓣寬(petal width)表示為x4。3 種花各記錄了50 組特征(即屬性)的數(shù)據(jù)，按照setosa、versicolor 和virginica 的順序存放。

為了觀察Iris 數(shù)據(jù)集對(duì)應(yīng)特征的統(tǒng)計(jì)中心位置，即不同屬性值的分布范圍所圍繞的大致中心，首先計(jì)算出每種鳶尾花的4 個(gè)屬性，即變量x1,x2,x3,x4的均值，如表2 和圖1 所示。

圖1 3 種鳶尾花特征變量均值的條形圖

表2 3 種花4 個(gè)屬性的均值 cm

根據(jù)數(shù)據(jù)樣本數(shù)量以及經(jīng)驗(yàn)規(guī)則，設(shè)Iris 數(shù)據(jù)可能的聚類數(shù)量范圍為[kmin,kmax]，其中kmin=2，kmax=12。對(duì)于[kmin,kmax]中的每個(gè)k值，運(yùn)行K-均值算法一次，并計(jì)算出相對(duì)應(yīng)的聚類有效性評(píng)價(jià)函數(shù)f(k)的值，其結(jié)果如表3 和圖2 所示。

表3 Iris 數(shù)據(jù)的f(k)與k 的對(duì)應(yīng)表

圖2 Iris 數(shù)據(jù)的f(k)隨聚類數(shù)量k 的變化曲線

從圖2 和表3 可以看出：1)函數(shù)f(k)隨著k值做相應(yīng)變化，這就說明聚類有效性評(píng)價(jià)函數(shù)f(k)用來對(duì)聚類數(shù)量k的選擇進(jìn)行評(píng)價(jià)是有效的；2)當(dāng)k=3 時(shí)，f(k)取得最小值，即最佳的聚類數(shù)量為3。這個(gè)結(jié)果證明聚類有效性評(píng)價(jià)函數(shù)f(k)能夠從Iris 數(shù)據(jù)集中找出最佳的聚類數(shù)量，即真實(shí)的鳶尾花所包含的種類。

這里需要說明，K-均值算法的另一個(gè)缺陷是它可以收斂到局部最優(yōu)，而且每次運(yùn)行K-均值算法時(shí)，初始的聚類中心是從所有數(shù)據(jù)中隨機(jī)選取的。因此算法要求必須有一個(gè)合理的初始化，在實(shí)際應(yīng)用中這是不現(xiàn)實(shí)的。對(duì)于不同的初始劃分，將導(dǎo)致K-均值算法收斂到不同的質(zhì)心位置。一種解決方案是通過重復(fù)運(yùn)行K-均值算法多次，并以多次運(yùn)行的平均結(jié)果來降低隨機(jī)初始化的影響。為此，將K-均值算法按照上述的仿真條件重復(fù)運(yùn)行10次，每次分別記錄下對(duì)應(yīng)的聚類有效性評(píng)價(jià)函數(shù)f(k)的值。為觀察方便，這里僅繪制出每次運(yùn)行中函數(shù)f(k)隨聚類數(shù)量k的變化曲線，其結(jié)果如圖3所示。

圖3 10 次運(yùn)行中Iris 數(shù)據(jù)的f(k)隨k 變化的曲線

從圖3 可以看出，雖然K-均值算法的10 次運(yùn)行結(jié)果各不相同，但在每次運(yùn)行中，聚類有效性評(píng)價(jià)函數(shù)f(k)的最小值都是在k=3 時(shí)取得的，這是不變的。圖3 的結(jié)果說明f(k)對(duì)于確定最佳聚類數(shù)量是有效的。

在多次運(yùn)行K-均值算法的基礎(chǔ)上，再考慮聚類有效性評(píng)價(jià)函數(shù)f(k)的平均性能。對(duì)于每個(gè)可能的k值，將10 次運(yùn)行的f(k)求平均值可得到E[f(k)]，其結(jié)果如表4 和圖4 所示?？梢钥闯?，聚類有效性評(píng)價(jià)函數(shù)f(k)在K-均值算法10 次運(yùn)行中的平均值E[f(k)]仍然在k=3 時(shí)取得最小值，這也反映了Iris 數(shù)據(jù)集中真實(shí)的鳶尾花品種為k=3。另外，由于K-均值算法對(duì)數(shù)據(jù)采用隨機(jī)的初始劃分，使得每次運(yùn)行獲得的聚類中心位置并不相同，但從多次運(yùn)行的結(jié)果來看，E[f(k)]仍然能夠準(zhǔn)確地反映Iris 數(shù)據(jù)集的本質(zhì)結(jié)構(gòu)。即聚類有效性評(píng)價(jià)函數(shù)對(duì)K-均值的隨機(jī)初始化具有魯棒性(robustness)。

表4 Iris 數(shù)據(jù)的E[f(k)]值與k 的對(duì)應(yīng)表

圖4 10 次運(yùn)行中Iris 數(shù)據(jù)的E[f(k)]隨k 變化的曲線

3.2 數(shù)據(jù)集Seeds 的仿真

種子(Seeds)數(shù)據(jù)包括3 種小麥粒(wheat kernels)的7 個(gè)幾何參數(shù)(屬性)：面積(area)x1、周長(zhǎng)(perimeter)x2、密度(compactness)x3、長(zhǎng)度(length)x4、寬度(width)x5、不對(duì)稱系數(shù)(asymmetry coefficient)x6、溝槽長(zhǎng)度(length of kernel groove)x7。顯然，這些屬性的度量單位是不相同的。Seeds 數(shù)據(jù)集對(duì)每一類小麥分別記錄了70 組特征的數(shù)據(jù)，按照類標(biāo)簽1、2、3 的順序存放。

對(duì)于Seeds 數(shù)據(jù)，分別計(jì)算3 類(class 1, 2,3)小 麥7 個(gè) 屬 性x1,x2, ···,x7的 均 值，如 圖5 所示。以上均值給出的是3 類小麥所有樣本幾何參數(shù)的分布中心。根據(jù)數(shù)據(jù)集的樣本數(shù)量以及經(jīng)驗(yàn)規(guī)則，設(shè)Seeds 數(shù)據(jù)集中可能的聚類數(shù)量范圍為[kmin,kmax]，其中kmin=2，kmax=13。對(duì)于[kmin,kmax]中的每個(gè)k值，運(yùn)行K-均值算法一次，并計(jì)算出相對(duì)應(yīng)的聚類有效性評(píng)價(jià)函數(shù)f(k)，其結(jié)果如圖6所示。

圖5 3 種小麥特征變量均值的條形圖

由聚類有效性評(píng)價(jià)函數(shù)(指標(biāo))的定義可知，若所有數(shù)據(jù)都屬于同一類(即k=1)，則指標(biāo)f(k)=1。為了便于觀察和比較，在圖6 中還給出了k=1 的波形?？梢钥闯?，當(dāng)k=3 時(shí)，聚類有效性評(píng)價(jià)指標(biāo)f(k)取得一個(gè)最小值0.327 1，即給出了K-均值算法的最佳聚類數(shù)量為3。這一結(jié)果與Seeds 數(shù)據(jù)集的實(shí)際情況是一致的。

圖6 Seeds 數(shù)據(jù)的f(k)隨聚類數(shù)量k 的變化曲線

同樣地，為了考察K-均值算法在重復(fù)多次運(yùn)行情況下的整體性能。對(duì)于Seeds 數(shù)據(jù)集，在k的可能取值范圍[kmin,kmax]內(nèi)重復(fù)運(yùn)行K-均值算法15 次，每次運(yùn)行記錄和保存聚類有效性評(píng)價(jià)函數(shù)f(k)的對(duì)應(yīng)值，其結(jié)果如圖7 所示。可以看到，在K-means 算法的15 次運(yùn)行中，盡管每次運(yùn)行f(k)的取值以及取值的分布情況都不相同，但是指標(biāo)f(k)的最小值毫無例外地在k=3 時(shí)獲得。這表明聚類有效性評(píng)價(jià)函數(shù)f(k)在確定最優(yōu)聚類數(shù)量方面的性能是非常穩(wěn)定的。

對(duì)于每個(gè)可能的k值，把上述15 次K-均值算法運(yùn)行所得到的f(k)值取平均得到E[f(k)]，繪制出E[f(k)]隨k值變化的曲線如圖8 所示。

由圖8 可以看出，從聚類有效性評(píng)價(jià)函數(shù)的平均性能E[f(k)]仍然可以清晰地識(shí)別出Seeds 數(shù)據(jù)集的真實(shí)聚類結(jié)構(gòu)(k=3)。另外，從圖7 和圖8 的結(jié)果可知，在最優(yōu)聚類數(shù)量的確定方面，指標(biāo)f(k)以及其平均值E[f(k)]的性能不會(huì)受到K-均值算法隨機(jī)初始化的影響。

圖7 15 次運(yùn)行中Seeds 數(shù)據(jù)的f(k)隨k 變化的曲線

圖8 15 次運(yùn)行中Seeds 數(shù)據(jù)的E[f(k)]隨k 變化的曲線

3.3 數(shù)據(jù)集Wine 的仿真

葡萄酒(Wine)數(shù)據(jù)是對(duì)在意大利同一地區(qū)種植，但來自3 個(gè)不同品種的葡萄酒進(jìn)行化學(xué)分析的結(jié)果。這種分析確定了3 種類型的葡萄酒中所含13 種成分(屬性、特征)的含量。這些屬性分別為酒精(x1)、蘋果酸(x2)、灰(x3)、灰分堿度(x4)、鎂(x5)、總酚(x6)、黃酮素類化合物(x7)、非黃酮類酚類(x8)、原花青素(x9)、顏色強(qiáng)度(x10)、色調(diào)(x11)、稀釋葡萄酒的OD280/OD315(x12)和脯氨酸(x13)。這些特征值的度量單位是不相同的。Wine數(shù)據(jù)集中共記錄了178 組數(shù)據(jù)，3 種類型葡萄酒的類標(biāo)簽分別為1, 2, 3，它們各自的樣本數(shù)分別為59, 71, 48。對(duì)于Wine 數(shù)據(jù)集，由于不同屬性(變量)的取值之間差距太大(相差3 720 倍)，無法用圖形表示變量的均值。這里僅給出全部13 個(gè)變量的平均值(包括所有葡萄酒的種類)，其結(jié)果如表5所示。

表5 Wine(全部種類)數(shù)據(jù)各屬性的平均值

Wine 數(shù)據(jù)的均值給出了各屬性值分布的大致統(tǒng)計(jì)中心。考慮到Wine 數(shù)據(jù)集的屬性較多，根據(jù)經(jīng)驗(yàn)規(guī)則將數(shù)據(jù)可能的聚類數(shù)量設(shè)置為kmin=2,kmax=16。首先對(duì)于區(qū)間[kmin,kmax]中的每個(gè)k值，運(yùn)行K-均值算法一次，并計(jì)算出相對(duì)應(yīng)的聚類有效性評(píng)價(jià)函數(shù)f(k)的值，其結(jié)果如表6 和圖9 所示。

表6 Wine 數(shù)據(jù)的f(k)與k 的對(duì)應(yīng)表

圖9 Wine 數(shù)據(jù)的f(k)隨聚類數(shù)量k 的變化曲線

為觀察方便，圖9 也給出了k=1 對(duì)應(yīng)的數(shù)據(jù)。由于f(k)取值的范圍較大，最小值附近其差別不易區(qū)分，為此把圖9 中的數(shù)據(jù)列在表6 中。從表6 中的數(shù)據(jù)可知，f(2)是f(3)的143 倍，f(4)是f(3)的236 倍。顯然，k=3 是指標(biāo)f(k)的最小值點(diǎn)，即k=3 是最優(yōu)的聚類數(shù)量，這與Wine 數(shù)據(jù)本質(zhì)結(jié)構(gòu)是一致的。

類似地，對(duì)于Wine 數(shù)據(jù)集，在可能的聚類數(shù)量范圍[kmin,kmax]內(nèi)重復(fù)運(yùn)行K-均值算法15 次，計(jì)算并記錄每次運(yùn)行中指標(biāo)f(k)的取值，其結(jié)果如圖10 所示。

從圖10 也可看出，在運(yùn)行K-均值算法的過程中，由于指標(biāo)f(k)的取值范圍較大，在它的最小值點(diǎn)附近的指標(biāo)f(k)取值也不易區(qū)分。為此，考慮15 次運(yùn)行K-均值算法得到的平均性能E[f(k)]，其結(jié)果如圖11所示。

圖10 15 次運(yùn)行中Wine 數(shù)據(jù)的f(k)隨k 變化的曲線

從圖11 可以看出，對(duì)于Wine 數(shù)據(jù)，隨著聚類數(shù)量k值的增加，指標(biāo)的平均值E[f(k)]曲線變化的大致趨勢(shì)是：當(dāng)k＜3 時(shí)，E[f(k)]曲線是遞減的；當(dāng)k＞3 時(shí)，E[f(k)]曲線是遞增的，因此在k=3 時(shí)取得E[f(k)]的最小值。為了更清楚地比較在E[f(k)]最小值附近數(shù)值上的差別，將圖11 中的E[f(k)]值列在表7 中?？梢钥闯觯珽[f(2)]大約是E[f(3)]的3.65 倍，而E[f(4)]大約是E[f(3)]的6.8 倍。

圖11 15 次運(yùn)行中Wine 數(shù)據(jù)的E[f(k)]隨k 變化的曲線

表7 Wine 數(shù)據(jù)的E[f(k)]值與k 的對(duì)應(yīng)表

盡管Wine 數(shù)據(jù)集的平均性能E[f(k)]的取值范圍相當(dāng)大，但從它的全局極小值即最小值來說，仍然能辨別出k=3 是Wine 數(shù)據(jù)集最優(yōu)的聚類數(shù)量。

從以上對(duì)3 個(gè)UCI 數(shù)據(jù)集(Iris, Seeds, Wine)的仿真結(jié)果可知，利用聚類有效性評(píng)價(jià)函數(shù)f(k)，不僅能夠?qū)υ紨?shù)據(jù)集提供最優(yōu)的聚類數(shù)量，而且從多次重復(fù)運(yùn)行K-均值算法的效果來看，函數(shù)f(k)還能夠?qū)﹄S機(jī)初始化提供很強(qiáng)的魯棒性。

4 結(jié) 束 語

為了克服K-均值聚類算法需要用戶預(yù)先指定聚類數(shù)量的缺陷，本文對(duì)K-均值算法的基本迭代步驟和聚類有效性進(jìn)行了分析；然后，基于數(shù)據(jù)點(diǎn)的歐幾里得距離，給出了類間質(zhì)心距離之和、類內(nèi)距離之和的定義，用于度量不同聚類間和同一聚類的數(shù)據(jù)距離；最后，提出了一種由類間質(zhì)心距離之和與類內(nèi)距離之和構(gòu)造而成的聚類有效性評(píng)價(jià)函數(shù)，用以確定數(shù)據(jù)最優(yōu)的聚類數(shù)量。在數(shù)據(jù)可能的聚類數(shù)量范圍內(nèi)，利用求解聚類有效性評(píng)價(jià)函數(shù)的最小值來確定K-均值算法的最佳聚類數(shù)量。通過對(duì)UCI 中Iris、Seeds 和Wine 數(shù)據(jù)集的仿真，證明了所提出的聚類有效性評(píng)價(jià)函數(shù)不僅能夠準(zhǔn)確地反映原始數(shù)據(jù)的真實(shí)聚類結(jié)構(gòu)，而且還能有效地降低K-均值算法對(duì)隨機(jī)初始化的敏感性。