曹傳杰 王靖 趙偉豪 周科藝 楊曉君

摘 要：降維是處理高維數(shù)據(jù)的一項關(guān)鍵技術(shù)，其中線性判別分析及其變體算法均為有效的監(jiān)督算法。然而大多數(shù)判別分析算法存在以下缺點：a）無法選擇更具判別性的特征；b）忽略原始空間中噪聲和冗余特征的干擾；c）更新鄰接圖的計算復(fù)雜度高。為了克服以上缺點，提出了基于子空間學(xué)習(xí)的快速自適應(yīng)局部比值和判別分析算法。首先，提出了統(tǒng)一比值和準(zhǔn)則及子空間學(xué)習(xí)的模型，以在子空間中探索數(shù)據(jù)的潛在結(jié)構(gòu)，選擇出更具判別信息的特征，避免受原始空間中噪聲的影響；其次，采用基于錨點的策略構(gòu)造鄰接圖來表征數(shù)據(jù)的局部結(jié)構(gòu)，加速鄰接圖學(xué)習(xí)；然后，引入香農(nóng)熵正則化，以避免平凡解；最后，在多個數(shù)據(jù)集上進(jìn)行了對比實驗，驗證了算法的有效性。

關(guān)鍵詞：降維； 線性判別分析； 子空間學(xué)習(xí)； 比值和

中圖分類號：TP391.4?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2024）01-017-0108-08

doi：10.19734/j.issn.1001-3695.2023.05.0194

Fast adaptive local ratio sum discriminant analysis based on subspace learning

Abstract：Dimensionality reduction is a key technique for processing high-dimensional data， and linear discriminant analysis and its variant algorithms are effective supervised algorithms. However， most discriminant analysis algorithms have the following disadvantages： a）It cannot select more discriminative features; b）It ignores the interference of noise and redundant features in the original space; c）The computational complexity of updating the adjacency graph is high. In order to overcome these shortcomings， this paper proposed a fast adaptive local ratio sum discriminant analysis algorithm based on subspace learning. Firstly， this paper proposed a model that unified the ratio sum criterion and subspace learning to explore the potential structure of the data in the subspace， select features with more discriminative information， and avoid being affected by noise in the original space. Secondly， it used an anchor-based strategies to construct an adjacency graph to represent the local structure of the data to accelerate the learning of the adjacency graph. Finally， it introduced Shannon entropy to avoid trivial solutions， and verified the effectiveness of the algorithm by comparison experiments on multiple data sets.

Key words：dimensionality reduction; linear discriminant analysis; subspace learning; ratio sum

0 引言

在如今傳感器技術(shù)快速發(fā)展的背景下，采集的數(shù)據(jù)維度也隨之快速增長，涌現(xiàn)出越來越多的高維數(shù)據(jù)［1］，然而維度的增加導(dǎo)致了計算復(fù)雜度劇烈增加，以及原始數(shù)據(jù)中存在大量冗余特征等問題［2］，阻礙了一些領(lǐng)域的發(fā)展，如視頻分析［3］、人群分析［4］、圖像分析［5］等。因此，設(shè)計一個用來提取數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，以尋求數(shù)據(jù)最優(yōu)表示的降維算法是極其緊迫的。

在過去的幾十年，大量學(xué)者提出了許多的特征提取方法。其中主成分分析（principal component analysis，PCA）［6］和線性判別分析（linear discriminant analysis，LDA）［7］分別是無監(jiān)督和有監(jiān)督領(lǐng)域最著名的特征提取算法。LDA通過尋找一個投影矩陣，將高維數(shù)據(jù)投影于低維空間中，以尋求使得類內(nèi)散度最小和類間散度最大的低維表示。LDA可歸納為求解跡比（trace ratio，TR）［8］問題，然而TR問題不能直接獲得全局最優(yōu)的封閉解［9］，通常需要轉(zhuǎn)換為跡差問題，通過廣義特征值求解得到近似解，這會影響后續(xù)分類的性能。此外，LDA還存在小樣本量、最大維度限制等缺點。因此，近年來，許多研究工作采用正交線性判別分析［10］、最大裕度準(zhǔn)則［11］來解決上述問題。

上述算法皆只適用于服從高斯分布的數(shù)據(jù)，而無法處理更為復(fù)雜分布的真實世界數(shù)據(jù)。為了解決這一問題，受到局部投影保持［12］的啟發(fā)，局部費舍判別分析（local Fisher discriminant analysis，LFDA）［13］通過引入樣本之間的相似度來構(gòu)造局部散度矩陣，以代替全局散度矩陣，能更好地提取數(shù)據(jù)的局部信息。此外，Cai等人［14］提出了一種局部感知判別分析（locality sensitive discriminant analysis，LSDA），該算法通過引入KNN思想，使樣本的感受野只在近鄰樣本內(nèi)，利用近鄰關(guān)系構(gòu)造類內(nèi)圖和類間圖，以使得每個局部區(qū)域最大化不同標(biāo)簽近鄰點的彼此距離，最小化相同標(biāo)簽的近鄰點彼此距離。有學(xué)者注意到，根據(jù)TR準(zhǔn)則來進(jìn)行特征提取，會傾向于選擇投影方向上總體方差較小或趨于零的方向，而這些不具有強烈判別性的特征對于分類任務(wù)是無意義的。為此，有學(xué)者提出了比值和（ratio sum，RS）［15］準(zhǔn)則來避免這個問題，該準(zhǔn)則會更傾向于選擇總體方差較大的組合。這種準(zhǔn)則已經(jīng)在許多文章中被證明是有效的，例如，貪心比值和（greedy ratio sum，GRS）［15］與比值和線性判別分析（ratio sum linear discriminant analysis，RSLDA）［16］。

