近鄰系數(shù)協(xié)同強化人臉圖像子空間聚類法

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

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

0 引言

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

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

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

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

利用最小二乘回歸模型求解表示系數(shù)，其數(shù)學(xué)模型如下：

(1)

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

ω=(XTX+λI)-1XTy

(2)

這里，I是單位矩陣.

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

(3)

2 近鄰系數(shù)協(xié)同強化子空間聚類法

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

2.1 研究動機

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

2.2 目標函數(shù)

(4)

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

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

(5)

其中:γ≥0是正則參數(shù)用來平衡樣本重構(gòu)項和近鄰系數(shù)協(xié)同強化項，當(dāng)γ=0時退化為最小二乘回歸模型.

2.3 模型求解

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

(6)

展開為：

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

(7)

關(guān)于ω求導(dǎo)得：

(8)

令其為0，得解析解為：

(9)

2.4 算法流程

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

d=|ω|

(10)

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

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

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

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

3 實驗分析

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

3.1 實驗設(shè)置

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

表1 數(shù)據(jù)集描述

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

3.2 對比實驗與參數(shù)討論

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

表2 聚類準確率對比

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

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

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

4 結(jié)語

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