非凸張量多視圖子空間聚類

洪振寧,蘇雅茹

(福州大學(xué)計(jì)算機(jī)與大數(shù)據(jù)學(xué)院,福建 福州 350108)

0 引言

在實(shí)踐中,多視圖學(xué)習(xí)有著廣泛的應(yīng)用,傳統(tǒng)的機(jī)器學(xué)習(xí)算法,如譜聚類[1],將多個(gè)視圖串聯(lián)成一個(gè)視圖來進(jìn)行學(xué)習(xí).然而這種串聯(lián)缺乏物理意義,可能導(dǎo)致過擬合.與單視圖學(xué)習(xí)相比,多視圖學(xué)習(xí)引入了一個(gè)函數(shù)來模擬特定的視圖,并聯(lián)合優(yōu)化所有的函數(shù),以利用同一輸入數(shù)據(jù)的不同視圖提高學(xué)習(xí)性能.

在實(shí)際應(yīng)用中,高維數(shù)據(jù)增加了模型訓(xùn)練參數(shù)的數(shù)量,給硬件帶來了計(jì)算壓力,同時(shí)其廣泛的數(shù)據(jù)表現(xiàn)形式,也對魯棒性提出了挑戰(zhàn).子空間學(xué)習(xí)采用潛伏的低維特征組合來保留數(shù)據(jù)的基本信息,從而提高模型的訓(xùn)練效率.子空間學(xué)習(xí)中最具代表性的工作是低秩表示[2]和稀疏子空間聚類.

然而,這些方法往往具有較高的時(shí)間復(fù)雜度,并且只對矩陣進(jìn)行學(xué)習(xí).因此,張量結(jié)構(gòu)被引入,探索視圖之間的關(guān)聯(lián)[3].考慮到使用的是基于矩陣的奇異值分解(singular value decompostion,SVD)[4],其張量的物理意義并不明確,因此文獻(xiàn)[5]使用了具有物理意義的張量奇異值分解(singular value decompostion,t-SVD)代替了矩陣SVD,并引入了張量旋轉(zhuǎn)操作.近年來,為了進(jìn)一步減少噪聲的影響,文獻(xiàn)[6-9]將不同的圖學(xué)習(xí)方法與張量結(jié)構(gòu)相結(jié)合,即先對輸入的特征矩陣進(jìn)行不同的圖學(xué)習(xí),再將學(xué)習(xí)到的矩陣重構(gòu)為張量.但是仍存在一些不足,如所結(jié)合的魯棒圖與聯(lián)合圖不利于處理人臉數(shù)據(jù)集[6],采用tucker分解與領(lǐng)域自適應(yīng)增強(qiáng)了聚類效果但忽略了張量的空間特性[7].

以上算法往往使用凸函數(shù)來近似張量秩,但這種近似可能不是最優(yōu)的[10].本研究提出一種非凸張量多視圖子空間聚類(nonconvex tensor multi-view subspace clustering,NTMSC).通過非凸函數(shù)來近似張量秩,并結(jié)合廣義奇異值閾值算子(generalized singular value thresholding,GSVT)[11]進(jìn)行求解,目的是獲得更好的聚類結(jié)果.

1 非凸張量多視圖子空間聚類

1.1 非凸最小化

迭代重賦權(quán)核范數(shù)(iteratively reweighted nuclear norm,IRNN)[12]被提出來解決以下的非凸最小化問題:

(1)

其中：σi(X)代表矩陣X∈Rm×n的第i個(gè)奇異值.函數(shù)g:R+→R+是連續(xù)的、凹的并且在[0,+∞]上非遞增.h:Rm×n→R+是有Lipschitz連續(xù)梯度?的損失函數(shù).

目標(biāo)函數(shù)的一個(gè)更緊的替代是保持g的同時(shí)只松弛h.然后按如下規(guī)則更新,稱為廣義近端梯度(generalized proximal gradient,GPG) :

(2)

解決式(2)需要引入廣義奇異值閾值算子:

(3)

對于滿足g:R+→R+,g(0)=0,g是凹的、非遞減和可微的且梯度?g為凸的非凸函數(shù),文獻(xiàn)[11]提出了相應(yīng)GSVT的解法并且證明GPG是收斂的,作為更緊的一個(gè)替換,其下降速度優(yōu)于IRNN.

綜上,對GSVT進(jìn)行求解再根據(jù)GPG規(guī)則更新即可得到對于非凸最小化問題的解.本研究使用該解法來對張量的秩函數(shù)進(jìn)行近似,并將其應(yīng)用于多視圖子空間聚類問題以提高聚類效果.

1.2 目標(biāo)函數(shù)

本研究提出的非凸張量多視圖子空間聚類算法的目標(biāo)函數(shù)如下式所示：

(4)

(5)

(6)

其中:α和β為懲罰參數(shù)；P和Yi為拉格朗日乘子；T為輔助張量；M代表視圖數(shù).〈A,B〉代表內(nèi)積.

首先對表示矩陣和誤差矩陣進(jìn)行如下更新:

(7)

