自適應(yīng)加權(quán)低秩約束的多視圖子空間聚類算法①

劉金花,岳根霞,王 洋,賀瀟磊

1(山西醫(yī)科大學(xué)汾陽學(xué)院,汾陽 032200)

2(北方自動(dòng)控制技術(shù)研究所,太原 030006)

1 引言

在實(shí)際應(yīng)用中將來自多個(gè)源或者通過不同的采集器采集到的數(shù)據(jù),稱為是多視圖數(shù)據(jù)[1].例如,我們可以通過人臉、指紋、簽名或虹膜來進(jìn)行人物識(shí)別；通過顏色、紋理或圖注特征來表示一張圖像.多視圖聚類就是利用隱藏在多個(gè)視圖數(shù)據(jù)中的互補(bǔ)信息和一致信息來提高聚類性能[2,3].最直接的方式就是將多視圖數(shù)據(jù)的特征進(jìn)行簡(jiǎn)單拼接,然后執(zhí)行單視圖聚類算法.然而,在實(shí)際應(yīng)用中,特別是多媒體領(lǐng)域,每個(gè)視圖的數(shù)據(jù)都是一個(gè)高維的特征空間,將各視圖特征拼接顯然會(huì)帶來“維度詛咒”.另外,對(duì)于高維數(shù)據(jù),特征分布通常更稀疏,傳統(tǒng)歐式距離來進(jìn)行相似性度量的方法根本不適用[4].為了解決這個(gè)問題,本文使用了低秩約束的方法從高維數(shù)據(jù)中學(xué)習(xí)低維的子空間,這樣既縮減了計(jì)算的復(fù)雜度,也提高了對(duì)噪聲數(shù)據(jù)的魯棒性.

另外,目前的多視圖聚類方法主要分為基于潛在一致信息、基于多樣互補(bǔ)信息和綜合潛在一致和互補(bǔ)信息三大類.這些方法都有一個(gè)共同的缺點(diǎn),它們平等的對(duì)待各視圖.由于各視圖表征數(shù)據(jù)的能力有強(qiáng)弱之分,故賦予各視圖不同的權(quán)重更具合理性[5].洪敏等[6]考慮到不同樣本存在的“全局”信息的差異,提出了樣本加權(quán)的K-means 多視圖聚類算法；Xu 等[7]提出了在各視圖間和視圖內(nèi)特征都進(jìn)行加權(quán)的K-means 多視圖聚類算法；聶飛平等致力于研究自動(dòng)加權(quán)的多圖學(xué)習(xí)模型,主要有AMGL[8]和SwMC[9]模型,還有Huang和Wang 等[10,11]提出無需引入任何權(quán)值和懲罰參數(shù)自動(dòng)為各視圖分配權(quán)重的多視圖聚類算法,但這些方法主要是針對(duì)基于K-means 或基于圖的多視圖聚類.本文針對(duì)基于子空間的多視圖聚類方法提出的自適應(yīng)權(quán)重學(xué)習(xí)方法,在目標(biāo)函數(shù)中設(shè)置了權(quán)重參數(shù),且在函數(shù)優(yōu)化的過程中以自動(dòng)學(xué)習(xí)的方式同時(shí)優(yōu)化各權(quán)值.

2 本文方法

2.1 自表示的子空間聚類

自表示的子空間聚類可以有效處理高維數(shù)據(jù),它是基于這樣的假設(shè)：空間中的任何數(shù)據(jù)點(diǎn)都可以通過其他樣本點(diǎn)的線性組合得到.設(shè)X(v)=Rdv×n為第v個(gè)視圖的數(shù)據(jù)矩陣,其中每一列為一個(gè)樣本,dv為特征空間的維度.自表示方式的子空間聚類方程如下所示：

其中,L (·,·) 表示數(shù)據(jù)重構(gòu)的誤差損失函數(shù),Ω (·)表示正則項(xiàng),并且λ用于平衡公式中的兩項(xiàng).Z(v)為潛在的自表示系數(shù)矩陣,當(dāng)求得Z(v)后,就可以通過式(2)來得到用于譜聚類輸入的親鄰矩陣S.

2.2 低秩約束

