改進K-means加權自適應多視圖數據聚類算法

李麗亞，閆宏印

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

1 引言

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

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

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

2 基于加權自適應的多視圖數據聚類算法

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

(1)

雖然以上方法可以對不同樣本的兩種類型信息進行重要性的差異學習，但是在信息融合過程中，需要將空間進行維度變換，可能導致一些信息的損失，而且同維度變換會增加算法的復雜性，使得對節點簇結構的差異性缺乏靈敏度，因此本部分內容提出加權自適應多視圖聚類算法。

如果有Nw個視圖，所有視圖的數據用公式表示為

(2)

由以上的目標函數可以求得多視圖的矩陣分解模型，公式表示為

(3)

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

(4)

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

(5)

其中，e表示數據的稀疏誤差矩陣；H表示數據的低秩數據矩陣。將這種模型應用到多視圖數據中，則加權自適應多視圖數據聚類模型用公式可表示為

(6)

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

(7)

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

(8)

(9)

3 多視圖數據的K-means優化理論

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

綜上可知，J是關于F(w)的凸函數，對其進行求導，可以得到

(15)

(16)

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

(17)

(18)

至此所有視圖數據信息聚類優化已完成。

4 多視圖數據集及衡量指標

4.1 數據集描述

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

1)差異性數據集描述

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

Wiki數據集：該數據集經常用在跨模態的檢索環境中，其中包含訓練樣本2173個、測試樣本693個，類別10個。每個視圖都應用128維的特征向量視圖和10維的主題描述向量視圖。

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

2)相同性數據集描述

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

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

4.2 數據集度量標準

本文采用4個性能評價指標對多視圖聚類算法進行衡量，分別為F-meansure、正確率、RI以及Speedup性能指標。

F-meansure：該指標的公式表示為

(19)

正確率：該指標的公式表示為

(20)

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

RI：該指標用來評價2個聚類劃分效果的相似程度，公式表示為

(21)

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

上面三種評價指標，得出的數據結果越接近1，說明聚類效果越好。

Speed：該指標是用來評價多視圖數據集運行時間的。公式表示為

(22)

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

5 實驗結果及分析

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

表1 WebKB數據集上的實驗結果

表2 Wiki數據集上的實驗結果

表3 VOC數據集上的實驗結果

表4 Handwritten numerals數據集上的實驗結果

表5 Caltech101-7數據集上的實驗結果

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

6 結束語

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