基于統(tǒng)一標(biāo)簽矩陣的快速多視圖聚類

劉怡俊 王嘉達(dá) 鐘仕杰 楊曉君? 葉武劍

（1.廣東工業(yè)大學(xué) 集成電路學(xué)院，廣東 廣州 510006；2.廣東工業(yè)大學(xué) 先進(jìn)制造學(xué)院，廣東 揭陽(yáng) 515200；3.廣東工業(yè)大學(xué) 信息工程學(xué)院，廣東 廣州 510006）

數(shù)據(jù)集可以通過多個(gè)視圖、不同的來源和異構(gòu)屬性進(jìn)行編碼［1-2］?；谶@類數(shù)據(jù)集產(chǎn)生了一種聚類方法，稱為多視圖聚類［3-4］。這種方法可以學(xué)習(xí)來自不同觀點(diǎn)的互補(bǔ)信息，并輸出一致的結(jié)果。例如，在自然語(yǔ)言處理中，文檔通?？梢杂枚喾N語(yǔ)言表示。每種語(yǔ)言都表示一個(gè)視圖，Kumar 等［5］提出的共正則化譜聚類（CoregSC）在這個(gè)領(lǐng)域中已經(jīng)成為常用的數(shù)據(jù)處理方法。

眾多學(xué)者對(duì)多視圖學(xué)習(xí)進(jìn)行了充分的研究分析與討論［6-7］。目前，多視圖聚類方法包括協(xié)作訓(xùn)練方法［8-9］、多核學(xué)習(xí)方法［10］和基于圖的方法［11-12］等類型。由于基于圖的聚類方法通過考慮不同視圖之間的多樣性信息和互補(bǔ)信息，可以有效地挖掘出數(shù)據(jù)的潛在信息，所以性能更為出色［13］。本文主要研究基于圖的多視圖聚類。

近年來，有眾多學(xué)者提出在單視圖聚類的基礎(chǔ)上拓展多視圖聚類的方法。Zhou 等［14］通過將歸一化切割從單視圖擴(kuò)展到多視圖，提出了一種多視圖聚類方法；Cai 等［15］為每個(gè)特征描述建立了一個(gè)模型，然后將這些模型統(tǒng)一起來學(xué)習(xí)一個(gè)拉普拉斯矩陣；Liu 等［16］通過聯(lián)合非負(fù)矩陣分解的方法（Multi-NMF）提出了多視圖聚類，采用了一種共正則化策略來融合視圖間的信息；為了處理大規(guī)模數(shù)據(jù)集，Li等［17］使用二部圖構(gòu)造相似性矩陣，發(fā)現(xiàn)了對(duì)每個(gè)視圖獨(dú)立使用流形融合或k-means 的不可行性；Zhan 等［18］提出了一種新的目標(biāo)函數(shù)，通過最小化不同視圖之間的差異來學(xué)習(xí)統(tǒng)一圖，并在拉普拉斯矩陣中添加了秩約束，提出多視圖一致圖的聚類（MCGL）；為了直接獲得聚類結(jié)果，Cai等［19］提出了一種新的魯棒多視圖k-means 聚類方法（MkC），該方法可以通過分解每個(gè)視圖數(shù)據(jù)特征直接獲得聚類結(jié)果；Xia 等［20］提出的基于低秩和稀疏分解的魯棒多視圖譜聚類（MSC），首先為每個(gè)視圖構(gòu)造了一個(gè)概率轉(zhuǎn)移矩陣，然后恢復(fù)低秩概率轉(zhuǎn)移矩陣，最后將公共矩陣輸入到馬爾可夫鏈方法中，得到聚類結(jié)果；Zhu 等［21］提出了一種一步多視圖譜聚類，該方法從低維數(shù)據(jù)中學(xué)習(xí)親和矩陣。

上述方法可以根據(jù)是否生成一致圖分為兩類。對(duì)于需要生成一致圖的方法，其無法避免對(duì)一致圖矩陣采用其他聚類方法進(jìn)行處理，容易導(dǎo)致聚類結(jié)果產(chǎn)生次優(yōu)解；對(duì)于不需要生成一致圖的方法，通常具有更為出色的性能，但由于需要進(jìn)行特征分解，所以時(shí)間復(fù)雜度很高且需要后處理。

