融合自動權重學習的深度子空間聚類

江雨燕，邵 金，李 平

（1.安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243032；2.南京郵電大學 計算機學院，南京 210023）

0 概述

聚類作為一種無監督的學習方法，廣泛應用于機器學習［1］、模式識別［2］等技術，其通過將數據劃分為多個有意義的簇從而達到分類的目的。例如，在人臉識別中，提取人臉特征后往往以特征點之間的距離為單位來衡量圖像的相似度，通過聚類分析將數據分為多個簇，將相似度高的數據劃分到同一簇中，從而挖掘數據之間的關系以得到正確的分類結果；在圖像分割中，為了更好地區分目標與背景，可以依據圖像的灰度、顏色、紋理等特征將其分割成幾個區域，通過度量不同區域的灰度值將目標特征劃分到同一區域，從而實現圖像分割的目的。

常見的聚類方法包括K-means［3］、層次聚類［4］、譜聚類［5］、子空間聚類［6］等。K-means 算法將數據點分配給最近的簇，更新每個簇的中心并重新分配所有數據點以達到聚類的效果，其性能簡單且高效，但是對異常點較為敏感。譜聚類是基于圖論而演化來的聚類方法，其對數據分布的適應性更強，可以識別非凸分布聚類，但是對輸入的相似圖十分敏感。子空間聚類是目前處理高維數據最流行的方法之一，常見的子空間聚類算法包括低秩表示（Low Rank Representation，LRR）算法［7］、低秩子空間聚類（Low Rank Subspace Clustering，LRSC）［8］、稀疏子空間聚類（Sparse Subspace Clustering，SSC）［9］、核化稀疏子空間聚類（Kernel Sparse Subspace Clustering，KSSC）［10］。其中，LRR 尋找字典中最低秩的表示以更好地捕獲數據結構，該方法在處理損壞數據時可以發揮關鍵作用；LRSC 提出一個聯合優化框架以求得閉合解，其能解決子空間聚類中噪聲及誤差的問題；SSC 利用稀疏表示方法處理數據，當處理分布在多個子空間上的高維數據時，由于其自表示模型的魯棒性而受到廣泛應用；KSSC是SSC基于核技巧的拓展，使用核技巧可以得到高維空間中的稀疏表示，使得數據線性可分，從而獲得更好的聚類結果。上述方法面對高維數據時取得了較好的聚類效果，但是，聚類精確性高度依賴于所學習到的相似圖。因此，改變相似圖學習方式能否提升聚類性能成為新的研究熱點。

為了獲得穩定且準確的聚類效果，NIE 等［11］提出一種自適應近鄰聚類（Clustering with Adaptive Neighbors，CAN），其設計新的相似圖學習方式，直接在數據空間中學習相似圖，基于局部距離為每個數據自適應分配近鄰，同時學習數據的相似性與聚類結構。此外，針對高維數據的處理問題，該文提出基于自適應近鄰聚類的投影（Projected Clustering with Adaptive Neighbors，PCAN）方法，這種新的相似圖學習方式取得了優異的效果并在實際場景中得到廣泛應用。但是，該方法在學習相似圖時未考慮不同特征的重要性。因此，文獻［12］提出一種自動權重的自適應近鄰聚類（Self-Weighted Clustering with Adaptive Neighbors，SWCAN），其對PCAN 進行改進，通過對每個特征賦予相對應的權重以提升聚類性能。

上述方法均通過CAN 獨特的相似圖學習方式獲得了良好的聚類效果，然而，它們依然存在以下問題需要解決：在處理高維非線性數據時，最優核函數的選擇依然存在困難；為數據分配近鄰的方式考慮到了全局數據結構但未兼顧局部數據結構。

近年來，在無監督聚類任務中，隨著深度學習技術的發展［13］，自編碼器的應用日益廣泛。自編碼器具有可壓縮性，可以學習到原始數據中的重要特征，原始數據由編碼層投影到潛在空間獲得低維的潛在表示，再由解碼層重構數據，通過最小化重構誤差保留數據局部結構信息。JI 等［14］提出一種深度子空間聚類網絡（Deep Subspace Clustering Network，DSC-Net），其在編碼層與解碼層之間加入自表示層，以模仿子空間聚類中的自表示。XIE 等［15］提出無監督深度嵌入聚類（Deep Embedded Clustering，DEC），其通過軟分配方法學習數據類別，使用深度網絡同時學習數據表示與聚類。LI等［16］提出基于自編碼器的自適應近鄰聚類，其通過引入自編碼器自適應地學習數據的非線性結構，同時更新潛在表示及相似圖。文獻［17］改進DSC-Net的自表達層，使之由參數化的全連接層變為一個無需參數的閉合解。上述算法利用自編碼器的特性能夠保留局部數據結構，但是它們認為所有特征的重要性都一致且未考慮數據的全局結構。基于以上分析，為了處理高維非線性數據同時提升聚類準確性及算法泛化能力，在聚類過程中必須兼顧全局與局部數據結構，并根據不同特征、不同重要性來對深度聚類方法進行設計與驗證。

