基于低秩張量圖學習的不完整多視角聚類

文 杰 顏 珂 張 正,3 徐 勇, 3

聚類是機器學習領域的重要研究方向之一,旨在將一組無標簽信息的數據劃分為一些合理的類別[1].近年來,便利的數據獲取技術使得實際應用中待處理的數據呈現多樣化的表現形式,如多媒體數據存在音頻、視頻、圖像和文字等異構信息;醫療病例中含有多種醫療設備采集到的數據信息.在機器學習領域,由多種數據傳感器或從不同源域、不同角度以及不同特征提取器所獲取到的多樣化數據統稱為多視角數據.多視角數據包含客觀物體更完整的信息,反映了客觀物體的不同特性[2-3].因此,若能有效利用多個視角的信息,將獲得比單視角方法更精確的聚類結果.基于此,許多研究人員投入到多視角聚類研究并提出諸如多視角K-means 聚類[4]、多視角模糊聚類[5]、基于多視角矩陣分解的聚類[6]以及多視角一致圖聚類[7]等方法.雖然這些方法普遍獲得比單視角聚類更好的性能,但是這些方法都基于視角完備性假設,要求待處理的多視角數據不能存在視角缺失情形[8].事實上,視角缺失下的非完整多視角數據在近年來許多實際應用場景中十分普遍,如在基于核磁共振、正電子成像技術和腦脊液數據信息的阿爾茲海默癥診斷中,許多人通常只含有其中一種或兩種數據信息[9].在推薦系統中,客戶普遍存在信息不完整現象[10].此外,在多媒體分析、文檔分析或多語言文本分析任務中也存在視角缺失的情形[11-12].視角缺失不僅造成信息損失,而且引起了如下3 個問題: 1)破壞多視角數據的匹配結構;2)加劇視角間信息的不平衡;3)造成樣本信息失衡.這些因素使得不完整多視角聚類具有一定的挑戰性.

雖然傳統多視角聚類方法可通過刪除含有缺失視角的樣本或對缺失視角信息進行填充的方式來使得其模型得以執行,但是這兩種方式顯然不合理[13-14].近10 年來學者們針對不完整多視角聚類問題進行了研究并提出了許多方法.例如,Trivedi 等[15]提出了基于核相關性分析的不完整核矩陣恢復方法,該方法的缺陷是只能處理兩個視角的數據集,而且要求其中一個視角完備.隨后基于矩陣分解的方法得以拓展到不完整多視角聚類,其中比較典型的方法有: 局部多視角聚類 (Partial multi-view clustering,PMVC)[14]、多個不完整視角聚類 (Multiple incomplete-views clustering,MIC)[16]、雙對齊不完整多視角聚類 (Doubly aligned incomplete multiview clustering,DAIMC)[17]、在線不完整多視角聚類 (Online multi-view clustering with incomplete views,OMVC)[10]和單趟不完整多視角聚類 (Onepass incomplete multi-view clustering,OPIMC)[18]

等.PMVC 建立了局部對齊不完整多視角矩陣分解模型,利用含有完整視角的部分樣本的對齊信息來約束模型以得到視角間的共同表征.該方法的缺陷是僅適于處理部分樣本含有完整視角且剩余樣本僅含有其中一個視角的不完整多視角數據聚類任務.不同于PMVC,MIC、DAIMC、OMVC和OPIMC等方法引入加權矩陣分解技術,首先利用樣本均值或零向量來填充缺失的視角以對齊多視角數據,然后引入基于視角缺失先驗位置信息的預定義對角矩陣來約束多視角共同表征學習模型,進而實現任意視角缺失下的多視角聚類.此外,為了處理大規模數據的聚類問題,OMVC和OPIMC 還提出了區塊分解優化方案.總的來說,這些方法在傳統矩陣分解的多視角聚類模型的基礎上,通過引入視角缺失信息的先驗矩陣約束,讓模型僅利用未缺失視角的信息來學習共同表征矩陣,進而削弱視角缺失所造成的負面影響.基于視角間的語義一致性,統一嵌入對齊框架 (Unified embedding alignment framework,UEAF),建立了一個缺失視角恢復和共同表征學習的聯合模型[19].該方法的不足之處是要求各視角的特征維度高于數據類別數.除上述方法外,一些基于圖學習和核學習的方法也被拓展來解決不完整多視角學習問題,其中代表性的方法有: 基于自適應圖學習的不完整多視角譜聚類 (Incomplete multi-view spectral clustering with adaptive graph learning,IMVSC_AGL)[20]和基于核補全的不完整多核K-means (Incomplete multiple kernel K-means with incomplete kernels,IMKKM-IKMKC)[21].這兩種方法將特征空間的視角缺失問題轉換到流形空間的樣本關聯信息缺失問題,利用未缺失樣例間的相似度來獲得數據的共同表征,以實現任意視角缺失下的多視角聚類.

