張倪妮，葛洪偉+

1.江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室（江南大學(xué)），江蘇無(wú)錫214122

2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫214122

聚類分析是數(shù)據(jù)挖掘中的重要技術(shù)。它將一組沒(méi)有標(biāo)記的對(duì)象分組，使具有高度相似性的對(duì)象為一組。經(jīng)過(guò)數(shù)十年的發(fā)展，研究人員提出了大量的聚類算法[1-5]。其中最經(jīng)典的是K-均值聚類算法[1]。K-均值算法簡(jiǎn)單高效，其基于平方誤差的劃分方法在超球面簇中表現(xiàn)良好。但是它存在對(duì)初始點(diǎn)的選取敏感并且不擅長(zhǎng)識(shí)別非凸模式簇的問(wèn)題。

針對(duì)第一個(gè)問(wèn)題，相應(yīng)的改進(jìn)算法有使初始聚類中心間距離盡可能大的K-means++[6]；基于蒙特卡洛取樣進(jìn)行初始化的方法AFKMC2[7]（assumption-freek-Markov chain Monte Carlo）；基于采樣和密度峰值選擇初始中心的方法SDPC[8]（sampled-clustering by fast search and find of density peaks）等。這些算法在一定程度上提高了K-均值算法聚類效果的穩(wěn)定性，但是這些方法的聚類結(jié)果還是因?yàn)槌跏键c(diǎn)的選取存在一定的波動(dòng)。因此，K-均值類的算法如何選取初始中心仍是一個(gè)有意義的課題。

針對(duì)第二個(gè)問(wèn)題，考慮到在很多實(shí)際應(yīng)用中，每個(gè)類包含很多子類，不能用一個(gè)聚類原型來(lái)表示，出現(xiàn)了兩類解決方法。第一類是非線性的聚類方法，例如基于核的聚類和譜聚類[9-13]；第二類是將每個(gè)類設(shè)置多原型的聚類方法，例如文獻(xiàn)[14-19]。2019 年Nie 等人在ACM SIGKDD 上提出的指定k個(gè)聚類的多均值聚類算法（multiple-means clustering method with specifiedK，KMM）[20]屬于第二類方法。該算法不同于其他同類方法，它將含多個(gè)次聚類中心的數(shù)據(jù)分配給特定的k類變成一個(gè)優(yōu)化問(wèn)題，交替更新數(shù)據(jù)對(duì)次聚類中心的劃分和k個(gè)類的劃分。這種方法解決了K-均值算法在非凸模式簇上的劣勢(shì)，并且比同類方法用時(shí)更少，聚類效果更好。

然而KMM 算法作為K-均值算法的一種拓展，同樣存在對(duì)初始聚類原型的選取敏感，聚類結(jié)果不穩(wěn)定的問(wèn)題。針對(duì)上述問(wèn)題，本文提出了一種穩(wěn)定的K-多均值聚類方法。該算法先計(jì)算出每個(gè)數(shù)據(jù)樣本的最鄰近樣本，根據(jù)最鄰近關(guān)系構(gòu)造鄰接矩陣，得到關(guān)于數(shù)據(jù)樣本的圖，將圖中每個(gè)連通分支的均值點(diǎn)作為初始聚類原型。因?yàn)檫@種方法用到了每個(gè)數(shù)據(jù)樣本的最鄰近樣本來(lái)尋找初始原型，所以將算法命名為FN-KMM（multiple-means clustering method with specifiedKby using first neighbor）。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)證明，與KMM 算法相比，F(xiàn)N-KMM的聚類結(jié)果非常穩(wěn)定且效果更優(yōu)。

1 KMM 算法及其缺陷分析

KMM 算法[20]的核心思想是將聚類原型的選取和數(shù)據(jù)對(duì)原型的劃分變?yōu)橐粋€(gè)優(yōu)化問(wèn)題，將數(shù)據(jù)和原型存在k個(gè)簇類作為限制條件加入到優(yōu)化問(wèn)題中，通過(guò)對(duì)優(yōu)化問(wèn)題的求解得到聚類結(jié)果。

令X=[x1,x2,…,xn]T∈Rn×d為數(shù)據(jù)樣本矩陣，A=[a1,a2,…,am]T∈Rm×d為原型矩陣，第i個(gè)數(shù)據(jù)樣本xi與第j個(gè)原型aj相連的概率為sij。通常情況下，xi與aj的距離越小，sij的值越大。因此KMM[20]將選取原型并將n個(gè)數(shù)據(jù)樣本分配給它的相鄰原型的問(wèn)題寫為如下形式：

