摘 要：特征提取是處理高維數(shù)據(jù)的最有效工具之一。然而，當前特征提取方法存在兩個問題：一是它們沒有同時捕捉數(shù)據(jù)的局部和全局結(jié)構；二是構建的圖脫離數(shù)據(jù)的聚類數(shù)，沒有與聚類相同的連通分量。為了解決這些問題，提出了面向無監(jiān)督特征提取的結(jié)構化圖嵌入方法（structured graph embedding，SGE）。通過構建數(shù)據(jù)表征的K近鄰和使用最小二乘回歸，SGE能夠同時保持數(shù)據(jù)的局部與全局相關結(jié)構。而且，SGE對表征圖的拉普拉斯矩陣施加秩約束，使構建的最優(yōu)圖具有與c個聚類一致的c個連通分量，從而能揭示數(shù)據(jù)的聚類結(jié)構。因此，SGE能夠找到更有判別力的投影。在多個真實數(shù)據(jù)集的實驗表明，SGE優(yōu)于其他主流降維方法。特別是在PIE數(shù)據(jù)集上，SGE的聚類精度比LRPP_GRR的聚類精度高出18.7%。這些結(jié)果表明SGE方法可以有效降低數(shù)據(jù)維數(shù)。

關鍵詞：特征提??；局部結(jié)構；秩約束；最小二乘回歸

中圖分類號：TP181 文獻標志碼：A 文章編號：1001-3695（2024）11-020-3343-07

doi：10.19734/j.issn.1001-3695.2024.03.0072

Structured graph embedding for unsupervised feature extraction

Yuan Fengyan^{1， 2}， Yin Xuesong^2?， Wang Yigang²

（1.Pinghu School， Zhejiang Open University， Pinghu Zhejiang 314200， China; 2. Dept. of Digital Media Technology， Hangzhou Dianzi University， Hangzhou 310018， China）

Abstract：Feature extraction is one of the most effective tools for processing high-dimensional data. However， existing feature extraction methods suffer from two problems： they do not capture both the local and global structures of the data simultaneously， the constructed graph is disconnected from the number of data cluster and does not have an exact connected component. To address these issues， this paper proposed a SGE for unsupervised feature extraction. By constructing K-nearest neighbor graph for data representation and using least squares regression， SGE can simultaneously respect the local and global correlation structures of the data. Moreover， by enforcing rank constraints on the Laplacian matrix of the representation， SGE constructed the optimal graph of c connected components with c clusters， and thus revealed the clustering structure of the data. Therefore， the proposed SGE can find more discriminative projections. Experiments on real-world datasets show that SGE outperforms other mainstream dimensionality reduction methods. Especially on the PIE dataset， the clustering accuracy of SGE is 18.7% higher than that of LRPP_GRR. These results indicate that the proposed SGE algorithm can effectively reduce the dimensionality of the data.

Key words：feature extraction; local structure; rank constraint; least squares regression

0 引言

由于信息技術和硬件設備的快速發(fā)展，人們獲取的數(shù)據(jù)大多數(shù)都是高維數(shù)據(jù)。在計算機視覺、圖像處理、數(shù)據(jù)挖掘和機器學習等眾多應用領域，處理這樣的高維數(shù)據(jù)是一個挑戰(zhàn)性的問題。事實上，高維數(shù)據(jù)的特征一般包括一些噪聲和冗余特征。這些噪聲和冗余特征不僅會影響算法的性能，還極大地增加了算法的計算量。維數(shù)約簡，也稱降維（dimensionality reduction，DR），通過有效地減少高維數(shù)據(jù)的特征數(shù)，將高維數(shù)據(jù)變成低維數(shù)據(jù)，是緩解這一問題的有效工具^［1］。因此，它受到越來越多的研究人員關注。在大多數(shù)情況下，通過降維方法從原始特征空間中選擇或提取一小部分特征得到低維數(shù)據(jù)，達到降維目的。顯然，有效的降維方法獲得的特征既可以保留有價值的信息，又可以丟棄噪聲和冗余信息^［2］。

根據(jù)獲取數(shù)據(jù)特征的方式不同，降維方法可以分成特征選擇和特征提取。特征選擇是從原高維特征集中選擇一小部分特征子集；特征提取是從原高維特征集中生成新的一小部分特征子集。與前者相比，特征提取的優(yōu)勢在于能夠得到更有判別力的特征^{［3，4］}。根據(jù)是否使用數(shù)據(jù)的類信息，特征提取方法可以分成監(jiān)督^［5］、半監(jiān)督^［6］和無監(jiān)督^{［7，8］}三類方法。由于在實際應用中獲取類標號費時費力，但獲取大量的無標號數(shù)據(jù)非常容易，所以無監(jiān)督降維方法比另外兩類有更廣泛的應用。無監(jiān)督降維方法需要構建一個無向圖來揭示原高維空間中樣本之間的內(nèi)在幾何結(jié)構，借助于內(nèi)在的數(shù)據(jù)結(jié)構尋找投影方向。顯然，構建一個好的圖能很好地揭示數(shù)據(jù)之間的內(nèi)在幾何關系，從而可以獲取具有判別力的投影。三種假設通常用于無監(jiān)督降維方法構圖中，它們分別是基于距離假設、基于稀疏假設和基于低秩假設。

基于距離假設方法認為在投影空間里有更小距離的樣本屬于同一個聚類。這類方法中代表的算法有局部保持投影（LPP）^［9］、局部線性嵌入（LLE）^［10］、近鄰保持嵌入（NPE）^［11］、魯棒非負矩陣分解^［12］、魯棒潛在非負矩陣分解^［13］和魯棒結(jié)構正則化非負矩陣分解^［14］等。LLE為每個樣本找到k個最近鄰居，然后計算這k個最近近鄰的線性表示系數(shù)，通過獲取的樣本之間的重構關系來尋找投影方向；其他方法通過構建k近鄰圖來表達數(shù)據(jù)之間內(nèi)在結(jié)構學習投影方向。基于稀疏假設方法通過L₁范數(shù)稀疏性約束為每個樣本找到自適應的、靈活的選擇少量樣本的線性表示。稀疏保持投影（SPP）^［15］和低秩稀疏保持嵌入^［16］是這類構圖的代表算法?；诘椭燃僭O的方法使用核范數(shù)獲取數(shù)據(jù)之間親和關系，并使用學到的親和關系構建投影矩陣。與前兩種假設相比，這類構圖方法是在低秩表征子空間分割方法^［17］的基礎上拓展得到，因而研究成果較新。低秩保持投影^［18］、低秩保持嵌入^［19］、低秩嵌入^［20］、低秩自適應圖嵌入^［21］、魯棒低秩表征^［22］與低秩局部保持投影^［23］等方法借助于求解系數(shù)矩陣的核范數(shù)，得到低秩表征并被用于學習投影方向。

