投影自表示無監督極限學習機

汪巧萍，陳曉云

(福州大學數學與統計學院，福建 福州 350108)

0 引言

子空間聚類是數據聚類的有效方法之一，在計算機視覺、機器學習等領域引起了廣泛的關注.對高維數據進行子空間聚類時，主要存在以下兩個問題： 1) 高維數據中存在大量無關的屬性使樣本中存在簇的可能性很?。?) 高維空間中數據分布稀疏，刻畫樣本間相似度困難.因此, 研究面向聚類任務的降維方法是必要的.典型的線性降維方法有： 主成分分析[1](以最大化投影散度為目標)、局部保持投影[2]、近鄰保持嵌入[3](以保持原數據近鄰結構為目標降維).當數據非線性分布時，上述線性降維算法無法有效提取特征.

無監督極限學習機(unsupervised extreme learning machine，US-ELM)和極限學習機自編碼器(extreme learning machine auto-encoder，ELM-AE )是兩類典型的非線性降維方法.無監督極限學習機如US-ELM[4]和SNP-ELM[5]，US-ELM通過投影后樣本的近鄰結構保持不變實現降維；SNP-ELM通過投影后的樣本同時保持樣本的稀疏性和局部近鄰不變學習投影矩陣.極限學習機自編碼器如ELM-AE[6]、GELM-AE[7]，ELM-AE引入自編碼器的思想，網絡輸出和輸入保持不變為目標學習降維投影矩陣；GELM-AE在ELM-AE的基礎上引入局部流形思想，保持數據全局和局部結構實現降維.

上述極限學習機方法基于全局或局部保持不變的思想進行降維，但是忽視了樣本集所特有的簇類子空間結構信息.本研究在US-ELM基礎上引入子空間聚類的自表示模型[8]，提出投影自表示無監督極限學習機(projected self-expressive unsupervised extreme learning machine，PS-ELM)模型.PS-ELM同時學習降維投影矩陣β和投影后樣本的自表示矩陣Z，通過交替迭代更新β和Z，可提取更加有效的低維特征和更接近數據本質特征的自表示矩陣.

1 無監督極限學習機

無監督極限學習機US-ELM是單隱含層前饋神經網絡，第一過程先將輸入數據映射到r維(r是隱含層節點數)特征空間中. 給定數據矩陣X=[x1,x2, …,xn]∈Rm×n，m是樣本的維度，n是樣本數目，H(xi)=[g(w1,b1,xi),g(w2,b2,xi), …,g(wr,br,xi)]T∈Rr，輸入數據映射到r維的特征空間H(xi). 其中g為激活函數，如Sigmoid函數. 權重w和偏置b隨機初始化，則X在隱含層輸出為：

(1)

第二過程是求解輸出權重矩陣β∈Rd×r，d是樣本投影后的維度，樣本xi經過US-ELM輸出為yi=βH(xi)∈Rd. US-ELM隱含層向輸出層投影時對原始空間中距離相近的樣本點加大懲罰使得投影后樣本仍保持近鄰關系，最小化目標函數如下:

(2)

其中:wij表示樣本xi和樣本xj的相似度.wij定義如下：

(3)

這里，Nk(xi)為樣本xi在原空間中的k近鄰集合. 經過代數運算得到US-ELM目標函數為：

(4)

(I+λH(X)LH(X)T)v=θH(X)H(X)Tv

(5)

2 投影自表示無監督極限學習機

2.1 基于自表示學習的子空間聚類

給定原始樣本數據矩陣X∈Rm×n，m為樣本的維數，n為樣本數目. 基于自表示學習的子空間聚類模型的基本框架為：

(6)

其中：Z∈Rn×n是自表示矩陣，可用來衡量樣本間的相似度，對角陣為0的約束是為了避免平凡解即樣本被自身完全表示. 對Z的范數約束常用l1范數[9]、核范數[10]、Frobenius范數[11]. 在實際生活中, 數據往往含有噪聲, 因此松弛式(6)得：

(7)

2.2 投影自表示無監督極限學習機模型

由于高維數據存在一定的冗余信息，導致自表示矩陣不能刻畫數據之間的本質關系.SNP-ELM保持高維數據中的稀疏性和近鄰表示，但是在低維空間中這兩種結構不一定保持.針對上面的問題，本研究提出投影自表示無監督極限學習機(PS-ELM)模型.在投影過程中引入自表示模型指導學習投影矩陣β，反過來投影后的樣本特征用于學習樣本間的自表示矩陣Z，從而有利于子空間聚類，具體模型如下：

(8)