針對(duì)產(chǎn)生次優(yōu)解、高時(shí)間復(fù)雜度以及需要后處理等缺陷，本研究基于圖重建、聚類結(jié)果的可解釋性和時(shí)間成本，提出了一種新穎的多視圖聚類模型。該模型不需要構(gòu)建統(tǒng)一圖，同時(shí)也避免了特征分解以降低時(shí)間復(fù)雜度并避免后處理，從而提升運(yùn)行速度。該方法首先從傳統(tǒng)的譜聚類（SC）中歸一化切割（SNcut）和比例切割（SRcut）的統(tǒng)一觀點(diǎn)出發(fā)，將非負(fù)約束和正交約束作為結(jié)構(gòu)化約束構(gòu)建模型；其次，隨機(jī)選取錨點(diǎn)的地址，將每個(gè)視圖中對(duì)應(yīng)地址的數(shù)據(jù)定義為錨點(diǎn)，并嵌入到相似矩陣中，可以免去前處理（例如k-means）的迭代計(jì)算；同時(shí)，將多個(gè)視圖的數(shù)據(jù)對(duì)齊；最后，通過非負(fù)的統(tǒng)一標(biāo)簽矩陣快速迭代更新。

1 相關(guān)工作

1.1 單視圖譜聚類

譜聚類是一種近似于SRcut（或SNcut）的聚類方法［22］。而對(duì)子圖的最小化切割極有可能是簡(jiǎn)單的將某個(gè)頂點(diǎn)從其他頂點(diǎn)的集合中切割下來。為了保證切割后每個(gè)子圖的大小平衡，需要借助SRcut 和SNcut。其目標(biāo)函數(shù)如下：

其中，非空子集需要滿足Ai∩Aj=?(i，j=1，2，…，c)和Ai∪，…，∪Ac={v1，v2，…，vn}。但是，為使子圖大小均勻，以上兩個(gè)需要解決的問題均為NP 難，因此，需要松弛上述兩個(gè)問題。設(shè)指示矩陣為F∈Rn×c，則第j列向量用fj來表示。在SNcut 中，第i行的fj表示為

由式（3）可得，=cut(Aj)/vol(Aj)和FTDF=Ic，其中Ic為c階單位矩陣。由此可將式（2）的SNcut問題轉(zhuǎn)化為跡的形式：

其中，F(xiàn)需要滿足式（3）。該問題對(duì)SNcut進(jìn)行松弛后，則可以忽略離散化的要求，同時(shí)保留正交約束。若設(shè)H=D1/2F，代入到式（4）則可以將問題轉(zhuǎn)化為

式（5）即為松弛的歸一化譜聚類的目標(biāo)函數(shù)。類似地，將式（3）中定義指示矩陣時(shí)的vo（lAi）j改為 |Aj|，可得松弛的SRcut的目標(biāo)函數(shù)：

可以對(duì)L或進(jìn)行特征分解，再?gòu)那癱個(gè)最小特征值對(duì)應(yīng)的特征向量來獲得F或H的最優(yōu)解，并對(duì)其行向量進(jìn)行k-means來獲得聚類標(biāo)簽。

1.2 多視圖譜聚類

在現(xiàn)實(shí)世界中，由于單視圖數(shù)據(jù)無法對(duì)事物完整地進(jìn)行描述，因此，數(shù)據(jù)通常用多個(gè)異構(gòu)源來描述，從而形成多視圖數(shù)據(jù)［23］。由1.1節(jié)可以寫出對(duì)應(yīng)的多視圖譜聚類目標(biāo)函數(shù)：

