陳璐瑤，劉奇龍，許云霞，陳 震

（貴州師范大學數(shù)學科學學院，貴陽 550025）

0 概述

基于矩陣分解的數(shù)據(jù)處理方法近年來在計算機視覺、模式識別、信號處理、生物醫(yī)學工程和圖像工程等［1-3］研究領域中得到了成功的應用，如奇異值分解、主成分分析、獨立成分分析、線性判別分析等方法。這些方法都是將原始矩陣近似分解為多個低秩矩陣的乘積［4］。分解的因子矩陣的元素可能是正數(shù)也可能是負數(shù)，但在實際應用問題中負值元素往往沒有意義或無法解釋，如圖像數(shù)據(jù)的像素值不可能是負值，文檔的數(shù)目及詞匯的個數(shù)也不可能是負值。鑒于此，文獻［5］提出一種新的矩陣分解方法——非負矩陣分解（Nonnegative Matrix Factorization，NMF），與傳統(tǒng)的矩陣分解方法相比，非負矩陣分解所得結果均為非負值，這使得非負矩陣分解在實際問題中得到了廣泛應用。文獻［6］提出已有的非負矩陣分解方法通常是將二維的圖像變?yōu)橐痪S向量處理，這種做法破壞了圖像像素點之間的幾何結構關系，在數(shù)據(jù)降維和特征提取過程中容易導致信息丟失、維數(shù)災難和小樣例問題，文獻［7］提出張量表示能在一定程度上避免上述問題。張量是矩陣和向量的高階推廣，其中0 階張量是標量、1 階張量是向量、2 階張量是矩陣。張量分解的兩種經(jīng)典模型為PARAFAC 分解和Tucker 分解［8-10］。PARAFAC 分解是將一個N階張量分解為若干個秩一張量和的形式；Tucker 分解是將原張量分解成核張量和因子矩陣乘積的形式。文獻［11］提出在非負性約束下，Tucker 分解可以像矩陣分解一樣提取基于局部特征的表示。因此，非負Tucker 分解（Nonnegative Tucker Decomposition，NTD）是處理非負張量數(shù)據(jù)的一種常用方法。

文獻［12-14］研究數(shù)據(jù)之間的幾何結構，流形學習能夠發(fā)現(xiàn)嵌入在高維數(shù)據(jù)空間中觀測數(shù)據(jù)的低維本質(zhì)結構，以取得更好的低維表示［15］。目前已有一些研究將流形學習理論與非負張量分解理論結合。例如，文獻［16］考慮到圖像空間的流形結構，將局部線性嵌入正則化項添加到非負平行因子分析（NPARAFAC）模型，研究了鄰域保持的非負張量分解方法。另外，文獻［17］提出拉普拉斯正則化非負張量分解方法（Laplace Regularized Nonnegative Tensor Decomposition，LRNTD）并用于圖像聚類。在每種模式下，NPARAFAC通常比NTD 需要更多的分量［18］，導致NPARAFAC 的數(shù)據(jù)表示效果不如NTD。傳統(tǒng)的Tucker 分解只涉及屬性信息，而沒有考慮圖像之間的成對相似信息。文獻［19］考慮屬性信息與圖像間局部表示的相似程度，提出一種圖拉普拉斯Tucker分解（Graph Laplace Tucker Decomposition，GLTD）方法。文獻［20］將流形正則化項引入非負Tucker 分解中，提出一種流形正則化非負Tucker 分解（Manifold Regularized Nonnegative Tucker Decomposition，MRNTD）方法。文獻［21］在低維表示的前提下，為了同時保持內(nèi)部的多線性結構和幾何信息，將圖正則化引入到非負Tucker分解中，提出一種圖正則化的非負Tucker 分解（Graph regularized Nonnegative Tucker Decomposition，GNTD）方法。

然而上述研究只考慮到了樣本間的成對關系，忽略了樣本間的高階關系［22-24］，文獻［25-27］則利用超圖可以解決這一不足。本文結合超圖學習［22］和NTD 算法，提出一種基于超圖正則化非負Tucker 分解算法（HyperGraph Regularized Nonnegative Tucker Decomposition，HGNTD）。利用K-最鄰近（K-Nearest Neighbor，KNN）方法建立超圖，將超圖正則項添加到非負Tucker 分解中，并基于交替非負最小二乘法（Alternating Nonnegative Least Squares，ANLS），設計超圖正則化非負Tucker 分解算法（HGNTD）求解模型。

