數(shù)據(jù)降維與K-均值聚類的質(zhì)量評(píng)估

何 帆,何選森,劉潤(rùn)宗,樊躍平,熊茂華

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

0 引言

在大數(shù)據(jù)時(shí)代,對(duì)數(shù)據(jù)的分析和處理變得越來(lái)越重要,而對(duì)數(shù)據(jù)的分類則在數(shù)據(jù)分析中占據(jù)至關(guān)重要的地位,分類又包括監(jiān)督和無(wú)監(jiān)督2種。監(jiān)督分類[1]是指對(duì)具有類標(biāo)簽的樣本數(shù)據(jù)進(jìn)行訓(xùn)練與學(xué)習(xí),通過(guò)判別函數(shù)和判別準(zhǔn)則進(jìn)行分類。無(wú)監(jiān)督分類[2](或稱聚類[3])是用于處理無(wú)分類標(biāo)簽的數(shù)據(jù),屬于探索性數(shù)據(jù)分析[4],由于它可以發(fā)現(xiàn)數(shù)據(jù)固有的結(jié)構(gòu),因而獲得了廣泛的應(yīng)用。聚類分析具有劃分聚類、層次聚類和單個(gè)(individual)集群3種常見的聚類結(jié)構(gòu),其中劃分聚類應(yīng)用最為廣泛,例如K-均值類型的算法[5]。由于此類算法易于執(zhí)行且計(jì)算效率高而獲得了廣泛的應(yīng)用,從而成為經(jīng)典的聚類算法[6]。在此基礎(chǔ)上,又出現(xiàn)了很多改進(jìn)的版本。在K-均值算法中,數(shù)據(jù)點(diǎn)被分配到一個(gè)確定的聚類中,這也稱為硬聚類;而模糊C均值聚類[7]是對(duì)K-均值算法的改進(jìn),是軟聚類的典型代表,它不僅把一個(gè)數(shù)據(jù)點(diǎn)分配給一個(gè)或幾個(gè)聚類,而且給出屬于某個(gè)聚類的概率值[8]。另一個(gè)改進(jìn)版本是k-Medoids算法[9],由于它在對(duì)噪聲以及異常值(離群值)處理方面的優(yōu)異能力,因而具有較強(qiáng)的魯棒性[10]。在這幾種算法中,從計(jì)算效率和穩(wěn)定性來(lái)講,K-均值算法仍然是最優(yōu)的[11]。然而,K-均值聚類算法也存在2個(gè)主要的缺陷:其一是使用算法的前提條件是用戶必須知道數(shù)據(jù)的聚類數(shù)量K,這在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的;其二是聚類結(jié)果對(duì)算法的隨機(jī)初始劃分非常敏感[12],因而可能造成聚類效果變差,甚至使聚類失敗。正是這些因素影響算法對(duì)數(shù)據(jù)的聚類質(zhì)量,因此,本文中提出相應(yīng)的解決方案。為提高聚類性能,對(duì)原數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化預(yù)處理使其服從正態(tài)分布,利用監(jiān)督的線性辨別分析(linear discriminant analysis,LDA)[13]對(duì)高維數(shù)據(jù)進(jìn)行壓縮(降維);通過(guò)對(duì)K-均值算法隨機(jī)初始化的改進(jìn),使得對(duì)初始聚類中心的劃分能避免空聚類并確保數(shù)據(jù)的可分離性;對(duì)聚類結(jié)果采用輪廓分析(silhouette analysis)[14],直觀地評(píng)價(jià)算法的聚類質(zhì)量,以確定數(shù)據(jù)固有的聚類數(shù)量。

1 數(shù)據(jù)預(yù)處理

在聚類問(wèn)題中,假設(shè)p維數(shù)據(jù)的樣本數(shù)量為n,則觀測(cè)數(shù)據(jù)矩陣X一般可表示為

(1)