上述這些方法雖然在不同程度上提升了經(jīng)典降維算法的性能，但它們?nèi)匀幻媾R如下兩個問題。一是它們沒有同時保持數(shù)據(jù)的局部和全局結(jié)構。基于距離假設的方法使用K近鄰圖來刻畫數(shù)據(jù)的局部結(jié)構，忽略了全局結(jié)構，或者使用最大方差建模全局結(jié)構，忽略了局部結(jié)構。由于稀疏的特性，基于稀疏假設的方法只能找到與目標樣本最近樣本來線性表達，因此這類方法事實上并不能很好地保持數(shù)據(jù)的內(nèi)在結(jié)構?；诘椭燃僭O的方法使用核范數(shù)替代矩陣的最低秩解，以此保持數(shù)據(jù)的全局結(jié)構。然而，核范數(shù)只是求解矩陣的低秩解一個替代，并不能很好地揭示數(shù)據(jù)的全局結(jié)構^{［24，25］}。二是上述方法構建的圖脫離數(shù)據(jù)的聚類數(shù)，沒有與聚類一致的連通分量，因而不利于后續(xù)的聚類工作。

為了更具體、更清晰地界定問題和闡述動機，以醫(yī)院采集的乳腺癌數(shù)據(jù)集BreaKHis為例，該數(shù)據(jù)集有2 500個3 072維CT圖像組成，包括陰性和陽性兩類。圖1顯示四個代表性方法將BreaKHis數(shù)據(jù)集投影到二維平面的結(jié)果。從圖1可以看到，主成分分析方法（PCA）^［7］只關注全局結(jié)構，忽略了局部結(jié)構，因此，它在投影BreaKHis數(shù)據(jù)集時，將兩類圖像投影到一起，這樣后續(xù)分類或聚類工作很難能將它們分開，因此得到的聚類精度較低；低秩自適應圖嵌入方法（LRAGE）^［21］使用核范數(shù)替代矩陣的最低秩解，以此保持數(shù)據(jù)的全局結(jié)構，但它不能很好地揭示數(shù)據(jù)的全局結(jié)構，在它的投影中，兩類中的很多樣本重疊在一起；圖優(yōu)化的無監(jiān)督投影（GOSUP）^［4］考慮了數(shù)據(jù)的局部結(jié)構和投影矩陣的稀疏性，但忽略了全局結(jié)構，因而將兩類中很多圖像投影在一起，很難分開，而且這些方法構圖時沒有考慮數(shù)據(jù)的聚類數(shù)；文中提出的結(jié)構化圖嵌入方法（SGE）兼顧全局和局部結(jié)構，又在構圖時使用了數(shù)據(jù)的聚類數(shù)，因此將BreaKHis數(shù)據(jù)集投影到二維平面時，如圖1（d）所示，兩類樣本被很好地分開。

為了解決上述兩個問題，提出面向無監(jiān)督特征提取的結(jié)構化圖嵌入方法。SGE通過使用表征的K近鄰和最小二乘回歸同時捕捉數(shù)據(jù)的局部與全局相關結(jié)構，并對表征圖的拉普拉斯矩陣施加秩約束，以強制學習的圖具有精確的c個連通分量，從而找到到具有判別力的投影方向。具體地說，所提出結(jié)構化圖嵌入的貢獻如下：

a）SGE構建一個K近鄰圖建模數(shù)據(jù)的流形結(jié)構，這使得該模型能夠選擇少數(shù)最近鄰樣本進行表示；另外，使用最小二乘回歸約束揭示全局相關結(jié)構，因此，所提方法可以同時學習一個能保持數(shù)據(jù)的局部與全局相關結(jié)構的圖。

b）通過對表征圖的拉普拉斯矩陣施加秩約束，SGE強制學習的圖具有精確的c個連通分量，因而所構建的表征圖和聚類有效結(jié)合，從而有可能獲得用于聚類的全局最優(yōu)圖。

c）通過對表征施加非負約束，SGE學到的表征可以更加準確地描述樣本之間的相似性，也使得學到的表征具有更清晰的物理意義，所以新方法有潛力學到更有判別力的投影。

1 基礎理論

1.1 基于距離假設的投影方法

Yu等人^［26］提出一個靈活鄰域的無監(jiān)督降維算法（USFNO）。該方法通過使用自適應鄰域?qū)W習過程來構建相似圖，以保持高維數(shù)據(jù)的流形結(jié)構，并且利用靈活的鄰域來學習高維數(shù)據(jù)的流形結(jié)構的投影和潛在表示，以消除噪聲的影響；通過將自適應概率鄰域?qū)W習和流形殘差項集成到統(tǒng)一的目標函數(shù)中，USFNO聯(lián)合學習自適應相似圖和潛在投影。這個方法的目標函數(shù)被定義如下：

minA，F(xiàn)，s_ij12∑ni=1 ∑nj=1‖f_i－f_j‖22s_ij+α∑ni=1 ∑nj=1s²_ij+β‖X^TA－F‖22

s.t. A^TA=I，0≤s_ij≤1，s^T_i1=1（1）

這個算法需要迭代求解三個變量：投影矩陣A、潛在表征F和相似度矩陣S，因此只能得到局部最優(yōu)解。Qu等人^［27］使用動態(tài)圖正則化保持數(shù)據(jù)之間的局部固有結(jié)構，提出動態(tài)圖正則化的魯棒判別投影，它集成判別分析、重構數(shù)據(jù)和流形學習的統(tǒng)一框架來學習可靠的投影。

1.2 基于稀疏假設的投影方法