1 相關工作

1.1 非負Tucker 分解

張量分解有兩種經(jīng)典模型：PARAFAC 分解［8］和Tucker 分解［9］。這兩種模型都是矩陣奇異值分解的高階推廣，也可看作是主成分分析（PCA）的高階形式，且前者是后者的一種特例。

NTD 可以看作是NMF 的多線性推廣，NTD 的矩陣形式（式（1））和NMF 之間的一個最大的區(qū)別是前者的基矩陣是核張量與因子矩陣從模-1 到模-(N-1)的乘積，這有利于改善基矩陣的稀疏性。

1.2 超圖學習

超圖是普通圖的推廣，在普通圖中，一個數(shù)據(jù)對象表示一個頂點，兩個頂點之間的邊用來描繪頂點之間的關系。超圖中的超邊連接3 個或者更多的頂點可以更好地表示數(shù)據(jù)的高維信息，超圖已經(jīng)廣泛應用于分類、聚類中。下文簡單地介紹超圖的一些基本理論［22，26］：

假 設G=(V,E,W)，其 中V={ν1,ν2,…,νN}是 頂點集，集合V中的每一個元素稱為頂點；E={e1,e2,…,eM}是超邊集，集合E中的每一個元素稱為超邊，每條超邊是頂點集V的子集；W為超圖的權重矩陣，是由超邊的權重構成的對角矩陣，其中每條超邊e的權重是事先賦的一個正值w(e)。如果以下兩個條件成立：ej??,?j∈1,2,…,M，e1∪e2∪…∪eM=V，則G是定義在集合V上的超圖。

超圖可使用一個|V| ×|E|的關聯(lián)矩陣H來表示：

下文用幾何圖形解釋超圖，如圖1 所示，其對應的頂點與超邊的關聯(lián)矩陣H如表1 所示。

圖1 超圖G 的幾何示意圖Fig.1 Geometric schematic diagram of hypergraph G

表1 圖1 對應的關聯(lián)矩陣HTable 1 The correlation matrix H corresponding to Fig.1

圖1給出一個超圖G=(V,E)，實心節(jié)點表示為頂點，由橢圓虛線標記的集合表示超邊。表1表示為其對應的關聯(lián)矩陣H，其 中，V={ν1,ν2,…,ν7}，E={e1,e2,e3}，e1={ν1,ν2,ν3}，e2={ν3,ν4,ν5}，e3={ν5,ν6,ν7}。

對于頂點ν∈V，ν所屬的超邊的權重之和稱為ν的階（或度），記為；對于超邊e∈E，e所包含的頂點數(shù)稱為e的階（或度），記為δ(e)=|e|。因此：

分別用Dν、De、W表示頂點的度、超邊的度和超邊的權重所形成的對角矩陣，可分別表示為：

根據(jù)文獻［22］定義，非標準化超圖拉普拉斯矩陣為：

根據(jù)超邊的定義，允許包含任意數(shù)量的頂點。為了方便起見，本文采用在每條超邊中包含相同頂點個數(shù)的一致超圖。

2 超圖正則非負Tucker 分解

本文在NTD 和超圖學習基礎上，提出張量數(shù)據(jù)超圖的構造方法，并將超圖的正則化項引入NTD 目標函數(shù)中，最后給出求解HGNTD 模型的有效算法。

2.1 超圖構造

為了構造超圖，可以把數(shù)據(jù)集中的每個數(shù)據(jù)點看作超圖的頂點，將當前頂點和其最鄰近的頂點看作一條超邊，通過改變最鄰近半徑大小定義一組超邊。根據(jù)超圖的不同構造方法可以生成大量超邊，使超圖更好地描述數(shù)據(jù)結構。此外，超邊權重的選擇也很重要，目前最常用的加權方案有3 種：0-1 加權方案，熱核（Heat Kernel）加權方案和點乘加權方案。不同的加權方案適用于不同的應用問題，如點乘權重通常適用于文本匹配問題，而熱核加權方案常用于處理圖像數(shù)據(jù)。

