郭蕾蕾，俞 璐，段國侖，陶性留

(1.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的快速普及與發(fā)展，Web數(shù)據(jù)量急劇增長，這些海量的數(shù)據(jù)包含著豐富的信息，如何對其進(jìn)行有效的挖掘已經(jīng)成為當(dāng)前互聯(lián)網(wǎng)應(yīng)用的關(guān)鍵問題之一。聚類分析作為一項(xiàng)十分有效的數(shù)據(jù)挖掘技術(shù)，需要的驅(qū)動條件少[1]，而且適應(yīng)能力強(qiáng)，適合處理多種類型數(shù)據(jù)。

數(shù)據(jù)通?？梢詮牟煌I(lǐng)域的不同來源收集或從不同視圖觀察得到，即多數(shù)據(jù)包含多種類型的特征。例如，網(wǎng)站上的文檔可能包含頁面文本、鏈接文本以及一些伴隨圖像等；同一幅圖像可由不同的特征(如HOG特征、SIFT特征等)進(jìn)行描述；傳感器信號可在時域和頻域分解等。諸如此類的數(shù)據(jù)也稱為多視圖數(shù)據(jù)，因其從不同角度刻畫同一事物，因此包含了更豐富的識別信息。不同視圖數(shù)據(jù)通常存在一定的信息冗余，如何充分地從多視圖數(shù)據(jù)中提取有用特征并進(jìn)行融合是一個較新的研究方向。

多視圖聚類是將多個異構(gòu)特征進(jìn)行融合的聚類技術(shù)，目前多視圖聚類已經(jīng)取得了很多研究成果。根據(jù)多特征融合方式的不同，多視圖聚類可以分為前融合聚類、后融合聚類和過程中融合聚類[2-3]。前融合聚類就是將數(shù)據(jù)信息的多個特征集成到一個公共向量空間上，再利用傳統(tǒng)的聚類方法進(jìn)行聚類。特征集成常用的方法是將各個特征直接拼接或加權(quán)相加。后融合聚類是分別對不同的特征進(jìn)行單獨(dú)聚類，再將它們的結(jié)果采用投票等策略進(jìn)行集成。過程中融合聚類是指對多視圖屬性特征融合時存在多次迭代，每次迭代只產(chǎn)生一個具有所有視圖信息的聚類結(jié)果，通常有基于協(xié)同訓(xùn)練和非負(fù)矩陣分解的方法等[3]。多特征融合聚類雖然取得了一些成果，但對于不同的問題仍然缺乏完善且普適的算法。

針對多特征信息融合的Web圖像聚類這一具體問題，分析Web圖像的特點(diǎn)，融合圖像特征和文本特征，提出了一種基于成對約束的多特征融合AP聚類算法。

1 相關(guān)工作

1.1 AP聚類

Affinity Propagation聚類算法又叫近鄰傳播算法，簡稱AP[4]，其基本思想是將全部樣本看作網(wǎng)絡(luò)的節(jié)點(diǎn)，通過數(shù)據(jù)元素之間的消息傳遞，實(shí)現(xiàn)數(shù)據(jù)集合中元素的自適應(yīng)聚類[5]。AP聚類的輸入為節(jié)點(diǎn)間的相似度矩陣S，其中s(i,j)表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的相似度值，表明了j作為i的聚類中心的能力。聚類過程中，共有兩種消息在各節(jié)點(diǎn)間傳遞，分別是吸引度(responsibility)和歸屬度(availability)。AP算法通過迭代過程不斷更新每一個節(jié)點(diǎn)的吸引度和歸屬度值，直到產(chǎn)生m個高質(zhì)量的質(zhì)心，同時將其余的數(shù)據(jù)點(diǎn)分配到相應(yīng)的聚類中。吸引度信息用r(i,k)表示，即數(shù)據(jù)點(diǎn)k適合作為數(shù)據(jù)點(diǎn)i的聚類中心的程度，r(i,k)值越大，數(shù)據(jù)點(diǎn)k成為聚類中心的能力越強(qiáng)；歸屬度信息用a(i,k)表示，即數(shù)據(jù)點(diǎn)i選擇數(shù)據(jù)點(diǎn)k作為聚類中心的合適程度。兩種信息的迭代公式如下：

(1)

(2)

(3)

其中，a(i,k')表示除k外其他點(diǎn)對i點(diǎn)的歸屬度值，初始為0；r(i,k')表示節(jié)點(diǎn)k作為除i外其他節(jié)點(diǎn)的聚類中心的吸引度值。

在相似度矩陣中，索引相同的點(diǎn)(如s(i,i))的值稱為參考度或偏好參數(shù)(preference)，此參數(shù)會影響到最后聚類的數(shù)量，參考度越大則說明某個數(shù)據(jù)點(diǎn)成為聚類中心的能力越強(qiáng)，則最終聚類中心的個數(shù)越多。迭代開始前，假設(shè)所有點(diǎn)成為聚類中心的能力相同，因此參考度一般設(shè)為相似度矩陣中所有值的最小值或中位數(shù)。

在消息傳遞過程中，為防止數(shù)據(jù)震蕩，引入衰減系數(shù)。在每次循環(huán)迭代中，r(i,k)和a(i,k)的更新結(jié)果都由當(dāng)前迭代過程中更新的值和上一次迭代的結(jié)果加權(quán)得到[6]。加權(quán)公式為：

rnew(i,k)=λrold(i,k)+(1-λ)rnew(i,k)

(4)

anew(i,k)=λaold(i,k)+(1-λ)anew(i,k)

(5)

迭代完成后，綜合吸引度值和歸屬度值確定最終的聚類中心點(diǎn)，即對于點(diǎn)i來說，不論是否k=i，使得a(i,k)+r(i,k)取值最大的那個k即為點(diǎn)i的聚類中心。當(dāng)經(jīng)過若干次迭代后其聚類中心不變或者迭代次數(shù)超過既定的次數(shù)時，算法結(jié)束。

不同于其他聚類算法，AP聚類算法不需要指定聚類簇?cái)?shù)或其他描述聚類個數(shù)的參數(shù)，而且樣本中的所有數(shù)據(jù)點(diǎn)都可當(dāng)作潛在的聚類中心，實(shí)值信息在節(jié)點(diǎn)之間傳播直至產(chǎn)生一組高質(zhì)量的聚類簇。同時它對初始值不敏感，并且比其他方法產(chǎn)生的誤差平方和都要低。