Wan等人^［13］提出了一種新的模型魯棒潛在非負矩陣分解與稀疏重構（RLNMF-SR）來執(zhí)行降維工作。RLNMF-SR利用稀疏節(jié)點自動重建基于全局的親和圖，而無須手動定義圖結(jié)構，這保證了模型獲取數(shù)據(jù)的基本分布。一方面，通過用低秩結(jié)構分解主成分，不僅可以去除冗余特征并降低計算成本，還可以獲得判別性和可解釋性的低秩表征；另一方面，應用L_2，1范數(shù)進行基于部分的非負分解獲得數(shù)據(jù)的局部屬性信息。它的目標函數(shù)如下：

minU≥0，V≥0，Z≥0‖XZ－UV^T‖_2，1+α（‖Z‖_*+‖L‖_*）+βTr（V^TL_SV）+‖E‖₁

s.t. X=LXZ+E（2）

1.3 基于低秩假設的投影方法

Zhang等人^［19］通過利用數(shù)據(jù)的自表達屬性提取數(shù)據(jù)的全局結(jié)構，從而提出低秩保持嵌入（LRPE）。LRPE在稀疏矩陣上施加低秩約束，將其強制為塊對角形式，使得有可能來自同一聚類具有相似內(nèi)在結(jié)構的樣本由相似的基集來描述。LRPE首先優(yōu)化下面的方程得到稀疏矩陣Z：

minZ‖Z‖_*+λ‖E‖_2，1

s.t. ‖X－XZ－E‖²_F≤ε，e^Tz_i=1（3）

在得到系數(shù)矩陣Z后，LRPE定義如下的目標函數(shù)：

minATr（A^TX（I－Z）（I－Z）^TX^TA）

s.t. a^T_iXX^Ta_i=1（4）

Lu等人^［21］提出了一種新的無監(jiān)督特征提取方法，稱為低秩自適應圖嵌入（LRAGE），該方法可以在重構誤差最小化的基礎上同時執(zhí)行子空間學習和自適應鄰域圖嵌入。

1.4 現(xiàn)有方法與SGE方法比較

為了清楚展示現(xiàn)有代表性方法和SGE方法的優(yōu)劣，將各個方法的特點概括如表1所示。

2 結(jié)構化圖嵌入

上述這些無監(jiān)督方法雖然降低數(shù)據(jù)維數(shù)，為后續(xù)的分類或者聚類工作提供了便利，但它們在尋找投影方向時只關注全局結(jié)構或局部結(jié)構，因而難以找到一個更有判別力的投影，難以有效提升分類或聚類的性能。為了解決這個問題，本文提出一個新的基于無監(jiān)督特征提取的結(jié)構化圖嵌入方法同時捕捉全局和局部結(jié)構尋找更有判別力的投影方向，新方法由求解親和矩陣和投影矩陣兩步組成。

2.1 結(jié)構感知表征模型

最近研究表明^{［24，25］}，當最小二乘回歸與數(shù)據(jù)自表達特性相結(jié)合時，能夠有效地揭示數(shù)據(jù)的全局相關結(jié)構，可以將具有相關結(jié)構的數(shù)據(jù)分組到同一個聚類中。顯然，這種尊重全局相關結(jié)構的方法自然能夠得到一個相對精確的表征。另一個方面，最小二乘回歸技術只捕捉了數(shù)據(jù)的全局相關結(jié)構，忽略了數(shù)據(jù)的局部結(jié)構。因此需要引入一個簡單距離約束和非負約束到自表達模型中，就可以在保持數(shù)據(jù)全局結(jié)構的同時捕捉數(shù)據(jù)的局部結(jié)構。這個新模型被定義如下：

minZ∑ni， j=1‖x_i－x_j‖22z_ij+λ₁2‖Z‖2F

s.t. X=XZ，diag（Z）=0，Z≥0，1^Tz_i=1（5）

其中：X∈?^m×n是給定數(shù)據(jù)矩陣；m是樣本的維數(shù)；n是樣本數(shù)；Z∈?^n×n是需要學習的表征，它的任一個元素Z_ij描述兩個樣本x_i與x_j之間的重構關系，Z≥0表示它的每一個元素都是非負的；λ₁是非負的懲罰參數(shù)。通過引入兩個距離約束，式（5）有如下優(yōu)秀特性：

a）由于Z為非負矩陣，第一項∑ni， j=1‖x_i－x_j‖22z_ij可以看做是加權稀疏正則化，這使得該模型能夠自適應地選擇少數(shù)最近鄰樣本進行表示，因此引入這個距離約束既可以捕捉數(shù)據(jù)的局部結(jié)構，又可以保持表征的稀疏性。

b）第二項使用最小二乘回歸技術保持數(shù)據(jù)的全局相關結(jié)構，有助于學習到表征能有效找到結(jié)構相關的樣本。結(jié)合第一項，式（5）同時利用數(shù)據(jù)的全局和局部信息來構建圖，這有助于新方法學習一個捕捉數(shù)據(jù)內(nèi)在結(jié)構的最優(yōu)圖。

c）表征Z的非負性使得模型揭示數(shù)據(jù)內(nèi)在幾何關系時有更清楚的物理意義，一方面避免了樣本之間有負數(shù)的權重，使得構建的圖能有效地揭示樣本之間的相似度，另一方面保證構建的圖是一個非負的，這讓新方法有潛力學到更有判別力的投影。

d）通過施加約束1^Tz_i= 1，既避免表征Z的任一行元素的值為0，又讓它自然地保持了數(shù)據(jù)的判別信息。在無監(jiān)督場景中，這種判別信息有助于在從學習到投影的過程中，將同一聚類樣本映射到同一組中。具體地說，對于任一個來自第j聚類的第i個樣本x^j_i，可以被表達為

x^j_i=0·x¹₁+…+z_i，i－2·x^j_i－2+z_i，i－1·x^j_i－1+

z_i，i+1·x^j_i+1+z_i，i+2·x^j_i+2+…+0·x^c_n（6）

其中： j=1， …，c表示聚類標號；表征z_i=［0， …， z_i，i-2， z_i，i-1，0， z_i，i+1， z_i，i+2，…，0］是稀疏的，這表明它能將第j個聚類樣本的權重賦非零值，不同聚類中樣本的權重賦零值，因而自然地包含判別信息。

