一種基于ELM-AE特征表示的譜聚類算法

王麗娟，丁世飛

（1. 中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116; 2. 徐州工業(yè)職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，江蘇徐州 221114）

聚類[1-3]是一種將數(shù)據(jù)集劃分為若干組或類，使類內(nèi)相似性最大，類間相似性最小的方法。現(xiàn)有文獻(xiàn)提出，傳統(tǒng)的聚類方法有k均值算法(kmeans)[4]、FCM算法[5]、子空間聚類等。它們雖然簡單，但缺乏處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力，當(dāng)樣本為凸型時(shí)，這些算法對(duì)數(shù)據(jù)的處理有較好的效果，當(dāng)樣本空間為非凸時(shí)，算法容易陷入局部最優(yōu)。為解決這一難題，譜聚類應(yīng)運(yùn)而生，它不受樣本空間形狀限制，聚類結(jié)果為全局最優(yōu)解。在這些算法中，由于譜類算法便于實(shí)現(xiàn)、性能良好，已被廣泛應(yīng)用于圖像分割、信息檢索、人臉識(shí)別等領(lǐng)域。

譜聚類來源于圖論中的最小切割問題[6-8]。眾所周知，數(shù)據(jù)通過非線性變換，將數(shù)據(jù)映射到高維特征空間后，數(shù)據(jù)將變得線性可分。因此，可以通過各種非線性變換，例如基于核的方法，提高高維特征空間中輸入數(shù)據(jù)的特征表示能力。然而，以往的譜聚類方法一般只注重?cái)?shù)據(jù)降維、優(yōu)化時(shí)間復(fù)雜度等，而不是進(jìn)一步提高數(shù)據(jù)特征的表示能力。在聚類任務(wù)中，數(shù)據(jù)的特征表示是至關(guān)重要的，通過反復(fù)的實(shí)驗(yàn)和一系列的工作，獲得良好的數(shù)據(jù)特征表示是提高聚類準(zhǔn)確度的保證。

ELM[9-11]最初用于訓(xùn)練“廣義”單隱層前饋神經(jīng)網(wǎng)絡(luò)(SLFN)，具有快速學(xué)習(xí)、良好的泛化能力和特征表示能力，被廣泛應(yīng)用于各種機(jī)器學(xué)習(xí)任務(wù)，如回歸和分類等[12-14]。近年來，ELM已經(jīng)擴(kuò)展到聚類，一般是在ELM獲得的嵌入特征空間中進(jìn)行聚類。ELM的隱層參數(shù)選擇是隨機(jī)的，和輸入數(shù)據(jù)無關(guān)，與常用的反向傳播訓(xùn)練算法相比，ELM最大限度地減小了訓(xùn)練誤差和輸出權(quán)的范數(shù)。根據(jù)Bartlett理論[15]，最小化輸出權(quán)值范數(shù)將產(chǎn)生更好的泛化能力。

自編碼器(Auto Encoder AE)[16-17]是深度學(xué)習(xí)中的一種無監(jiān)督學(xué)習(xí)方法，能夠從大量數(shù)據(jù)中自動(dòng)學(xué)習(xí)到數(shù)據(jù)中的有效特征[18-20]。傳統(tǒng)自編碼器就是一種在輸出層重建輸入數(shù)據(jù)并且結(jié)構(gòu)對(duì)稱的神經(jīng)網(wǎng)絡(luò)。常見的自編碼器有降噪自編碼器、稀疏自編碼器、收縮自編碼器和卷積自編碼器等[21]。使用自編碼器進(jìn)行特征提取要比特征分解快，并讓目標(biāo)值等于輸入值，是一種盡可能復(fù)現(xiàn)輸入信號(hào)的神經(jīng)網(wǎng)絡(luò)。

基于以上啟發(fā)，本文將極限學(xué)習(xí)機(jī)(ELM)和自編碼器(AE)結(jié)合起來改進(jìn)譜聚類，提出了一種基于ELM-AE嵌入特征空間的譜聚類算法。