式中，L（v）為第v個(gè)視圖的圖拉普拉斯矩陣。顯然，這個(gè)目標(biāo)函數(shù)存在問題，無法滿足多視圖聚類的需要。主要問題有3個(gè)：其一，式（7）沒有考慮不同視圖之間的關(guān)系，在多次迭代后，指示矩陣F無法得到一致性嵌入，從而無法準(zhǔn)確地形成多視圖指示矩陣；其二，依然沒有擺脫后處理的限制，由于k-means算法對(duì)初始化敏感，不同的初始點(diǎn)將導(dǎo)致聚類結(jié)果不同，因此，后處理使得聚類結(jié)果不魯棒；其三，該方法需要特征分解，這將導(dǎo)致計(jì)算復(fù)雜度和時(shí)間成本的大幅提升。有眾多研究者對(duì)這一公式通過添加非歸一化系數(shù)、增加正則項(xiàng)等手段進(jìn)行優(yōu)化，如文獻(xiàn)［4］和［24］。本研究將通過增加平衡項(xiàng)和平衡系數(shù)來實(shí)現(xiàn)聚類算法的快速收斂并擺脫后處理的限制。

1.3 隨機(jī)選取錨點(diǎn)地址

在單視圖聚類中，選取的錨點(diǎn)通常是作為聚類中心，以提升聚類的速度和性能。但是，在多視圖聚類中，需要無監(jiān)督地學(xué)習(xí)不同視圖之間的聯(lián)系和差異。

目前，主流的錨點(diǎn)選擇方式有k-means 和隨機(jī)選取等［17］。其中，k-means 選取的錨點(diǎn)無法保證每個(gè)視圖能夠?qū)R，因此，本研究采用隨機(jī)選取錨點(diǎn)地址的方法。如圖1所示，以3行6列的矩陣為例，在一個(gè)矩陣中的5 個(gè)虛線矩形表示錨點(diǎn)所在位置。隨機(jī)選取錨點(diǎn)地址的方法通常是隨機(jī)選取同一個(gè)視圖中的m個(gè)錨點(diǎn)地址，然后將其應(yīng)用到每一個(gè)視圖中。該方法選取的錨點(diǎn)不需要表示原始數(shù)據(jù)的特征，其主要目的是對(duì)齊各個(gè)視圖。

圖1 錨點(diǎn)嵌入示意圖Fig.1 Schematic diagram of anchor embedding

該方法主要有3個(gè)優(yōu)勢(shì)：其一，由于其隨機(jī)性可以避免偏見選擇，所以可提升準(zhǔn)確性；其二，計(jì)算復(fù)雜度較低，可以保證在提升準(zhǔn)確性的同時(shí)將時(shí)間成本降低；其三，具有廣泛的適用性，能夠適用于不同的數(shù)據(jù)類型，例如數(shù)值型數(shù)據(jù)、類別型數(shù)據(jù)和文本數(shù)據(jù)等。

2 基于統(tǒng)一標(biāo)簽矩陣的快速多視圖聚類

本研究提出了一種無監(jiān)督學(xué)習(xí)方法，即基于統(tǒng)一標(biāo)簽矩陣的快速多視圖聚類（FMCULM），如圖2所示。通過將多視圖數(shù)據(jù)矩陣轉(zhuǎn)化為嵌入錨點(diǎn)的相似圖后，對(duì)標(biāo)簽矩陣進(jìn)行迭代更新，從而使模型在最少的迭代次數(shù)后達(dá)到收斂；最后通過標(biāo)簽矩陣直接得出聚類結(jié)果。

圖2 FMCULM方法框架Fig.2 Framework of FMCULM

2.1 算法思想

在譜聚類中，特征分解得到的拉普拉斯矩陣的特征向量就是指示向量。這一方法使得聚類失去了可解釋性，故而十分依賴于后處理，可以把后處理理解為是對(duì)連續(xù)值重新離散化的過程［18］。如果想擺脫后處理，就需要在切圖時(shí)避免過分的松弛［25］。因此，需要對(duì)式（7）增加非負(fù)約束，從而得到

本文從4個(gè)方面解釋式（8）提出的模型。其一，該模型與譜聚類相比更接近SRcut（SNcut），因?yàn)樵谑剑?）的模型和SRcut（SNcut）中的指標(biāo)矩陣均有非負(fù)元素，而譜聚類將其松弛為實(shí)數(shù)。其二，在同一個(gè)簇中的兩個(gè)樣本可能具有不同的相似性，而SRcut（SNcut）在同一個(gè)簇內(nèi)應(yīng)該具有相同的相似性。其三，非負(fù)約束使式（8）提供了聚類的可解釋性，即F的元素能反映數(shù)據(jù)和簇之間聯(lián)系的緊密程度。其四，該問題是一個(gè)具有正交非負(fù)約束的問題，實(shí)質(zhì)上式（8）的解已經(jīng)具備離散性。如圖3 所示，假設(shè)F∈R3×9，表示有9 個(gè)數(shù)據(jù)點(diǎn)分別隸屬于3 個(gè)不同的簇。白色方塊表示值為零的元素，其他方塊表示非零元素。由于約束，使得F的每一行有且僅有一個(gè)非零元素，且每一列的L2范數(shù)為1。F為離散稀疏又具有物理意義的矩陣，其物理意義是F中元素的數(shù)值可以直接表示數(shù)據(jù)點(diǎn)和簇之間的關(guān)系。

