穩定的K-多均值聚類算法

張倪妮，葛洪偉+

1.江蘇省模式識別與計算智能工程實驗室（江南大學），江蘇無錫214122

2.江南大學物聯網工程學院，江蘇無錫214122

聚類分析是數據挖掘中的重要技術。它將一組沒有標記的對象分組，使具有高度相似性的對象為一組。經過數十年的發展，研究人員提出了大量的聚類算法[1-5]。其中最經典的是K-均值聚類算法[1]。K-均值算法簡單高效，其基于平方誤差的劃分方法在超球面簇中表現良好。但是它存在對初始點的選取敏感并且不擅長識別非凸模式簇的問題。

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

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

然而KMM 算法作為K-均值算法的一種拓展，同樣存在對初始聚類原型的選取敏感，聚類結果不穩定的問題。針對上述問題，本文提出了一種穩定的K-多均值聚類方法。該算法先計算出每個數據樣本的最鄰近樣本，根據最鄰近關系構造鄰接矩陣，得到關于數據樣本的圖，將圖中每個連通分支的均值點作為初始聚類原型。因為這種方法用到了每個數據樣本的最鄰近樣本來尋找初始原型，所以將算法命名為FN-KMM（multiple-means clustering method with specifiedKby using first neighbor）。在人工數據集和真實數據集上的實驗證明，與KMM 算法相比，FN-KMM的聚類結果非常穩定且效果更優。

1 KMM 算法及其缺陷分析

KMM 算法[20]的核心思想是將聚類原型的選取和數據對原型的劃分變為一個優化問題，將數據和原型存在k個簇類作為限制條件加入到優化問題中，通過對優化問題的求解得到聚類結果。

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

根據文獻[21]，KMM[20]將數據樣本與原型存在k個簇類轉換為限制條件添加到問題（1）中，得到問題（3）：

為了方便求解，KMM 算法[20]對限制條件適當放寬，并根據文獻[22]中的定理得到了最終的優化問題（4）。

最后KMM[20]通過交替迭代的求解方法，完成對數據樣本的聚類。

KMM 算法把多均值聚類問題轉化為優化問題使得它的性能和速度比其他的多均值聚類算法更具優越性，但它存在K-均值類的算法普遍存在的對初始點選取敏感的問題，原型的選取極大影響了聚類的結果。

2 FN-KMM 算法

針對KMM 算法受初始原型的影響，導致聚類結果不穩定的問題，提出了FN-KMM 算法，這一章是對FN-KMM 算法的詳細介紹。

2.1 初始次類原型的選取

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

定義2表示距離第i個數據樣本最近的數據樣本。

定義3Z∈Rn×n為基于數據樣本的最鄰近關系構造的鄰接矩陣，Z中各元素的定義為：

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

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

為了方便理解，用一個只有10個樣本的二維數據集來解釋選取初始原型的方法。數據集如圖1 所示。

Fig.1 Sample dataset圖1 數據集樣例

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

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

2.2 求解優化問題

FN-KMM 在得到了初始原型后，可用交替迭代的方法來對優化問題（4）進行求解[20]。下面是求解過程的具體描述。

2.2.1 固定A 并更新S、F

當A固定后，問題（4）轉化為問題（6）如下：

問題（6）同樣也可以用交替更新的方法來解決。當S固定后，將F和D改寫成如下形式：

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

問題（7）可以通過文獻[23]中提出的定理1 來解決。

定理1設A∈Rn×m，X∈Rn×k，Y∈Rm×k，且有問題如下：

F更新后，固定F。問題（6）轉變為問題（9）：

根據如下關系（10）：

因為問題（11）在不同的i之間是獨立的，所以可以分別對每個i解決問題（12）如下：

2.2.2 固定S、F 并更新A

當S、F固定以后，A可以根據式（15）來進行更新。

當A的賦值或數據樣本的次類劃分不再變化時，算法收斂，停止迭代更新。

2.3 FN-KMM 算法步驟

FN-KMM 算法流程簡單描述如下：

步驟1通過計算數據樣本之間的距離來求每個樣本的最鄰近樣本。

步驟2根據式（5）求鄰接矩陣Z，構造圖G，得到圖G中的m個連通分支。

步驟3計算m個連通分支的數據樣本均值，求得原型矩陣A∈Rm×d。

步驟4對每一個i，用文獻[12]的方法求解問題（16），計算S的第i行。

步驟8對于每一個j，根據式（15）更新A的第j行。

步驟9重復步驟4～步驟8 直到收斂。

2.4 算法復雜度分析

假設聚類對象有n個樣本，d個維數。在尋找初始原型這一階段，時間復雜度主要是由計算樣本間的距離和使用kd-樹來獲得最鄰近樣本產生。因此，FN-KMM 算法在尋找初始原型階段的時間復雜度為O(nlogn+nd)。

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

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

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

