改進(jìn)K-means加權(quán)自適應(yīng)多視圖數(shù)據(jù)聚類(lèi)算法

李麗亞，閆宏印

(1.太原工業(yè)學(xué)院，山西 太原 030008；2.太原理工大學(xué)，山西 太原 030024)

1 引言

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)信息量和數(shù)據(jù)信息種類(lèi)越來(lái)越多，將這些數(shù)據(jù)看成多個(gè)特征集合，并把每一個(gè)具有特征的集合比作一個(gè)視圖，這樣便構(gòu)成了多視圖數(shù)據(jù)。例如：若想識(shí)別一個(gè)人，可以結(jié)合他的聲音、長(zhǎng)相、外形等特征對(duì)其進(jìn)行辨別。因此對(duì)多視圖數(shù)據(jù)有以下定義：同一個(gè)物體從不同角度觀察所產(chǎn)生的異構(gòu)特征數(shù)據(jù)，叫多視圖數(shù)據(jù)[1-4]?，F(xiàn)階段由于測(cè)量方法的多樣性，多視圖數(shù)據(jù)在各行各業(yè)中廣泛存在。對(duì)數(shù)據(jù)進(jìn)行描述時(shí)可以通過(guò)對(duì)不同的視圖從不同的角度進(jìn)行分析，如何對(duì)多個(gè)視圖數(shù)據(jù)采取高效聚類(lèi)是當(dāng)前研究領(lǐng)域的一個(gè)重點(diǎn)問(wèn)題。

文獻(xiàn)[5]提出一種樣本加權(quán)的多視圖聚類(lèi)算法，對(duì)每個(gè)樣本的不同視圖作加權(quán)處理，然后采用交替方向乘子算法實(shí)現(xiàn)自適應(yīng)學(xué)習(xí)。實(shí)驗(yàn)結(jié)果表明，該算法不僅體現(xiàn)了樣本的差異性，還能夠很好地刻畫(huà)出視圖的重要性，但是該算法提出的模型在視圖數(shù)據(jù)上的聚類(lèi)效果相對(duì)較差。文獻(xiàn)[6]提出一種魯棒自加權(quán)的多視圖子空間聚類(lèi)模型，該模型利用范數(shù)處理多視圖數(shù)據(jù)的平方差，并通過(guò)范數(shù)對(duì)數(shù)據(jù)的離群點(diǎn)進(jìn)行分析優(yōu)化，有效地解決了普通點(diǎn)和離群點(diǎn)對(duì)多視圖數(shù)據(jù)性能的干擾，但該方法不能使模型盡可能的收斂到局部極小值，因此導(dǎo)致模型不能取得最優(yōu)求解策略。文獻(xiàn)[7]提出了一種大規(guī)模多視圖數(shù)據(jù)的自降維K-means算法，通過(guò)找到某一個(gè)視圖上的最優(yōu)子空間達(dá)到多維數(shù)據(jù)的自動(dòng)降維處理，并利用非負(fù)矩陣分解的方法對(duì)有損函數(shù)重新構(gòu)建，達(dá)到視圖數(shù)據(jù)共享、多視圖數(shù)據(jù)信息互補(bǔ)的目的，完成多視圖數(shù)據(jù)的聚類(lèi)。實(shí)驗(yàn)結(jié)果表明，該算法能更準(zhǔn)確的聚類(lèi)，但就大規(guī)模多視圖數(shù)據(jù)的計(jì)算復(fù)雜度而言，還需進(jìn)一步優(yōu)化。

基于現(xiàn)有研究成果及其優(yōu)缺點(diǎn)，本文提出了一種基于改進(jìn)K-means加權(quán)自適應(yīng)多視圖聚類(lèi)算法，針對(duì)離群點(diǎn)對(duì)數(shù)據(jù)模型的影響，對(duì)數(shù)據(jù)條件進(jìn)行優(yōu)化，通過(guò)改進(jìn)目標(biāo)函數(shù)系數(shù)，平衡多視圖數(shù)據(jù)的大小誤差。在進(jìn)行優(yōu)化之前，通過(guò)損失函數(shù)，確定多視圖不同簇的聚類(lèi)中心，并結(jié)合拉格朗日乘子法，將多視圖數(shù)據(jù)信息進(jìn)行聚類(lèi)。

2 基于加權(quán)自適應(yīng)的多視圖數(shù)據(jù)聚類(lèi)算法