圖3 正交約束示意圖Fig.3 Schematic diagram of orthogonal constraints

若相似矩陣W是一個(gè)雙隨機(jī)矩陣，即W的每一行和每一列所有元素之和為1的矩陣，則度矩陣是一個(gè)單位矩陣。那么L-I-W=，且F=H。此時(shí)，圖拉普拉斯矩陣已經(jīng)標(biāo)準(zhǔn)化，則式（5）與（6）完全等價(jià)。這就是從SNcut 和SRcut 的統(tǒng)一觀點(diǎn)出發(fā)得出的結(jié)論。在后續(xù)分析中，默認(rèn)W是雙隨機(jī)矩陣，同時(shí)也是結(jié)構(gòu)化圖。因此，可以通過命題1進(jìn)一步變換等式（8）為式（9）。

命題1求解式（8）等價(jià)于求解

證明設(shè)W為對(duì)稱的雙隨機(jī)矩陣，常數(shù)項(xiàng)為

在本研究中，式（9）是一種十分重要的模型，可以理解為是一種基于正交非負(fù)約束的圖重構(gòu)。因?yàn)樵紙D的構(gòu)建通常在數(shù)據(jù)中存在噪聲，所以沒有清晰的結(jié)構(gòu)，因此在學(xué)習(xí)結(jié)構(gòu)化圖時(shí)，圖重構(gòu)是一種優(yōu)化過程。如圖4 所示，M中每一個(gè)塊對(duì)應(yīng)一個(gè)連通分量，而一個(gè)連通分量屬于同一個(gè)簇。在大多數(shù)情況下，一個(gè)連通分量直接對(duì)應(yīng)一個(gè)簇。式（9）的目標(biāo)是通過對(duì)角分塊矩陣重構(gòu)相似矩陣，重構(gòu)后的矩陣需要與原始圖W相似，即用具有結(jié)構(gòu)信息的重構(gòu)圖來近似原始圖。這種清晰的結(jié)構(gòu)包含了很多關(guān)于簇類的準(zhǔn)確信息。在圖4 中，矩陣M的3 個(gè)位于對(duì)角線上的塊矩陣之間具有顯著差異。然而，在塊內(nèi)的數(shù)據(jù)不完全相同，但具有相似之處，因此這是一個(gè)十分優(yōu)秀的模型，在聚類過程中可以保證既關(guān)注聚類標(biāo)簽又關(guān)注簇內(nèi)的差異。

圖4 圖重構(gòu)示意圖Fig.4 Schematic diagram of reconstructed graph

因此，本研究的目標(biāo)函數(shù)為

式中：第1 項(xiàng)是重構(gòu)項(xiàng)，用于硬聚類；第2 項(xiàng)為平衡項(xiàng)，用于軟聚類；λ為平衡系數(shù)，用于保持兩項(xiàng)之間的平衡。當(dāng)λ足夠大時(shí)，F(xiàn)與G將無限接近，式（10）與式（9）等價(jià)。其中，G∈Rn×k，為標(biāo)簽矩陣，雖然描述的是聚類和樣本之間的非排他性關(guān)系，但最終是通過索引標(biāo)簽矩陣G中每行最大元素所在列，從而確定聚類標(biāo)簽。并且，與G無限接近的F中元素的數(shù)值可以直接表示數(shù)據(jù)點(diǎn)和簇之間的關(guān)系。因此，硬聚類不需要閾值或界限值來保證硬分配。被松弛的F具有連續(xù)值，但是與譜聚類不同的是，在式（10）的模型中，F(xiàn)無限接近非負(fù)矩陣G。式（10）與式（9）相比其計(jì)算成本更低，且更具有可解釋性。因此，將第2項(xiàng)用于統(tǒng)一標(biāo)簽矩陣可以降低時(shí)間成本，使該算法快速收斂。