式中:X的每一行表示一個(gè)樣本,每一列就是特征列即數(shù)據(jù)的屬性(或變量),特征數(shù)量就是數(shù)據(jù)的維數(shù)。聚類的基本思想是根據(jù)數(shù)據(jù)之間的相似度(或距離)來(lái)劃分?jǐn)?shù)據(jù),在聚類分析中,采用歐幾里得(歐氏)距離來(lái)測(cè)度數(shù)據(jù)的遠(yuǎn)近。考慮到不同的特征取值之間的差別可能很大,甚至不在同一個(gè)數(shù)量級(jí)上;為提高算法的性能,通常要進(jìn)行特征縮放的預(yù)處理, 使得不同特征處于同樣的尺度上。典型的縮放有歸一化和標(biāo)準(zhǔn)化[12]。數(shù)據(jù)特征的標(biāo)準(zhǔn)化為

(2)

式中:xjk為數(shù)據(jù)點(diǎn)xj的第k個(gè)特征;mk和σk分別為第k個(gè)特征列的均值和標(biāo)準(zhǔn)差。經(jīng)過(guò)標(biāo)準(zhǔn)化后的特征服從正態(tài)分布。標(biāo)準(zhǔn)化既能保留數(shù)據(jù)中離群值的有用信息,也能有效降低優(yōu)化算法對(duì)噪聲與異常值的敏感性[11]。

另一種數(shù)據(jù)預(yù)處理是對(duì)高維數(shù)據(jù)的降維,包括主分量分析[15]、核主分量分析[16]以及LDA等。考慮到數(shù)據(jù)經(jīng)過(guò)標(biāo)準(zhǔn)化處理后具有正態(tài)性,而監(jiān)督的LDA方法的假設(shè)條件正是數(shù)據(jù)服從正態(tài)分布,且各聚類的協(xié)方差矩陣是相同的。因此,本文采用LDA方法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理以實(shí)現(xiàn)數(shù)據(jù)壓縮。

設(shè)數(shù)據(jù)X的固有聚類數(shù)量為K,某個(gè)聚類Ck(k=1,2,…,K)的質(zhì)心(中心或均值)mk(k=1,2,…,K)定義為

(3)

式中:nk為聚類Ck中的樣本數(shù)量。同樣地,定義來(lái)自各個(gè)聚類中所有數(shù)據(jù)樣本總的均值m為

(4)

式中:n為數(shù)據(jù)X中全部樣本的總數(shù)。

對(duì)聚類Ck,其散射矩陣(scatter matrix)[13]為

(5)

把所有聚類Ck(k=1,2,…,K)對(duì)應(yīng)的散射矩陣Sk加起來(lái)就構(gòu)成了類內(nèi)(within-class)散射矩陣

(6)

式中:散射矩陣Sk和SW都是p×p維方陣。對(duì)于實(shí)值的觀測(cè)數(shù)據(jù),散射矩陣一般是非奇異的,因而它們存在逆矩陣。

同樣,類間(between-class)散射矩陣[17]為

(7)

在此基礎(chǔ)上,本文定義一個(gè)增廣矩陣G,它由類內(nèi)散射矩陣SW的逆和類間散射矩陣SB相乘:

(8)

