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

（鹽城工學(xué)院 信息工程學(xué)院，江蘇 鹽城 224002）

聚類(lèi)分析是在沒(méi)有先驗(yàn)知識(shí)的情況下進(jìn)行的，即訓(xùn)練樣本的真實(shí)標(biāo)簽未知，僅根據(jù)數(shù)據(jù)的內(nèi)在特性及規(guī)律，將訓(xùn)練樣本進(jìn)行分組。聚類(lèi)分析的主要目標(biāo)是將數(shù)據(jù)集（也稱(chēng)為模式集、點(diǎn)集或?qū)ο蠹﹦澐譃樽匀唤M或簇，使得屬于同一簇的對(duì)象相似，屬于不同簇的對(duì)象不相似［1］。目前，聚類(lèi)分析已廣泛應(yīng)用于心理學(xué)［2］、醫(yī)學(xué)［3］、模式識(shí)別、信息檢索、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域。

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

研究指出，簇個(gè)數(shù)k 對(duì)聚類(lèi)集成的結(jié)果有很大的影響［7-8］。然而，目前尚無(wú)關(guān)于聚類(lèi)成員簇個(gè)數(shù)選擇方法的系統(tǒng)研究和比較。因此，本文對(duì)不同的簇個(gè)數(shù)設(shè)置方法進(jìn)行了比較研究，為聚類(lèi)成員生成研究提供了有益的參考。

1 相關(guān)工作

在已有的聚類(lèi)集成算法中，對(duì)于簇個(gè)數(shù)的選擇方式有很多，大多數(shù)方法都是在給定的區(qū)間內(nèi)隨機(jī)選擇簇個(gè)數(shù)，但對(duì)其設(shè)置方法的解釋非常有限，也缺少對(duì)不同設(shè)置方法優(yōu)劣的比較。

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

2 研究方法

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

圖1 聚類(lèi)集成算法流程圖Fig. 1 Flow chart of cluster ensemble algorithm

2.1 維數(shù)約簡(jiǎn)

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

UMAP 是一種建立在黎曼幾何和代數(shù)拓?fù)涞睦碚摽蚣苌系姆蔷€性降維方法。UMAP 一定程度上類(lèi)似于t-SNE，在數(shù)據(jù)可視化方面有著較好的效果。與t-SNE 相比，UMAP 能夠能更好地保存全局結(jié)構(gòu)，比t-SNE有著更好的連續(xù)性，運(yùn)行速度更快，且嵌入維數(shù)也不受計(jì)算限制。因此，本文在聚類(lèi)成員生成階段引入U(xiǎn)MAP進(jìn)行降維。

UMAP 的第一步驟是加權(quán)kw鄰域的構(gòu)造；第二步驟是找到一個(gè)低維的表示來(lái)優(yōu)化交叉熵目標(biāo)函數(shù)。第一個(gè)步驟中，計(jì)算每一個(gè)xi在指定維度下的kw最近鄰，使得局部連通性約束ρi和歸一化系數(shù)σi分別定義為：

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

設(shè)A為加權(quán)有向圖Gˉ的加權(quán)鄰接矩陣，其對(duì)稱(chēng)矩陣B可通過(guò)下式獲得：

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

最后使用隨機(jī)梯度下降來(lái)優(yōu)化模糊集交叉熵。

2.2 聚類(lèi)成員生成

指定簇個(gè)數(shù)的選擇范圍，對(duì)降維后的數(shù)據(jù)使用K-means算法進(jìn)行聚類(lèi)，產(chǎn)生聚類(lèi)成員。

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

在相同的簇個(gè)數(shù)選擇區(qū)間內(nèi)重復(fù)運(yùn)行Kmeans 算法r次，來(lái)獲得r個(gè)聚類(lèi)成員。在每個(gè)選定的簇個(gè)數(shù)范圍內(nèi)，可以得到r個(gè)聚類(lèi)成員。

2.3 聚類(lèi)集成

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

式中：a和b分別是CA和CB的質(zhì)心，nA和nB分別是CA和CB中數(shù)據(jù)點(diǎn)的數(shù)量。

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

Algorithm 1：

輸入：數(shù)據(jù)集X

輸出：聚類(lèi)集成結(jié)果

1. 根據(jù)式（1）、式（2）、式（3）構(gòu)建模糊集

2. 利用式（4）將模糊集表示為對(duì)稱(chēng)規(guī)范化加權(quán)鄰接矩陣

3. 用隨機(jī)梯度下降法優(yōu)化式（5）中的交叉熵目標(biāo)函數(shù)

4.Settto 1

5.repeat

6. 選擇k′個(gè)初始質(zhì)心

7. 將所有點(diǎn)分配到最近的質(zhì)心

8. 更新每個(gè)簇的質(zhì)心

9. 重復(fù)步驟7和8直至質(zhì)心不再發(fā)生變化

10.t=t+1

11.untilt>20

12. 計(jì)算兩個(gè)簇之間的鄰近度