對(duì)于多視圖聚類(lèi)問(wèn)題，大多數(shù)學(xué)者采用學(xué)習(xí)樣本上不同類(lèi)型信息對(duì)節(jié)點(diǎn)簇結(jié)構(gòu)有差異的K-means型算法。這種算法將多視圖的兩種類(lèi)型信息映射到同一個(gè)維度空間上，再通過(guò)對(duì)其進(jìn)行融合，得到具有統(tǒng)一的簇中心，其目標(biāo)函數(shù)用公式表示為

(1)

雖然以上方法可以對(duì)不同樣本的兩種類(lèi)型信息進(jìn)行重要性的差異學(xué)習(xí)，但是在信息融合過(guò)程中，需要將空間進(jìn)行維度變換，可能導(dǎo)致一些信息的損失，而且同維度變換會(huì)增加算法的復(fù)雜性，使得對(duì)節(jié)點(diǎn)簇結(jié)構(gòu)的差異性缺乏靈敏度，因此本部分內(nèi)容提出加權(quán)自適應(yīng)多視圖聚類(lèi)算法。

如果有Nw個(gè)視圖，所有視圖的數(shù)據(jù)用公式表示為

(2)

由以上的目標(biāo)函數(shù)可以求得多視圖的矩陣分解模型，公式表示為

(3)

大多數(shù)多視圖子空間算法都可以取得很好的效果，但由于數(shù)據(jù)具有誤差性，普通的多視圖數(shù)據(jù)不能保證低秩的性質(zhì)，所以不能直接在數(shù)據(jù)上做矩陣分解。于是引入約束條件Y(w)=E(w)WT，從而使目標(biāo)函數(shù)達(dá)到最優(yōu)狀態(tài)，用公式可表示為

(4)

由上述公式可知，模型對(duì)數(shù)據(jù)誤差較大的離群點(diǎn)很難做到多視圖數(shù)據(jù)的有效融合，只能處理誤差小的多視圖數(shù)據(jù)。但現(xiàn)階段大多數(shù)算法都忽略了離群點(diǎn)對(duì)數(shù)據(jù)模型的影響。針對(duì)這種情況，假定多視圖數(shù)據(jù)矩陣Y用公式表示為

(5)

其中，e表示數(shù)據(jù)的稀疏誤差矩陣；H表示數(shù)據(jù)的低秩數(shù)據(jù)矩陣。將這種模型應(yīng)用到多視圖數(shù)據(jù)中，則加權(quán)自適應(yīng)多視圖數(shù)據(jù)聚類(lèi)模型用公式可表示為

(6)

由于數(shù)據(jù)中的小誤差對(duì)多視圖數(shù)據(jù)結(jié)果有影響，因此對(duì)數(shù)據(jù)條件H(w)=E(w)WT進(jìn)行優(yōu)化處理。把Frobenius范數(shù)作為條件進(jìn)行改進(jìn)，起到對(duì)多視圖數(shù)據(jù)加權(quán)的作用。用公式表示為

(7)

其中，γ表示目標(biāo)函數(shù)系數(shù)，在平衡多視圖數(shù)據(jù)的大小誤差上起著關(guān)鍵性作用。除此之外，還需結(jié)合自由度問(wèn)題。假設(shè)存在某個(gè)可逆矩陣Q，滿(mǎn)足如下條件

(8)

(9)

3 多視圖數(shù)據(jù)的K-means優(yōu)化理論

為了進(jìn)一步求解到最小值，本節(jié)利用動(dòng)態(tài)規(guī)劃的方法將目標(biāo)函數(shù)進(jìn)行分步優(yōu)化。對(duì)于多視圖數(shù)據(jù)中的任何一個(gè)視圖數(shù)據(jù)，進(jìn)行QR分解處理，將U(w)作為正交矩陣Q的初始值。在含有噪聲的空間中，把多視圖數(shù)據(jù)看成整個(gè)簇，根據(jù)K-means優(yōu)化理論，可知

(10)

u(w)表示視圖常數(shù)。在進(jìn)行優(yōu)化之前，引入損失函數(shù)，公式表示為

(11)