對(duì)矩陣G進(jìn)行特征分解[18],即分解為特征值和其對(duì)應(yīng)的特征向量,并將特征值按照從大到小的次序排列。對(duì)于具有K個(gè)聚類的數(shù)據(jù)集X,由類間矩陣SB的定義可知,它是由秩為1或秩為小于1的K個(gè)矩陣之和所構(gòu)成的,因而它生成的線性辨別量(linear discriminants)的個(gè)數(shù)最多只能為K-1個(gè)[19]。在實(shí)際應(yīng)用中,只有很少的幾個(gè)最具辨別性的特征向量(對(duì)應(yīng)于非零特征值)被抽取,假設(shè)抽取了v個(gè)(v<

(9)

式中:E1是取值為最大的特征值所對(duì)應(yīng)的特征向量;E2是對(duì)應(yīng)于第二大特征值的特征向量,以此類推。

將觀測(cè)數(shù)據(jù)矩陣X乘以變換矩陣W,也就把原始的數(shù)據(jù)X映射到一個(gè)v維的特征子空間上:

Xsub=XW

(10)

顯然,上式是將原始的p維數(shù)據(jù)變換為(更低的)v維數(shù)據(jù),即利用LDA實(shí)現(xiàn)了數(shù)據(jù)的降維。

2 初始化改進(jìn)與聚類質(zhì)量評(píng)價(jià)

經(jīng)典的K-均值算法的基本迭代步驟[6]如下。

步驟1：從數(shù)據(jù)樣本中隨機(jī)指定K個(gè)數(shù)據(jù)點(diǎn)作為初始的聚類中心(即質(zhì)心)mk(k=1,2,…,K)。

步驟2：將其他數(shù)據(jù)樣本分配給鄰近的質(zhì)心,形成K個(gè)聚類Ck(k=1,2,…,K)。

步驟3：根據(jù)當(dāng)前數(shù)據(jù)所在的聚類,重新計(jì)算(更新)每個(gè)聚類中數(shù)據(jù)的質(zhì)心(即按照式(3)計(jì)算)。

步驟4：重復(fù)步驟2和步驟3,直到聚類中心不再變化, 或達(dá)到用戶指定的最大迭代次數(shù),或達(dá)到用戶指定的誤差容限。對(duì)于劃分聚類,常用的誤差度量就是平方誤差和(sum-of-squared-error,SSE)[20]:

(11)

由于初始質(zhì)心選擇是隨機(jī)的,一些質(zhì)心之間的距離可能會(huì)太近,因而在后面的迭代中被合并, 造成空聚類。為解決此問(wèn)題,提出改進(jìn)的K-均值聚類算法,其主要流程如下。

1) 計(jì)算任意2個(gè)樣本點(diǎn)的歐氏距離,并把距離最遠(yuǎn)的2個(gè)點(diǎn)(設(shè)為x1和x2)作為初始的2個(gè)質(zhì)心。

D(x1,x2)=max{D(xi,xj)}(i,j=1,2,…,n)

(12)

式中:D(x1,x2)為數(shù)據(jù)點(diǎn)x1和x2之間的歐氏距離。

2) 在1)的基礎(chǔ)上,第3個(gè)聚類中心x3的選取則遵循最小-最大規(guī)則

min{D(x3,xr),r=1,2}=

max{[D(xi,xr),r=1,2],i≠1,2}

(13)

即x3與(x1,x2)的距離中的最小者為其他數(shù)據(jù)點(diǎn)xi(i≠1,2)與(x1,x2)的距離中的最大者。

3) 在1)和2)選定的數(shù)據(jù)點(diǎn)(x1,x2,x3)的條件下,仍利用最小-最大規(guī)則,依此可獲得初始的K個(gè)聚類中心。

顯然,經(jīng)過(guò)以上的處理,就確保了初始聚類中心之間是完全可分的,避免出現(xiàn)空聚類,也使得算法有一個(gè)合理的初始劃分,從而解決了經(jīng)典K-均值算法的步驟1中對(duì)隨機(jī)初始化敏感的問(wèn)題。然后繼續(xù)經(jīng)典K-均值算法的步驟2—4即可實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類分析。本文中將經(jīng)過(guò)改進(jìn)后的算法仍稱為K-均值算法。

要驗(yàn)證聚類結(jié)果是否反映數(shù)據(jù)的固有結(jié)構(gòu),需要對(duì)聚類的質(zhì)量進(jìn)行客觀評(píng)價(jià)。輪廓分析就是一種能對(duì)聚類結(jié)果進(jìn)行直觀評(píng)估的方法。

對(duì)于給定聚類Ci中的數(shù)據(jù)點(diǎn)xi,定義ai為

(14)

