高魯棒性的改進(jìn)最小生成樹(shù)聚類算法

沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院 李云帆 陳禹銘 文 峰

聚類是一種應(yīng)用廣泛的無(wú)監(jiān)督學(xué)習(xí)任務(wù)，目前的主流聚類方法種類繁多，但在實(shí)際應(yīng)用中需要根據(jù)數(shù)據(jù)分布和具體要求選擇聚類方法或設(shè)定超參數(shù)，十分不便。針對(duì)這一問(wèn)題，提出了一種改進(jìn)的最小生成樹(shù)聚類算法，該算法通過(guò)充分利用簇規(guī)模信息，增強(qiáng)了其抗噪聲的能力，同時(shí)可以處理不同形狀、不同密度的簇。這種方法只需要設(shè)定聚類簇?cái)?shù)一個(gè)超參數(shù)，此外還有易于實(shí)現(xiàn)、可解釋性強(qiáng)等優(yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)算法具有更強(qiáng)的魯棒性，在多種測(cè)試集上的聚類效果明顯優(yōu)于其他傳統(tǒng)方法，并在圖像分割應(yīng)用上仍有著優(yōu)秀的表現(xiàn)。

聚類是一種十分常見(jiàn)的無(wú)監(jiān)督學(xué)習(xí)問(wèn)題。根據(jù)算法思想不同，聚類算法可以分為很多種，如K-Means等基于劃分的方法和DBSCAN等基于密度的方法。最小生成樹(shù)(MST)聚類是一種基于圖論的聚類方法，算法等價(jià)于使用各節(jié)點(diǎn)間的相似度對(duì)所有數(shù)據(jù)構(gòu)建最小生成樹(shù)，再將相似度大于閾值的邊刪去，從而得到一片森林，森林中每顆樹(shù)視為聚類結(jié)果中的一個(gè)簇。

經(jīng)典的最小生成樹(shù)聚類算法具有分割閾值難以確定、易受離群點(diǎn)干擾、難以處理變密度數(shù)據(jù)等缺點(diǎn)。針對(duì)這些問(wèn)題，本文提出基于簇規(guī)模信息的改進(jìn)MST聚類算法，該算法只需給定聚類簇?cái)?shù)，便可以通過(guò)計(jì)算并修改各邊權(quán)重的方式得到自適應(yīng)抗噪聲的聚類結(jié)果。最終通過(guò)在模擬數(shù)據(jù)集和圖像分割應(yīng)用上的實(shí)驗(yàn)，證明了該方法的有效性。

1 算法原理與設(shè)計(jì)

1.1 基于簇規(guī)模信息的修正系數(shù)

聚類算法需要克服的一大困難對(duì)噪聲點(diǎn)的處理。

針對(duì)這一問(wèn)題，本文的方法是引入平衡度修正系數(shù)的概念，通過(guò)對(duì)邊權(quán)值的修改，來(lái)控制聚類效果，避免產(chǎn)生相對(duì)容量極小的類。生成樹(shù)聚類中，每當(dāng)分割一條邊，均會(huì)將一個(gè)簇劃分為兩個(gè)簇，設(shè)兩個(gè)簇的容量分別為m和n，則平衡度修正系數(shù)可以由兩者歸一化后的調(diào)和平均數(shù)開(kāi)根號(hào)得到。記m和n的調(diào)和平均數(shù)為hm(m,n)，平衡度修正系數(shù)為Be，則有：

當(dāng)m與n的和確定時(shí)，該函數(shù)圖像如圖1所示。可以看出，該函數(shù)具有良好性質(zhì)，當(dāng)兩個(gè)簇容量相差較大時(shí)，平衡度修正系數(shù)較小，修正后的邊權(quán)值降低，更不易于被分割，從而在一定程度上自適應(yīng)地減少噪聲干擾。

圖1 平衡度修正系數(shù)與簇大小的關(guān)系

經(jīng)典最小生成樹(shù)聚類方法不能處理變密度數(shù)據(jù)，容易將噪聲點(diǎn)單獨(dú)分為一類。對(duì)于這一問(wèn)題，本文的解決方案是引入正比于當(dāng)前分割簇容量的權(quán)重，稱為簇容量修正系數(shù)，這使算法更傾向于分割大的簇。設(shè)遍歷森林時(shí)當(dāng)前邊所屬簇的容量為C，該樹(shù)相當(dāng)于聚類過(guò)程中的一個(gè)簇，則當(dāng)前邊的簇容量修正系數(shù)Se為：