此外，張家樂等人［8］注意到基于圖嵌入降維算法的缺點，即它們在原始空間中學(xué)習(xí)忽略了噪聲和冗余特征的干擾，且構(gòu)圖方式受到調(diào)參的影響，這使得構(gòu)圖不合理，導(dǎo)致性能下降。為此，張家樂等人提出了自適應(yīng)近鄰局部比值和線性判別分析算法（adaptive neighbor local ratio sum linear discriminant analysis，ANLRSLDA），通過采用非熱核自適應(yīng)構(gòu)圖策略構(gòu)建鄰接圖，能在一定程度上減少原始空間中噪聲和冗余特征帶來的影響。但該算法仍然是基于原始空間進(jìn)行構(gòu)圖，因此，無法避免原始空間中噪聲和冗余特征的影響。文獻(xiàn)［17］認(rèn)為數(shù)據(jù)的內(nèi)在幾何形狀隱藏在低維空間中，因此，每個樣本的鄰域應(yīng)在子空間中尋找，而不是在原始空間中。為此，大量研究者付出巨大努力。例如，自適應(yīng)局部線性判別分析（adaptive local linear discriminant analysis，ALLDA）［18］和動態(tài)最大熵圖（dynamic maximum entropy graph，DMEG）［19］等方法通過迭代算法，自適應(yīng)地學(xué)習(xí)子空間中數(shù)據(jù)的局部關(guān)系，以避免原始空間中噪聲的影響。但上述子空間學(xué)習(xí)算法是根據(jù)全部數(shù)據(jù)點之間的相似度或重構(gòu)關(guān)系來學(xué)習(xí)局部信息，導(dǎo)致更新鄰接圖的時間復(fù)雜度至少是樣本數(shù)量的平方，這意味著此類算法訓(xùn)練大規(guī)模的數(shù)據(jù)集是非常耗時的。為了更準(zhǔn)確、更具魯棒性、快速地學(xué)習(xí)局部流形結(jié)構(gòu)，本文提出了一種快速自適應(yīng)比值和局部判別分析（fast adaptive local ratio sum discriminant analysis，F(xiàn)ALRSDA）算法。該算法能很好地學(xué)習(xí)更具判別性的特征和數(shù)據(jù)潛在局部結(jié)構(gòu)，同時能快速地自適應(yīng)學(xué)習(xí)最優(yōu)的子空間鄰接圖。

本文的主要貢獻(xiàn)為：a）建立了一種快速、自適應(yīng)的比值和分析判別模型，統(tǒng)一了投影矩陣、內(nèi)在流形結(jié)構(gòu)和類內(nèi)劃分的學(xué)習(xí)，以學(xué)習(xí)更具判別性的特征和探索低維的潛在結(jié)構(gòu)，并提出了一種高效的迭代優(yōu)化算法來求解該模型;b）基于錨點［20］的策略加速構(gòu)造鄰接圖，降低了算法的時間復(fù)雜度;c）鄰接圖會自適應(yīng)學(xué)習(xí)，可消除原始空間的噪聲干擾，并且引入最大熵控制圖權(quán)值的均勻性，避免平凡解。同時，錨點的自適應(yīng)分配可隱式地將每個類劃分為不相交的簇，以探索數(shù)據(jù)的局部結(jié)構(gòu)，使算法適用于同類非高斯分布的數(shù)據(jù)。

1 相關(guān)工作

1.1 線性判別分析

設(shè)數(shù)據(jù)矩陣X=［x1，x2，…，xn］∈RApd×n，其中n為樣本數(shù)，xi∈RApd×1是單個樣本，具有d個特征維度。假設(shè)數(shù)據(jù)X已經(jīng)按標(biāo)簽大小排序。LDA的目標(biāo)是尋找一個最優(yōu)投影矩陣W=［w1，w2，…，wk］∈RApd×k，其中d>>k，k為降維的維數(shù)，通過Y=WTX∈RApk×n將數(shù)據(jù)映射到低維空間中，使得同類數(shù)據(jù)變近，而不同類數(shù)據(jù)更遠(yuǎn)。LDA具有許多變種［19］，LDA的目標(biāo)函數(shù)之一可以寫成以下TR問題：

其中：Sw為類內(nèi)散度矩陣;St為總體方差矩陣;c是樣本類數(shù);ni是第i類樣本個數(shù);n是樣本總數(shù)。最優(yōu)的投影矩陣W*可通過求解式（1）得到。