正如前面討論的,對(duì)于高維數(shù)據(jù),構(gòu)造一個(gè)低秩的矩陣可以很好地捕獲數(shù)據(jù)的特征.Liu 等[12]提出了用于單視圖數(shù)據(jù)的低秩表示方法,即將數(shù)據(jù)樣本表示為基的線性組合,然后從這些候選對(duì)象中尋找最低的秩表示.本文將它擴(kuò)展到多個(gè)視圖,也就是每個(gè)視圖數(shù)據(jù)都進(jìn)行最低秩表示,如式(3)所示.

2.3 加權(quán)融合

由于多視圖數(shù)據(jù)描述的是同一事物,所以這些視圖數(shù)據(jù)有潛在相同的數(shù)據(jù)結(jié)構(gòu)[13],那么多視圖聚類的目的就是要從不同視圖數(shù)據(jù)中挖掘出潛在一致的數(shù)據(jù)結(jié)構(gòu).類似的,本文假設(shè)潛在一致數(shù)據(jù)結(jié)構(gòu)Z是由各視圖低秩表示Z(v)線性組合得到的.另外,考慮到數(shù)據(jù)的噪聲、缺失等因素,還有不同視圖數(shù)據(jù)表征能力的差異性,表征能力強(qiáng)的數(shù)據(jù)可以很好助力聚類,而表征能力差的數(shù)據(jù)含有大量噪聲和冗余特征阻礙了聚類性能.因此,我們利用了加權(quán)的方法來融合得到潛在一致矩陣Z,如式(4)為本文提出的目標(biāo)函數(shù).

3 優(yōu)化

式(4)是典型的低秩優(yōu)化問題,本文利用了增廣拉格朗日乘子法來進(jìn)行優(yōu)化.為了變量可分,引入了輔助變量R(v)代替Z(v)得到式(5).

3.1 更新R(v)

固定除R之外的其他所有變量,得到關(guān)于R的子問題如式(7)：

上式可以通過奇異值閾值法[14]來求解如式(8),獲得閉形式的解.其中Sτ[·]是收縮閾值操作符.

3.2 更新Z(v)

固定除Z(v)之外的其他所有變量,得到關(guān)于Z(v)的子問題如式(9)：

對(duì)式(9)求關(guān)于Z(v)的導(dǎo)數(shù),并令其為0,得到了下面的優(yōu)化解.

3.3 更新E(v)

固定除E之外的所有變量,得到關(guān)于E的子問題如式(11)：

參照文獻(xiàn)[12]中引理3.3 得到下面的優(yōu)化解.

3.4 更新Z

固定除Z外的其他變量,得到了關(guān)于Z的子問題：

對(duì)式(13)求關(guān)于Z的導(dǎo)數(shù),并令其為零,得到了下面的優(yōu)化公式：

3.5 更新Π

固定Π 之外的其他變量,得到了關(guān)于Π 的子問題.

3.6 更新拉格朗日乘子

算法1.優(yōu)化過程輸入：多視圖數(shù)據(jù)集X={X(1),…,X(V)},類簇?cái)?shù)k,參數(shù),最大迭代次數(shù)maxIter,,ρ=1.1.1：Repeat 2：For v∈V do R(v)λ,γμmax=106 3：利用求解式(8)更新4：利用求解式(10)更新Z(v)E(v)5：利用求解式(12)更新6：利用求解式(16)更新權(quán)重Π Y1(v) Y2(v)7：利用式(17)更新拉格朗日乘子,8：end 9：利用求解式(14)更新Zμ=min(ρμ,μmax)10：更新11：Until 收斂或達(dá)到最大迭代次數(shù)輸出：Z.

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

4.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

為了驗(yàn)證所提多視圖聚類算法的有效性,本文選取了5 個(gè)公開的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),各數(shù)據(jù)集描述如下：

(1)Digits 數(shù)據(jù)集包含2000 張手寫的0-9 數(shù)字圖像數(shù)據(jù),每個(gè)數(shù)字包含200 條樣本,共有6 個(gè)視圖.本實(shí)驗(yàn)選擇了Fourier 和pixel 兩個(gè)視圖.

(2)Caltech101-7 是一個(gè)廣泛使用的圖像數(shù)據(jù)集,包含7 個(gè)類別共441 張圖像,由CENTRIST、CMT、GIST、HOG、LBP 和SIFT 6 個(gè)視圖組成.

(3)3-source 數(shù)據(jù)集包含BBC、Reuters 和Guardian 3 個(gè)源的新聞數(shù)據(jù),共169 條分為6 個(gè)類別.

