一種高效的雙邊聚類集成算法

楊 輝，彭 晗，朱建勇，聶飛平

(1.華東交通大學(xué)電氣與自動(dòng)化工程學(xué)院，江西 南昌 330013；2.江西省先進(jìn)控制與優(yōu)化重點(diǎn)實(shí)驗(yàn)室，江西 南昌330013；3.西北工業(yè)大學(xué)光學(xué)影像分析與學(xué)習(xí)中心，陜西 西安710072)

1 引言

在數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)等領(lǐng)域中，聚類技術(shù)是無(wú)監(jiān)督數(shù)據(jù)探索和分析的重要工具，但數(shù)據(jù)聚類仍然是一個(gè)非常具有挑戰(zhàn)性的問(wèn)題。其目的是發(fā)現(xiàn)給定數(shù)據(jù)集本身的固有結(jié)構(gòu)并將該數(shù)據(jù)集劃分為特定的同類組，即簇。在過(guò)去的幾十年中，通過(guò)利用各種技術(shù)提出了許多聚類算法[1-6]。

聚類集成旨在合并多個(gè)聚類[7]以獲得可能更好，更魯棒的聚類結(jié)果，這在發(fā)現(xiàn)奇異聚類，處理噪聲的聚類解決方案方面顯示出優(yōu)勢(shì)[8]。隨著聚類集成技術(shù)的不斷發(fā)展，其中有些研究者通過(guò)結(jié)合其它技術(shù)來(lái)提高最終聚類準(zhǔn)確率，如投票法[9]、超圖劃分[10]。Fred等[11]提出了證據(jù)累積方法，通過(guò)斷裂最弱的連接發(fā)現(xiàn)自然的簇。王紅軍等[12]提出了一種基于隱含變量的聚類集成模型，直接利用多個(gè)聚類的結(jié)果來(lái)組成原始數(shù)據(jù)集的不同特征，直接應(yīng)用聚類算法。Strehl等[13]基于圖劃分的思想提出了基于簇相似的分割算法CSPA(Cluster-based Similarity Partitioning Algorithm)，超圖分割算法HGPA(HyperGraphs Partitioning Algorithm)和元聚類算法MCLA(Meta-CLustering Algorithm)3種聚類集成算法。通過(guò)構(gòu)造共協(xié)矩陣，并將樣本和基聚類分別作為圖的頂點(diǎn)，將最初的優(yōu)化問(wèn)題轉(zhuǎn)化為圖的分割問(wèn)題，有效提高了聚類質(zhì)量。Fern等[14]提出一個(gè)稱為混合二部圖的構(gòu)想HBGF(Hybrid Bipartite Graph Formulation)算法充分的利用樣本與基聚類之間的潛在信息。

以往的聚類集成不能直接得到最終的聚類結(jié)果，得到的解還需要運(yùn)用傳統(tǒng)的聚類算法比如k-means算法[15]，譜聚類算法[16]等等，在整個(gè)過(guò)程中使解由離散-連續(xù)-離散的轉(zhuǎn)變，可能會(huì)導(dǎo)致最終的解與最優(yōu)解產(chǎn)生較大的偏離。本文提出的聚類集成SBKM(Spectral Bilateral K-means Algorithm)不僅準(zhǔn)確度高而且可以直接得到最終的聚類結(jié)果。在生成基聚類階段運(yùn)用譜聚類算法得到多個(gè)的基聚類。在多個(gè)基聚類中，用NMI(Normalized Mutual Information)聚類評(píng)價(jià)指標(biāo)選取基聚類，通過(guò)增大聚類結(jié)果中基聚類之間的差異，從而獲得更好的集成，并將選出的基聚類結(jié)果作為新矩陣的特征并轉(zhuǎn)換為對(duì)應(yīng)的指示矩陣，將新的矩陣作為輸入通過(guò)雙邊聚類算法BKM(Bilateral K-means Algorithm)[17]將樣本和基聚類同時(shí)聚類，直接得到最終的聚類結(jié)果。

為了更好的理解本文符號(hào)和規(guī)范的定義，總結(jié)如表1所示。

表1 符號(hào)的定義

2 譜聚類生成基聚類

譜聚類(spectral clustering)是一種基于圖劃分的方法，它通過(guò)構(gòu)建圖將聚類問(wèn)題轉(zhuǎn)變成圖論里面的劃分問(wèn)題。在聚類里面應(yīng)用比較廣泛的的譜聚類算法Ncut(Normalized cut)，其目標(biāo)函數(shù)可以表示為[18]

(1)

