洪 敏，賈彩燕+，王曉陽(yáng)

1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044

2.交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044

1 引言

由于不同測(cè)量方法的使用，多視圖數(shù)據(jù)廣泛存在于各種應(yīng)用中[1-7]。例如由文本、圖片、視頻和超鏈接組成的網(wǎng)頁(yè)，以及圖像數(shù)據(jù)中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]等不同的局部特征描述。也就是說，這些數(shù)據(jù)集上同一實(shí)例有多種不同的表示形式，這些表現(xiàn)形式常被稱為視圖。既然不同的視圖從不同角度對(duì)數(shù)據(jù)進(jìn)行了描述，并且具有不同的判別力，那么如何有效結(jié)合來源于多個(gè)視圖的數(shù)據(jù)，并找到滿足所有視圖的最優(yōu)劃分是當(dāng)前研究領(lǐng)域的一個(gè)熱點(diǎn)。

K-means算法不僅可以用在傳統(tǒng)的單視圖學(xué)習(xí)中，還可以拓展到多視圖場(chǎng)景下。本質(zhì)上講，K-means型多視圖聚類算法不僅存在K-means算法初值敏感和類個(gè)數(shù)事先指定的問題，還由于綜合考慮來自多個(gè)視圖的數(shù)據(jù)而造成了數(shù)據(jù)規(guī)模不一的現(xiàn)象。目前，多視圖聚類中常用的初始化方法是隨機(jī)初始化和全局核K-means[14]初始化方法。前者因隨機(jī)性使得聚類效果不穩(wěn)定，后者結(jié)果雖具有確定性，但是在大規(guī)模數(shù)據(jù)中比較耗時(shí)。另外，這兩種初始化方法都需要事先指定類數(shù)目。那么如何有效解決K-means型多視圖聚類的初始化問題呢？本文基于單視圖下的K-means初值敏感和類個(gè)數(shù)選擇問題，研究了現(xiàn)存的多種經(jīng)典初始化方法，如隨機(jī)初始化、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]，并將這些方法應(yīng)用于K-means型多視圖聚類算法的初始化中，研究不同的初始化方法對(duì)K-means型多視圖聚類效果的影響。另外，還提出了一種基于采樣的主動(dòng)式初始中心選擇方法（sampledclustering by fast search and find of density peaks，SDPC），進(jìn)一步優(yōu)化K-means型多視圖聚類的初始中心和類個(gè)數(shù)的選擇策略。多個(gè)多視圖基準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明：不同的初始化方法可以改善K-means型多視圖聚類的效果。與DPC相比，SDPC在聚類精度和效率上取得了較好的折衷。

2 相關(guān)工作

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

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

面對(duì)多視圖聚類問題，研究者們也提出了多種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綜合考慮數(shù)據(jù)視圖和視圖特征的貢獻(xiàn)，進(jìn)一步優(yōu)化多視圖聚類效果，RMKMC在目標(biāo)函數(shù)?2,1范式下考慮視圖的重要性。值得關(guān)注的是，這些K-means型多視圖聚類算法不可避免地存在K-means聚類中初始中心敏感和類個(gè)數(shù)事先指定的問題。因此，本文將單視圖的各種初始化方法用于K-means型多視圖聚類中，進(jìn)一步研究對(duì)多視圖聚類的效果。

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

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

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

（1）WMKC算法

當(dāng)處理多視圖數(shù)據(jù)時(shí)，直接的方法是將所有視圖特征拼接起來執(zhí)行K-means聚類算法。在所有視圖中，每個(gè)數(shù)據(jù)都會(huì)被指派到同一個(gè)簇。但是這種方法平等看待每個(gè)視圖，從而聚類結(jié)果也沒有得到優(yōu)化。因此通過對(duì)多視圖數(shù)據(jù)的每一個(gè)視圖增加權(quán)重參數(shù)，進(jìn)而體現(xiàn)出不同視圖的重要程度，將該方法簡(jiǎn)記為WMKC。相應(yīng)的目標(biāo)函數(shù)如式（1）所示：

ωv表示第v個(gè)視圖的權(quán)重，滿足。p1是根據(jù)先驗(yàn)知識(shí)選擇的參數(shù)，用于控制視圖權(quán)重ωv的分配。是在視圖v中簇k的中心。由于不同視圖下數(shù)據(jù)表示形式不一，從而同一個(gè)簇的簇中心也是不同的。

（2）MVKKM算法

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

（3）WMCFS算法

Xu和Wang等人[31]提出具有特征選擇的加權(quán)多視圖聚類算法（WMCFS）。該算法通過對(duì)視圖和視圖中的特征施加兩種不同的加權(quán)模式，從而在聚類時(shí)選出最優(yōu)視圖和每個(gè)視圖中最具代表性的特征。目標(biāo)函數(shù)如式（3）所示：

