共享和私有信息最大化的跨媒體聚類

閆小強 葉陽東

(鄭州大學信息工程學院 鄭州 450001)

聚類方法按照“物以”的原則將數據對象劃分為不同的簇，并保持簇間數據元素間的距離盡可能地大、簇內數據元素間的距離盡可能地小，進而抽取數據對象中蘊含的模式結構.聚類分析無須借鑒數據的先驗知識，僅根據數據的實際分布情況即可得到自然的數據劃分，在認識數據中的不確定性和價值的隱蔽性方面具有重要的研究價值.然而，隨著信息技術的迅猛發展和廣泛應用，具有典型多源異構特性的跨媒體數據已經遍布生活的各個角落.跨媒體數據是指以不同模態、來源、空間等形式出現，但具有相似的高層語義的數據.如圖1所示，相同的新聞可以用多種語言進行報道[1]；同一幅圖像可以在形狀、紋理、顏色等特征空間上獲得異構的描述[2]；同一概念或事件可用圖像、文本、視頻、音頻等不同類型的媒體共同表達[3]；傳統聚類方法在做數據分析時僅考慮單模態的數據信息，已經無法適應跨媒體數據的特征異構性.

Fig. 1 The typical cross-media data圖1 典型的跨媒體數據

跨媒體聚類(cross-media clustering, CMC)[4]是一種基于數據驅動的分析方法，旨在根據不同模態數據的分布相似性，同時聚類多個模態以揭示不同模態間的潛在關聯.跨媒體聚類任務的核心問題在于捕捉多模態數據間的關聯性，以實現信息的跨模態共享.針對此問題，較為直觀的解決方法是尋找多模態數據的公共子空間.例如文獻[5]提出基于典型關聯分析(canonical correlation analysis, CCA)[6]的跨媒體聚類算法，該算法將多個模態的特征投影到低維的子空間上；文獻[7]使用共享核嵌入、文獻[8]使用高斯過程隱式變量模型學習多模態間的共享特征.然而，基于子空間的跨媒體聚類方法將各模態的特征映射到低維空間的同時，會破壞跨媒體數據的原始結構，導致一些重要信息的丟失.除了學習多模態共享子空間之外，近年來相關研究人員也提出了一些行之有效的跨媒體聚類策略.文獻[9]使用層次模型[10](hierarchical model)自底向上地構建文本和視覺特征間的關聯，進而在聚類過程中結合跨媒體特征；文獻[11]首先將圖像分割為區域的集合，此時，若將圖像視為文檔，則每個圖像區域類似于文檔中的單詞，之后通過主題模型隱含狄利克雷分布(latent Drichlet allocation, LDA)[12]將文本與視覺信息轉化為一種跨模態的向量表示；文獻[2]提出多模態譜聚類算法，自動地結合圖像數據的多種異構特征表示；文獻[13]提出多視角聯合矩陣分解方法，通過學習多視角數據的公共系數矩陣尋求多視角之間兼容的聚類劃分；文獻[14]提出魯棒的多視角k-means方法，用來處理大規模數據的多種異構特征表示.然而，上述跨媒體數據聚類分析方法僅依賴各模態間的共享信息建立多模態數據的關聯，忽略了各模態自身的私有信息，這顯然與實際應用情況不符.

另外，機器學習領域中的集成聚類(consensus clustering, CC)方法可有效地處理多模態數據，引起了跨媒體研究人員的關注.集成聚類方法在處理跨媒體數據時，首先根據單模態的數據分布得到其自身的聚類劃分(基聚類)，之后按照特定的合并準則將不同模態的聚類劃分進行合并，從而將多個模態的異構信息進行融合，得到最終的聚類劃分.例如文獻[15]設計基于相似簇、超圖、集群3種一致性度量函數合并基聚類；文獻[16]提出基于稀疏圖表示和概率軌跡的聚類集成算法，同時根據基聚類的局部和全局信息獲取最終的聚類劃分；文獻[17]在不考慮原始數據分布的情況下，通過局部密度估計方法對基聚類進行加權，進而區分基聚類的可依賴程度.然而，現有的集成聚類在處理跨媒體數據時忽略原始數據的特征分布，僅依賴基聚類構建最終的聚類劃分，導致最終的聚類劃分過度依賴基聚類的質量.

