李向利，張 穎

1.桂林電子科技大學 數(shù)學與計算科學學院，廣西 桂林 541004

2.廣西密碼學與信息安全重點實驗室，廣西 桂林 541004

3.廣西自動檢測技術(shù)與儀器重點實驗室，廣西 桂林 541004

4.廣西高校數(shù)據(jù)分析與計算重點實驗室，廣西 桂林 541004

1 引言

隨著信息技術(shù)的發(fā)展，在許多實際的應(yīng)用如模式識別、計算機視覺中，需要處理的數(shù)據(jù)通常都是高維數(shù)據(jù)。這可能導致“維數(shù)災(zāi)難”，給數(shù)據(jù)處理帶來很大的挑戰(zhàn)。為了解決這個問題，研究者們提出了很多降維方法，例如主成分分析（principal component analysis，PCA）[1]、線性判別分析（linear discriminant analysis，LDA）[2]、奇異值分解（singular value decomposition，SVD）[3]和非負矩陣分解（nonnegative matrix factorization，NMF）[4]。目前，最流行的降維方法是NMF。NMF 將非負的數(shù)據(jù)矩陣分解成兩個非負的因子矩陣的乘積，其中一個稱為基矩陣，一個稱為系數(shù)矩陣（也稱為低維的表示矩陣）。由于非負約束的存在，NMF 只允許使用加法運算進行線性組合，這使得NMF 的分解結(jié)果是基于部分表示的。從心理學和生理學角度來說，NMF 的分解結(jié)果是符合人類局部相加構(gòu)成整體這一認知的，具有較強的解釋性。

非負矩陣分解不僅是一種有效的降維方法，而且在圖像聚類上有廣泛的應(yīng)用，這是因為NMF 的目標函數(shù)可以從聚類的角度解釋，并且在文獻[5-6]中已經(jīng)證明非負矩陣分解與許多聚類算法如K-means、核K-means 以及譜聚類算法有一定的等價性。最初的NMF是由Lee等人[4]于1999年提出的，并在文獻[7]中給出了原始模型的迭代規(guī)則?；跇藴实腘MF，很多學者提出了改進的版本，例如Cai等人[8]提出了圖正則非負矩陣分解（graph regularized NMF，GNMF）。但是，初始版本的NMF 以及GNMF 存在一些不足，它們都是無監(jiān)督的方法，沒有使用有標簽數(shù)據(jù)的標簽信息。然而，在大部分實際應(yīng)用中獲得的實驗數(shù)據(jù)通常都會有一部分數(shù)據(jù)已知標簽信息。充分使用這些已知的標簽信息能夠顯著地提高聚類效果。為此，學者們在NMF 模型上加入標簽約束，提出半監(jiān)督的NMF，例如判別非負矩陣分解（discriminative NMF，DNMF）[9]。然而，單純的半監(jiān)督方法只使用了數(shù)據(jù)的標簽信息，并不能捕獲數(shù)據(jù)固有的幾何結(jié)構(gòu)信息。

上述的NMF 方法都是線性的方法，只能夠處理線性分布的數(shù)據(jù)，不能夠很好地處理數(shù)據(jù)是非線性的情況。常用的解決非線性分布數(shù)據(jù)的方法是核方法，這種方法也是一種經(jīng)常使用的非線性特征提取方法。核方法的基本思路是先尋找一個從原始數(shù)據(jù)空間到一個高維核空間的非線性映射，使得數(shù)據(jù)在映射之后是線性可分離的，然后在這個核空間中運行一般的線性方法，例如NMF 等。由此可以拓展出許多的基于核方法的算法，比如核主成分分析（kernel PCA，KPCA）[10]、核線性判別分析（kernel LDA，LDA）[11]以及核非負矩陣分解（kernel NMF，KNMF）[12]。但是，KNMF 既沒有保存數(shù)據(jù)的幾何結(jié)構(gòu)信息，也不是一種半監(jiān)督的方法，沒有充分使用標簽信息，因此聚類效果也受到限制。

