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

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

1 引言

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

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

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

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

表1 符號的定義

2 譜聚類生成基聚類

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

(1)

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

(2)

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

(3)

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

3 雙邊聚類一致性集成

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

(4)

將多劃分Ncut算法對所構圖進行劃分，在這個過程中雙邊聚類算法能將輸入數(shù)據(jù)的行和列同時聚類。目標函數(shù)如下所示

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

式中P=[p1，p2，…，pn]T∈Rn×c矩陣里面保存著行(樣本)的聚類結果，每一行有且只有一個非零元素1(若第i個樣本屬于第j個簇，則pij=1，其它則為0)，Q=[q1，q2，…，qd]T∈R(t×c)×c矩陣里面保存著列(特征)的聚類結果，每一行有且只有一個非零元素1(若第i特征屬于第j個簇，則qij=1，其它則為0)。c為行和列的聚類簇數(shù)，S=(YTDY)-1為對角矩陣。通過交替更新的方法得到最終的最優(yōu)值，更新如下

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

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

(10)

對S求偏導，并令等式為零，即

(11)

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

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

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

(12)

(13)

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

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

(14)

(15)

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

4 算法步驟

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

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

2)通過計算每個基聚類的平均標準互信息來選取基聚類，將選出的基聚類將基聚類轉化為指示矩陣W；

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

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

5 實驗結果與分析

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

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

實驗共選擇7個數(shù)據(jù)集進行實驗，這7個數(shù)據(jù)集都是來自數(shù)據(jù)庫的真實數(shù)據(jù)。Ecoli，Yeast，Ionosphere，Solar，Auto和Zoo都是來自UCI的數(shù)據(jù)集，其中Ecoli和Yeast都是關于蛋白質的數(shù)據(jù)集，Ionosphere是雷達從電離層返回的分類數(shù)據(jù)集，Zoo 關于動物分類數(shù)據(jù)集，Dig1-10是來自benchmark的數(shù)字數(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次，記錄每一次集成算法的最終聚類結果與真實標簽的標準互信息，最終取20次標準互信息的平均值。并與4個聚類集成算法HGPA，MCLA，CSPA，HBGF 相比較，記錄每次實驗的標準互信息并求20次的平均值，實驗結果如表3所示。

表3 標準互信息的平均值(最優(yōu)值標黑)

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

表4 標準互信息的平均值(最優(yōu)值標黑)

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

5.3 收斂性分析

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

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

5.4 基聚類大小的討論

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

在Ecoli、Ionosphere、Dig1-10數(shù)據(jù)集上隨著基聚類的增大，標準互信息的平均值也逐漸增大而在Yeast數(shù)據(jù)集上基本不變。即隨著基聚類增大能夠對本算法聚類集成算法的準確度有一定程度的提高。

6 結論

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