1 相關(guān)工作

1.1 譜聚類算法

譜聚類的概念起源于譜劃分，將數(shù)據(jù)聚類轉(zhuǎn)化為無向圖的多路劃分問題求解，尤其適用于數(shù)據(jù)集非凸的情況[22-23]。假設(shè)數(shù)據(jù)集有n個(gè)數(shù)據(jù)點(diǎn)，目標(biāo)是將所有數(shù)據(jù)點(diǎn)劃分到c個(gè)簇中。譜聚類[24]首先將數(shù)據(jù)點(diǎn)看作圖的頂點(diǎn)，根據(jù)數(shù)據(jù)點(diǎn)成對(duì)相似性，先用歐氏距離計(jì)算距離矩陣，再使用高斯核函數(shù)將距離矩陣構(gòu)造為相似矩陣并計(jì)算出所對(duì)應(yīng)的拉普拉斯矩陣，譜方法是基于相似拉普拉斯矩陣的特征值和特征向量進(jìn)行聚類的方法，將這些特征向量構(gòu)造為低維的特征子空間，再在這個(gè)特征子空間上使用諸如k-means的聚類方法進(jìn)行聚類，NJW譜聚類算法[24]是一個(gè)典型的譜聚類算法。下面簡單介紹該方法的原理。

給定一組數(shù)據(jù)集X=(x1,x2,···,xn)，要把這些數(shù)據(jù)點(diǎn)分成k類，使用譜聚類的一般過程是：

1)根據(jù)一定的相似矩陣生成方式構(gòu)建樣本的相似矩陣，W中的每一項(xiàng)表示每一對(duì)點(diǎn)之間的相似性:

式中：當(dāng)i=j時(shí)，Wij=0。

2)根據(jù)相似矩陣W計(jì)算度矩陣D，D是一個(gè)對(duì)角矩陣，它的非零元素是W的所有行元素(或者列元素)的總和：

3)根據(jù)D和W計(jì)算出拉普拉斯矩陣L，定義拉普拉斯矩陣有很多種方法。非標(biāo)準(zhǔn)化的拉普拉斯矩陣為

L=D?W

4)對(duì)L進(jìn)行標(biāo)準(zhǔn)化會(huì)產(chǎn)生更好的聚類效果，因此一般將拉普拉斯矩陣標(biāo)準(zhǔn)化形式表示為

Lnorm=D?1/2LD?1/2

還可以表示為

Lnorm=D?1/2WD?1/2

5)接下來計(jì)算標(biāo)準(zhǔn)化后的拉普拉斯矩陣的前k個(gè)最小特征值對(duì)應(yīng)的特征向量f，將各自對(duì)應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化，最終組成n×k維的特征矩陣F；

6)將F中的每一行作為一個(gè)k維的樣本(共n個(gè)樣本)，用k-means算法進(jìn)行聚類得到最終聚類結(jié)果。

1.2 極限學(xué)習(xí)機(jī)自編碼器

極限學(xué)習(xí)機(jī)自編碼器[19]是一種既可以再現(xiàn)輸入數(shù)據(jù)也可以自行編碼的神經(jīng)網(wǎng)絡(luò)方法，具有極限學(xué)習(xí)機(jī)的計(jì)算速度快、精確率高等特點(diǎn)。與傳統(tǒng)的極限學(xué)習(xí)機(jī)相似，ELM-AE包含輸入層、單隱含層以及輸出層；不同的是，ELM-AE的輸出層與輸入層相等。給定一個(gè)訓(xùn)練樣本，ELM-AE的模型結(jié)構(gòu)包括M個(gè)輸入層節(jié)點(diǎn)、J個(gè)隱層節(jié)點(diǎn)和M個(gè)輸出層節(jié)點(diǎn)。ELM-AE的隱含層輸出可以用式(1)表示：