2.2 優(yōu)化

由于式（10）是一個(gè)非凸問題，因此優(yōu)化過程采用交替方向乘子法（ADMM），將式（10）所提的問題分解為兩個(gè)子問題進(jìn)行求解。兩個(gè)子問題分別是對(duì)標(biāo)簽矩陣G和指示矩陣F求得局部最優(yōu)解。本文將最終的方法總結(jié)在下文的算法1中。

第1 步固定F并更新G?？梢允褂美窭嗜粘俗臃ǎ↙agrange Multiplier Method）和KKT（Karush-Kuhn-Tucker）條件進(jìn)行求解。雖然固定了F，但仍然需要滿足條件FTF=I。通過增加和刪除常數(shù)項(xiàng)，可以將問題轉(zhuǎn)化為

從而可以進(jìn)一步求解得：

則標(biāo)簽矩陣的最優(yōu)解可以表示為

式中，（·）+表示矩陣中每個(gè)元素均取絕對(duì)值。

第2步固定G并更新F。假設(shè)(W(v)F+λF)的奇異值分解（SVD）為則式（10）可轉(zhuǎn)化為

最終的方法總結(jié)如下。

2.3 初始化與構(gòu)圖

指示矩陣F的初始化有兩種方法：第1 種，可以通過隨機(jī)生成一個(gè)符合正交約束的矩陣進(jìn)行；第2 種，可以通過計(jì)算的前k個(gè)最小特征值對(duì)應(yīng)的特征向量構(gòu)建，這種方法等價(jià)于計(jì)算W（v）的前k個(gè)最大特征值對(duì)應(yīng)的特征向量。計(jì)算W（v）或并對(duì)其進(jìn)行特征分解是一種十分消耗內(nèi)存及時(shí)間的方法，為提升效率，可以通過奇異值分解的方法來求解。假設(shè)。若對(duì)(v)進(jìn)行SVD 可得到。因?yàn)?v)的左奇異向量為W（v）的特征向量，因此，可通過計(jì)算前k個(gè)最大的奇異值對(duì)應(yīng)的左奇異向量對(duì)F初始化。

FMCULM的詳細(xì)流程見圖5。

圖5 FMCULM算法流程圖Fig.5 Flow chart of FMCULM algorithm

2.4 時(shí)間復(fù)雜度

為進(jìn)一步驗(yàn)證本研究所提算法在運(yùn)行時(shí)間方面的優(yōu)勢(shì)，對(duì)時(shí)間復(fù)雜度進(jìn)行進(jìn)一步分析。隨機(jī)選取錨點(diǎn)地址的時(shí)間復(fù)雜度為O（1），通過SVD初始化F的過程需要O（m2n+m3），構(gòu)建的時(shí)間復(fù)雜度為O（mndv），迭代的過程需要O（mnk+m2k+nk2+k3）tv（其中t為迭代次數(shù)），對(duì)M進(jìn)行SVD 的過程需要O（nk2+k3）。由于m＞k且n?m，因此，總體的時(shí)間復(fù)雜度為O（m2n+mnktv），即只需要線性的時(shí)間復(fù)雜度。

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

為說明本算法的有效性，本節(jié)將該算法與其他聚類算法在真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比。實(shí)驗(yàn)中所有代碼的運(yùn)行環(huán)境均為Matlab R 2020a，硬件系統(tǒng)配置為2.60 GHz、i7-10750H CPU、16 Gbyte 運(yùn)行內(nèi)存、Windows 10系統(tǒng)。

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

在本文所述實(shí)驗(yàn)中，采用準(zhǔn)確率（γACC）、歸一化互信息（γNMI）和調(diào)整的蘭德指數(shù)（γARI）3 個(gè)指標(biāo)來判斷該算法的性能。其中γACC和γNMI指標(biāo)的區(qū)間均為［0，1］，γARI的區(qū)間為［-1，1］，三者均為數(shù)值越大則性能越佳。

