基于Sinkhorn距離特征縮放的多約束非負(fù)矩陣分解算法

李松濤 李維剛* 甘 平 蔣 林

①(武漢科技大學(xué)冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心 武漢 430081)

②(武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室 武漢 430081)

1 引言

近年來，隨著電子信息技術(shù)的發(fā)展，圖像數(shù)據(jù)在維度與數(shù)量上雙重爆發(fā)式增長(zhǎng)，導(dǎo)致視覺特征與高層語義之間“語義鴻溝”逐漸增大，成為視覺感知領(lǐng)域的瓶頸，因此如何從圖像中提取有效的低維數(shù)據(jù)來提高視覺感知的性能成為一個(gè)重要的問題[1–3]。作為一種著名的子空間學(xué)習(xí)方法，非負(fù)矩陣分解(Nonnegative Matrix Factorization, NMF)可以以適當(dāng)?shù)姆绞皆诘途S子空間中表達(dá)高維數(shù)據(jù)，進(jìn)而可以更好地揭示數(shù)據(jù)的潛在結(jié)構(gòu)信息，并提高各種模式感知算法的能力[4]。由于NMF算法的非負(fù)性子空間表達(dá)更符合人們心理學(xué)和生理學(xué)對(duì)整體數(shù)據(jù)感知的描述，而且其對(duì)整體數(shù)據(jù)的分解符合純加性的感知，這也更易于直觀的理解，因此它在某種意義上抓住了數(shù)據(jù)描述的本質(zhì)，這與其他子空間學(xué)習(xí)方法(例如矢量量化(Vector Quantization, VQ)、主成分分析(Principal Component Analysis, PCA)、奇異值分解(Singular Value Decomposition, SVD)等)相區(qū)別。NMF在多種任務(wù)中取得了令人印象深刻的性能，例如社區(qū)檢測(cè)[5]、高光譜解混[6]、面部特征提取[7]、推薦系統(tǒng)[8]等。

傳統(tǒng)NMF算法的缺點(diǎn)之一是忽略了數(shù)據(jù)集的固有結(jié)構(gòu)，該問題表現(xiàn)在多個(gè)方面。首先，樣本之間的相關(guān)性可能存在于原始數(shù)據(jù)集中，所以希望可以利用這些相關(guān)性信息來提高NMF的性能；其次，特征之間存在一定的相關(guān)性，基于高斯誤差的L2距離方法不能準(zhǔn)確度量特征之間的距離，這使得樣本內(nèi)部特征的相關(guān)性較弱，導(dǎo)致NMF算法對(duì)高維空間的平移噪聲有著不準(zhǔn)確的預(yù)估，抑制了算法的性能；最后，原NMF算法在分解過程由于其非負(fù)性的約束條件，忽略了編碼矩陣的稀疏性約束，導(dǎo)致分解結(jié)果的稀疏性較低，進(jìn)而影響全局的稀疏表達(dá)。

