動態(tài)加權聚類算法在多媒體信息融合中的應用

鄭濤，林亮景，鄧永強

（廣東科學技術職業(yè)學院，珠海519090）

0 引言

通常，網(wǎng)絡中的圖像，按事件主題的方式進行分組。盡管從整體的語義概念角度上看，這些圖像類同度很高，但是同一主題的圖像，有時候視覺效果卻大相徑庭，如圖1所示。原因是圖中的每一行都代表了一個獨立的類別，與其他行完全不同。既便是同一行的圖像，有的描述是圖像的整體，有的卻是細節(jié)部分。在這種條件下，人們較難從中提取出共同相似的、有代表意義的圖像特征。所以，檢索時僅僅靠判斷圖像表面現(xiàn)象來進行識別，較難達到完全理想的效果。

圖1 四行分別代表四種不同的網(wǎng)絡圖像演示

由于在網(wǎng)絡圖像的基本屬性中，含有所屬用戶提供的相關描述信息，像圖像文本描述、語音、視頻等。因此，為了獲得更好的檢索結果，許多學者已經(jīng)開始尋求其他新的解決方案，即通過提取圖像屬性中的多個有用信息像文本、圖像等，然后進行融合，生成新的融合后的多媒體表示空間，它表達的信息比較豐富，相對單一的圖像空間，進而加強了原空間的圖像識別能力。

1 數(shù)據(jù)集描述

無論與圖像融合的是文本，還是語音、視頻，它們的加權矩形與相似性度量準則都是一樣的。但由于語音和視頻的特殊性，需要先進行相關信息特征的過濾提取再融合，本文先以圖像與文本描述為例進行信息融合，從中國疫情網(wǎng)站（https://www.ncovchina.com）上搜集了355個關于“疫情”的真實的網(wǎng)絡多媒體目標，包括真實的疫情圖像及對應的文本描述，如圖2所示。該數(shù)據(jù)集包含與疫情相關的四個不同主題：①疫情預防宣傳；②醫(yī)務人員抗疫；③疫情控制措施；④疫情下生活情況。每個疫情主題分別包含101、101、53和100幅圖像及對應的文本屬性描述，共計355（101+101+53+100）個多媒體目標，這些目標本次將全部用于圖像檢索實驗。在圖像分類實驗中，將整個數(shù)據(jù)集分成兩部分，從四個類別中隨機抽取約60%的數(shù)據(jù)（每一類別包含60、60、31和60個數(shù)據(jù)，共211幅圖像及其對應的文本描述），對分類器進行訓練，約40%的數(shù)據(jù)（144個數(shù)據(jù)）被用作測試數(shù)據(jù)。

圖2 中國疫情網(wǎng)圖像及其部分相應的文本描述的示例

2 多媒體信息融合中的算法分析

基于網(wǎng)絡上的數(shù)據(jù)具有多模態(tài)屬性，它的表示形式也就可以從多個側面來反映。為此，許多學者開始研究多信息源多視角學習算法的設計，即通過融合不同信息源的特征，加強單個特征的辨別能力，在網(wǎng)絡圖像聚類或分類中發(fā)揮優(yōu)勢[1-5]。

從融合的角度分析，根據(jù)各類信息源的使用方法，多視角學習算法目前有三種不同級別：特征級[6]、語義級[7-9]和內(nèi)核級[10]融合。這三種融合均是先各自操作每個信息源的數(shù)據(jù)，然后對每個信息源，于三個級別上進行融合。這樣做的缺陷就是忽略了信息源之間的幫助指導性與可能存在的滲透性[11]。

在音樂的檢索中，曾有研究者闡述了如何通過聲學特征和用戶訪問模式之間的相關性學習合適的相似性度量準則[12]。受這篇論文的啟發(fā)，本文將動態(tài)特征加權的概念引入到網(wǎng)絡圖像聚類的問題中，旨在提升無監(jiān)督的網(wǎng)絡圖像的聚類性能。

3 網(wǎng)絡圖像聚類

要完成網(wǎng)絡圖像聚類，前提是要分析出不同信息源之間相互參考與借鑒的可行性，為此，在多媒體信息融合方面，本文提出了一種新的圖像聚類算法——動態(tài)加權聚類算法（Dynamic Weighted Clustering Algorithm）。該算法是在傳統(tǒng)聚類算法的基礎上，假定圖像的不同特征對內(nèi)容的表達具有不同的重要級別，動態(tài)地確定每個特征的權重。特別是在圖像語義表示中，對內(nèi)容表達起重要作用的圖像特征占據(jù)較大的權重，這樣在相似度計算中它將發(fā)揮舉足輕重的作用。這種方法稱之為加權相似性度量準則。圖像對之間的相似度基于此準則來度量，度量之后會在圖像對間形成一個加權相似矩陣，對此矩陣進行分解，通過對稱非負矩陣分解（Symmetric Nonnegative Matrix Factorization，SNMF）[13]的方法，一般情況下，都可以得到較好的聚類結果。下面介紹該算法的框架和步驟。