針對上述問題，本文提出共享和私有信息最大化(share and private information maximization, SPIM)的跨媒體聚類算法.如圖2所示，該算法通過兼顧跨媒體數據間的共享信息和各媒體數據自身的私有信息進行聚類分析，以求得更加合理的聚類模式結構.首先，提出混合單詞模型(hybrid words model, H-words)和聚類集成模型(clustering ensemble model, CE)構建跨媒體數據的2種共享信息，分別保持各模態底層特征的統計相似性和各模態的高層聚類劃分間的相關性.其次，提出基于信息論的目標函數，將跨媒體數據的共享和私有信息融合在同一目標函數中.同時處理各模態自身的私有信息(原始特征)和聚類集成模型構建的共享信息(聚類劃分)，有助于克服集成聚類算法對基聚類的過度依賴.最后，采用順序“抽取-合并”優化過程，保證SPIM算法的目標函數收斂到局部最優解.在6種跨媒體數據上的實驗結果表明SPIM算法性能優于現有方法.本文的主要貢獻總結為3個方面：

1) 提出共享和私有信息最大化的跨媒體聚類算法SPIM，該算法通過兼顧跨媒體數據的共享和私有信息，以求得更加合理的模式結構.

2) 提出2種跨媒體數據的共享信息構建模型：混合單詞模型和聚類集成模型，分別保持各模態底層特征的統計相似性和各模態的高層聚類劃分間的相關性.

3) 提出基于信息論的目標函數，并采用順序“抽取-合并”優化策略對該目標函數進行優化，保證其收斂到局部最優解.

Fig. 2 The illustration of SPIM method圖2 SPIM方法示意圖

本文工作與文獻[18-19]中的多特征信息瓶頸(multi-feature information bottleneck, MfIB)算法、文獻[20]中的多視角概念學習(multi-view concept learning, MCL)算法、文獻[21]中的跨媒體社交圖像聚類(cross-media social image clustering, CSIC)算法關聯較為密切.其中MfIB算法是信息瓶頸(information bottlenede, IB)算法的擴展，該算法使用互信息量化聚類模式與多個特征間的信息量，然而，該算法要求多種特征表示來自同一數據分布，無法處理跨模態的異構特征.MCL算法和CSIC算法采用多模態數據的共享特征和獨有特征進行跨模態分析.其中，MCL算法學習多模態數據的概念性隱式空間，并將該隱式空間分解為共享和獨有2個部分.然而，該算法是半監督算法，無法處理聚類問題.CSIC算法將社交圖像中視覺和社交標簽信息的共享特征空間學習視為一個共軛詞典學習問題，通過L范數的正則項保證各模態的詞典稀疏化，這種稀疏化使得各模態的獨有特征得以保留.然而，該算法需要借助WordNet獲得輔助的社交語義關系，僅適用圖像和文本2種模態數據，無法處理更多模態.近年來，深度神經網絡在跨媒體數據的一致性表征中取得了較好的結果，例如多層次跨模態關聯學習[22]、多網絡共享表征[23].深度神經網絡需要大量已標注的訓練數據，然而，數據標簽信息的獲取是費時費力的過程.

1 背景知識

IB算法[24-25]是一種典型的基于信息最大化的數據分析方法[18-19,26].給定源變量X與特征變量Y之間的聯合概率分布p(X,Y)，IB算法力圖尋求源變量X的最優壓縮表示T，同時使壓縮變量T最大化地保存特征變量Y中蘊含的關于源變量X的信息量.如圖3所示，源變量X與其特征變量Y之間的信息通過壓縮變量T進行保存.IB算法可形式化描述為

(1)

其中，p(t|x)是源變量X到壓縮變量T之間的編碼方案，I(X;T)是變量之間的互信息，D是X到T之間所有可能的編碼方案.從式(1)可知，IB算法是在信息保存程度滿足I(T;Y)≥D的條件下，尋找能夠最小化I(X;T)的一個編碼方案p(t|x).文獻[22]給出IB算法的目標函數：

(2)

