動(dòng)態(tài)加權(quán)聚類算法在多媒體信息融合中的應(yīng)用

鄭濤，林亮景，鄧永強(qiáng)

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

3.1 動(dòng)態(tài)加權(quán)聚類的框架

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

圖3 動(dòng)態(tài)加權(quán)聚類的框架圖

3.2 動(dòng)態(tài)權(quán)重如何進(jìn)行動(dòng)態(tài)分配

設(shè)mi=(fi,ti)代表數(shù)據(jù)集中的第i幅圖像，變量ti和fi分別代表第i幅圖像的文本特征和圖像特征；Sf(fi,fj,w) =∑l fi,l fj,l代表在確立參數(shù)權(quán)重w時(shí)，鑒于圖像特征第i幅與第j幅圖像間的相似性度量準(zhǔn)則，變量fi,l代表圖像特征fi中的第l維，fj,l代表圖像特征fj中的第l維；代表鑒于文本特征第i幅與第j幅圖像間的相似性度量準(zhǔn)則。另外，針對(duì)每一個(gè)k,ti,k代表第i幅圖像，圖像里面的文本介紹是否含有第k個(gè)詞。基于圖像特征，為了得到合適它的權(quán)重向量w，需要采用上面的分別基于文本和圖像的相似性度量準(zhǔn)則，即Sf(fi,fj;w)與St(ti,tj)間的一致性。總之，可以理解為解決一個(gè)最優(yōu)化問(wèn)題：

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

上述最優(yōu)化問(wèn)題可以通過(guò)二次規(guī)劃技術(shù)得到動(dòng)態(tài)權(quán)重的最優(yōu)解。

3.3 加權(quán)相似矩陣

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

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

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

3.4 對(duì)稱非負(fù)矩陣分解

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

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

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

4 網(wǎng)絡(luò)圖像聚類的實(shí)驗(yàn)?zāi)Ｐ徒?/h2>

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

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

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

4.2 模型建立

實(shí)驗(yàn)中所采用的不同特征空間包含5種，因?yàn)檎Z(yǔ)義級(jí)融合是一類有監(jiān)督的學(xué)習(xí)方法[17-18]，不適用于本案例無(wú)監(jiān)督的聚類過(guò)程，因此這里只比較特征級(jí)和內(nèi)核級(jí)融合在各種不同的聚類算法中的結(jié)果。

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

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

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

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

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

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

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

4.3 實(shí)驗(yàn)結(jié)果與分析

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

通過(guò)比較表1所示結(jié)果，可以得出以下結(jié)論：

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 DyW聚類算法在k=2時(shí)對(duì)n個(gè)樣本點(diǎn)的聚類效果

5 結(jié)語(yǔ)

相比其他常用的聚類算法，本文中的動(dòng)態(tài)加權(quán)聚類算法有兩個(gè)主要優(yōu)勢(shì)：

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

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