本文中采用的是熱核加權方案，基于給定的圖像空間鄰域構造一個超圖G=(V,E,W)。首先，將Y={y1,y2,…,yN}中的每張圖像yi看作超圖的一個頂點νi。然后，以每個頂點νi作為空間區(qū)域的“質(zhì)心”節(jié)點，并使用K-最鄰近（KNN）方法構造相應的超邊ei∈E，因此，超圖G由構造在不同空間區(qū)域上的N個超邊組成。基于這些超邊，通過式（2）獲得關聯(lián)矩陣最后，使用熱核加權方案，賦予每條超邊一個正權重［28］，即：

根據(jù)上述超圖的構造方法，每個頂點與至少一條超邊連接，并且每條超邊與權重相關聯(lián)。對角權重矩陣W∈RN×N由下式給出：

權重矩陣W的權值與兩點間的歐氏距離成反比。兩個點之間的歐氏距離越小，它們的相似性越高。因此，使用下式來刻畫低維數(shù)據(jù)的光滑性：

其中：Tr(·)表示矩陣的跡；LHyper是式（3）所定義的非標準化超圖G的超圖拉普拉斯矩陣。

2.2 目標函數(shù)

將超圖正則化項式（4）加入到原始NTD 的目標函數(shù)中，得到HGNTD 目標函數(shù)如下：

其中：λ是一個非負參數(shù)，用于平衡超圖正則化項和重構誤差項；LHyper是式（3）所定義的非標準化超圖G的超圖拉普拉斯矩陣。

采用拉格朗日乘子法，并考慮模-n展開形式，然后確定基于式（5）的拉格朗日函數(shù)：

可將目標函數(shù)重新寫為：

2.3 迭代規(guī)則更新

為了求解式（6），采用交替非負最小二乘迭代方法，即每次只更新核心張量或一個因子矩陣，同時固定其他因子矩陣。

2.3.1 因子矩陣A(n)(n≠N)更新

LHGNTD對于A(n),n≠N的偏導數(shù)為：

因此，得到以下更新規(guī)則：

其中：P+(ξ)=max(0,ξ)。

2.3.2 因子矩陣A(N)更新

求LHGNTD關于A(N)的偏導數(shù)為：

同理，由KKT 條件可以得到以下更新規(guī)則：

2.3.3 核張量S更新

基于式（5）采用拉格朗日乘子法，并考慮其向量化形式：

LHGNTD對于vec(S)的偏導數(shù)為：

同上，由KKT 條件從而得到以下更新規(guī)則：

根據(jù)以上分析，給出本文算法。

2.4 收斂性分析

定理1若≥0(n∈N),vec(S)≥0，則目標函數(shù)式（5）在更新迭代規(guī)則式（7）、式（8）和式（9）下是非增的。

為證明該定理，首先引入輔助函數(shù)的定義：

定義1若G(x,x′)滿足G(x,x)=F(x)，G(x,x′) ≥F()x，則G(x,x′)是F(x)的輔助函數(shù)［29］。

引理1若G(x,x′)是F(x)的輔助函數(shù)，則F(x)在更新迭代規(guī)則［29］：

下是非增的。

證明根據(jù)定義1 和更新迭代規(guī)則式（10），有：

為證明目標函數(shù)式（5）在更新規(guī)則式（7）下是非增的，先構造關于矩陣A(n)的(i,j)元素的輔助函數(shù)。對固定的行列指標(i,j)，令A(n)(x)是通過將矩陣A(n)的(i,j)元素替換為變量x，其余元素不變得到的矩陣函數(shù)。

引理2函數(shù)：

是Fij(x)的輔助函數(shù)，其中：

因為：

由定理1 知算法1 是局部收斂的。

3 數(shù)值實驗

現(xiàn)實中的高維圖像數(shù)據(jù)依據(jù)人們能否獲得先驗信息可以分成兩類：一類是可以通過人工標記或可以直接獲得先驗標簽信息的數(shù)據(jù)；另一類是沒有任何類別標簽信息的數(shù)據(jù)。

圖像數(shù)據(jù)分析與處理的方法分為有標簽數(shù)據(jù)的圖像分類和無標簽數(shù)據(jù)的圖像聚類。它們的區(qū)別是：分類是事先定義好類別，類別數(shù)不變。分類器需要由人工標注的分類訓練語料訓練得到，屬于有監(jiān)督學習。而聚類是沒有事先規(guī)定類別，類別數(shù)不確定。聚類不需要人工標注和預先訓練分類器，類別在聚類過程中自動生成，屬于無監(jiān)督學習。