為此，受核方法以及基于圖的判別非負矩陣分解的啟發(fā)，本文提出基于核的判別圖正則非負矩陣分解（discriminative and graph regularized nonnegative matrix factorization with kernel method，KGDNMF）。該方法是一種半監(jiān)督的方法，通過部分有標簽數(shù)據(jù)的標簽構(gòu)造標簽矩陣，使得具有相同標簽的數(shù)據(jù)分解后的表示對準同一個軸。能夠充分地使用標簽信息，利用標簽信息引導無標簽數(shù)據(jù)聚類，相比無監(jiān)督方法有更好的聚類效果。該方法在NMF 的框架上加入了圖正則項，能夠探索數(shù)據(jù)固有的幾何結(jié)構(gòu)，克服了原始NMF 忽略數(shù)據(jù)流形結(jié)構(gòu)的問題。同時，該方法結(jié)合了核方法，能夠處理一般NMF 處理不了的非線性分布數(shù)據(jù)，提高了聚類效果。

2 相關(guān)工作和預(yù)備知識

基于Lee 等人[4]提出的標準的NMF，很多學者提出了改進的NMF，在標準的NMF 的框架中增加一些有必要的約束，提高分解數(shù)據(jù)的聚類效果。Ding 等人[13]提出了凸非負矩陣分解（convex NMF，CNMF）。CNMF 通過使用原始數(shù)據(jù)的非負線性組合來表示基矩陣，使得所得到的基矩陣更能體現(xiàn)作為一個聚類的中心的性質(zhì)。同時，這樣得到的系數(shù)矩陣相比標準的NMF 更加稀疏。為了得到更加稀疏的結(jié)果，Hoyer[14]提出了非負稀疏編碼（non-negative sparse coding，NNSC），該方法通過對編碼矩陣加上l1范數(shù)約束來增強分解結(jié)果的稀疏性，提高了聚類效果。Cai等人[8]提出了圖正則非負矩陣分解（GNMF），通過構(gòu)造數(shù)據(jù)的圖拉普拉斯矩陣來探索數(shù)據(jù)固有的幾何結(jié)構(gòu)，顯著提升了聚類性能。文獻[15]和文獻[9]分別提出了兩種判別非負矩陣分解（DNMF）。文獻[15]通過將LDA 整合到NMF 框架中，來捕獲數(shù)據(jù)的判別信息。而文獻[9]則通過構(gòu)造標簽矩陣，使得有相同標簽的數(shù)據(jù)分解后的表示（系數(shù)矩陣）對準同一個軸。顯然DNMF 是一種半監(jiān)督的聚類方法，需要使用部分已知標簽數(shù)據(jù)的標簽信息。Li 等人[16]在DNMF 的框架中加入圖正則項提出基于圖的判別非負矩陣分解。Wang 等人[17]提出最大最小距離非負矩陣分解（max-min distance NMF，MMDNMF），最小化最大類內(nèi)距離，最大化最小類間距離來捕獲判別信息，提高聚類效果。文獻[18]針對樣本具有的先驗信息是成對關(guān)系約束的情況，提出了一個相對成對關(guān)系約束非負矩陣分解（relative pairwise relationship constrained NMF，RPR-NMF），通過對相對成對關(guān)系的數(shù)據(jù)之間的距離進行懲罰，使得數(shù)據(jù)點分解后與原始數(shù)據(jù)保持相似的相對關(guān)系。Peng 等人[19]提出了一個基于超平面的非負矩陣分解，該方法為每個類構(gòu)造一個超平面，使得有標簽的數(shù)據(jù)點靠近對應(yīng)的超平面。

上述的NMF 變體都是針對數(shù)據(jù)是線性分布的情況的。針對數(shù)據(jù)非線性分布的情況，文獻[20]和文獻[21]將核方法與NMF 結(jié)合提出了核非負矩陣分解。使用核方法可以采取的核函數(shù)也是多種多樣的。在文獻[20]中，采用的核函數(shù)是多項式核函數(shù)，文獻[21]則將多項式核函數(shù)拓展為分數(shù)階內(nèi)積核。