假定數(shù)據(jù)類別數(shù)為c，對(duì)初始數(shù)據(jù)運(yùn)行m次譜聚類算法(Ncut)，得到m個(gè)聚類結(jié)果。從m個(gè)聚類結(jié)果中利用標(biāo)準(zhǔn)互信息NMI 選擇基聚類。標(biāo)準(zhǔn)互信息計(jì)算公式[19]如下所示

(2)

式中nij表示聚類結(jié)果的第i個(gè)簇中包含原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù)，ni表示聚類結(jié)果的第i個(gè)簇的樣本總數(shù)，nj表示原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù)，n表示樣本總數(shù)。I和J分別表示聚類得到的簇個(gè)數(shù)和原數(shù)據(jù)集的類個(gè)數(shù)，如果NMI的值越接近1，說(shuō)明和?吻合程度越高，即所包含的信息越相似差異性較小。通過(guò)利用NMI評(píng)價(jià)指標(biāo)從生成的m個(gè)聚類結(jié)果中來(lái)選擇基聚類，從而增大基聚類之間的差異[20]。將最終得到的基聚類作為特征構(gòu)建矩陣R=[r1，r2，…，rm]∈Rn×m，其中ri表示運(yùn)行第i次譜聚類算法產(chǎn)生的基聚類的結(jié)果。通過(guò)計(jì)算基聚類ri與其它基聚類rj(i≠j)標(biāo)準(zhǔn)互信息總和，從而得到第i個(gè)基聚類總的平均標(biāo)準(zhǔn)互信息Ui，公式如下

(3)

Ui的值越大，說(shuō)明第i基聚類里面所包含的信息與其它基聚類所包含的信息相差不大，從而使整體的差異性有所下降。在所有的基聚類中選出Ui中最小的t個(gè)基聚類，將t個(gè)基聚類分別轉(zhuǎn)化為指示矩陣(每一行有且只有一個(gè)非零元素1，其它則為0)并將其作為新數(shù)據(jù)矩陣的特征(列)，即新的數(shù)據(jù)矩陣W∈Rn×(t×c)。例如通過(guò)選擇最終有2個(gè)基聚類結(jié)果被選出來(lái)且數(shù)據(jù)簇?cái)?shù)為2，分別為[1，1]T，[1，2]T。將其轉(zhuǎn)化為指示矩陣[10;10]和[10;01]并作為新的數(shù)據(jù)矩陣W的特征(列)，即此時(shí)數(shù)據(jù)矩陣為[1010;1001]。

3 雙邊聚類一致性集成

將數(shù)據(jù)矩陣W的行和列同時(shí)作為圖中的頂點(diǎn)，其鄰接矩陣A可以表示為如下圖所示

(4)

將多劃分Ncut算法對(duì)所構(gòu)圖進(jìn)行劃分，在這個(gè)過(guò)程中雙邊聚類算法能將輸入數(shù)據(jù)的行和列同時(shí)聚類。目標(biāo)函數(shù)如下所示

s.t.Y∈φ(n+d)×c

(5)

s.t.Y∈φ(n+d)×c

(6)

上式L=D-A，Y=[PT，QT]。所以式(6)可以改寫為

(7)

即目標(biāo)優(yōu)化函數(shù)又可以轉(zhuǎn)變成如下所示

(8)

由于上式求解是一個(gè)NP問(wèn)題，加入Tr(WTW))和Tr((YTDY)-1PTP(YTDY)-1QTQ)，式(8)的目標(biāo)優(yōu)化函數(shù)可以轉(zhuǎn)變成如下

(9)

式中P=[p1，p2，…，pn]T∈Rn×c矩陣?yán)锩姹４嬷?樣本)的聚類結(jié)果，每一行有且只有一個(gè)非零元素1(若第i個(gè)樣本屬于第j個(gè)簇，則pij=1，其它則為0)，Q=[q1，q2，…，qd]T∈R(t×c)×c矩陣?yán)锩姹４嬷?特征)的聚類結(jié)果，每一行有且只有一個(gè)非零元素1(若第i特征屬于第j個(gè)簇，則qij=1，其它則為0)。c為行和列的聚類簇?cái)?shù)，S=(YTDY)-1為對(duì)角矩陣。通過(guò)交替更新的方法得到最終的最優(yōu)值，更新如下

固定P，Q更新S，將目標(biāo)函數(shù)展開并將其定義為J即

=Tr(WTW)-2Tr(QTWTPS)+Tr(SPTPQTQS)

(10)

對(duì)S求偏導(dǎo)，并令等式為零，即