為了克服上述限制，研究人員主要從兩個(gè)方面著手優(yōu)化研究，多數(shù)研究圍繞算法本身改進(jìn)展開，如Shirdhonkar等人[9]使用地球真實(shí)距離(Earth Mover's Distance, EMD)來測(cè)量原始數(shù)據(jù)矩陣與乘積矩陣之間的差異，從而提出了EMD NMF。由于EMD對(duì)不同維度之間的關(guān)系敏感，與其他測(cè)量方法相比，EMD在感知空間差異上更加準(zhǔn)確，因此EMD NMF能提高樣本的子空間區(qū)分能力；Cai等人[10]結(jié)合流形學(xué)習(xí)的圖結(jié)構(gòu)理論提出了GNMF(Graph regularized Nonnegative Matrix Factorization)算法，其使用最近鄰圖對(duì)局部模型進(jìn)行幾何結(jié)構(gòu)建模，旨在找到保留圖結(jié)構(gòu)的矩陣分解，因此GNMF保留了固有的幾何結(jié)構(gòu)，同時(shí)獲得了隱藏語義信息的緊湊表示；Qian等人[11]結(jié)合EMD NMF與GNMF的建模思想，將Sinkhorn距離以損失函數(shù)的形式置入GNMF算法，而提出了SDNMF (Nonnegative Matrix Factorization with Sinkhorn Distance)算法，該方法在EMD NMF的基礎(chǔ)上提高了計(jì)算速度，并保留了空間的結(jié)構(gòu)與特征關(guān)聯(lián)能力，有較好的子空間學(xué)習(xí)能力；Hoyer[12]提出了一種稀疏的非負(fù)矩陣分解方法(Non-negative Matrix Factorization with Sparseness constrains, SNMF)，將稀疏約束引入到NMF目標(biāo)函數(shù)中，以控制分解因子的稀疏表示程度，這可以保證基于特征的零件信息表示形式的直接可解釋性；Liu等人[13]提出了一種稱為CNMF (Constrained Nonnegative Matrix Factorization)的半監(jiān)督NMF算法，它將一些先驗(yàn)標(biāo)簽信息視為附加的硬約束，并將其集成到NMF模型中以提高區(qū)分能力。同時(shí)也有研究人員從特征選擇與縮放方向入手，優(yōu)化算法性能，如Li等人[14]通過K鄰近算法縮放有效特征，進(jìn)而放大其他非核心特征的差距，使整體數(shù)據(jù)更易被定位捕獲，Jimenez-Cordero等人[15]通過同性高斯核結(jié)合特征關(guān)聯(lián)方法實(shí)現(xiàn)特征的縮放處理，從而提出了一種高精度的支持向量機(jī)批量分類方法。

但是，這些NMF算法的變體仍然存在各種缺陷。例如，EMD NMF與SDNMF在分解過程中需要重復(fù)計(jì)算分解因子乘積與原始矩陣之間的距離，這使算法計(jì)算非常耗時(shí)，雖然SDNMF算法在計(jì)算過程中使用熵正則方法去估算整體距離而提高了計(jì)算速度，但是整體速度仍然十分緩慢；GNMF缺乏對(duì)原始矩陣特征向量之間關(guān)系的考慮，導(dǎo)致在處理平移噪聲時(shí)性能較差；SNMF僅對(duì)分解過程施加稀疏約束，但缺乏對(duì)輸入數(shù)據(jù)原始結(jié)構(gòu)的約束，導(dǎo)致其子空間學(xué)習(xí)能力較弱；CNMF使用原始數(shù)據(jù)的標(biāo)簽信息，盡管提高了算法的性能，但在分解過程中未能充分利用原始數(shù)據(jù)的局部幾何特征和潛在的結(jié)構(gòu)信息，從而限制算法的應(yīng)用范圍及性能。

考慮到NMF中各種信息結(jié)構(gòu)與原始特征向量之間相關(guān)性的重要性，本文提出一種基于Sinkhorn距離特征縮放的多約束非負(fù)矩陣分解算法(Semi-Supervised Sinkhorn distance sparse and dual-Graph regularized Non-negative Matrix Factorization, S3GNMF)，本算法充分利用了流形圖結(jié)構(gòu)、稀疏約束以及標(biāo)簽信息來誘導(dǎo)分解，同時(shí)基于Sinkhorn距離對(duì)原始特征矩陣進(jìn)行縮放，提高了輸入數(shù)據(jù)中的特征關(guān)聯(lián)性，解決了將Sinkhorn距離引入損失函數(shù)而導(dǎo)致的計(jì)算效率緩慢問題，同時(shí)也提高了算法性能。在數(shù)學(xué)上，將算法公式化為定義明確的非負(fù)約束優(yōu)化問題，利用KKT (Karush–Kuhn–Tucker)條件推導(dǎo)出交叉迭代規(guī)則。此外，通過多組算法在不同的真實(shí)數(shù)據(jù)集和平移噪聲數(shù)據(jù)集上的聚類實(shí)驗(yàn)結(jié)果證明了所提算法的有效性。

2 基于Sinkhorn距離特征縮放的多約束非負(fù)矩陣分解

作為一種優(yōu)秀的NMF變種算法，SDNMF算法通過Sinkhorn距離構(gòu)造損失函數(shù)及流形圖結(jié)構(gòu)來保持?jǐn)?shù)據(jù)的幾何特征結(jié)構(gòu)，提高了算法的子空間學(xué)習(xí)能力，但其缺乏考慮稀疏性與先驗(yàn)標(biāo)簽的誘導(dǎo)分解，因此算法整體子空間學(xué)習(xí)能力不強(qiáng)，同時(shí)由于反復(fù)利用Sinkhorn距離計(jì)算分解誤差值，導(dǎo)致算法速度十分緩慢。為了克服上述問題，本文提出基于Sinkhorn距離特征縮放的多約束非負(fù)矩陣分解(S3GNMF)算法。本算法不僅首次將Sinkhorn距離作為原始矩陣的特征縮放工具，提高了特征關(guān)聯(lián)性，而且將標(biāo)簽信息納入雙流形圖結(jié)構(gòu)正則化，提高了算法的子空間學(xué)習(xí)能力，同時(shí)引入稀疏約束到NMF框架中，使分解因子稀疏化并提高了算法速度，也使算法更加穩(wěn)定；最后，綜合上述方法建立一個(gè)集成的S3GNMF算法的目標(biāo)函數(shù)，算法流程示意圖如圖1所示。