下面將給出本文的相關(guān)預(yù)備知識。

2.1 非負矩陣分解

給出非負數(shù)據(jù)矩陣X=[x1，x2，…，xn]∈Rm×n，其中xi∈Rm表示一個數(shù)據(jù)。標準的NMF 模型是將數(shù)據(jù)矩陣X分解成一個非負的基矩陣U∈Rm×k和一個非負的系數(shù)矩陣V∈Rn×k的乘積，這里k是降維的維數(shù)。為了找到近似的X≈UVT，文獻[4]給出了兩種損失函數(shù)，分別是采用歐氏距離的平方和廣義的Kullback-Leibler 散度。一般的，采用歐氏距離的平方作為損失函數(shù)可以構(gòu)造如下的優(yōu)化問題：

其中，||?||F表示矩陣的Frobenius范數(shù)。

顯然，優(yōu)化問題（1）是非凸的，求解這個問題的全局最優(yōu)解是非常困難的。然而，當固定兩個變量中的一個去求解另一個最優(yōu)解就是一個凸優(yōu)化問題。因此，文獻[7]提出了一種交替迭代兩個變量的乘性迭代規(guī)則。

2.2 圖正則非負矩陣分解

基于標準的NMF，Cai 等人[8]提出了圖正則非負矩陣分解（GNMF）。假設(shè)X表示數(shù)據(jù)矩陣，每一列表示一個數(shù)據(jù)。如果在原始的高維數(shù)據(jù)空間中，數(shù)據(jù)點xi和xj相距比較近，那么在降維之后的空間中，新的數(shù)據(jù)表示vi和vj也應(yīng)該相距很近。構(gòu)造一個權(quán)重矩陣W來度量兩個數(shù)據(jù)點之間的相似性，通常使用的0-1 度量定義如下：

通常使用歐氏距離來測量數(shù)據(jù)點之間的距離，則有：

2.3 判別非負矩陣分解

2.4 核非負矩陣分解

3 帶核方法的判別圖正則非負矩陣分解

3.1 算法

在NMF 標準模型（1）中，系數(shù)矩陣V給出了原始高維數(shù)據(jù)矩陣X基于部分的降維表示。但是這個模型并未給出數(shù)據(jù)固有的幾何結(jié)構(gòu)和判別信息，并且該模型只能夠處理線性可分離的數(shù)據(jù)。GNMF[8]能夠很好地描述數(shù)據(jù)空間的幾何結(jié)構(gòu)，DNMF[9]能夠使用部分有標簽數(shù)據(jù)給出判別信息，而核方法能夠處理非線性的情況。結(jié)合這三種方法到NMF 中，可以得到本文提出的帶核方法的判別圖正則非負矩陣分解（KGDNMF）。

模型中φ是從原始數(shù)據(jù)空間到核空間的映射，核函數(shù)采用多項式核。Q是根據(jù)式（5）構(gòu)造的標簽矩陣，有標簽的數(shù)據(jù)個數(shù)為p。Vl是V無標簽數(shù)據(jù)對應(yīng)部分全部取0。L=D-W是Laplace 矩陣，其中Dii=∑jWij，W是相似度權(quán)重。關(guān)于權(quán)重選擇有熱核權(quán)重、0-1 權(quán)重、內(nèi)積權(quán)重等，本文選擇0-1 權(quán)重。α＞0 和β＞0 是各個正則項的平衡參數(shù)。

一般NMF 采取交替迭代更新的方法進行求解，而迭代更新初始的U和V是隨機給出的，這個隨機性會影響實驗的結(jié)果。為了解決這個問題，本文采用了一種“熱啟動”的策略[22]。首先對數(shù)據(jù)進行一次K-means 聚類，得到一組聚類中心，然后將這些聚類中心作為初始的基矩陣U0。為此，在優(yōu)化問題（13）上加上正則項?？梢缘玫剑?/p>