3.1 動態(tài)加權聚類的框架

大體流程是這樣的：首先假定網(wǎng)絡多媒體目標確定，并且屬性中具備文本與圖像特征，分別提取這兩個特征；然后根據(jù)文本特征的內(nèi)容重要程度，依據(jù)動態(tài)加權方案，動態(tài)賦予不同圖像特征相應的權重，得到每個圖像特征的權重后，采用加權相似度度量準則，衡量算出圖像對之間的加權相似度，把每個相似度代入運算，一個基于圖像對間的加權相似矩陣被建立；最后，再對這個加權相矩陣采用對稱非負矩陣分解的方式，獲取聚類結果?？蚣苋鐖D3所示。

圖3 動態(tài)加權聚類的框架圖

3.2 動態(tài)權重如何進行動態(tài)分配

設mi=(fi,ti)代表數(shù)據(jù)集中的第i幅圖像，變量ti和fi分別代表第i幅圖像的文本特征和圖像特征；Sf(fi,fj,w) =∑l fi,l fj,l代表在確立參數(shù)權重w時，鑒于圖像特征第i幅與第j幅圖像間的相似性度量準則，變量fi,l代表圖像特征fi中的第l維，fj,l代表圖像特征fj中的第l維；代表鑒于文本特征第i幅與第j幅圖像間的相似性度量準則。另外，針對每一個k,ti,k代表第i幅圖像，圖像里面的文本介紹是否含有第k個詞?；趫D像特征，為了得到合適它的權重向量w，需要采用上面的分別基于文本和圖像的相似性度量準則，即Sf(fi,fj;w)與St(ti,tj)間的一致性?？傊梢岳斫鉃榻鉀Q一個最優(yōu)化問題：

圖像特征中的維數(shù)用p代表，公式（1）可以用下面的形式重新改寫：

上述最優(yōu)化問題可以通過二次規(guī)劃技術得到動態(tài)權重的最優(yōu)解。

3.3 加權相似矩陣

已知兩幅圖像，圖像特征分別為fi和fj，w*為fi和fj的最優(yōu)動態(tài)權重，則這兩幅圖像間的加權相似度[14]可以寫為：

這里，圖像特征fi中的第l維用fi,l代表，圖像特征fj中的第l維用fj,l代表；圖像特征fi和fj及權重w*均要進行處理，使其保持統(tǒng)一規(guī)范性，且動態(tài)權重w*符合所以公式（6）中的加權相似度的取值范圍在[0,1]之間。這里的相似性度量準則以歐氏距離為參考標準。

根據(jù)公式（6）中的加權相似性度，可以得到一個鑒于全部圖像數(shù)據(jù)集的加權相似矩陣M，M中的每個元素Mij代表第i幅與第j幅圖像之間的加權相似度。明顯地，該矩陣M是對稱的，且對角線上的全部元素均為1。最后，對這個矩陣展開對稱非負矩陣分解，獲取聚類結果。

3.4 對稱非負矩陣分解

在得到圖像對的加權相似矩陣后，需要使用聚類算法將這些圖像進行聚類。本文采用對稱非負矩陣分解算法對圖像聚集成一些不同的簇。

在SNMF聚類算法中，已知圖像對，且由這些對形成的加權相似矩陣，需要找到滿足公式（7）的條件：

根據(jù)以上分析，SNMF算法的過程可以概括為：先給出矩陣H初值，然后用公式（12）迭代更新矩陣H，直至收斂。這種梯度下降法定會進行收斂，最后取求解方程的一個局部極小值。至于動態(tài)加權方案對聚類結果的最終影響程度，下面將進行分析。

4 網(wǎng)絡圖像聚類的實驗模型建立

為了檢驗本文中動態(tài)加權聚類算法的效果，特地抽取了幾種目前常用的聚類算法，查看其在不同的特征空間中的聚類性能，再將本文算法的平均結果與不同空間的最優(yōu)聚類結果進行比對，最后分析總結出本算法優(yōu)越的主要原因。