1.2 比值和線性判別分析

式（1）也可被寫為

然而LDA采用TR準(zhǔn)則會導(dǎo)致最優(yōu)投影矩陣傾向于選擇方差較小的投影方向，使得降維后的數(shù)據(jù)在個別投影方向上的方差很小，因此所選擇的子空間低維特征的判別性較低［16］。對于分類任務(wù)，沒有強烈判別性的特征對于分類任務(wù)的影響是極低的，但數(shù)據(jù)存儲卻需要更多空間。顯然，選擇方差較小的投影方向不利于分類問題。幸運的是，文獻(xiàn)［15］提出了新的RS準(zhǔn)則，并證明了RS準(zhǔn)則可以避免TR更傾向于選擇方差較小的投影方向的缺點。用RS準(zhǔn)則替換TR準(zhǔn)則，可得到模型：

下面給出一個簡單例子，來比較TR和RS準(zhǔn)則在LDA中選擇投影方向的區(qū)別，以證明RS在LDA中的優(yōu)勢。如表1所示，假設(shè)有三個相互獨立的投影方向，其類內(nèi)距離為wTpSwwp，總體方差為wTpStwp，假設(shè)需要保留兩個投影方向，則TR準(zhǔn)則的數(shù)值關(guān)系如下：

對于TR準(zhǔn)則，根據(jù)式（4），會傾向于選擇投影方向1和投影方向3。而RS準(zhǔn)則的數(shù)值關(guān)系如下：

同樣，根據(jù)式（5），投影方向1和2會被RS準(zhǔn)則選擇出來。根據(jù)TR準(zhǔn)則選擇出來投影方向1和3的組合，因投影方向3方差較小，使得該組合的整體判別性較小，相比之下，RS會選擇出方差大的投影方向1、2組合，顯然，RS選擇的組合更具判別性。由此可以看出，RS可以避免選擇方差較小的投影方向，以提高降維后低維數(shù)據(jù)的判別性。

2 快速自適應(yīng)局部比值和判別分析算法

2.1 局部比值和線性判別分析模型

雖然比值和模型可以選擇更具判別性的特征，但模型只關(guān)注樣本的全局信息，這導(dǎo)致模型只適用于服從高斯分布的數(shù)據(jù)集，使得算法的應(yīng)用十分受限。而在現(xiàn)實世界中，數(shù)據(jù)集往往是服從非高斯分布的，如流形數(shù)據(jù)。受到LFDA的啟發(fā)，數(shù)據(jù)的局部結(jié)構(gòu)能更適合流形數(shù)據(jù)的嵌入［13］，因此將樣本的局部信息引入到式（5）的模型中。為了更好地闡述模型的物理意義，先將式（5）展開為向量對形式，具體如下：

其中：Si的第h行第h列元素為sijh、sijh為第i類的第j個樣本和第h個樣本的相似度，相似度越大，表示兩樣本距離越近、越相似。傳統(tǒng)計算sijh通過高斯核函數(shù)得到，如下所示。

sijh=exp（－（‖xij－xih‖22/σ））（10）

其中：σ為任意正數(shù)。與式（8）相比，式（8）是式（9）的Si的每個元素都為1/ni的情況，即同類樣本之間的權(quán)重相同，這意味模型會優(yōu)先優(yōu)化彼此距離遠(yuǎn)的樣本，而不關(guān)注與彼此較近的樣本關(guān)系，從而無法保留樣本的局部結(jié)構(gòu)。對于式（9），為了目標(biāo)函數(shù)最小化，式（9）會更關(guān)注sijh大的兩個樣本，即更關(guān)注局部較近的樣本信息，從而保留局部結(jié)構(gòu)。

2.2 基于香農(nóng)熵的自適應(yīng)子空間學(xué)習(xí)

雖然在2.1節(jié)提出了局部比值和模型，但相似度的獲取是從原始空間中的樣本得到，一旦原始空間受到了噪聲和冗余特征的污染，會直接影響相似度的評判，且式（10）獲取的sijh是否合理，依賴σ的選取，這些缺點將極大地影響算法的性能。

本文認(rèn)為最優(yōu)鄰接圖應(yīng)在最優(yōu)化子空間中尋找，這是由于降維的實質(zhì)是尋找數(shù)據(jù)的低維嵌入結(jié)構(gòu)，而最優(yōu)鄰接圖理應(yīng)由低維嵌入結(jié)構(gòu)得到。因此，鄰接圖應(yīng)由在子空間中的低維數(shù)據(jù)WTX得到，而不應(yīng)如式（10）的方式，由原始空間數(shù)據(jù)而得到。根據(jù)子空間來學(xué)習(xí)鄰接圖，可避免直接受到原始空間噪聲和冗余特征的干擾。具體來說，算法會交替優(yōu)化投影矩陣W和相似度矩陣S，利用子空間的數(shù)據(jù)學(xué)習(xí)S，且交替時無須調(diào)參，可以自適應(yīng)學(xué)習(xí)鄰接圖，以更好地表征樣本的局部結(jié)構(gòu)。

