李會(huì)榮，張 林，趙鵬軍，李 超

商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛 726000

在機(jī)器學(xué)習(xí)、模式識(shí)別等具體應(yīng)用中，人們通常會(huì)遇到高維數(shù)據(jù)，如何提取這些高維數(shù)據(jù)的潛在結(jié)構(gòu)信息，將是機(jī)器學(xué)習(xí)領(lǐng)域的一大挑戰(zhàn)。非負(fù)矩陣分解（non-negative matrix factorization，NMF）是處理高維數(shù)據(jù)最流行的技術(shù)之一，它將原始的數(shù)據(jù)矩陣分解為兩個(gè)或兩個(gè)以上低階矩陣的乘積[1-2]，目前已經(jīng)成功應(yīng)用到特征提取[3]、數(shù)據(jù)挖掘[4-5]、圖像表示[6]等領(lǐng)域中。然而，NMF只能應(yīng)用于非負(fù)的數(shù)據(jù)矩陣，同時(shí)也不能核化[7]。為了克服這些缺點(diǎn)，Xu等人提出了一種用于文檔聚類的CF（concept factorization）算法，它將每一個(gè)基向量（或概念）都表示為數(shù)據(jù)點(diǎn)的線性組合，每一個(gè)數(shù)據(jù)點(diǎn)表示為基向量的線性組合[7]。與NMF 相比，CF 不僅可以核化，而且還可以應(yīng)用到非負(fù)數(shù)據(jù)的情況，但是它并沒(méi)有考慮到數(shù)據(jù)的流形結(jié)構(gòu)或者稀疏性等特征。為此，研究者針對(duì)CF提出了多種改進(jìn)的算法。例如：Cai等人將圖正則化融入到CF 中提出了一種局部一致的概念分解（locally consistent concept factorization，LCCF）算法[8]，有效提取了數(shù)據(jù)的局部幾何結(jié)構(gòu)信息。Liu 等人提出了一種局部坐標(biāo)的概念分解（local coordinate concept factorization，LCF）算法[9]，利用局部坐標(biāo)約束學(xué)習(xí)了數(shù)據(jù)的稀疏性。Li等人利用局部坐標(biāo)和圖正則化提出了一種帶有局部坐標(biāo)的圖正則化的概念分解（graphregularized CF with local coordinate，LGCF）算法[10],它不僅使得學(xué)習(xí)的系數(shù)更稀疏，而且有效維持了數(shù)據(jù)空間的幾何結(jié)構(gòu)。

然而前面提到的算法都是無(wú)監(jiān)督的學(xué)習(xí)方法，它們不能利用數(shù)據(jù)有效的標(biāo)簽信息。研究者發(fā)現(xiàn)，當(dāng)利用少量的標(biāo)簽數(shù)據(jù)結(jié)合大量的無(wú)標(biāo)簽數(shù)據(jù)，能夠大大提高機(jī)器學(xué)習(xí)算法的性能[11-16]。近年來(lái)也提出一些將數(shù)據(jù)的部分標(biāo)簽信息加入到CF算法中的半監(jiān)督學(xué)習(xí)方法。例如：Liu等人將標(biāo)簽約束加入到CF算法中，提出了約束概念分解（constrained concept factorization，CCF）算法[17]，CCF可以保證擁有同類標(biāo)簽的數(shù)據(jù)在低維表示空間中擁有相同的概念；Li等人同時(shí)考慮數(shù)據(jù)的標(biāo)簽信息和局部流形正則化，提出了一種半監(jiān)督圖正則化識(shí)別的概念分解（graph-based discriminative concept factorization，GDCF）算法[18]，它可以將同類的數(shù)據(jù)點(diǎn)在新的表示空間中盡可能地接近或者位于同一軸線上，提高了GDCF算法的識(shí)別能力。

