一種改進的多視圖K-均值聚類算法

收稿日期：2014－04－15

基金項目：國家自然科學基金(61300114)；教育部博士點新教師基金(20132302120047)；中國博士后科學基金(2013M530156)；中央高校基本

科研業務費專項資金(HIT.NSRIF.2013066)；教育部-微軟語言語音重點實驗室開放基金-面向大規模文本數據的信息演化分析資助。

作者簡介：伍國鑫(1990 - )，男，陜西渭南人，碩士研究生，主要研究方向：自然語言處理、文本聚類；

劉秉權(1970 - )，男，黑龍江哈爾濱人，博士，副教授，主要研究方向：自然語言處理、Web信息處理；

劉銘(1981 - )，男，黑龍江哈爾濱人，博士，講師，主要研究方向：自然語言處理、文本聚類。

摘要：近幾年來，隨著互聯網的發展以及大數據時代的來臨，具有多種表示即多視圖數據越來越多，如何將傳統的單一表示的數據聚類方法應用在多視圖數據被廣泛研究。其中傳統的K-均值聚類算法因為有效性以及對于大數據的高效性而被擴展到了多視圖數據領域，本文針對最近提出的一個新的多視圖K-均值聚類方法，結合co-training的思想，提出了一個改進的多視圖K-均值聚類算法，并在三個標準數據集上進行了實驗，同時和已有的一些方法進行了比較，結果表明了算法的有效性。

關鍵詞：聚類； 多視圖； K-均值； 協同訓練

中圖分類號：TP181文獻標識碼：A文章編號：2095-2163（2014）03-0011-05

An Improved Multi-view K-means Clustering Algorithm

WU Guoxin， LIU Bingquan， LIU Ming

(School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China)

Abstract：In recent years， with the development of Internet， more and more multi-view data are collected. How to apply the traditional clustering algorithm into the multi-view data have been studied widely. Among them， the K-means clustering algorithm has been extended into the multi-view data firstly because of its efficiently on large-scale dataset. This paper presents an improved multi-view K-means clustering algorithm by introducing the idea of co-training. The paper also evaluates the proposed method on three standard datasets and compares with some baseline methods. The experiment results show the validity of the proposed method.

Key words：Clustering; Multi-view; K-means; Co-training

0引言

聚類分析是數據挖掘以及無監督機器學習領域的基礎問題。目前已經有許多經典的聚類算法，如K-均值、層次聚類以及譜聚類［1-2］等。然而，傳統的聚類算法通常針對具有單一表示或者單一視圖的聚類對象。在多視圖數據的情形下，聚類對象有多種不同的表示并且從每一種表示出發都能對該數據對象進行聚類。多視圖對象實現聚類的一個基本方法就是將該對象的相應于不同表示的樣本向量合并成一個向量，如此則將多視圖的聚類問題轉化成單一視圖的聚類問題，其后即可應用任何已知的單一視圖聚類方法。可是，簡單地將數據對象的不同表示合并成一個統一的形式卻并未考慮到各個不同表示之間的關系，因而如何基于多視圖數據的特點，充分利用各個視圖的信息對數據對象進行有效聚類即已成為多視圖聚類算法的主要目標［3-8］。

多視圖數據廣泛出現在許多應用領域。在自然語言處理領域，一篇文檔或者整個語料庫可能具有多語言版本，每一種語言的版本實際上都是該文檔的一個表示，一個典型實例就是機器翻譯領域中的平行語料庫。公開發表的學術文章可以有摘要、關鍵詞以及文章正文等多種表示，這些表示均能概括文章的主旨內容。而且，互聯網也是多視圖數據的另一個重要來源。網頁可以表示成自然語言文本，同時也可以由網頁中的鏈接和錨文本來表示。其他的則如計算機圖形學中的圖像也都具有大量的不同表示，如像素值、直方圖等，甚至還包括圖像對應的標注文本。此外，在自動語音識別領域，語音數據一方面可以由聲音表示，同時也可以由一系列表示嘴唇移動的圖片來表示。綜上所述，對于這些日漸豐富的多視圖數據的聚類問題，已經引起了人們的廣泛關注和高度重視。