1.2 圖像特征提取

(1)顏色特征。

顏色特征代表圖像色彩整體的分布規(guī)律，是人眼能識別的最直觀顯著的特征。常用的圖像顏色特征提取方法有：顏色直方圖、顏色矩和顏色熵等[7]。顏色直方圖是使用最廣泛的顏色特征，用來表示整個不同的顏色分量在圖像中所占的比例。文中使用HSV顏色空間直方圖來對圖像的顏色特征進(jìn)行描述。首先，將RGB模型轉(zhuǎn)為HSV模型，然后將HSV顏色空間分為若干個小的顏色區(qū)間，每個小區(qū)間成為直方圖的一個bin，這個過程叫做顏色直方圖的量化。最后，通過計(jì)算顏色落在每個小區(qū)間內(nèi)的像素?cái)?shù)量可以得到顏色直方圖。

(2)紋理特征。

紋理特征是一種不依賴于顏色或亮度而變化的視覺特性，它刻畫了圖像像素鄰域灰度空間的分布規(guī)律[8]，常采用灰度共生矩來描述圖像的紋理特征。紋理特征統(tǒng)計(jì)量包括能量、熵、對比度和相關(guān)性，分析圖像相鄰像素的灰度排列，根據(jù)圖像在0°、45°、90°、135°方向的灰度共生矩[6]，分別計(jì)算每個方向的能量、熵、對比度和相關(guān)性，求取每個方向的均值和方差作為紋理特征向量。

(3)形狀特征。

形狀特征是人類進(jìn)行物體識別所需要的關(guān)鍵信息之一，通常有兩類表示方法：描述邊界的輪廓特征和描述整個區(qū)域的區(qū)域特征。常用的形狀特征描述子有傅里葉描述子、Hu矩、Zernike矩等。文中利用Hu矩來提取形狀特征，即利用二階和三階中心距構(gòu)造七個不變矩，這七個不變矩構(gòu)成一組特征量，在連續(xù)圖像條件下可保持平移、縮放和旋轉(zhuǎn)不變性。相較于其他提取形狀特征的方法，由Hu矩組成的特征量對圖像進(jìn)行識別，可以得到更快的處理速度。

(4)HOG特征。

HOG又名梯度方向直方圖，由Dalal和Triggs于2005年提出[9-10]。提取HOG特征的過程：首先將圖像分割成多個小的連通區(qū)域，稱為細(xì)胞單元(cell)，然后在cell中統(tǒng)計(jì)所有像素點(diǎn)的梯度或邊緣方向信息得到梯度方向直方圖，最后將所有直方圖組合起來即可得到HOG描述子特征向量。

1.3 文本特征提取