4.1 數(shù)據(jù)預處理

首先對于給定的網(wǎng)絡多媒體目標，采用不同的特征空間來表示，同時也把這些目標用作各種聚類算法的輸入。在文本特征提取中，首先獲取每個圖像的文本描述，緊接著調(diào)用MALLET工具包，獲得文本描述中出現(xiàn)次數(shù)較高的詞項。在圖像特征提取中，引用了新的特征表示CEDD[16]，它把顏色特征和紋理特征進行了有效地集成。CEDD算法利用一種特別的方式，將24列彩色直方圖、6列紋理直方圖融合為144維直方圖。由于CEDD獲取特征時需要的運算量不大，所以特征被獲取的速度也相當快。

4.2 模型建立

實驗中所采用的不同特征空間包含5種，因為語義級融合是一類有監(jiān)督的學習方法[17-18]，不適用于本案例無監(jiān)督的聚類過程，因此這里只比較特征級和內(nèi)核級融合在各種不同的聚類算法中的結果。

（1）獨立的文本特征空間（記為Text）：CEDD圖像特征是一個144維的特征向量，但使用MALLET工具包從數(shù)據(jù)集中提取的原始文本項為1788個。為此，在1788個出現(xiàn)頻率最高的單詞中選擇144個來表示文本特征。

（2）獨立的圖像特征空間（記為Img）：各種聚類算法的輸入值，通過提取數(shù)據(jù)集中所有圖像的144維CEDD特征來表示。

（3）基于特征級的混合特征空間（記為Feat）：通俗地說，這里的混合特征是基于特征級進行了融合。只要將上面的文本特征和圖像特征，各取144維進行簡單的串聯(lián)，就形成一個混合特征向量，維度相加后為288維。因為圖像特征和文本特征各自的向量維數(shù)一般不在同一個標準上，在鏈接前需要將這兩個不同的特征規(guī)范化到[0,1]的范圍內(nèi)。

圖4是高原4月整體及各分區(qū)的感熱通量與長江以南地區(qū)夏季降水的相關系數(shù)分布。高原整體(圖4a)、高原E區(qū)(圖4f)及高原東南部的G區(qū)(圖4h)與夏季長江以南的降水具有較好的相關性關系,尤其是高原喜馬拉雅地區(qū)(E區(qū))感熱通量與長江以南絕大部分地區(qū)降水的相關通過了95%置信度的顯著性檢驗。

（4）PCA（Principal Components Analysis）用于特征選擇（記為PCA）：即主要成分分析。用于減少數(shù)據(jù)集的維度，同時保持數(shù)據(jù)集的對方差貢獻最大的特征，改變了原來特征的形式[19]。在上述特征級融合的基礎上，對特征選擇使用主成分分析的方法，將288維融合特征向量降維為144維。

（5）基于內(nèi)核級的混合特征空間（記為Sim）：這里的混合特征與第3類不同，這是基于內(nèi)核級進行了融合。方法是對于文本特征和圖像特征，要各自計算它們的成對相似度，然后把這兩類相似度的加權和，當作判斷整體相似的度量標準。根據(jù)實驗評價，這里使用的權重系數(shù)為0.5。

得到了網(wǎng)絡多媒體對象在上述不同特征空間中的表示，并對幾種常用的聚類算法進行了實驗比較。由于不確定性是某些聚類算法的常態(tài)，在這里我們將每個算法各自運行10次，取均值。

4.3 實驗結果與分析

（1）把本文介紹的動態(tài)加權聚類（記為DyW）與常用的五種聚類算法進行了比較，這五種聚類算法分別是：K-means聚類[20]、層次聚類（Hierarchical Clustering）[21]、非負矩陣分解（Non-negative Matrix Factorization）[22]和譜聚類（Spectral Clustering）[23]在上節(jié)4.2描述的5種特征空間進行了聚類。

通過比較表1所示結果，可以得出以下結論：

表1 DyW與其他聚類算法在不同特征空間中的性能比較

①在大多數(shù)聚類算法中，文本特征空間優(yōu)于圖像特征空間；②基于特征級和內(nèi)核級的融合，在大多數(shù)情況下均提高了聚類的準確性，提示了文本信息在一定程度上，能指引和監(jiān)督圖像聚類；③把PCA方法用于特征選擇，所得到的平均聚類性能一般不高。原因是：對融合后的特征空間中的每個特征，PCA都將視為來自同一個信息源。但是，在運算網(wǎng)絡多媒體目標的加權相似度時，由于多信息源的不同特征，內(nèi)容重要級別與出現(xiàn)頻率卻是不同的。所以，在用PCA特征選擇后聚類性能較差，有所降低。