顯然，優(yōu)化問題同時求解U、V和A是非凸的，但是分別求解是凸的。因此，采用交替更新迭代的方式求解。目標函數(shù)可以展開為：

3.2 收斂性證明

根據(jù)上面提出的交替迭代更新算法，有如下的定理。

定理1優(yōu)化問題（14）在迭代更新公式（17）～（19）下是非增加的。當且僅當U、V和A到達一個穩(wěn)定點時目標函數(shù)值不變。

下面將證明定理和文獻[16]相似，本文引入輔助函數(shù)證明V在更新規(guī)則下的收斂性，U的收斂性也可以相似證明。關(guān)于輔助函數(shù)有如下引理成立。

引理1對函數(shù)F（x） 存在輔助函數(shù)G（x，x′） 滿足G（x，x′）≥F（x）且G（x，x）=F（x），那么F（x）在如下的更新規(guī)則下時非增加的：

下面證明對每一個vab，都是按照式（20）的規(guī)則更新的。

引理2假設(shè)F′表示對變量V的一階導數(shù)，那么函數(shù)（23）是Fvab的輔助函數(shù)。

綜合式（26）～式（28），不等式（25）成立。因此式（23）定義的函數(shù)是Fvab的輔助函數(shù)。

輔助函數(shù)（23）在更新規(guī)則式（20）下得到的迭代公式正是關(guān)于V的迭代公式。因此定理關(guān)于V成立。關(guān)于U的部分可以類似證明。由于優(yōu)化問題關(guān)于A是無約束的凸優(yōu)化問題，更新公式是直接求解直接得到的，因此關(guān)于A也是收斂的。故定理是成立的。

4 實驗與分析

本章中，將本文提出的算法在COIL20、MNIST和Yale 人臉數(shù)據(jù)集3 個圖片數(shù)據(jù)集上運行，并與Kmeans、NMF、GNMF、DNMF、GDNMF（discriminative nonnegative matrix factorization）進行比較。為了能夠更好地驗證算法的性能，首先從數(shù)據(jù)集中隨機選擇k類數(shù)據(jù)，對每個選出的數(shù)據(jù)子集重復10 次實驗，并計算平均聚類性能。對于半監(jiān)督聚類算法（DNMF、GDNMF 和KGDNMF），從每一類中隨機選擇20%作為有標簽數(shù)據(jù)。對于降維算法，降維維數(shù)采用聚類數(shù)目，然后對降維后新的數(shù)據(jù)表示使用K-means 進行聚類。每次實驗中K-means 進行20 次，取最好的結(jié)果。對于實驗效果，使用準確率（accuracy，ACC）和互信息（mutual information，MI）作為評價指標，ACC 和MI的計算方法參考文獻[8]。

4.1 參數(shù)選擇

本文提出的算法有3 個平衡參數(shù)，α、β和γ。下面將從實驗分析參數(shù)對聚類結(jié)果的影響并選擇最優(yōu)參數(shù)。對COIL20，選擇20 個類進行實驗；對MNIST 選擇10 個類，每類選擇2 000 個圖片進行實驗；對于Yale 人臉數(shù)據(jù)集，使用所有數(shù)據(jù)進行實驗。重復10次實驗，然后取平均值。具體實驗結(jié)果見圖1～圖3。從圖中可以看出，在COIL20 數(shù)據(jù)集上，選擇參數(shù)α=100.0，β=0.1，γ=100.0 ；在MNIST 數(shù)據(jù)集上，選擇參數(shù)α=100.0，β=5.0，γ=0.2 ；在Yale 人臉數(shù)據(jù)集上，選擇參數(shù)α=20.0，β=20.0，γ=5.0。

Fig.1 Influence of parameter α on experimental results圖1 參數(shù)α 對實驗結(jié)果的影響

Fig.2 Influence of parameter β on experimental results圖2 參數(shù)β 對實驗結(jié)果的影響