文本特征常用向量空間模型(VSM)來表示，其主要思想是將文本用多維空間的向量來表示，每一個不同的特征項(xiàng)(詞語或句子)對應(yīng)向量空間的一維，而每一維的值就是對應(yīng)的特征項(xiàng)在文本中的特征值。之后在這個向量空間模型中，采用歐氏距離或夾角余弦等相似度度量方法，得到文本之間的相似度。特征權(quán)重常用的計(jì)算方法有TF-IDF統(tǒng)計(jì)法、word2vec模型訓(xùn)練法等。

2 基于AP聚類的多特征融合算法

現(xiàn)有的聚類方法大多只適用于有單個特征的數(shù)據(jù)集，無法直接應(yīng)用于多視圖數(shù)據(jù)。而現(xiàn)有的拼接、加權(quán)等特征融合方法又都存在著明顯的缺陷，直接拼接容易引發(fā)維數(shù)災(zāi)難問題，且由于不同特征量綱和物理意義的不同會導(dǎo)致樣本數(shù)據(jù)不具有可解釋性，此外還可能因?yàn)椴煌卣鞯某叨炔煌瑢?dǎo)致有價值但尺度較小的特征被忽視。不同特征線性加權(quán)的融合方法只適用于各特征維數(shù)相同的情況，也同樣面臨著加權(quán)后的樣本不具有可解釋性和尺度較小的特征易被忽視的問題。

多視圖學(xué)習(xí)，包括有監(jiān)督的分類和無監(jiān)督的聚類，都可能存在各特征單獨(dú)使用時的學(xué)習(xí)效果差異較大的問題，即有的特征經(jīng)過學(xué)習(xí)可以獲得很好的分類或聚類效果，稱為“好特征”；有的則不能得到好的效果，稱為“差特征”，文中將這種現(xiàn)象稱之為“視圖(特征)不平衡”問題。針對“視圖(特征)不平衡”數(shù)據(jù)，直接拼接的特征融合方式很可能會因?yàn)楸憩F(xiàn)較差的特征的平等加入而影響最終學(xué)習(xí)效果；加權(quán)相加的特征融合方式雖可以通過設(shè)定權(quán)重因子調(diào)節(jié)不同視圖特征之間的權(quán)重，但仍然無法避免由于特征物理意義、量綱、尺度不同而導(dǎo)致的問題。據(jù)了解發(fā)現(xiàn)，現(xiàn)有的多視圖學(xué)習(xí)方法沒有考慮“視圖(特征)不平衡問題”，在特征融合時大都平等地對待不同的視圖數(shù)據(jù)，這樣很可能會導(dǎo)致“差特征”極大地影響到“好特征”學(xué)習(xí)的結(jié)果。

由前文對AP聚類算法的介紹得知，相似度矩陣S的定義直接影響到AP聚類算法的性能，若相似度矩陣能夠準(zhǔn)確地度量數(shù)據(jù)點(diǎn)之間的相似性關(guān)系，則可以得到很好的聚類結(jié)果。針對“視圖(特征)不平衡”數(shù)據(jù)，文中提出了一種基于成對約束的多特征融合AP聚類算法。該算法主要思想是利用成對約束來調(diào)整AP聚類的相似度矩陣，“好特征”數(shù)據(jù)在相似度矩陣中占據(jù)主導(dǎo)，“差特征”數(shù)據(jù)以約束的形式發(fā)揮作用。

約束信息有多種，聚類算法中較為重要和常用的是成對約束，成對約束信息最早來源于半監(jiān)督學(xué)習(xí)，即約束信息是少量且已知的。成對約束包括正約束和負(fù)約束兩種[11]：若兩個數(shù)據(jù)點(diǎn)一定屬于同一個類，則這兩個數(shù)據(jù)點(diǎn)屬于正約束對；反之若兩個數(shù)據(jù)點(diǎn)一定不屬于同一個類，則這兩個數(shù)據(jù)點(diǎn)屬于負(fù)約數(shù)對。

同半監(jiān)督學(xué)習(xí)不同，文中的聚類是無監(jiān)督學(xué)習(xí)，樣本類別、聚類個數(shù)、約束信息都未知。為此，用一種特征進(jìn)行聚類產(chǎn)生約束信息。對于“視圖(特征)不平衡”數(shù)據(jù)，“差特征”數(shù)據(jù)被加入了較大噪聲，有用且正確的信息不是特別多，但這些信息又不能完全丟棄，此時將“差特征”信息以約束形式加入有利于充分利用各特征。雖然“差特征”計(jì)算的相似度矩陣可信度不高，但若設(shè)置較大的聚類簇?cái)?shù)，可以較好地保證聚類純度，那么此時位于同一個簇內(nèi)的樣本最終屬于同一個聚類的概率較大。文中就將這些信息作為正約束，用于調(diào)整基礎(chǔ)相似度矩陣得到最終的相似度矩陣S。