本文進行的是無監(jiān)督的聚類實驗，因此無需訓練集和測試集，數(shù)據(jù)集的標簽只用于和聚類實驗結果進行對比。

為驗證本文算法的有效性，選擇如下代表性算法進行比較：NMF［5］，GNMF［14］，NTD［18］，GNTD［21］和K-means［30］。本文分別在兩個常用公開的數(shù)據(jù)集Yale 和COIL-100 上進行聚類實驗，實驗環(huán)境為：Matlab 2019a，Intel?Core（TM）i5-7500 CPU@3.40 GHz，3.41 GHz 處理器，8.00 GB 內(nèi)存，64 位的Win10 操作系統(tǒng)。

3.1 數(shù)據(jù)描述

實驗中所使用數(shù)據(jù)集如下：

1）Yale。該數(shù)據(jù)集是由耶魯大學計算視覺與控制中心創(chuàng)建，包含15 位志愿者，每個采集志愿者包含光照、表情和姿態(tài)的變化以及遮擋臉部（不戴眼鏡、戴普通眼睛和戴墨鏡）狀態(tài)下的11 張樣本，總共有165 幅分辨率為100×100 像素的人臉圖像。在實驗中，Yale 數(shù)據(jù)集的所有圖像都被調(diào)整為32×32 像素的大小，Yale 數(shù)據(jù)集的部分圖片如圖2 所示。

圖2 Yale 數(shù)據(jù)集的部分圖片F(xiàn)ig.2 Some images of Yale dataset

2）COIL-100。該數(shù)據(jù)集是哥倫比亞大學采集的（COIL-100）圖像數(shù)據(jù)集。COIL-100 由7 200 幅尺寸為128×128 像素的彩色圖像組成，包含100 個目標，每個目標有72 幅不同角度的圖像。在實驗中，每個彩色圖像被調(diào)整為大小32×32 像素的灰度圖像。COIL-100 數(shù)據(jù)集的部分圖片如圖3 所示。

圖3 COIL-100 數(shù)據(jù)集的部分圖片F(xiàn)ig.3 Some images of COIL-100 dataset

傳統(tǒng)的非負矩陣分解方法將每幅圖像向量化后構成相應的1 024×165 和1 024×7 200 的矩陣再做分解，破壞了圖像像素幾何結構關系。非負張量分解方法直接對32×32×11K和32×32×72K（其中K是簇數(shù)）兩個張量進行分解，不會破壞圖像原有的結構。

3.2 評估指標

為評估聚類效果，使用兩個流行的評估指標來評估聚類效果：一種度量標準是聚類準確度（Accuracy）；另一種度量標準是歸一化互信息（Normalized Mutual Information，NMI）。

聚類準確度（Accuracy，ACC）定義如下［31］：

其中：Ci是真實類標簽集合是算法得到的聚類標簽集合；n是數(shù)據(jù)樣本總數(shù)；δ(x,y)是一個kronecker函數(shù)，如果x=y，則δ(x,y)=1，否則δ(x,y)=0，并且map)是將每個聚類標簽映射到真實類標簽集Ci中等效標簽的映射函數(shù)。為得到最佳映射，通常使用Kuhn-Munkres 算法。

3.3 對比算法與參數(shù)設置

為驗證本文所提算法的有效性，將HGNTD 分別與NMF［5］、GNMF［14］、NTD［18］、GNTD［21］和k-means［30］算法進行比較，具體參數(shù)如下：

1）基于NMF 算法的聚類。目標函數(shù)中距離使用Frobenius 范數(shù)度量，基矩陣的行數(shù)r=10，即低維子空間的維數(shù)為r。

2）基于GNMF 算法的聚類。目標函數(shù)中距離使用Frobenius 范數(shù)度量，并采用熱核（Heat Kernel）加權方案，使用k-最鄰近方法構造權重矩陣W，其中k=3，圖的正則化參數(shù)λ取0.5。

3）基于NTD 算法的聚類。目標函數(shù)中距離使用Frobenius范數(shù)度量，核張量的規(guī)模為

4）基于GNTD 算法的聚類。目標函數(shù)中距離使用Frobenius 范數(shù)度量，核張量的規(guī)模同NTD 算法。采用熱核加權方案，GNTD 的其他參數(shù)設置與GNMF 的設置相同。

