聶耀鑫，蔣東來(lái)，程國(guó)軍

（太極計(jì)算機(jī)股份有限公司 北京 100012）

0 引言

隨著大量數(shù)據(jù)的產(chǎn)生，數(shù)據(jù)分析手段越來(lái)越重要，尤其是聚類方法的作用越來(lái)越重要。其在文獻(xiàn)分析等領(lǐng)域和促進(jìn)科技創(chuàng)新方面發(fā)揮著重要的作用，有助于學(xué)者發(fā)掘更深層次的數(shù)據(jù)關(guān)系。例如截至2019 年1 月，僅生物醫(yī)學(xué)文獻(xiàn)數(shù)據(jù)庫(kù)PubMed（https：/ /pubmed. ncbi. nlm. nih.gov/）中就包含有2 900 萬(wàn)篇文章，更有每天超3 000 篇新文章在不斷地被加入到其中。因此越來(lái)越需要精準(zhǔn)可靠的方法對(duì)海量數(shù)據(jù)進(jìn)行聚類和分析。但這些聚類方法仍然存在很多尚未攻克或研究較少的問(wèn)題，例如聚類數(shù)目k對(duì)于大多數(shù)聚類算法而言都很重要，不管是對(duì)于劃分式聚類方法或是基于密度的聚類方法或其他方法而言，都需要聚類數(shù)目k作為輸入。但是以往的工作證明了對(duì)k的良好預(yù)估并非易事。

近年來(lái)，聚類數(shù)目的重要性越來(lái)越被研究者們所關(guān)注。對(duì)于傳統(tǒng)方法來(lái)說(shuō)，不管是對(duì)于以k 均值聚類（kmeans）等為代表的劃分聚類、以DBSCAN 為代表的密度聚類、以Chameleon 聚類為代表的層次聚類，還是以譜聚類為代表的圖聚類和以高斯混合模型（Gaussian mixture model， GMM）為代表的模型聚類，都需要聚類數(shù)目k作為輸入。這就導(dǎo)致了上述的傳統(tǒng)方法雖然有其各自擅長(zhǎng)的聚類情形，但是一旦聚類數(shù)目k預(yù)估失誤，將會(huì)使聚類結(jié)果性能下降。

深度學(xué)習(xí)（deep learning， DL）的發(fā)展也沒(méi)有繞開聚類這個(gè)經(jīng)典問(wèn)題。DL 憑借其層次化結(jié)構(gòu)和非線性映射能力使得大規(guī)模深層次特征提取成為了可能。雖然各種深度聚類算法也進(jìn)一步提高了準(zhǔn)確率，但這些聚類方法大多數(shù)也是參數(shù)化方法，預(yù)先輸入的k值是對(duì)聚類效果非常重要的影響因素，例如：熱點(diǎn)研究［1］，航天數(shù)據(jù)檢測(cè)［2］，對(duì)于k-means 友好算法的研究［3］以及對(duì)電力數(shù)據(jù)的分析［4］。

本文提出了一種有效的方法來(lái)預(yù)測(cè)高維數(shù)據(jù)集的聚類數(shù)目。利用自編碼器技術(shù)［5］和T-SNE 技術(shù)［6］實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)集的降維并學(xué)習(xí)提取特征，使用基于蒙特卡洛的方法預(yù)測(cè)聚類數(shù)目。

1 聚類數(shù)目預(yù)測(cè)算法

1.1 自編碼器模塊

自編碼器是一種能夠基于輸入數(shù)據(jù)來(lái)學(xué)習(xí)有效編碼方法的神經(jīng)網(wǎng)絡(luò)模型。其結(jié)構(gòu)通常包括一個(gè)輸入層、一個(gè)或多個(gè)隱藏層和一個(gè)輸出層。大部分技術(shù)在考慮數(shù)據(jù)集未知聚類數(shù)量問(wèn)題時(shí)，都不直接在數(shù)據(jù)集空間上預(yù)測(cè)。例如在對(duì)xi＝1 ∈X這組數(shù)據(jù)聚類時(shí)，不直接在X的空間上預(yù)測(cè)，而是提出了一個(gè)非線性映射f來(lái)將xi轉(zhuǎn)換為zi，其中Z是潛在特征空間。為了使Z適合聚類，特征空間Z的維數(shù)應(yīng)盡可能低。本算法的目標(biāo)是找到一個(gè)合適的方法來(lái)達(dá)到f的效果，從而可以提取生成低維嵌入點(diǎn)和一個(gè)合適的聚類算法來(lái)確定聚類數(shù)目k。