根據(jù)文獻(xiàn)[21]，KMM[20]將數(shù)據(jù)樣本與原型存在k個(gè)簇類轉(zhuǎn)換為限制條件添加到問(wèn)題（1）中，得到問(wèn)題（3）：

為了方便求解，KMM 算法[20]對(duì)限制條件適當(dāng)放寬，并根據(jù)文獻(xiàn)[22]中的定理得到了最終的優(yōu)化問(wèn)題（4）。

最后KMM[20]通過(guò)交替迭代的求解方法，完成對(duì)數(shù)據(jù)樣本的聚類。

KMM 算法把多均值聚類問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題使得它的性能和速度比其他的多均值聚類算法更具優(yōu)越性，但它存在K-均值類的算法普遍存在的對(duì)初始點(diǎn)選取敏感的問(wèn)題，原型的選取極大影響了聚類的結(jié)果。

2 FN-KMM 算法

針對(duì)KMM 算法受初始原型的影響，導(dǎo)致聚類結(jié)果不穩(wěn)定的問(wèn)題，提出了FN-KMM 算法，這一章是對(duì)FN-KMM 算法的詳細(xì)介紹。

2.1 初始次類原型的選取

通常情況下屬于同一次類的數(shù)據(jù)樣本間的距離要比屬于不同次類的數(shù)據(jù)樣本間的距離更小，且數(shù)據(jù)樣本與它最鄰近的數(shù)據(jù)樣本屬于同次聚類的概率最大。因此FN-KMM基于最鄰近關(guān)系來(lái)選擇初始原型。

定義2表示距離第i個(gè)數(shù)據(jù)樣本最近的數(shù)據(jù)樣本。

定義3Z∈Rn×n為基于數(shù)據(jù)樣本的最鄰近關(guān)系構(gòu)造的鄰接矩陣，Z中各元素的定義為：

計(jì)算所有樣本與其他樣本間的歐式距離。根據(jù)定義2 和定義3 得到鄰接矩陣Z，構(gòu)造圖G=(V,E)，其中V是頂點(diǎn)（數(shù)據(jù)樣本）集合，E是邊的集合，Z(i,j)=1代表了第i個(gè)數(shù)據(jù)樣本與第j個(gè)數(shù)據(jù)樣本相連。記Cj為圖G的一個(gè)連通分支，則可得到聚類原型aj=

KMM 算法根據(jù)用戶輸入的參數(shù)m或者默認(rèn)，隨機(jī)選取m個(gè)原型。用戶很難估計(jì)出m的值，而默認(rèn)的雖然有一定的合理性，反映了原型數(shù)目與聚類數(shù)和樣本數(shù)的關(guān)系，但忽略了數(shù)據(jù)樣本間的關(guān)系。FN-KMM 算法選取的初始原型其數(shù)目和位置不僅反映了樣本的數(shù)量還反映了數(shù)據(jù)樣本間的關(guān)系。原型數(shù)目不需要人為設(shè)定而是由基于最鄰近關(guān)系構(gòu)造的圖G的連通分支數(shù)來(lái)決定，當(dāng)兩個(gè)樣本中的一個(gè)樣本為另一個(gè)的最近樣本時(shí)兩個(gè)樣本相連，這樣嚴(yán)苛的限制條件，可以保證構(gòu)造的圖有足夠多的連通分支，避免了得到的原型數(shù)少于聚類數(shù)的情況。原型的位置是由圖G中連通分支的點(diǎn)集決定，兩個(gè)數(shù)據(jù)點(diǎn)距離越近屬于同一類的概率就越大，每個(gè)點(diǎn)的最鄰近點(diǎn)都屬于同一個(gè)連通分支的點(diǎn)集，取連通分支點(diǎn)集的均值點(diǎn)為原型，原型的位置要比隨機(jī)選取更合理。并且這種方法選取的初始原型不存在隨機(jī)性，從而保證了聚類結(jié)果的穩(wěn)定。

為了方便理解，用一個(gè)只有10個(gè)樣本的二維數(shù)據(jù)集來(lái)解釋選取初始原型的方法。數(shù)據(jù)集如圖1 所示。

Fig.1 Sample dataset圖1 數(shù)據(jù)集樣例