考慮到有限的標(biāo)簽信息和局部坐標(biāo)約束，提出了一種帶有局部坐標(biāo)約束的半監(jiān)督的概念分解（semisupervised CF with local coordinate constraint，SLCF）算法。SLCF 利用局部坐標(biāo)約束使得學(xué)習(xí)的系數(shù)更稀疏，利用標(biāo)簽信息增強(qiáng)了數(shù)據(jù)不同類之間的識(shí)別能力。利用輔助函數(shù)證明了SLCF算法的收斂性，并在多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，表明SLCF算法具有比較好的聚類性能。

1 基本NMF和CF算法

給定一個(gè)非負(fù)的數(shù)據(jù)矩陣X=[x1,x2,…,xn]∈Rm×n，其中每個(gè)數(shù)據(jù)點(diǎn)xi為一個(gè)m維的向量?；镜腘MF算法就是尋找兩個(gè)非負(fù)低秩數(shù)據(jù)矩陣U∈Rm×k，V∈Rn×k，使得X≈UVT，其中k≤min{m,n}。通常，利用歐式距離來(lái)衡量這種近似程度，因此NMF 算法可以轉(zhuǎn)化為求解如下的優(yōu)化問(wèn)題[1-2]：

其中，U稱為基矩陣，V稱為系數(shù)矩陣。

在CF算法中，將NMF算法中的基向量uj（基矩陣U的第j列）表示為每個(gè)數(shù)據(jù)點(diǎn)xi的線性組合，即，其中wij≥0,令W=[wij]∈Rn×k，則CF 算法將數(shù)據(jù)矩陣X分解為如下形式：

利用歐氏距離來(lái)度量這種近似程度，因此CF 算法求解如下的優(yōu)化問(wèn)題：

由于目標(biāo)函數(shù)對(duì)于W或者V是凸的，但是同時(shí)對(duì)W和V是非凸的，因此很難求解優(yōu)化問(wèn)題（3）的全局最優(yōu)解。Xu等人提出了利用乘性迭代方法得到優(yōu)化問(wèn)題（3）局部最優(yōu)解如下[7]：

其中，K=XXT。

2 帶有局部坐標(biāo)的半監(jiān)督概念分解（SLCF）算法

由于CF 算法不能利用有限的標(biāo)簽信息，為一個(gè)無(wú)監(jiān)督的學(xué)習(xí)方法，同時(shí)也不能保證學(xué)習(xí)系數(shù)矩陣具有稀疏性。為了更好利用數(shù)據(jù)的有限的標(biāo)簽信息和稀疏性，提出了一種帶有局部坐標(biāo)約束的半監(jiān)督的概念分解（SLCF）算法。

2.1 標(biāo)簽約束矩陣

為了利用有效的標(biāo)簽信息，Liu等人利用標(biāo)簽約束矩陣A，提出了一種約束的概念分解算法[17]。假設(shè)數(shù)據(jù)集X有c類，前l(fā)個(gè)數(shù)據(jù)點(diǎn)x1,x2,…,xl是有標(biāo)簽的，且屬于c類中的某一類，余下的n-l個(gè)數(shù)據(jù)點(diǎn)xl+1,xl+2,…,xn是未知標(biāo)簽的，指示矩陣B∈Rl×c定義如下：

結(jié)合無(wú)標(biāo)簽的數(shù)據(jù)點(diǎn)，定義標(biāo)簽約束矩陣A∈Rn×(c+n-l)如下[15]：

其中，In-l為(n-l)×(n-l)的單位矩陣。標(biāo)簽約束矩陣A能夠保證同類標(biāo)簽的數(shù)據(jù)點(diǎn)映射到低維表示空間中擁有相同的標(biāo)簽。引入輔助矩陣Z，使得V=AZ，就可以將CF算法推廣到半監(jiān)督的學(xué)習(xí)方法，即數(shù)據(jù)矩陣X可以表示為：

2.2 局部坐標(biāo)約束