其中，η(w)表示自動(dòng)學(xué)習(xí)的權(quán)重系數(shù)；σ是權(quán)衡權(quán)重系數(shù)的分布式參數(shù)。由于每個(gè)視圖數(shù)據(jù)都是不同的，因此通過(guò)η(w)給信息量較多的視圖分配較大的權(quán)重；反之，給信息量較少的視圖分配較小的權(quán)重，這樣便可通過(guò)權(quán)重系數(shù)減少數(shù)據(jù)對(duì)多視圖聚類(lèi)的影響。算法的最終損失函數(shù)作如下變形處理

(12)

(W(w)TE(w)TY(w)-W(w)TE(w)TF(w)GT)T}

(13)

其中，N(w)表示對(duì)角矩陣，該對(duì)角矩陣的對(duì)角元素是其對(duì)應(yīng)視圖中行向量函數(shù)，公式表示為

(14)

綜上可知，J是關(guān)于F(w)的凸函數(shù)，對(duì)其進(jìn)行求導(dǎo)，可以得到

(15)

(16)

其中，G表示離散的矩陣向量，為了達(dá)到優(yōu)化離散矩陣的目的，可以為每個(gè)多視圖數(shù)據(jù)分配指示向量。保持F(w)和G不變，確定多視圖不同簇的聚類(lèi)中心，通過(guò)計(jì)算，可以得出

(17)

(18)

至此所有視圖數(shù)據(jù)信息聚類(lèi)優(yōu)化已完成。

4 多視圖數(shù)據(jù)集及衡量指標(biāo)

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

為了評(píng)估本文所提出改進(jìn)K-means加權(quán)自適應(yīng)多視圖數(shù)據(jù)聚類(lèi)算法的效果，對(duì)不同多視圖聚類(lèi)模型進(jìn)行對(duì)比分析，選取存在多視圖差異的3個(gè)數(shù)據(jù)集，和不存在差異的2個(gè)數(shù)據(jù)集作為比較，分別為WebKB、Wiki、VOC和Handwritten numerals、Caltech101-7。下面分別介紹這5個(gè)數(shù)據(jù)集的特點(diǎn)。

1)差異性數(shù)據(jù)集描述

WebKB數(shù)據(jù)集：該數(shù)據(jù)集分別包含{195，187，230，265}個(gè)樣本，每個(gè)樣本對(duì)應(yīng)的維數(shù)分別為{195，1703}維、{187，1703}維、{230，1703}維、{265，1626}維。該數(shù)據(jù)集涉及了5個(gè)類(lèi)別，分別為：工程、學(xué)院、課程、員工、學(xué)生。

Wiki數(shù)據(jù)集：該數(shù)據(jù)集經(jīng)常用在跨模態(tài)的檢索環(huán)境中，其中包含訓(xùn)練樣本2173個(gè)、測(cè)試樣本693個(gè)，類(lèi)別10個(gè)。每個(gè)視圖都應(yīng)用128維的特征向量視圖和10維的主題描述向量視圖。

VOC數(shù)據(jù)集：該數(shù)據(jù)集是一個(gè)自然圖像數(shù)據(jù)集，每一張圖片都包含512維的GIST文本特征和399維的TF文本特征，整個(gè)文本涉及了20個(gè)類(lèi)別。

2)相同性數(shù)據(jù)集描述

Handwritten numerals數(shù)據(jù)集：該數(shù)據(jù)集包含10個(gè)類(lèi)別的2000個(gè)手寫(xiě)數(shù)據(jù)。選取的特征分別為85維的FOU特征、73維的KAR特征、225維的FAC特征、231維的PIX特征和56維的ZER特征的共計(jì)5個(gè)視圖數(shù)據(jù)。

Caltech101-7數(shù)據(jù)集：該數(shù)據(jù)集經(jīng)常用在對(duì)象識(shí)別的環(huán)境中，包含1526張視圖，7個(gè)類(lèi)別，6個(gè)特征，視圖對(duì)應(yīng)的特征維數(shù)分別為49維、51維、365維、2095維、623維、1039維。

4.2 數(shù)據(jù)集度量標(biāo)準(zhǔn)

本文采用4個(gè)性能評(píng)價(jià)指標(biāo)對(duì)多視圖聚類(lèi)算法進(jìn)行衡量，分別為F-meansure、正確率、RI以及Speedup性能指標(biāo)。

F-meansure：該指標(biāo)的公式表示為

(19)

正確率：該指標(biāo)的公式表示為

(20)

其中，n表示多視圖數(shù)據(jù)中正確劃分的樣本數(shù)；N表示多視圖數(shù)據(jù)樣本總數(shù)。