雖然上述方法為不完整多視角聚類問題提供了解決方案,但是還存在以下局限: 1)未能挖掘和利用數據間最優的相似度信息,如基于矩陣分解的方法普遍忽略了數據間的近鄰結構信息;2)現有方法普遍僅利用未缺失視角的特征或近鄰結構信息,忽略了缺失視角的信息,如IMVSC_AGL 這種基于圖的方法忽略了與缺失視角相關聯的樣本相似度信息.為了解決以上兩個問題,本文提出一種基于低秩張量圖學習的不完整多視角聚類方法,該方法不僅能夠有效地利用視角間的信息和視角內的信息,而且能挖掘不同視角的相似圖間的高階相關性,實現缺失樣例間的鄰接元素補全,進而得到更合理的聚類指示表征.

本文主要貢獻簡述如下: 1)針對不完整多視角聚類問題,提出了一種靈活的基于圖學習的聚類方法,能夠處理任意視角缺失下的聚類問題;2)與現有方法相比,所提出的方法建立了缺失圖元素自適應補全和最優共同表征學習的聯合框架,能夠得到數據間正確的鄰接關系和最具可分性的聚類表征;3)在多個數據集上的實驗驗證了所提出的方法在相似圖補全和不完整多視角聚類上的優越性和有效性.

1 相關知識

1.1 符號定義

1.2 張量相關基礎運算

其中,Af為張量A沿著第3 個維度的快速傅里葉變換結果,Sf(i,i,k)為張量Af的張量奇異值分解后的第k個正面切片的第i個奇異值.

2 本文方法

本節主要介紹一種基于低秩張量圖學習的不完整多視角聚類模型 (Low-rank tensor graph learning,LASAR),其模型框圖如圖1 所示.該方法根據各個不完整視角的相似圖信息,通過聯合挖掘多視角數據的互補信息來補全不完整相似圖的缺失信息,進而得到最優的聚類共同表征.其中關于不完整多視角聚類的具體定義表述如下.

圖1 基于低秩張量圖學習的不完整多視角聚類框圖Fig.1 The flow chart of the low-rank tensor graph learning based incomplete multi-view clustering

圖2 多視角樣本分布典型范例,其中 表示a、b兩樣本的第 v 個視角特征的相似度Fig.2 Example of the distribution of multi-view samples,where denotes the similarity degree of samples a and b in the v -th view

2.1 基于低秩張量圖學習的不完整多視角聚類模型

基于圖的譜聚類是多視角聚類領域的重要分支之一,其不僅能夠處理非線性流形結構(線性不可分)的數據聚類問題,而且對噪聲和視角特征維度失衡問題具有一定的魯棒性.傳統基于圖的多視角譜聚類模型可表示為

對于多視角數據而言,其視角間不僅存在一致聚類信息,而且存在豐富的互補信息.此外,對于每個樣本而言,盡管其缺失多個視角,但至少其某一個視角內必然存在一個樣例.因此,可根據該視角內的樣例鄰接信息來推斷該樣本與其他樣本在其他視角的關聯信息,進而實現各視角不完整相似圖的自適應補全.基于此思想,本文設計了如下自適應圖補全和聚類表征學習聯合模型

從模型(2)可以發現,通過引入二值約束矩陣W(v),LASAR 能夠有效地利用各個視角內的未缺失樣例間的有效鄰接信息Z(v)來得到完整的相似圖.而張量低秩約束項‖S‖?和共同表征學習項將使得模型充分考慮視角間的互補信息和一致信息,進而得到數據間最正確的鄰接關系和最優的聚類指示矩陣.此外,共同表征學習項能促使模型獲得具有c個連通分量的最優且最適于聚類的相似圖S(v)[7].

2.2 模型優化

由于優化問題(2)含有多個變量,難以直接求得其解析解,本部分采用交替迭代優化算法,通過逐一求解各變量優化子問題,進而得到問題(2)的最優解.首先,為便于問題(2)中各變量的優化,引入如下變量A

優化問題(2)等價于優化問題(3),其中問題(3)可進一步改寫為

其中,C為與張量S具有同樣維度的張量,由l個矩陣C(v)Rn×n(1≤v ≤l) 組成.μ是懲罰項參數.

關于問題(4)的詳細優化過程如下.

步驟1.求變量S(v).由問題(4)可知,當固定變量U、A和C時,關于變量S(v)的優化問題退化為