圖1 S3GNMF算法示意圖

2.1 基于Sinkhorn距離的特征縮放

給定兩個(gè)離散的直方圖Px與Py，距離度量矩陣M以及單位距離運(yùn)輸量矩陣T，EMD距離[16]定義了從Px到Py的最小運(yùn)輸量，該距離定義為

Txy表 示 由x到y(tǒng)的運(yùn) 輸 量，Mxy則 表 示x到y(tǒng)的 地面距離(通常以L1或L2距 離來定義) ，Sx代 表在x處需要運(yùn)輸?shù)目偭?，Ey是y處的總運(yùn)輸成本。Cuturi[17]提出了一種利用熵正則化來加速EMD距離的計(jì)算方法，該方法稱為Sinkhorn距離，F(xiàn)rogner等人[18]提出了一種將平滑傳輸擴(kuò)展到非標(biāo)準(zhǔn)化措施的松弛方法，該方法對(duì)Sinkhorn距離中傳輸邊緣的平等約束施加了KL散度的軟懲罰，得到了一個(gè)無約束的近似運(yùn)輸模型，在理論上加速了Sinkhorn距離的計(jì)算。該距離方法可表示如式(2)所示

{S矩陣可以有效地實(shí)現(xiàn)輸入矩陣的特征縮放，從而達(dá)到數(shù)據(jù)預(yù)處理的目的。

2.2 融合標(biāo)簽信息的雙圖流形結(jié)構(gòu)

為了充分地利用流形結(jié)構(gòu)對(duì)分解過程的正則化約束，本文分別構(gòu)建了兩個(gè)圖流形結(jié)構(gòu)，在NMF分解過程中對(duì)分解因子V和U進(jìn)行正則化處理。具體而言，首先構(gòu)造一個(gè)真實(shí)的最近鄰數(shù)據(jù)圖G，并連接X= [x1,x2,...,xn]中的近鄰點(diǎn)。為方便起見，采用0-1加權(quán)法構(gòu)造數(shù)據(jù)圖的權(quán)重矩陣，定義為

為提高數(shù)據(jù)圖結(jié)構(gòu)的正則化能力，將部分原始標(biāo)簽信息引入圖結(jié)構(gòu)中，有V=AZ，其中Z為輔助矩陣，A為標(biāo)簽約束矩陣，并帶有原始標(biāo)簽約束信息?？蓪(V)重寫為

該流形圖拉普拉斯矩陣為L(zhǎng)U=DU ?WU。

2.3 L2,1/2范數(shù)稀疏約束

基于稀疏約束的方法可以發(fā)掘特征空間的潛在關(guān)聯(lián)，很多研究表明稀疏約束可以選擇鑒別性稀疏特征來提高算法的效率和有效性，稀疏約束旨在使用適當(dāng)?shù)南∈枘Ｐ蛠韺?shí)現(xiàn)稀疏數(shù)據(jù)表示。該方法通常使用Lp,q的范數(shù)形式對(duì)分解過程進(jìn)行約束，是一種常見的提高矩陣分解性能的方法。例如，SNMF[12]在分解過程中對(duì)分解因子施加L2范數(shù)稀疏約束使因子更加稀疏，SGCNMF[5]在全局分解誤差上添加L2,1范數(shù)稀疏約束使分解誤差更加平滑，RGNMF[19]在輸入數(shù)據(jù)的噪聲中添加L1范數(shù)約束，以提高對(duì)噪聲特征的屏蔽能力，但是近年來Xu等人[20]發(fā)現(xiàn)Lp為標(biāo)準(zhǔn)范數(shù)，且q為1 /2 時(shí)，即Lp,1/2類的范數(shù)約束具有較好的稀疏性約束。因此，S3GNMF算法的基矩陣U上的L2,1/2范數(shù)稀疏約束為

