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

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

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

1 引言

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

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

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

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

表1 符號的定義

2 譜聚類生成基聚類

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

(1)

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

(2)

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

(3)

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

3 雙邊聚類一致性集成

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

(4)

將多劃分Ncut算法對所構(gòu)圖進(jìn)行劃分，在這個過程中雙邊聚類算法能將輸入數(shù)據(jù)的行和列同時聚類。目標(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)

由于上式求解是一個NP問題，加入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é)果，每一行有且只有一個非零元素1(若第i個樣本屬于第j個簇，則pij=1，其它則為0)，Q=[q1，q2，…，qd]T∈R(t×c)×c矩陣?yán)锩姹４嬷?特征)的聚類結(jié)果，每一行有且只有一個非零元素1(若第i特征屬于第j個簇，則qij=1，其它則為0)。c為行和列的聚類簇數(shù)，S=(YTDY)-1為對角矩陣。通過交替更新的方法得到最終的最優(yōu)值，更新如下

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

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

(10)

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

(11)

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

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

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

(12)

(13)

式中R=PS，r·k代表矩陣R的第k列。在矩陣Q的尋優(yōu)過程中。即尋找矩陣W分解后的每一列，與矩陣PSQT對應(yīng)列的最小歐式距離，從而使得目標(biāo)函數(shù)達(dá)到最小。由于Q為指示矩陣，其中每一行有且只有一個非零元素1。通過矩陣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)化過程中。即尋找矩陣W分解后的每一行，與矩陣PSQT對應(yīng)行的最小歐式距離，從而使得目標(biāo)函數(shù)達(dá)到最小。由于矩陣P中每一行有且只有一個非零元素1。在矩陣P第i行非零元素，選出矩陣L=SQT中的第k行，使得lk·與矩陣W中第i行的歐式距離達(dá)到最小值，使得目標(biāo)函數(shù)達(dá)到最小值。即在更新每一個參數(shù)的過程中都會使得目標(biāo)函數(shù)最小化，最終使得S，Q，P的值穩(wěn)定不變時整個目標(biāo)函數(shù)達(dá)到最小值，即目標(biāo)函數(shù)收斂。

4 算法步驟

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

1)運行m次譜聚類算法，得到m個基聚類；

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

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

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

5 實驗結(jié)果與分析

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

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

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

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

5.2 實驗比較

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

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

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

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

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

5.3 收斂性分析

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

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

5.4 基聚類大小的討論

為了研究基聚類大小對本算法聚類集成準(zhǔn)確度的影響。在本實驗中，從譜聚類生成的多個聚類結(jié)果中選擇基聚類(ensemble size分別為：20、30、40、50、60)。在數(shù)據(jù)集Ecoli、Ionosphere、Yeast、Dig1-10上分別獨立運行SBKM算法20次，記錄每次算法的標(biāo)準(zhǔn)互信息并且計算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算法在生成階段通過譜聚類(Ncut)算法獲得基聚類，并通過對基聚類的選擇，盡可能的挖掘數(shù)據(jù)的潛在信息，從而提高基聚類的質(zhì)量。在集成階段通過雙邊聚類充分利用將樣本與基聚類之間的潛在信息，同時對樣本和基聚類進(jìn)行聚類，直接得到最終的聚類結(jié)果，并且能夠在七個數(shù)據(jù)集上有較好的表現(xiàn)。相比于其它聚類集成算法文中的算法不僅能夠充分的利用數(shù)據(jù)之間的潛在信息，而且能夠之間得到最終的聚類結(jié)果而不需要借助其它傳統(tǒng)聚類算法。