(11)

由式(11)得S=[(PTPQTQ)T]-1(PTWQ)

在P，Q更新求解過(guò)程中將數(shù)據(jù)矩陣W分解即：在求解Q矩陣的過(guò)程中將數(shù)據(jù)矩陣W分解成t×c列，而在求解P矩陣的過(guò)程中則是將數(shù)據(jù)矩陣W分解成n行。

當(dāng)固定S，P更新Q。目標(biāo)函數(shù)可以表示為

(12)

(13)

式中R=PS，r·k代表矩陣R的第k列。在矩陣Q的尋優(yōu)過(guò)程中。即尋找矩陣W分解后的每一列，與矩陣PSQT對(duì)應(yīng)列的最小歐式距離，從而使得目標(biāo)函數(shù)達(dá)到最小。由于Q為指示矩陣，其中每一行有且只有一個(gè)非零元素1。通過(guò)矩陣QT的第i列非零元素，選出矩陣R=PS中的第k列，使得r·k與矩陣W中的第i列的歐式距離達(dá)到最小值，從而使得目標(biāo)函數(shù)達(dá)到最小值。

固定S，Q更新P。其目標(biāo)函數(shù)可以表示為

(14)

(15)

式中L=SQT，lk·代表矩陣L的第k行。在矩陣P的優(yōu)化過(guò)程中。即尋找矩陣W分解后的每一行，與矩陣PSQT對(duì)應(yīng)行的最小歐式距離，從而使得目標(biāo)函數(shù)達(dá)到最小。由于矩陣P中每一行有且只有一個(gè)非零元素1。在矩陣P第i行非零元素，選出矩陣L=SQT中的第k行，使得lk·與矩陣W中第i行的歐式距離達(dá)到最小值，使得目標(biāo)函數(shù)達(dá)到最小值。即在更新每一個(gè)參數(shù)的過(guò)程中都會(huì)使得目標(biāo)函數(shù)最小化，最終使得S，Q，P的值穩(wěn)定不變時(shí)整個(gè)目標(biāo)函數(shù)達(dá)到最小值，即目標(biāo)函數(shù)收斂。

4 算法步驟

假定樣本矩陣X∈Rn×d，樣本的聚類簇?cái)?shù)c，其步驟總結(jié)如下：

1)運(yùn)行m次譜聚類算法，得到m個(gè)基聚類；

2)通過(guò)計(jì)算每個(gè)基聚類的平均標(biāo)準(zhǔn)互信息來(lái)選取基聚類，將選出的基聚類將基聚類轉(zhuǎn)化為指示矩陣W；

3)根據(jù)式(11)、(13)、(15)分別計(jì)算S、Q、P；

4)最終收斂時(shí)指示矩陣P所存儲(chǔ)的結(jié)果就是最終聚類結(jié)果。

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

本節(jié)將提出的聚類集成算法(SBKM)與流行的聚類集成算法相比較，并對(duì)所得的實(shí)驗(yàn)結(jié)果進(jìn)行分析。并選取了標(biāo)準(zhǔn)互信息作為評(píng)價(jià)指標(biāo)。

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

實(shí)驗(yàn)共選擇7個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，這7個(gè)數(shù)據(jù)集都是來(lái)自數(shù)據(jù)庫(kù)的真實(shí)數(shù)據(jù)。Ecoli，Yeast，Ionosphere，Solar，Auto和Zoo都是來(lái)自UCI的數(shù)據(jù)集，其中Ecoli和Yeast都是關(guān)于蛋白質(zhì)的數(shù)據(jù)集，Ionosphere是雷達(dá)從電離層返回的分類數(shù)據(jù)集，Zoo 關(guān)于動(dòng)物分類數(shù)據(jù)集，Dig1-10是來(lái)自benchmark的數(shù)字?jǐn)?shù)據(jù)集。實(shí)驗(yàn)數(shù)據(jù)集的具體描述見表2。

表2 數(shù)據(jù)集的具體描述

5.2 實(shí)驗(yàn)比較

在實(shí)驗(yàn)中，主要分為兩個(gè)部分：第一部分，選取數(shù)據(jù)集(Ecoli，Yeast，Ionosphere，Dig1-10)作為數(shù)據(jù)輸入分別獨(dú)立運(yùn)行多次譜聚類(Ncut)，選擇出t個(gè)基聚類分別為20，30，40(即ensemble size分別為20，30，40)。獨(dú)立運(yùn)行SBKM聚類集成算法20次，記錄每一次集成算法的最終聚類結(jié)果與真實(shí)標(biāo)簽的標(biāo)準(zhǔn)互信息，最終取20次標(biāo)準(zhǔn)互信息的平均值。并與4個(gè)聚類集成算法HGPA，MCLA，CSPA，HBGF 相比較，記錄每次實(shí)驗(yàn)的標(biāo)準(zhǔn)互信息并求20次的平均值，實(shí)驗(yàn)結(jié)果如表3所示。

