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

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

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

中圖分類(lèi)號(hào)：TP391.4?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：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ù)維度也隨之快速增長(zhǎng)，涌現(xiàn)出越來(lái)越多的高維數(shù)據(jù)［1］，然而維度的增加導(dǎo)致了計(jì)算復(fù)雜度劇烈增加，以及原始數(shù)據(jù)中存在大量冗余特征等問(wèn)題［2］，阻礙了一些領(lǐng)域的發(fā)展，如視頻分析［3］、人群分析［4］、圖像分析［5］等。因此，設(shè)計(jì)一個(gè)用來(lái)提取數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，以尋求數(shù)據(jù)最優(yōu)表示的降維算法是極其緊迫的。

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

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

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

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

1 相關(guān)工作

1.1 線性判別分析

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

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

1.2 比值和線性判別分析

式（1）也可被寫(xiě)為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 基于錨點(diǎn)的加速策略

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

3 算法優(yōu)化

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

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

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

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

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

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

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

對(duì)于式（16）的任意第p項(xiàng)，可分為如下兩個(gè)子問(wèn)題。

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

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

式（21）可展開(kāi)為

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

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

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

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

因此，由式（18）可得

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

為了優(yōu)化式（31），不妨假設(shè)投影矩陣中只有一項(xiàng)wp，而其他的投影方向已達(dá)到最優(yōu)。由于求解wp應(yīng)取決于投影方向，而不是wp的模長(zhǎng)，所以可以進(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和λ皆為拉格朗日乘子。對(duì)式（33）關(guān)于wp求導(dǎo)，并令式（34）為0。

令μ=1/（2α），對(duì)上式左乘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）

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

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

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

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

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

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

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

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

則有

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

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

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

3.1 FALRSDA算法流程

算法1 FALRSDA

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

輸出：投影矩陣W。

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

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

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

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

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

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

本節(jié)在合成數(shù)據(jù)集上進(jìn)行了魯棒性實(shí)驗(yàn)，并將結(jié)果進(jìn)行可視化。具體來(lái)說(shuō)，采用高斯隨機(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總是無(wú)法探索其在低維子空間中的內(nèi)在結(jié)構(gòu)，這主要是由LDA、GRS的全局性導(dǎo)致的，所以無(wú)法適用于非高斯分布數(shù)據(jù)。局部降維算法LFDA、LSDA在兩種情況下同樣表現(xiàn)不佳，這是因?yàn)樵肼暤木S數(shù)和方差的增加對(duì)原始空間中近鄰的選擇有負(fù)面影響，說(shuō)明鄰接圖容易受到噪聲的影響。而ANLRSLDA在噪聲較小的情況下，能較好地保存低維數(shù)據(jù)的局部結(jié)構(gòu)，但在噪聲較大時(shí)，表現(xiàn)同樣不佳。這是由于ANLRSLDA可以自適應(yīng)構(gòu)造鄰接圖，在一定程度上抑制噪聲的干擾，但當(dāng)噪聲比較大時(shí)，低維數(shù)據(jù)的局部結(jié)構(gòu)被噪聲淹沒(méi)，而無(wú)法提取有效的局部結(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ū)策略。通過(guò)為每個(gè)類(lèi)分配錨點(diǎn)，隱式地劃分為多個(gè)簇，以此來(lái)描述數(shù)據(jù)的局部結(jié)構(gòu)。此外，本文采用香農(nóng)熵理論來(lái)控制圖權(quán)值的均勻性，促進(jìn)了內(nèi)在結(jié)構(gòu)的學(xué)習(xí)。

4.4 真實(shí)數(shù)據(jù)集分類(lèi)實(shí)驗(yàn)

在本次實(shí)驗(yàn)中，隨機(jī)選擇UCI和人臉數(shù)據(jù)集的40%的樣本作為訓(xùn)練集，60%的樣本作為測(cè)試集，利用訓(xùn)練集學(xué)習(xí)出各算法的最優(yōu)投影矩陣W，再對(duì)測(cè)試集進(jìn)行投影。最后采用最近鄰分類(lèi)器對(duì)降維后的測(cè)試樣本進(jìn)行分類(lèi)預(yù)測(cè)，重復(fù)10次實(shí)驗(yàn)，再統(tǒng)計(jì)預(yù)測(cè)的準(zhǔn)確率，以得到平均準(zhǔn)確率和方差。在表3中，列出各算法在所有真實(shí)數(shù)據(jù)集中最優(yōu)的平均準(zhǔn)確率和對(duì)應(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個(gè)百分點(diǎn)，在German、USPS數(shù)據(jù)集都比其他算法高1個(gè)百分點(diǎn)，特別地，在balance上，比其他算法高5個(gè)百分點(diǎn)。而在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個(gè)百分點(diǎn)。同時(shí)在Coil20、UMIST和Pose27數(shù)據(jù)集上擁有極低的方差。

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

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

4.5 收斂和運(yùn)行時(shí)間實(shí)驗(yàn)

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

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

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

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

［2]王繼奎，楊正國(guó)，劉學(xué)文，等.一種基于極大熵的快速無(wú)監(jiān)督線性降維方法［J］.軟件學(xué)報(bào)，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]張家樂(lè)，林浩申，周科藝，等.自適應(yīng)近鄰局部比值和線性判別分析算法［J］.計(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.