為了學(xué)習(xí)稀疏系數(shù)，劉海峰等人引入局部坐標(biāo)約束，提出了一種局部坐標(biāo)的概念分解（local-coordinate CF，LCF）算法[9]。首先，引入坐標(biāo)編碼的定義[19]：

定義1一個(gè)坐標(biāo)編碼就是一對(duì)(γ,C)，其中C∈RD是一個(gè)錨點(diǎn)集，γ是一個(gè)錨點(diǎn)x∈RD到[γv(x)]v∈C∈R|C|的映射，并且滿足于是，在RD中的x有γ(x)=∑v∈Cγv(x)v。

其中，ak表示標(biāo)簽約束矩陣A的第k行，zi表示輔助矩陣Z的第i列。

2.3 提出的SLCF算法

標(biāo)簽信息可以提高CF 算法的聚類性能，局部坐標(biāo)約束R1可以使CF學(xué)習(xí)的系數(shù)矩陣更稀疏，因此將有限的標(biāo)簽信息和局部坐標(biāo)約束R1融入到CF 算法中，提出了一種半監(jiān)督的帶有局部坐標(biāo)的概念分解（SLCF）算法，即求解如下優(yōu)化問(wèn)題：

其中，α>0 為平衡參數(shù)，主要衡量局部坐標(biāo)約束項(xiàng)的影響程度。

很顯然，SLCF算法的目標(biāo)函數(shù)關(guān)于變量W和V是非凸的，很難求它的全局最優(yōu)解?？梢岳贸俗痈乱?guī)則[20]迭代優(yōu)化問(wèn)題（9），可以得到SLCF算法的迭代更新規(guī)則。

首先，將優(yōu)化問(wèn)題式（9）的目標(biāo)函數(shù)可以表示為：

其中，Ci=diag(|aiz1|,|aiz2|,…,|aizk|)∈Rk×k，diag(v)表示由向量v構(gòu)成的對(duì)角矩陣，1 表示元素全為1 的k×1的向量。利用矩陣的性質(zhì)，可以得到：

其中，K=XTX。假設(shè)φik、ψjk分別為wik≥0,zjk≥0的拉格朗日乘子，令Φ=[φik]，Ψ=[ψjk]，則優(yōu)化問(wèn)題（9）的拉格朗日函數(shù)L為：

令e=diag(K)∈Rn，f=diag(WTKW)∈Rk，定義E=(e,e,…,e)∈Rn×k，F(xiàn)=(f,f,…,f)T∈Rn×k，則拉格朗日函數(shù)L關(guān)于矩陣變量W和Z的偏導(dǎo)數(shù)分別為：

利用Kuhn-Tucher條件φikwik=0，ψjkzjk=0，有：

從優(yōu)化問(wèn)題（9）中可以看出，當(dāng)α=0 時(shí)，SLCF算法就為CCF算法。

2.4 計(jì)算復(fù)雜度分析

為了精確分析SLCF 算法的復(fù)雜度，計(jì)算SLCF算法更新規(guī)則每次迭代過(guò)程中加法、乘法、除法運(yùn)算的個(gè)數(shù)，并與CF和NMF進(jìn)行比較，結(jié)果如表1所示，其中n表示數(shù)據(jù)點(diǎn)的個(gè)數(shù)，m表示數(shù)據(jù)的維數(shù)，k表示特征因子的維數(shù)，k≤min{m,n}。

對(duì)于局部坐標(biāo)約束，與CF算法相比，每次迭代中SLCF 算法比CF 算法多2n2k+2nk2次加法與乘法運(yùn)算。對(duì)于SLCF算法，由于約束標(biāo)簽矩陣A的每行只有一個(gè)非零元素1，因此在計(jì)算矩陣AZ時(shí)不需要額外的加法與乘法運(yùn)算，但在計(jì)算ATB（B∈Rn×k）時(shí)只需nk次加法運(yùn)算。在CF、SLCF算法中，計(jì)算核矩陣K需要n2m次加法與乘法運(yùn)算。因此由表1 可以看出，每次迭代過(guò)程中SLCF、CF 算法總的計(jì)算復(fù)雜度都為O(n2k+n2m)。

