賀 娜 馬盈倉 張 丹 續(xù)秋霞

（西安工程大學(xué)理學(xué)院 西安 710600）

1 引言

聚類分析是把一個(gè)數(shù)據(jù)樣本集劃分為多個(gè)簇的過程，應(yīng)用到許多領(lǐng)域，包括圖像模式識(shí)別、商務(wù)智能和生物學(xué)等。通常來說，對(duì)于每個(gè)樣本，可以對(duì)其從不同的視圖進(jìn)行描述，并且綜合多個(gè)視圖的信息有利于得到更好的聚類結(jié)果。處理這一問題的方法一般分為基于圖的方法［1～3］、矩陣分解方法［4～6］、基于多重核的方法［7～9］和基于子空間學(xué)習(xí)的方法［10～11］。特別是基于圖的方法，因其具有挖掘非線性結(jié)構(gòu)信息的能力，在聚類精度方面通常優(yōu)于其他方法。

經(jīng)典的譜聚類算法是一種重要的基于圖論的聚類算法［12］，不僅可以在任意樣本空間進(jìn)行聚類，而且可以收斂到全局最優(yōu)［13］。但是，該算法也存在一些問題，因譜聚類的最終結(jié)果完全依賴于開始構(gòu)造的相似矩陣，然而不同的構(gòu)造方法會(huì)影響聚類結(jié)果，因此構(gòu)造理想的相似矩陣成為了一個(gè)問題［14］。

近年來，許多學(xué)者對(duì)譜聚類算法中相似矩陣的構(gòu)造方法做了進(jìn)一步研究與改進(jìn)。Shi等通過高斯核函數(shù)構(gòu)造相似矩陣［15］；Ng等提出NJW（Ng-Jor?dan-Weiss）算法通過高斯核函數(shù)構(gòu)造相似矩陣，采用全連接構(gòu)造方法［16］；Zhang等利用兩個(gè)樣本數(shù)據(jù)點(diǎn)之間的局部密度求得相似矩陣［17］；Nie等通過基于局部連通性為每個(gè)數(shù)據(jù)點(diǎn)分配自適應(yīng)和最優(yōu)鄰居來學(xué)習(xí)相似矩陣［18］；Xie等采用樣本點(diǎn)與樣本點(diǎn)的近鄰點(diǎn)兩者的歐式距離作為局部標(biāo)準(zhǔn)差構(gòu)造相似矩陣［19］；Nataliani等利用數(shù)據(jù)點(diǎn)的相關(guān)性估計(jì)冪參數(shù)構(gòu)造冪高斯核函數(shù)來求解相似矩陣［20］。然而這些文獻(xiàn)中構(gòu)造的相似矩陣都是固定的，不能很好地挖掘和利用數(shù)據(jù)結(jié)構(gòu)。

為了更好地挖掘和利用數(shù)據(jù)，近年來發(fā)展起來的多視圖學(xué)習(xí)，在學(xué)習(xí)過程中充分利用多視圖數(shù)據(jù)之間的互補(bǔ)信息和關(guān)聯(lián)信息，使最終的學(xué)習(xí)結(jié)果在各視圖上趨于一致的機(jī)器學(xué)習(xí)算法。本文將多視圖學(xué)習(xí)引入譜聚類過程，提出了基于譜聚類和L2，1范數(shù)的多視圖聚類算法（Multi-view clustering algo?rithm based on spectral clustering andL2，1norm）。將改進(jìn)的多視圖親和矩陣?yán)肔2，1范數(shù)正則項(xiàng)合理地構(gòu)造出相似矩陣S，同時(shí)進(jìn)行譜聚類過程，F(xiàn)與S交替迭代更新，最后對(duì)F進(jìn)行聚類。該算法不僅可以更好地反映數(shù)據(jù)的流行結(jié)構(gòu)，而且可以得到更加穩(wěn)定的聚類結(jié)果。

2 相關(guān)工作

2.1 多視圖相似矩陣的構(gòu)造

為了充分利用多視圖數(shù)據(jù)之間的互補(bǔ)信息和關(guān)聯(lián)信息，本文將不同視角下的親和矩陣通過相加的方式，融合為一個(gè)全局親和矩陣A?，即（v為視圖的個(gè)數(shù)），由于學(xué)習(xí)的相似矩陣S與全局親和矩陣A?存在距離，為了得到更好的結(jié)果，進(jìn)一步對(duì)相似矩陣進(jìn)行稀疏化處理，通過L2，1范數(shù)的魯棒性學(xué)習(xí)得到一個(gè)最理想的相似矩陣S，表示如下：