將| |U||2,1/2作為正則化項(xiàng)加入目標(biāo)函數(shù)，在優(yōu)化目標(biāo)函數(shù)時(shí)，使用最小化L2,1/2范數(shù)能保證矩陣行列均稀疏，可以提高矩陣整體的稀疏性，使算法局部特征特異性降低，既可以降低噪聲對(duì)算法的影響，又可以提高算法的泛化能力與計(jì)算速度。

2.4 S3GNMF目標(biāo)函數(shù)

通過將特征縮放、R(V),R(U)、稀疏性約束和NMF集成到目標(biāo)函數(shù)中，從而可以得到S3GNMF算法的目標(biāo)函數(shù)為

其中，λ,β為流形圖正則化系數(shù)，θ為稀疏系數(shù)，S為輸入原始矩陣的Sinkhorn距離特征縮放結(jié)果。

3 S3GNMF算法求解

由于S3GNMF算法的非凸性，很難獲得全局最優(yōu)解，所以我們采用梯度下降法來優(yōu)化目標(biāo)函數(shù)。將算法的目標(biāo)函數(shù)展開重寫為

4 實(shí)驗(yàn)結(jié)果與分析

標(biāo)準(zhǔn)的圖像數(shù)據(jù)集中圖像數(shù)據(jù)大多是對(duì)齊且居中的，而在現(xiàn)實(shí)世界中，真實(shí)圖像可能十分復(fù)雜而且主體難以居中，導(dǎo)致無法完美地對(duì)齊；在校準(zhǔn)主體后仍可能存在局部變形。這些問題均會(huì)導(dǎo)致針對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集設(shè)計(jì)的算法性能受到極大的影響。所以我們嘗試在多類標(biāo)準(zhǔn)數(shù)據(jù)集與非對(duì)齊的平移噪聲數(shù)據(jù)上進(jìn)行算法子空間聚類實(shí)驗(yàn)。在第1個(gè)實(shí)驗(yàn)中，本文使用多種算法對(duì)5個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集分別進(jìn)行了聚類實(shí)驗(yàn)，并表明了本文所提算法對(duì)標(biāo)準(zhǔn)對(duì)齊數(shù)據(jù)有著更強(qiáng)的子空間學(xué)習(xí)能力，在第2個(gè)實(shí)驗(yàn)中，本文使用小范圍隨機(jī)平移的COIL20數(shù)據(jù)集來模擬非對(duì)齊數(shù)據(jù)，并證明了本方法比以往方法具有更強(qiáng)的魯棒性。為了公平地比較驗(yàn)證各算法在多方面的有效性，本文將所提算法與其他各NMF算法結(jié)果進(jìn)行比較，所有的實(shí)驗(yàn)均基于MATLABR2018b模擬，CPU為Intel Core I7-9700 K。

表1 基于Sinkhorn距離特征縮放的多約束非負(fù)矩陣分解算法S3GNMF (算法1)

4.1 數(shù)據(jù)集

本文基于COIL20與Faces95數(shù)據(jù)集設(shè)計(jì)了2個(gè)平移噪聲數(shù)據(jù)集，分別在2個(gè)平移噪聲數(shù)據(jù)集與5個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集(COIL20, PIE, Faces95, Pixraw10P,JAFFE)上進(jìn)行了聚類實(shí)驗(yàn)，數(shù)據(jù)集詳細(xì)說明如表2所示。

表2 各數(shù)據(jù)集的詳細(xì)說明

