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

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

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

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

1 引言

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

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

2 本文方法

2.1 自表示的子空間聚類

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

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

2.2 低秩約束

正如前面討論的,對于高維數(shù)據(jù),構(gòu)造一個低秩的矩陣可以很好地捕獲數(shù)據(jù)的特征.Liu 等[12]提出了用于單視圖數(shù)據(jù)的低秩表示方法,即將數(shù)據(jù)樣本表示為基的線性組合,然后從這些候選對象中尋找最低的秩表示.本文將它擴展到多個視圖,也就是每個視圖數(shù)據(jù)都進行最低秩表示,如式(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ù)表征能力的差異性,表征能力強的數(shù)據(jù)可以很好助力聚類,而表征能力差的數(shù)據(jù)含有大量噪聲和冗余特征阻礙了聚類性能.因此,我們利用了加權(quán)的方法來融合得到潛在一致矩陣Z,如式(4)為本文提出的目標函數(shù).

3 優(yōu)化

式(4)是典型的低秩優(yōu)化問題,本文利用了增廣拉格朗日乘子法來進行優(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)：

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

3.3 更新E(v)

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

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

3.4 更新Z

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

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

3.5 更新Π

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

3.6 更新拉格朗日乘子

算法1.優(yōu)化過程輸入：多視圖數(shù)據(jù)集X={X(1),…,X(V)},類簇數(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 收斂或達到最大迭代次數(shù)輸出：Z.

4 實驗

4.1 數(shù)據(jù)集及評價指標

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

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

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

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

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

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

另外,本文采用了兩個通用的聚類評價指標ACC和NMI 來對實驗結(jié)果進行評價.

4.2 比較實驗及討論

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

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

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

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

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

5 總結(jié)與展望

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

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