K-means型多視圖聚類中的初始化問題研究*

洪 敏，賈彩燕+，王曉陽

1.北京交通大學 計算機與信息技術學院，北京 100044

2.交通數據分析與挖掘北京市重點實驗室，北京 100044

1 引言

由于不同測量方法的使用，多視圖數據廣泛存在于各種應用中[1-7]。例如由文本、圖片、視頻和超鏈接組成的網頁，以及圖像數據中SIFT（scale invariant feature transform）[8]、HOG（histogram of oriented gradient）[9]、LBP（local binary pattern）[10]、GIST[11]、CTM（color texture moment）[12]和CENTRIST[13]等不同的局部特征描述。也就是說，這些數據集上同一實例有多種不同的表示形式，這些表現形式常被稱為視圖。既然不同的視圖從不同角度對數據進行了描述，并且具有不同的判別力，那么如何有效結合來源于多個視圖的數據，并找到滿足所有視圖的最優劃分是當前研究領域的一個熱點。

K-means算法不僅可以用在傳統的單視圖學習中，還可以拓展到多視圖場景下。本質上講，K-means型多視圖聚類算法不僅存在K-means算法初值敏感和類個數事先指定的問題，還由于綜合考慮來自多個視圖的數據而造成了數據規模不一的現象。目前，多視圖聚類中常用的初始化方法是隨機初始化和全局核K-means[14]初始化方法。前者因隨機性使得聚類效果不穩定，后者結果雖具有確定性，但是在大規模數據中比較耗時。另外，這兩種初始化方法都需要事先指定類數目。那么如何有效解決K-means型多視圖聚類的初始化問題呢？本文基于單視圖下的K-means初值敏感和類個數選擇問題，研究了現存的多種經典初始化方法，如隨機初始化、K-means++[15]、全局（核）K-means、基于蒙特卡洛取樣（Markov chain Monte Carlo，MCMC）的初始化方法AFKMC2（assumption-freeK-MC2）[16]和密度峰值快速搜索方法（clustering by fast search and find of density peaks，DPC）[17]，并將這些方法應用于K-means型多視圖聚類算法的初始化中，研究不同的初始化方法對K-means型多視圖聚類效果的影響。另外，還提出了一種基于采樣的主動式初始中心選擇方法（sampledclustering by fast search and find of density peaks，SDPC），進一步優化K-means型多視圖聚類的初始中心和類個數的選擇策略。多個多視圖基準數據集的實驗結果表明：不同的初始化方法可以改善K-means型多視圖聚類的效果。與DPC相比，SDPC在聚類精度和效率上取得了較好的折衷。

2 相關工作

針對多視圖學習研究者們進行了很多研究。目前，現存的大部分多視圖聚類方法都是采用最小化不一致性的思想將單視圖經典算法拓展到多視圖場景下[18]。Bickel和Scheffer[18]提出兩視圖場景下的EM（expectation maximization）算法和K-means算法。另外，他們也研究了多于兩個視圖的混合模型估計問題[19]。de Sa[20]提出了一個二視圖譜聚類方法。這種方法的主要思想是為視圖創建一個二部圖以描述兩個視圖中信息共現的情況。Blaschko、Lampert[21]和Chaudhuri、Kakade等人[22]從典型相關性分析考慮，他們認為可以先投影數據，再進行聚類。Zhou和Burges[23]提出一個面向多視圖聚類中的正則割（normalized cut）框架。這個模型包含一個先驗參數，用于決定每個視圖的相對重要性。Kumar等人[24-25]使用來自一個視圖的譜嵌入，進而在其他視圖上進行聚類，目的是為了保持不同視圖上聚類結果的一致性。Wang等人[26]也設計了一個多視圖譜聚類方法。該方法是依賴Pareto優化尋找所有視圖上最佳公共割。Nie和Li等人[27]提出一個新型的無參數自動加權的多圖學習框架。這種方法可以用于多視圖聚類中。Nie和Cai等人[28]從具有自適應性的近鄰角度提出了一種新型的多視圖聚類算法。以上方法都集中研究了不同視圖之間的關系。