其中：我們限制相似矩陣S的每一行和等于1，使其具有仿射性，有利于后期的計(jì)算處理。

由于使用L2范數(shù)的平方作為損失函數(shù)對(duì)較大的異常值比較敏感，對(duì)較小的異常值不敏感；使用L1范數(shù)作為損失函數(shù)對(duì)較大的異常值不敏感，對(duì)較小的異常值比較敏感。然而L2，1范數(shù)［21］不僅綜合了L2范數(shù)和L1范數(shù)的魯棒性優(yōu)點(diǎn)，還減少了異常值的影響，并保持了適當(dāng)?shù)南∈栊浴?/p>

2.2 譜聚類中引入多視圖學(xué)習(xí)的合理性

在2.1小節(jié)中，我們介紹了多視圖相似矩陣的構(gòu)造保留了各個(gè)視圖攜帶的信息，在學(xué)習(xí)過程中充分利用多視圖數(shù)據(jù)之間的互補(bǔ)信息和關(guān)聯(lián)信息，使最終的學(xué)習(xí)結(jié)果在各視圖上趨于一致，構(gòu)造了一個(gè)合理的相似矩陣，本節(jié)為了說明在譜聚類中引入多視圖學(xué)習(xí)的重要性，設(shè)計(jì)了如下實(shí)驗(yàn)。

我們將經(jīng)典的單視圖譜聚類算法（即將譜聚類算法在每個(gè)視圖上分別執(zhí)行）與2.1小節(jié)中構(gòu)造的多視圖相似矩陣的算法在數(shù)據(jù)集ALOI（具體介紹見4.1小節(jié)）上構(gòu)造相似矩陣，參數(shù)k均為10，并通過影像圖展示，如圖1所示。所測(cè)試的多視圖數(shù)據(jù)集ALOI有4個(gè)視圖，即X={X(1)，X(2)，X(3)，X(4)}∈Rn×dv，分 別 為X(1)∈R64×1079，X(2)∈R64×1079，X(3)∈R77×1079，X(4)∈R13×1079。

圖1 ALOI數(shù)據(jù)集上生成的相似矩陣影像圖

在圖1（a）～（d）為在每個(gè)視圖上分別執(zhí)行譜聚類算法得出的相似矩陣影像圖，圖（a）為視圖1相似矩陣影像圖，（b）為視圖2相似矩陣影像圖，（c）為視圖3相似矩陣影像圖，（d）為視圖4相似矩陣影像圖，（e）為2.1小節(jié)構(gòu)造的多視圖相似矩陣生成算法得出的相似矩陣影像圖。我們可以看到，經(jīng)典的單視圖譜聚類算法在視圖1和視圖2的時(shí)候，還可以構(gòu)造出較為合理的相似矩陣，但是在視圖3和視圖4時(shí)，結(jié)果很不理想，特別是對(duì)視圖4構(gòu)造相似矩陣時(shí)，表現(xiàn)出很不好的結(jié)果。而相比經(jīng)典的單視圖譜聚類算法，圖（e）可以很明顯地看到，多視圖學(xué)習(xí)方法可以構(gòu)造出比圖（a）～（d）更合理的相似矩陣，比單視圖譜聚類算法更加穩(wěn)定。

由此可以得出，在譜聚類算法中引入多視圖學(xué)習(xí)方法，可以構(gòu)造出更合理的相似矩陣，證明了多視圖學(xué)習(xí)的優(yōu)越性和有效性，有利于提高聚類精度。

3 模型的建立及求解

3.1 模型建立

在2.1小節(jié)中，構(gòu)造了理想的相似矩陣，接著，在譜聚類的過程中引入多視圖學(xué)習(xí)，同時(shí)進(jìn)行相似矩陣的學(xué)習(xí)和譜聚類過程，建立目標(biāo)函數(shù)為

3.2 模型求解

對(duì)于上述目標(biāo)函數(shù)式（2），我們通過迭代交替優(yōu)化方法來求解。

1）固定S，問題（2）可以轉(zhuǎn)化為

最優(yōu)解F由Ls前c個(gè)最小的特征值所對(duì)應(yīng)的c個(gè)特征向量構(gòu)成。

2）固定F，對(duì)于式（2），根據(jù)文獻(xiàn)［22］，已知存在fi∈Rc×1，則下式成立：