在眾多真實應用場景中，獲得的數(shù)據(jù)通常包含噪聲。為了解決噪聲干擾問題，引入一個稀疏的殘差項，損失函數(shù)被修改為

minZ，E ∑ni， j=1‖x_i－x_j‖22z_ij+λ₁2‖Z‖2F+λ₂‖E‖₁

s.t. X=XZ+E，diag（Z）=0，Z≥0，1^Tz_i=1（7）

其中：E表示殘差；λ₂是一個非負的懲罰參數(shù)。

盡管式（7）構建的圖同時保持數(shù)據(jù)的全局和局部結(jié)構，但在某種程度上對噪聲不敏感，這種圖割離了與聚類的聯(lián)系，即對于具有c個聚類的數(shù)據(jù)，式（7）不能確保所獲得的圖有精確的c個連通分量，因此不是最優(yōu)圖。研究表明^{［29，30］}，構建有c個連通分量的圖有助于揭示聚類結(jié)構，從而學習到一個最優(yōu)的圖。為此，引入定理1。

定理1^［31］ 設Z為非負親和矩陣，度矩陣D為對角矩陣，其對角元素的值為Z相應的行或者列的所有元素和，拉普拉斯矩陣L_Z被定義為L_Z=D-（Z+Z^T）/2，則L_Z的特征值為0的個數(shù)與親和矩陣Z的連通分量數(shù)相等。

定理1表明如果rank（L_Z）=n-c， 則構建的圖有c個連通分量，從而得到一個最優(yōu)的圖。增加約束rank（L_Z）=n-c到式（7）中，得到表征Z包括清晰的聚類結(jié)構。因此，新的結(jié)構感知表征定義如下：

minZ，E ∑ni， j=1‖x_i－x_j‖22z_ij+λ₁2‖Z‖2F+λ₂‖E‖₁

s.t. X=XZ+E，diag（Z）=0，Z≥0

1^Tz_i=1，rank（L_Z）=n－c（8）

2.2 表征模型優(yōu)化

由于約束rank（L_Z）=n-c涉及到度矩陣和親和矩陣，式（8）不宜求解。既然L_Z是半正定，那么它的特征值為非負，式（8）可以改寫為

minZ，E∑ni， j=1‖x_i－x_j‖22z_ij+λ₁2‖Z‖2F+λ₂‖E‖₁+2λ₃∑ci=1δ_i（L_Z）

s.t. X=XZ+E，diag（Z）=0，Z≥0，1^Tz_i=1（9）

其中：δ_i（L_Z）代表L_Z第i個最小特征值，且δ_i（L_Z）≥0；λ₃是一個非負的懲罰參數(shù)，當它足夠大時，強迫式（9）的第四項為0，L_Z的c個最小特征值的和為0，因此，秩約束rank（L_Z）=n-c被滿足^{［29，32］}。根據(jù)Fan^［33］提出的定理，有如下等式：

∑ci=1δ_i（L_Z）=minF^TF=ITr（F^TL_ZF）（10）

其中：F∈?^n×c是聚類指示器矩陣。式（9）等價于以下優(yōu)化問題：

minZ，E，F(xiàn)∑ni， j=1‖x_i－x_j‖22z_ij+λ₁2‖Z‖2F+λ₂‖E‖₁+2λ₃Tr（F^TL_ZF）

s.t. X=XZ+E，diag（Z）=0，Z≥0，1^Tz_i=1，F(xiàn)^TF=I（11）

其中：n與c分別是樣本數(shù)和聚類數(shù)；Tr（·）表示矩陣的跡；I代表單位陣。

式（11）包含三個變量，是一個非凸函數(shù)。最近提出很多方法解上述優(yōu)化問題，由于LADM^［34］方法簡單有效，本文使用它來解式（11）。根據(jù)LADM，引入兩個變量S和Q替代式（11）中的Z，得到如下模型：

minZ，S，Q，E，F(xiàn) ∑ni， j=1‖x_i－x_j‖22S_ij+λ₁2‖Q‖2F+λ₂‖E‖₁+2λ₃Tr（F^TL_ZF）

s.t. X=XZ+E，Z=S，Z=Q，F(xiàn)^TF=I，

diag（S）=0，S≥0，1^Ts_i=1（12）

式（12）變換為以下的增廣拉格朗日乘子函數(shù)：

L（Z，S，Q，F(xiàn)，E）=∑ni， j=1‖x_i－x_j‖22S_ij+λ₁2‖Q‖2F+λ₂‖E‖₁+

2λ₃Tr（F^TL_SF）+〈P₁，X－XZ－E〉+〈P₂，Z－S〉+〈P₃，

Z－Q〉+μ2（‖X－XZ－E‖2F+‖Z－S‖2F+‖Z－Q‖2F）（13）

其中：P₁、P₂和P₃是拉格朗日乘子； μ是一個非負的懲罰參數(shù)。進一步化簡式（13），得到下面的式子：

L（Z，S，Q，F(xiàn)，E）=∑ni， j=1‖x_i－x_j‖22S_ij+λ₁2‖Q‖2F+

λ₂‖E‖_2，1+2λ₃Tr（F^TL_SF）+

μ2（‖X－XZ－E+P₁μ‖2F+‖Z－S+P₂μ‖2_F+‖Z－Q+P₃μ‖2F）（14）

通過在其他變量固定的情況下交替求解式（14）的每個變量，可以得到五個變量Z、S、Q、E和F的解，具體求解步驟如下：

a）求解Z的更新規(guī)則。當固定S、Q、E和F時，最小化下面的式子可得到Z的更新規(guī)則：

L（Z）=‖X－XZ－E+P₁μ‖2F+‖Z－S+P₂μ‖2F+

‖Z－Q+P₃μ‖2F（15）

通過求函數(shù)L（Z）關于Z的偏導數(shù)，得到

?L?Z=μ（X^TXZ－X^TJ₁+Z－J₂+Z－J₃）（16）

其中：J₁=X-E+P₁/μ，J₂=S-P₂/μ和J₃=Q-P₃/μ。因此，通過設置?L/?Z=0，Z的解為

Z=（X^TX+2I）^－1（X^TJ₁+J₂+J₃）（17）

