帶有局部坐標約束的半監督概念分解算法

李會榮，張 林，趙鵬軍，李 超

商洛學院數學與計算機應用學院，陜西商洛 726000

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

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

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

1 基本NMF和CF算法

給定一個非負的數據矩陣X=[x1,x2,…,xn]∈Rm×n，其中每個數據點xi為一個m維的向量。基本的NMF算法就是尋找兩個非負低秩數據矩陣U∈Rm×k，V∈Rn×k，使得X≈UVT，其中k≤min{m,n}。通常，利用歐式距離來衡量這種近似程度，因此NMF 算法可以轉化為求解如下的優化問題[1-2]：

其中，U稱為基矩陣，V稱為系數矩陣。

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

利用歐氏距離來度量這種近似程度，因此CF 算法求解如下的優化問題：

由于目標函數對于W或者V是凸的，但是同時對W和V是非凸的，因此很難求解優化問題（3）的全局最優解。Xu等人提出了利用乘性迭代方法得到優化問題（3）局部最優解如下[7]：

其中，K=XXT。

2 帶有局部坐標的半監督概念分解（SLCF）算法

由于CF 算法不能利用有限的標簽信息，為一個無監督的學習方法，同時也不能保證學習系數矩陣具有稀疏性。為了更好利用數據的有限的標簽信息和稀疏性，提出了一種帶有局部坐標約束的半監督的概念分解（SLCF）算法。

2.1 標簽約束矩陣

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

結合無標簽的數據點，定義標簽約束矩陣A∈Rn×(c+n-l)如下[15]：

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

2.2 局部坐標約束

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

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

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

2.3 提出的SLCF算法

標簽信息可以提高CF 算法的聚類性能，局部坐標約束R1可以使CF學習的系數矩陣更稀疏，因此將有限的標簽信息和局部坐標約束R1融入到CF 算法中，提出了一種半監督的帶有局部坐標的概念分解（SLCF）算法，即求解如下優化問題：

其中，α>0 為平衡參數，主要衡量局部坐標約束項的影響程度。

很顯然，SLCF算法的目標函數關于變量W和V是非凸的，很難求它的全局最優解。可以利用乘子更新規則[20]迭代優化問題（9），可以得到SLCF算法的迭代更新規則。

首先，將優化問題式（9）的目標函數可以表示為：

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

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

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

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

從優化問題（9）中可以看出，當α=0 時，SLCF算法就為CCF算法。

2.4 計算復雜度分析

為了精確分析SLCF 算法的復雜度，計算SLCF算法更新規則每次迭代過程中加法、乘法、除法運算的個數，并與CF和NMF進行比較，結果如表1所示，其中n表示數據點的個數，m表示數據的維數，k表示特征因子的維數，k≤min{m,n}。

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

3 SLCF算法收斂性證明

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

定理1優化問題（9）的目標函數O在迭代更新規則（14）、（15）下是非增的。目標函數O在迭代更新規則（14）、（15）下是不變的當且僅當W和Z是一個穩定點。

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

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

證明

現在，證明關于變量W的迭代更新規則式（14）正是某一合適的輔助函數在更新規則（16）下可得。令矩陣W中任意元素用wab表示，Fab表示式（9）中的目標函數O僅與wab有關。目標函數O關于變量wab的一階、二階導數分別為：

Table 1 Computational operation counts for each iteration in NMF,CF and SLCF表1 在NMF、CF、SLCF中每次迭代運算的個數

令Hab表示式（9）中的目標函數O僅與zab有關，計算目標函數O關于變量zab的一階、二階導數分別為：

由于式（19）、式（26）分別為Fab、Hab的輔助函數，因此Fab、Hab在更新規則式（14）、式（15）下是非增的。因此優化問題式（9）中的目標函數O在迭代更新規則（14）、（15）下是非增的。定理1得證。

4 數值實驗

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

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

4.1 在COIL20數據集上的實驗

COIL20圖像數據集包含20類共1 440張灰色圖像，每張圖像裁剪成32×32 像素，表示為1 024維的向量。在COIL20數據庫上實驗結果如表2、表3所示。

Table 2 Clustering AC performance on COIL20 database表2 在COIL20數據集的AC聚類性能%

Table 3 Clustering NMI performance on COIL20 database表3 在COIL20數據集的NMI聚類性能%

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

4.2 在YaleB數據集上的實驗

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

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

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

從表4、表5中可以看出，CCF算法的聚類性能優于K-means、NMF、CF、NLCF及LCF方法。主要由于CCF為半監督學習方法，而K-means、NMF、CF、NLCF、LCF這5種算法均為無監督的學習方法，沒有充分利用有效的標簽信息。與CCF算法相比，SLCF在平均聚類精度AC上提高了0.39個百分點，在NMI上提高了0.17 個百分點，從而表明局部坐標約束能夠提高算法的聚類性能。

4.3 在MNIST數據集上的實驗

手寫體MNIST數據集包含有60 000張圖像的訓練集和10 000張圖像的測試集。圖像分別為數字0～9共有10類，每張圖像裁剪成28×28 像素。從前10 000個訓練集中每類隨機選擇100 張圖像組成的數據集進行實驗，實驗結果如表6、表7所示。

Table 6 Clustering AC performance on MNIST database表6 在MNIST數據集的AC聚類性能%

由表6、表7 可以看出，提出的SLCF 算法在不同的聚類數下的算法聚類性能優于其他比較的算法。具體來說，與NMF 算法相比，NLCF 在AC 上提高了2.85個百分點，在NMI上提高了1.86個百分點，主要由于NLCF 利用局部坐標約束提取了數據的稀疏性。與NLCF相比，SLCF算法在AC上提高了7.84個百分點，在NMI 上提高了8.37 個百分點，因為SLCF算法不僅考慮了數據的稀疏性，還有效地利用數據的部分標簽信息，進一步提高了算法的聚類性能。

Table 7 Clustering NMI performance on MNIST database表7 在MNIST數據集的NMI聚類性能%

4.4 參數分析

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

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

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

提出的SLCF算法也是一個半監督學習方法，標簽數據的比例與算法的性能具有密切的關系。為了討論有標簽數據的比例對算法性能的影響程度，隨機選擇每類有標簽數據的比例分別從10%到80%的變化，每次實驗獨立運行10次，在不同的數據集上的實驗結果如圖2所示。從圖2中可以看出，半監督學習算法CCF 和SLCF 算法隨著有標簽數據的比例增加算法的聚類性能逐漸提高。

4.5 收斂性分析

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

Fig.2 Effect of the number of labeled data on performance圖2 有標簽數據的比例對算法性能的影響

Fig.3 Convergence curves of CF,CCF and SLCF on 3 databases圖3 CF、CCF、SLCF在3個數據集上的收斂曲線

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

5 結論

針對傳統的概念分解算法不能利用有效的標簽信息，也不能提取數據空間的稀疏性問題，本文將有限的標簽信息和局部坐標約束融入到CF中，提出了一種帶有局部坐標約束的半監督的概念分解（SLCF）算法。同時給出了SLCF算法的迭代更新規則，從理論上也證明了SLCF 算法的收斂性，在COIL20、Yale B 以及MNIST 數據庫上實驗表明提出的SLCF 算法是有效的。