李麗亞，閆宏印

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

1 引言

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

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

(15)

(16)

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

(17)

(18)

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

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

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

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

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

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

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

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

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

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

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

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

本文采用4個性能評價指標(biāo)對多視圖聚類算法進行衡量，分別為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)用來評價2個聚類劃分效果的相似程度，公式表示為

(21)

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

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

Speed：該指標(biāo)是用來評價多視圖數(shù)據(jù)集運行時間的。公式表示為

(22)

其中，t表示增量算法對普通聚類算法聚類所運行的時間；T表示增量算法對數(shù)據(jù)集聚類所運行的時間。Speed越大表示增量聚類算法運行時間越短，反之時間越長。

5 實驗結(jié)果及分析

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

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

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

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

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

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

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

6 結(jié)束語

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