聚類成員簇個數的選擇方法研究

王江峰，徐 森，徐秀芳，花小朋，皋 軍，安 晶

（鹽城工學院 信息工程學院，江蘇 鹽城 224002）

聚類分析是在沒有先驗知識的情況下進行的，即訓練樣本的真實標簽未知，僅根據數據的內在特性及規律，將訓練樣本進行分組。聚類分析的主要目標是將數據集（也稱為模式集、點集或對象集）劃分為自然組或簇，使得屬于同一簇的對象相似，屬于不同簇的對象不相似［1］。目前，聚類分析已廣泛應用于心理學［2］、醫學［3］、模式識別、信息檢索、機器學習和數據挖掘等領域。

各種聚類算法接連被提出，聚類算法得到了不斷改進，但找到適合所有數據集的聚類算法幾乎是不可能的。為了在沒有先驗知識的情況下組合數據分區和產生一個更好的聚類結果，文獻［4］提出了聚類集成的概念。聚類集成是為了提高聚類結果的準確性、穩定性和魯棒性的一種算法［5］，通過將多個基聚類結果集成可以產生一個更優的結果。聚類集成將數據集的不同聚類結果組合成最終的聚類結果。單一的聚類算法有其自身的缺點，會導致一種算法只適用于特定的某一類數據集。聚類集成將這些聚類算法結合起來，可以在一定程度上彌補單一聚類算法的不足。相較于單一聚類算法，聚類集成既適用于更多的數據集，也抗噪聲和離群值［6］。近年來的研究主要集中在3 個方面：（1）聚類成員生成，即如何獲取精度較高且具有多樣性的聚類成員。（2）聚類成員選擇，即如何選出精度較高且差異性較大的聚類成員。（3）共識函數設計，即如何將聚類成員組合為精度更高的一致聚類結果。

研究指出，簇個數k 對聚類集成的結果有很大的影響［7-8］。然而，目前尚無關于聚類成員簇個數選擇方法的系統研究和比較。因此，本文對不同的簇個數設置方法進行了比較研究，為聚類成員生成研究提供了有益的參考。

1 相關工作

在已有的聚類集成算法中，對于簇個數的選擇方式有很多，大多數方法都是在給定的區間內隨機選擇簇個數，但對其設置方法的解釋非常有限，也缺少對不同設置方法優劣的比較。

Li等［9］認為聚類成員的簇個數應該大于真實類別數，因此將其設置為k=min｛ n，50｝，其中n為對象個數。Bai 等［10］將每個聚類成員中的簇個數設置為每個給定數據集上的真實類別個數，這也是聚類集成研究中最常用的方法。由于使用相同的聚類算法，且每種算法生成的簇個數相等，聚類成員的差異只是由不同的初始聚類中心引起的，聚類集體往往缺乏多樣性。為了增強聚類成員的多樣性，研究人員提出了很多簇個數的隨機取值區間，包括Liu 等［17］針對較大的數據集，簇個數在［2，2k］內隨機選取，而其他數據集則在［k，］范圍內隨機選取。Zhou 等［18］針對較小的數據集設定簇個數等于真實類別個數，而其他數據集則在［2，M］范圍內隨機選取，其中M= min｛，50｝。徐森等［19］使用了兩種不同的方法來生成聚類成員，分別是：（1）k=k*；（2）k從區間［2，2k*］中隨機選擇。

2 研究方法

設數據集X=｛x1，x2， …，xN｝，其中xi∈?δ，? 為實數集，δ是特征個數，i=1，...，N。首先，本文預設簇個數的選擇區間，以確保所有聚類成員簇個數都在相同取值范圍內隨機選擇，不妨假設降維后的數據為Y=｛y1，y2， …，y N｝，其中yi∈?d，d是降維后的維度，i=1，...，N；其次，設計K-means聚類算法對數據集Y進行聚類，生成聚類成員，重復該步驟直至獲得r個聚類成員；最后，使用Ward 層次聚類算法［20］對這r個聚類成員集成，獲得最終的聚類結果。研究流程如圖1 所示，下面分別對這3個步驟詳細描述。

圖1 聚類集成算法流程圖Fig. 1 Flow chart of cluster ensemble algorithm

2.1 維數約簡