如式（18）所示，γACC是指通過本方法進(jìn)行聚類后獲得的標(biāo)簽與真實(shí)標(biāo)簽之間匹配結(jié)果的平均聚類精度。

式中：pi為第i個(gè)樣本在該算法下產(chǎn)生的標(biāo)簽，yi為真實(shí)標(biāo)簽；當(dāng)x=y時(shí)，?(x，y)=1，否則為0；map（·）用來映射預(yù)測(cè)標(biāo)簽與真實(shí)標(biāo)簽之間的不同，聚類精度將以最佳的映射結(jié)果計(jì)算。

設(shè)θ為正確的聚類標(biāo)簽，而θ'則為通過算法預(yù)測(cè)的聚類標(biāo)簽，可以通過下式計(jì)算γNMI：

式中，P(·)為該樣本屬于該集群的概率，P（·，·）為二者的聯(lián)合概率，H（·）表示熵。

γARI用于測(cè)量?jī)蓚€(gè)集合之間的相似性，即

式中，和分別為第i個(gè)聚類的真實(shí)標(biāo)簽和學(xué)習(xí)標(biāo)簽，表示從a個(gè)元素構(gòu)成的集合中選取b個(gè)。

3.1.2 對(duì)比算法

將FMCULM與下列9種基準(zhǔn)算法進(jìn)行比較。為加以區(qū)分，將單視圖k-means 和Ncut 分別標(biāo)記為Sk-means 和SNcut，二者均為單視圖聚類算法。MSC 和CoregSC 是傳統(tǒng)的多視圖聚類方法，且是基于協(xié)同訓(xùn)練的多視圖聚類方法。MkC 和multiNMF是基于多視圖子空間的多視圖聚類方法。ASMV、MGL和MCGL是基于加權(quán)的多視圖聚類方法。由于Sk-means 和SNcut 只對(duì)單視圖數(shù)據(jù)有效，所以對(duì)于多視圖數(shù)據(jù)，本文將二者在每個(gè)視圖中分別運(yùn)行，并記錄最佳性能的視圖結(jié)果。

本研究從其作者的主頁(yè)獲得比較算法的原始代碼并在MATLAB中運(yùn)行。對(duì)比算法的參數(shù)設(shè)置采用對(duì)應(yīng)文獻(xiàn)中具備最佳性能的參數(shù)進(jìn)行設(shè)置，以避免該方法的結(jié)果非最佳性能。對(duì)于FMCULM，也在MATLAB中運(yùn)行，以確保環(huán)境的一致性。在參數(shù)設(shè)置中，利用經(jīng)驗(yàn)將k設(shè)置為20，并將平衡系數(shù)設(shè)置為1。

3.1.3 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)選取了不同視圖數(shù)量、不同數(shù)據(jù)來源、不同維度的4種數(shù)據(jù)集。數(shù)據(jù)集來自于植物、新聞、手寫數(shù)字和網(wǎng)頁(yè)4類真實(shí)案例，對(duì)本研究所提算法進(jìn)行多方面的比較。本文將重要參數(shù)歸納在表1中，以方便對(duì)比。表1中，n表示實(shí)例數(shù)量，v表示視圖數(shù)量，c表示簇類數(shù)量，d1至d6分別表示第1個(gè)至第6 個(gè)視圖的數(shù)據(jù)數(shù)量。①100leaves：有3 個(gè)視圖，每個(gè)視圖均為來自100 種植物葉片的1 600 個(gè)數(shù)據(jù)點(diǎn)。每個(gè)對(duì)象可以分別用3個(gè)視圖中的形狀描述符、精細(xì)比例邊距和紋理直方圖來描述。② 3sources：來自BBC、路透社和《衛(wèi)報(bào)》均涉及的3 個(gè)視圖。每個(gè)視圖有169條新聞，可以分為6個(gè)簇。③Mfeat：手寫數(shù)字?jǐn)?shù)據(jù)集，包括來自UCI存儲(chǔ)庫(kù)的手寫數(shù)字（0-9）。共計(jì)6個(gè)視圖，每個(gè)視圖包含2 000個(gè)樣本。其中，每個(gè)樣本均可以由6種不同類型的特征來表示。④ WebKB：有3個(gè)視圖，其中每個(gè)視圖有4類共203個(gè)網(wǎng)頁(yè)。每個(gè)網(wǎng)頁(yè)都可以用超類網(wǎng)頁(yè)的錨定文本、頁(yè)面的內(nèi)容和標(biāo)題來描述。