(4)WebKB 數(shù)據(jù)集包含Texas、Cornell、Washington和Wisconsin 4 個(gè)大學(xué)的網(wǎng)頁數(shù)據(jù).每個(gè)網(wǎng)頁由內(nèi)容、鏈入信息、視角和城市4 個(gè)視圖.由于4 個(gè)子數(shù)據(jù)集是相似的,本文采用了Texas 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),它包含187 條樣本共5 個(gè)類別.

(5)MRSCV1 數(shù)據(jù)集包含240 張共8 個(gè)類別的圖像,本實(shí)驗(yàn)選擇常用的牛、樹、建筑、飛機(jī)、人臉、汽車和自行車7 個(gè)物體,包含與Caltech101-7 數(shù)據(jù)集相同的6 個(gè)視圖.

另外,本文采用了兩個(gè)通用的聚類評(píng)價(jià)指標(biāo)ACC和NMI 來對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià).

4.2 比較實(shí)驗(yàn)及討論

將所提算法與現(xiàn)有相關(guān)算法進(jìn)行比較,包括單視圖的子空間聚類模型(LRR)、協(xié)同正則的多視圖譜聚類模型(CoregSPC)[15]還有潛在的多視圖子空間聚類模型(LMSC)[16].對(duì)于單視圖的LRR 模型,我們進(jìn)行了兩次實(shí)驗(yàn),在每個(gè)視圖上執(zhí)行LRR 算法,從得到的結(jié)果中取最好的記為LRR_best；另外,我們將各視圖的特征進(jìn)行直接拼接后,在其上執(zhí)行LRR 算法,得到的結(jié)果記為LRR_catFea.對(duì)于比較算法,涉及到的參數(shù)都按照原論文中作者建議的值進(jìn)行設(shè)置.另外,為了避免算法中隨機(jī)初始化引起的誤差,每個(gè)算法在各數(shù)據(jù)集上都重復(fù)進(jìn)行10 次實(shí)驗(yàn),然后取均值作為最后結(jié)果.表1就是各算法在相應(yīng)數(shù)據(jù)集上的聚類準(zhǔn)確率和NMI 值.

表1 各算法在5 個(gè)公開數(shù)據(jù)集上的ACC 和NMI 值

從表中可以看出本文所提算法在5 個(gè)公開的數(shù)據(jù)集均優(yōu)于其他的模型,可見算法發(fā)揮出了它應(yīng)有的效果,將表征能力強(qiáng)的視圖賦予了大的權(quán)重,且摒棄了冗余的特征和噪聲特征.

4.3 參數(shù)敏感性分析

在所提算法中存在λ和γ兩個(gè)參數(shù),我們采用網(wǎng)格搜索的策略來選擇最優(yōu)的參數(shù)組合,設(shè)置λ的取值范圍均為[10-4,104],γ的取值范圍為[1,105],圖1分別展示了兩個(gè)參數(shù)在設(shè)定范圍內(nèi)所提算法在3 個(gè)數(shù)據(jù)集上的準(zhǔn)確率和NMI 值.從圖中可以看出參數(shù)在給定的范圍內(nèi)對(duì)應(yīng)的ACC 與NMI 值變化都不是特別大,說明該算法在給出的取值范圍內(nèi)對(duì)參數(shù)λ和γ不敏感；不過從MRSCV1 和3-sources 數(shù)據(jù)集的結(jié)果可以看出γ取值在[1,105],λ取[10-2,102]聚類結(jié)果相對(duì)較好,故在其他數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)時(shí),我們固定γ值為10,然后讓?duì)巳10-2,102].

5 總結(jié)與展望

文章提出了一個(gè)低秩約束的自適應(yīng)權(quán)重的多視圖子空間聚類算法,由于高維數(shù)據(jù)的特征分布比較稀疏,所以利用低秩約束來進(jìn)行各視圖子空間的自表示矩陣,然后學(xué)習(xí)各視圖共享的潛在一致數(shù)據(jù)結(jié)構(gòu),另外,在尋找各視圖的一致結(jié)構(gòu)時(shí)對(duì)各視圖設(shè)置權(quán)值,在算法優(yōu)化的過程中該權(quán)值會(huì)隨著目標(biāo)函數(shù)優(yōu)化.在公開的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)證明了所提算法的優(yōu)越性.

圖1 在MRSCV1、WebKB 和3-sources 數(shù)據(jù)集上參數(shù)λ 和γ 取不同值時(shí)的聚類ACC 和NMI 值