相比于傳統(tǒng)最小生成樹(shù)聚類算法，改進(jìn)后的算法使用修正后的邊權(quán)值We

'進(jìn)行聚類。修正后的邊權(quán)值由原邊權(quán)值與兩個(gè)修正系數(shù)相乘求得，即：

1.2 算法流程

算法1：基于簇規(guī)模信息的改進(jìn)最小生成樹(shù)聚類算法

輸入：聚類簇?cái)?shù)N，樣本點(diǎn)集X

輸出：標(biāo)簽列表Labels

步驟：

Step 1：計(jì)算樣本點(diǎn)集X的相似度矩陣，構(gòu)造最小生成樹(shù)。

Step 2：遍歷最小生成樹(shù)的所有邊，根據(jù)公式(3)計(jì)算修正后的邊權(quán)值，并刪去權(quán)值最大的邊，增加一個(gè)簇。

Step 3：若簇?cái)?shù)小于設(shè)定數(shù)，則重復(fù)Step 2，直到簇?cái)?shù)達(dá)到目標(biāo)數(shù)時(shí)聚類完畢，得到Labels。

2 實(shí)驗(yàn)

2.1 模擬數(shù)據(jù)集實(shí)驗(yàn)

以下是多個(gè)不同模擬數(shù)據(jù)集上對(duì)比實(shí)驗(yàn)的結(jié)果。本文將改進(jìn)算法同小批量K-Means、DBSCAN、經(jīng)典最小生成樹(shù)聚類等算法進(jìn)行對(duì)比實(shí)驗(yàn)，其中所有算法均已進(jìn)行超參數(shù)調(diào)優(yōu)，部分算法規(guī)定當(dāng)簇內(nèi)樣本數(shù)小于最小簇容量時(shí)視為噪聲點(diǎn)，實(shí)驗(yàn)結(jié)果如圖2所示，最右側(cè)一列為改進(jìn)算法結(jié)果。

圖2 不同數(shù)據(jù)集上的聚類實(shí)驗(yàn)結(jié)果

不難看出，改進(jìn)后的最小生成樹(shù)聚類算法在眾多數(shù)據(jù)集上均具有非常強(qiáng)的優(yōu)越性，可以擬合不同形狀或不同密度的簇，適應(yīng)性極強(qiáng)。缺點(diǎn)是速度略微慢于大部分聚類算法，經(jīng)測(cè)試，這主要是由計(jì)算樣本點(diǎn)相似度矩陣導(dǎo)致的。

2.2 圖像分割實(shí)驗(yàn)

本文還將改進(jìn)算法應(yīng)用到了圖像分割領(lǐng)域。對(duì)于一張位圖，可以將其中每個(gè)像素點(diǎn)看作一個(gè)五維向量，前兩維儲(chǔ)存位置信息，后三位儲(chǔ)存RGB值（對(duì)于四通道圖像則為六維）。實(shí)際處理時(shí)可在兩者間適當(dāng)?shù)募訖?quán)或進(jìn)行歸一化。經(jīng)實(shí)驗(yàn)驗(yàn)證，改進(jìn)MST算法具有一定的無(wú)監(jiān)督圖像分割能力，分割結(jié)果如圖3所示。其中左側(cè)為圖像原圖，右側(cè)為圖像分割后的結(jié)果。

圖3 圖像分割實(shí)驗(yàn)結(jié)果

結(jié)論：本文提出了一種基于簇規(guī)模信息的改進(jìn)最小生成樹(shù)聚類算法，并在模擬數(shù)據(jù)集和實(shí)際應(yīng)用中進(jìn)行充分實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該方法聚類效果明顯優(yōu)于K-Means，DBSCAN等傳統(tǒng)聚類算法，且僅需要設(shè)定聚類簇?cái)?shù)作為超參數(shù)，便可以在聚類中適應(yīng)不同形狀或密度的簇，同時(shí)還具備一定抗噪聲能力，在多種數(shù)據(jù)集上與圖像分割應(yīng)用中均具有很好的表現(xiàn)。