胡慧旗，張維強(qiáng)，徐晨

（深圳大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 深圳 518060）

0 概述

子空間聚類是一種非常有效的高維數(shù)據(jù)聚類方法，假設(shè)高維數(shù)據(jù)分布在幾個(gè)低維子空間的并中，其目的是將高維數(shù)據(jù)分成不同的類，一類對(duì)應(yīng)一個(gè)子空間。目前，子空間聚類已被廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)［1］、圖像處理［2-3］、系統(tǒng)識(shí)別［4］等領(lǐng)域。基于譜聚類的子空間聚類算法因其計(jì)算簡(jiǎn)單、聚類性能優(yōu)異而成為研究熱點(diǎn)。稀疏子空間聚類（SSC）［5-6］、低秩表示子空間聚類（LRR）［7-8］和最小二乘回歸子空間聚類（LSR）［9］是基于譜聚類的子空間聚類中3 個(gè)經(jīng)典的算法，它們的共同點(diǎn)是利用高維數(shù)據(jù)的自表示構(gòu)建相似度矩陣，然后通過(guò)譜聚類得到聚類結(jié)果。3 種算法的不同點(diǎn)在于自表示系數(shù)的約束不同：SSC 對(duì)自表示系數(shù)矩陣采用l0或l1范數(shù)約束，希望每個(gè)數(shù)據(jù)的自表示是稀疏的，僅被其所屬子空間（即同類）的數(shù)據(jù)表示，但是稀疏約束會(huì)導(dǎo)致自表示過(guò)于稀疏，即僅從同類數(shù)據(jù)中挑選最相似的數(shù)據(jù)對(duì)其表示，忽略了其他相關(guān)的數(shù)據(jù)，不利于聚類；LRR 對(duì)自表示系數(shù)矩陣采用低秩約束，這是一種全局結(jié)構(gòu)，但低秩表示可能導(dǎo)致過(guò)于稠密的自表示，即不同子空間的數(shù)據(jù)參與了表示，另外，當(dāng)數(shù)據(jù)采樣不足時(shí)，低秩表示可能會(huì)失效；LSR 對(duì)自表示系數(shù)采用l2范數(shù)正則，這有利于將高度相關(guān)的數(shù)據(jù)聚集在一起，但也會(huì)導(dǎo)致類內(nèi)類間的自表示都是均勻的，不利于分離不同類別的數(shù)據(jù)。

在子空間獨(dú)立的條件下，以上3 種算法都被證明自表示系數(shù)矩陣是一個(gè)分塊對(duì)角矩陣，即來(lái)自不同子空間數(shù)據(jù)間的表示系數(shù)為零。自表示系數(shù)矩陣的塊對(duì)角結(jié)構(gòu)揭示了數(shù)據(jù)與低維空間的真實(shí)隸屬關(guān)系，從而相應(yīng)相似度矩陣表現(xiàn)出類內(nèi)相似度高、類間相似度低的特性，這有利于譜聚類產(chǎn)生正確的聚類標(biāo)簽。因此，子空間聚類問(wèn)題關(guān)鍵在于自表示系數(shù)矩陣的構(gòu)造，理想的自表示系數(shù)矩陣應(yīng)同時(shí)具有稀疏性和聚集性，即類間稀疏、類內(nèi)聚集。鑒于這一考慮，很多算法［10-12］對(duì)數(shù)據(jù)的自表示矩陣同時(shí)進(jìn)行稀疏約束和低秩約束，或者同時(shí)進(jìn)行稀疏約束和l2范數(shù)約束，強(qiáng)制自表示系數(shù)矩陣具有稀疏性和聚集性。FENG等［13］指出自表示系數(shù)矩陣應(yīng)具有塊對(duì)角結(jié)構(gòu)，并通過(guò)添加顯式的硬約束，強(qiáng)迫SSC 和LRR 得到的自表示系數(shù)矩陣具有精確的塊對(duì)角結(jié)構(gòu)。進(jìn)一步地，LU等［14］提出K塊對(duì)角正則項(xiàng)，迫使自表示系數(shù)矩陣具有塊對(duì)角結(jié)構(gòu)?？紤]模型的整體性能，LI等［15］提出結(jié)構(gòu)稀疏子空間聚類（SSSC）模型，通過(guò)引入聯(lián)合正則項(xiàng)實(shí)現(xiàn)系數(shù)矩陣和聚類標(biāo)簽的聯(lián)合學(xué)習(xí)，使得模型直接輸出聚類標(biāo)簽。受SSSC 模型啟發(fā)，ZHANG等［16］在LRR 模型中加入聯(lián)合正則項(xiàng)，提出低秩結(jié)構(gòu)稀疏子空間聚類（LRS3C）模型，構(gòu)建了一個(gè)聯(lián)合優(yōu)化框架。在LRS3C 基礎(chǔ)上，YOU等［17］通過(guò)添加促使低相關(guān)數(shù)據(jù)盡量遠(yuǎn)離的l1范數(shù)正則項(xiàng)，防止系數(shù)矩陣過(guò)于密集，加強(qiáng)了類間數(shù)據(jù)的稀疏性，進(jìn)一步提升了聚類性能。