許多現存的多視圖聚類算法都是基于Co-training［9］的思想［10-14］。Co-training最早是為了解決半監督機器學習領域的問題而由Michal Blum等人引入的。其核心思想是同時訓練兩個模型，而后用其中一個模型去預測未標注的訓練數據，再將這些數據加入到原始的標注數據中，利用新得到的訓練數據集訓練另一個模型，如此反復直至達到某一目標。受Co-training的啟發，多視圖的聚類算法旨在利用聚類對象在一個視圖上的聚類結果去影響在其他視圖上的聚類結果，即在聚類過程中考慮到了不同視圖之間的交互作用。這一類型中的一個典型例子就是多視圖的K-均值聚類算法。在該算法中，一個視圖上的聚類結果將會用于初始化另一個視圖的聚類中心，反之亦然。但是，當聚類對象的不同視圖的個數有所增加時，此一方法則變得復雜且難以分析。例如，當出現三個視圖時，任何兩個視圖都可以對最后一個視圖的初始聚類中心進行初始化，但應當選擇哪一個視圖卻難以確定，而當視圖個數更大時，這些問題的復雜度也隨之提升。另一個嚴重的問題則是該算法并不能保證收斂，這也進一步限制了該算法的應用。

為了克服基于Co-training的K-均值聚類算法的這些缺點，并結合其他學者的已有研究成果，本文提出了一個改進的多視圖K-均值聚類方法，該方法具有以下幾個特點：

(1)定義了一個合適的目標函數同時將聚類問題重新表述成為一個凸優化問題。為了最小化該目標函數，必然得出了一個迭代的優化算法。而且由于這是一個凸優化問題，算法的收斂性可以得到保證。

(2)該算法考慮到了不同視圖之間的交互作用，而為了簡化這些交互作用，文中只考慮每兩個視圖之間的交互，通過這一考慮，即可將Co-training的思想擴展到具有大量不同視圖的情形，同時還能保持模型的一致性。第3期伍國鑫，等：一種改進的多視圖K-均值聚類算法智能計算機與應用第4卷

1多視圖K-均值的形式化

K-均值聚類算法已廣泛應用于實際的聚類問題中，研究通過對已有的一個多視圖K-均值算法加以改進，可以更好地利用多視圖數據的特點進行聚類。下面，首先將K-均值聚類算法的求解形式變換成為一個優化問題。

1.1基于聚簇指示矩陣的形式化

從正交非負矩陣因子模型［15-16］的角度，傳統的K-均值聚類方法可以看作是如下的一個優化問題：

minF，G‖X-GF‖2F

s.t.Gik∈{0，1}∑Kk=1Gik=1，i=1，2，…，n(1)

其中，X是輸入樣本矩陣，矩陣的每一行是一個聚類對象的向量表示，每一列則表示這個樣本向量的一維。而G稱之為聚簇指示矩陣，且滿足(1)中的約束條件，即該矩陣的每一個元素為0或者1，并且每一行有且僅有一個位置為1，如果第i行的第k個元素為1，則表明第i個樣本在第k個聚簇中，該矩陣實際上刻畫了這些聚類對象的聚簇結構，圖1即給出了對應的一個樣例。矩陣F是聚簇中心矩陣，其中的每一行表示一個聚簇中心的向量表示。如果n表示樣本個數，K表示聚簇個數，而d為樣本的維度，那么這三個矩陣的大小即可分別表示為n×d、n×K以及K×d。

100

010

001

100

010聚簇1：{1，4}

聚簇2：{2，5}

聚簇3：{3}

圖1聚簇指示矩陣

Fig.1Cluster indicator matrix

1.2多視圖聚類的目圖標函數

如果將上節中定義的目標函數寫成標量的形式，就會發現這個目標函數實際上給出的是每個樣本到其所在聚簇中心距離的平方和，而該平方和就是K-均值聚類算法 的原始目標函數。為了適應多視圖的情形，Cai Xiao等［17］提出了一個新的目標函數：

minF（v），G，α(v)∑Mv=1(α(v))γ‖X(v)-GF(v)‖1，2

s.t.Gik∈{0，1}，∑Kk=1Gik=1.n∑Mv=1α(v)=1，α(v)＞0(2)

式（2）與式(1)的區別可作如下表述：

首先，在多視圖情形下，每一個聚類對象有多個表示，因此也會有多個樣本輸入矩陣，對應于視圖v的樣本矩陣為X(v)，類似地也有多個聚簇中心矩陣F(v)，同時這個新的目標函數對各個視圖亦賦予了不同的權值α(v)。和式(1)相同，該目標函數中也有一個聚簇指示矩陣，該指示矩陣將不同的視圖實現了聯結。但是這個目標函數卻存在一個問題，也就是函數假定了在每個視圖上的聚簇結構完全相同，基于該假定，這個目標函數中只有一個聚簇指示矩陣。在實際的聚類問題中，不同視圖上的聚類結果可能偏差很大，強制要求所有視圖的聚簇結構一樣實際上是在不同的聚類結果中選取了一個折中，但如此一來就有可能損害最優的聚類結果，因為在其中加入了較差的聚類結果。為了解決這一問題，文中對這個目標函數進行了修改，得到了如下的目標：

