基于動(dòng)態(tài)離差平方和準(zhǔn)則的無監(jiān)督機(jī)器學(xué)習(xí)

肖枝洪，于 浩，王一超

(重慶理工大學(xué) 理學(xué)院， 重慶 400054)

經(jīng)典K-means算法具體流程[8]如下：

1) 確定類別個(gè)數(shù)，再選取初始種子,計(jì)算各個(gè)樣品與各個(gè)初始種子之間的距離。

2) 找出每個(gè)樣品與各個(gè)種子之間最短距離,按照最短距離原則將全部樣品劃分到相應(yīng)的類別中。

3) 再次計(jì)算每類重心,并將其作為新的種子,重復(fù)步驟1)。

4) 重復(fù)步驟2)、3),直到新的聚類結(jié)果與上一次相同,或者新的種子與上一次相同。

目前，對無監(jiān)督機(jī)器學(xué)習(xí)算法主要對經(jīng)典K-means 算法初始種子的選取進(jìn)行研究。如馬福民等[9]提出了一種基于局部密度自適應(yīng)度量的粗糙K-means聚類算法；楊菊蜻等[10]提出一種基于改進(jìn) BA法的K-means算法，實(shí)現(xiàn)聚類結(jié)果的優(yōu)化并提高聚類質(zhì)量；薛衛(wèi)等[11]采用可伸縮空間密度的相似性距離來度量數(shù)據(jù)點(diǎn)間的相似度的K-means 算法；于佐軍等[12]提出一種改進(jìn)的人工蜂群K-means算法，引入算術(shù)交叉操作并利用最優(yōu)解指導(dǎo)搜索方向來提高K-means算法收斂的速度；田詩宵等[13]構(gòu)造局部密度指標(biāo)，并根據(jù)數(shù)據(jù)樣本的局部密度分布情況，選取處在密度的峰值點(diǎn)作為初始種子以此來改進(jìn)K-means算法；謝修娟等[14]提出一種基于樣本密度選取初始種子的K-means改進(jìn)算法；張陽等[15]通過設(shè)定K-means算法的終止條件的標(biāo)準(zhǔn)值以此減少算法迭代次數(shù)；楊玉梅[16]通過采用信息熵對樣本數(shù)據(jù)賦權(quán)進(jìn)而調(diào)整初始種子的選取以此達(dá)到優(yōu)化K-means算法的效果；王茜等[17]基于“合并與分裂”思想，引入點(diǎn)密度概念和最小支撐樹聚類算法提出了一種改進(jìn)的K-means聚類算法；劉芝怡等[18]提出了一種利用最大距離等分策略來選取初始聚類中心的K-means 改進(jìn)算法；王春龍等[19]提出一種基于隱含狄利克雷分概率模型的初始種子選取的K-means改進(jìn)算法；此外還有袁方、賴玉霞等[20-22]分別采用不同的樣本密度的計(jì)算方法來估計(jì)樣本點(diǎn)的密度，從而選擇相互距離最遠(yuǎn)并且處在高密度區(qū)域的K個(gè)樣本作為K-means 算法的初始種子。綜上，相關(guān)的研究多是將經(jīng)典K-means與其他方法相結(jié)合得到的改進(jìn)算法或者運(yùn)用不同方法選取初始種子的改進(jìn)方法，而針對劃分標(biāo)準(zhǔn)進(jìn)行改進(jìn)的方法相對較少，所以本文在經(jīng)典K-means算法步驟中第2步的劃分標(biāo)準(zhǔn)基礎(chǔ)上，提出了一種新的劃分標(biāo)準(zhǔn)，也就是使得每次調(diào)整后的類內(nèi)離差平方和遞減，從而對經(jīng)典K-means 算法進(jìn)行改進(jìn)，使得聚類結(jié)果更加準(zhǔn)確。

1 基于動(dòng)態(tài)離差平方和機(jī)器學(xué)習(xí)算法

1.1 動(dòng)態(tài)離差平方和準(zhǔn)則

假設(shè)已知以p個(gè)變量x1,x2,…,xp為指標(biāo)的n個(gè)樣品如表1所示，可以劃分為C1,…,CK類如表2如示。

表1 p個(gè)指標(biāo)n個(gè)樣品

易知T(s)=T,T(s)=W(s)+A(s)。

那么，第s+1次調(diào)整后的類內(nèi)離差平方和W(s+1)為：

W(s)+Δlm

(1)

K-means算法的劃分原理要求

(2)

由DSSD算法可知，相對K-means算法而言，對數(shù)據(jù)的劃分是基于整個(gè)類的離差平方和來判斷的，是一種全局最優(yōu)的聚類方法。在后面的例子中可以看到：它可以對K-means的聚類結(jié)果進(jìn)行改進(jìn)，使聚類結(jié)果更加精確。

1.2 動(dòng)態(tài)離差平方和算法

動(dòng)態(tài)離差平方和法算法流程：

1) 確定K個(gè)初始種子,并將全部觀測聚類成為K個(gè)類,其中第j類的觀測數(shù)記為nj,j=1,2,…,K。

4) 直至所有Δkl均大于0時(shí)，停止調(diào)整，得到最終的聚類結(jié)果。

1.3 DSSD算法與K-means算法比較

假設(shè)有16組觀測數(shù)據(jù)如表3所示，并從表中選取x(3)、x(4)、x(15)為初始種子,采用K-means無監(jiān)督機(jī)器學(xué)習(xí)算法進(jìn)行聚類,得到結(jié)果如表4所示。