τv表示長(zhǎng)度為dv的特征權(quán)重向量，表示在視圖v中第t個(gè)特征的權(quán)重。是用于控制特征權(quán)重向量τv的稀疏性。

（4）RMKMC算法

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

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

上式中含有共同的簇指示矩陣G，且目標(biāo)函數(shù)上施加了結(jié)構(gòu)性稀疏約束?2,1-范式，從而對(duì)含有異常值的輸入數(shù)據(jù)具有魯棒性。

3.2 類初始化方法

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

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

（1）隨機(jī)初始化

隨機(jī)初始化是聚類中最常用、最直接的類指派方法，即隨機(jī)將每一個(gè)數(shù)據(jù)點(diǎn)指派到K個(gè)類之一。但是結(jié)果受隨機(jī)影響大。

（2）K-means++初始化

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

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

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

（4）全局核K-means算法

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

算法1全局核K-means算法

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

輸出：類劃分（K個(gè)類中心）。

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

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

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

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

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

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

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

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

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

4 基于采樣的主動(dòng)式初始中心選擇方法

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

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

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

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

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

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

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

步驟3以K和InitCen在X'上運(yùn)行K-means算法。

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

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

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

5 實(shí)驗(yàn)與結(jié)果

本章將基于采樣的主動(dòng)式初始中心選擇方法（SDPC）和現(xiàn)有的其他五種初始化方法應(yīng)用到K-means型多視圖聚類算法中，并在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果采用標(biāo)準(zhǔn)化互信息[38]和純度[39]兩個(gè)標(biāo)準(zhǔn)聚類評(píng)估指標(biāo)。另外，計(jì)算了初始化所需時(shí)間衡量不同初始化方法在K-means型多視圖聚類中的效率。

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

本次實(shí)驗(yàn)采用的數(shù)據(jù)集是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個(gè)數(shù)據(jù)集的多個(gè)視圖之間是同質(zhì)的，都利用不同特征描述同一圖像，最后一個(gè)是由文本和圖像構(gòu)成的異質(zhì)視圖數(shù)據(jù)集，數(shù)據(jù)集總體情況如表1所示。

Table 1 Datasets summary表1 數(shù)據(jù)集情況

HW（handwritten numerals）：由2 000個(gè)0～9數(shù)字類組成的手寫體數(shù)據(jù)。該數(shù)據(jù)共有6個(gè)特征：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)。實(shí)驗(yàn)中僅使用前5個(gè)具有代表性的視圖。

Caltech101-7：是一個(gè)由101類組成的對(duì)象識(shí)別數(shù)據(jù)集。實(shí)驗(yàn)中僅選取廣泛使用的7個(gè)類，即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形成多個(gè)視圖。

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

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

Pascal Visual Object Classes 2007(VOC 2007)：該數(shù)據(jù)集是有關(guān)自然圖像的數(shù)據(jù)。采用其中的20個(gè)類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張圖片用于實(shí)驗(yàn)。由圖片的512維GIST特征和圖片標(biāo)注的 TF-IDF（term frequency-inverse document frequency）值組成兩個(gè)不同的視圖。

5.2 聚類評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)各種初始化方法在不同多視圖算法上的聚類效果，文中使用標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）[38]和純度（Purity）[39]。

（1）標(biāo)準(zhǔn)化互信息（NMI）

該衡量預(yù)測(cè)類標(biāo)與真實(shí)類標(biāo)的相近程度。計(jì)算公式如下：

式中，C是真實(shí)的類標(biāo)，C'是計(jì)算得到的類標(biāo)，K是真實(shí)類數(shù)目，K'是算法中的類個(gè)數(shù)，表示真實(shí)類i中節(jié)點(diǎn)的數(shù)量，表示計(jì)算出的類j中節(jié)點(diǎn)的數(shù)量，nij表示將類i的節(jié)點(diǎn)分配到計(jì)算后j中節(jié)點(diǎn)的數(shù)量。

（2）純度（Purity）

純度是另一個(gè)評(píng)價(jià)聚類質(zhì)量的指標(biāo)。純度越高，聚類效果越好。計(jì)算公式如下：

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

5.3 結(jié)果比較

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

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

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

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

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

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

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

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

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

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

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

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數(shù)據(jù)集上使用RMKMC聚類方法沒有得到聚類結(jié)果，因此圖2中僅展示了其他三種多視圖聚類方法上的NMI值。可以看到：該數(shù)據(jù)集下NMI值對(duì)SDPC的采樣比例是敏感的。初始的采樣量較少時(shí)，聚類效果比較差?？赏茰y(cè)是因?yàn)樵摂?shù)據(jù)集上視圖間是異質(zhì)的。當(dāng)采樣比例達(dá)到50%及以上時(shí)，三種方法的NMI值有了明顯的提升。

6 總結(jié)

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