經典的K-means聚類是一種基于中心的聚類方法[29]。由于具有計算成本低、易于并行處理的特點，K-means聚類被廣泛應用于大規模的數據聚類問題中。但是算法結果易受到初始聚類中心的影響。若選取的初始類中心比較好，根據Forgy方法將數據點指派到相應的初始類中心，最終會得到在全局上最優的聚類結果。但當初始中心選擇不好時，容易產生空類，得到不好的劃分結果。因此，學者們給出了多種不同的初始類中心選擇方法，如K-means++和AFKMC2等。

面對多視圖聚類問題，研究者們也提出了多種K-means型多視圖聚類算法，如WMKC（weighted multi-viewK-means clustering）、MVKKM（kernel-based weighted multi-viewK-means clustering）[30]，WMCFS（weighted multi-view clustering with feature selection）[31]和 RMKMC（robust multi-viewK-means clustering）[32]。其中，WMKC算法考慮了不同視圖的重要性，MVKKM用于處理非線性可分的多視圖聚類問題，WMCFS綜合考慮數據視圖和視圖特征的貢獻，進一步優化多視圖聚類效果，RMKMC在目標函數?2,1范式下考慮視圖的重要性。值得關注的是，這些K-means型多視圖聚類算法不可避免地存在K-means聚類中初始中心敏感和類個數事先指定的問題。因此，本文將單視圖的各種初始化方法用于K-means型多視圖聚類中，進一步研究對多視圖聚類的效果。

3 K-means型多視圖聚類算法和初始化算法

本章詳細介紹幾種經典的K-means型多視圖聚類算法和K-means常用的初始化方法。

3.1 K-means型多視圖聚類算法

（1）WMKC算法

當處理多視圖數據時，直接的方法是將所有視圖特征拼接起來執行K-means聚類算法。在所有視圖中，每個數據都會被指派到同一個簇。但是這種方法平等看待每個視圖，從而聚類結果也沒有得到優化。因此通過對多視圖數據的每一個視圖增加權重參數，進而體現出不同視圖的重要程度，將該方法簡記為WMKC。相應的目標函數如式（1）所示：

ωv表示第v個視圖的權重，滿足。p1是根據先驗知識選擇的參數，用于控制視圖權重ωv的分配。是在視圖v中簇k的中心。由于不同視圖下數據表示形式不一，從而同一個簇的簇中心也是不同的。

（2）MVKKM算法

Tzortzis和Likas[30]提出基于核的加權多視圖K-means算法（MVKKM）。與上述普通帶權多視圖K-means算法（WMKC）相比，它可以處理非線性可分的簇。主要是通過預先定義的核函數將數據映射到一個高維特征空間中，并將其作為算法的輸入。一般情況下，對于所有視圖可采用線性核函數和高斯徑向基核函數進行變換。相應的目標函數如式（2）所示：

（3）WMCFS算法

Xu和Wang等人[31]提出具有特征選擇的加權多視圖聚類算法（WMCFS）。該算法通過對視圖和視圖中的特征施加兩種不同的加權模式，從而在聚類時選出最優視圖和每個視圖中最具代表性的特征。目標函數如式（3）所示：

τv表示長度為dv的特征權重向量，表示在視圖v中第t個特征的權重。是用于控制特征權重向量τv的稀疏性。

（4）RMKMC算法

利用G-正交非負矩陣分解等價于松弛性的K-means聚類[33]，Cai和Nie等人[32]引入類指示矩陣重新設計了K-means聚類目標函數，如式（4）所示：

式中，X∈Rd×n是具有d維特征n個數據點的數據矩陣，F∈Rd×K是簇中心矩陣，G∈Rn×K是簇指示矩陣，每一行有且只有一個Gik=1。在此基礎上，Cai等人[32]提出了一種具有魯棒性的多視圖K-means聚類算法（RMKMC）。目標函數如式（5）所示：

上式中含有共同的簇指示矩陣G，且目標函數上施加了結構性稀疏約束?2,1-范式，從而對含有異常值的輸入數據具有魯棒性。

3.2 類初始化方法

目前，K-means型多視圖聚類中常用的初始化方法有隨機初始化和全局核K-means初始化方法。隨機初始化結果具有不確定性，全局核K-means雖初始中心唯一，但是在大數據中耗時太長。另外，這兩種方法都需要事先指定類個數。