2.5 算法收斂性分析

FN-KMM 算法的目標函數可寫為式（17）的形式。

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

3 實驗與分析

這一章展示了FN-KMM 算法在人工數據集和真實數據集上的表現，同時將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]這些優秀算法進行對比。

3.1 聚類結果評價

實驗中使用準確率（Accuracy）、標準互信息（normalized mutual information，NMI）和純度（Purity）三個聚類評價指標來對算法進行對比。設C為真實聚類結果，W為算法得到的結果。準確率的定義如下：

其中，map為最佳映射函數，可以將算法得到的標簽與真實聚類標簽變為一一映射的關系。δ是指示函數，定義如下：

標準互信息的定義如下：

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

純度的定義如下：

評價指標Accuracy、NMI、Purity 的值越大，聚類性能越好，評價指標的取值范圍是[0,1]。

3.2 實驗結果與分析

為了驗證FN-KMM 算法的性能，分別在人工數據集和真實數據集上進行實驗。

3.2.1 人工數據集的實驗結果分析

將FN-KMM 算法與KMM 算法分別在表1 中的4個人工數據集上進行實驗。

Table 1 4 artificial data sets表1 4 個人工數據集信息

表1 中，D1 由兩個團狀簇和一個流形簇構成；Aggregation 由6 個團狀簇構成，其中個別團狀簇相互連接；Zelink1 由兩個團狀簇和一個流行簇構成；Zelink3 由一個團狀簇和兩個環狀簇構成。

圖3 和圖4 分別為KMM 算法和FN-KMM 在4 個人工數據集上的表現。

Fig.3 Clustering results on artificial data sets by KMM圖3 KMM 在人工數據集的聚類結果

圖3 和圖4 中紅點表示的是原型，不同類別的樣本點用不同顏色來區分。KMM 隨機選取原型的方式導致了聚類結果波動很大。當原型選取不佳時，如圖3 所示算法不能得到正確的聚類結果。而FNKMM 通過數據樣本的最鄰近關系尋找原型，不僅結果穩定，沒有任何波動，并且如圖4 所示可以得到正確的聚類結果。

3.2.2 真實數據集的實驗結果分析

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

Fig.4 Clustering results on artificial data sets by FN-KMM圖4 FN-KMM 在人工數據集的聚類結果

Table 2 6 real data sets表2 6 個真實數據集信息

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

表3 中K-means、KKmeans、MEAP、K-MEAP、KMM 在6 個數據集上的運行結果全部取自文獻[20]。K-均值類的算法會因為原型的選擇而產生波動，對于這些有波動的算法，表中的數據是它們運行100 次后結果的平均值和標準平方差。MEAP、K-MEAP 在數據集Htru2 上的運行結果由于時間過長因此沒有展示，表中標粗的數據為各個算法在該數據集上表現最好的結果。

針對K-means 算法對非凸簇或大小形狀差異大的簇聚類時效果不佳的問題，KKmeans 將輸入空間的數據樣本映射到高維特征空間中，并選取合適的核函數代替非線性映射的內積，在特征空間進行聚類分析。從實驗結果看，這種方法在個別數據集上有微小的改善，遠不如通過設置多個次類來提高聚類效果的方法。而在K-means基礎上設置多個次類的KMM 與FN-KMM 算法比在近鄰算法基礎上設置多個次類的MEAP 與K-MEAP 算法聚類效果更優。尤其是FN-KMM 算法在大部分數據集上取得了最優的結果，作為對KMM 算法的一種改進算法，在BinAlpha上的準確率甚至比KMM 算法提高了10 個百分點左右。值得一提的是KMM 算法因為隨機選取原型所以算法效果波動很大，一些數據集上標準方差能達到7%。而FN-KMM 通過最鄰近關系來選取的初始原型是確定的，因此最后得到的聚類結果非常穩定，不存在任何的波動。此外在人工數據集和真實數據集上的實驗表明，由于數據集的不同FN-KMM 的收斂速度略有差異，但所有實驗經過15 次以內的迭代都能取得令人滿意的聚類結果。

Table 3 Performance of different algorithms on real data sets表3 不同算法在真實數據集上的表現%

4 結束語

針對KMM 算法隨機選取初始原型，并且聚類結果不穩定的問題，提出了FN-KMM 算法，它可以自動確定原型的數量和位置，取得穩定且更優的結果。

FN-KMM 算法在一定程度上提高了KMM 算法的性能，避免了結果的波動，但是也犧牲了一定的運算時間。在一般數據集上FN-KMM 與KMM 在運算時間上的差異并不明顯，在樣本數較大的數據集上這種差異會更明顯。如何提高算法的計算效率并減少算法的運算時間將是后面的研究重點。