稱ai為聚類凝聚力[21]。若xi是Ci中唯一的數(shù)據(jù)點(diǎn), 則ai=0;否則,ai為點(diǎn)xi到Ci中其他數(shù)據(jù)點(diǎn)的平均距離。ai的取值表示xi與它所在聚類中其他數(shù)據(jù)點(diǎn)的相似程度。

一個(gè)給定聚類Ci中的數(shù)據(jù)點(diǎn)xi到其他聚類Ck(k≠i)中數(shù)據(jù)點(diǎn)的平均距離定義為

(15)

基于平均距離bik,聚類分離性bi定義[21]為

(16)

即bi是數(shù)據(jù)點(diǎn)xi到與它最鄰近的那個(gè)聚類中所有數(shù)據(jù)點(diǎn)的平均距離。顯然,bi的取值是表示某個(gè)聚類中數(shù)據(jù)點(diǎn)與其他聚類中數(shù)據(jù)點(diǎn)的相異程度。

對(duì)于每一個(gè)數(shù)據(jù)點(diǎn)xi,定義其輪廓系數(shù)[22]為

(17)

顯然,輪廓系數(shù)si的取值范圍為[-1,1]。若bi與ai的取值相等,bi=ai,則可得si=0,即聚類質(zhì)量差;相反,若bi與ai差值很大,bi>>ai,則得到si≈1,即表示聚類質(zhì)量高。每個(gè)聚類的輪廓用于表示該聚類中樣本之間的緊密程度。

數(shù)據(jù)集X中所有樣本的平均輪廓系數(shù)S為

(18)

平均系數(shù)S用于辨識(shí)各聚類中是否包含異常值,且可推斷聚類結(jié)果,S值越大,聚類質(zhì)量越高。

對(duì)好的聚類結(jié)果,各聚類的輪廓系數(shù)應(yīng)具有大致相同的尺寸[22]。因此,實(shí)際應(yīng)用中可通過(guò)對(duì)聚類的輪廓進(jìn)行視覺(jué)檢查來(lái)評(píng)價(jià)聚類的質(zhì)量。

3 仿真結(jié)果與分析

為驗(yàn)證本文方案的有效性,利用2個(gè)不同類型的數(shù)據(jù)集進(jìn)行仿真。通過(guò)輸入不同K值,比較聚類結(jié)果以確定數(shù)據(jù)集本身所固有的聚類數(shù)量。

仿真在個(gè)人計(jì)算機(jī)(PC)上進(jìn)行。采用的操作系統(tǒng)為Windows 10,編程使用Python 3.8。

3.1 二維數(shù)據(jù)集

在這個(gè)仿真中,采用具有2個(gè)特征的Blob數(shù)據(jù)集,其由600個(gè)樣本點(diǎn)形成3個(gè)簇(各含200個(gè)數(shù)據(jù)點(diǎn),用圓圈表示)。橫軸表示特征1,縱軸表示特征2,該數(shù)據(jù)的二維散點(diǎn)圖如圖1所示。

圖1 數(shù)據(jù)集Blob的二維散點(diǎn)

3.1.1 指定聚類數(shù)與數(shù)據(jù)固有聚類數(shù)相同

對(duì)于Blob數(shù)據(jù)集,利用K-均值算法進(jìn)行聚類,主要參數(shù)設(shè)置如下:指定聚類數(shù)量K=3,這也是數(shù)據(jù)本身的聚類數(shù)量;算法的最大迭代次數(shù)為max_iter=300。這里需要說(shuō)明:實(shí)際應(yīng)用中,若在最大迭代次數(shù)之前算法已收斂,則迭代就停止。相反,算法可能在某次運(yùn)行中不收斂,這時(shí)若選擇更大的迭代次數(shù),則算法的計(jì)算成本將增加。為此,本文附加另外一個(gè)參數(shù),即誤差容限(tol)來(lái)控制算法的收斂條件。在以下仿真中,統(tǒng)一設(shè)置一個(gè)較大值:tol=0.000 1。