3 SLCF算法收斂性證明

關(guān)于SLCF 算法的迭代更新規(guī)則（14）、（15），下面定理從理論上保證了SLCF算法的收斂性。

定理1優(yōu)化問(wèn)題（9）的目標(biāo)函數(shù)O在迭代更新規(guī)則（14）、（15）下是非增的。目標(biāo)函數(shù)O在迭代更新規(guī)則（14）、（15）下是不變的當(dāng)且僅當(dāng)W和Z是一個(gè)穩(wěn)定點(diǎn)。

為了證明收斂性定理，給出以下引理：

引理1如果存在F(x)的輔助函數(shù)G(x,x′)滿足G(x,x′)≥F(x)，且G(x,x)=F(x)，則F(x)在以下更新規(guī)則下是非增的[21]：

證明

現(xiàn)在，證明關(guān)于變量W的迭代更新規(guī)則式（14）正是某一合適的輔助函數(shù)在更新規(guī)則（16）下可得。令矩陣W中任意元素用wab表示，F(xiàn)ab表示式（9）中的目標(biāo)函數(shù)O僅與wab有關(guān)。目標(biāo)函數(shù)O關(guān)于變量wab的一階、二階導(dǎo)數(shù)分別為：

Table 1 Computational operation counts for each iteration in NMF,CF and SLCF表1 在NMF、CF、SLCF中每次迭代運(yùn)算的個(gè)數(shù)

令Hab表示式（9）中的目標(biāo)函數(shù)O僅與zab有關(guān)，計(jì)算目標(biāo)函數(shù)O關(guān)于變量zab的一階、二階導(dǎo)數(shù)分別為：

由于式（19）、式（26）分別為Fab、Hab的輔助函數(shù)，因此Fab、Hab在更新規(guī)則式（14）、式（15）下是非增的。因此優(yōu)化問(wèn)題式（9）中的目標(biāo)函數(shù)O在迭代更新規(guī)則（14）、（15）下是非增的。定理1得證。

4 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證SLCF算法的有效性，將在COIL20、YaleB、MNIST數(shù)據(jù)庫(kù)上進(jìn)行實(shí)驗(yàn)，并與K-means、NMF[2]、CF[8]、局部坐標(biāo)的概念分解（LCF）[9]、約束概念分解算法（CCF）[15]以及非負(fù)局部坐標(biāo)分解算法（non-negative local coordinate fact-orization，NLCF）[22]進(jìn)行比較。

從每個(gè)數(shù)據(jù)庫(kù)中隨機(jī)選擇P（P從2到10）類樣本，同時(shí)在這P類樣本構(gòu)成的數(shù)據(jù)子集X上進(jìn)行實(shí)驗(yàn)。設(shè)置新表示空間的維數(shù)等于數(shù)據(jù)類別的個(gè)數(shù)P，并利用K-means 算法對(duì)系數(shù)表示矩陣V進(jìn)行聚類，在每次實(shí)驗(yàn)中K-means 重復(fù)20 次并記錄最好結(jié)果。在半監(jiān)督學(xué)習(xí)算法CCF、SLCF 中，從每類樣本中隨機(jī)選擇20%樣本作為已知的標(biāo)簽信息，并用它構(gòu)造標(biāo)簽約束矩陣A。在NMF、CF、NLCF、LCF、CCF、SLCF 中，最大迭代次數(shù)T=200，參數(shù)α將在后面討論，對(duì)于每一個(gè)給定的聚類數(shù)P，每個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行20次并計(jì)算平均聚類結(jié)果。采用聚類精度（accuracy，AC）和歸一化互信息（normalized mutual information，NMI）來(lái)評(píng)價(jià)聚類性能[22-23]。

4.1 在COIL20數(shù)據(jù)集上的實(shí)驗(yàn)