然而，原始數(shù)據(jù)中往往存在噪聲和其他干擾，直接對(duì)原始數(shù)據(jù)進(jìn)行自表示得到的相似度矩陣也會(huì)受到噪聲或干擾的影響，導(dǎo)致不能準(zhǔn)確反映數(shù)據(jù)的真實(shí)子空間隸屬關(guān)系，造成數(shù)據(jù)誤分類。針對(duì)此問(wèn)題，SRR［18］對(duì)原始數(shù)據(jù)進(jìn)行了二階自表示：首先對(duì)原始數(shù)據(jù)進(jìn)行自表示，由于得到的自表示矩陣反映了每個(gè)數(shù)據(jù)與其他數(shù)據(jù)的某種相關(guān)性，因此稱其為鄰域關(guān)系矩陣；然后將每個(gè)數(shù)據(jù)的自表示向量作為數(shù)據(jù)的新特征，對(duì)新特征再進(jìn)行二階自表示，也稱為重構(gòu)系數(shù)矩陣；最后基于此矩陣構(gòu)造相似度矩陣，并通過(guò)譜聚類得到最終聚類結(jié)果。實(shí)驗(yàn)結(jié)果表明，該方法具有較高的聚類精度。

本文基于SRR 中數(shù)據(jù)的鄰域關(guān)系可準(zhǔn)確反映數(shù)據(jù)類別屬性這一特點(diǎn)，提出一種兼顧相似度矩陣稀疏性和聚集性的子空間聚類方法。利用F 范數(shù)代替核范數(shù)，降低SRR 模型的求解難度，并構(gòu)建一個(gè)新的正則項(xiàng)來(lái)增強(qiáng)不同類別數(shù)據(jù)之間表示系數(shù)的判別性。在此基礎(chǔ)上，使用人臉和手寫(xiě)體數(shù)字?jǐn)?shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文方法的聚類效果。

1 符號(hào)定義與相關(guān)工作

考慮到原始數(shù)據(jù)中存在大量噪聲和干擾，WEI等［18］認(rèn)為數(shù)據(jù)間的鄰域關(guān)系特征比原數(shù)據(jù)更能揭示其類別屬性，并提出如下SRR 模型：