需要注意的是，所有的標(biāo)準(zhǔn)數(shù)據(jù)集全是對(duì)齊數(shù)據(jù)，為了考驗(yàn)所提算法針對(duì)非對(duì)齊數(shù)據(jù)的學(xué)習(xí)能力，本文使用小的隨機(jī)平移來模擬局部變形并在新的數(shù)據(jù)集上測(cè)試了本文方法，以顯示其魯棒性。具體來說，本文的數(shù)據(jù)集是由以下方法生成的：將數(shù)據(jù)集中每張圖片調(diào)整為( 32?ω)×(32?ω)大小，其中ω∈[1,4]的整數(shù)，然后將調(diào)整的圖像以隨機(jī)位置放入32×32的空白圖像中，圖2–圖6展示了上述數(shù)據(jù)集原始數(shù)據(jù)以及原始數(shù)據(jù)與平移噪聲數(shù)據(jù)對(duì)比。

圖2 PIE數(shù)據(jù)集

圖3 Pixraw10P數(shù)據(jù)集

圖4 JAFFE數(shù)據(jù)集

圖5 COIL20數(shù)據(jù)集與平移噪聲數(shù)據(jù)集對(duì)比

圖6 Faces95數(shù)據(jù)集與平移噪聲數(shù)據(jù)集對(duì)比

4.2 參數(shù)分析

如上所述，將Sinkhorn距離特征縮放過程中的兩個(gè)參數(shù)α和ε設(shè)為固定值(α= 10,ε= 100)，所以本節(jié)主要討論λ,β,θ3個(gè)約束參數(shù)。在參數(shù)對(duì)比實(shí)驗(yàn)中，本文在COIL20, PIE, Faces95, Pixraw10P和JAFFE 5個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集，以最大類別數(shù)做聚類對(duì)比，可以得出最佳的參數(shù)組合。例如：COIL20數(shù)據(jù)集以20作為k值，然后分別使λ,β,θ以[0.001,0.01, 0.1, 0, 1, 10, 100, 1000]，進(jìn)行20次綜合實(shí)驗(yàn)，取最終聚類結(jié)果的平均值做對(duì)比，S3GNMF參數(shù)對(duì)比實(shí)驗(yàn)如圖7所示。圖7中每個(gè)點(diǎn)的位置代表了λ, β, θ3個(gè)參數(shù)的具體值，顏色代表了實(shí)際的聚類精度，顏色越黃，表示實(shí)際聚類精度越高，顏色越藍(lán)表示聚類精度越低。

由圖7得知，λ和β作為流形正則化參數(shù)，β的取值在10以上時(shí)能取得較好效果，λ更多的是作為特征空間的約束，做整體子空間表達(dá)的一個(gè)微調(diào)，參數(shù)取值不宜過大，當(dāng)λ取值到1000時(shí)，對(duì)整體算法效果有負(fù)反饋。稀疏系數(shù)θ在上述實(shí)驗(yàn)過程中，更多起到的是對(duì)分解因子的稀疏約束與平滑噪聲中野值點(diǎn)作用，對(duì)準(zhǔn)確度提升不大，但是對(duì)算法性能穩(wěn)定性有顯著提升。

圖7 S3GNMF在5個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的參數(shù)表現(xiàn)

4.3 聚類結(jié)果與分析

本實(shí)驗(yàn)中，以本文所提算法S3GNMF與多個(gè)先進(jìn)NMF算法(NMF[21], CNMF[13], GNMF[10], SNMF[12], SDNMF[11], DSDNMF[22], SODNMF[23],AGNMF[24], ONMF[25], DENMF[26])對(duì)上述5個(gè)數(shù)據(jù)集進(jìn)行子空間學(xué)習(xí)聚類對(duì)比，聚類評(píng)價(jià)指標(biāo)為準(zhǔn)確度(ACcuracy, AC)與歸一化互信息(Normalized Mutual Information, NMI)，對(duì)應(yīng)指標(biāo)越高則表明子空間特征學(xué)習(xí)能力越強(qiáng)。由于S3GNMF, CNMF,SODNMF, DENMF算法需要部分標(biāo)簽信息，上述半監(jiān)督NMF方法均抽取了實(shí)驗(yàn)數(shù)據(jù)集的前20%的數(shù)據(jù)標(biāo)簽作為標(biāo)記樣本。所有的算法最大迭代次數(shù)為100，對(duì)比算法參數(shù)均為參考文獻(xiàn)中的最佳參數(shù)(例 如S O D N M F 取α=100, β=0.01, θ=0.1)，S3GNMF的參數(shù)設(shè)置為4.2節(jié)中實(shí)驗(yàn)對(duì)比得出的最佳參數(shù)組合，實(shí)驗(yàn)流程如下：