本文提出融合自動權重學習與結構化信息的深度子空間聚類（Deep Subspace Clustering Fused with Auto-Weight Learning and Structured Information，DSC-AWSI）算法。對自編碼器進行預訓練與微調，利用自編碼器將原始數據投影到非線性潛在空間以學習數據的潛在表示，根據特征重要性的不同自適應地賦予各特征權重，從而學習相似圖并完成聚類。

1 相關工作

1.1 自適應近鄰聚類

假設數據矩陣X={x1,x2,…,xn}?Rn×d，其中，n表示樣本數量，d表示維度。每列數據點xi的近鄰可以被定義為k-nearest 個數據點，將歐氏距離作為距離度量單位。所有與xi相近的數據點都有一個對應的近鄰概率aij，若較小，則對應的aij往往較大，其目標函數如下：

其中：ai?Rn×1是一個向量；1是所有元素均為1 的向量。式（1）有平凡解，即當概率為1 時其他數據點無法被分配為xi的近鄰。為解決該問題，加入正則約束，如式（2）所示：

其中：γ為正則化參數=1；L為拉普拉斯矩陣，表示塊對角的相似圖；DA為相似圖A的度矩陣（對角矩陣），對其添加低秩約束Rank(L)=n-c，n為樣本數量，c為類別數量，為了以清晰的結構實現理想的近鄰分配，連接分量必須是準確的c值。對于每一個數據點xi，均可以通過式（2）為其分配近鄰。為了實現理想的近鄰分配使之成為自適應的分配過程，概率應該被施加約束，目的是無需使用K-means 或其他離散方法也能使連接元素被劃分為c個類別。

1.2 自編碼器

自編碼器通過其編碼器與解碼器的特性，在無監督的場景下可以將原始數據非線性地投影到一個潛在空間，該過程是一種非線性降維。自編碼器的作用是利用編碼層將高維輸入數據編碼為低維數據，然后提取低維數據的顯著特征［18］，自編碼器本質上可以作為特征提取器，再通過解碼層解碼將提取到的特征還原到初始維度，從而得到重構數據［19］。假設神經網絡具有m+1 層結構，執行m層非線性轉化，對每個輸入xi都有對應的潛在表示和重構輸出，X={x1,x2,…,xn}?Rn×d為原始輸入數據x，則神經網絡的計算過程為：i

首先，將原始數據映射到潛在空間Z={z1,z2,…,zn}?Rl×n，其中，l

2 模型與優化

現有很多聚類方法對大規模數據及噪聲敏感，在處理高維數據時往往需要犧牲聚類質量來解決離群樣本及大規模擴展問題［20］。為此，一些優秀的特征選擇方法被引入到聚類任務中［21-22］，該類方法提取感興趣的特征從而提升聚類效果。本文引入自編碼器作為非線性數據處理方法，同時結合文獻［12］中的自動權重學習思想，賦予噪聲特征較低權重、有效特征較高權重，根據特征不同的重要性來為潛在空間中所學習到的特征賦予不同的權重。本文算法流程如圖1 所示。

圖1 本文算法流程Fig.1 Procedure of this algorithm

2.1 深度聚類模型

對于所有數據點X={x1,x2,…,xn}?Rn×d，通過自編碼器的編碼層將數據轉換到潛在空間，得到良好的特征表示Z={z1,z2,…,zn}?Rl×n。解碼層重構數據，表示為則損失函數?1可以表示為：

其中：第一項通過最小化輸入與輸出之間的重構誤差來保留局部數據結構，相比常見的核方法，該自編碼器具有更好的顯式轉換效果及更高的可伸縮性；第二項是正則化項，通過限制神經網絡中權重與偏執的大小來避免模型過擬合。