步驟2.求變量U.將除變量U以外的所有變量視為已知量,此時模型(4)將退化為如下關于特征值分解的優化問題

步驟3.求變量A.在將S(v)、U和C視為已知量時,問題(4)退化為如下典型的張量低秩優化問題

問題(10)可通過張量奇異值分解進行求解[22-23].其封閉解可表示為

μ的更新式可表示為

其中,ρ和μ0為常數.

至此,問題(4)的未知變量均已求得.算法1 總結了上述優化過程.

算法 1.問題的優化過程

2.3 計算復雜度分析

鑒于諸如矩陣加、減、乘及元素點除和點乘等矩陣基本運算的計算時間相對較少,因此,在本部分對問題(4)的優化算法的計算復雜度分析中,并不考慮這些基本運算的計算復雜度.從第2.2 節的介紹可以發現,步驟1和步驟4 僅包含上述簡單的矩陣運算,因此其計算復雜度可忽略.步驟2 中計算復雜度較高的運算為矩陣特征值分解運算.對于維度為n×n的矩陣,可利用eigs 函數來快速地求得其最小的c個特征值所對應的特征向量,該過程的計算復雜度為 O(cn2)[25].因此,步驟2 的計算復雜度大約為 O(cn2).在步驟3 中,具有較高計算復雜度的運算為傅里葉變換、傅里葉逆變換和張量奇異值分解運算等.對于維度為n×l×n的張量矩陣,傅里葉變換和逆變換的計算復雜度大約為 O(l×n2log(n)),張量奇異值分解的計算復雜度為 O(l2n2)[23].因此,步驟3 的計算復雜度大約為 O(l×n2log(n)+l2n2).綜上分析,算法1 的計算復雜度大約為O(τ(l×n2log(n)+l2n2+c×n2)),其中,τ為算法總的迭代步數.

2.4與相關方法之間的聯系和區別

IMVSC_AGL、基于光譜擾動的不完整多視角聚類 (Spectral perturbation-oriented incomplete multi-view data,PIC)[26]以及生成式不完整多視角聚類 (Generative model for partial multi-view clustering,GM-PMVC)[22]是近年來較先進的基于圖學習的不完整多視角聚類方法.這3 種方法和本文所提出方法都利用各視角未缺失的樣例之間的鄰接關系來獲取視角的共同鑒別表征,區別和聯系之處在于: 1) IMVSC_AGL 僅利用視角間未缺失樣例之間的相似度信息來學習共有表征矩陣.2) PIC從預定義的近鄰相似圖的拉普拉斯矩陣中學習視角間一致的拉普拉斯矩陣來聚類.在該方法中,每個預構建的相似圖中的缺失鄰接信息由其他視角的鄰接信息的均值來填充,該操作會引入錯誤干擾信息.3) GM-PMVC和本文所提出的方法都采用低秩張量約束來挖掘多視角相似圖的高階關聯信息1三階以上的張量通常稱之為高階張量,在高階張量空間挖掘的信息稱之為高階信息[3,22].,但是GMPMVC 方法采用的是特征級的視角特征恢復策略,且其目的是學習多個具有視角間差異性的相似圖來聚類;而本文方法的目的是利用視角間的互補信息和一致信息得到各視角最優的相似圖和視角間一致的聚類表征.

3 實驗

本節將通過在真實數據集上的實驗來驗證所提出的LASAR 算法的有效性,其中聚類性能的評價指標為聚類準確度(Accuracy,ACC)、歸一化互信息(Normalized mutual information,NMI)和純度(Purity)[20].在實驗中,本文方法的相似圖Z(v)初始化為各視角未缺失樣例中構建的K 近鄰圖,其元素值通過高斯核計算,近鄰參數設置為15.

3.1 實驗設置

3.1.1 數據集