但對式（9）優(yōu)化S時，極易陷入平凡解，舉個簡單的例子，假設(shè)sij為第i類相似度矩陣Si的第j行，sij只有三個元素。顯然sij的最優(yōu)解為設(shè)置離第j個樣本最近的樣本權(quán)重為1，其他權(quán)重為0，即可使目標(biāo)函數(shù)最小的值，如sij為［1，0，0］，但這是平凡解，因為只能保留最近樣本的局部信息。而理想的最優(yōu)解應(yīng)能保留多個近鄰點的局部信息。因此，引入香農(nóng)熵H（sij）=-∑nih=1sijhln sijh。-H（sij）作為懲罰項，在出現(xiàn)解［1，0，0］時，值最大，以懲罰目標(biāo)函數(shù)，使sij考慮元素權(quán)值分配更均勻的解。式（9）重寫為

其中：γ是平衡因子，用于權(quán)衡判別分析和香農(nóng)熵之間的關(guān)系。

2.3 基于錨點的加速策略

2.2節(jié)提到了子空間學(xué)習(xí)需要迭代更新S，但更新S的時間復(fù)雜度至少為O（n2），對大數(shù)據(jù)集而言，這個時間復(fù)雜度是難于令人接受的。針對子空間學(xué)習(xí)這一缺點，本文采用錨點的策略，通過錨點和樣本之間的相似度來表征低維數(shù)據(jù)的局部結(jié)構(gòu)，以實現(xiàn)更新S的加速，式（11）重寫為

3 算法優(yōu)化

優(yōu)化式（12）是一個NP問題，為了高效優(yōu)化該問題，采用交替迭代的策略：固定W、S，更新U；固定U、S，更新W；固定U、W，更新S。

1）固定W和S，優(yōu)化錨點矩陣U

由于固定S和W，則式（12）中的香農(nóng)熵項和分母項為常數(shù)，所以，優(yōu)化問題可簡化為

若忽略較小sijh，錨點物理含義表現(xiàn)為周圍同類點的中心，隱式地將同類數(shù)據(jù)劃分為不同的簇，使同簇樣本越近越好，以探索數(shù)據(jù)局部結(jié)構(gòu)，而不是關(guān)注數(shù)據(jù)的全局結(jié)構(gòu)，使得算法能適應(yīng)同類非高斯分布的數(shù)據(jù)。舉個簡單例子說明利用錨點探索局部結(jié)構(gòu)是有效的，如圖1所示，類別1是同類非高斯分布數(shù)據(jù)，可以明顯分為兩個簇。根據(jù)LDA使同類數(shù)據(jù)越近越好的思想，在全局視角下，不難想象圖1在全局情況下的投影方向，而投影結(jié)果是類別1和2的數(shù)據(jù)混在一起，難以區(qū)分；而在局部視角下，類別1的錨點會把周圍相似度高的同類樣本劃分為不同簇，對于優(yōu)化來說，不同簇可以被認(rèn)為是不同的類，因此可得到局部情況下的投影方向，在投影后，依然保持對兩類別的區(qū)分度，說明了局部算法可以適用于同類非高斯分布的數(shù)據(jù)。

根據(jù)式（15）便可依此類推，隨著錨點的自適應(yīng)更新，得到最優(yōu)錨點矩陣U。

2）固定U和S，優(yōu)化投影矩陣W

為方便優(yōu)化，固定S和U，根據(jù)式（15），則式（12）可簡化為

對于式（16）的任意第p項，可分為如下兩個子問題。

根據(jù)式（3），式（17）可簡化為

為了簡化式（18），提出以下引理1，并詳細(xì)證明引理1。

式（21）可展開為

顯然，式（22）的三項可以用跡函數(shù)的形式表達(dá)，如下所示。

其中：D1、D2為對角矩陣，D1的第j個對角元素為∑vih=1sijh，D2的第h個對角元素為∑nij=1sijh。由約束∑vih=1sijh=1和式（23）可得

由式（15）轉(zhuǎn)為矩陣形式，可得i=XiSiDi，代入式（24）（25）得

結(jié)合式（26）～（28），式（21）可重寫為

因此，由式（18）可得

證畢。由引理1，且令SL=XLXT，式（16）可簡化為

為了優(yōu)化式（31），不妨假設(shè)投影矩陣中只有一項wp，而其他的投影方向已達(dá)到最優(yōu)。由于求解wp應(yīng)取決于投影方向，而不是wp的模長，所以可以進(jìn)行放縮，則式（31）可轉(zhuǎn)換為

其中：W（p）=［w1，wp-1，wp+1，…，wk］T，0為全0向量。構(gòu)造式（32）的拉格朗日函數(shù)為

L（Wp，α，λ）=wTpStwp-αTWT（p）wp，λ（wTpSLwp-1）（33）

其中：α=［α1，α2，…，αk－1］T和λ皆為拉格朗日乘子。對式（33）關(guān)于wp求導(dǎo)，并令式（34）為0。