COIL20圖像數(shù)據(jù)集包含20類共1 440張灰色圖像，每張圖像裁剪成32×32 像素，表示為1 024維的向量。在COIL20數(shù)據(jù)庫(kù)上實(shí)驗(yàn)結(jié)果如表2、表3所示。

Table 2 Clustering AC performance on COIL20 database表2 在COIL20數(shù)據(jù)集的AC聚類性能%

Table 3 Clustering NMI performance on COIL20 database表3 在COIL20數(shù)據(jù)集的NMI聚類性能%

從表2、表3 中可以看出，不論從平均聚類精度，還是從平均的歸一化互信息來(lái)看，提出的SLCF算法的性能優(yōu)于其他比較的方法。與CF 和LCF 算法相比，SLCF 在平均聚類精度AC 上分別提高了6.16 個(gè)百分點(diǎn)、5.86個(gè)百分點(diǎn)，在NMI上分別提高了5.74個(gè)百分點(diǎn)、6.26個(gè)百分點(diǎn)。因此SLCF算法的平均聚類性能優(yōu)于CF、LCF 方法，主要由于SLCF 算法考慮了數(shù)據(jù)有效的標(biāo)簽信息和局部坐標(biāo)約束，進(jìn)一步提高了算法的聚類性能。

4.2 在YaleB數(shù)據(jù)集上的實(shí)驗(yàn)

Yale B包含有38個(gè)人在不同燈光變化下獲取的2 414 張人臉圖像，每個(gè)人大約有59～64 張圖像。在本實(shí)驗(yàn)中，每類隨機(jī)選擇50張圖像進(jìn)行實(shí)驗(yàn)，并且每張圖像裁剪成像素，實(shí)驗(yàn)結(jié)果如表4、表5所示。

Table 4 Clustering AC performance on Yale B database表4 在Yale B人臉數(shù)據(jù)集的AC聚類性能%

Table 5 Clustering NMI performance on Yale B database表5 在Yale B人臉數(shù)據(jù)集NMI聚類性能 %

從表4、表5中可以看出，CCF算法的聚類性能優(yōu)于K-means、NMF、CF、NLCF及LCF方法。主要由于CCF為半監(jiān)督學(xué)習(xí)方法，而K-means、NMF、CF、NLCF、LCF這5種算法均為無(wú)監(jiān)督的學(xué)習(xí)方法，沒(méi)有充分利用有效的標(biāo)簽信息。與CCF算法相比，SLCF在平均聚類精度AC上提高了0.39個(gè)百分點(diǎn)，在NMI上提高了0.17 個(gè)百分點(diǎn)，從而表明局部坐標(biāo)約束能夠提高算法的聚類性能。

4.3 在MNIST數(shù)據(jù)集上的實(shí)驗(yàn)

手寫體MNIST數(shù)據(jù)集包含有60 000張圖像的訓(xùn)練集和10 000張圖像的測(cè)試集。圖像分別為數(shù)字0～9共有10類，每張圖像裁剪成28×28 像素。從前10 000個(gè)訓(xùn)練集中每類隨機(jī)選擇100 張圖像組成的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表6、表7所示。

Table 6 Clustering AC performance on MNIST database表6 在MNIST數(shù)據(jù)集的AC聚類性能%

由表6、表7 可以看出，提出的SLCF 算法在不同的聚類數(shù)下的算法聚類性能優(yōu)于其他比較的算法。具體來(lái)說(shuō)，與NMF 算法相比，NLCF 在AC 上提高了2.85個(gè)百分點(diǎn)，在NMI上提高了1.86個(gè)百分點(diǎn)，主要由于NLCF 利用局部坐標(biāo)約束提取了數(shù)據(jù)的稀疏性。與NLCF相比，SLCF算法在AC上提高了7.84個(gè)百分點(diǎn)，在NMI 上提高了8.37 個(gè)百分點(diǎn)，因?yàn)镾LCF算法不僅考慮了數(shù)據(jù)的稀疏性，還有效地利用數(shù)據(jù)的部分標(biāo)簽信息，進(jìn)一步提高了算法的聚類性能。