數據集包括: 1) Caltech7.Caltech7 數據集包含7 類目標和1 474 個樣本.其樣本來源于有名的目標識別數據庫Caltech101[27].Li 等[28]提取每幅圖像的Gabor、小波矩、統計變換直方圖 (Census transform histogram,CENTRIST)、HOG (Histogram of oriented gradient)、GIST (Generalized search tree)和LBP (Local binary pattern) 等特征構成6 個視角數據.2) BBCSport.傳統BBCSport 數據集包含737 個從BBCSport 網站所收集的文檔,這些文檔含有 2～4 個視角表征,隸屬于田徑、板球、足球、橄欖球和網球等5 種體育運動類新聞[29].在本實驗中,選取其中116 個含有完整4 個視角的樣本來對比各算法的性能.3) Handwritten[30].Handwritten 多視角數據集包含2 000 個樣本和10個數字類別(0～9),其中每個樣本含有傅里葉系數、Profile 相關性、Karhunen-Love 系數、窗口像素均值特征、Zernike 矩特征和形態學特征等6 種視角特征.在本實驗中,選取其前5 個特征視角來驗證各算法在不完整多視角聚類任務上的有效性.4) Animal[31].原始Animal 數據集包含30 475 幅圖像和50 個類別.在本實驗中,參考文獻[32],選取其中含有10 158 個樣本和50 個類別的子集進行實驗對比,其中每個樣本含有DECAF (Deep convolutional activation feature)[33]和VGG (Visual geometry group)[34]兩種深度網絡所提取的特征.5) Reuters[35].Reuters 是一個大尺度多語種的文檔數據集,每個文檔含有英語、法語、德語、西班牙語和意大利語等5 種表現形式.本實驗中選取其中包含英文和法文兩個視角的18 758 個文檔來驗證本文方法的有效性.

3.1.2 對比算法

對比算法包含前面所介紹的MIC、OMVC、DAIMC、OPIMC、UEAF、IMKKM-IK-MKC、IMVSC_AGL和GM-PMVC 等較為先進的不完整多視角聚類方法以及基于多視角非負矩陣分解的聚類方法 (Multi-view nonnegative matrix factorization,MultiNMF)[36]和基于質心的協同正則化(Centroid-based co-regularization multi-view spectral clustering,CCo_MVSC)[37]兩種知名的完整多視角聚類基準算法.其中,MultiNMF 采用矩陣分解技術得到多視角數據的共同表征;而CCo_MVSC 根據多視角數據的相似圖矩陣信息,利用譜聚類方法得到捕獲其數據流形結構的共同表征.對于MultiNMF,缺失視角分別用如下兩種方式填充:一種用所對應的視角的均值樣本填充;另一種方法參考文獻[38-39]采用K 近鄰方法進行填充.這兩種方法分別稱為 “MultiNMF+均值”和“MultiNMF+KNN”.在實驗中,CCo_MVSC 也采用兩種缺失視角填充方式: 一種是先構建核矩陣,然后將缺失樣例所關聯的核矩陣元素置為0;另一種是先采用K近鄰方法補全缺失視角,然后構建核矩陣.

3.1.3 不完整多視角數據集的構建

在保證每個樣例至少含有一個視角特征的前提條件下,隨機刪除Caltech7、BBCSport和Handwritten 三個數據庫中各視角p% 的樣例,以構成含有p% 視角缺失率的不完整多視角數據集.對于Animal和Reuters 數據集,首先隨機選取p% 個樣本作為含有完整視角的樣本;然后針對剩余樣本,隨機刪除其中一半樣本的第二視角特征,接著刪除剩余一半樣本的第一視角特征,以構成含有p% 視角配對率的不完整多視角數據集.

3.2 聚類實驗結果和分析

各不完整多視角聚類方法在上述數據集上的實驗對比結果如表1、表2和圖3 所示.其中,所列的值為這些方法在同樣的多組隨機生成的不完整多視角數據上的實驗結果的均值.從實驗結果中可發現:1) CCo_MVSC+KNN/零值、UEAF、IMVSC_AGL、GM-PMVC和LASAR 等基于圖信息的方法普遍獲得比同類型方法更好的聚類結果,表明數據間的鄰接信息含有豐富的聚類信息;2)隨著視角缺失率的增加,所有方法的性能顯著下降,表明視角缺失因素給多視角數據一致聚類信息的挖掘帶來了一定的挑戰;3)所提出的LASAR 方法在這些數據集上獲得了一致最好的聚類結果,驗證了LASAR 在不完整多視角聚類上的有效性;4)與同樣使用低秩張量約束來挖掘高階相關信息的GM-PMVC 方法相比,本文方法在這些數據集上普遍獲得了更好的聚類結果,表明本文方法從不完整多視角數據中得到的相似圖更精確.

表1 各方法在不同視角缺失率下的Caltech7和BBCSport 數據集上的實驗結果Table 1 Experimental results of different methods on Caltech7 and BBCSport datasets with different missing-view rates

圖3 各方法在不同視角缺失率下的Handwritten、不同視角配對率下的Animal和不同視角配對率下的Reuters 數據集上的聚類Purity (%)Fig.3 The clustering Purities (%) of different methods on Handwritten dataset with different missing-view rates,Animal dataset with different paired-view rates,and Reuters dataset with different paired-view rates

3.3 算法運行時間對比