b）求解S的更新規(guī)則。當固定Z、Q、E和F時，最小化下面的式子可得到S的更新規(guī)則：

minS∑ni， j=1‖x_i－x_j‖22S_ij+2λ₃Tr（F^TL_SF）+μ2‖Z－S+P₂μ‖2F

s.t. S≥0，1^Ts_i=1（18）

進一步化簡式（18），得到

∑ni， j=1‖x_i－x_j‖22S_ij+λ₃∑ni， j=1‖f_i－f_j‖22S_ij+μ2‖Z－S+P₂μ‖2F=

∑ni， j=1（‖x_i－x_j‖22+λ₃‖f_i－f_j‖22）S_ij+μ2‖Z－S+P₂μ‖2F=

∑ni， j=1H_ijS_ij+μ2‖S－V‖2F=Tr（H^TS）+μ2‖S－V‖2F（19）

其中：H_ij=‖x_i－x_j‖²₂+λ₃‖f_i－f_j‖²₂和V=Z+P₂/μ。設h_i、s_i和v_i分別為矩陣H、S、V的行向量，式（18）等價于解下列問題：

minsi≥0，1Tsi=1‖s_i－（v_i－h(huán)_i/μ）‖22（20）

式（20）有解析解，使用文獻［29］可以快速解S的最優(yōu)值。

c）求解F的更新規(guī)則。當固定Z、Q、E和S時，最小化下面的式子可得到F的更新規(guī)則：

minFTr（F^TL_SF）

s.t. F^TF=I，F(xiàn)∈?^n×c（21）

其中：L_S=D-S是一個拉普拉斯矩陣；D是一個對角矩陣，它的對角元素值為D_ii=∑_jS_ij。通過特征分解可以得到式（21）的解。顯然，F(xiàn)是由L_S的c個最小特征值對應的特征向量組成的矩陣。

d）求解Q的更新規(guī)則。當固定Z、E、S和F時，最小化下面的式子可得到Q的更新規(guī)則：

minQλ₁2‖Q‖2F+μ2‖Z－Q+P₃μ‖2F（22）

通過簡單解式（22），Q的最優(yōu)值為

Q=μZ+P₃μ+λ₁（23）

e）求解E的更新規(guī)則。當固定Z、Q、S和F時，最小化下面的式子可得到S的更新規(guī)則：

minEλ₂‖E‖₁+μ2‖X－XZ－E+P₁μ‖2F（24）

E的解析解為

E=Φ_λ2/μ（X－XZ+P₁/μ）（25）

其中：Ф是shrinkage算子^［35］。

f）更新參數(shù)P₁、P₂、P₃、μ。拉格朗日參數(shù)P₁、P₂、P₃和懲罰系數(shù)μ分別使用如下的更新規(guī)則：

P₁=P₁+μ（X－XZ－E）（26）

P₂=P₂+μ（Z－S）（27）

P₃=P₃+μ（Z－Q）（28）

μ=min（ρμ，μ_max）（29）

其中：ρ和μ_max是固定的常數(shù)。

根據(jù)上述分析，求解親和矩陣Z可以概括在算法1中。

算法1 求解親和矩陣Z

輸入：數(shù)據(jù)矩陣X，正則化參數(shù)λ₁、λ₂、λ₃，聚類數(shù)c。

輸出：Z、S、Q、F和E。

初始化：近鄰數(shù)k，P₁=P₂= P₃=0， E=0， μ=0.01，ρ=1.2， μ_max=10⁸。

while （不收斂）

1.使用式（17）更新Z；

2.解式（20）更新S；

3.解式（21）更新F；

4.使用式（23）更新Q；

5.使用式（25）更新E；

6.使用式（26）～（29）分別更新P₁、P₂、P₃、μ；

end while

2.3 結(jié)構化圖嵌入算法（SGE）

通過算法1得到的數(shù)據(jù)之間最優(yōu)的重構權重Z，保持數(shù)據(jù)全局結(jié)構的同時捕捉數(shù)據(jù)的局部結(jié)構，而且非負約束使得它有更清楚的物理意義。顯然，在高維空間中的這些特性希望在數(shù)據(jù)映射到低維空間時，也自然保持這些特性。為此，本文定義如下目標函數(shù)尋找一個更有判別力的投影來保持這些特性：

mina∑ni=1‖a^Tx_i－a^TXz_i‖22（30）

通過簡化式（30），得到

∑ni=1‖a^Tx_i－a^TXz_i‖22=a^T（∑ni=1（x_i－Xz_i）（x_i－Xz_i）^T）a=

a^TX（∑ni=1（e_i－z_i）（e_i－z_i）^T）X^Ta=

a^TX（∑ni=1（e_ie^T_i－z_ie^T_i－e_iz^T_i－z_iz^T_i））X^Ta=

a^TX（I－Z－Z^T+ZZ^T）X^Ta（31）

根據(jù)式（31），最小化式（30）等價于最大化下面的式子：

maxa a^TXS_ZX^Ta（32）

其中：S_Z=Z+Z^T-ZZ^T。為了避免最后的解退化，SGE增加約束a^TX S_t X^Ta=1，S_t=I-11^T/n。因此，聯(lián)合這個約束，求解式（32）可以得到最優(yōu)的投影矩陣。這個投影矩陣是由下列廣義特征問題的d個最大特征值對應的特征向量組成：

XS_ZX^Ta=λXS_tX^Ta（33）

基于上面的討論，SGE被概括在算法2中。

算法2 結(jié)構化圖嵌入算法（SGE）

輸入：數(shù)據(jù)矩陣X。

輸出：投影矩陣A。

1.使用算法1計算親和矩陣Z；

2.使用式（33）計算投影向量，d個最大特征值對應的特征向量組成最優(yōu)投影矩陣；

2.4 收斂性分析

SGE在求解親和矩陣時涉及到5個變量Z、S、Q、E和F，如式（12）所示，使用LADM^［32］可以得到一個局部最優(yōu)解。顯然，式（12）是一個非凸函數(shù)。LADM已經(jīng)給出兩個變量的收斂證明，而SGE包含5個變量Z、S、Q、E和F。因此，在計算某一個變量時，固定其他變量，這樣式（12）成為一個凸函數(shù)?？梢宰C明SGE的解是不遞增的，從而保證所提方法的收斂性^［36］。為此，給出如下的定理。