(1) 以原始數(shù)據(jù)集作為輸入數(shù)據(jù)，實(shí)驗(yàn)中設(shè)置k值為數(shù)據(jù)集的最大類別數(shù)，并作為k?means的聚類數(shù)；

(2) 以學(xué)習(xí)到的低維子空間特征表示作為輸入，進(jìn)行k ?means聚類，對(duì)聚類結(jié)果進(jìn)行AC和NMI評(píng)估；

(3) 重復(fù)執(zhí)行步驟(1)和步驟(2) 20次，取其平均值與標(biāo)準(zhǔn)差作為最終實(shí)驗(yàn)結(jié)果。

表3顯示了不同算法在5個(gè)數(shù)據(jù)集上的詳細(xì)聚類結(jié)果(每個(gè)聚類實(shí)驗(yàn)中有兩行數(shù)據(jù)展示，第1行數(shù)值代表聚類準(zhǔn)確度，第2行數(shù)據(jù)代表歸一化互信息)。

表3 各算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的對(duì)比(%)

各算法在兩個(gè)平移噪聲數(shù)據(jù)集上的聚類實(shí)驗(yàn)結(jié)果如表4和表5所示，其中ω表示空間平移尺度，ω越大，平移越劇烈。

表4 各算法在平移噪聲COIL20數(shù)據(jù)集上的對(duì)比(%)

表5 各算法在平移噪聲Faces95數(shù)據(jù)集上的對(duì)比(%)

為驗(yàn)證本文所提Sinkhorn距離特征縮放的作用，在S3GNMF基礎(chǔ)上移除特征縮放處理后，得到新的算法為(Semi-Supervised sparse and dual-Graph regularized Non-negative Matrix Factorization, S2GNMF)，S2GNMF與S3GNMF在上述多個(gè)數(shù)據(jù)集的詳細(xì)聚類結(jié)果如表6所示。

表6 S2GNMF與S3GNMF的聚類效果對(duì)比(%)

上述實(shí)驗(yàn)數(shù)據(jù)表明：

(1) 基于流形正則化的算法GNMF, SDNMF,DSDNMF, SODNMF, AGNMF, DENMF, S3GNMF在實(shí)驗(yàn)中表現(xiàn)要明顯優(yōu)于其他非流行正則化算法，證明了子空間學(xué)習(xí)中流形正則化在隱式結(jié)構(gòu)的重要性。

(2) 基于稀疏約束的各類算法在實(shí)驗(yàn)中，準(zhǔn)確度和歸一化互信息的標(biāo)準(zhǔn)差均低于其他非稀疏約束算法，證明了稀疏約束能增加局部學(xué)習(xí)能力與魯棒性。

(3) 對(duì)于半監(jiān)督學(xué)習(xí)算法CNMF, DENMF,SODNMF, S3GNMF，多混合約束算法明顯優(yōu)于單一約束算法，即部分標(biāo)簽信息能提高算法的學(xué)習(xí)能力，但是仍然需要有其他的子空間學(xué)習(xí)增強(qiáng)方法來針對(duì)有效數(shù)據(jù)進(jìn)行學(xué)習(xí)。

(4) 隨著平移噪聲強(qiáng)度的增加，S3GNMF算法的性能明顯優(yōu)于其他算法，證明了本文所提的Sinkhorn距離特征縮放與多約束的有效性，其中Sinkhorn距離特征縮放簡(jiǎn)化了特征矩陣的距離度量，平滑了特征矩陣中野值點(diǎn)對(duì)分解結(jié)果的影響，而結(jié)合多流形隱式結(jié)構(gòu)的正則化使整體算法泛化能力得到了提高，結(jié)合L2,1/2的稀疏約束，使實(shí)驗(yàn)數(shù)據(jù)十分穩(wěn)定，而且基矩陣表達(dá)的局部特征更為稀疏，更有利于子空間的學(xué)習(xí)表達(dá)。

