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

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

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

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

1 引言

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

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

2 本文方法

2.1 自表示的子空間聚類

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

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

2.2 低秩約束

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

2.3 加權融合

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

3 優化

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

3.1 更新R(v)

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

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

3.2 更新Z(v)

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

對式(9)求關于Z(v)的導數,并令其為0,得到了下面的優化解.

3.3 更新E(v)

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

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

3.4 更新Z

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

對式(13)求關于Z的導數,并令其為零,得到了下面的優化公式：

3.5 更新Π

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

3.6 更新拉格朗日乘子

算法1.優化過程輸入：多視圖數據集X={X(1),…,X(V)},類簇數k,參數,最大迭代次數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)更新權重Π Y1(v) Y2(v)7：利用式(17)更新拉格朗日乘子,8：end 9：利用求解式(14)更新Zμ=min(ρμ,μmax)10：更新11：Until 收斂或達到最大迭代次數輸出：Z.

4 實驗

4.1 數據集及評價指標

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

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

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

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

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

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

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

4.2 比較實驗及討論

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

表1 各算法在5 個公開數據集上的ACC 和NMI 值

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

4.3 參數敏感性分析

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

5 總結與展望

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

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