式中：a是輸入層和隱含層之間的輸入；b是隱含層的偏置。隱含層輸出與ELM-AE的輸出層之間的數(shù)值關(guān)系可以用式(2)表示：

式中：β 是連接隱含層和輸出層的輸出權(quán)值；g(·)是激活函數(shù)。ELM-AE的目標(biāo)是通過最小化正則化最小二乘估計(jì)成本函數(shù)得到輸出權(quán)重，其公式為

式中：C是平衡經(jīng)驗(yàn)風(fēng)險(xiǎn)與結(jié)構(gòu)風(fēng)險(xiǎn)的參數(shù)。通過取L1對(duì) β 的偏導(dǎo)數(shù)并令其等于零，則輸出權(quán)值矩陣 β 為

2 ELM-AE特征空間的譜聚類算法

前面從理論層面分析了譜聚類及ELM-AE的特征提取方法。傳統(tǒng)的譜聚類是將原始數(shù)據(jù)樣本作為聚類初始值，而在實(shí)際應(yīng)用中數(shù)據(jù)通常冗余且復(fù)雜，能夠從原始數(shù)據(jù)中充分挖掘內(nèi)在信息，通過機(jī)器學(xué)習(xí)算法進(jìn)行特征學(xué)習(xí)，使用獲得的數(shù)據(jù)特征空間進(jìn)行譜聚類將有效提高聚類質(zhì)量。ELM可以隨機(jī)初始化輸入權(quán)重和偏置并得到相應(yīng)的輸出權(quán)重，然而隨機(jī)生成的輸入權(quán)值和偏差會(huì)導(dǎo)致ELM隱層的輸出不能很好地代表原始樣本的特征。ELM-AE是一種能夠重建輸入信號(hào)的人工神經(jīng)網(wǎng)絡(luò)算法，和自動(dòng)編碼器一樣，ELM-AE無需迭代可以獲得原始樣本的主要特征，與傳統(tǒng)的ELM不同的是，ELM-AE通過選擇隨機(jī)權(quán)重和隨機(jī)偏差正交，可以獲得更高的性能。通過ELM-AE的輸出β實(shí)現(xiàn)從特征空間到原始輸入數(shù)據(jù)的轉(zhuǎn)換，使得輸出數(shù)據(jù)等于輸入數(shù)據(jù)。

本文提出的基于ELM-AE嵌入特征空間的譜聚類是將ELM-AE的特征空間作為聚類原始值，從而提高聚類性能。SC-ELM-AE模型包含輸入層、單隱層和輸出層，其模型結(jié)構(gòu)如圖1，也具有M個(gè)輸入層節(jié)點(diǎn)，J個(gè)隱藏層節(jié)點(diǎn)和M個(gè)輸出層節(jié)點(diǎn)，然后如圖所示通過ELM-AE獲得輸出層權(quán)值β，ELM-AE輸出層的嵌入特征(embedding feature,EF)可由式(5)計(jì)算：

然后采用歸一化譜聚類算法將ELM-AE的嵌入特征(EF)作為聚類輸入數(shù)據(jù)點(diǎn)進(jìn)行聚類。SCELM-AE算法流程如圖1所示。基于ELM-AE嵌入特征空間的譜聚類算法(SC-ELM-AE)流程詳見算法1。

圖1 SC-ELM-AE算法流程Fig.1 Flow of SC-ELM-AE algorithm

算法1 基于ELM-AE嵌入特征空間的譜聚類

輸入 數(shù)據(jù)集樣本 (x1,x2,···,xn)，參數(shù)a和b；

輸出 基于EF空間的N個(gè)樣本的k個(gè)簇。

1)初始化由N個(gè)隱藏層神經(jīng)元組成的ELMAE網(wǎng)絡(luò)，計(jì)算隱藏層的輸出HELM?AE∈Rn×n，激活函數(shù)使用 S igmod(·)；

2)使用式(3)、(4)計(jì)算ELM-AE的輸出層權(quán)值；