通過編碼層轉換后，學習到的特征表示為Z={z1,z2,…,zn}?Rl×n，原始數據得到了更好的低維表征。但是，不同特征的重要性不同，在實際應用中往往沒有足夠的先驗知識來判斷各個特征的重要性。為了使模型更具魯棒性，需要針對有效特征、噪聲特征設置不同的權重，即對潛在空間的數據矩陣Z賦予不同的權重，且這種自動學習權重的方式不會改變數據的結構信息。因此，本文受文獻［11-12］方法的啟示，將式（2）改寫為：

其中：c為類別數量：W表示權重矩陣，其為一個對角矩陣，每個wi值對應一個zi特征，不同的特征自適應地學習權重；W=diag(wk),0 ≤wk≤1,k=1,2,…,d。目標函數的第一項是學習自動權重與自適應近鄰的過程，根據W賦予特征Z不同的權重，再進行自適應近鄰過程，學習相似圖并實現聚類；第二項是低秩約束項，拉普拉斯矩陣L是半正定的［23］，為了對L施加低秩約束，令σi(L)表 示L的第i個最小特征值，σi(L)≥0，根據Ky Fan’s定理［24］中的進行推導得出，其作用等同于式（2）中的Rank(L)=n-c。

綜上，本文算法的損失函數?sum=?1+λ?2，具體計算如下：

其中：δ、λ是非負權衡的參數。式（7）右側第一項為最小化自編碼器輸入與輸出的重構誤差；第二項為正則化項，限制神經網絡中的權重和偏置；第三項為聚類損失，在學習相似圖A的同時根據特征重要性賦予不同的權重wi，A必須為塊對角結構，F的最優解是由拉普拉斯矩陣L的c個特征向量對應的最小的c個特征值而構成的。通過本文模型將原始數據投影到低維潛在空間，學習到的特征表示能夠兼顧全局與局部的數據結構，同時為不同的特征賦予相對應的權重，從而指導后續聚類工作。

2.2 算法優化

2.2.1P,b更新子問題

其中：g′(·)為激活函數g(·)的導數，g′(x)=tanh′(x)=1-tanh2(x)；⊙表示逐元素相乘。

在執行算法前先對所設計的神經網絡進行預訓練與微調，從而得到初始化的P(m)、b(m)。根據式（8）、式（9），利用隨機梯度下降（Stochastic Gradient Descent，SGD）法迭代更新如下：

其中：η表示學習率。

2.2.2W更新子問題

固定?sum中的其他變量，除去無關項，對W更新如下：

s.t.WT1=1,0≤wk≤1,k=1,2,…,d,W=diag(w)（13）

定理1假設L為相似圖A的拉普拉斯矩陣，矩陣Q?Rn×c的第i行表示為則有：

根據定理1［12］，假設qi=Wzi?Rd×1，即Q=WZ，則有：

再考慮約束WT1=1，式（17）的拉格朗日函數可以寫為：

對拉格朗日函數求導并令其等于0，有：

將約束WT1=1 代入式（19）中，則有：

結合式（19）與式（20），對于wi的更新如下：

2.2.3A更新子問題

固定?sum中的其他變量，除去無關項，假設?R1×c表示矩陣F?Rn×c的第i行，根據定理1，對A更新如下：

由于式（22）在每個i之間是獨立的，因此可以對其進行簡化以獨立解決每個i的A更新問題，如下：

對式（24）使用交替迭代的方法進行更新，其拉格朗日函數如下：

其中：α、β≥0均為拉格朗日乘子。根據KKT 條件［25］，可推導出：

其中：(·)+表示max(·,0)。若ai僅有k個非零元素，可推出aik>0,ai,k+1=0。根據文獻［11］可知，參數γi的取值可以控制數據點的k個近鄰數量。在擁有k近鄰數據下，學習一個稀疏的相似圖A有助于減少后續的計算成本。為了不失一般性，假設?i,，ai有k個近鄰，則有：

將式（27）與式（28）相結合，可得：

為了獲得具有k個非零值的ai的優化解，令：

考慮到γ=[γ1,γ2,…,γn]，此處假設γi=γ，對γ的求解則可轉化為對每個γi相加求均值，如下：

根據式（26）與式（31）可推導出ai中第j個元素的閉合解為：

特別地，當j0；當j≥k+1 時，aij=0。

2.2.4F更新子問題

固定?sum中的其他變量，除去無關項，F更新子問題如下：