針對單視圖下K-means聚類中存在的初值敏感和類個數指定問題，學者們給出了多種初始類中心選擇策略：如隨機初始化、K-means++、AFKMC2和DPC初始化方法。

（1）隨機初始化

隨機初始化是聚類中最常用、最直接的類指派方法，即隨機將每一個數據點指派到K個類之一。但是結果受隨機影響大。

（2）K-means++初始化

Arthur和Vassilvitskii[15]提出用于為K-means聚類選擇初始值（種子）的算法（K-means++）。核心思想是使所選取的K個種子之間盡可能得遠。該方法首先隨機選擇一個點作為初始聚類中心；接著計算數據中每一個點x與所選最近類中心之間的距離D(x)；當選擇一個新的數據點作為下一個中心時，D(x)越大，越有可能被選為類中心，直到選出了K個類中心為止。但是這種種子選取策略需要計算所有點到類中心之間的距離。當數據量很大時，這種方法計算復雜性高。另外，這種方法也可能選到異常值或者處于密度低的區域點作為類中心，出現次優的聚類結果。

（3）基于蒙特卡洛取樣MCMC的初始化方法

Bachem和Lucic等人[34]提出一種加速K-means++采樣的方法（K-MC2）。該方法基于MCMC采樣，首先隨機選取第一個類中心，接著使用均勻分布下的Metropolis-Hasting算法[35]構建一個長度為m的馬爾可夫鏈，選擇下一個中心不再需要對所有數據點計算D(x)，只需要計算鏈上m個點和所選類中心的距離。由于K-MC2在數據集服從特定分布時才能得到較好的效果，因此文獻[16]又提出了一種新型的初始化方法 Assumption-freeK-MC2，簡稱 AFKMC2。其中，Metropolis-Hasting算法采用非均勻分布，服從任何分布下的數據均可應用該算法。

（4）全局核K-means算法

基于全局K-means[36]和核K-means[37]算法，Tzortzis和Likas[14]提出了具有增量確定性的全局核K-means算法。該算法使用K-means局部搜索策略對全局進行優化以克服初始中心敏感的問題。每執行一次核K-means得到一個最佳的簇中心，直至得到K個類中心。算法步驟如下：

算法1全局核K-means算法

輸入：數據集X={x1,x2,…,xn}的核矩陣，類數目K。

輸出：類劃分（K個類中心）。

步驟1K=1執行核K-means算法找到類中心m1(1)。

步驟2K=2時，初始中心是(m1(1),xn)執行核K-means，重復執行n次，找到最佳類中心(m1(2),m2(2))且核K-means目標函數誤差最小。其中，xn∈X。

步驟3依此類推，直到找到K個最佳的類中心。

這種方法的優勢是具有確定性，聚類結果不受類初始化的影響。同時能夠劃分輸入空間中非線性可分的簇。但該方法計算復雜度過高，不適于處理數據集較大的聚類問題。

（5）密度峰值快速搜索方法（DPC）

Rodriguez和Laio[17]提出一種基于密度的聚類算法。他們認為類中心需要滿足兩個條件：一是類中心是密度較大的點；同時，不同類中心之間具有相對較遠的距離。在算法中使用ρi描述樣本i的局部密度，δi描述類中心之間的距離。具體定義如式（6）和式（7）所示：

其中，dij是樣本i和j之間的距離，dc是樣本密度的鄰域半徑。當χ?0時，χ(x)=1，否則χ(x)=0。

但若i是局部密度最大的樣本，則令δi=maxjdij。

可見類中心是那些ρi和δi都比較大的點，因此該方法在決策圖右上角選擇K個點作為類中心，并將剩余數據指派到與其距離最近且密度比它大的數據樣本所在的簇中。該方法利用主動式策略解決了類個數和類中心選擇的問題，通過一次指派策略完成類劃分。當樣本間距離給定時具有較高的聚類效率，但當數據規模太大，且樣本間距離未事先給定時，樣本點對間距離計算時間復雜度高。

4 基于采樣的主動式初始中心選擇方法