定理2 SGE的目標函數(shù)式（12）在更新規(guī)則1～6步中得到的解是不遞增的。

證明 根據(jù)文獻［34，36］，SGE的目標函數(shù)式（12）轉(zhuǎn)換為如式（13）的增廣拉格朗日函數(shù)。

根據(jù)式（13），所有變量的迭代規(guī)則如下：

Z^t+1=arg minZ L（Z^t，S^t，Q^t，F(xiàn)^t，E^t）（34）

S^t+1=arg minS L（Z^t，S^t，Q^t，F(xiàn)^t，E^t）（35）

Q^t+1=arg minQ L（Z^t，S^t，Q^t，F(xiàn)^t，E^t）（36）

F^t+1=arg minF L（Z^t，S^t，Q^t，F(xiàn)^t，E^t）（37）

E^t+1=arg minE L（Z^t，S^t，Q^t，F(xiàn)^t，E^t）（38）

P^t+1₁=P^t₁+μ（X-XZ^t-E）（39）

P^t+1₂=P^t₂+μ（Z^t-S^t）（40）

P^t+1₃=P^t₃+μ（Z^t-Q^t）（41）

從算法1看到，SGE優(yōu)化式（13）與典型方法LADM的優(yōu)化問題非常相似。當其他變量固定時，Z和E的優(yōu)化問題等價于LADM的Z和E的優(yōu)化問題，根據(jù)LADM方法，Z和E的優(yōu)化問題是收斂的。設Ф^t= （Z^t， S^t， Q^t， E^t， F^t， P^t₁， P^t₂， P^t₃）是SGE的第t次迭代的解，則Z和E的優(yōu)化問題可以表示為

Φ（Z^t+1，E^t+1）≤Φ（Z^t，E^t）（42）

當Z和E固定時，根據(jù)文獻［34］，可以得到如下不等式：

Φ （S^t+1，Q^t+1，F(xiàn)^t+1，P^t+1₁，P^t+1₂，P^t+1₃）≤

Φ （S^t，Q^t，F(xiàn)^t，P^t₁，P^t₂，P^t₃）（43）

聯(lián)合式（42）和（43）得到

Φ （Z^t+1，S^t+1，Q^t+1，F(xiàn)^t+1，E^t+1，P^t+1₁，P^t+1₂，P^t+1₃）≤

Φ （Z^t，S^t，Q^t，F(xiàn)^t，E^t，P^t₁，P^t₂，P^t₃）（44）

完成定理2的證明，即算法1是收斂的。

SGE方法使用ORL和UMIST數(shù)據(jù)集來驗證算法的收斂性。目標函數(shù)值定義為

V=∑ni， j=1‖x_i－x_j‖22S_ij+λ₁2‖Q‖2F+λ₂‖E‖₁+

2λ₃Tr（F^TL_ZF）‖X‖²_F（45）

實驗結(jié)果如圖2所示，其中x軸表示迭代次數(shù)，y軸代表目標函數(shù)值。通過圖2可以發(fā)現(xiàn)，SGE很快就可以收斂到一個局部最優(yōu)值。相似的現(xiàn)象也可以在其他數(shù)據(jù)集上觀察到，因而省略。

2.5 復雜度分析

SGE方法是由計算親和矩陣Z和投影矩陣A兩步組成，涉及到矩陣逆操作、奇異值閾值（SVT）和特征分解。在算法1中，時間開銷大的計算分別是計算Z和E。（X^TX+2I）^-1操作和奇異值閾值（SVT）的時間復雜度均為O（n³），其中n是樣本數(shù)。因此，算法1的時間復雜度為O（Tn³），其中T是迭代次數(shù)。算法2主要是通過特征分解計算投影矩陣，其時間復雜度為O（n³）。因此，SGE方法的時間復雜度為O（Tn³）。

3 實驗結(jié)果

3.1 實驗設置

本文使用基線和SGE算法在實例應用中來驗證它們的性能。 這些實例應用是使用算法將不同應用場景中采集到的高維數(shù)據(jù)投影到低維空間中。在低維空間中，如果算法將不同類樣本投影得更遠、相同類樣本投影得更近，則它的性能自然就高，否則它的性能較差。這些實例應用的數(shù)據(jù)來自不同的應用領域，包括人臉圖像數(shù)據(jù)集、醫(yī)學圖像數(shù)據(jù)集和對象圖像數(shù)據(jù)集，共有8個數(shù)據(jù)集。其中PIE、UMIST、ORL、Grimace、Faces94是人臉圖像數(shù)據(jù)集；Palm和MFD是對象圖像數(shù)據(jù)集；BreaKHis是乳腺癌圖像數(shù)據(jù)集。這些數(shù)據(jù)集的特征如表2所示。

本文使用7個流行的具有代表性的無監(jiān)督特征提取方法作為基線來驗證所提算法的效能。7個方法中PCA^［7］ 、LPP^［9］ 和SPP^［15］是三個經(jīng)典降維算法；LRAGE^［21］、LRPP_GRR^［28］、RLNMF-SR^［13］和GOSUP^［4］是最新提出的降維算法。為了全面比較基線方法和SGE的有效性，本文使用聚類精度（ACC）^{［4，13，21，28］}和歸一化互信息（NMI）^{［4，13，21，28］}來度量它們的聚類性能。ACC和NMI取值在0～1，它們的值越大，意味著該算法的性能越好。事實上，ACC和NMI也是這些無監(jiān)督特征提取方法中常用的評估指標。為了公平對比，每個算法都運行20次，報告為最終的聚類結(jié)果的均值和標準差。

3.2 可視化實驗