根據Ky Fan’s 定理［24］，最優解F由拉普拉斯矩陣L的c個特征向量所對應的c個最小的特征值構建。由于算法需要設計準確的c值，因此最優解F可以直接用于聚類任務，無需K-means 或者其他離散方法。

基于上述分析，本文DSC-AWSI 算法描述具體如算法1 所示。

算法1DSC-AWSI 算法

2.3 復雜度分析

本文所提模型設定的隱藏層數M=2，模型包含神經網絡反向傳播訓練及聚類過程，聚類優化過程分為3 個子問題，A更新子問題的復雜度為O(nd2+n2d)，F更新子問題的復雜度為O(n3)，W更新子問題的復雜度為O(n2d)，聚類過程的總復雜度為O(n3+ndmax(n,d))。假設自編碼器中隱藏層的維度最大值為D，則算法的總復雜度為O(n3+ndmax(n,d)+nD2)。

3 實驗結果與分析

3.1 實驗設置

為了驗證本文算法的有效性，使用較為常見的幾種聚類算法在多種數據集上進行實驗測試，并選取10次實驗的平均值作為結果。實驗環境為AMD Ryzen 2600X處理器、16 GB RAM、顯卡配置GeForce GTX 1660ti，在Windows 10 系統上進行實驗。

在ORL、COIL-20、UMIST 這3 個數據集上進行實驗測試：

1）ORL 數據集中包含40 個人在不同的光照、時間和表情下的400 幅面部圖像。

2）COIL-20 數據集包含20 個物體在不同旋轉角度下的圖像，每個物體有72 幅圖像。

3）UMIST 數據集包含20 個人的575 幅圖像，每個人具有不同角度、不同姿態的多幅圖像。

上述數據集中的圖像都為32×32 像素，數據集具體描述如表1 所示。

表1 實驗數據集信息Table 1 Experimental datasets information

在實驗過程中，自編碼器的隱藏層數M=2，隱藏層維度設置為400維-200維-400維（以下簡寫為400-200-400），類別數目c根據數據集設置不同值，近鄰數目k在（2，50）區間內取值，從而觀察不同k值下算法的聚類性能（由于k為近鄰數目，值為0 或1 均不合理）。設置γ=-1，μ為拉普拉斯矩陣約束參數，為了加速收斂過程，令μ=γ，在每次迭代中，若相似圖A的連通分量遠小于c，則增大μ，反之則減小μ。學習率η設置為η=2-12，δ設置為固定值10-3，根據不同數據集，參數λ從{5×10-4,10-3,5×10-3,10-2,5×10-2,10-1}中選出最優值。此外，當網絡的均方誤差損失最小值小于10-3或迭代次數達到400 時，則默認算法收斂。

3.2 結果分析

將本文算法與6 種常見的聚類算法在上述數據集上進行實驗，對比算法包括LRR［7］、LRSC［8］、SSC［9］、KSSC［10］、CAN［11］、SWCAN［12］。上述6 種算法均由原作者提供的代碼進行實驗，為確保公平性，算法具體參數根據原論文設置為最優，在最優參數下進行結果對比。使用常見的聚類指標ACC（Accuracy）、NMI（Normal Mutual Information）來衡量算法的聚類性能，實驗結果如表2 所示，最優結果加粗表示。

表2 各算法在3 個數據集上的實驗結果對比Table 2 Comparison of experimental results of each algorithm on three datasets

從表2 可以看出，相比子空間聚類算法及自適應近鄰聚類算法，本文算法在公開數據集上可以得出更好的聚類效果：在COIL-20 數據集上本文算法的ACC 相比CAN、SWCAN算法提高了6.6 和3.23 個百分點；在ORL 數據集上本文算法的ACC 相比CAN、SWCAN 算法提高了3.51 和1.75 個百分點；在UMIST 數據集上本文算法的ACC、NMI 值相比CAN、SWCAN 平均提高了6.94 和5.12 個百分點，這說明引入自編碼器可以在特征選擇時更好地保持局部數據結構，驗證了深度網絡處理高維非線性數據的有效性，同時也體現出自動權重學習通過賦予特征權重的方式能夠解決噪聲數據問題，使得鄰接矩陣能夠取得更好的學習效果。但是，本文算法的NMI 值與SWCAN 算法相差較小，原因可能是兩者的子空間相似圖學習方式相同。在ORL 數據集上，本文算法的NMI 值低于SSC 算法，原因可能是本文算法沒有使用數據自表示以及對相似圖的分割沒有使用譜聚類，這說明了數據自表示方法有利于加強相同簇內數據點之間的聯系。