通常而言，調(diào)整相似度矩陣S的基本原則應(yīng)該是當(dāng)約束對屬于正約束時，即認(rèn)為兩樣本具有很高的相似性，將其相似度值置為較高值；當(dāng)約束對屬于負(fù)約束時，即認(rèn)為兩樣本相似度很低，將其相似度值置為較低值。那么文中為何不使用負(fù)約束對。如前所述，聚類是無監(jiān)督學(xué)習(xí)，由聚類所獲得約束信息不能保證完全準(zhǔn)確，無論設(shè)置多大的聚類簇?cái)?shù)，不同簇之間樣本都不能完全確定一定不屬于同一類。文中僅通過設(shè)置較大的聚類簇?cái)?shù)保證純度以提高正約束對的準(zhǔn)確性。

(6)

這樣得到的約束矩陣S1中有2Q個元素值為1，其余值為0。假設(shè)“好特征”數(shù)據(jù)的余弦相似度矩陣為S2，則對S的調(diào)整方式如下：

S=S2+αS1

(7)

其中，α為調(diào)節(jié)因子，表示樣本相似度修改的程度，取值為[0,1]。α為0時，表示不加入約束信息。

具體的算法流程如下所示：

輸出：聚類簇C1,C2,…,Ck2。

(3)隨機(jī)從集合M中選取Q個約束對，按如下規(guī)則轉(zhuǎn)化為稀疏的約束矩陣S1：

(5)調(diào)整S：S=S2+αS1，其中α∈[0,1]；

(6)在S上進(jìn)行AP聚類，輸出聚類結(jié)果C1,C2,…,Ck2。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)集

在PyCharm EDU環(huán)境下編寫python程序爬取百度百科網(wǎng)頁，獲得了480幅圖像及對應(yīng)的伴隨文本(一幅圖像對應(yīng)一個伴隨文本文檔)，這些圖像大致分為7類：狗(70)、植物(70)、飛機(jī)(70)、橋(70)、鳥類(70)、建筑(70)、山水(60)。

用前文所述的圖像特征提取方法，提取了每幅圖像的256維顏色特征、7維形狀特征、8維紋理特征以及3 780維HOG特征。對于文本，經(jīng)過分詞、去除停用詞、訓(xùn)練word2vec模型后得到其余弦相似度矩陣。

3.2 評價標(biāo)準(zhǔn)

對于聚類結(jié)果，首先采用純度[12]進(jìn)行了簡單的評價，定義第i簇的純度為：

(8)

其中，mi是第i簇中樣本的個數(shù)；mij是第i簇中第j類的樣本個數(shù)；K是聚類簇的個數(shù)。

聚類的總純度為：

(9)

其中，K是聚類簇的個數(shù)；m是樣本的總數(shù)。

聚類純度這一評價指標(biāo)有一個明顯的缺點(diǎn)，即若每個樣本單獨(dú)聚為一類，此時純度值為1，認(rèn)為所有樣本都被劃分到正確的簇中，顯然這一結(jié)果是不準(zhǔn)確的。因此單獨(dú)使用純度這一指標(biāo)，將無法對這種退化的聚類結(jié)果給出正確的評價[13]。為了更進(jìn)一步評價聚類結(jié)果與實(shí)際分配的吻合程度，文中還計(jì)算了調(diào)整蘭德指數(shù)、標(biāo)準(zhǔn)化互信息量、調(diào)整互信息量三個指標(biāo)。

調(diào)整蘭德指數(shù)需要給定實(shí)際類別信息L，假設(shè)K是聚類結(jié)果，a表示在L和K中都是同類別的元素對數(shù)，b表示在L和K中都是不同類別的元素對數(shù)，則蘭德指數(shù)為：

(10)

(11)

假設(shè)L和K分別是n個樣本標(biāo)簽的實(shí)際分配和聚類后分配情況，則兩種分布的熵分別為：

(12)

(13)

其中，P(i)=|Li|/n；P'(j)=|Kj|/n。

(14)

其中，P(i,j)=|Li∩Kj|/n。

標(biāo)準(zhǔn)化后的互信息(normalized mutual information)為：

(15)

調(diào)整互信息(adjusted mutual information)定義為：

(16)

其中，NMI取值范圍為[0,1]，AMI取值范圍為[-1,1]。它們都是值越大，意味著聚類結(jié)果與真實(shí)標(biāo)簽越吻合。

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