其中，β是拉格朗日乘數因子，用來平衡數據對象的壓縮與相關信息的保存.在聚類任務中，簇的個數M往往遠遠小于原始數據對象的數量，即M?|X|，這意味著源變量X與其壓縮變量T之間存在大幅度壓縮.因此，實際應用中通常將β設置為無窮大.這種做法的有效性在多種數據類型的聚類任務中得到驗證，例如文本[25]、圖像[18]、視頻[26].因此，IB算法的目標函數可改寫為

(3)

其中，互信息I(T;Y)度量壓縮變量T與特征變量Y之間的信息量.

Fig. 3 The model of IB algorithm圖3 IB算法的模型圖

2 共享和私有信息最大化的跨媒體聚類

本文提出共享和私有信息最大化的跨媒體聚類算法SPIM，該算法旨在兼顧跨模態數據間的共享信息和各模態自身的私有信息進行跨媒體聚類分析，以求得更加合理的模式結構.為了清晰地描述，本節首先給出SPIM算法的問題定義.

定義1.使用源變量X=(x1,x2,…,xn)表示跨媒體數據對象的集合,使用私有變量Y1,Y2,…,Yk表示不同模態數據自身的私有信息(即各模態自身的特征表示，又稱作源變量X的特征變量)，使用共有變量S表示模態間的共享信息，其中,n是數據對象的數量，k是跨媒體數據的模態數量.SPIM算法的目標是尋求源變量X到壓縮變量T的一種最優壓縮表示p(t|x)，在壓縮過程中使壓縮變量T同時最大化地保存與各模態自身的私有變量Y1,Y2,…,Yk和共有變量S間的信息.根據式(3)，可給出SPIM目標函數：

(4)

其中，λ是控制私有信息與共享信息之間側重程度的平衡參數.當λ=0且k=1時，SPIM算法回歸至IB算法，因此，IB算法可視為SPIM算法的特例.

2.1 混合單詞模型

詞庫模型[27]是一種常用的數據表示方法，該方法可將跨媒體的各模態數據轉換為單詞或視覺單詞出現頻率的向量形式，例如一幅城市場景的圖像可由高樓、街道、紅綠燈等視覺單詞出現頻率表示；一則體育新聞可由比分、隊員、場地等文字出現頻率表示.在聚類任務中同時考慮不同模態數據的詞頻表示能在一定程度上刻畫多模態間的關聯性，但不同模態數據的詞頻向量在尺度上具有明顯的差異，且存在較大的樣本冗余.因此，本文提出混合單詞H-words模型，首先將各模態的底層特征轉換為統一的詞頻向量表示，然后使用自凝聚信息最大化方法自底向上地構建多模態的混合單詞空間，抽取模態間的共享信息，最大化地保持各模態底層特征的統計相似性.

Fig. 4 The mutual information between two clusters of different modalities圖4 不同模態的聚類劃分間的互信息

(5)

(6)

(7)

(8)

給出自凝聚信息最大化的詳細執行過程：

1) 將每個特征點初始化為1個單獨簇.

2.2 聚類集成模型

為了進一步挖掘各模態間的關聯關系，本文提出聚類集成CE模型，首先為各模態數據構建各自的聚類劃分，然后使用互信息度量各模態高層聚類劃分間的相關性，進而捕捉到多個模態的異構信息.

(9)

圖4舉例說明聚類集成模型中使用互信息度量各模態間高層聚類劃分的相關性.圖4中第i行第j列若為黑框，表示數據元素xj出現在簇ci中，否則表示不出現.另外，為了使展示更加清晰，該例中數據元素可被劃分至多個簇中.圖4(a)中聚類模式Cl和T高度相似，得到最高的互信息；圖4(b)中Cl和T的相關性減弱，互信息也相應降低；圖4(c)中Cl和T的相似度最弱，得到最低的互信息.因此，使用互信息可有效地度量跨模態高層聚類劃分之間的相關性.

2.3 SPIM算法的目標函數

根據定義1可知，SPIM算法的目標是尋求源變量X到壓縮變量T的一種最優壓縮表示p(t|x)，在壓縮過程中使壓縮變量T最大化地保存與各模態自身的私有變量Y1,Y2,…,Yk和共有變量S的信息量，其中共有變量由混合單詞模型和聚類集成模型共同求得，因此，SPIM算法的目標函數可改寫為

(10)

2.4 SPIM算法目標函數的優化