目前，多視圖學習常用的思想可分為兩種：一是分別對每個視圖聚類，再按照某個規則集成它們的結果；另一種是將來自不同視圖中的信息融合到一個統一的表示空間中，然后在該空間下尋找最佳類劃分。無論使用哪種方法，與傳統的單視圖聚類一樣，多視圖聚類效果也會受到初始類中心的影響。因此，可考慮將單視圖下的初始化結果作為多視圖聚類中的初始中心。但這種方式也有一定的問題：首先，由于事先無法確定多個視圖間的重要性差異，這種初始化方法需要選擇哪個視圖用于初始化；其次，大部分初始化方法需要提前指定類個數，而類個數需要專家知識，不容易獲得。雖然DPC初始化方法可以確定類個數和類中心，但是在多視圖場景下，由于考慮了多個視圖的數據使得數據規模較大，會造成DPC算法中距離計算復雜度過高的問題。

對于K-means型算法初始中心的選擇并不一定要求是類中心，只要分散在各個類中即可。針對以上問題，提出一種基于采樣的主動式初始中心選擇方法（SDPC）。在SDPC中，首先對原始數據均勻采樣，利用DPC算法在樣本集上獲得類中心和類個數，再將其作為多視圖K-means的初始中心，最終得到類劃分結果。對于多視圖場景下的初始樣本選取共有兩種方法：選擇其中的一個視圖或將多個視圖融合之后作為初始數據。SDPC算法的流程如算法2所示。

算法2基于采樣的主動式初始中心選擇算法（SDPC）

輸入：Xv或者是X'，采樣比例ρ。其中，Xv∈{X1,X2,…,XV}，X'表示融合視圖。

輸出：K-means型多視圖聚類的類劃分。

步驟1對Xv或X'按采樣比ρ均勻采樣，得到樣本Xs。

步驟2在Xs上使用DPC算法獲得初始類個數K和類中心InitCen。

步驟3以K和InitCen在X'上運行K-means算法。

步驟4得到多視圖K-means的初始類劃分。

其中，X'的融合方式有三種：一是不考慮視圖重要性直接融合多個視圖；二是核函數下的視圖權值融合；三是視圖權和特征權下的雙權融合模式。

相比隨機初始化、K-means++、全局核K-means初始化和AFKMC2初始化方法而言，本文所提出的基于采樣的主動式初始中心選擇方法（SDPC）通過主動式選擇類中心和類個數解決了K-means型聚類算法在單視圖和多視圖場景中的初值敏感問題。另外，在中心選擇方面，SDPC中采樣策略和K-means再迭代策略的應用不僅加速了密度峰值快速搜索方法（DPC）的中心選擇效率，還能進一步確定初始類劃分，進而改善了聚類效果。

5 實驗與結果

本章將基于采樣的主動式初始中心選擇方法（SDPC）和現有的其他五種初始化方法應用到K-means型多視圖聚類算法中，并在標準數據集上進行實驗。實驗結果采用標準化互信息[38]和純度[39]兩個標準聚類評估指標。另外，計算了初始化所需時間衡量不同初始化方法在K-means型多視圖聚類中的效率。

5.1 數據集描述