在以上參數(shù)的條件下,K-均值算法對(duì)數(shù)據(jù)的劃分以及對(duì)聚類質(zhì)心的辨識(shí)結(jié)果如圖2所示。

圖2 在給定K=3時(shí)Blob數(shù)據(jù)的聚類結(jié)果

在圖2中,不同聚類中數(shù)據(jù)點(diǎn)用不同的形狀和顏色表示。可以看出,3個(gè)聚類的質(zhì)心(紅色五角星表示)被放置在每個(gè)數(shù)據(jù)堆的中心位置,該點(diǎn)不一定是某個(gè)數(shù)據(jù)點(diǎn),可能是幾個(gè)數(shù)據(jù)點(diǎn)之間的點(diǎn)。顯然圖2的結(jié)果與數(shù)據(jù)集Blob的自然劃分完全一致,因此聚類效果很好。

為了直觀地分析聚類結(jié)果中每一類數(shù)據(jù)的緊湊性,繪制出每個(gè)聚類對(duì)應(yīng)的輪廓系數(shù)如圖3所示。

圖3 在給定K=3時(shí)Blob數(shù)據(jù)簇的輪廓系數(shù)

從圖3可以看出,3個(gè)聚類的輪廓具有大致一樣的寬度和長(zhǎng)度;且所有樣本的平均輪廓系數(shù)(圖中用紅色虛線表示)的值超過(guò)了0.7(即遠(yuǎn)離0值),這意味著聚類效果良好。

小結(jié):綜合圖2和圖3的結(jié)果可知,如果指定數(shù)據(jù)集的真實(shí)聚類數(shù)量作為算法的參數(shù),則算法在這個(gè)Blob數(shù)據(jù)集上提供了優(yōu)良的聚類質(zhì)量。

3.1.2 指定聚類數(shù)小于數(shù)據(jù)固有聚類數(shù)

若用戶指定的聚類數(shù)量小于數(shù)據(jù)本身的聚類數(shù)量,例如指定算法的聚類數(shù)量為K=2,則聚類結(jié)果的散點(diǎn)圖和輪廓系數(shù)分別如圖4和圖5所示。

圖4 在給定K=2時(shí)Blob數(shù)據(jù)簇的聚類結(jié)果

圖5 在給定K=2時(shí)Blob數(shù)據(jù)簇的輪廓系數(shù)

從圖4可以看出,在上部原本的兩堆數(shù)據(jù)被強(qiáng)行地合并成一個(gè)聚類;而在圖5中Cluster1的輪廓系數(shù)正是由原來(lái)2個(gè)聚類輪廓合并而成的,而且全部數(shù)據(jù)的平均輪廓系數(shù)比圖3也降低了10%以上。

小結(jié):綜合圖4和圖5的結(jié)果可知,如果指定的聚類數(shù)量小于數(shù)據(jù)集原本的聚類數(shù)量,其聚類結(jié)果發(fā)生扭曲,聚類質(zhì)量變差。

3.1.3 設(shè)置聚類數(shù)大于數(shù)據(jù)固有聚類數(shù)

若指定算法的聚類數(shù)量大于數(shù)據(jù)固有的聚類數(shù)量,例如設(shè)置聚類數(shù)量為K=4,則聚類的散點(diǎn)圖和相應(yīng)的輪廓系數(shù)如圖6和圖7所示。

圖6 在給定K=4時(shí)Blob數(shù)據(jù)簇的聚類結(jié)果

圖7 在給定K=4時(shí)Blob數(shù)據(jù)簇的輪廓系數(shù)

從圖6可以看出,右下角的數(shù)據(jù)被算法強(qiáng)行拆分成2個(gè)聚類;圖7中,Cluster2和Cluster4的輪廓系數(shù)正是圖6中被拆分的2個(gè)聚類所對(duì)應(yīng)的輪廓,而且整個(gè)樣本數(shù)據(jù)的平均輪廓系數(shù)與圖3相比較,下降了15%左右。