本節使用順序“抽取-合并”策略優化SPIM算法的目標函數，求解源變量X到壓縮變量T之間的編碼方案p(t|x).順序“抽取-合并”優化方法包含3個步驟：

1) 將源變量X=(x1,x2,…,xn)隨機劃分至M個簇T=(t1,t2,…,tM)；

2) 順序地將每個數據元素x從當前簇told中抽取出來，作為單獨簇{x}；

3) 計算將單獨簇{x}合并至其他簇中時SPIM算法目標函數中信息的損失量，并選取使得信息損失最小的簇tnew進行合并.

(11)

(12)

根據互信息的定義，可得：

[p(x)+p(t)]·JSπ[p(Yi|x),p(Yi|t)]，

(13)

在將{x}合并至簇t時，根據聚類集成模型中的式(9)可得到p(Tbef,Ci)，p(Taft,Ci),因此可計算將{x}合并前后由I(T;Ci)引起的合并代價.綜上所述，可計算將{x}合并至簇t的合并代價：

(14)

給出SPIM算法的實現過程:

算法1.SPIM算法.

輸入：源變量X與多個模態的私有變量Y1，Y2,…,Yk之間的聯合概率分布p(X,Y1),p(X,Y2),…,p(X,Yk);簇的個數M;平衡參數λ.

輸出：X到T的編碼方案p(t|x).

② 根據聚類集成模型構建多個模態自身的聚類劃分C1,C2,…,Ck；

③ 將源變量X隨機劃分為M個簇；

④ Repeat：

⑤ For everyx∈X

⑥ 將x從當前簇told中抽取出來，作為單獨簇{x}；

⑧ End For

⑨ Untilp(t|x)不再發生變化.

2.5 算法分析

2.5.1 收斂性分析

定理1.SPIM算法可在有限迭代次數內收斂到局部最優解.

證畢.

2.5.2 復雜度分析

3 實驗與性能分析

3.1 數據集

本文在6種跨媒體數據集上驗證SPIM算法的有效性：

1) Wikipedia數據集[28].該數據集包含2 866個文本圖像對共計10個類，每幅圖像的共生文本至少有70個單詞.對于圖像，本文采用文獻[28]提供的128維SIFT[29]特征構建BoVW視覺特征表示；對于文本，首先構建500維BoW表示，然后通過LDA抽取100個話題的概率分布作為文本特征表示.

2) Pascal Sentence數據集[30].該數據集包含1 000個文本圖像對共計20個類.對于圖像，本文抽取1 024維的SIFT BoVW視覺特征表示；對于文本，首先構建300維BoW表示，然后通過LDA抽取100個話題的概率分布作為文本特征表示.

3) Pascal VOC 2007數據集[31].該數據集包含9 963個文本圖像對共計20個類.本文采用文獻[32]提供的798維基于標簽排序的文本特征和776維的BoVW視覺特征.

4) X-Media[33-34]是針對檢索任務[35]構建的跨媒體數據集，該數據集包含文本、圖像、視頻、音頻、3維模型等多種模態的數據，共計20個類.我們使用5 000個文本、圖像對評估算法性能.關于該數據集的特征描述，本文采用文獻[33]提供的10維LDA文本特征、128維BoVW圖像特征.

5) Reuters多語種數據集[1].該數據集由5種語言的新聞文檔組成，包括西班牙語、意大利語、德語、法語和英語，每種語言的文檔被分為6類：C15，CCAT，E21，ECAT，GCAT，M11.本文隨機從每種語言類中挑取500個文檔，并使用BoW模型抽取1 000個關鍵詞，為每個語種構建1 000維BoW表示.

6) HMDB數據集[36].該數據集由51類共計6 849個人體動作視頻序列組成，主要來源電影片段、網絡視頻等.本文提取視頻序列3種異構描述子[37]：梯度直方圖(histogram of oriented gradient, HOG)、光流直方圖(histogram of optical flow, HOF)和空間時間特征(space-time interest points, STIP)，分別構建視頻序列的1 000維BoVW表示.

3.2 評價指標

為了公正地對聚類結果進行評估，本文使用2種指標[15]評估算法的聚類性能：

1) 聚類精度(clustering accuracy,ACC)：

(15)