本次實驗采用的數據集是Handwritten numerals(http：//archive.ics.uci.edu/ml/datasets/Multiple+features)、Caltech101-7[40]、MSRC-v1[41]、COIL-20(http：//www.cs.columbia.edu/CAVE/software/softlib/coil-20.php)和Pascal Visual Object Classes 2007(http：//host.robots.ox.ac.uk/pascal/VOC/)。前4個數據集的多個視圖之間是同質的，都利用不同特征描述同一圖像，最后一個是由文本和圖像構成的異質視圖數據集，數據集總體情況如表1所示。

Table 1 Datasets summary表1 數據集情況

HW（handwritten numerals）：由2 000個0～9數字類組成的手寫體數據。該數據共有6個特征：76 FOU(Fourier coefficients of the character shapes)、216 FAC(profile correlations)、64 KAR(Karhunen-Love coefficients)、240 PIX(pixel averages in 2×3 windows)、47 ZER(Zernike moments)、6 MOR(morphological features)。實驗中僅使用前5個具有代表性的視圖。

Caltech101-7：是一個由101類組成的對象識別數據集。實驗中僅選取廣泛使用的7個類，即Face、Motorbike、DollaBill、Garfield、Snoopy、Stop-Sign、Windsor-Chair，共1 474張圖片。由圖片的48維Gabor feature，40維 Wavelet Moments，254維 CENTRIST feature，1 984維HOG feature，512維GIST feature，928維LBP feature形成多個視圖。

MSRC-v1：是一個含有8個類240張圖片的場景識別數據集。選擇7個類，即tree、building、airplane、cow、face、car、bicycle。每個類有30張圖片，把每張圖片的4個可視化特征（24維CM(colour moment),512維 GIST，254維 CENTRIST，256維 LBP(local binary pattern)）作為不同視圖。

COIL-20：是一個含有1 440張、20個類的哥倫比亞圖像數據集，且每個類含有72張圖片。由圖片的1 024維密度、3 304維LBP和6 750維Gabor特征構成3個視圖。

Pascal Visual Object Classes 2007(VOC 2007)：該數據集是有關自然圖像的數據。采用其中的20個類aeroplane、bicycle、bird、boat、bottle、Bus、car、cat、chair、cow、dining table、dog、horse、motorbike、person、potted plant、sheep、Sofa、train、tv/monitor，并選取5 649張圖片用于實驗。由圖片的512維GIST特征和圖片標注的 TF-IDF（term frequency-inverse document frequency）值組成兩個不同的視圖。

5.2 聚類評價指標

為了評價各種初始化方法在不同多視圖算法上的聚類效果，文中使用標準化互信息（normalized mutual information，NMI）[38]和純度（Purity）[39]。

（1）標準化互信息（NMI）

該衡量預測類標與真實類標的相近程度。計算公式如下：

式中，C是真實的類標，C'是計算得到的類標，K是真實類數目，K'是算法中的類個數，表示真實類i中節點的數量，表示計算出的類j中節點的數量，nij表示將類i的節點分配到計算后j中節點的數量。

（2）純度（Purity）

純度是另一個評價聚類質量的指標。純度越高，聚類效果越好。計算公式如下：

式中，Ω=(ω1,ω2,…,ωK)表示算法中的聚類結果，C=(c1,c2,…,cj)表示實際類別集合，N是數據總數。

5.3 結果比較

本節具體展示不同初始化方法下K-means型多視圖聚類算法在多個基準多視圖數據集上的實驗結果。對于AFKMC2，由于m=200時表現出較好性能，選用鏈長m=200。對于SDPC，選擇性能穩定且較優的采樣比例。在Handwritten numerals、Caltech101-7和COIL-20數據集上選取20%的采樣率，MSRC-v1和Pascal Visual Object Classes 2007選取50%的采樣比率。表2～表5展示了5個基準數據集的多視圖算法在不同初始化方法上NMI、Purity和初始化用時。其中HW數據集在WMKC、MVKKM和RMKMC算法上參數值分別為p1=10，p2=3和r=2，WMCFS參數值分別為p=10和β=0.1；Caltech101-7數據集在WMKC、MVKKM和RMKMC算法上參數值分別是p1=15，p2=5和r=16，WMCFS參數值分別為p=5和β=0.000 5；MSRC-v1數據集在WMKC、MVKKM和RMKMC算法上參數值分別為p1=25，p2=5和r=10，WMCFS參數值分別為p=14和β=0.000 1；COIL-20數據集在WMKC、MVKKM和RMKMC算法上參數值分別為p1=10，p2=8和r=8，WMCFS參數值分別為p=5和β=0.5；VOC2007數據集在WMKC和MVKKM參數值分別為p1=30和p2=15，WMCFS參數值取p=20和β=0.000 5。VOC2007在RMKMC算法中全局K-means初始化在24 h沒有得到實驗結果，使用其他五種初始化方法時目標函數無法收斂，表中使用“*”表示。另外，最好結果加粗表示，次優結果用斜體加線表示?！啊北硎?4 h內該算法在數據集上沒有得到實驗結果。

Table 2 NMI,Purity and Time comparison results on different initialization methods of WMKC表2 WMKC中各初始化方法的NMI、Purity和Time結果

Table 3 NMI,Purity and Time comparison results on different initialization methods of MVKKM表3 MVKKM中各初始化方法的NMI、Purity和Time結果

Table 4 NMI,Purity and Time comparison results on different initialization methods of WMCFS表4 WMCFS中各初始化方法的NMI、Purity和Time結果

Table 5 NMI,Purity and Time comparison results on different initialization methods of RMKMC表5 RMKMC中各初始化方法的NMI、Purity和Time結果

總體上看，不同的初始化方法在K-means型多視圖聚類算法中表現出不同的性能，本文所提出的基于采樣的主動式選擇初始中心的方法（SDPC）較密度峰值搜索算法（DPC）在精度和效率上取得了較好的折衷。從表2～表5可看出：全局（核）K-means初始化方法效率較低，不適于實際中較大規模數據的聚類。AFKMC2較K-means++而言，采樣速度明顯加快，但聚類精度有時略有損失，如表2和表3所示。SDPC可以主動式選擇類數目和類中心，加上均勻采樣策略和K-means再迭代策略的選擇，不但在效率上優于DPC，在精度上也常優于DPC的直接指派策略。

同時，還對比了單視圖下的SDPC初始化方法在多視圖聚類方法中的效果。以HW數據集的WMKC聚類方法為例,展示了采樣比例為20%的聚類結果，見表6。

由表6可見，相比在融合空間進行SDPC初始化，mfeat_fou視圖使用采樣比是20%的SDPC初始化方法在WMKC多視圖聚類效果是最好的。但是由于事先未能知道該視圖的重要性，存在著初始化視圖選擇問題，因此在實驗中選用多個視圖融合之后再進行初始化的策略以對比各初始化方法的優劣。

Table 6 Results on HW of different views表6 HW中不同視圖下的結果

另外，由于SDPC的聚類效果受采樣比例的影響，選取了有代表性的同質視圖數據集HW（見圖1）和異質視圖數據集VOC2007（見圖2）驗證不同采樣比例對各K-means型多視圖聚類算法性能的影響。

由圖1可看出，總體上數據集HW上受SDPC數據集采樣比例的影響較小，在一定程度上可以改善聚類效果。另外，WMCFS由于自身算法的特點，不同采樣比例下的SDPC聚類效果是最優的?？傮w上看，當采樣率是20%時，多視圖聚類算法的NMI值相對理想，可推測出該方法下所獲得的初始中心是分散在每個類中的。

Fig.1 NMI of SDPC on HW in different sampling ratios圖1 不同采樣比下SDPC在HW上NMI變化情況

Fig.2 NMI of SDPC onVOC2007 in different sampling ratios圖2 不同采樣比下SDPC在VOC2007上NMI變化情況

由于在VOC2007數據集上使用RMKMC聚類方法沒有得到聚類結果，因此圖2中僅展示了其他三種多視圖聚類方法上的NMI值。可以看到：該數據集下NMI值對SDPC的采樣比例是敏感的。初始的采樣量較少時，聚類效果比較差?？赏茰y是因為該數據集上視圖間是異質的。當采樣比例達到50%及以上時，三種方法的NMI值有了明顯的提升。

6 總結

本文在K-means型多視圖聚類算法中應用了單視圖下現有的不同初始化方法，并提出了一種基于采樣的主動式初始中心選擇方法(SDPC)，研究不同初始化方法對多視圖聚類效果的影響。實驗結果顯示：全局（核）K-means雖類劃分具有確定性，但是效率較低。AFKMC2通過加速K-means++采樣方法，在大規模數據中效率有明顯的提升。DPC從密度角度考慮，可以自適應地選擇類中心和類個數，但是計算復雜性還可進一步改善。所提出的SDPC方法不僅避免了多視圖初始化時的單視圖選擇問題，還在一定程度上克服了DPC時間花費高和內存開銷大的缺點。同時，SDPC方法中的K-means再迭代策略進一步優化了初始中心選擇策略?？傮w來說，不同的初始化方法在K-means型多視圖聚類算法中表現出不同的性能，SDPC較DPC在精度和效率上取得了較好的折衷。