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

王麗娟，丁世飛

（1. 中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116; 2. 徐州工業職業技術學院 信息工程學院，江蘇徐州 221114）

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

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

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

自編碼器(Auto Encoder AE)[16-17]是深度學習中的一種無監督學習方法，能夠從大量數據中自動學習到數據中的有效特征[18-20]。傳統自編碼器就是一種在輸出層重建輸入數據并且結構對稱的神經網絡。常見的自編碼器有降噪自編碼器、稀疏自編碼器、收縮自編碼器和卷積自編碼器等[21]。使用自編碼器進行特征提取要比特征分解快，并讓目標值等于輸入值，是一種盡可能復現輸入信號的神經網絡。

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

1 相關工作

1.1 譜聚類算法

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

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

1)根據一定的相似矩陣生成方式構建樣本的相似矩陣，W中的每一項表示每一對點之間的相似性:

式中：當i=j時，Wij=0。

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

3)根據D和W計算出拉普拉斯矩陣L，定義拉普拉斯矩陣有很多種方法。非標準化的拉普拉斯矩陣為

L=D?W

4)對L進行標準化會產生更好的聚類效果，因此一般將拉普拉斯矩陣標準化形式表示為

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

還可以表示為

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

5)接下來計算標準化后的拉普拉斯矩陣的前k個最小特征值對應的特征向量f，將各自對應的特征向量f組成的矩陣按行標準化，最終組成n×k維的特征矩陣F；

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

1.2 極限學習機自編碼器

極限學習機自編碼器[19]是一種既可以再現輸入數據也可以自行編碼的神經網絡方法，具有極限學習機的計算速度快、精確率高等特點。與傳統的極限學習機相似，ELM-AE包含輸入層、單隱含層以及輸出層；不同的是，ELM-AE的輸出層與輸入層相等。給定一個訓練樣本，ELM-AE的模型結構包括M個輸入層節點、J個隱層節點和M個輸出層節點。ELM-AE的隱含層輸出可以用式(1)表示：

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

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

式中：C是平衡經驗風險與結構風險的參數。通過取L1對 β 的偏導數并令其等于零，則輸出權值矩陣 β 為

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

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

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

然后采用歸一化譜聚類算法將ELM-AE的嵌入特征(EF)作為聚類輸入數據點進行聚類。SCELM-AE算法流程如圖1所示?；贓LM-AE嵌入特征空間的譜聚類算法(SC-ELM-AE)流程詳見算法1。

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

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

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

輸出 基于EF空間的N個樣本的k個簇。

1)初始化由N個隱藏層神經元組成的ELMAE網絡，計算隱藏層的輸出HELM?AE∈Rn×n，激活函數使用 S igmod(·)；

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

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

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

3 實驗結果與分析

3.1 實驗環境及數據集說明

為了驗證基于ELM-AE嵌入特征空間的譜聚類算法的有效性，選取了UCI機器學習數據庫中的5個常用數據集進行驗證測試，數據集的基本特征如表1所示。

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

實驗使用的對比算法分別為：傳統譜聚類[25](spectral clustering，SC)、k-means聚類、基于無監督極限學習機(unsupervised extreme learning machine US-ELM)的K-means聚類、基于ELM-AE嵌入特征的無監督極限學習機[26](unsupervised extreme learning machine based on embedded features of ELM-AE, US-EF-ELM)k-means聚類算法。

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

3.2 性能指標

當參數a=1 時，就是F1指標

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

ACC表示聚類結果中被正確劃分的數據點比例：

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

NMI 衡量的是算法的劃分質量：

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

3.3 實驗結果

所提出的SC-ELM-AE與k-means、SC、USELM和US-EF-ELM在5個數據集上的表現對比見表2。

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

續表2

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

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

為了驗證提出的SC-ELM-AE算法在增加隱含層節點后的表現，在實驗中將ELM-AE模型結構的隱含層節點數從100增加到2 000，并在數據集WDBC和PEMS-SF上基于ELM-AE的嵌入特征空間進行快速譜聚類，實驗結果如圖2、3所示。

圖2 在數據集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)中選取正則化參數，當隱藏節點較小，ACC、F-measure和NMI值較低。而在(10?1,100,101,102,103,104)選取正則化參數時，隱藏節點數量的變化基本不會引起算法性能的波動。

從圖3可以看出，本文提出的SC-ELM-AE始終是穩定的。因此，可以推斷參數的選擇對算法性能的影響不大，在合適的正則化參數下，采用很少的隱藏節點即可實現較高的聚類精度，與傳統的聚類方法相比，所提出的SC-ELM-AE算法具有更強的實用性。此外，在UCI的其他3個基準數據集上進行驗證，實驗結果與推斷一致，也證明了所提SC-ELM-AE的性能的有效性。

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

4 結束語

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