Fig.3 Influence of parameter γ on experimental results圖3 參數(shù)γ 對實驗結(jié)果的影響

4.2 COIL20 數(shù)據(jù)集實驗結(jié)果

COIL20 數(shù)據(jù)集包含20 個物體的總共1 440 張圖片，每個物體72 張。將每張圖片處理成32×32 像素大小。所有的實驗結(jié)果展示在表1中。相比GDNMF，KGDNMF在ACC和MI上平均分別有0.044 0和0.025 8的提高。相比GNMF 和DNMF，KGDNMF 在ACC 上平均分別有0.053 8 和0.137 5 的提高，在MI上分別有0.032 5 和0.165 7 的提高。對比實驗結(jié)果可以發(fā)現(xiàn)KGDNMF 相比其他幾種方法，在聚類結(jié)果的準確率（ACC）和互信息（MI）上均有所提高。

4.3 MNIST 數(shù)據(jù)集實驗結(jié)果

MNIST 是手寫數(shù)字圖片數(shù)據(jù)集，包含手寫數(shù)字0～9 訓練樣本60 000 張，測試樣本10 000 張。本次實驗，從訓練樣本中每類選擇200 張作為實驗數(shù)據(jù)集，每張圖片處理成28×28 像素大小。實驗結(jié)果展示在表2 中。對比實驗結(jié)果可以發(fā)現(xiàn)，KGDNMF 相比其他方法，在ACC 和MI 兩個指標上都有提高。與GDNMF 相比，在聚類類數(shù)較少時，聚類效果提升不多，但是隨著聚類數(shù)目增加，KGDNMF 表現(xiàn)越優(yōu)越。相比GNMF 和DNMF，KGDNMF 在ACC 上平均分別有0.167 8 和0.241 4 的提高，在MI 上分別有0.166 6和0.442 8 的提高。

Table 1 Experimental results on COIL20 dataset表1 COIL20 數(shù)據(jù)集實驗結(jié)果

Table 2 Experimental results on MNIST dataset表2 MNIST 數(shù)據(jù)集實驗結(jié)果

4.4 Yale人臉數(shù)據(jù)集實驗結(jié)果

Yale是人臉圖片數(shù)據(jù)集，包含40個人不同表情光照下的圖片共400 張，每個人10 張圖片。本次實驗，每張圖片處理成32×32 像素大小。實驗結(jié)果展示在表3 中。從實驗結(jié)果可以看出，大部分情況效果最好的算法還是KGDNMF。相比KGDNMF，GDNMF 在ACC 和MI平均分別低0.017 6 和0.005 1；DNMF 在ACC 和MI上平均分別低0.414 6和0.424 5；GNMF 在ACC 和MI 上平均分別低0.155 3 和0.106 0。綜合來說還是KGDNMF 聚類效果最好。

Table 3 Experimental results on Yale face dataset表3 Yale人臉數(shù)據(jù)集實驗結(jié)果

4.5 實驗結(jié)果分析

分析上述3 個數(shù)據(jù)集的實驗結(jié)果，在大部分情況下效果最好的算法還是KGDNMF。這是由于KGDNMF 同時采用了圖正則項和核方法，還是半監(jiān)督的方法。而GDNMF 沒有采取核方法，只能處理數(shù)據(jù)是線性分布的情況；DNMF 只使用了標簽矩陣約束，無法保存數(shù)據(jù)的幾何結(jié)構(gòu)；GNMF 只加入了圖正則項，是一種無監(jiān)督的方法，對比半監(jiān)督的KGDNMF效果要差。

5 結(jié)論

本文提出了一個新的帶核方法的判別圖正則非負矩陣分解算法。這個算法結(jié)合圖正則和部分標簽信息，使用核方法對數(shù)據(jù)進行處理，并且采取了一種熱啟動的策略，提高了聚類效果。實驗結(jié)果證明了提出的算法相比現(xiàn)有的一些算法性能有所提升。