圖2～圖4 分別表示在不同數據集上根據迭代次數增加的神經網絡訓練的重構損失變化。從中可以看出，在迭代400 次以后，COIL-20 數據集上的均方誤差最低達到0.017 88，ORL數據集上的均方誤差最低達到0.060 34，UMIST 數據集上的均方誤差最低達到0.039 986，即隨著迭代次數的增加，通過深度網絡訓練的重構誤差逐漸減小，表明在影響（誤差）較小的情況下能夠通過深度網絡保留數據局部結構。

圖2 深度網絡在COIL-20 數據集上的均方誤差Fig.2 Mean square error of depth network on COIL-20 dataset

圖3 深度網絡在ORL 數據集上的均方誤差Fig.3 Mean square error of depth network on ORL dataset

圖4 深度網絡在UMIST 數據集上的均方誤差Fig.4 Mean square error of depth network on UMIST dataset

由于特征權值有部分是稀疏的，因此在某些維度上判別性較低。圖5～圖7 給出不同數據集下學習到的各個特征的不同權重，圖中橫坐標為200 維特征，縱坐標為權重。根據學習到的特征權重值可以區分有效特征、噪聲特征、無用特征，因此，自動學習權重的方式可以學習判別性低的特征，從而有效指導后續的聚類工作。

圖5 在COIL-20 數據集上學習到的特征權重Fig.5 Feature weights learned on COIL-20 dataset

圖6 在ORL 數據集上學習到的特征權重Fig.6 Feature weights learned on ORL dataset

圖7 在UMIST 數據集上學習到的特征權重Fig.7 Feature weights learned on UMIST dataset

本文相似圖學習方法與CAN、SWCAN 算法相同，近鄰數k值在很大程度上影響了聚類準確率，為了測試k值變化對算法性能的影響，將k的取值區間設置為（2，50）以顯示不同的聚類結果。通過圖8～圖10 可以看出，在COIL-20 數據集上，當k=5時聚類準確率達到最優，在ORL 數據集上，當k=3時聚類準確率達到最優，在UMIST 數據集上，當k=4 時聚類準確率達到最優。從中可知，k值對于聚類效果較為敏感，通過對k值進行調整能夠提升算法性能。

圖8 在COIL-20 數據集上不同k 值的聚類結果Fig.8 Clustering results of different k values on COIL-20 dataset

圖9 在ORL 數據集上不同k 值的聚類結果Fig.9 Clustering results of different k values on ORL dataset

圖10 在UMIST 數據集上不同k 值的聚類結果Fig.10 Clustering results of different k values on UMIST dataset

為了研究深度網絡中隱藏層的大小對算法性能的影響，分別使用600-200-600、400-200-400、400-150-400這3 種不同維度的隱藏層進行實驗，結果如圖11、圖12所示。從中可以看出，當隱藏層的維度設置為400-150-400 時，算法的ACC 與NMI 值均低于400-200-400，但均高于600-200-600；當隱藏層的維度設置為600-200-600 時，3 個數據集下算法的ACC 與NMI值均低于其他2 種情況。因此，深度網絡的隱藏層維度設置為400-200-400 時最優。

圖11 不同網絡層數對算法ACC 值的影響Fig.11 Influence of different network layers on ACC value of algorithm

圖12 不同網絡層數對算法NMI 值的影響Fig.12 Influence of different network layers on NMI value of algorithm

4 結束語

近年來，子空間聚類由于其計算效率高、易處理等特性而得到廣泛研究與應用，然而，子空間學習方式在對高維非線性數據進行聚類時難以很好地捕獲局部數據結構。因此，本文提出一種融合自動權重學習的深度聚類算法，通過端到端的學習方式，引入自編碼器將特征投影到潛在空間并進行降維，從而實現子空間聚類。該算法能夠兼顧全局數據結構與局部數據結構，并通過自適應學習特征權重的方式賦予潛在空間特征不同的權重，其中，賦予有效特征更高的權重，賦予噪聲特征更低的權重，以此獲得更好的聚類效果。在公開數據集上進行對比實驗，結果表明，該算法的聚類效果優于LRR、LRSC、SSC 等算法。下一步將在深度網絡設計中加入生成對抗網絡，以更精確地判別所學習到的特征，提升算法的聚類性能。