為了直觀看到各個算法的投影結(jié)果，本文將所有算法在BreaKHis數(shù)據(jù)集上的實驗結(jié)果用二維平面展示，即將該數(shù)據(jù)集投影到二維平面上，如圖3所示，小圓代表一類，小正方形代表另一類。從圖3（h）觀察到，SGE似乎可以將兩類樣本很好地投影開來。小圓與小正方形很少有重疊，也就是說，SGE將不同類之間的樣本盡可能分開，而相同類的樣本盡可能投影到一起。這表明兼顧局部和全局結(jié)構并考慮數(shù)據(jù)聚類結(jié)果的SGE方法能找到一個更有判別力的投影，因此能得到讓人滿意的聚類結(jié)果。與SGE相比，其他方法的投影結(jié)果顯示出兩類樣本都有不同程度的重疊，因此，不能給出令人滿意的結(jié)果。例如，PCA幾乎將兩類樣本投影到一起，造成這種結(jié)果的原因是它只是關注方差變化最大的方向，而忽略了數(shù)據(jù)的內(nèi)在幾何結(jié)構。RLNMF-SR方法不僅將兩類部分樣本投影到一起，還分散各類內(nèi)的樣本，不利于聚類。顯然，它不能給出好的結(jié)果。雖然GOSUP方法將類內(nèi)的樣本投影得更近，但兩類中有很多樣本重疊在一起。相似的結(jié)果也在LRPP_GRR、LRAGE和SPP等方法上觀察到。

3.3 實驗結(jié)果與分析

所有算法在8個數(shù)據(jù)集上的聚類結(jié)果如表3和4所示（加粗數(shù)字代表最好的結(jié)果）。從表3和4可以得到如下有趣的觀察：

a）本文算法SGE在8個數(shù)據(jù)集上總是得到最好的ACC 和NMI值，也就是說SGE在這些數(shù)據(jù)集上聚類結(jié)果要優(yōu)于其他方法的聚類結(jié)果。例如，在PIE數(shù)據(jù)集上，SGE的ACC值比排名第二的LRPP_GRR的ACC值高出大約18%；在BreaKHis數(shù)據(jù)集上，SGE的NMI值比排名第二的LPP的NMI值高出大約13%。這表明通過保持數(shù)據(jù)全局和局部結(jié)構，SGE找到的投影方向具有更強的判別力，它能將高維空間中的同一聚類的樣本投影得更近，并將高維空間中的不同聚類的樣本投影得更遠，從而得到較好的聚類結(jié)果。

b）雖然最新提出的RLNMF-SR和GOSUP比本文SGE要差，但與其他方法相比，它們可以得到相對較好的聚類性能。在PIE數(shù)據(jù)集上，這兩個算法的聚類結(jié)果要優(yōu)于剩余方法；相似的結(jié)果也可以在ORL數(shù)據(jù)集上觀察到，只是它們優(yōu)勢并不明顯。與上述兩個方法有相同之處的SPP也是通過保持重構權值的稀疏來尋找投影方向，但它的性能相對較差，這表明通過使用稀疏保持找到的投影方向并不是最優(yōu)的。

c）LRAGE性能相對較差，原因是該方法使用核范數(shù)近似求解親和矩陣的低秩并不能很好地保持數(shù)據(jù)的全局結(jié)構。相比之下，LPP可以得到較好的性能，如在BreaKHis數(shù)據(jù)集上，它的ACC值要高于除SGE外的其他算法，這表明在無監(jiān)督學習中數(shù)據(jù)的局部結(jié)構在聚類或者分類任務中扮演非常重要的作用。遺憾的是，在Faces94數(shù)據(jù)集上，LPP的性能很差，原因是它忽略了數(shù)據(jù)的全局結(jié)構。

d）不同的方法在不同的數(shù)據(jù)集上表現(xiàn)不同。如LPP在UMIST數(shù)據(jù)集上得到僅次于SGE的性能，在Faces94數(shù)據(jù)集上表現(xiàn)較差；SPP在Palm數(shù)據(jù)集上得到次優(yōu)的性能，在ORL數(shù)據(jù)集上表現(xiàn)較差；GOSUP方法在Faces94數(shù)據(jù)集上得到較好的性能，在MFD數(shù)據(jù)集上表現(xiàn)相對較差；RLNMF-SR方法在PIE數(shù)據(jù)集上得到次優(yōu)的性能；LRPP_GRR在BreaKHis數(shù)據(jù)集上得到次優(yōu)的性能，在Faces94數(shù)據(jù)集上表現(xiàn)較差。 總體上，RLNMF-SR方法在本文使用的數(shù)據(jù)集上得到了較好的性能，僅次于SGE；PCA表現(xiàn)較差。SGE在本文使用的數(shù)據(jù)集上得到了最好的性能，這證明了SGE的有效性。

4 結(jié)束語

本文提出一個新的面向無監(jiān)督特征提取的結(jié)構化圖嵌入方法（SGE），該方法構建表征的K近鄰圖來尊重數(shù)據(jù)的局部結(jié)構，使用最小二乘回歸建模全局結(jié)構，從而能同時捕捉數(shù)據(jù)的全局和局部結(jié)構。此外，SGE引入表征圖的拉普拉斯矩陣秩約束和非負約束，使構建的圖既可以很好地揭示數(shù)據(jù)的聚類結(jié)構，又使表征圖具有良好的可解釋性。因此，SGE能學習到更有判別力的投影。大量的實驗結(jié)果證實了所提方法的有效性。

參考文獻：

［1］Wang Quan， Wang Fei， Li Zhongheng， et al. Coordinate descent optimized trace difference model for joint clustering and feature extraction ［J］. Pattern Recognition， 2024， 146： 110062.

［2］Hu Wenjun， Zhang Ke， Wang Shitong， et al. Joint group and pairwise localities embedding for feature extraction ［J］. Information Sciences， 2024， 657： 119960.

［3］Ruan Weiyong， Sun Lei. Robust latent discriminative adaptive graph preserving learning for image feature extraction ［J］. Knowledge-Based Systems， 2023， 268： 110487.

［4］Wang Jingyu， Wang Lin， Nie Feiping， et al. Joint feature selection and extraction with sparse unsupervised projection ［J］. IEEE Trans on Neural Networks and Learning Systems， 2023， 34（6）： 3071-3081.

［5］Wen Jie， Fang Xiaozhao， Cui Jinrong， et al. Robust sparse linear discriminant analysis ［J］. IEEE Trans on Circuits and Systems for Video Technology， 2019， 29（2）： 390-403.

［6］Nie Feiping， Wang Zheng， Wang Rong， et al. Adaptive local embedding learning for semi-supervised dimensionality reduction ［J］. IEEE Trans on Knowledge and Data Engineering， 2021， 34（10）： 4609-4621.