文中先利用圖像特征進(jìn)行K均值聚類，將得到的帶類標(biāo)簽的結(jié)果轉(zhuǎn)化為約束對集合，隨機(jī)選取Q個約束對求得約束矩陣S1。然后用前文所述方式調(diào)整文本相似度矩陣，之后再進(jìn)行AP聚類，此方法用KAP表示。實(shí)驗(yàn)中根據(jù)不同特征聚類所得約束對數(shù)目的不同選擇不同的Q值，約占總約束對數(shù)目的10%；調(diào)節(jié)α值得到不同結(jié)果。

為了驗(yàn)證文中方法的有效性，將得到的結(jié)果與以下幾種方式進(jìn)行對比：

(1)單特征聚類：只用圖像特征和文本特征進(jìn)行AP聚類。

(2)兩種特征簡單拼接后再聚類。

(3)多視圖譜聚類算法[14]：首先在每個視圖中根據(jù)輸入的相似度矩陣獲得各自拉普拉斯矩陣的特征向量U1和U2，然后使用U1和U2分別更新第2個視圖和第1個視圖的相似度矩陣，這個過程進(jìn)行多次重復(fù)迭代。

結(jié)果如表1～表4所示。

表1 圖像顏色特征與文本特征融合聚類結(jié)果 (KAP算法中Q=40，α=0.9)

表2 圖像形狀特征與文本特征融合聚類結(jié)果 (KAP算法中Q=30，α=0.6)

表3 圖像紋理特征與文本特征融合聚類結(jié)果 (KAP算法中Q=40，α=0.1)

表4 圖像HOG特征與文本特征融合聚類結(jié)果 (KAP算法中Q=100，α=0.4)

圖1展示了各指標(biāo)隨α值的變化情況。

(a)顏色、文本特征融合聚類結(jié)果指標(biāo)變化

(b)形狀、文本特征融合聚類結(jié)果指標(biāo)變化

(c)紋理、文本特征融合聚類結(jié)果指標(biāo)變化

(d)HOG、文本特征融合聚類結(jié)果指標(biāo)變化

由以上4個表的結(jié)果可以看出，單獨(dú)使用某個圖像特征聚類的效果很差，且與單獨(dú)文本特征聚類效果差異較大，將這兩種特征簡單拼接后再聚類結(jié)果也較差。這是因?yàn)楹唵纹唇印安钐卣鳌眹?yán)重影響了“好特征”的效果發(fā)揮。多視圖譜聚類雖較拼接聚類有所提高，但仍落后于單獨(dú)使用文本特征聚類，這是因?yàn)樵诙嘁晥D譜聚類過程中，“好特征”與“差特征”同等對待造成聚類結(jié)果也被平均。由此可見，直接拼接、多視圖譜聚類等所有平等對待各種特征的聚類方法都不適合處理“視圖(特征)不平衡”數(shù)據(jù)。

無論采用哪種圖像特征，相比于比對算法，文中提出的多特征融合聚類算法都得到了較好的聚類結(jié)果。由圖1可以看出，隨著α值的增大，各指標(biāo)呈現(xiàn)震蕩趨勢，但幅度變化不大，α值繼續(xù)增大，各指標(biāo)有下降趨勢，特別是HOG特征與文本特征的融合，因此α值不宜過大。由于成對約束信息是圖像經(jīng)過K均值聚類后得到，并不能完全保證約束信息的準(zhǔn)確性，因此相較于單獨(dú)文本聚類結(jié)果評價指標(biāo)提高不是很大，這也是今后仍需努力提高的地方?？偠灾闹兴惴ㄟ_(dá)到了預(yù)期的目標(biāo)。

4 結(jié)束語

提出了一種基于成對約束的多特征融合AP聚類算法。該算法針對多視圖數(shù)據(jù)存在“特征不平衡”問題以及現(xiàn)有聚類技術(shù)的不足，啟發(fā)式地引入某個特征聚類后得到的帶標(biāo)簽的結(jié)果形成的約束對信息來調(diào)整相似度矩陣，即“好特征”數(shù)據(jù)占主導(dǎo)地位，“差特征”數(shù)據(jù)以約束信息形式加權(quán)，然后在新的相似度矩陣基礎(chǔ)上進(jìn)行AP聚類。實(shí)驗(yàn)結(jié)果表明，該算法有效地改善了聚類性能。但由于約束對信息是經(jīng)過特征聚類所得，并不能完全保證其準(zhǔn)確性，故下一步將對如何保證約束對信息的完全準(zhǔn)確性進(jìn)行探索研究。