小結(jié):圖6和圖7的聚類結(jié)果說(shuō)明,若設(shè)置算法的聚類數(shù)量大于數(shù)據(jù)固有的聚類數(shù)量,則產(chǎn)生的聚類質(zhì)量急劇下降。

通過(guò)對(duì)Blob數(shù)據(jù)集的仿真可知,無(wú)論是對(duì)聚類數(shù)量K的過(guò)高或過(guò)低估計(jì),都將對(duì)聚類結(jié)果產(chǎn)生影響,致使聚類形狀畸變、聚類效果惡化。

3.2 高維數(shù)據(jù)集

在下面的仿真中,使用著名的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中真實(shí)的紅酒(Wine)數(shù)據(jù)集。該數(shù)據(jù)集是對(duì)意大利同一地區(qū)種植,但來(lái)自3種不同品種的葡萄酒進(jìn)行化學(xué)分析得出的數(shù)據(jù)。Wine給出這3種葡萄酒的13種不同成分的含量,不同成分就是數(shù)據(jù)的特征。它們分別為酒精(表示為x1)、蘋果酸(x2)、灰(x3)、灰分堿度(x4)、鎂(x5)、總酚(x6)、黃酮素類化合物(x7)、非黃酮類酚類(x8)、原花青素(x9)、顏色強(qiáng)度(x10)、色調(diào)(x11)、稀釋葡萄酒的OD280/OD315(x12)以及脯氨酸(x13)。

3.2.1 高維數(shù)據(jù)集Wine聚類的主要步驟

① 對(duì)13維的Wine數(shù)據(jù)集標(biāo)準(zhǔn)化。

② 對(duì)于每個(gè)類(葡萄),計(jì)算13維均值向量。

③ 構(gòu)建散射矩陣SB和SW,計(jì)算增廣矩陣G。

④ 將矩陣G分解為它的特征值和特征向量。

⑤ 按降序?qū)μ卣髦颠M(jìn)行排序,從而對(duì)相應(yīng)的特征向量進(jìn)行排序。

⑥ 選擇對(duì)應(yīng)于v(v<13)個(gè)最大特征值的v個(gè)特征向量來(lái)構(gòu)造13×v維變換矩陣W;所選定的特征向量就是變換矩陣W的列。

⑦ 使用變換矩陣W將原始數(shù)據(jù)集投影到新的特征子空間上。

⑧ 在特征子空間上,對(duì)變換后的數(shù)據(jù)進(jìn)行聚類。

3.2.2 Wine數(shù)據(jù)集的降維

Wine數(shù)據(jù)集共有178個(gè)樣本,每一類葡萄酒的樣本數(shù)量分別為59、71、48。3種葡萄酒的類標(biāo)簽分別表示為1、2、3。為了觀察不同特征的取值的差異性,表1給出所有樣本的13個(gè)特征的均值(m)和標(biāo)準(zhǔn)差(σ)。

表1 Wine數(shù)據(jù)集全部樣本的13個(gè)特征均值與標(biāo)準(zhǔn)差

從表1可以看出,特征x8和特征x13的均值之間相差達(dá)2 064倍,而標(biāo)準(zhǔn)差之間相差達(dá)2 529倍。這反映了不同特征所包含的信息是不同的。如果考慮所有特征,則會(huì)給計(jì)算帶來(lái)大的負(fù)擔(dān)。因此,利用LDA對(duì)Wine數(shù)據(jù)集進(jìn)行降維,以找出對(duì)聚類最具有辨別性的少數(shù)幾個(gè)特征。

首先對(duì)Wine數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化預(yù)處理,然后對(duì)每一類葡萄酒的13個(gè)特征,計(jì)算出其相對(duì)應(yīng)的均值向量(mv),結(jié)果如表2所示。

表2 標(biāo)準(zhǔn)化后Wine數(shù)據(jù)的均值向量

