近鄰系數協同強化人臉圖像子空間聚類法

許毅強，夏靖波，簡彩仁，翁謙

(1.廈門大學嘉庚學院，福建 漳州 363105； 2.福州大學計算機與大數據學院，福建 福州 350108)

0 引言

子空間聚類是最流行的數據分析技術之一，引起計算機視覺[1-2]、 圖像分析[3-5]和基因表達數據識別[6-7]等多個領域研究人員的興趣.假設高維數據是從低維子空間的并集中近似提取出來的，子空間聚類的目的是尋找一組子空間來擬合給定的數據集，并基于所識別的子空間進行聚類.子空間聚類方法通過將高維數據點表示為其線性相關的低維子空間的組合以降低數據集的高維性.特別是，基于自表示理論的子空間聚類方法取得了顯著的效果，在各種無監督機器學習領域取得突出成就.

子空間聚類方法作為高維數據聚類的一種解決方案，人們提出了各種子空間聚類方法.目前大多數子空間聚類方法都執行兩個步驟： 首先，通過施加各種約束來構造相似矩陣確定給定數據點之間有意義的關系； 第二，將譜聚類應用于構造以確定最終數據點成員關系的相似矩陣.大多數高性能線性子空間聚類方法是基于自表示理論的，這意味著每個樣本點可以表示為其他樣本點的線性組合，使用幾個相同子空間的向量基，這個線性組合會突出顯示樣本點之間的冗余.典型的線性子空間聚類方法是稀疏子空間聚類(SSC)[8]、 低秩表示子空間聚類(LRR)[9]和最小二乘回歸子空間聚類(LSR)[10].SSC方法使用L1范數來尋找最稀疏的表示，LRR方法利用核范數尋求最低秩表示，而LSR方法利用F-范數尋求良好聚集性的表示.這3種方法都是比較成功的，隨后針對特定應用，研究人員開發了一些改進模型.然而，由于SSC方法為每個數據點單獨找到了最稀疏的表示，其無法捕獲全局數據結構； 由于核范數極小化計算量大，LRR方法受到限制.此外，如果數據點不足，基于SSC方法和LRR方法的聚類性能會顯著下降.LSR方法因為其聚集性能優越，并且模型具有解析解，因此得到了許多學者的青睞.核截斷回歸表示子空間聚類(KTRR)[11]利用核方法尋找能刻畫非線性的表示.縮放單純形表示子空間聚類(SSR)[12]利用縮放和非負約束求解更有區分能力的表示.

盡管這些方法在一定程度上提高了高維數據無監督的學習能力，但是這些方法仍存在一些不足.例如，近鄰樣本更有可能屬于同一類別，因此對所有的樣本點一視同仁存在不合理.考慮近鄰樣本的表示系數將有利于尋找更加合理的表示.基于這一發現，利用近鄰樣本的表示系數協同強化求解表示系數提出改進LSR的一種方法.

1 最小二乘回歸子空間聚類法

利用最小二乘回歸模型求解表示系數，其數學模型如下：

(1)

其中:λ>0是正則參數.那么，不難得到其解析解：

ω=(XTX+λI)-1XTy

(2)

這里，I是單位矩陣.

利用公式(2)對每個樣本分別求解表示系數ω=(ω1,ω2,…,ωn-1)T，利用ω構造表示系數矩陣Zn×n=(zi)n×n如下：

(3)

2 近鄰系數協同強化子空間聚類法

直觀上，近鄰樣本更有可能屬于同一類別，因此在同一度量空間中，相同類別的表示系數應該很接近.本節針對最小二乘回歸子空間聚類法在求解表示系數時，對每個樣本同等對待的不足，利用近鄰系數協同強化的思想提出一種改進方法： 近鄰系數協同強化子空間聚類法.

2.1 研究動機

因此測試樣本P的表示系數(4.06, 4.45)與五角星類最為接近，根據表示系數相近，將P歸為五角星類.依據這一發現，當利用表示理論求解表示系數時，往往以數據集X作為基，此時，同類別的樣本得到的表示系數也應該很接近.

2.2 目標函數

(4)

其中:p是y的近鄰樣本數量.子空間聚類的目標是將相同類別的樣本聚集，而近鄰樣本更可能屬于同一類.因此，在相同度量空間下，近鄰樣本的表示系數應該很接近，于是旨在求解使公式(4)最小的表示系數.

將公式(1)和公式(4)合并得到近鄰系數協同強化子空間聚類法的數學模型如下：

(5)

其中:γ≥0是正則參數用來平衡樣本重構項和近鄰系數協同強化項，當γ=0時退化為最小二乘回歸模型.

2.3 模型求解

顯然，公式(5)是一個可微的凸優化問題，可以求解其解析解.利用矩陣的跡tr(·)將公式(5)重寫為：

(6)

展開為：

L(ω)=tr(yTy)-2tr(ωTXTy)+tr(ωTXTXω)+λtr(ωTω)+

(7)

關于ω求導得：

(8)

令其為0，得解析解為：