13.repeat

14. 合并最接近的兩個(gè)簇

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

16.until僅剩下一個(gè)簇

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

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)中使用了5 個(gè)取自UCI 機(jī)器學(xué)習(xí)庫(kù)的真實(shí)數(shù)據(jù)集，即Ecoli，Pen Digit（PD），Semeion，Multiple Features（MF），ISOLET，其詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集的描述Table 1 Description of the datasets

3.2 評(píng)價(jià)指標(biāo)

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

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

式中：n′是π′中的簇?cái)?shù)；nG是πG中的簇?cái)?shù)；n′i是π′中第i個(gè)簇中的對(duì)象數(shù)量；是πG中第j個(gè)簇中的對(duì)象數(shù)量；nij是π′中第i個(gè)簇和πG中第j個(gè)簇所共有的對(duì)象數(shù)量；n是數(shù)據(jù)集的樣本數(shù)。

ARI 是蘭德指數(shù)（RI）［28］的推廣，可衡量預(yù)測(cè)標(biāo)簽和真實(shí)標(biāo)簽之間的一致性。π′和πG的ARI計(jì)算如下［27］：

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

3.3 實(shí)驗(yàn)設(shè)計(jì)

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

3.4 實(shí)驗(yàn)結(jié)果

不同簇個(gè)數(shù)選擇方法獲得的聚類(lèi)集成結(jié)果的NMI 和ARI 分別如表2 和表3 所示。由表2 和表3可見(jiàn)：

表2 不同簇個(gè)數(shù)選擇方法獲得的NMITable 2 NMI obtained by different cluster number selection methods

表3 不同簇個(gè)數(shù)選擇方法獲得的ARITable 3 NMI obtained by different cluster number selection methods

（1）當(dāng)簇個(gè)數(shù)k = k*時(shí)，在所有數(shù)據(jù)集上都獲得了最高的NMI和ARI。

（2）當(dāng)簇個(gè)數(shù)k∈［2，2k*］時(shí)，聚類(lèi)集成結(jié)果的NMI和ARI僅次于k = k*時(shí)的情況。

（3）由于不同數(shù)據(jù)集的k 和n 不同，所以［2，4k*］、［2］和［k*，］的值區(qū)間大小也不同，總體來(lái)看，這三種方法獲得的聚類(lèi)集成結(jié)果NMI 和ARI較低。

（4）在［2，4k*］和［2，］兩種設(shè)置方法中，下限均為2，上限4k*與 n 的大小因數(shù)據(jù)集的不同而不同。MF 和PD 數(shù)據(jù)集的4k*小于，在［2，4k*］中的性能優(yōu)于［2，］。Ecoli 和ISOLET 數(shù)據(jù)集的4k*大于，它們?cè)冢?，4k*］中的表現(xiàn)不如［2］。Semeion 數(shù)據(jù)集的4k*和大小接近，性能也相差無(wú)幾。對(duì)于［2］和［k*，］，兩組的取值上限相同，由于下限2 和k*的差異不大，所以?xún)山M的結(jié)果也很接近。一般情況下，選擇區(qū)間為［k*］時(shí)，聚類(lèi)集成效果較好。

綜上，當(dāng)選擇的簇個(gè)數(shù)k 等于數(shù)據(jù)集的真實(shí)類(lèi)別數(shù)時(shí)，聚類(lèi)集成效果最好，隨著簇個(gè)數(shù)選擇的區(qū)間變大，聚類(lèi)集成效果變差。

3.5 進(jìn)一步探索

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

圖2 取值區(qū)間較小時(shí)的NMIFig. 2 NMI with small value range

圖3 取值區(qū)間較小時(shí)的ARIFig. 3 ARI with small value range

（1）當(dāng)簇個(gè)數(shù)k = k*時(shí)，在所有數(shù)據(jù)集上都獲得了最高的NMI和ARI；

（2）當(dāng)簇個(gè)數(shù)取值區(qū)間增大時(shí)，聚類(lèi)集成結(jié)果的NMI和ARI都在減小。

4 總結(jié)

本文系統(tǒng)研究比較了聚類(lèi)集成中幾種常見(jiàn)的簇個(gè)數(shù)設(shè)置方法，并進(jìn)一步探索較優(yōu)的設(shè)置方法。通過(guò)聚類(lèi)集成效果的對(duì)比分析發(fā)現(xiàn)，將簇個(gè)數(shù)設(shè)置為真實(shí)類(lèi)別數(shù)時(shí)，聚類(lèi)成員的質(zhì)量相對(duì)較高，能夠獲得較優(yōu)的聚類(lèi)集成結(jié)果。同時(shí)也發(fā)現(xiàn)當(dāng)簇個(gè)數(shù)取值區(qū)間變大時(shí)，聚類(lèi)集成效果變差。本文對(duì)不同的簇個(gè)數(shù)設(shè)置方法進(jìn)行了比較研究，為聚類(lèi)成員生成研究提供了有益的參考。