表1 真實(shí)數(shù)據(jù)集參數(shù)Table1 Real-world data set parameters

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

實(shí)驗(yàn)結(jié)果比較如表2、表3和表4所示，表中結(jié)果記錄為“→0”代表其結(jié)果接近于0，并非其結(jié)果實(shí)際為0。本實(shí)驗(yàn)將每種算法運(yùn)行10次取最佳結(jié)果，以百分比的形式記錄在表格中，并在表格中的括號(hào)內(nèi)記錄運(yùn)行10次的標(biāo)準(zhǔn)差。為了方便觀察，表中每個(gè)數(shù)據(jù)集中性能最佳的前兩個(gè)數(shù)據(jù)加粗表示。圖6和圖7分別給出了圖重構(gòu)的實(shí)例圖以及對(duì)于目標(biāo)函數(shù)和平衡項(xiàng)收斂速度的對(duì)比圖。

表2 聚類性能在準(zhǔn)確率方面的比較Table 2 Clustering performance comparison in terms of ACC %

表3 聚類性能在歸一化信息方面的比較Table 3 Clustering performance comparison in terms of NMI %

圖6 正交非負(fù)約束在實(shí)例中的說明Fig.6 Practical illustrations of orthogonal non-negative constraint in the example

圖7 在3個(gè)真實(shí)數(shù)據(jù)集中算法收斂性的分析Fig.7 Analysis of algorithm convergence in three real data sets

進(jìn)一步分析FMCULM的算法性能，可以從圖表中得出如下實(shí)驗(yàn)結(jié)果。FMCULM 在大部分?jǐn)?shù)據(jù)集上達(dá)到了所列性能指標(biāo)的最高聚類性能。例如，F(xiàn)MCULM 在100leaves 上相對(duì)于最好的第2 種MCGL的ACC超過了約11.9%，在3sources上相對(duì)于MGL的NMI 結(jié)果超過了約5.9%。FMCULM 優(yōu)于其他算法的性能是由于在選取錨點(diǎn)時(shí)不再需要k-means 等前工程，這使得算法擺脫了選取錨點(diǎn)的質(zhì)量對(duì)其的影響。同時(shí)，由于算法不需要后處理，而是通過直接索引標(biāo)簽矩陣每行最大元素所在列，從而使算法的性能得以提升［28］。此外，由于手寫數(shù)字的數(shù)據(jù)集中包含大量的負(fù)值，而MultiNMF 是基于非負(fù)矩陣分解的聚類方法，因此，在Mfeat 數(shù)據(jù)集中，MultiNMF無法處理。與CoregSC和MSC等由譜聚類改進(jìn)而來的多視圖算法相比，F(xiàn)MCULM有明顯的優(yōu)勢(shì)。這可能是由于本研究的算法不依賴于統(tǒng)一圖的學(xué)習(xí)，而是通過統(tǒng)一標(biāo)簽矩陣獲得標(biāo)簽。

此外，圖6（a）給出了FMCULM 在100leaves 上圖重構(gòu)的實(shí)例說明?？梢灾庇^地看到，通過FGT重建的圖具有清晰的結(jié)構(gòu)，圖中存在較強(qiáng)的簇內(nèi)連接和較弱的簇間連接。結(jié)構(gòu)化圖重建過程使本研究的方法優(yōu)于其他方法的聚類性能。如圖6（b）所示，原始構(gòu)造圖是雙隨機(jī)矩陣W。對(duì)比可知，通過FGT重建的圖比W具有更清晰的結(jié)構(gòu)。

3.3 計(jì)算效率實(shí)驗(yàn)