計(jì)算樣本數(shù)據(jù)間的歐式距離，得到每個(gè)數(shù)據(jù)樣本最鄰近的樣本，構(gòu)造如圖2（a）所示的鄰接矩陣Z，根據(jù)該矩陣可以構(gòu)造圖如圖2（b）所示。

Fig.2 Demo of looking for initial prototypes圖2 尋找初始原型的演示

2.2 求解優(yōu)化問(wèn)題

FN-KMM 在得到了初始原型后，可用交替迭代的方法來(lái)對(duì)優(yōu)化問(wèn)題（4）進(jìn)行求解[20]。下面是求解過(guò)程的具體描述。

2.2.1 固定A 并更新S、F

當(dāng)A固定后，問(wèn)題（4）轉(zhuǎn)化為問(wèn)題（6）如下：

問(wèn)題（6）同樣也可以用交替更新的方法來(lái)解決。當(dāng)S固定后，將F和D改寫成如下形式：

其中，U∈Rn×k，V∈Rm×k，DU∈Rn×n，DV∈Rm×m。問(wèn)題（6）可以被轉(zhuǎn)化為問(wèn)題（7）如下：

問(wèn)題（7）可以通過(guò)文獻(xiàn)[23]中提出的定理1 來(lái)解決。

定理1設(shè)A∈Rn×m，X∈Rn×k，Y∈Rm×k，且有問(wèn)題如下：

F更新后，固定F。問(wèn)題（6）轉(zhuǎn)變?yōu)閱?wèn)題（9）：

根據(jù)如下關(guān)系（10）：

因?yàn)閱?wèn)題（11）在不同的i之間是獨(dú)立的，所以可以分別對(duì)每個(gè)i解決問(wèn)題（12）如下：

2.2.2 固定S、F 并更新A

當(dāng)S、F固定以后，A可以根據(jù)式（15）來(lái)進(jìn)行更新。

當(dāng)A的賦值或數(shù)據(jù)樣本的次類劃分不再變化時(shí)，算法收斂，停止迭代更新。

2.3 FN-KMM 算法步驟

FN-KMM 算法流程簡(jiǎn)單描述如下：

步驟1通過(guò)計(jì)算數(shù)據(jù)樣本之間的距離來(lái)求每個(gè)樣本的最鄰近樣本。

步驟2根據(jù)式（5）求鄰接矩陣Z，構(gòu)造圖G，得到圖G中的m個(gè)連通分支。

步驟3計(jì)算m個(gè)連通分支的數(shù)據(jù)樣本均值，求得原型矩陣A∈Rm×d。

步驟4對(duì)每一個(gè)i，用文獻(xiàn)[12]的方法求解問(wèn)題（16），計(jì)算S的第i行。

步驟8對(duì)于每一個(gè)j，根據(jù)式（15）更新A的第j行。

步驟9重復(fù)步驟4～步驟8 直到收斂。

2.4 算法復(fù)雜度分析

假設(shè)聚類對(duì)象有n個(gè)樣本，d個(gè)維數(shù)。在尋找初始原型這一階段，時(shí)間復(fù)雜度主要是由計(jì)算樣本間的距離和使用kd-樹(shù)來(lái)獲得最鄰近樣本產(chǎn)生。因此，F(xiàn)N-KMM 算法在尋找初始原型階段的時(shí)間復(fù)雜度為O(nlogn+nd)。

更新F所需要的時(shí)間復(fù)雜度主要是由計(jì)算S～ 的奇異值分解產(chǎn)生，為O(m3+m2n)。更新S所需時(shí)間復(fù)雜度為O(nmk+nmlogm)。設(shè)交替更新S、F的迭代次數(shù)為t1。通常情況下，m3與logm的值較小因此迭代更新S、F的時(shí)間復(fù)雜度為O((nmk+m2n)t1)。根據(jù)式（16）可知，更新A所需時(shí)間復(fù)雜度為O(nmd)。

綜上，假設(shè)A參與了t2次迭代，那么FN-KMM算法總的時(shí)間復(fù)雜度為O(n((mk+m2)t1+md)t2+nlogn+nd)。

由文獻(xiàn)[20]可知KMM 算法的時(shí)間復(fù)雜度為O(n((md+mc+m2)t1+md)t2)。FN-KMM 雖然在選取初始原型的過(guò)程中比KMM 耗費(fèi)了更多時(shí)間，但是與KMM 一樣算法復(fù)雜度都是關(guān)于n的線性縮放，屬于一個(gè)量級(jí)。