表3 標(biāo)準(zhǔn)互信息的平均值(最優(yōu)值標(biāo)黑)

在實(shí)驗(yàn)的第二部分，選取數(shù)據(jù)集(Zoo，Solar，Auto)作為數(shù)據(jù)輸入與譜聚類算法(Ncut)相比較，在這部分實(shí)驗(yàn)中分別獨(dú)立運(yùn)行SBKM算法和譜聚類算法(Ncut)20次，且在SBKM算法中ensemble size分別設(shè)置為20，30，40，記錄每次實(shí)驗(yàn)的標(biāo)準(zhǔn)互信息并求20次的平均值，實(shí)驗(yàn)結(jié)果如表4所示。

表4 標(biāo)準(zhǔn)互信息的平均值(最優(yōu)值標(biāo)黑)

實(shí)驗(yàn)結(jié)果如表3，表4所示。根據(jù)表3可知，本文提出的算法SBKM在一些方面優(yōu)于其它聚類集成算法。在NMI評(píng)價(jià)指標(biāo)下，SBKM算法在這4個(gè)數(shù)據(jù)集中取得了最優(yōu)結(jié)果，相較于其它幾個(gè)對(duì)比算法有效地提高了聚類集成的質(zhì)量。根據(jù)表4可知，在其它3個(gè)數(shù)據(jù)集中也取得了較好的結(jié)果，這說(shuō)明聚類集成的質(zhì)量比單一聚類要好。SBKM算法能夠有效使用基聚類與樣本之間的潛在信息來(lái)提高聚類質(zhì)量。

5.3 收斂性分析

本文提出的一種基于譜聚類的雙邊聚類集成算法(SBKM)。通過(guò)實(shí)驗(yàn)研究最終得到的S，P，Q三個(gè)參數(shù)都是最優(yōu)值，使得目標(biāo)函數(shù)值最小即目標(biāo)函數(shù)收斂。假定ensemble size 為20時(shí)，SBKM算法在7個(gè)數(shù)據(jù)集上的目標(biāo)函數(shù)值如圖1所示。SBKM算法最終都能在數(shù)據(jù)集上目標(biāo)函數(shù)達(dá)到最終的收斂。

圖1 迭代過(guò)程中的目標(biāo)函數(shù)值

5.4 基聚類大小的討論

為了研究基聚類大小對(duì)本算法聚類集成準(zhǔn)確度的影響。在本實(shí)驗(yàn)中，從譜聚類生成的多個(gè)聚類結(jié)果中選擇基聚類(ensemble size分別為：20、30、40、50、60)。在數(shù)據(jù)集Ecoli、Ionosphere、Yeast、Dig1-10上分別獨(dú)立運(yùn)行SBKM算法20次，記錄每次算法的標(biāo)準(zhǔn)互信息并且計(jì)算20次算法的標(biāo)準(zhǔn)互信息的平均值，如圖2所示。

在Ecoli、Ionosphere、Dig1-10數(shù)據(jù)集上隨著基聚類的增大，標(biāo)準(zhǔn)互信息的平均值也逐漸增大而在Yeast數(shù)據(jù)集上基本不變。即隨著基聚類增大能夠?qū)Ρ舅惴ň垲惣伤惴ǖ臏?zhǔn)確度有一定程度的提高。

6 結(jié)論

本文提出了一種新的聚類集成算法。SBKM算法在生成階段通過(guò)譜聚類(Ncut)算法獲得基聚類，并通過(guò)對(duì)基聚類的選擇，盡可能的挖掘數(shù)據(jù)的潛在信息，從而提高基聚類的質(zhì)量。在集成階段通過(guò)雙邊聚類充分利用將樣本與基聚類之間的潛在信息，同時(shí)對(duì)樣本和基聚類進(jìn)行聚類，直接得到最終的聚類結(jié)果，并且能夠在七個(gè)數(shù)據(jù)集上有較好的表現(xiàn)。相比于其它聚類集成算法文中的算法不僅能夠充分的利用數(shù)據(jù)之間的潛在信息，而且能夠之間得到最終的聚類結(jié)果而不需要借助其它傳統(tǒng)聚類算法。