構(gòu)造矩陣SB和SW并計(jì)算增廣矩陣G,對(duì)其進(jìn)行分解,可獲得特征值、特征向量。將特征值按照由大到小的次序排列,結(jié)果如表3所示。

表3 降序排列的12個(gè)特征值

第13個(gè)特征值為0。從表3可以看出,從第3到第12個(gè)特征值雖然不為0,這是由于Python語(yǔ)言浮點(diǎn)數(shù)的表現(xiàn)形式,但實(shí)際上它們?nèi)≈刀紴?。換句話說(shuō),除了前2個(gè)特征值是明顯的非零值之外,其余特征值均為0。

在LDA中,特征向量代表與聚類有關(guān)的辨別信息,其內(nèi)容稱為可辨別性(discriminability)。為了測(cè)度每個(gè)特征向量所包含的辨別性信息,將特征值按照降序排列,并按照同樣次序繪制出對(duì)應(yīng)的線性辨別量(即特征向量)以及累計(jì)(cumulative)的可辨別性的圖形,其結(jié)果如圖8所示。

圖8 Wine數(shù)據(jù)集13個(gè)特征的可辨別性

從圖8可以看出,僅前2個(gè)特征向量就獲得了Wine數(shù)據(jù)集累計(jì)100%的辨別信息。因此,把這2個(gè)特征向量列疊加起來(lái)即可得到變換矩陣W。

利用變換矩陣W將原始的13維Wine數(shù)據(jù)X進(jìn)行變換:Xsub=XW,則得到新的2維特征子空間。數(shù)據(jù)Xsub在2維空間的散點(diǎn)圖如圖9所示。

圖9 數(shù)據(jù)集Xsub在2維子空間的散點(diǎn)

從圖9可以看出,由2個(gè)線性辨別量(linear discriminant)構(gòu)成的2維特征子空間中,變換后的數(shù)據(jù)Xsub形成了3個(gè)自然的數(shù)據(jù)簇,且各聚類之間是完全可分離的。這意味著利用2個(gè)線性辨別量進(jìn)行聚類分析也不會(huì)損失原本數(shù)據(jù)的有關(guān)信息,即本文采用的LDA對(duì)數(shù)據(jù)的降維是非常有效的。

3.2.3 降維后數(shù)據(jù)集的聚類分析

在2維的數(shù)據(jù)集Xsub基礎(chǔ)上,利用K-均值算法對(duì)其進(jìn)行聚類分析。這里僅考慮算法的指定參數(shù)K與數(shù)據(jù)集原始聚類數(shù)量是否相等2種情況。

1) 指定聚類數(shù)與數(shù)據(jù)固有聚類數(shù)相同

當(dāng)正確地設(shè)置K-均值算法的聚類數(shù)量為K=3時(shí),對(duì)變換后的數(shù)據(jù)Xsub進(jìn)行聚類,其結(jié)果的散點(diǎn)圖和輪廓系數(shù)如圖10和圖11所示。

圖10 在給定K=3時(shí)數(shù)據(jù)Xsub的聚類結(jié)果

圖11 在給定K=3時(shí)數(shù)據(jù)Xsub聚類的輪廓系數(shù)

從圖10可以看出,3個(gè)聚類的質(zhì)心被準(zhǔn)確地定位在每一堆數(shù)據(jù)的中心。從圖11也可以看出,3個(gè)聚類的輪廓尺寸略有不同,這是由于3種葡萄酒的樣本數(shù)量各不相同所致。但從總體上來(lái)看,3個(gè)聚類的輪廓具有大致相同的長(zhǎng)度和寬度,表現(xiàn)為相互之間較為協(xié)調(diào)。另外,從圖11還可以看出,數(shù)據(jù)集Xsub全部樣本的平均輪廓系數(shù)值接近于0.7,說(shuō)明聚類質(zhì)量較高。

小結(jié):綜合圖10和圖11的聚類結(jié)果可知,對(duì)Wine數(shù)據(jù)集采用LDA降維后,在2維的特征子空間上,若指定K-均值算法的參數(shù)K等于數(shù)據(jù)集的固有聚類數(shù)量,則聚類效果很好。