令μ=1/（2α），對上式左乘WT（p）S－1L得

μ=（WT（p）S－1LW（p））－1WT（p）S－1LStwp（35）

將式（35）代入式（34），可得

（I-S－1LW（WT（p）S－1LW（p））－1WT（p））S－1LStwp=λwp（36）

對上式左乘wTpSL，且wTpW（p）=0，可得

因此，式（32）的解wp為式（38）特征值分解的最大特征值所對應(yīng)的特征向量。

（I-S－1LW（WT（p）S－1LW（p））－1WT（p））S－1LSt（38）

依此類推，便可迭代優(yōu)化出投影矩陣W的k列向量。

3）固定U和W，優(yōu)化相似度矩陣S

由于固定U和W，則式（12）可被改寫為

注意到，對式（39）的每個類的優(yōu)化問題是相互獨立的，并且對于Si的每一行也可單獨求解。因此，對Si的第j行sij的優(yōu)化可以表述為以下問題：

其中：η是拉格朗日算子。對式（41）關(guān)于sijh求導(dǎo)，且令求導(dǎo)結(jié)果為0，如下所示。

則有

結(jié)合約束∑vih=1sijh=1和式（44），則有

將式（44）代入式（43），可得

可以注意到，式（45）總是滿足約束0≤sijh≤1。因此，通過式（45）即可計算出最優(yōu)的相似度矩陣S。綜上，利用式（15）（38）和（45）交替優(yōu)化錨點矩陣U、投影矩陣W和相似度矩陣S，直到式（12）的目標(biāo)函數(shù)值收斂，即可得到最優(yōu)的W。

3.1 FALRSDA算法流程

算法1 FALRSDA

輸入：原始數(shù)據(jù)X，標(biāo)簽矩陣Y，每類的錨點個數(shù)vi，正則化系數(shù)γ。

輸出：投影矩陣W。

a）初始化：對原始數(shù)據(jù)X按標(biāo)簽進(jìn)行排序，且進(jìn)行歸一化處理。隨機(jī)初始化滿足WTW=I的投影矩陣W。通過模糊聚類算法得到第i類相似度矩陣Si。

b）根據(jù)式（20），更新L。

c）根據(jù)式（38），更新每個wp。

d）根據(jù)式（15），更新每個Ui。

e）根據(jù)式（45），更新每個Si。

f）重復(fù)步驟b）～e），直到收斂。

3.2 時間復(fù)雜度分析

本文算法輸入的訓(xùn)練矩陣為X∈RApd×n，d為維數(shù)，n為樣本數(shù)，降維維數(shù)為k。為了方便，假設(shè)每個類的錨點數(shù)是相同的v。時間復(fù)雜度主要由迭代更新投影矩陣W、相似度矩陣S和更新錨點U來提供，迭代收斂需要的次數(shù)為t，則更新投影矩陣W所需的時間復(fù)雜度為O（k（d3+d2k+dk2+k3）），更新相似度矩陣S所需的時間復(fù)雜度為O（nkd+cvdk+nkv+nvlog（v）），錨點矩陣U所需的時間復(fù)雜度為O（cvdk）?？紤]到n>>c、n>>v和d>>k，因此，F(xiàn)ALRSDA總的時間復(fù)雜度可近似為O（t（kd3+nkd）），且對于大數(shù)據(jù)集n>>d，算法的時間復(fù)雜度可近似為O（tnkd）。

4 實驗與分析

在本章中，所有實驗在MATLAB R2017b，計算機(jī)CPU為Intel i5-8500 3.00 GHz，內(nèi)存為16 GB的實驗環(huán)境中進(jìn)行。本文將通過以下實驗來驗證算法的有效性：a）在合成數(shù)據(jù)上的二維數(shù)據(jù)魯棒可視化實驗;b）在8個真實數(shù)據(jù)集上的分類實驗;c）收斂和運行時間實驗。

4.1 對比算法和參數(shù)設(shè)置

為驗證本文算法的有效性，將FALRSDA與LDA、GRS、ANLRSLDA、LFDA、LSDA、ALLDA、DMEG等降維算法進(jìn)行對比實驗。其中LDA、GRS是全局降維算法，其余為局部降維算法，特別地，GRS、ANLRSLDA是基于RS準(zhǔn)則的降維算法，ALLDA、DMEG是具有子空間學(xué)習(xí)能力的降維算法。在本次實驗中，LDA的降維維數(shù)設(shè)置為［1：min（d－1，c－1）］，而其余算法的降維維數(shù)都設(shè)置在［1：d－1］搜索，而LFDA、LSDA、ALLDA、DMEG的類內(nèi)近鄰數(shù)［1：o－1］，o是數(shù)據(jù)集中最小類樣本數(shù)，單獨地，將LSDA類間近鄰數(shù)設(shè)置為10，DMEG的超參數(shù)根據(jù)文獻(xiàn)［19］給出的經(jīng)驗值設(shè)置為1，其余超參數(shù)皆從［0.001，0.01，0.1，1，10，100］中進(jìn)行網(wǎng)格搜索，F(xiàn)ALRSDA算法的每類錨點數(shù)取占本類數(shù)［0.1，0.2，0.4，0.6］比率的數(shù)量。