2.5 算法收斂性分析

FN-KMM 算法的目標(biāo)函數(shù)可寫為式（17）的形式。

其中，S∈Ω可以看作是數(shù)據(jù)和原型可以被分為k個(gè)簇類的限制條件。S可看作EM（expectation-maximization algorithm）算法中的隱藏變量，A可看作其他參數(shù)。求解目標(biāo)函數(shù)的過(guò)程可看作EM 算法中交替更新隱藏變量與其他參數(shù)直至收斂的過(guò)程。EM算法的收斂性在文獻(xiàn)[24]中已經(jīng)給出了證明。綜上FN-KMM 算法是可收斂的。

3 實(shí)驗(yàn)與分析

這一章展示了FN-KMM 算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的表現(xiàn)，同時(shí)將FN-KMM 與KMM[20]、Kmeans[25]、KKmeans（Mercer kernelk-means）[26]、MEAP（multi-exemplar affinity propagation）[18]、K-MEAP（multiple exemplars affinity propagation with specifiedkclusters）[19]這些優(yōu)秀算法進(jìn)行對(duì)比。

3.1 聚類結(jié)果評(píng)價(jià)

實(shí)驗(yàn)中使用準(zhǔn)確率（Accuracy）、標(biāo)準(zhǔn)互信息（normalized mutual information，NMI）和純度（Purity）三個(gè)聚類評(píng)價(jià)指標(biāo)來(lái)對(duì)算法進(jìn)行對(duì)比。設(shè)C為真實(shí)聚類結(jié)果，W為算法得到的結(jié)果。準(zhǔn)確率的定義如下：

其中，map為最佳映射函數(shù)，可以將算法得到的標(biāo)簽與真實(shí)聚類標(biāo)簽變?yōu)橐灰挥成涞年P(guān)系。δ是指示函數(shù)，定義如下：

標(biāo)準(zhǔn)互信息的定義如下：

其中，I表示互信息，H表示信息熵。

純度的定義如下：

評(píng)價(jià)指標(biāo)Accuracy、NMI、Purity 的值越大，聚類性能越好，評(píng)價(jià)指標(biāo)的取值范圍是[0,1]。

3.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證FN-KMM 算法的性能，分別在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

3.2.1 人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

將FN-KMM 算法與KMM 算法分別在表1 中的4個(gè)人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

Table 1 4 artificial data sets表1 4 個(gè)人工數(shù)據(jù)集信息

表1 中，D1 由兩個(gè)團(tuán)狀簇和一個(gè)流形簇構(gòu)成；Aggregation 由6 個(gè)團(tuán)狀簇構(gòu)成，其中個(gè)別團(tuán)狀簇相互連接；Zelink1 由兩個(gè)團(tuán)狀簇和一個(gè)流行簇構(gòu)成；Zelink3 由一個(gè)團(tuán)狀簇和兩個(gè)環(huán)狀簇構(gòu)成。

圖3 和圖4 分別為KMM 算法和FN-KMM 在4 個(gè)人工數(shù)據(jù)集上的表現(xiàn)。

Fig.3 Clustering results on artificial data sets by KMM圖3 KMM 在人工數(shù)據(jù)集的聚類結(jié)果

圖3 和圖4 中紅點(diǎn)表示的是原型，不同類別的樣本點(diǎn)用不同顏色來(lái)區(qū)分。KMM 隨機(jī)選取原型的方式導(dǎo)致了聚類結(jié)果波動(dòng)很大。當(dāng)原型選取不佳時(shí)，如圖3 所示算法不能得到正確的聚類結(jié)果。而FNKMM 通過(guò)數(shù)據(jù)樣本的最鄰近關(guān)系尋找原型，不僅結(jié)果穩(wěn)定，沒(méi)有任何波動(dòng)，并且如圖4 所示可以得到正確的聚類結(jié)果。

3.2.2 真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

為了進(jìn)一步驗(yàn)證FN-KMM 算法性能，分別將K-means[25]、KKmeans[26]、MEAP[18]、K-MEAP[19]、KMM[20]和FN-KMM 在表2 中的真實(shí)數(shù)據(jù)集上進(jìn)行展示。

Fig.4 Clustering results on artificial data sets by FN-KMM圖4 FN-KMM 在人工數(shù)據(jù)集的聚類結(jié)果