其中：X表示原始數(shù)據(jù)矩陣，其中一列對(duì)應(yīng)一個(gè)數(shù)據(jù)樣本；C為鄰域關(guān)系矩陣；Z為重構(gòu)系數(shù)矩陣；用于刻畫(huà)數(shù)據(jù)中的離群點(diǎn)；用于處理鄰域關(guān)系矩陣中的高斯噪聲；λ1和λ2為權(quán)重參數(shù)。在SSR 模型中：首先鄰域關(guān)系矩陣C的每一列表達(dá)了原始數(shù)據(jù)矩陣X中的對(duì)應(yīng)列與其他數(shù)據(jù)之間的某種相關(guān)性，并利用l1范數(shù)對(duì)其進(jìn)行約束；然后將C作為原始數(shù)據(jù)X的新特征進(jìn)行自表示或自重構(gòu)，用核范數(shù)來(lái)約束重構(gòu)系數(shù)矩陣Z；最后用Z計(jì)算相似度矩陣，并通過(guò)譜聚類得到聚類結(jié)果。實(shí)驗(yàn)結(jié)果表明，該模型能夠顯著提升子空間聚類性能。

本文在SRR 模型基礎(chǔ)上進(jìn)行改進(jìn)，提出一個(gè)新的模型，并給出求解算法。

2 判別性增強(qiáng)的稀疏子空間聚類模型

2.1 模型構(gòu)建

文獻(xiàn)［19］中證明，在一定條件下，基于F 范數(shù)的表示和基于核范數(shù)的表示是等價(jià)的，而平方F 范數(shù)最小化問(wèn)題不需要矩陣奇異值分解運(yùn)算。因此，本文利用平方F 范數(shù)代替SRR 中的核范數(shù)，使模型易于求解。F 范數(shù)能夠保證重構(gòu)系數(shù)矩陣Z的類內(nèi)一致性，但是不能保證類間判別性，而C的l1范數(shù)有利于保證C的類間判別性，不能保證類內(nèi)聚集性。因此，本文引入新的正則項(xiàng)來(lái)保證Z的類間判別性和C的類內(nèi)聚集性。實(shí)際上有兩重作用：當(dāng)C給定時(shí)，若Ci、Cj不相似，即較大，則該正則項(xiàng)有利于使Zij接近于0，從而兩個(gè)對(duì)應(yīng)數(shù)據(jù)的相似度較小，有利于將其分為不同類；反之，當(dāng)Z給定時(shí)，若兩個(gè)數(shù)據(jù)的相似度|Zij|較大，則該正則項(xiàng)有利于使新特征Ci、Cj相似，從而保證特征的類內(nèi)聚集性。

綜上，本文給出以下改進(jìn)的SRR 模型：

其中：α是權(quán)衡參數(shù)；diag(Z)=0 防止出現(xiàn)平凡解。

2.2 模型求解

本文采用交替方向乘子法（ADMM）［20-21］求解式（2）模型，引入輔助變量J和P，使模型轉(zhuǎn)變?yōu)椋?/p>

式（3）模型的增廣拉格朗日函數(shù)表示為：

其中：Y1、Y2、Y3、Y4是拉格朗日乘子；μ1、μ2、μ3、μ4是懲罰項(xiàng)。交替更新J、C、Z、P、E1、E2、Y1、Y2、Y3、Y4，更新一個(gè)變量的同時(shí)固定其他變量的值。

固定其他變量，關(guān)于J的子問(wèn)題為：

利用軟閾值算子求解式（5），得到J的解為：

固定其他變量，關(guān)于C的子問(wèn)題為：

式（9）是關(guān)于C的二次函數(shù)，其最優(yōu)解滿足以下方程：

式（10）是一個(gè)標(biāo)準(zhǔn)的Sylvester 方程，可以通過(guò)Matlab 的lyap 函數(shù)解決。

固定其他變量，求解下列問(wèn)題更新Z：

對(duì)變量Z量求導(dǎo)并令其為0，Z的閉式解如下：

式（13）可以通過(guò)軟閾值算子求解：

固定其他變量，更新E1即求解：

根據(jù)軟閾值算子可得E1的解為：

固定其他變量，更新E2即求解：

變量E2的解為：

更新拉格朗日乘子：