［7］Seghouane A K， Shokouhi N， Koch I. Sparse principal component analysis with preserved sparsity pattern ［J］. IEEE Trans on Image Processing， 2019， 28（7）： 3274-3285.

［8］Nie Feiping， Wu Danyang， Wang Rong， et al. Truncated robust principle component analysis with a general optimization framework ［J］， IEEE Trans on Pattern Analysis and Machine Intelligence， 2021， 44（2）： 1081-1097.

［9］He Xiaofei， Niyogi P. Locality preserving projections ［C］// Proc of the 16th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2003： 153-160.

［10］Roweis， S T， Saul， L K. Nonlinear dimensionality reduction by locally linear embedding ［J］. Science， 2000， 290（5500）： 2323-2326.

［11］He Xiaofei， Cai Deng， Yan Shuicheng， et al. Neighborhood preserving embedding ［C］// Proc of IEEE International Conference on Computer Vision. Piscataway，NJ： IEEE Press， 2005： 1208-1213.

［12］Huang Qi， Yin Xuesong， Chen Songcan， et al. Robust nonnegative matrix factorization with structure regularization ［J］. Neurocompu-ting， 2020， 412： 72-90.

［13］Wan Minghua， Cai Mingxiu， Yang Zhangjing， et al. Robust latent nonnegative matrix factorization with automatic sparse reconstruction for unsupervised feature extraction ［J］. Information Sciences， 2023， 648： 119517.

［14］董文婷， 尹學松， 余節(jié)約， 等. 魯棒結(jié)構正則化非負矩陣分解 ［J］. 計算機應用研究， 2023， 40（3）： 794-799. （Dong Wenting， Yin Xuesong， Yu Jieyue， et al. Robust structure regularized nonnegative matrix factorization ［J］. Application Research of Computers， 2023， 40（3）： 794-799.）

［15］Qiao Lishan， Chen Songcan， Tan Xiaoyang. Sparsity preserving projections with applications to face recognition ［J］. Pattern Recognition， 2010， 43（1）： 331-341.

［16］Zhan Shanhua， Wu Jigang， Han Na， et al. Unsupervised feature extraction by low-rank and sparsity preserving embedding ［J］. Neural Networks， 2019， 109： 56-66.

［17］Liu Guangcan， Lin Zhouchen， Yan Shuicheng， et al. Robust recovery of subspace structures by low-rank representation ［J］. IEEE Trans on Pattern Analysis and Machine Intelligence， 2013， 35（1）： 171-184.

［18］Lu Yuwu， Lai Zhihui， Xu Yong， et al. Low-rank preserving projections ［J］. IEEE Trans on Cybernetics， 2016， 46（8）： 1900-1913.

［19］Zhang Yupei， Xiang Ming， Yang Bo. Low-rank preserving embedding ［J］. Pattern Recognition， 2017， 70： 112-125.

［20］Wong W K， Lai Zhihui， Wen Jiajun， et al. Low-rank embedding for robust image feature extraction ［J］. IEEE Trans on Image Processing， 2017， 26（6）： 2905-2917.

［21］Lu Jianglin， Wang Hailing， Zhou Jie， et al. Low-rank adaptive graph embedding for unsupervised feature extraction ［J］. Pattern Recognition， 2021， 113： 107758.

［22］Hui Kaifa， Shen Xiangjun， Abhadiornhen S E， et al. Robust low-rank representation via residual projection for image classification ［J］. Knowledge-Based Systems， 2022， 241： 108230.

［23］Yin Shuai， Sun Yanfeng， Gao Junbin， et al. Robust image representation via low rank locality preserving projection ［J］. ACM Trans on Knowledge Discovery from Data， 2021， 15（4）： 1-22.

［24］Kou Simin， Yin Xuesong， Wang Yigang， et al. Structure-aware subspace clustering ［J］. IEEE Trans on Knowledge and Data Engineering， 2023， 35（10）： 10569-10582.

［25］Lu Canyi， Min Hai， Zhao Zhongqiu， et al. Robust and efficient subspace segmentation via least squares regression ［C］// Proc of European Conference on Computer Vision. Berlin： Springer， 2012： 347-360.

［26］Yu Weizhong， Bian Jintang， Nie Feiping， et al. Unsupervised subspace learning with flexible neighboring ［J］. IEEE Trans on Neural Networks and Learning Systems， 2023， 34（4）： 2043-2056.

［27］Qu Hongchun， Li Lin， Li Zhaoni， et al. Robust discriminative projection with dynamic graph regularization for feature extraction and classification ［J］. Knowledge-Based Systems， 2022， 253： 109563.

［28］Wen Jie， Han Na， Fang Xiaozhao， et al. Low-rank preserving projection via graph regularized reconstruction ［J］. IEEE Trans on Cybernetics， 2018， 49（4）： 1279-1291.

［29］Nie Feiping， Zhu Wei， Li Xuelong. Structured graph optimization for unsupervised feature selection ［J］. IEEE Trans on Knowledge and Data Engineering， 2021， 33（3）： 1210-1222.

［30］Zhao Xiaowei， Nie Feiping， Yu Weizhong， et al. Fast neighborhood reconstruction with adaptive weights learning ［J］. Knowledge-Based Systems， 2023， 259： 110082.

［31］Von Luxburg. A tutorial on spectral clustering ［J］. Statistics and Computing， 2007， 17（4）： 395-416.

［32］Nie Feiping， Zhu Wei， Li Xuelong. Unsupervised feature selection with structured graph optimization ［C］// Proc of the 30th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press，2016： 1302-1308.

［33］Fan K. On a theorem of Weyl concerning eigenvalues of linear transformations ［J］. Proc of the National Academy of Sciences， 1949， 35（11）： 652-655.

［34］Yang Junfeng， Yuan Xiaoming. Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization ［J］. Mathematics of Computation， 2013， 82（281）： 301-329.

［35］Wen Jie， Fang Xiaozhao， Xu Yong， et al. Low-rank representation with adaptive graph regularization ［J］. Neural Networks， 2018， 108： 83-96.

［36］Boyd S， Parikh N， Chu E， et al. Distributed optimization and statistical learning via the alternating direction method of multipliers ［J］. Foundations and Trends in Machine Learning， 2011， 3（1）： 1-222.