(9)

2.4 算法流程

由于現實中的數據集往往是非線性的，因此基于歐式距離的相似度度量不夠準確.借鑒文獻[14]的思想，選出p個近鄰樣本.利用最小二乘回歸的表示系數，即公式(2)定義相似度為：

d=|ω|

(10)

其中： |ω|為表示系數ω的絕對值；di=|ωi|=sim(xi,y)表示樣本xi與樣本y的相似度，越大的di=|ωi|說明xi在重構y時的作用越大，也意味著xi與y的相似度越高.將d按照降序排列，選出前p個作為y的近鄰樣本.利用公式(9)和公式(3)得到相似矩陣:

最后用標準化分割方法對W進行分割完成聚類.

綜上所述，近鄰系數協同強化子空間聚類法(nearest neighbor coefficient cooperative reinforcement subspace clustering method，2N2CR)流程如下：

算法1 近鄰系數協同強化子空間聚類法(2N2CR)Input: 數據集A, 參數λ, γ, 近鄰數量p, 類別數量Kfor i in 1∶n Step1: 將A分為第i個樣本y=ai和X=A-i, 利用公式(2)求解表示系數得到相似度向量d, 并按照降序排列, 選出前p個作為y的近鄰樣本; Step2: 對X、 y和p個近鄰樣本, 利用公式(9)求解表示系數ωi; end Step3: 利用公式(3)組合表示系數得到表示系數矩陣, 并構造相似矩陣W; Step4: 利用標準化分割方法對W進行分割完成聚類; Output: 聚類結果, 即K個類簇.

3 實驗分析

本節通過對比實驗和參數討論等研究2N2CR方法的性能.

3.1 實驗設置

選用6個標準的人臉圖像數據集為研究對象，如表1所示.2N2CR方法作為LSR方法的一種改進，KTRR和SSR也是LSR的擴展模型.為了突出2N2CR方法的性能，選用LSR、 KTRR和SSR為對比方法，KMEANS作為一種經典的傳統方法也作為一種對比方法.

表1 數據集描述

為了便于實驗操作，在對比實驗中固定各種方法的參數，其中，統一的正則參數λ設為0.01，2N2CR方法的近鄰數量p設為5，γ設為0.3.鑒于所有方法的聚類結果都有隨機性，采用Matlab固定隨機種子的方法以避免隨機性.選用研究聚類方法常用的聚類準確率(AC)[15]作為聚類性能評價指標.

3.2 對比實驗與參數討論

表2給出了所有對比方法的聚類準確率.從表2的實驗結果可以看出，除pixraw10P數據集外，子空間聚類方法，即2N2CR等方法的聚類準確率明顯優于KMEANS聚類方法，這表明傳統的基于歐式距離度量的聚類方法難以適應高維樣本的聚類.這一結果表明子空間聚類方法更適合高維數據的聚類.2N2CR方法的聚類準確率優于LSR及其擴展方法.所以，2N2CR方法利用近鄰系數協同強化求解的表示系數能很好地反映樣本相似度，從而提高聚類準確率.因此, 2N2CR方法是對LSR方法的一種有效改進.

表2 聚類準確率對比

2N2CR方法有3個參數，正則參數λ和γ，以及近鄰數量p，本節研究參數對2N2CR方法的影響.圖2為固定參數λ=0.01和γ=0.3的情形下，參數p對2N2CR方法的聚類準確率的影響.圖3給出了固定參數p=5的情形下，參數λ和γ對2N2CR方法的聚類準確率的影響.從圖2的實驗結果不難發現，當近鄰數量p=7時，2N2CR方法在6個數據集上都取得了最高的聚類準確率，這一結果為選擇近鄰數量提供了指導，增強了2N2CR方法的實用性.

從圖3的實驗結果可以看出，λ和γ對2N2CR方法的聚類準確率有明顯的影響，當固定λ=0.01時，在γ>0的情況下，γ變化時，2N2CR方法的聚類準確率變化不大，這表明γ對聚類準確率的影響較小.但是當固定γ(比如取γ=0.5)，λ變化時，2N2CR方法的聚類準確率變化比較明顯，從圖中可以發現當λ為0.01或0.1時，2N2CR方法可以取到較好的聚類準確率.

綜合圖2～3的實驗結果，選擇正則參數λ為0.1或0.01，γ為0.3或0.5，近鄰數量p為7時，2N2CR方法將取得比較理想的聚類準確率.

4 結語

針對最小二乘回歸子空間聚類法沒有考慮近鄰樣本對求解表示系數的影響這一不足，提出近鄰系數協同強化子空間聚類法.在6個人臉圖像數據集上的實驗表明2N2CR方法是LSR方法的一種有效改進.2N2CR方法的關鍵在于求解每個樣本表示系數，因此更適合小樣本數據的聚類研究.盡管2N2CR方法可以取得較好的聚類準確率，但是與LSR方法對比，2N2CR方法不僅要對每個樣本尋找近鄰樣本，還要對每個樣本求解表示系數，因此運行效率較低.