5）基于HGNTD 算法的聚類。目標函數(shù)中使用Frobenius 范數(shù)度量距離。核張量的規(guī)模同NTD 算法。采用熱核加權方案，使用k-最鄰近方法構造權重矩陣W，其中k=3，超圖正則化參數(shù)λ=0.5。

3.4 實驗與結果分析

具體實驗步驟如下：

1）為使實驗更具有說服力，對聚類實驗配置進行隨機化處理，即在不同的類別個數(shù)進行聚類實驗。每次隨機選擇數(shù)據(jù)庫中K個類別（COIL-100：K=2，4，…，20；Yale：K=3，5，…，15）。

2）對于k-means 算法，作為一種基線（Baseline）算法，只在原始數(shù)據(jù)空間中進行聚類。對于NMF、GNMF、NTD、GNTD 和HGNTD 算法，在進行分解后，可以得到各個對比算法對應的低維子空間表示，那么聚類則在這些低維子空間中進行。然后，再將k-means 應用于這些重構表征上進行聚類。

3）計算兩個聚類指標精度（ACC）和歸一化互信息（NMI）。

4）重復上述步驟20 次，并記錄各個聚類算法的平均性能以及上下偏差情況。

Yale 數(shù)據(jù)集的聚類準確度和歸一化互信息的結果如表2、表3 所示，COIL-100 數(shù)據(jù)集的聚類準確度和歸一化互信息的結果如表4、表5 所示，其中粗體為最優(yōu)值。

表2 Yale 數(shù)據(jù)集聚類準確度Table 2 Clustering accuracy of Yale dataset %

表3 Yale 數(shù)據(jù)集聚類歸一化互信息Table 3 Clustering normalized mutual information of Yale dataset %

表4 COIL-100 數(shù)據(jù)集聚類準確度Table 4 Clustering accuracy of COIL-100 dataset %

表5 COIL-100 數(shù)據(jù)集聚類歸一化互信息Table 5 Clustering normalized mutual information of COIL-100 dataset %

從表2～表5 可以看出：在保留幾何信息和內(nèi)部結構的情況下，HGNTD 與NMF、GNMF、NTD、GNTD 和k-means 算法相比，聚類性能更好。本文方法比其他方法的聚類準確度提升了8.6～11.4%，歸一化互信息提升了2.0～7.5%，這也表明本文提出算法對圖像聚類是有效的。

表6、表7 給出Yale 數(shù)據(jù)集上NMF、GNMF、NTD、GNTD 和HGNTD 算法分別在維數(shù)r=4 和r=5下的對比結果，其中粗體為最優(yōu)值。

表6 Yale 數(shù)據(jù)集上不同算法的聚類準確度Table 6 Clustering accuracy of different algorithms on Yale dataset %

表7 Yale 數(shù)據(jù)集上不同算法聚類歸一化互信息Table 7 Clustering normalized mutual information of different algorithms on Yale dataset %

由表6、表7 可以看出：在不同維數(shù)下，本文算法的聚類結果要比其他算法的聚類結果更好。

圖4 所示為NMF、GNMF、NTD、GNTD 和HGNTD 算法在Yale 數(shù)據(jù)集上的人臉重構效果，分別給出在Yale 數(shù)據(jù)集上的部分圖像，其中，第1 行為原始圖像，第2 行～第6 行分別為HGNTD 算法、GNTD算法、GNTD 算法、GNMF 算 法和NMF 算法的樣本重構圖像。其中，HGNTD 算法的重構圖像比其他算法下的樣本重構圖像更加清晰，復原效果更好。

圖4 Yale 數(shù)據(jù)集部分樣本重構圖像Fig.4 Reconstructed images from partial samples of Yale dataset

4 結束語

本文提出一種基于超圖正則化非負Tucker 分解算法（HGNTD）。利用k-最鄰近方法構造超圖，將超圖正則項添加到非負Tucker 分解中，建立基于超圖正則化非負Tucker 分解模型，基于交替非負最小二乘法算法，給出超圖正則化非負Tucker 分解算法求解此模型，并證明算法是收斂的。在公開數(shù)據(jù)集上的實驗結果表明，與k-means、NMF、GNMF、NTD、GNTD 等算法相比，該算法具有更好的聚類效果。由于在本文實驗中發(fā)現(xiàn)圖像只需少數(shù)基底表示即可，因此下一步將繼續(xù)對基于稀疏約束的超圖正則化非負張量分解算法進行研究，以提高模型的適用性。