由于式（2）對(duì)于不同i是獨(dú)立的，因此我們可以分別對(duì)每個(gè)i求解如下問題：

其中：D為對(duì)角矩陣，主對(duì)角元素dii=1/

根據(jù)拉格朗日乘子法，得

對(duì)si求偏導(dǎo)，令其等于0，可得

對(duì)si的第j個(gè)元素，有

根據(jù)KKT條件，得

其中(v)+=max(0，v)，定義η下述函數(shù)為

注意上式，gi(η)是一個(gè)分段單調(diào)遞增函數(shù)，可以很容易地用牛頓迭代法求解。

3.3 算法流程

MVSC-L2，1算法流程如下所示。

3.4 收斂性證明

引理1［21］對(duì)于任意非零向量x，y∈Rc，有以下不等式成立

聯(lián)合本文的目標(biāo)函數(shù)，給出如下定理：

定理1目標(biāo)函數(shù)

在固定F時(shí)，交替迭代優(yōu)化S的過程中，目標(biāo)函數(shù)值逐步減小。

證明：令更新后的si為sdow i，上一次的si為，通過式（5）只是式（6）的一個(gè)解，而是式（2）的最小解，所以根據(jù)式（2）有

因?yàn)?/p>

所以

由引理1知道：

將式（17）和式（18）相加得

由L2，1范數(shù)［21］的定義可得：

因此該算法收斂。

4 實(shí)驗(yàn)

在這一節(jié)，將根據(jù)三個(gè)評(píng)價(jià)指標(biāo)［23］來評(píng)估我們的結(jié)果：聚類精度（ACC），純度（purity），標(biāo)準(zhǔn)化互信息（NMI），對(duì)MVSC-L2，1進(jìn)行評(píng)價(jià)。

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

3-Sources［24］該數(shù)據(jù)集包含294篇新聞文章，涵蓋六個(gè)標(biāo)簽：商業(yè)、娛樂、健康、政治、體育和技術(shù)。第一視圖有3068個(gè)特征，第二視圖有3631個(gè)特征，第三視圖有3560個(gè)特征（http：//mlg.ucd.ie/datasets/3sources.html）。

Caltech-101（7）圖像數(shù)據(jù)集有101個(gè)類別的圖像［25］。我們選取了廣泛使用的7個(gè)類，得到了1474張［26］圖像。這七種類別分別是面孔、摩托車、美鈔、加菲貓、停車標(biāo)志和溫莎椅。每幅圖像由六個(gè)特征描述。

Extended Yale-B是由三種視圖描述的人臉圖像數(shù)據(jù)集。綜上所述，這個(gè)數(shù)據(jù)集中有38個(gè)不同的人臉圖像被試。我們選擇前10個(gè)被試進(jìn)行多視圖聚類，每個(gè)被試65張圖像（http：//cvc.yale.edu/projects/yalefaces/yalefaces.html）。

ALOI包含1000個(gè)對(duì)象的110，250張圖像，每個(gè)對(duì)象大約有100張圖像。該算法提取了10個(gè)對(duì)象的1079張圖像，包括RGB顏色直方圖，HSV顏色直方圖，顏色相似度，Haralick特征的4個(gè)視圖。表1給出了上述四個(gè)數(shù)據(jù)集的簡要說明。

表1 數(shù)據(jù)的屬性

4.2 評(píng)價(jià)指標(biāo)

使用三個(gè)評(píng)價(jià)指標(biāo)［23］來評(píng)估我們的結(jié)果：聚類精度（ACC），純度（Purity），標(biāo)準(zhǔn)化互信息（NMI），對(duì)于這些廣泛使用的指標(biāo)，值越大表示集群性能越好。這些指標(biāo)是通過比較每個(gè)樣本獲得的標(biāo)簽與數(shù)據(jù)集中提供的真實(shí)標(biāo)簽來計(jì)算的。

4.2.1聚類準(zhǔn)確率

ACC是反映聚類的精度，定義為

其中n為數(shù)據(jù)點(diǎn)的個(gè)數(shù)，τi為第i個(gè)樣本點(diǎn)真實(shí)的類標(biāo)簽，ri為學(xué)習(xí)到的第i個(gè)樣本點(diǎn)對(duì)應(yīng)的類標(biāo)簽。δ(x)，y定義為一個(gè)函數(shù)，即當(dāng)x=y時(shí)δ(x，y)=1，否則為0；map(ri)是一個(gè)映射函數(shù)，它將學(xué)習(xí)到的標(biāo)簽ri與真實(shí)標(biāo)簽τi進(jìn)行匹配。ACC的取值范圍為[0，1]，值越靠近1，越好。