2) 指定聚類數(shù)與數(shù)據(jù)固有聚類數(shù)不同

盡管Wine數(shù)據(jù)集本身具有類標(biāo)簽,即聚類數(shù)量事先是已知的。但在實(shí)際應(yīng)用中,一般的數(shù)據(jù)集的聚類結(jié)構(gòu)是無(wú)法得到的,因此對(duì)于未知的聚類數(shù)量的確定(估計(jì))并不容易。

如果對(duì)K-均值算法指定的聚類數(shù)量K與數(shù)據(jù)集Xsub本身的聚類數(shù)量不相符,例如:假定設(shè)置算法的參數(shù)K=4,則對(duì)應(yīng)的聚類結(jié)果的散點(diǎn)圖以及輪廓系數(shù)如圖12和圖13所示。

圖12 在給定K=4時(shí)數(shù)據(jù)Xsub的聚類結(jié)果

圖13 在給定K=4時(shí)數(shù)據(jù)Xsub聚類的輪廓系數(shù)

從圖12可以看出,左上角數(shù)據(jù)被算法強(qiáng)制地劃分為2個(gè)聚類。這種劃分造成了聚類結(jié)構(gòu)的復(fù)雜化,使得對(duì)其結(jié)果的解釋更為困難。

從圖13可以看出,Cluster1和Cluster4的輪廓尺寸明顯小于其他2個(gè)聚類的輪廓,這正是反映了圖12中被強(qiáng)制劃分成2個(gè)新的聚類所對(duì)應(yīng)的輪廓。另外,在圖13中,所有樣本的平均輪廓系數(shù)也被降低到小于0.6,與圖11相比較,平均輪廓系數(shù)大約降低了10%左右,即聚類質(zhì)量變差。

小結(jié):綜合圖12和圖13的結(jié)果可知,若指定K-均值算法的參數(shù)K不等于數(shù)據(jù)集Xsub的固有聚類數(shù)量,則聚類效果明顯惡化。

從以上對(duì)現(xiàn)實(shí)數(shù)據(jù)集Wine的仿真可知,在未知數(shù)據(jù)集固有聚類結(jié)構(gòu)的情況下,估計(jì)的聚類數(shù)量是否正確,直接決定聚類的效果和聚類的質(zhì)量。

4 結(jié)論

為了解決劃分聚類(經(jīng)典的K-均值)算法需要用戶事先指定聚類數(shù)量的缺陷,本文進(jìn)行了相關(guān)的研究。對(duì)于算法的隨機(jī)初始化問(wèn)題,利用最小-最大規(guī)則對(duì)其進(jìn)行改進(jìn),避免算法出現(xiàn)空聚類并確保數(shù)據(jù)的可分離性。對(duì)于現(xiàn)實(shí)世界真實(shí)的數(shù)據(jù)集,利用標(biāo)準(zhǔn)化預(yù)處理使之服從正態(tài)分布,并利用監(jiān)督的線性判別分析LDA用于抽取高維數(shù)據(jù)中所包含對(duì)聚類最具辨別性的特征,以實(shí)現(xiàn)數(shù)據(jù)降維。通過(guò)計(jì)算各聚類的輪廓系數(shù)并比較其尺寸,利用輪廓分析法評(píng)估聚類質(zhì)量。本文方案的主要貢獻(xiàn)體現(xiàn)在:對(duì)于復(fù)雜的數(shù)據(jù)集,由于估計(jì)準(zhǔn)確的聚類數(shù)量是很困難的,為此可采用LDA對(duì)數(shù)據(jù)降維,通過(guò)估計(jì)未知數(shù)據(jù)集的聚類數(shù)量K的大致范圍,然后對(duì)不同K值的聚類質(zhì)量進(jìn)行可視化檢查,從而為各種劃分聚類算法提供原數(shù)據(jù)的固有聚類數(shù)量。