其中，li和ti分別表示數據對象的真實劃分和聚類劃分，n是數據集的大小.δ(x,y)為狄克拉函數，當x==y時，δ(x,y)=1，否則δ(x,y)=0.map(ti)是聚類劃分ti與真實劃分之間的映射函數.

2) 標準化互信息(normalized mutual information,NMI)：

(16)

其中，T和C分別表示數據對象的聚類劃分和真實劃分，I(T;C)是T和C間的互信息，H(T)和H(C)分別表示聚類劃分和真實劃分的信息熵.ACC，NMI的值越大，聚類結果越好.

3.3 對比方法

為驗證SPIM算法在跨媒體聚類任務中的有效性，本文將其與7種算法進行對比：

1)k-means算法.經典的單模態聚類算法.

2) IB算法[22].對各模態分別使用IB算法進行聚類，我們在所有圖表中公布各模態中最好的聚類結果.

3) Concate -IB算法.將各模態的特征直接相連，然后使用IB算法進行聚類.

4) 典型關聯分析(canonical correlation analysis， CCA)算法[6].采用CCA算法學習2個模態間的共享信息.對于Reuters和HMDB數據集，本文選擇2種表現最優的模態作為CCA算法的輸入.

5) CSPA(cluster-based similarity partitioning algorithm)算法[15].該算法是一種典型的聚類集成算法，首先根據基聚類的co-association矩陣生成圖，其中頂點是數據對象，邊的權重的數據對象間的co-association值，然后使用METIS算法進行聚類.

6) PTGP(probability trajectory graph parti-tioning)算法[16].該算法是基于稀疏圖表示和概率軌跡的聚類集成算法，能夠同時根據基聚類的局部和全局信息獲取最終的聚類劃分.

7) LWGP(locally weighted evidence accumu-lation)算法[17].該算法在不考慮原始數據分布的情況下，通過局部密度估計方法對基聚類進行加權，進而區分基聚類的可依賴程度.

表1給出算法的時間復雜度對比.其中，CCA算法的O(Md2)項為計算2個模態的協方差矩陣的時間復雜度，O(d3)項是特征分解的時間復雜度，d=max(|Yi|,|Yj|)是任意2個模態的特征維度的最大值.CSPA算法采用METIS算法[38]對基聚類的生成圖進行劃分，其時間復雜度為O(|X|2).LWGP算法首先構建數據對象X與基聚類之間的二分圖(bipartite graph)，之后使用TCut算法[39]圖劃分.與LWGP算不同，PTGP算法首先對數據對象X進行初步聚類生成中間簇Xmcluster，構建中間簇Xmcluster與基聚類的二分圖，最后使用TCut算法進行二分圖劃分，其中|Xmcluster|是中間簇的數量.

Table 1 The Complexities of Different Baselines表1 不同算法的時間復雜度對比

3.4 實驗結果分析

為了驗證數據不同模態表示能力的差異，圖5給出IB算法在跨媒體數據不同模態上的聚類結果.圖5中的實驗結果表明：

1) IB算法在Wikipedia，Pascal Sentence和Pascal VOC 07數據集的文本、圖像2種模態上的聚類結果具有較大的差異，且IB算法在文本模態上的聚類性能明顯優于圖像模態.這說明在跨模態的圖像聚類任務中僅依賴圖像信息很難獲得較好的聚類結果，豐富的語義關系能夠帶來更加準確的語義相關性.因此，兼顧語義和視覺等模態信息有助于提升跨模態聚類任務的聚類性能.

2) IB算法在多語種數據集Reuters的各語種上和視頻數據集HMDB的各異構特征空間上得到相近的聚類結果.這說明數據對象往往具有多個側面的描述，例如相同的新聞可以用多種語言進行報道；包含相同人體動作的視頻序列可以在梯度、光流、時空等特征空間上獲得異構的描述.不同側面的特征信息反映數據不同的內在特性，有效地組織和使用特征之間的互補作用以便確保高質量的聚類結果.

Fig. 5 Clustering results of IB on different media sources圖5 IB算法在不同媒體源上的聚類結果

Note: The best clustering results in each case is boldfaced.

Table 3 The NMI Comparison Results on 6 Cross-Media Datasets表3 在6種跨媒體數據集上的NMI對比結果 %