3)使用式(5)計(jì)算嵌入特征EF，激活函數(shù)使用 S igmod(·)；

4)得到嵌入特征樣本 E F=(EF1,EF2,···,EFn)，初始化高斯相似度函數(shù)的參數(shù) σ，k個(gè)聚類；

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

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集說明

為了驗(yàn)證基于ELM-AE嵌入特征空間的譜聚類算法的有效性，選取了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的5個(gè)常用數(shù)據(jù)集進(jìn)行驗(yàn)證測(cè)試，數(shù)據(jù)集的基本特征如表1所示。

實(shí)驗(yàn)在MATLAB R2016b環(huán)境下實(shí)現(xiàn)，運(yùn)行在Windows 10上，實(shí)驗(yàn)中使用的計(jì)算機(jī)CPU 型號(hào)為Inter(R)Core(TM)i5-8250U @1.60 GHz，內(nèi)存為8 GB。本文所有實(shí)驗(yàn)中，ELM-AE模型包含輸入層、輸出層、隱藏層，為了方便實(shí)驗(yàn)，隱藏層、輸出層的激活函數(shù)都采用sigmoid函數(shù)。

實(shí)驗(yàn)使用的對(duì)比算法分別為：傳統(tǒng)譜聚類[25](spectral clustering，SC)、k-means聚類、基于無監(jiān)督極限學(xué)習(xí)機(jī)(unsupervised extreme learning machine US-ELM)的K-means聚類、基于ELM-AE嵌入特征的無監(jiān)督極限學(xué)習(xí)機(jī)[26](unsupervised extreme learning machine based on embedded features of ELM-AE, US-EF-ELM)k-means聚類算法。

本文中，k-means、SC、US-ELM和US-EFELM所有算法在數(shù)據(jù)集上運(yùn)行10次，記錄平均結(jié)果和標(biāo)準(zhǔn)差。根據(jù)文獻(xiàn)[20]在所有數(shù)據(jù)集上，US-ELM隱藏節(jié)點(diǎn)數(shù)和US-EF-ELM隱藏節(jié)點(diǎn)數(shù)均設(shè)置為2 000，US-ELM和US-EF-ELM的激活函數(shù)均為sigmoid函數(shù)。在SC-EF-ELM中，從{100、200、500、1 000、2 000}中選擇隱藏節(jié)點(diǎn)個(gè)數(shù)，激活函數(shù)也為sigmoid函數(shù)。在US-ELM、USEF-ELM和SC-EF-ELM中，正則化參數(shù)選取范圍為{10?4, 10?3, 10?2, 10?1, 100, 101, 102, 103, 104}，在SC和SC-EF-ELM中，核函數(shù)為高斯核函數(shù)，其中高斯核函數(shù)的參數(shù)為樣本間的中值距離。

3.2 性能指標(biāo)

當(dāng)參數(shù)a=1 時(shí)，就是F1指標(biāo)

式中：P是精確率(precision)度量值；R是召回率(recall)度量值。F1綜合了P和R的結(jié)果，當(dāng)F1較大時(shí)則比較說明實(shí)驗(yàn)結(jié)果比較理想。

ACC表示聚類結(jié)果中被正確劃分的數(shù)據(jù)點(diǎn)比例：

式中：n表示數(shù)據(jù)樣本的個(gè)數(shù)；當(dāng)x=y時(shí),則δ(x,y)=1， 否 則 δ (x,y)=0 。 map(·) 表 示 通 過Hungarian算法將每個(gè)聚類標(biāo)簽映射到一個(gè)類標(biāo)簽，并且映射是最佳。

NMI 衡量的是算法的劃分質(zhì)量：

NMI的值越大，聚類有效性越好。

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

所提出的SC-ELM-AE與k-means、SC、USELM和US-EF-ELM在5個(gè)數(shù)據(jù)集上的表現(xiàn)對(duì)比見表2。

表2 提出的SC-ELM-AE算法5個(gè)UCI數(shù)據(jù)集上的性能比較Table 2 Performance comparison of the proposed SC-ELM-AE on five UCI datasets