算法的運(yùn)行時(shí)間如表5所示，F(xiàn)MCULM 明顯優(yōu)于其他算法，在100leaves、3sources、Mfeat 和WebKB 數(shù)據(jù)集上均為最快的。在數(shù)據(jù)量最大的Mfeat 數(shù)據(jù)集上，F(xiàn)MCULM 的運(yùn)行時(shí)間也明顯高于其他算法，這顯現(xiàn)出了該算法在時(shí)間成本上的優(yōu)勢(shì)。主要原因有3個(gè)：其一，由于本文的算法沒有求解相似矩陣而是求解聚類過程中必要的值；其二，擺脫了特征值分解導(dǎo)致的O（n3）的高昂時(shí)間成本，轉(zhuǎn)而利用SVD求解F，從而降低時(shí)間成本；其三，由于非負(fù)約束使得可解釋性大幅提升，從而使得FMCULM不需要后處理。

表5 真實(shí)數(shù)據(jù)集中聚類性能在時(shí)間方面的比較Table 5 Performance comparison of each method in terms of running times s

3.4 算法收斂性驗(yàn)證

由于FMCULM是一種迭代算法，不可避免地要關(guān)注其收斂性。本研究還對(duì)該算法的收斂速度展開了實(shí)驗(yàn)。圖7 中虛線顯示了FMCULM 在100leaves、3sources和Mfeat 3個(gè)數(shù)據(jù)集上的收斂曲線。虛線表示目標(biāo)函數(shù)值與迭代次數(shù)的關(guān)系，實(shí)線代表平衡項(xiàng)與迭代次數(shù)之間的關(guān)系。在實(shí)際的實(shí)驗(yàn)中，通常在目標(biāo)函數(shù)兩次迭代的變化量不大于10-4時(shí)判定為收斂。在收斂性驗(yàn)證的實(shí)驗(yàn)中，取消這一限制，強(qiáng)制其執(zhí)行20次迭代。對(duì)于本研究中的平衡項(xiàng)，進(jìn)行了100 次迭代的實(shí)驗(yàn)，從而充分驗(yàn)證這一方法的有效性和穩(wěn)定性。FMCULM 通常是在10 次迭代之內(nèi)收斂，原因是本研究為每個(gè)子問題提供了一個(gè)優(yōu)化的解決方案。

FMCULM在目標(biāo)函數(shù)中加入了平衡項(xiàng)，即統(tǒng)一標(biāo)簽矩陣，并設(shè)置了平衡系數(shù)λ。F和G在每次迭代中逐漸相互接近，表示負(fù)項(xiàng)逐漸趨小或消失。從式（14）可知，這正是F和G之間的差異或負(fù)數(shù)的部分。在圖7 中，平衡項(xiàng)的值在迭代5 次左右趨向于0，這說明平衡項(xiàng)達(dá)到了收斂。此外，由于本研究所提出的算法是一種無監(jiān)督學(xué)習(xí)方法且需要輸入聚類數(shù)量，因此大大降低了快速收斂后過擬合的風(fēng)險(xiǎn)，為方法的穩(wěn)定性和可靠性提供了充分的保證。

4 結(jié)語(yǔ)

本研究提出了一種基于統(tǒng)一標(biāo)簽矩陣的快速多視圖聚類算法。該算法具有可解釋性強(qiáng)、準(zhǔn)確率高和運(yùn)行速度快的優(yōu)點(diǎn)。FMCULM 從譜聚類統(tǒng)一的切圖觀點(diǎn)出發(fā)，將構(gòu)建的相似矩陣在正交和非負(fù)約束下重構(gòu)為具有強(qiáng)簇內(nèi)連接和弱簇間連接的結(jié)構(gòu)圖。非負(fù)約束使聚類更具有可解釋性，從而避免后處理。在真實(shí)數(shù)據(jù)集上進(jìn)行的大量實(shí)驗(yàn)表明，F(xiàn)MCULM 具有良好的性能。此外，由于FMCULM 在不同數(shù)據(jù)集中參數(shù)的設(shè)置主要依據(jù)經(jīng)驗(yàn)進(jìn)行調(diào)整，這導(dǎo)致該算法的自適應(yīng)性有待提高。在接下來的研究中，將重點(diǎn)研究如何提高FMCULM的自適應(yīng)性；此外，如何利用多視圖互補(bǔ)信息來解決數(shù)據(jù)缺失的多視圖聚類問題，也是我們后續(xù)重點(diǎn)關(guān)注的內(nèi)容。