維數約簡通過降低數據復雜性來提高數據質量，可以有效解決維數災難問題［21］。近年來，t-SNE因其能有效地識別數據中的局部結構而成為最常用的降維技術［22-23］。2018 年，Mcinnes 等［24］提出了一種全新的降維算法——一致流形逼近與投影（uniform manifold approximation and projec?tion for dimension reduction，UMAP）。UMAP 使用了拉普拉斯特征映射初始化和交叉熵目標函數，因而在保留全局結構方面優于t-SNE［25］。

UMAP 是一種建立在黎曼幾何和代數拓撲的理論框架上的非線性降維方法。UMAP 一定程度上類似于t-SNE，在數據可視化方面有著較好的效果。與t-SNE 相比，UMAP 能夠能更好地保存全局結構，比t-SNE有著更好的連續性，運行速度更快，且嵌入維數也不受計算限制。因此，本文在聚類成員生成階段引入UMAP進行降維。

UMAP 的第一步驟是加權kw鄰域的構造；第二步驟是找到一個低維的表示來優化交叉熵目標函數。第一個步驟中，計算每一個xi在指定維度下的kw最近鄰，使得局部連通性約束ρi和歸一化系數σi分別定義為：

加權有向圖定義為Gˉ=（V，E，ω），其中V是頂點集，E={(xi，xj)|1 ≤h≤k，1 ≤i≤N}是邊的集合，邊的權重ω定義如下：

設A為加權有向圖Gˉ的加權鄰接矩陣，其對稱矩陣B可通過下式獲得：

第二個步驟中，UMAP 在低維空間中使用了力導向圖布局算法，對沿邊和頂點之間施加引力和斥力。最小化兩個模糊集(A，u)和(A，v)的交叉熵目標函數C，其中，u和v為成員強度函數，C的定義如下：

最后使用隨機梯度下降來優化模糊集交叉熵。

2.2 聚類成員生成

指定簇個數的選擇范圍，對降維后的數據使用K-means算法進行聚類，產生聚類成員。

K-means算法是一種基于原型和劃分的聚類技術，根據k′集合來尋找最優質心。首先選擇k′個初始質心，其中，k′是指定的參數，即期望的簇個數，每個點都被指派到距離其最近的質心所在的簇；然后更新每個簇的質心。重復指定和更新步驟，直到質心不再變化為止或迭代次數t達到指定閾值。

在相同的簇個數選擇區間內重復運行Kmeans 算法r次，來獲得r個聚類成員。在每個選定的簇個數范圍內，可以得到r個聚類成員。

2.3 聚類集成

Ward 連接是最符合聚類目的的連接，因此也是最有效的連接［26］。與其他層次聚類一樣，Ward連接從個體點開始，相繼合并兩個最接近的簇，直到只剩下一個簇。對于Ward連接，兩個簇的鄰近度定義為兩個簇合并時導致的平方誤差的增量。兩個簇CA和CB之間的Ward 距離由下式給出：

式中：a和b分別是CA和CB的質心，nA和nB分別是CA和CB中數據點的數量。

綜上，本文算法主要步驟如Algorithm 1所示。

Algorithm 1：

輸入：數據集X

輸出：聚類集成結果

1. 根據式（1）、式（2）、式（3）構建模糊集

2. 利用式（4）將模糊集表示為對稱規范化加權鄰接矩陣

3. 用隨機梯度下降法優化式（5）中的交叉熵目標函數

4.Settto 1

5.repeat

6. 選擇k′個初始質心

7. 將所有點分配到最近的質心

8. 更新每個簇的質心

9. 重復步驟7和8直至質心不再發生變化

10.t=t+1

11.untilt>20

12. 計算兩個簇之間的鄰近度

13.repeat

14. 合并最接近的兩個簇

15. 更新鄰近度矩陣，以反映新的簇與原來的簇之間的鄰近性

16.until僅剩下一個簇

3 實驗

3.1 數據集

本文實驗中使用了5 個取自UCI 機器學習庫的真實數據集，即Ecoli，Pen Digit（PD），Semeion，Multiple Features（MF），ISOLET，其詳細信息如表1所示。

表1 數據集的描述Table 1 Description of the datasets

3.2 評價指標

本文選取了兩種被廣泛使用的評估指標用于評估聚類的性能，即歸一化互信息（normalized mutual information，NMI）［1］和調整后的蘭德指數（adjusted rand index，ARI）［27］。NMI 和ARI 的值越大，表示聚類結果越好。NMI 可以有效地度量測試聚類和真值聚類之間的匹配度。設π′為預測標簽，πG為真實標簽。