表3 列出了各對比算法和本文所提出的方法在上述5 個數據集上的聚類運行時間,其中視角缺失率或視角配對率均選擇為30%.運行時間測試的軟硬件平臺為: Ubuntu 18.04,128 GB 內存和Intel i7-9800X CPU.從表3 可以看出,在大多數情形下,本文方法的實際運行時間與MIC、OMVC和DAIMC 等具有較低計算復雜度的方法相差不大,特別是在Animal和Reuters 等大尺度數據集上,本文方法明顯比MIC和OMVC 更高效.從表3 還可以看出,與同樣采用低秩張量約束的GM-PMVC相比,本文方法能夠在更短的時間內獲得數據的聚類結果.

表3 各方法在5 個數據集上的運行時間(s),其中視角缺失率或配對率為30%Table 3 Running time (s) of different methods on the above five datasets with a missing-view rate or paired-view rate of 30%

3.4 模型分析

1)超參數敏感性分析.本部分主要分析λ1和λ2兩個超參數對模型性能的影響.圖4 展示了所提出的LASAR 在視角缺失率為30%的Handwritten和Caltech7 數據集上的聚類NMI 與這兩個超參數之間的關系,可以發現,當λ1取值在[0.01,0.1]之間且λ2取值較小時,如在 [0.00001,0.001] 范圍內時,LASAR 能夠得到相對較好的聚類結果.

圖4 在視角缺失率為30%的Handwritten和Caltech7 數據集上,所提出LASAR 方法的聚類NMI (%) 與超參數 λ1和λ2 的關系Fig.4 Clustering NMI (%) of the proposed LASAR v.s.hyper-parameters λ1 and λ2 on Handwritten and Caltech7 datasets with a missing-view rate of 30%

2)消融實驗分析.為了驗證低秩張量約束的有效性,本部分在4 個數據集上對比了本模型的兩種退化模型: 一種將低秩張量約束替換為傳統的低秩約束;另一種將低秩張量約束替換為傳統“Frobenius”范數約束.這兩種退化模型分別稱為“退化模型1”和“退化模型2”.兩種退化模型與本文LASAR的實驗對比結果如圖5 所示.從該實驗結果可看出,采用低秩張量約束的本文模型獲得了更好的聚類性能,驗證了低秩張量約束在數據結構信息挖掘上的有效性.

圖5 本文模型和其兩種退化模型在視角缺失率或配對率均為30%的4 個數據集上的聚類NMI和聚類ACCFig.5 Clustering NMIs and ACCs of the proposed method and two degraded models on the four datasets with a missing-view rate or paired-view rate of 30%

3)收斂性分析.圖6 顯示了LASAR 的學習模型在視角缺失率為30%的Handwritten和Caltech7數據集上的目標函數值與迭代步數的關系.為了更好地展示算法的收斂性,在圖6 中單獨展示了第5個迭代步至收斂步的目標函數值.從圖6 中可看出,聚類NMI 先隨著迭代步數的增加而增加,后趨于穩定;而目標函數值則呈現單調下降后收斂至穩定值的趨勢.該現象表明,本文針對LASAR 的目標模型設計的優化算法具有良好的收斂性.

圖6 在視角缺失率為30%的Handwritten和Caltech7 數據集上,LASAR 的目標函數值和聚類NMI (%)與迭代步數之間的關系Fig.6 Objective function value and clustering NMI (%) of LASAR v.s.the iterations on Handwritten and Caltech7 datasets with a missing-view rate of 30%

4)相似圖恢復分析.圖7 展示了所提出的方法在視角缺失率為70%的Handwritten 數據集上所得到的第1 個和第5 個視角的相似圖.可以發現,在每個視角缺失1 400 個樣例的情形下,本文所提出的方法仍然能夠得到具有明顯聚類連接結構的相似圖,驗證了所提出的方法在相似圖補全上的有效性.

圖7 本文方法在視角缺失率為70%的Handwritten 數據集上得到的第1 個視角和第5 個視角的相似圖Fig.7 Two similarity graphs,corresponding to the 1st view and the 5th view,obtained by the proposed method on Handwritten dataset with a missing-view rate of 70%

4 結束語

針對視角缺失下的不完整多視角聚類難題,本文提出了一種基于低秩張量圖學習的方法.該方法建立了自適應不完整圖補全和最優聚類表征學習的統一框架模型,通過挖掘視角間鄰接結構的高階相關性和視角間鄰接信息的一致性,得到了很好的相似圖恢復效果.在多種視角缺失率下的5 個數據集上,與多種先進的不完整多視角聚類方法進行對比,實驗結果表明,LASAR 在這些數據集上普遍獲得了最好的性能,驗證了其在不完整多視角聚類任務上的有效性.