4.2 數(shù)據(jù)集描述及預(yù)處理

實驗所涉及的數(shù)據(jù)集共九個，包括一個合成數(shù)據(jù)集，三個UCI數(shù)據(jù)集，三個人臉數(shù)據(jù)集，以及USPS手寫數(shù)字?jǐn)?shù)據(jù)集和Coil20物體數(shù)據(jù)集。合成數(shù)據(jù)集由隨機(jī)高斯函數(shù)產(chǎn)生，包含三類，一類為150個樣本、兩類包含300樣本的二維非高斯分布的數(shù)據(jù)集，如圖2所示。UCI數(shù)據(jù)集包含balance、Australian、German數(shù)據(jù)集。人臉數(shù)據(jù)集包括UMIST、YaleB和Pose27。本文實驗對所有的數(shù)據(jù)集進(jìn)行了歸一化處理，為了避免對比算法因樣本存在零空間而無法運行，采用PCA對USPS、Coil20和人臉數(shù)據(jù)集進(jìn)行預(yù)處理，保留樣本的95%方差信息，以去除零空間。關(guān)于數(shù)據(jù)集的詳細(xì)信息如表2所示。

4.3 合成數(shù)據(jù)集魯棒性實驗

本節(jié)在合成數(shù)據(jù)集上進(jìn)行了魯棒性實驗，并將結(jié)果進(jìn)行可視化。具體來說，采用高斯隨機(jī)函數(shù)產(chǎn)生兩組高維高斯噪聲作為合成數(shù)據(jù)集的擴(kuò)展維數(shù)，其中，兩組高斯噪聲的維數(shù)和方差分別為（15，2）和（250，4）。最后，采用所有的降維算法將這些受噪聲污染的數(shù)據(jù)投影到二維子空間中。結(jié)果如圖3、4所示。

觀察圖3、4可以發(fā)現(xiàn)，在兩種情況中，LDA、GRS總是無法探索其在低維子空間中的內(nèi)在結(jié)構(gòu)，這主要是由LDA、GRS的全局性導(dǎo)致的，所以無法適用于非高斯分布數(shù)據(jù)。局部降維算法LFDA、LSDA在兩種情況下同樣表現(xiàn)不佳，這是因為噪聲的維數(shù)和方差的增加對原始空間中近鄰的選擇有負(fù)面影響，說明鄰接圖容易受到噪聲的影響。而ANLRSLDA在噪聲較小的情況下，能較好地保存低維數(shù)據(jù)的局部結(jié)構(gòu)，但在噪聲較大時，表現(xiàn)同樣不佳。這是由于ANLRSLDA可以自適應(yīng)構(gòu)造鄰接圖，在一定程度上抑制噪聲的干擾，但當(dāng)噪聲比較大時，低維數(shù)據(jù)的局部結(jié)構(gòu)被噪聲淹沒，而無法提取有效的局部結(jié)構(gòu)。子空間學(xué)習(xí)算法ALLDA、DMEG、FALRSDA在不同的噪聲情況下，都能很好地保留低維數(shù)據(jù)的局部結(jié)構(gòu)，這表明在最優(yōu)子空間上學(xué)習(xí)最優(yōu)相似圖的方式可以有效地避免原始空間中噪聲的影響。特別地，根據(jù)圖4可以看出，F(xiàn)ALRSDA相比其他的子空間學(xué)習(xí)算法具有更好的表現(xiàn)，這歸因于自適應(yīng)的子塊分區(qū)策略。通過為每個類分配錨點，隱式地劃分為多個簇，以此來描述數(shù)據(jù)的局部結(jié)構(gòu)。此外，本文采用香農(nóng)熵理論來控制圖權(quán)值的均勻性，促進(jìn)了內(nèi)在結(jié)構(gòu)的學(xué)習(xí)。

4.4 真實數(shù)據(jù)集分類實驗

在本次實驗中，隨機(jī)選擇UCI和人臉數(shù)據(jù)集的40%的樣本作為訓(xùn)練集，60%的樣本作為測試集，利用訓(xùn)練集學(xué)習(xí)出各算法的最優(yōu)投影矩陣W，再對測試集進(jìn)行投影。最后采用最近鄰分類器對降維后的測試樣本進(jìn)行分類預(yù)測，重復(fù)10次實驗，再統(tǒng)計預(yù)測的準(zhǔn)確率，以得到平均準(zhǔn)確率和方差。在表3中，列出各算法在所有真實數(shù)據(jù)集中最優(yōu)的平均準(zhǔn)確率和對應(yīng)的方差以及最優(yōu)維度，加粗?jǐn)?shù)據(jù)表示為同一數(shù)據(jù)集下的最優(yōu)結(jié)果。圖5為在UCI數(shù)據(jù)集上，不同算法在不同降維數(shù)上的準(zhǔn)確率曲線。圖6（a）為在USPS上的表現(xiàn)，圖6（b）（c）為在Coil上各算法的性能表現(xiàn)。圖7～9分別為在UMIST、YaleB、Pose27上各算法的性能曲線。