minF(v)，G(v)，α(v)∑Mv=1(α(v))γ‖X(v)-G(v)F(v)‖2F

+λL(G(1);G(2);…，G(M))(3)

其中，M為不同視圖的個數。

在式(3)中，對每個視圖賦予了一個聚簇指示矩陣G(v)，同時為了保證各個聚簇指示矩陣之間的交互關系又加入了一個約束項，而λ則表示了該約束項的強度。如果沒有該約束項，將會很容易看到，最小化該目標函數即是在每一個視圖上分別最小化 (1) 式，因為各個視圖之間沒有任何關系。約束項的設置就是控制各個視圖的聚類結果之間的差異，防止結果之間出現較大的偏差。為了達到這個目的，即需要求約束函數L滿足如下的兩個條件：

(1)非負性，即對于任意的參數值，L≥0；

(2)當且僅當各個視圖的聚簇矩陣相同時，L=0。

然而，在本文的模型中對于每個視圖都有一個聚簇指示矩陣，而聚類的最終結果只能是一個，因此就必須從這些指示矩陣中選擇一個最優的結果。目前，研究主要是根據數據的特點，定義一個主視圖。一個視圖稱為主視圖，當且僅當該視圖是聚類對象的相比于其他視圖的一個更好的表示。如何選取主視圖則依賴于研究者對數據的理解。

下節將給出一個具體的約束函數。

1.3基于視圖成對交互的約束項

這一節將會給出一個具體的約束函數的定義，這個約束函數將多個視圖之間的交互關系分解為若干個視圖之間的成對交互，如此變換后一方面能夠簡化視圖之間的交互作用，另一方面則可以在有更多視圖的情形下依然保持模型的一致性。L的定義如下：

L(G(1)，G(2)，…，G(M))=∑(j，k)∈1l(j，k)（4）

式（4）中的I稱為交互集，定義如下：

I={(j，k)｜j＜k，j，k=1，2，……，I}

該集合定義了有哪些視圖之間存在交互作用。而l(j，k)的定義即如下：

l(j，k)=‖(G(j)-G(k))‖2F

=∑ni=1‖(g(j)i-g(k)i)‖22（5）

其中，g(j)i表示視圖j的聚簇指示矩陣的第i行，由聚簇指示矩陣的定義可知

‖g(j)i-g(k)i‖22=0g(j)i=g(k)i

2g(j)i≠g(k)i（6）

因而本研究中定義的L符合上一節提出的約束函數需要滿足的兩個條件。上面已經定義了交互集，集合的每個元素表示兩個彼此有影響的視圖，而對于M個視圖，交互集可能的元素個數即為M(M-1)/2，當M很大時，該集合元素就會很多，模型也隨之趨于復雜。并且，在實際聚類中，并不是任意兩個視圖之間都會存在交互關系，為此即可根據數據集定義一個合適的交互集。

2模型求解與優化算法

前述分析中已經給出了一個改進的多視圖聚類目標函數，下面即將給出一個迭代優化算法。

2.1迭代優化算法

算法的模型中有三個參數需要求解：F(v)，G(v)以及α(v)，為了求得最優解，每次迭代都需要固定兩個參數，其后求出另一個參數的最優值，最終達到收斂。首先固定G(v)以及α(v)，更新F(v)。此時目標函數的優化實際上相當于K-均值算法中聚簇中心的更新過程，即對每個聚簇，取該聚簇中所有樣本的平均值作為該聚簇新的中心。接下來，則要固定F(v)以及α(v)，更新G(v)，不失一般性，假設要更新G(1)，可將目標函數寫成如下形式：

J=∑v(α(v))γ‖X(v)-G(v)F(v)‖2F+

λ∑(1，j)∈I‖G(1)-G(j)‖2F+C

=∑ni=1(∑v(α(v))γ‖x(v)i-gi(v)F(v)‖22)+

λ∑ni=1∑(1，j)∈I‖g(1)i-g(j)‖22+C

=∑ni=1(∑v(α(v))γ‖x(v)i-g(1)iF(v)‖22+

λ∑(1，j)∈I‖g(1)i-g(j)‖22)+C(7)

從式（7）可以看到，為了最小化J，只需要對每一個樣本，求解如下的優化問題：

ming(1)i∑v(α(v))γ‖x(v)i-g(1)iF(v)‖22

+λ∑(1，j)∈I‖g(1)i-g(j)i‖2（8）