以上給出了利用ADMM 求解式（3）問(wèn)題的各個(gè)變量的迭代公式?；谏鲜龇治觯o出以下迭代算法：

輸入數(shù)據(jù)矩陣X，類別個(gè)數(shù)k，權(quán)衡參數(shù)α、λ1、λ2

輸出聚類標(biāo)簽

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

本文算法中更新變量J、Z、P、E1、E2的計(jì)算復(fù)雜度均為O(n2)，更新式（10）中鄰域關(guān)系矩陣C需要求解Sylvester方程，其計(jì)算復(fù)雜度為O(n3)，因此，算法總的計(jì)算復(fù)雜度為T(mén)1×O(n3)，其中T1為迭代次數(shù)。由文獻(xiàn)［18］可知，SRR 的計(jì)算復(fù)雜度為T(mén)2×O(n3)，其中T2代表迭代次數(shù)。通過(guò)對(duì)比發(fā)現(xiàn)，本文模型求解算法和SRR 模型求解算法的計(jì)算復(fù)雜度均為3階。

3 實(shí)驗(yàn)

在經(jīng)典數(shù)據(jù)集Extended Yale B［23］、ORL［24］、USPS［25］和MNIST［26］上進(jìn)行實(shí)驗(yàn)來(lái)驗(yàn)證本文方法的有效性。同時(shí)，將本文模型與SSC［6］、LRR［7］、LSR1［9］、LSR2［9］、SSSC［15］、BDR-B［14］、BDR-Z［14］和SRR［18］模型進(jìn)行比較。使用聚類錯(cuò)誤率作為性能評(píng)價(jià)指標(biāo)，其定義為誤分類數(shù)據(jù)點(diǎn)個(gè)數(shù)與數(shù)據(jù)點(diǎn)總數(shù)的比值。聚類錯(cuò)誤率越小，表示誤分類的數(shù)據(jù)點(diǎn)越少，聚類效果越好；反之亦然。

本文實(shí)驗(yàn)在Intel?CoreTMi7-9700 CPU@3.00 GHz處理器配置下，Matlab R2018b 環(huán)境中進(jìn)行。

3.1 參數(shù)分析

本文模型包含3 個(gè)權(quán)衡參數(shù)：α，λ1，λ2。參數(shù)α的取值越大，不同類別數(shù)據(jù)之間的自表示系數(shù)越小；參數(shù)λ1的取值大小決定了對(duì)原始數(shù)據(jù)奇異點(diǎn)進(jìn)行處理的程度，設(shè)置適當(dāng)?shù)膮?shù)λ1，可以有效去除數(shù)據(jù)樣本中的噪聲，減小噪聲對(duì)獲取數(shù)據(jù)的新特征的影響；參數(shù)λ2用于進(jìn)一步去除數(shù)據(jù)的新特征中的噪聲。在Extended Yale B上，各參數(shù)對(duì)聚類結(jié)果的影響如圖1所示。

圖1 Extended Yale B 數(shù)據(jù)集上聚類錯(cuò)誤率隨參數(shù)的變化Fig.1 Clustering error rate versus parameters on Extended Yale B dataset

圖1（a）是固定α=0.005，聚類錯(cuò)誤率隨另外2個(gè)參數(shù)變化的柱形圖?？梢钥闯觯疚哪Ｐ偷木垲愬e(cuò)誤率主要取決于參數(shù)λ1，當(dāng)λ1=0.5時(shí)，參數(shù)λ2取{0.001，0.005，0.01，0.05，0.1，0.5，1}中的任意值，聚類錯(cuò)誤率都處于較低水平，這表明相較于第2次自表示中的噪聲處理，第1次自表示對(duì)原始數(shù)據(jù)的噪聲適當(dāng)處理更為重要。