從表3中可以觀察到，F(xiàn)ALRSDA在所有數(shù)據(jù)集上的性能表現(xiàn)皆為最好，在Australian能比其他算法都高出3個百分點，在German、USPS數(shù)據(jù)集都比其他算法高1個百分點，特別地，在balance上，比其他算法高5個百分點。而在Coil20、UMIST數(shù)據(jù)集上，除了LDA，其他算法都表現(xiàn)得十分優(yōu)異，特別地，F(xiàn)ALRSDA在兩數(shù)據(jù)集上分別達(dá)到了99.96%和99.97%的準(zhǔn)確率。在YaleB和Pose27數(shù)據(jù)集上，F(xiàn)ALRSDA同樣都比其他算法高0.5～1個百分點。同時在Coil20、UMIST和Pose27數(shù)據(jù)集上擁有極低的方差。

從圖5中可以看出，F(xiàn)ALRSDA在balance和German上性能表現(xiàn)始終高于其他對比算法，在Australian上，前面維度FALRSDA表現(xiàn)優(yōu)秀，但隨著維度增加，性能出現(xiàn)下降。在圖6（a）中，F(xiàn)ALRSDA性能在前面維度與對比算法相差不大，隨著維度增加，F(xiàn)ALRSDA取得最高的分類準(zhǔn)確度。在圖6（b）（c）～圖9中，F(xiàn)ALRSDA在總體上的性能始終高于其他對比算法，但在YaleB和Pose27，隨著維度逐漸達(dá)到最高，所有算法皆出現(xiàn)了性能下降的現(xiàn)象，這表明當(dāng)維度達(dá)到一定時，增加更多維度并不利于分類任務(wù)，反而會增加冗余信息和計算量。與此同時，除了FALRSDA，GRS和ANLRSLDA在所有數(shù)據(jù)集上的表現(xiàn)同樣出色，這歸結(jié)于RS框架對分類任務(wù)的有效性。值得注意的是，LDA在Coil20、UMIST、YaleB上，性能曲線表現(xiàn)最差，但性能曲線依然保持很強的上升趨勢，這可能是由最大降維數(shù)的限制造成的。

綜合上述各種性能表現(xiàn)，說明了FALRSDA算法無論是在低維數(shù)據(jù)集，還是高維數(shù)據(jù)集上，都有良好的表現(xiàn)，證明了FALRSDA的有效性。這是由于基于RS準(zhǔn)則能夠提取更具判別信息的特征，錨點能探索數(shù)據(jù)的局部結(jié)構(gòu)，子空間學(xué)習(xí)使其最優(yōu)的鄰接圖，所以才有最佳的分類性能表現(xiàn)。

4.5 收斂和運行時間實驗

為了驗證本文優(yōu)化算法在尋找最優(yōu)子空間時目標(biāo)函數(shù)已經(jīng)收斂，給出在對應(yīng)3.4節(jié)中最優(yōu)子空間條件下，固定參數(shù)γ為1，錨點數(shù)量固定為類數(shù)的20%，迭代次數(shù)為10，8個數(shù)據(jù)集的目標(biāo)函數(shù)收斂圖如圖10所示。接著，為了驗證本文錨點的加速策略是有效的，在各算法的最優(yōu)子空間中運行10次，并統(tǒng)計平均值和方差，如表4所示。

對于圖10，可以看出本文優(yōu)化算法在8個數(shù)據(jù)集上訓(xùn)練，經(jīng)過10次迭代，所有目標(biāo)函數(shù)皆達(dá)到收斂狀態(tài)，證明了所提出的迭代優(yōu)化算法的有效性。對于表4，由于子空間學(xué)習(xí)算法需要迭代更新鄰接圖，而其他算法無須迭代，所以，非迭代算法在時間上更有競爭力。而本文算法使用的錨點加速策略是針對優(yōu)化子空間學(xué)習(xí)算法計算量高的問題，因此可以發(fā)現(xiàn)，F(xiàn)ALRSDA在所有數(shù)據(jù)集上花費的時間皆比另外兩個子空間學(xué)習(xí)算法ALLDA和DMEG要少。另外，對于n/d最大的balance數(shù)據(jù)集，F(xiàn)ALRSDA甚至快過非迭代算法ANLRSLDA。因此，證明了本文算法錨點策略的有效性，且在n>>d的條件下，優(yōu)勢更明顯。

5 結(jié)束語

本文提出了一個基于子空間學(xué)習(xí)的快速自適應(yīng)比值和局部判別分析算法。該算法首先采用了比值和準(zhǔn)則來避免傳統(tǒng)的跡比準(zhǔn)則的弊端，以選擇更具判別性的投影方向；并且引用保留局部結(jié)構(gòu)的思想和子空間學(xué)習(xí)，使得算法能探索出樣本之間內(nèi)在的局部結(jié)構(gòu)，同時避免受到原始空間噪聲帶來的影響；通過引入香農(nóng)熵約束，使得相似度分布更加均勻，以避免平凡解；針對避免子空間學(xué)習(xí)計算量大的問題，通過引入錨點，加速子空間學(xué)習(xí)，同時為同類數(shù)據(jù)分塊，使其適應(yīng)同類非高斯分布的數(shù)據(jù)集。最后，通過大量的實驗驗證了本文算法的有效性。