Table 2 6 real data sets表2 6 個(gè)真實(shí)數(shù)據(jù)集信息

表2的數(shù)據(jù)集中BinAlpha與Palm為圖像數(shù)據(jù)集，256個(gè)屬性值是圖片的像素值，除了Ecoil[27]與Abalone[27]有文本屬性需轉(zhuǎn)換為離散值外，其他數(shù)據(jù)集的屬性均為連續(xù)值。為了取得更好的聚類效果，數(shù)據(jù)集的屬性值在轉(zhuǎn)為數(shù)值型數(shù)據(jù)后進(jìn)行了歸一化處理。

表3 中K-means、KKmeans、MEAP、K-MEAP、KMM 在6 個(gè)數(shù)據(jù)集上的運(yùn)行結(jié)果全部取自文獻(xiàn)[20]。K-均值類的算法會(huì)因?yàn)樵偷倪x擇而產(chǎn)生波動(dòng)，對(duì)于這些有波動(dòng)的算法，表中的數(shù)據(jù)是它們運(yùn)行100 次后結(jié)果的平均值和標(biāo)準(zhǔn)平方差。MEAP、K-MEAP 在數(shù)據(jù)集Htru2 上的運(yùn)行結(jié)果由于時(shí)間過(guò)長(zhǎng)因此沒(méi)有展示，表中標(biāo)粗的數(shù)據(jù)為各個(gè)算法在該數(shù)據(jù)集上表現(xiàn)最好的結(jié)果。

針對(duì)K-means 算法對(duì)非凸簇或大小形狀差異大的簇聚類時(shí)效果不佳的問(wèn)題，KKmeans 將輸入空間的數(shù)據(jù)樣本映射到高維特征空間中，并選取合適的核函數(shù)代替非線性映射的內(nèi)積，在特征空間進(jìn)行聚類分析。從實(shí)驗(yàn)結(jié)果看，這種方法在個(gè)別數(shù)據(jù)集上有微小的改善，遠(yuǎn)不如通過(guò)設(shè)置多個(gè)次類來(lái)提高聚類效果的方法。而在K-means基礎(chǔ)上設(shè)置多個(gè)次類的KMM 與FN-KMM 算法比在近鄰算法基礎(chǔ)上設(shè)置多個(gè)次類的MEAP 與K-MEAP 算法聚類效果更優(yōu)。尤其是FN-KMM 算法在大部分?jǐn)?shù)據(jù)集上取得了最優(yōu)的結(jié)果，作為對(duì)KMM 算法的一種改進(jìn)算法，在BinAlpha上的準(zhǔn)確率甚至比KMM 算法提高了10 個(gè)百分點(diǎn)左右。值得一提的是KMM 算法因?yàn)殡S機(jī)選取原型所以算法效果波動(dòng)很大，一些數(shù)據(jù)集上標(biāo)準(zhǔn)方差能達(dá)到7%。而FN-KMM 通過(guò)最鄰近關(guān)系來(lái)選取的初始原型是確定的，因此最后得到的聚類結(jié)果非常穩(wěn)定，不存在任何的波動(dòng)。此外在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，由于數(shù)據(jù)集的不同F(xiàn)N-KMM 的收斂速度略有差異，但所有實(shí)驗(yàn)經(jīng)過(guò)15 次以內(nèi)的迭代都能取得令人滿意的聚類結(jié)果。

Table 3 Performance of different algorithms on real data sets表3 不同算法在真實(shí)數(shù)據(jù)集上的表現(xiàn)%

4 結(jié)束語(yǔ)

針對(duì)KMM 算法隨機(jī)選取初始原型，并且聚類結(jié)果不穩(wěn)定的問(wèn)題，提出了FN-KMM 算法，它可以自動(dòng)確定原型的數(shù)量和位置，取得穩(wěn)定且更優(yōu)的結(jié)果。

FN-KMM 算法在一定程度上提高了KMM 算法的性能，避免了結(jié)果的波動(dòng)，但是也犧牲了一定的運(yùn)算時(shí)間。在一般數(shù)據(jù)集上FN-KMM 與KMM 在運(yùn)算時(shí)間上的差異并不明顯，在樣本數(shù)較大的數(shù)據(jù)集上這種差異會(huì)更明顯。如何提高算法的計(jì)算效率并減少算法的運(yùn)算時(shí)間將是后面的研究重點(diǎn)。