其中:P(i)和T(i)分別是張量P和T第i個(gè)正向切片；(·)T代表矩陣的轉(zhuǎn)置；I為單位矩陣.

(8)

(9)

最后對拉格朗日乘子Yi，以及懲罰參數(shù)α和β進(jìn)行更新:

Yi=Yi+α(X(i)-X(i)G(i)-E(i));α=min(θα,tol)β=min(θβ,tol)

(10)

其中:tol為預(yù)先設(shè)置的閾值;θ為學(xué)習(xí)率.

1.3 算法

表1 非凸張量多視圖子空間聚類Tab.1 Nonconvex tensor multi-view subspace clustering

2 實(shí)驗(yàn)分析

表2 實(shí)驗(yàn)數(shù)據(jù)集Tab.2 Datasets used in our experiments

本實(shí)驗(yàn)采用兩個(gè)不同類型的多視圖數(shù)據(jù)集,具體信息在表2中展示.對于每個(gè)數(shù)據(jù)集,分別采用LRR[2]、t-SVD-MSC[5]、ETLMSC[6]、CGL[9]、RMSC[13]、CGD[14]、CoMSC[15]7種算法進(jìn)行對比實(shí)驗(yàn).本實(shí)驗(yàn)使用6個(gè)指標(biāo)來評(píng)價(jià)聚類效果:歸一化互信息(normalized mutual information,NMI)、準(zhǔn)確度(accuracy,ACC)、調(diào)整的隨機(jī)指數(shù)(adjusted rand index,AR)、F-score、精確度(Precision)和召回率(Recall).對于所有方法,每個(gè)實(shí)驗(yàn)均重復(fù)10次,最后記錄平均值和方差.

圖1為滿足收斂條件時(shí)學(xué)習(xí)到的相似性矩陣的可視化圖像.圖2為固定參數(shù)λ對參數(shù)μ進(jìn)行調(diào)整所對應(yīng)的指標(biāo)值變化圖像.表3～4 分別記錄了本研究方法在6個(gè)指標(biāo)上的聚類表現(xiàn),其中表3中的數(shù)據(jù)在λ=0.01且μ=15時(shí)取得,表4的數(shù)據(jù)在λ=1.3且μ=5時(shí)取得.

最終相似性矩陣代表各視圖所共享的子空間.從圖1中可以觀察到,學(xué)習(xí)到的相似性矩陣中多數(shù)較大的值都聚集在對角分塊上,說明本研究的方法獲取到了更豐富的聚類信息,有利于提升聚類效果,表3～4中的聚類結(jié)果也證實(shí)了這一點(diǎn).圖2表明,式(5)中對于參數(shù)μ的引入是有必要的,一個(gè)好的μ可以更好地對張量秩進(jìn)行近似,需注意對于不同類型數(shù)據(jù)集最優(yōu)值的區(qū)間會(huì)有所不同.

從表3～4中可以看出,相比單視圖算法LRR,多視圖算法t-SVD-MSC挖掘了視圖之間的互補(bǔ)性與一致性信息而具有更好的表現(xiàn).另外對比RMSC和ETLMSC可知張量結(jié)構(gòu)由于探索高維空間關(guān)聯(lián)能加強(qiáng)效果.同時(shí),不同相似性矩陣學(xué)習(xí)方式對聚類結(jié)果也有影響,比如ETLMSC和RMSC均采用基于魯棒圖的轉(zhuǎn)移概率矩陣而在人臉數(shù)據(jù)集上表現(xiàn)不佳,而CGL構(gòu)造一致性圖并與低秩張量結(jié)合明顯具有更好的效果.本研究方法對比各算法均有明顯提升,不僅由于結(jié)合了低秩表示和張量旋轉(zhuǎn)操作,更是因?yàn)槭褂胠og函數(shù)對張量秩進(jìn)行非凸近似,更好地利用了張量的性質(zhì).

圖1 相似性矩陣的可視化Fig.1 Visualization of learned similarity matrix

圖2 參數(shù)μ對聚類效果的影響Fig.2 Clustering result by tuning parameter μ

表3 COIL-20數(shù)據(jù)集上的聚類表現(xiàn)Tab.3 Clustering result on COIL-20

表4 Extended YaleB數(shù)據(jù)集上的聚類表現(xiàn)Tab.4 Clustering result on Extended YaleB

3 結(jié)語

通過在兩個(gè)不同類型的多視圖數(shù)據(jù)集上的實(shí)驗(yàn),得出以下結(jié)論:1) 多視圖聚類算法相對于單視圖聚類算法因?yàn)樘剿髁硕嘁晥D間的互補(bǔ)性和一致性具有更好的性能；2) 使用張量結(jié)構(gòu)學(xué)習(xí)多視圖間的空間關(guān)聯(lián),引入張量旋轉(zhuǎn)操作并使用側(cè)向切片進(jìn)行實(shí)驗(yàn)可以取得相對好的結(jié)果；3) 使用非凸方法代替凸優(yōu)化來近似張量秩可以獲取更多視圖間的關(guān)聯(lián)信息.