這里，λ和η是平衡參數. 第一項是控制模型復雜度的正則項，第二項約束自表示矩陣Z塊對角結構，第三項使投影后的樣本保持數據局部流形結構，第四項是投影樣本的自表示誤差，為了避免平凡解，算法加入正交約束βH(X)H(X)TβT=I.PS-ELM模型的網絡結構如圖1所示，Y是投影后的特征空間，Z是Y的自表示矩陣，兩個過程聯合優化，使得投影和子空間聚類任務相互適應. 目標函數有兩個變量β和Z，為求解模型，采用交替迭代二乘法ALS[12]進行求解.

圖1 投影自表示無監督極限學習機結構圖Fig.1 The network structure of projected self-expressive unsupervised extreme learning machine

首先固定Z，使得投影樣本保持子空間結構Z求解投影矩陣β，則模型(8)可以轉化為：

(9)

(10)

為求解模型(10)，利用拉格朗日乘子法得到以下拉格朗日函數：

L(β)=tr(βTβ)+λtr(βH(X)LH(X)TβT)+ηtr(βH(X)AH(X)TβT)+

θtr(βH(X)H(X)TβT-I)

(11)

這里:θ是拉格朗日參數令?L/?β=0得：

(I+λH(X)LH(X)T+ηH(X)AH(X)T)βT=θH(X)H(X)TβT

(12)

求解關于矩陣M=I+λH(X)LH(X)T+ηH(X)AH(X)T和矩陣N=H(X)H(X)T的廣義特征值問題(12)得到最小的d個特征值及對應的特征向量構成輸出權重矩陣β.

當r>n時，H(X)H(X)T∈Rr×r的維數較高，直接求解式(12)的廣義特征值問題的計算復雜度較高. 根據文獻[13]的方法, 可令β=αTH(X)T, 式(11)兩邊同時左乘(H(X)TH(X))-1H(X)T得到：

(I+λLH(X)T(X)+ηAH(X)TH(X))α=θH(X)TH(X)α

(13)

因此解得廣義特征值問題(13)的最小的d個特征值及對應的特征向量構成矩陣α，從而可得模型(12)的解β=αTH(X)T.

其次固定投影矩陣β，利用樣本的低維表示βH(X)指導學習子空間自表示矩陣Z，目標函數如下：

(14)

目標函數(14)關于Z的拉格朗日函數為：

L(Z)=tr(ZTZ)+ηtr(βH(X)AH(X)TβT)

(15)

令?L/?Z=0，可以得到：

Z=(I+ηH(X)TβTβH(X))-1H(X)TβTβH(X)

(16)

綜上分析，投影自表示無監督極限學習機PS-ELM算法如下：

PS-ELM算法Input: 數據集X∈Rm×n, 平衡參數參數λ, η, 和最大迭代次數maxiter.Output: 降維后樣本矩陣Y=βH(X), 自表示矩陣Z, 聚類結果.Initialization: 隨機初始化w和b, 并計算隱含層輸出矩陣H(X), ε=10-5, iter=1, 利用最小二乘子空間聚類LSR計算原始數據X的自表示矩陣Z, 利用式(3)計算樣本之間的相似度矩陣W.Step 1: Repeat: if rmaxiter.Step2: 應用譜聚類N-Cuts算法對鄰接矩陣Z?=(Z+ZT)進行分割.Step 3: 對降維后的樣本矩陣Y=βH(X)∈Rd×n應用k-means聚類.

PS-ELM算法計算k近鄰圖的時間復雜度為O(n2)；求解自表示矩陣Z的復雜度為O(n2r)；求解投影矩陣β時若求解廣義特征值式(12)，則其時間復雜度為O(r3)，若求解廣義特征值式(13)的時間復雜度為O(n3)，則總的時間復雜度為O(n3+n2r).

3 實驗結果與分析

PS-ELM是面向聚類的降維方法，本研究設計兩個實驗，分別是數據降維的二維可視化和面向聚類的高維數據降維實驗.實驗基于MATLABR2016a編程實現，實驗環境為Win7系統，內存8 GB.ELM-AE、US-ELM、SNP-ELM和本研究方法PS-ELM均采用sigmoid激活函數，其中US-ELM、SNP-ELM、PS-ELM的近鄰數k和隱含層節點個數r分別設置為5和1 000，正則參數取值范圍為{10-4, 10-3, 0.5×10-3, 10-2, 0.5×10-2, 0.5×10-1, 10-1, 1, 5, 101, 102, 103}.

3.1 數據可視化實驗

IRIS數據集由三種鳶尾花組成，每個樣本有4個維度的特征.分別用ELM-AE、US-ELM、SNP-ELM和本研究方法PS-ELM將IRIS數據集投影到2維空間，直觀地展示低維投影.4種算法分別選取聚類準確率最好的降維結果進行展示，可視化結果如圖2所示.從圖2中看出上述幾種降維方法能夠將以藍色為代表的一類樣本較好地分離，而第二類和第三類樣本仍少部分重疊.其中US-ELM和ELM-AE投影得較為分散，簇類聚集性不高.SNP-ELM保持原始數據的稀疏性和局部近鄰不變，因而能夠比較好地將同類樣本聚集在一起.本研究提出的PS-ELM算法面向子空間聚類進行降維，學習投影后樣本的子空間結構，使得降維后同類樣本聚集性最高，而類間樣本的距離較大，有利于聚類.

