肖枝洪，于 浩，王一超

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

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

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

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

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

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

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

1 基于動態(tài)離差平方和機器學習算法

1.1 動態(tài)離差平方和準則

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

表1 p個指標n個樣品

易知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ù)的劃分是基于整個類的離差平方和來判斷的，是一種全局最優(yōu)的聚類方法。在后面的例子中可以看到：它可以對K-means的聚類結果進行改進，使聚類結果更加精確。

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

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

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

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

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

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

表3 16個樣本2個指標的觀測值

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

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

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

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

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

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

2 實例分析

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

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

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

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

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

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

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

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

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

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

表12 兩種算法運算時間比較

3 結束語

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

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