（2）為了更好地比較上面4種聚類算法與動態(tài)加權聚類算法的優(yōu)劣，本文還探討了采用共識聚類算法（Ensemble Clustering）[24]對這4種聚類算法的結果進行融合的情況。首先，把共識聚類設為非負矩陣分解，從4種聚類算法的結果中隨機抽取5種不同的結果，然后進行共識聚類。相似地，共識聚類也運行10次并取均值。當然本文介紹的動態(tài)加權聚類（記為DyW）也運行了10次，取均值。

最后，在上述5種不同特征空間中，將DyW聚類算法的正確率與4種常用聚類算法的正確率、共識聚類算法（記為Ensm）的聚類正確率進行了比較，由于層次聚類文字過長，均取了每個單詞的第一個字母，Hierarchical-Single記為H-S，Hierarchical-Complete記為H-C，Hierarchical-Average記為H-A，Hierarchical-Ward記為H-W，如圖4所示。

圖4 DyW與其他聚類算法在數(shù)據(jù)集中國疫情網(wǎng)的結果比較

從圖4中可以看出，DyW聚類算法在5個不同的特征空間中的平均正確率高于4種常用聚類算法的最優(yōu)聚類結果；并且，其平均正確率逼近共識聚類算法。

（3）本文還進一步比較了DyW算法在不同疫情主題下的聚類性能，運行10次取均值，如表2所示。圖中的Topic1-4分別表示：①疫情預防宣傳；②醫(yī)務人員抗疫；③疫情控制措施；④疫情下生活情況。

表2 DyW與其他聚類算法在不同疫情主題下的性能比較

1）DyW和大部分算法同時在Topic2中獲得了最好的聚類性能，在Topic1和Topic3上也得到了較合理的聚類結果，而在Topic4中的聚類性能最差；

2）大部分聚類算法在Topic4中的結果略差于其他主題的結果是由于主題4下的疫情生活情況的圖片覆蓋面廣，圖像內(nèi)容不太聚焦，不像主題2下的醫(yī)務人員抗疫，多為與白衣天使相關的圖像，比較聚焦，主題4在進行加權時權重比較均勻，而主題2相對來說，有比重占據(jù)份額較大的權重，能起到引領的作用，在這種情況下，DyW的效果尤其顯著；

3）四個主題情況各異，但DyW在這四個主題下均優(yōu)于其他算法，說明了該算法的優(yōu)越性。

（4）算法復雜度分析，設N為樣本個數(shù)，K為聚類團數(shù)量，T為迭代次數(shù)。

K-means聚類算法的時間復雜度是O（NKT）；層次聚類算法Hierarchical至少為O（N2）；NMF的算法復雜度較低，主要取決于迭代的次數(shù)，但變化幅度較大，不太穩(wěn)定；譜聚類Spectral算法依賴于相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同，而且它主要靠降維，如果最終聚類的維度非常高，則由于降維的幅度不夠，譜聚類的運行速度和最后的聚類效果均不好；而DyW算法由于結合了上述算法的優(yōu)勢，所以算法復雜度與NMF類同，但是卻在之前進行了加權，對相似矩陣進行了處理，所以穩(wěn)定性較高。圖5以K=2為例，展示對n個樣本點進行DyW聚類的效果。

圖5 DyW聚類算法在k=2時對n個樣本點的聚類效果

5 結語

相比其他常用的聚類算法，本文中的動態(tài)加權聚類算法有兩個主要優(yōu)勢：

（1）DyW依靠學習的方式，通過文本信息，為原始圖像特征尋找最好的加權方法。也就是說，動態(tài)權重學習過程的實現(xiàn)，是試圖利用A數(shù)據(jù)源的優(yōu)勢來改善B數(shù)據(jù)源的聚類性能，進而提高了原始圖像特征的辨別能力；

（2）對稱非負矩陣分解固有屬性呈現(xiàn)出來的某些優(yōu)勢，能使它很好地在眾多的聚類方法中脫穎而出。SNMF算法具有保持矩陣H近正交性的能力，這對目標聚類至關重要。因為精確正交性要求每行僅能存在一個非零元素，引起網(wǎng)絡多媒體目標的“硬聚類”；而矩陣H的非正交性沒有聚類的解釋性，SNMF的近正交性可以“軟聚類”，即允許每個待聚類的網(wǎng)絡多媒體目標隸屬多個族，這種情況一般都會提高聚類性能。