(a) ELM-AE

(b) US-ELM

(c) SNP-ELM

(d) PS-ELM

3.2 聚類實驗

圖3 2個醫學圖像數據集部分示例圖Fig.3 Partial examples of two medical image data sets

實驗采用6個高維基因表達數據集，2個醫學圖像數據集BreastMNIST[14]和PneumoniaMNIST[15]驗證所提方法面向聚類任務的有效性.BreastMNIST數據集收集了年齡在25歲到75歲之間女性的乳腺超聲圖像，正常和良性圖像作為陰性，惡性圖像作為陽性.PneumoniaMNIST數據集收集了兒童的胸部X光圖像，包括肺炎(細菌性和病毒性肺炎)圖像和正常圖像，實驗隨機選取其中的1 000張圖像.2個醫學圖像數據集部分示例展示如圖3.8個數據集的描述在表1，所有的實驗數據集都經過統一的標準化處理.以投影樣本的聚類準確率衡量降維質量，聚類準確率(accuracy, ACC)[16]計算公式為：

(17)

其中：n為樣本數;si和ri為真實標簽和預測標簽; map(·)將聚類得到的類標簽映射成與真實類標簽等價的類標簽, 當si=map(ri)時，δ(si, map(ri))=1，否則等于0 .

表1 數據集描述

PS-ELM方法求解得到β和Z后有兩種方式求解聚類結果，一是用k-means對降維后的樣本進行聚類，二是利用譜聚類對自表示矩陣Z進行分割.故實驗選取US-ELM、ELM-AE、SNP-ELM將樣本投影到{21, 22, 23, …, 2n}維用k-means聚類進行尋優并進行對比.同時選取文獻[8]中的投影最小二乘子空間(projection least square regression, PLSR)和投影低秩表示(projection low rank representation, PLRR)進行對比，對投影過程中學習的自表示矩陣Z執行N-cuts聚類.所有算法在每個數據集遵循參數尋優方法，并執行10次實驗取聚類準確率的均值和標準差，實驗結果如表2所示.

表2 八個數據集上的聚類準確率對比

從表2可以得出以下幾點結論：

1) ELM-AE僅保持自身的全局結構，相對于保持局部流形的US-ELM的聚類準確低.本研究提出的PS-ELM方法在US-ELM基礎上引入自表示模型，在投影過程中學習子空間結構適應于譜聚類，反過來子空間結構指導學習投影矩陣，聚類準確率得到大大提升.

2) SNP-ELM保持的原始高維數據的稀疏和局部近鄰結構不一定適應于低維空間.而本研究方法PS-ELM在投影過程中自適應學習子空間結構，除了在PneumoniaMNIST數據集用k-means聚類比SNP-ELM低0.5%，在其他數據集上的聚類準確率比SNP-ELM高.

3) PLRR和PLSR在子空間聚類模型中引入線性投影矩陣，降維過程中同時學習自表示矩陣，然而線性投影方法只能提取高維數據的線性特征，而本研究方法PS-ELM可以提取非線性的特征，經過多個數據集的對比，PS-ELM聚類準確率提高1.20%～24.3%.

4) PS-ELM在6個高維基因數據集上的提升范圍為0.79%～35.35%，而針對樣本數目較多、醫學背景復雜的2個醫學影像數據集提升范圍在2.39%～12.38%.對比PS-ELM的兩種聚類方式，用自表示矩陣Z執行譜聚類的效果比投影樣本執行k-means聚類更理想，證明了本研究所提方法是一種有效的面向子空間聚類的非線性投影算法.

3.3 參數分析

PS-ELM方法有2個正則參數λ和η，分別用來平衡流形正則項和子空間自表示誤差項，以LEUKEMIA1和DLBCL數據集為例，選取最優的投影維度d并討論這兩個參數對最終實驗聚類準確率的影響.

從圖4可以看出，當λ值在0.001～1.000之間，η取值在0.01～10.00之間時，PS-ELM方法的聚類效果更好.總的來說，對高維數據而言，λ和η取值較小時本研究方法能達到較好效果.

(a) LEUKEMIA1

(b) DLBCL

4 結論

本研究提出投影自表示無監督極限學習機PS-ELM方法，通過優化學習自表示矩陣和無監督極限學習機的投影矩陣，不僅保持了原有數據的局部流形結構，且投影過程中自適應地學習子空間結構，較好地適應子空間聚類.實驗結果表明在高維的基因表達數據集和醫學圖像數據集上表現突出，算法的性能優于其他面向聚類的降維方法.