圖1（b）是固定λ1=0.5，聚類錯(cuò)誤率隨另外2個(gè)參數(shù)變化的柱形圖?？梢钥闯?，當(dāng)α=0.001或0.005時(shí)，本文模型的聚類錯(cuò)誤率較低，λ2取{0.001，0.005，0.01，0.05，0.1，0.5，1}中何值對(duì)聚類錯(cuò)誤率影響不大，這表明本文提出的正則項(xiàng)對(duì)聚類性能起到重要作用。

綜上可知，當(dāng)α=0.005、λ1=0.5、λ2=0.001時(shí)，本文模型的聚類錯(cuò)誤率最低，因此，將此組參數(shù)值作為參考經(jīng)驗(yàn)最優(yōu)參數(shù)。

3.2 人臉數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)為選用Extended Yale B 和ORL 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果與分析。圖2（a）和圖2（b）分別為Extended Yale B數(shù)據(jù)集和ORL 數(shù)據(jù)集的部分人臉圖像。

圖2 Extended Yale B 與 ORL 數(shù)據(jù)集部分人臉圖像Fig.2 Some face images of Extended Yale B and ORL datasets

Extended Yale B人臉數(shù)據(jù)集包含38個(gè)人的2 414幅人臉圖像，其中每人約有64幅不同光照和姿勢(shì)下的人臉圖像。對(duì)于Extended Yale B數(shù)據(jù)集，本文遵循文獻(xiàn)［27］中的數(shù)據(jù)處理過(guò)程：1）將每幅圖像下采樣到48×42 像素；2）將38人分為4個(gè)小組：1～10，11～20，21～30，31～38，對(duì)每組考慮2、3、5、8 個(gè)不同人的人臉圖像的所有組合，對(duì)前3 組的每組考慮10 個(gè)不同人的人臉圖像的所有組合。在此數(shù)據(jù)集上，SSC、LRR、LSR1、LSR2 和SSSC 模型的聚類錯(cuò)誤率數(shù)據(jù)參考文獻(xiàn)［27］。對(duì)BDR-B、BDRZ、SRR 和本文模型，通過(guò)選擇參數(shù)以達(dá)到最低的聚類錯(cuò)誤率，然后計(jì)算所有實(shí)驗(yàn)中聚類錯(cuò)誤率的平均值、中值和標(biāo)準(zhǔn)差。

ORL 人臉數(shù)據(jù)集包含40 人在不同時(shí)間、光照、表情、角度、是否配戴眼鏡等環(huán)境下拍攝的400 幅人臉圖像，其中每人有10 幅人臉圖像。對(duì)于ORL 數(shù)據(jù)集，考慮到降低計(jì)算時(shí)間和復(fù)雜度，本文將每幅圖像下采樣到32×32 像素。在此數(shù)據(jù)集上，調(diào)節(jié)參數(shù)使得模型效果達(dá)到最優(yōu)。

各模型在Extended Yale B 和ORL 數(shù)據(jù)集上的聚類錯(cuò)誤率如表1 所示，其中加粗表示最優(yōu)值。

表1 各模型在Extended Yale B 和ORL 數(shù)據(jù)集上的聚類錯(cuò)誤率 Table1 Clustering error rate of each model on Extended Yale B and ORL datasets %

由表1 可以看出，本文模型在2 個(gè)人臉數(shù)據(jù)集上均實(shí)現(xiàn)了比其他模型更低的聚類錯(cuò)誤率。雖然所有模型的聚類錯(cuò)誤率隨著類別數(shù)目的增加都呈升高趨勢(shì)，但其他模型迅速升高，而本文模型增高幅度較小，聚類錯(cuò)誤率穩(wěn)定在2%以內(nèi)，標(biāo)準(zhǔn)差也穩(wěn)定在1%以內(nèi)，表明隨著類別數(shù)目的增加，當(dāng)聚類問(wèn)題更具有挑戰(zhàn)時(shí)，本文模型更加魯棒。ORL 人臉數(shù)據(jù)集具有強(qiáng)非線性結(jié)構(gòu)，對(duì)聚類方法提出了更大的挑戰(zhàn)，但本文模型依舊實(shí)現(xiàn)了較對(duì)比模型更低的聚類錯(cuò)誤率，聚類性能更優(yōu)。為了更直觀地對(duì)比不同方法，在Extended Yale B 數(shù)據(jù)集上，根據(jù)表1 的結(jié)果繪制了折線圖，如圖3 所示，從中可以明顯看出，本文模型的聚類錯(cuò)誤率始終低于其他對(duì)比模型。