RI：該指標(biāo)用來(lái)評(píng)價(jià)2個(gè)聚類(lèi)劃分效果的相似程度，公式表示為

(21)

其中，Ia表示在不同簇被劃分到不同簇的多視圖樣本數(shù)；Ib表示在不同粗被劃分到童簇的多視圖樣本數(shù)；Ic表示在童簇被劃分到不同簇的樣本數(shù)；Id表示在通粗被劃分到通粗的樣本數(shù)。

上面三種評(píng)價(jià)指標(biāo)，得出的數(shù)據(jù)結(jié)果越接近1，說(shuō)明聚類(lèi)效果越好。

Speed：該指標(biāo)是用來(lái)評(píng)價(jià)多視圖數(shù)據(jù)集運(yùn)行時(shí)間的。公式表示為

(22)

其中，t表示增量算法對(duì)普通聚類(lèi)算法聚類(lèi)所運(yùn)行的時(shí)間；T表示增量算法對(duì)數(shù)據(jù)集聚類(lèi)所運(yùn)行的時(shí)間。Speed越大表示增量聚類(lèi)算法運(yùn)行時(shí)間越短，反之時(shí)間越長(zhǎng)。

5 實(shí)驗(yàn)結(jié)果及分析

對(duì)多視圖數(shù)據(jù)進(jìn)行分塊處理時(shí)，本文采用五種分塊模式，分別占比為：25%、50%、75%和100%，并且采用隨機(jī)分塊模式。為了避免數(shù)據(jù)對(duì)多視圖聚類(lèi)結(jié)果的影響，本文取50次視圖數(shù)據(jù)的平均值作為實(shí)驗(yàn)結(jié)果。分別在WebKB、Wiki、VOC、Handwritten numerals和Caltech101-7數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果如表1～表5所示。

表1 WebKB數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表2 Wiki數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表3 VOC數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表4 Handwritten numerals數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

表5 Caltech101-7數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

通過(guò)對(duì)多視圖數(shù)據(jù)聚類(lèi)性能進(jìn)行分析，從表1-5可以看出，本文算法在5個(gè)數(shù)據(jù)集上均有較高的正確率和RI值，以及較高的F-meansure值，說(shuō)明本文所提出的算法可以保證多視圖數(shù)據(jù)的聚類(lèi)準(zhǔn)確性與聚類(lèi)精度。另外，從表中可以看出，在5個(gè)數(shù)據(jù)集上，當(dāng)視圖數(shù)據(jù)塊為多視圖整個(gè)數(shù)據(jù)集的25%時(shí)，算法的Speed值最大。隨著數(shù)據(jù)塊所占比例的增加，Speed值越來(lái)越小，其原因是隨著數(shù)據(jù)塊的增加，加權(quán)自適應(yīng)聚類(lèi)算法計(jì)算量越大，導(dǎo)致聚類(lèi)時(shí)間越長(zhǎng)。因此在多視圖數(shù)據(jù)中所分的數(shù)據(jù)塊越大，本文的算法越能減少聚類(lèi)運(yùn)算時(shí)間。

6 結(jié)束語(yǔ)

由于現(xiàn)階段所研究的多視圖聚類(lèi)算法運(yùn)行時(shí)間較長(zhǎng)且性能欠佳，本文將K-means算法進(jìn)行改進(jìn)結(jié)合加權(quán)自適應(yīng)算法，實(shí)現(xiàn)數(shù)據(jù)的可分性，即便在視圖數(shù)據(jù)較多的情況下，也能大大提高算法的聚類(lèi)效果?；贛ATLAB平臺(tái)，采用F-meansure、正確率、RI和Speedup作為性能指標(biāo)，針對(duì)WebKB、Wiki、VOC、Handwritten numerals和Caltech101-7進(jìn)行仿真驗(yàn)證。仿真結(jié)果表明，本文所提出的算法與文獻(xiàn)[5]、文獻(xiàn)[6]和文獻(xiàn)[7]相比，不僅提高了多視圖數(shù)據(jù)的聚類(lèi)準(zhǔn)確性與精度，而且還明顯地減少了運(yùn)行時(shí)間，降低資源消耗。說(shuō)明在處理大規(guī)模多視圖數(shù)據(jù)時(shí)，本文所提方法具有良好的可行性，擁有較高的實(shí)用價(jià)值。