4.2.2 純度

Purity是正確類標(biāo)簽的百分比，定義為

Purity的取值范圍為[0，1]，值越靠近1，越好。

4.2.3 標(biāo)準(zhǔn)互信息

標(biāo)準(zhǔn)化互信息NMI用于表示τi和ri之間的相似程度，定義為

上式中的：ni表示算法中每一類ri(1 ≤i≤c)包含的樣本點(diǎn)的個(gè)數(shù)以及n?j表示算法中每一類τj(1 ≤j≤c)包含的樣本點(diǎn)的個(gè)數(shù)；ni，j表示學(xué)習(xí)到的第i個(gè)樣本點(diǎn)對(duì)應(yīng)的類標(biāo)簽ri和真實(shí)的類標(biāo)簽τj的交集中所包含的樣本點(diǎn)的個(gè)數(shù)。NMI的取值范圍為[]

0，1，值越靠近1，越好。

4.3 實(shí)驗(yàn)設(shè)置

4.3.1 對(duì)比算法

將本文提出的算法與其它三種聚類算法進(jìn)行了比較：分別為SWMC［27］，AMGL［28］，MVGL［29］。比較算法中涉及參數(shù)的調(diào)整均根據(jù)相應(yīng)文獻(xiàn)作者的建議進(jìn)行設(shè)置并試驗(yàn)以顯示最優(yōu)結(jié)果，對(duì)于所有要求圖的相似度矩陣作為輸入的算法，我們使用文獻(xiàn)［18］中提出的方法來構(gòu)造每個(gè)視圖的相似度矩陣，將k固定為10來驗(yàn)證它們的性能，原因使它可以避免不同視圖之間的尺度差異，并為每個(gè)視圖生成歸一化相似矩陣。

4.3.2 參數(shù)設(shè)置

本文算法中的參數(shù)λ的取值為{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1}。k取 值 為0～15。我們?cè)趫D2中描述了不同參數(shù)的變化，其中橫坐標(biāo)表示k的取值，縱坐標(biāo)表示λ的取值，豎坐標(biāo)表示聚類準(zhǔn)確率ACC，具體的設(shè)置在四個(gè)數(shù)據(jù)集（a）3-sources、（b）Extended Yale-B、（c）Caltech-101（7）、（d）ALOI上的k和λ的取值分別為（8，0.9），（8，0.2），（10，0.7），（14，0.6）。

圖2 MVSC-L2，1中參數(shù)在數(shù)據(jù)集（a）3-sources、（b）Extended Yale-B、（c）Caltech-101（7）、（d）ALOI上的變化

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

從表2、表3和表4顯示的結(jié)果中可以得到，在ACC，Purity和NMI三個(gè)評(píng)價(jià)指標(biāo)下，首先在數(shù)據(jù)集3-sources上，我們所提的算法，相比次優(yōu)的分別提高23.84%、20%、19.6%；在數(shù)據(jù)集Extended Yale-B上，我們所提的算法，相比次優(yōu)的分別提高6.77%、7.08%、6.56%；在數(shù)據(jù)集Caltech-101（7）上，我們所提的算法，相比次優(yōu)的分別提高0.13%、0.07%、7.43%；在數(shù)據(jù)集ALOI上，我們所提的算法，相比次優(yōu)的分別提高8.89%、0.88%、0.52%。綜上，我們的算法MVSC-L2，1的聚類性能明顯高于對(duì)比算法，具有良好的聚類效果。

表2 不同算法在各數(shù)據(jù)集下的ACC比較

表3 不同算法在各數(shù)據(jù)集下的Purity比較

表4 不同算法在各數(shù)據(jù)集下的NMI比較

5 結(jié)語

本文提出了一種新的多視圖聚類算法MVSC-L2，1，該算法在構(gòu)造相似矩陣時(shí)，采用將各個(gè)視圖的信息相加融合的方式，比單視圖算法更優(yōu)，然后同時(shí)進(jìn)行相似矩陣和譜聚類過程，更新迭代優(yōu)化S和F，最后對(duì)F進(jìn)行聚類。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法可以產(chǎn)生較好的聚類結(jié)果。但是由于參數(shù)λ是人為選取的，使得該算法有一定的局限性。如何自動(dòng)確定參數(shù)，是下一步的研究方向。