圖3 Extended Yale B 數(shù)據(jù)集上平均聚類錯(cuò)誤率與類別數(shù)目的關(guān)系Fig.3 Relationship between average clustering error rate and number of subjects on Extended Yale B dataset

3.3 手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集實(shí)驗(yàn)

USPS 和MNIST 是2 個(gè)常用的手寫(xiě)數(shù)字圖像數(shù)據(jù)集，USPS 和MNIST 均包含0～9 這10 個(gè)類別手寫(xiě)數(shù)字圖像，部分圖像如圖4（a）和圖4（b）所示。

圖4 部分手寫(xiě)數(shù)字圖像Fig.4 Some handwritten digital images

USPS 數(shù)據(jù)集包含9 298 幅手寫(xiě)數(shù)字圖像，每幅圖像的尺寸為16×16 像素。在此數(shù)據(jù)集上，利用每個(gè)手寫(xiě)數(shù)字的前100 幅圖像進(jìn)行實(shí)驗(yàn)，則可得到256×1 000 的數(shù)據(jù)矩陣。在MNIST 數(shù)據(jù)集上，取訓(xùn)練集每類手寫(xiě)字的前100 幅圖像。考慮到算法運(yùn)行時(shí)間，將每幅圖像下采樣到28×28 像素，展開(kāi)為一個(gè)784 維的向量，此時(shí)數(shù)據(jù)矩陣的大小為784×1 000。

各模型在USPS和MNIST數(shù)據(jù)集上的聚類錯(cuò)誤率如表2所示，其中加粗表示最優(yōu)值。可以看出，本文模型的聚類錯(cuò)誤率遠(yuǎn)小于其他模型，聚類性能最優(yōu)。

表2 各模型在USPS 和MNIST 數(shù)據(jù)集上的聚類錯(cuò)誤率 Table 2 Clustering error rate of each model on USPS and MNIST datasets %

3.4 運(yùn)行時(shí)間對(duì)比

各模型在4 個(gè)數(shù)據(jù)集中指定數(shù)據(jù)上的運(yùn)行時(shí)間如表3 所示?？梢钥闯觯航y(tǒng)一模型SSSC 花費(fèi)時(shí)間最多；LSR 模型（包括LSR1 和LSR2）花費(fèi)時(shí)間最少；本文模型和SRR 模型雖然都具有3 階計(jì)算復(fù)雜度，但本文模型在4 個(gè)數(shù)據(jù)集上的實(shí)際運(yùn)行時(shí)間均少于SRR 模型。

表3 各模型在4 個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間 Table 3 Runtime of each model on four datasets 單位：s

4 結(jié)束語(yǔ)

本文對(duì)SRR 模型進(jìn)行改進(jìn)，首先用平方F 范數(shù)取代核范數(shù)，避免核范數(shù)求解需要的奇異值分解，并獲得解析解；然后引入類別屬性增強(qiáng)的正則項(xiàng)，提高不同類別數(shù)據(jù)的自表示系數(shù)的判別性。在多個(gè)人臉以及手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集上的聚類結(jié)果表明，本文改進(jìn)模型的聚類性能優(yōu)于SSC、LRR、SSSC 等對(duì)比模型。下一步將考慮算法的收斂性，將模型擴(kuò)展應(yīng)用于多視角數(shù)據(jù)的子空間聚類問(wèn)題。