Note: The best clustering results in each case is boldfaced.

Fig. 6 The impact of λ on the performance of SPIM algorithm圖6 平衡參數λ對SPIM算法聚類結果的影響

1) 將各模態的特征直接相連不能有效地提升聚類性能.例如相比IB算法在單一模態上的最優結果，Concate-IB算法在Wikipedia，Pascal Sentence，Pascal VOC 07數據集上的ACC和NMI值出現下降.說明簡單地連接多模態的特征信息不能穩定地提升算法的聚類質量.

2) 結合多模態信息的算法在聚類任務上的表現優于單模態聚類.從表2和表3可知，CCA，CSPA，PTGP，LWEA算法在本文使用的6種跨媒體數據上的平均聚類結果均優于k-means，IB等單模態聚類算法.這種現象驗證了多模態之間的互補作用能夠有效地提升聚類結果.

3) 相比于其他單模態和跨模態聚類算法，SPIM算法在本文使用的6種跨媒體數據集上的聚類結果均有提升.

3.5 參數分析

SPIM算法使用參數λ控制共享信息與私有信息間的側重程度，因此，本節通過實驗來觀察不同參數值對聚類結果的影響.從圖6可以看出，當λ取值較小時，SPIM算法得到較低的ACC值.隨著λ值的增大，SPIM算法聚類效果逐漸變好，此時共享信息與私有信息的互補作用得以體現.隨著λ值進一步增大，各模態的私有信息與共享信息達到平衡，SPIM算法的聚類結果也在一定程度上趨于穩定.注意，本文公布的SPIM算法的聚類結果對應參數取值為λ=60，聚類結果如圖6中星號所示.

Fig. 7 The iteration number of SPIM on different datasets圖7 SPIM算法在不同數據集上達到收斂時的迭代次數

3.6 收斂性分析

SPIM算法的目標函數只能收斂到一個局部最優解，因此有必要對其收斂性進行經驗性分析.圖7給出SPIM算法每次迭代后式(10)的值.從圖7可以看出，隨著算法的運行，式(10)的值先是迅速上升，然后上升的幅度趨于平緩，最終得到目標函數的局部最優值，說明該算法具有較好的收斂性.

Fig. 8 Model ablation test of SPIM algorithm in terms of NMI圖8 SPIM算法在NMI指標上的模型簡化測試

3.7 模型簡化測試

SPIM算法通過混合單詞模型和聚類集成模型對跨模態數據中各模態間的關聯進行建模，分別保持各模態底層的統計相似性和各模態的高層聚類劃分間的相關性.本節針對混合單詞模型和聚類集成模型設計單獨的實驗，以驗證單個模型的有效性.根據式(10)可知，SPIM算法在僅考慮單一混合單詞模型和聚類集成模型時的目標函數可分別簡化為

(17)

(18)

圖8和表4給出分別考慮單一混合單詞模型和聚類集成模型時SPIM算法的聚類精度和標準化互信息.從圖8和表4可知：

1) SPIM算法在僅考慮單一模型時的聚類結果優于IB算法在單個模態中最優的聚類結果，驗證SPIM算法中單一模型的有效性；

2) 在同時使用混合單詞模型和聚類集成模型對共享信息建模時，SPIM算法的聚類結果進一步提升.例如，表4中SPIM算法在6種跨媒體數據集上的平均結果均優于IB算法、聚類集成模型和混合詞庫模型.

Table 4 Model Ablation test of SPIM Algorithm in Terms of ACC表4 SPIM算法在ACC指標上的模型簡化測試 %

Note: The best clustering results in each case is boldfaced.

4 結 論

本文提出共享和私有信息最大化的跨媒體聚類算法SPIM，該算法能夠使用跨模態數據間的共享信息和各模態自身的私有信息進行聚類分析.首先，提出2種跨媒體數據的共享信息構建模型，分別保持各模態底層特征的統計相似性和各模態的高層聚類劃分間的相關性，其次，提出基于信息論的目標函數，將跨媒體數據的共享和私有信息融合在同一目標函數中.最后，采用順序“抽取-合并”優化過程，保證SPIM的目標函數收斂到局部最優解.在6種跨媒體數據上的實驗結果表明：本文提出的SPIM算法的優越性