π′和πG的NMI定義如下［1］：

式中：n′是π′中的簇數；nG是πG中的簇數；n′i是π′中第i個簇中的對象數量；是πG中第j個簇中的對象數量；nij是π′中第i個簇和πG中第j個簇所共有的對象數量；n是數據集的樣本數。

ARI 是蘭德指數（RI）［28］的推廣，可衡量預測標簽和真實標簽之間的一致性。π′和πG的ARI計算如下［27］：

式中：N11是在π′和πG中屬于同一簇的對象對的數量；N00是在π′和πG中屬于不同簇的對象對的數量；N10是在π′中屬于同一簇但在πG中屬于不同簇的對象對的數量；N01是屬于π′中不同簇但屬于πG中相同簇的對象對的數量。

3.3 實驗設計

為了系統地研究和比較不同聚類數對聚類集成最終結果的影響，將簇個數k 設置為：（1）k=k*，其中k*是數據集中包含的真實類別數；（2）在指定的范圍內隨機選擇：［2，2k*］，［2，4k*］，［2，，［k*］。本實驗中，K-means 算法運行20次，每次隨機選取初始質心，獲得20 個聚類成員作為1組，生成10組聚類成員集合。使用Ward算法對這10組聚類成員集合分別進行聚類集成，得到10 組聚類集成結果，并計算它們的NMI 和ARI，取平均值作為最終NMI和ARI。

3.4 實驗結果

不同簇個數選擇方法獲得的聚類集成結果的NMI 和ARI 分別如表2 和表3 所示。由表2 和表3可見：

表2 不同簇個數選擇方法獲得的NMITable 2 NMI obtained by different cluster number selection methods

表3 不同簇個數選擇方法獲得的ARITable 3 NMI obtained by different cluster number selection methods

（1）當簇個數k = k*時，在所有數據集上都獲得了最高的NMI和ARI。

（2）當簇個數k∈［2，2k*］時，聚類集成結果的NMI和ARI僅次于k = k*時的情況。

（3）由于不同數據集的k 和n 不同，所以［2，4k*］、［2］和［k*，］的值區間大小也不同，總體來看，這三種方法獲得的聚類集成結果NMI 和ARI較低。

（4）在［2，4k*］和［2，］兩種設置方法中，下限均為2，上限4k*與 n 的大小因數據集的不同而不同。MF 和PD 數據集的4k*小于，在［2，4k*］中的性能優于［2，］。Ecoli 和ISOLET 數據集的4k*大于，它們在［2，4k*］中的表現不如［2］。Semeion 數據集的4k*和大小接近，性能也相差無幾。對于［2］和［k*，］，兩組的取值上限相同，由于下限2 和k*的差異不大，所以兩組的結果也很接近。一般情況下，選擇區間為［k*］時，聚類集成效果較好。

綜上，當選擇的簇個數k 等于數據集的真實類別數時，聚類集成效果最好，隨著簇個數選擇的區間變大，聚類集成效果變差。

3.5 進一步探索

為了探究聚類成員簇個數選擇的較優方法，本文縮小簇個數的取值范圍，選擇了［k*，1.1k*］， ［k*，1.2k*］，［k*，1.4k*］，［k*，1.6k*］，［k*，1.8k*］，［k*，2k*］這6 種設置方法（取值的上限向上取整），與k = k*進行比較。實驗流程與之前相同，使用Ward算法進行聚類集成，得到的聚類結果NMI和ARI分別如圖2和圖3所示。由圖2和圖3可見：

圖2 取值區間較小時的NMIFig. 2 NMI with small value range

圖3 取值區間較小時的ARIFig. 3 ARI with small value range

（1）當簇個數k = k*時，在所有數據集上都獲得了最高的NMI和ARI；

（2）當簇個數取值區間增大時，聚類集成結果的NMI和ARI都在減小。

4 總結

本文系統研究比較了聚類集成中幾種常見的簇個數設置方法，并進一步探索較優的設置方法。通過聚類集成效果的對比分析發現，將簇個數設置為真實類別數時，聚類成員的質量相對較高，能夠獲得較優的聚類集成結果。同時也發現當簇個數取值區間變大時，聚類集成效果變差。本文對不同的簇個數設置方法進行了比較研究，為聚類成員生成研究提供了有益的參考。