(5) 由表6中S3GNMF和S2GNMF的對(duì)比結(jié)果可知，Sinkhorn距離對(duì)不同維度之間的關(guān)系更加敏感，能更好地捕獲類間關(guān)聯(lián)，所以S3GNMF中基于Sinkhorn距離特征縮放處理能有效地提高各特征類別之間的關(guān)聯(lián)，從而提高NMF算法的子空間學(xué)習(xí)能力。

4.4 算法復(fù)雜度與速度對(duì)比

本節(jié)首先分析了S3GNMF算法的復(fù)雜度，并討論了幾種對(duì)比算法的復(fù)雜度，最后設(shè)計(jì)了一組實(shí)驗(yàn)來計(jì)算各算法實(shí)際運(yùn)算時(shí)間。

接下來本文對(duì)比了各算法在COIL20, PIE,Faces95, Pixraw10P和JAFFE 5個(gè)數(shù)據(jù)集上的運(yùn)算速度，來驗(yàn)證算法的實(shí)際計(jì)算速度。實(shí)驗(yàn)中各算法單獨(dú)運(yùn)行20次，且設(shè)定最大迭代次數(shù)為100，k為數(shù)據(jù)集最大樣本種類數(shù)，將最終耗時(shí)平均值作為對(duì)比數(shù)值，詳細(xì)對(duì)比數(shù)據(jù)如表7所示。

由表7可知，SNMF算法分解效率最高，因?yàn)檫m當(dāng)?shù)南∈杓s束有利于算法速度的提高；而以Sinkhorn距離作為損失函數(shù)度量方法的SDNMF與DSDNMF計(jì)算十分緩慢，這兩種方法對(duì)平移噪聲有一定的魯棒性提升，結(jié)合流形圖結(jié)構(gòu)正則化也提高了算法性能，但是計(jì)算效率十分低下，其根本原因是Sinkhorn距離計(jì)算消耗極大，算法每次迭代均以分解因子的乘積與原始矩陣做距離對(duì)比，導(dǎo)致算法計(jì)算效率極低?；跉W氏距離的損失函數(shù)方法則明顯速度更優(yōu)，AGNMF算法雖然也有著不錯(cuò)的子空間學(xué)習(xí)能力，但是與SDNMF，DSDNMF算法類似，均在每次迭代中需要進(jìn)行重復(fù)的耗時(shí)計(jì)算，導(dǎo)致整體運(yùn)行速度不高，本文所提S3GNMF算法將Sinkhorn距離提取至迭代過程之外，直接對(duì)原始矩陣做縮放處理，避免了對(duì)Sinkhorn距離的反復(fù)計(jì)算，結(jié)合多流形正則與稀疏約束等，提高了算法性能的同時(shí)也提高了算法速度。

表7 各算法在不同數(shù)據(jù)集的運(yùn)算速度對(duì)比(s)

5 結(jié)論

本文基于Sinkhorn距離特征縮放結(jié)合多流形學(xué)習(xí)和半監(jiān)督稀疏非負(fù)矩陣分解，提出一種多約束非負(fù)矩陣分解算法S3GNMF。首先利用Sinkhorn距離對(duì)輸入矩陣進(jìn)行特征縮放，在充分利用縮放矩陣的流形圖結(jié)構(gòu)正則化與部分標(biāo)簽信息約束的同時(shí)，向基矩陣添加了高效的L2,1/2范數(shù)稀疏約束，并通過KKT條件推導(dǎo)出算法的乘法交叉更新規(guī)則。實(shí)驗(yàn)結(jié)果表明，S3GNMF算法不論是在標(biāo)準(zhǔn)數(shù)據(jù)集或是平移噪聲數(shù)據(jù)集上，都取得了十分優(yōu)秀的子空間學(xué)習(xí)結(jié)果，具有良好的魯棒性，相比于SDNMF與DSDNMF算法，其在大幅度提高算法速度的同時(shí)，也提升了算法的性能。但本算法在運(yùn)算速度上仍有優(yōu)化空間，相較于其他單約束NMF算法，不僅運(yùn)算復(fù)雜度更高且運(yùn)算速度更慢，所以未來將著重研究具有高性能的NMF算法，并將所提算法結(jié)合應(yīng)用在不同的領(lǐng)域[27,28]，如信息推薦、圖像標(biāo)記、網(wǎng)絡(luò)安全等。