表3 16個(gè)樣本2個(gè)指標(biāo)的觀測值

表4 K-means算法聚類結(jié)果及其類內(nèi)離差平方和

對表4的聚類結(jié)果計(jì)算其各類的類重心為：xC1=(1.333,4.333)，xC2=(4.75,2.5),xC3=(-1.778,0.111)，并將xC1、xC2、xC3作為初始種子，采用DSSD法進(jìn)行聚類，得到結(jié)果如表5所示。

表5 DSSD聚類結(jié)果及其類內(nèi)離差平方和

從表5中可以看出經(jīng)動(dòng)態(tài)離差平方法聚類后，將表4中劃分到C3類中的x(12)調(diào)整到了C1類中，并且類內(nèi)離差平方和相比表4中類內(nèi)離差平方和有所減小。這說明了基于動(dòng)態(tài)離差平方和為劃分依據(jù)的無監(jiān)督機(jī)器學(xué)習(xí)算法可以對K-means算法的結(jié)果再次進(jìn)行調(diào)整。

再直接采用K-means算法的初始種子x(3),x(4),x(15)，作為動(dòng)態(tài)離差平方和法的初始種子進(jìn)行聚類，得到結(jié)果與表5結(jié)果相同。其聚類結(jié)果不隨著初始種子的改變而改變，聚類結(jié)果穩(wěn)定。

由此看出，采用動(dòng)態(tài)離差平方和法，對K-means算法的結(jié)果進(jìn)行了進(jìn)一步調(diào)整，而且調(diào)整后類內(nèi)離差平方和有所下降，說明本文所提出的DSSD算法優(yōu)于K-means算法。上述分析解釋了DSSD算法相較于K-means算法的精確性，在下文中將進(jìn)一步對本文算法的性能進(jìn)行比較。

2 實(shí)例分析

本文采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫[23]中的4個(gè)常用測試無監(jiān)督機(jī)器學(xué)習(xí)算法的數(shù)據(jù)集如表6所示，并運(yùn)用表中的數(shù)據(jù)來驗(yàn)證本文所提算法的性能，并與K-means算法的速度進(jìn)行比較。

表6 UCI數(shù)據(jù)集描述

對表6中的4組數(shù)據(jù)集分別采用K-means無監(jiān)督機(jī)器學(xué)習(xí)與DSSD法進(jìn)行聚類，得到結(jié)果分別為表7～10所示。其中Cj為所對應(yīng)數(shù)據(jù)集中包含的樣品個(gè)數(shù),j=1,2,…,8。

表7 Iris數(shù)據(jù)集聚類結(jié)果比較

表8 Wine數(shù)據(jù)集聚類結(jié)果比較

表9 Zoo數(shù)據(jù)集聚類結(jié)果比較

表10 Ecoli數(shù)據(jù)集聚類結(jié)果比較

從表7～10的結(jié)果可以看出：本文的DSSD算法的類內(nèi)離差平方和均小于K-means無監(jiān)督機(jī)器學(xué)習(xí)算法，說明了在大樣本情形下，DSSD算法仍優(yōu)于K-means算法。為了進(jìn)一步驗(yàn)證DSSD算法相對K-means無監(jiān)督機(jī)器學(xué)習(xí)算法的性能，遂采用外部聚類評價(jià)法中的調(diào)整蘭德指數(shù)(adjusted rand index)進(jìn)行評判。調(diào)整蘭德指數(shù)是在數(shù)據(jù)集樣本分類已知情況下，對待測聚類算法的聚類性能進(jìn)行評價(jià)的有效指標(biāo)[24-26]。結(jié)果如表11所示。

調(diào)整蘭德指數(shù)的取值范圍為[-1,1]，其值越接近于1意味著聚類結(jié)果與真實(shí)情況越吻合，從表11中的結(jié)果可以看出：DSSD算法的調(diào)整蘭德指數(shù)均大于K-means無監(jiān)督機(jī)器學(xué)習(xí)算法的調(diào)整蘭德指數(shù)，說明DSSD算法相較于K-means算法性能更高。

表11 兩種算法調(diào)整蘭德指數(shù)

表12 兩種算法運(yùn)算時(shí)間比較

3 結(jié)束語

根據(jù)上述兩種方法機(jī)器學(xué)習(xí)結(jié)果的對比可以看出:DSSD法的無監(jiān)督機(jī)器學(xué)習(xí)算法在K-means算法結(jié)果之上又再次對其結(jié)果進(jìn)行了“精修”，無論是從聚類后類內(nèi)離差平方和還是調(diào)整蘭德指數(shù)來判斷，均可說明基于DSSD算法的聚類結(jié)果更具說服力。同時(shí)，DSSD算法的一個(gè)更具有吸引力的地方是聚類結(jié)果穩(wěn)定，不依賴于初始種子。

但DSSD法也有不盡人之處，一方面，仍然需要事先確定類的個(gè)數(shù)，也就是K值依舊需要人工進(jìn)行選取,不能動(dòng)態(tài)改變類的個(gè)數(shù)；另一方面就是速度較慢。本文所提出的DSSD算法將在后續(xù)繼續(xù)進(jìn)行研究，對之進(jìn)行優(yōu)化,能有效改進(jìn)類的動(dòng)態(tài)選取方法，提高速度，減少運(yùn)行時(shí)間。