盡管FALRSDA相較于對比算法有著更好的性能，但筆者認(rèn)為該算法依然有進(jìn)一步探索的空間。例如，能否讓樣本和錨點之間的關(guān)系稀疏，而進(jìn)一步提取低維空間的局部結(jié)構(gòu)和減少噪聲的影響，這將是未來探索的方向。

參考文獻(xiàn)：

[1]梁露方.Fisher線性判別分析問題的求解算法研究［D］.昆明：云南師范大學(xué)，2020.（Liang Lufang. Research on the algorithm of Fisher linear discriminant analysis［D］.Kunming：Yunnan Normal University，2020.）

［2]王繼奎，楊正國，劉學(xué)文，等.一種基于極大熵的快速無監(jiān)督線性降維方法［J］.軟件學(xué)報，2023，34（4）：1779-1795.（Wang Jikui， Yang Zhengguo， Liu Xuewen， et al. Fast unsupervised dimension reduction method based on maximum entropy[J].Journal of Software，2023，34（4）：1779-1795.）

［3]Jia Weikuan， Sun Meili， Lian Jian， et al. Feature dimensionality reduction：a review［J］.Complex & Intelligent Systems，2022，8（3）：2663-2693.

［4]Gao Junyu， Wang Qi， Li Xuelong. PCC Net： perspective crowd coun-ting via spatial convolutional network［J］.IEEE Trans on Circuits and Systems for Video Technology，2019，30（10）：3486-3498.

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

［6]Dong Wei， Woz＇niak M， Wu Junsheng， et al. Denoising aggregation of graph neural networks by using principal component analysis［J］.IEEE Trans on Industrial Informatics，2023，19（3）：2385-2394.

［7]Zhu Fa， Gao Junbin， Yang Jian， et al. Neighborhood linear discriminant analysis［J］.Pattern Recognition，2022，123：108422.

［8]張家樂，林浩申，周科藝，等.自適應(yīng)近鄰局部比值和線性判別分析算法［J］.計算機(jī)工程與應(yīng)用，2022，58（22）：291-296.（Zhang Jiale， Lin Haoshen， Zhou Keyi， et al. Adaptive neighbor local ratio sum linear discriminant analysis［J］.Computer Engineering and Applications，2022，58（22）：291-296.）

［9]Guo Yuefei， Li Shijin， Yang Jingyu， et al. A generalized Foley-Sammon transform based on generalized Fisher discriminant criterion and its application to face recognition［J］.Pattern Recognition Letters，2003，24（1-3）：147-158.

［10]Zhao Haifeng， Wang Zheng， Nie Feiping. Orthogonal least squares regression for feature extraction［J］.Neurocomputing，2016，216：200-207.

［11]Luo Fulin， Zhang Liangpei， Du Bo， et al. Dimensionality reduction with enhanced hybrid-graph discriminant learning for hyperspectral image classification［J］.IEEE Trans on Geoscience and Remote Sensing，2020，58（8）：5336-5353.

［12]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.

［13]Sugiyama M. Local Fisher discriminant analysis for supervised dimensionality reduction［C］//Proc of the 23rd International Conference on Machine Learning.New York：ACM Press，2006：905-912.

［14]Cai Deng， He Xiaofei， Zhou Kun， et al. Locality sensitive discriminant analysis［C］//Proc of the 20th International Joint Conference on Artificial Intelligence.San Francisco，CA：Morgan Kaufmann，2007：708-713.

［15]Liang Ke， Yang Xiaojun， Xu Yuxiong， et al. Ratio sum formula for dimensionality reduction［J］.Multimedia Tools and Applications，2020，80（3）：4367-4382.

［16]Wang Jingyu， Wang Hongmei， Nie Feiping， et al. Ratio sum versus sum ratio for linear discriminant analysis［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2021，44（12）：10171-10185.

［17]Luo Tingjin， Hou Chenping， Nie Feiping， et al. Dimension reduction for non-Gaussian data by adaptive discriminative analysis［J］.IEEE Trans on Cybernetics，2018，49（3）：933-946.

［18]Nie Feiping， Wang Zheng， Wang Rong， et al. Adaptive local linear discriminant analysis［J］.ACM Trans on Knowledge Discovery from Data，2020，14（1）：1-19.

［19]Wang Zheng， Nie Feiping， Wang Rong， et al. Local structured feature learning with dynamic maximum entropy graph［J］.Pattern Re-cognition，2021，111：107673.

［20]Wang Rong， Nie Feiping， Yu Weizhong. Fast spectral clustering with anchor graph for large hyperspectral images［J］.IEEE Geoscience and Remote Sensing Letters，2017，14（11）：2003-2007.