續(xù)表2

從表2中可以看出，本文所提出的SC-ELMAE算法在聚類準(zhǔn)確率上與對(duì)比算法相比在5個(gè)數(shù)據(jù)集上都有了較大提升。例如，對(duì)于高維數(shù)據(jù)集PEMS-SF，本文所提算法與對(duì)比算法相比在ACC上分別提升了33.2%、32.75%、31.46%、26.68%平均提升了31.02%。

SC-ELM-AE聚類算法利用ELM-AE模型無需迭代即可獲得低維特征表示空間，盡可能多地保留了原始數(shù)據(jù)集的豐富信息，使獲得的聚類結(jié)果更加準(zhǔn)確。實(shí)驗(yàn)數(shù)據(jù)結(jié)果表明，本文提出的SC-ELM-AE算法在進(jìn)行實(shí)驗(yàn)的數(shù)據(jù)集上與對(duì)比算法相比聚類精度有較大的提升，這也驗(yàn)證了本文所提算法的合理性和有效性。

為了驗(yàn)證提出的SC-ELM-AE算法在增加隱含層節(jié)點(diǎn)后的表現(xiàn)，在實(shí)驗(yàn)中將ELM-AE模型結(jié)構(gòu)的隱含層節(jié)點(diǎn)數(shù)從100增加到2 000，并在數(shù)據(jù)集WDBC和PEMS-SF上基于ELM-AE的嵌入特征空間進(jìn)行快速譜聚類，實(shí)驗(yàn)結(jié)果如圖2、3所示。

圖2 在數(shù)據(jù)集PEMS-SF上SC-ELM-AE的性能變化Fig.2 Performances for SC-ELM-AE on dataset PEMS-SF

從圖2可以看出：將ELM-AE特征表示空間作為譜聚類輸入，從(10?4,10?3,10?2)中選取正則化參數(shù)，當(dāng)隱藏節(jié)點(diǎn)較小，ACC、F-measure和NMI值較低。而在(10?1,100,101,102,103,104)選取正則化參數(shù)時(shí)，隱藏節(jié)點(diǎn)數(shù)量的變化基本不會(huì)引起算法性能的波動(dòng)。

從圖3可以看出，本文提出的SC-ELM-AE始終是穩(wěn)定的。因此，可以推斷參數(shù)的選擇對(duì)算法性能的影響不大，在合適的正則化參數(shù)下，采用很少的隱藏節(jié)點(diǎn)即可實(shí)現(xiàn)較高的聚類精度，與傳統(tǒng)的聚類方法相比，所提出的SC-ELM-AE算法具有更強(qiáng)的實(shí)用性。此外，在UCI的其他3個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果與推斷一致，也證明了所提SC-ELM-AE的性能的有效性。

圖3 在數(shù)據(jù)集WDBC上SC-ELM-AE的性能變化Fig.3 Performances for SC-ELM-AE on dataset WDBC

4 結(jié)束語

本文提出了一種通過ELM-AE特征表示空間的譜聚類算法。它利用ELM-AE將輸入的原始數(shù)據(jù)集轉(zhuǎn)化為數(shù)據(jù)特征表示空間，再對(duì)特征表示空間樣本集進(jìn)行譜聚類，利用ELM-AE獲得的特征空間可以更好地反映出原始數(shù)據(jù)的主要信息且計(jì)算成本較低；使用ELM-AE進(jìn)行特征提取，提高了聚類的準(zhǔn)確性。通過實(shí)驗(yàn)驗(yàn)證了本文算法在有效性和準(zhǔn)確性兩方面優(yōu)于現(xiàn)有的譜聚類算法，能夠快速有效地處理復(fù)雜高維數(shù)據(jù)。在未來的工作中需要考慮如何在保證聚類精確的情況下進(jìn)一步提高聚類的速度以及對(duì)大規(guī)模數(shù)據(jù)的處理。