首先是從輸入層到隱藏層的編碼過(guò)程：

其次是從隱藏層到輸入層的解碼過(guò)程：

最后算法的優(yōu)化目標(biāo)函數(shù)為：

這里dist是使用均方方差來(lái)計(jì)算兩者的距離度量函數(shù)。但是為了使數(shù)據(jù)可視化，算法仍然需要降低維數(shù)。因此采用T-SNE 降維方法對(duì)數(shù)據(jù)進(jìn)行可視化處理。此方法可以使高維數(shù)據(jù)可視化為更低維的數(shù)據(jù)。例如本模型需要2 維特征進(jìn)行判斷指數(shù)計(jì)算。因此算法將提取到的特征可視化為2 維數(shù)據(jù)。

1.2 蒙特卡洛聚類數(shù)目預(yù)測(cè)模塊

本模型確定聚類數(shù)目的指標(biāo)主要有如下幾個(gè)：模型的貝葉斯信息量準(zhǔn)則（Bayesian information criterion， BIC）值、赤池信息量準(zhǔn)則（Akaike information criterion， AIC）值［7］、輪廓系數(shù)［8］（Silhoutte） 值［9］和Calinski Harabasz（CH）值［10］。訓(xùn)練模型時(shí)，增加參數(shù)數(shù)量也就增加了模型復(fù)雜度，進(jìn)而會(huì)導(dǎo)致過(guò)擬合現(xiàn)象。針對(duì)該問(wèn)題，AIC 和BIC均引入了與模型參數(shù)個(gè)數(shù)相關(guān)的懲罰項(xiàng)，BIC 的懲罰項(xiàng)比AIC 的大，考慮了樣本數(shù)量，樣本數(shù)量過(guò)多時(shí)，可有效防止模型精度過(guò)高造成的模型復(fù)雜度過(guò)高。輪廓系數(shù)可以作為定義為該聚類是否合理、有效的度量。聚類結(jié)果的輪廓系數(shù)的取值在［－1，1］之間，值越大，說(shuō)明同類樣本相距越近，不同樣本相距越遠(yuǎn)，則聚類效果越好。模型CH 值越大代表著類自身越緊密，類與類之間越分散，即更優(yōu)的聚類結(jié)果。

第一步是創(chuàng)建一個(gè)高斯混合模型，該模型具有為簇?cái)?shù)［2，n］預(yù)設(shè)的k值范圍，其中n＝3，4，5，…，在基于k值范圍創(chuàng)建一組模型之后，通過(guò)蒙特卡洛方法判斷最佳聚類數(shù)目。具體來(lái)說(shuō)由于存在局部最優(yōu)，單個(gè)值是波動(dòng)的。因此，從統(tǒng)計(jì)的角度出發(fā)，引入了蒙特卡洛方法（Monte Carlo method）來(lái)獲取期望值，以避免局部最優(yōu)，并導(dǎo)出最佳簇?cái)?shù)。因此，算法可以根據(jù)得到的最佳聚類數(shù)量對(duì)數(shù)據(jù)進(jìn)行GMM 聚類分析。其中，GMM 模型的概率密度函數(shù)如式（4）所示。

式（4）中，設(shè)n為觀測(cè)值的數(shù)量，k為聚類數(shù)目，RSS 為殘差平方和，L為似然函數(shù)，AIC 和BIC 的計(jì)算方法如式（5）、式（6）所示。

簇內(nèi)不相似度為a（i），簇間差異為b（i）。S（i） 的計(jì)算方法如式（7）所示。

CH 的計(jì)算方法如式（8）所示。

式（8）中，ki為當(dāng)前類別，trB（k）為類間偏離矩陣的軌跡，trW（k）為類內(nèi)偏離矩陣的軌跡。

多次運(yùn)行模型后，本算法可以得到聚類預(yù)測(cè)數(shù)目。獲得聚類數(shù)目的總體公式如式（9）所示。

2 仿真驗(yàn)證

2.1 數(shù)據(jù)集與基準(zhǔn)模型

本文選擇的數(shù)據(jù)集和基準(zhǔn)模型方法有：差距分析（gap analysis， GAP），輪廓系數(shù)，卷積自編碼器（convolutional autoencoder， CAE）方法，均值漂移（mean-shift），改進(jìn)的GMM 方法（improved-GMM）。這些方法和本文算法都屬于較為完整的模型，可以在聚類數(shù)目預(yù)測(cè)精準(zhǔn)度和聚類效果上與本文算法的方法進(jìn)行比較。