因為向量g(1)i的元素均為0或者1，加之有且僅有一個元素為1，則g(1)i可能的取值有K個，此時枚舉所有可能的取值后，求出最優的解，對每個樣本依次求出對應的g(1)i，即可推得最優的聚簇指示矩陣G(1)。

接下來，就需要更新權值α(v)，即求解如下的最優化問題：

minα(v)∑v(α(v))γ‖X(v)-G(v)F(v)‖2F+λL

s.t.∑Mv=iα(v)=1，α(v)≥0（9）

利用Lagrange 函數消除約束，由其可以得到：

∑Mv=1(α(v))γH(v)+λL-β(∑Mv=1α(v)-1)（10）

式（10）中，H(v)=‖X(v)-G(v)F(v)‖2F中，對式（10）關于α(v)求導，并令導數為0即可以得到：

α(v)=(β/γH(v))1/(1-γ)（11）

將∑vα(v)=1代入上式，進一步得到了α(v)的更新公式：

α(v)=(γH(v))1/(1-γ)∑Mv=1(γH(v))1/(1-γ)（12）

至此，則完整給出了所有參數的更新過程。

2.2算法超參設定

以上算法中有兩個超參需要手工設定，特別地參數γ控制著不同視圖的權值分布，而γ也控制著一致性約束的強度。如果γ值很大，則算法賦予每個視圖的權值接近于1/M；反之，如果γ值很小，那么具有更小H(v)值的視圖對應的取值更大。通過在區間 ［2， 50］ 內按照一定的步長進行一維搜索得到最優參數，而在區間［1e-8， 0.1］直接進行搜索，可得到最優參數γ。當然，也許還存在更好的啟發式方法可用于選擇參數的最優值。

3實驗及結果分析

3.1 數據集

本文在三個標準數據集上進行了聚類實驗，這三個數據集分別是：

(1) Rertus21 578數據集。該語料庫包含許多不同的類別。在實驗過程中，選取了包含新聞最多的前10個類別，從每個類別中隨機選取了最多100篇文檔。文檔的標題和正文可看做是兩個不同的視圖，而正文則是主視圖。

(2)Rcv1。該語料庫包含同一篇文檔的多語言版本，對于一篇英文文檔，包含有通過機器翻譯生成的其他語言的相應文檔。總共有六種類別，可分別從每一類別中隨機選取200篇英文文檔以及對應的法文、德文版本。英文、法文以及德文被認為是三個不同的視圖，其中英文是主視圖。由于使用詞包模型得到的特征向量非常稀疏，又使用PLIS［18］進行了降維。

(3)UCI digits dataset是阿拉伯數字的手寫字識別數據集，總共有0~9 10個類別，各個類別均有200個實例，每個實例有四種視圖，分別是傅里葉系數FOU，相關系數FAU以及像素值PIX和KAR系數，其中PIX是主視圖。

表1即給出了這三個數據集的一個整體匯總。表1數據集匯總

Tab.1Dataset summary數據集#樣本#視圖#聚簇Reuters21 578901210Rcv11 20036UCI digits2 0004103.2實驗設置

實驗中，使用了一些經典的聚類算法以及最新的多視圖聚類算法，并將這些方法的結果同本文提出的方法進行了比較。具體的對比分析可做如下闡述：

（1）K-均值。在每個視圖上分別使用K-均值進行聚類，并將最好的視圖上的結果作為最終的聚類結果。

（2）譜聚類。在每個視圖上分別進行譜聚類，也將最好視圖上的結果作為最終的聚類結果。

（3）RMKMC 是在文獻［1］中提出的一個新的多視圖聚類算法。

文中使用了三個標準的聚類評價指標：純度(Purity)，正規化的互信息(NMI)以及F-值(F-score)［14］。因為本文提出的方法以及前面提到的比較方法都依賴于初始化，因此對于每一種方法都進行了隨機初始化并且運行50次，基于此來計算平均聚類結果以及標準差。三個數據集上的結果分別如表2、表3和表4所示（括號內為標準差）。

表2Reuters21 578實驗結果

Tab.2Experiment results on Reuters21 578 datasetMethodPurityNMIF-scoreK-means0.367(0.057)0.405(0.063)0.377(0.034)譜聚類0.394(0.034)0.460(0.032)0.360(0.030)RMKMC0.439(0.044)0.499(0.042)0.413(0.040)Ours0.457(0.020)0.504(0.020)0.433(0.020)表3RCV1數據集實驗結果