Table 7 Clustering NMI performance on MNIST database表7 在MNIST數(shù)據(jù)集的NMI聚類性能%

4.4 參數(shù)分析

下面討論一下SLCF 算法中參數(shù)α對(duì)算法性能的影響情況。分別從COIL20、Yale B、MNIST數(shù)據(jù)庫(kù)中隨機(jī)選取5類所構(gòu)成的數(shù)據(jù)子集X進(jìn)行實(shí)驗(yàn)，且在Yale B 數(shù)據(jù)庫(kù)中每類選取50 張圖像，在MNIST 數(shù)據(jù)集中每類選取100 張圖像。每個(gè)實(shí)驗(yàn)在選取不同的聚類數(shù)上獨(dú)立運(yùn)行10次，參數(shù)α分別從[10-3,10-2,10-1,100,101,102,103,104]變化的平均聚類性能結(jié)果如圖1所示。從圖1 中可以得到在本實(shí)驗(yàn)中NLCF、LCF 及SLCF 算法在不同數(shù)據(jù)庫(kù)中參數(shù)α設(shè)置情況，如表8所示。由于算法K-means、NMF、CF以及CCF中沒(méi)有任何參數(shù)，因此算法的性能并沒(méi)有改變。

Fig.1 Clustering performance comparison with parameter α圖1 參數(shù)α 變化的聚類性能比較圖

Table 8 Parameter α in NLCF,LCF and SLCF表8 算法NLCF、LCF及SLCF中參數(shù)α 設(shè)置

提出的SLCF算法也是一個(gè)半監(jiān)督學(xué)習(xí)方法，標(biāo)簽數(shù)據(jù)的比例與算法的性能具有密切的關(guān)系。為了討論有標(biāo)簽數(shù)據(jù)的比例對(duì)算法性能的影響程度，隨機(jī)選擇每類有標(biāo)簽數(shù)據(jù)的比例分別從10%到80%的變化，每次實(shí)驗(yàn)獨(dú)立運(yùn)行10次，在不同的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖2所示。從圖2中可以看出，半監(jiān)督學(xué)習(xí)算法CCF 和SLCF 算法隨著有標(biāo)簽數(shù)據(jù)的比例增加算法的聚類性能逐漸提高。

4.5 收斂性分析

利用輔助函數(shù)法從理論上證明了SLCF 算法的收斂性。為了分析SLCF算法迭代更新的有效性，分別比較了CF、CCF 以及SLCF 算法在數(shù)據(jù)集上的收斂情況，比較結(jié)果如圖3所示。

Fig.2 Effect of the number of labeled data on performance圖2 有標(biāo)簽數(shù)據(jù)的比例對(duì)算法性能的影響

Fig.3 Convergence curves of CF,CCF and SLCF on 3 databases圖3 CF、CCF、SLCF在3個(gè)數(shù)據(jù)集上的收斂曲線

從圖3 中可以看出，不論從收斂速度上，還是精度上，SLCF 算法優(yōu)于CF、CCF 算法，因此SLCF 算法的迭代更新過(guò)程是有效的。

5 結(jié)論

針對(duì)傳統(tǒng)的概念分解算法不能利用有效的標(biāo)簽信息，也不能提取數(shù)據(jù)空間的稀疏性問(wèn)題，本文將有限的標(biāo)簽信息和局部坐標(biāo)約束融入到CF中，提出了一種帶有局部坐標(biāo)約束的半監(jiān)督的概念分解（SLCF）算法。同時(shí)給出了SLCF算法的迭代更新規(guī)則，從理論上也證明了SLCF 算法的收斂性，在COIL20、Yale B 以及MNIST 數(shù)據(jù)庫(kù)上實(shí)驗(yàn)表明提出的SLCF 算法是有效的。