這里分別挑選了3 種類型的數(shù)據(jù)集用來(lái)證明自聚類算法對(duì)于多種類數(shù)據(jù)的適配性。它們分別是文本數(shù)據(jù)集20Newsgroup，圖像手寫數(shù)字?jǐn)?shù)據(jù)集MNIST 和音頻數(shù)據(jù)集Urbansound8k。

20Newsgroup 語(yǔ)料庫(kù)是18 846 個(gè)文本文檔的集合，這些文檔分為20 個(gè)不同的新聞組。使用這個(gè)語(yǔ)料庫(kù)，可以觀察到所提出的方法是如何在文本樣本上工作的。我們使用文檔的TF-IDF 表示，但這樣數(shù)據(jù)的維度會(huì)過(guò)高。因此我們選擇10 000 個(gè)最常用的單詞作為特征。特別需要說(shuō)明的是，在文檔數(shù)據(jù)集20Newsgroup 中同時(shí)存在某些類別過(guò)于相似（如IBM 系統(tǒng)下的個(gè)人電腦硬件（comp. sys.ibm.pc.hardware）/ mac 系統(tǒng)下的個(gè)人電腦硬件（comp.sys.mac.hardware））的情況。因此選擇完全不同的15 個(gè)類作為原始數(shù)據(jù)集。

MNIST 是一個(gè)非常簡(jiǎn)單的數(shù)據(jù)集。這個(gè)數(shù)據(jù)集包含一些手寫的阿拉伯?dāng)?shù)字（0 ～90 個(gè)數(shù)字）。其中訓(xùn)練集有60 000 張圖片，測(cè)試集有10 000 張圖片。

Urbansound8k 是一個(gè)廣泛用于城市環(huán)境聲音自動(dòng)分類研究的公共數(shù)據(jù)集。該數(shù)據(jù)集包含10 個(gè)類別共8 732個(gè)標(biāo)記的聲音片段（≤4 s），如：空調(diào)、汽車警報(bào)聲、兒童玩耍聲、狗叫聲、鉆孔聲、發(fā)動(dòng)機(jī)空轉(zhuǎn)聲、槍聲、手持鉆孔機(jī)聲、警報(bào)聲和街頭音樂(lè)。

2.2 聚類性能實(shí)驗(yàn)結(jié)果

本文對(duì)3 個(gè)數(shù)據(jù)集分別在基準(zhǔn)算法和自聚類算法上進(jìn)行了測(cè)試。計(jì)算了它們的準(zhǔn)確率和平均預(yù)測(cè)值。通過(guò)表1 和表2 的實(shí)驗(yàn)結(jié)果可以看出，在所有基準(zhǔn)算法當(dāng)中自聚類算法取得了最好的結(jié)果。

表1 聚類性能實(shí)驗(yàn)結(jié)果

表2 消融實(shí)驗(yàn)結(jié)果

2.3 消融實(shí)驗(yàn)

在這一小節(jié)中進(jìn)行了消融實(shí)驗(yàn)分別驗(yàn)證自聚類算法每一組成部分對(duì)自聚類模型的影響。消融實(shí)驗(yàn)的設(shè)計(jì)是為了探究實(shí)驗(yàn)中4 個(gè)參數(shù)的重要性。如表2 分別對(duì)每個(gè)參數(shù)進(jìn)行一次缺失處理，只采用其余3 個(gè)參數(shù)的值進(jìn)入下一步蒙特卡洛方法。其中缺失了CH 值的實(shí)驗(yàn)結(jié)果表現(xiàn)最差，這證明了CH 值對(duì)算法的影響最大。

3 結(jié)語(yǔ)

綜上所述，本文提出了一種基于蒙特卡洛方法預(yù)測(cè)聚類數(shù)目的深度學(xué)習(xí)方法。此算法設(shè)計(jì)了多個(gè)工作模塊，從學(xué)習(xí)到的信息中提取關(guān)鍵特征，以進(jìn)行聚類數(shù)目的預(yù)測(cè)。廣泛的實(shí)驗(yàn)表明，本算法達(dá)到了最先進(jìn)的聚類性能。此外，由于許多實(shí)際應(yīng)用中高維數(shù)據(jù)較多，所以預(yù)訓(xùn)練模型的編碼速度較慢。今后，研究人員將研究如何在保持實(shí)驗(yàn)結(jié)果基本不變的情況下，降低模型參數(shù)，提高訓(xùn)練速度。