Tab.3Experiment results on RCV1 datasetMethodPurityNMIF-scoreK-means0.433(0.038)0.596(0.054)0.495(0.032)譜聚類0.430(0.038)0.608(0.038)0.478(0.036)RMKMC0.475(0.026)0.616(0.030)0.518(0.021)Ours0.510(0.020)0.634(0.022)0.514(0.020)表4UCI digits數據集實驗結果

Tab.4Experiment results on UCI digits datasetMethodPurityNMIF-scoreK-means0.709(0.039)0.737(0.059)0.657(0.057)譜聚類0.756(0.043)0.786(0.071)0.720(0.067)RMKMC0.784(0.028)0.838(0.042)0.761(0.036)Ours0.826(0.025)0.862(0.050)0.810(0.040)3.3實驗結果分析

表2給出了在Reuters21 578數據集上的實驗結果。結果表明，同單視圖的K-均值和譜聚類相比，多視圖的K-均值聚類算法在Purity、NMI上提高了9%~10%左右，而在F-score上則提高了4%~6%左右。關于其他兩個數據集上的結果也與這一結論相符。而本文提出的方法同RMKMC相比則有了顯著提升，這也表明了該算法的有效性。

4結束語

本文通過引入一個一致性約束函數，得到一個新的多視圖聚類目標函數，為了最小化這個新的目標函數，則提供了一個迭代更新的優化算法，該算法能夠有效地給出一個局部最優解。一致性約束函數能夠有效地結合多種視圖提供的信息，從而提高聚類的效果。在三個數據集上的結果表明了本文提出的改進方法的有效性。

參考文獻：

［1］Manning C D， Raghavan P， Schütze H. Introduction to information retrieval［M］. Cambridge: Cambridge University Press， 2008.

［2］NG A Y， JORDAN M I， WEISS Y. On spectral clustering analysis and an algorithm［J］. Proceedings of Advances in Neural Information Processing Systems. Cambridge， MA: MIT Press， 2001， 14: 849-856.

［3］SUN S. A survey of multi-view machine learning［J］. Neural Computing and Applications， 2013， 23(7-8): 2031-2038.

［4］TANG W， LU Z， DHILLON I S. Clustering with multiple graphs［C］//Data Mining， 2009. ICDM'09. Ninth IEEE International Conference on. IEEE， 2009: 1016-1021.

［5］WANG H， NIE F， HUANG H. Multi-view clustering and feature learning via structured sparsity［C］//Proceedings of the 30th International Conference on Machine Learning (ICML-13)， 2013: 352-360.

［6］CHAUDHURI K， KAKADE S M， LIVESCU K， et al. Multi-view clustering via canonical correlation analysis［C］//Proceedings of the 26th annual international conference on machine learning. ACM， 2009: 129-136.

［7］de Sa V R. Spectral clustering with two views［C］//ICML Workshop on Learning With Multiple Views， 2005.

［8］ZHOU D， BRUGES C J C. Spectral clustering and transductive learning with multiple views［C］//Proceedings of the 24th international conference on Machine learning. ACM， 2007: 1159-1166.

［9］BLUM A， MITCHELL T. Combining labeled and unlabeled data with co-training［C］//Proceedings of the Eleventh Annual Conference on Computational Learning Theory. ACM， 1998: 92-100.

［10］KUMAR A， DAUM H. A co-training approach for multi-view spectral clustering［C］//Proceedings of the 28th International Conference on Machine Learning (ICML-11)， 2011: 393-400.

［11］BISSON G， GRIMAL C. Co-clustering of multi-view datasets: a parallelizable approach［C］//ICDM， 2012: 828-833.

［12］BICKEL S， SCHEFFER T. Multi-view clustering［C］//ICDM， 2004， 4: 19-26.

［13］KUMAR A， RAI P， DAUM III H. Co-regularized multi-view spectral clustering［C］//NIPS， 2011: 1413-1421.

［14］Bickel S， Scheffer T. Estimation of mixture models using Co-EM［M］.Machine Learning: ECML 2005. Springer Berlin Heidelberg， 2005: 35-46.

［15］Ding C， He X， Simon H D. Nonnegative Lagrangian relaxation of K-means and spectral clustering［M］.Machine Learning: ECML 2005. Springer Berlin Heidelberg， 2005: 530-538.

［16］Greene D， Cunningham P. A matrix factorization approach for integrating multiple data views［M］//Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg， 2009: 423-438.

［17］CAI X， NIE F， HUANG H. Multi-view k-means clustering on big data［C］//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. AAAI Press， 2013: 2598-2604.

［18］HOFMANN T. Probabilistic latent semantic indexing［C］//Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM， 1999: 50-57.