黃棟，王昌棟，賴劍煌，梁云，邊山，陳羽

(1.華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣東 廣州 510640； 2.中山大學(xué) 數(shù)據(jù)科學(xué)與計算機學(xué)院，廣東 廣州 510006； 3.廣東省信息安全技術(shù)重點實驗室, 廣東 廣州 510006)

?

基于決策加權(quán)的聚類集成算法

黃棟1，王昌棟2,3，賴劍煌2,3，梁云1，邊山1，陳羽1

(1.華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣東 廣州 510640； 2.中山大學(xué) 數(shù)據(jù)科學(xué)與計算機學(xué)院，廣東 廣州 510006； 3.廣東省信息安全技術(shù)重點實驗室, 廣東 廣州 510006)

摘要：聚類集成的目標(biāo)是融合多個聚類成員的信息以得到一個更優(yōu)、更魯棒的聚類結(jié)果。針對聚類成員可靠度估計與加權(quán)問題，提出了一個基于二部圖模型與決策加權(quán)機制的聚類集成方法。在該方法中，每個聚類成員被視作一個包含若干連接決策的集合。每個聚類成員的決策集合享有一個單位的可信度，該可信度由集合內(nèi)的各個決策共同分享?；诳尚哦确窒淼乃枷?，進一步對各個聚類成員內(nèi)的決策進行加權(quán)，并將此決策加權(quán)機制整合至一個統(tǒng)一的二部圖模型；然后利用快速二部圖分割算法將該圖劃分為若干子集，以得到最終聚類結(jié)果。實驗結(jié)果表明，該方法相較于其他對比方法在聚類效果及運算效率上均表現(xiàn)出顯著優(yōu)勢。

關(guān)鍵詞：聚類；聚類集成；決策加權(quán)；二部圖模型；圖分割；基聚類；可信度分享；加權(quán)集成

聚類集成(clustering ensemble)的目標(biāo)是融合多個聚類結(jié)果以得到一個更優(yōu)的最終聚類結(jié)果[1-10]。每一個輸入聚類稱為一個聚類成員(ensemble member)或者基聚類(base clustering)；聚類成員可以由不同聚類算法生成，或者由一個聚類方法在不同參數(shù)設(shè)定下生成。聚類成員的質(zhì)量(或可靠度)是影響聚類集成性能的關(guān)鍵因素之一。然而，在無監(jiān)督設(shè)定下，現(xiàn)有方法大多無法自動評估聚類成員可靠度并據(jù)此對其加權(quán)，從而容易受到低質(zhì)量聚類成員(甚至病態(tài)聚類成員)的負(fù)面影響。近年來，部分研究者開始對此進行研究并提出了一些加權(quán)聚類集成的方法[8,11]，但是這些方法往往在集成效果和運算效率上仍有局限性。例如，文獻(xiàn)[11]提出了一種基于非負(fù)矩陣分解的加權(quán)聚類集成方法，但該方法的非負(fù)矩陣分解過程運算負(fù)擔(dān)非常大，基本無法應(yīng)用于大數(shù)據(jù)集；文獻(xiàn)[8]提出了一種基于歸一化群體認(rèn)可度指標(biāo)的加權(quán)聚類集成方法，但較高的計算復(fù)雜度也是限制其更廣泛應(yīng)用的一個重要障礙。在當(dāng)前聚類集成研究中，如何高效地對聚類成員的可靠度進行評估并加權(quán)集成，仍是一個非常具有挑戰(zhàn)性的問題。

針對此問題，本文提出了一種基于二部圖構(gòu)造和決策加權(quán)機制的聚類集成算法。我們將每個聚類成員視作一個包含若干連接決策的集合。每個聚類成員的決策集合享有一個單位的可信度，該可信度由集合內(nèi)的各個決策共同分享。進一步，我們根據(jù)每個聚類成員的每個決策分享得到的可信度進行加權(quán)，并將之整合至一個二部圖模型，進而利用快速二部圖分割算法將該圖劃分為若干塊以得到最終聚類結(jié)果。我們將本文方法及多個對比方法在8個實際數(shù)據(jù)集上進行實驗分析，實驗結(jié)果表明，本文方法相較于其他對比方法在聚類集成效果及運算效率上均表現(xiàn)出顯著優(yōu)勢。

1相關(guān)研究

現(xiàn)有的聚類集成方法，主要可以分為3類：1)基于點對相似性的方法[4-5]；2)基于圖分割的方法[1,3]；3)基于中心聚類的方法[2,6]。

基于點對相似性的方法[4,5]根據(jù)數(shù)據(jù)點與數(shù)據(jù)點之間在多個聚類成員中屬于相同簇的頻率來得到一個共聯(lián)矩陣，并以該共聯(lián)矩陣作為相似性矩陣，進而采用層次聚類方法得到最終聚類結(jié)果。文獻(xiàn)[4]最早提出共聯(lián)矩陣的概念，并提出了線索集聚聚類(evidence accumulation clustering，EAC)方法。文獻(xiàn)[5]對EAC方法進行擴展，將簇的大小加入考慮，提出了概率集聚算法。

基于圖分割的方法[1,3]首先根據(jù)聚類集成信息構(gòu)造一個圖結(jié)構(gòu)，再利用圖分割算法將圖劃分為若干塊，進而得到最終的聚類集成結(jié)果。文獻(xiàn)[1]將聚類集成中的每一個簇視作一條超邊,構(gòu)造得到一個超圖結(jié)構(gòu)，進而可使用METIS算法[12]或Ncut算法[13]將其分割為若干塊，以得到最終聚類結(jié)果。

基于中心聚類的方法[2,6]將聚類集成問題建模為一個最優(yōu)化問題，其優(yōu)化目標(biāo)是尋找一個與所有聚類成員的相似性最大化的聚類結(jié)果。中心聚類問題是一個NP難問題[14]，因而在全局聚類空間尋找最優(yōu)解對于較大的數(shù)據(jù)集是幾乎不可行的。針對此問題，文獻(xiàn)[2]將聚類表示為染色體，并提出利用遺傳算法求得一個近似解。文獻(xiàn)[6]提出一種基于2-D串編碼的一致性度量，并利用0-1半正定規(guī)劃來最大化此一致性度量，以得到中心聚類。

盡管國內(nèi)外研究者已經(jīng)提出了許多聚類集成算法[1-6]，但這些算法大都將各個聚類成員同等對待，缺乏對聚類成員進行可靠度估計及加權(quán)的能力，容易受低質(zhì)量聚類成員(甚至病態(tài)聚類成員)的負(fù)面影響。針對此問題，近年來有研究者提出了一些解決方法[8,11]。文獻(xiàn)[11]提出了一種基于非負(fù)矩陣分解的加權(quán)聚類集成方法，在該方法的優(yōu)化過程中，可對各聚類成員的可靠度進行估計并加權(quán)；但是，該方法的非負(fù)矩陣分解過程的耗時非常大，使其無法應(yīng)用于較大數(shù)據(jù)集。文獻(xiàn)[8]利用歸一化群體認(rèn)可度指標(biāo)對各個聚類成員的可靠度進行估計，并進而提出了兩個加權(quán)聚類集成算法；但是歸一化群體認(rèn)可度指標(biāo)的計算復(fù)雜度較高，使其難以適用于大規(guī)模數(shù)據(jù)的聚類集成問題。在當(dāng)前聚類集成研究中，如何有效地、高效地估計聚類成員可靠度并據(jù)此加權(quán)集成，進而提高聚類集成性能，仍是一個亟待解決的挑戰(zhàn)性問題。

2基于決策加權(quán)的聚類集成算法

2.1問題建模

式中πm表示聚類集合Π中的第m個聚類成員。每一個聚類成員是對數(shù)據(jù)集X的一個聚類結(jié)果，各個聚類成員可以由不同聚類算法得到，或者由一個聚類算法在不同初始化和參數(shù)設(shè)置下運行得到。每個聚類成員包含若干個簇，記作

按照實驗方法，考慮和避免了各種不利影響因素后，測定4個鈦合金標(biāo)樣中的硅元素含量，測定結(jié)果見表1。測定結(jié)果表明樣品的絕對誤差和相對誤差均較小，鈦合金標(biāo)樣中硅含量測定的準(zhǔn)確度較高。

聚類集成的目標(biāo)是將聚類集合Π中各聚類成員的信息融合得到一個更優(yōu)、更魯棒的聚類結(jié)果。根據(jù)輸入信息的不同，聚類集成問題主要有2種不同的建模方式：第1種建模方式同時以聚類集合Π和數(shù)據(jù)集X作為輸入信息[15-17]；第2種建模方式則只以聚類集合Π為輸入信息，而不需要訪問數(shù)據(jù)集X中的數(shù)據(jù)特征[1-10]。兩種建模方式的區(qū)別就在于除聚類成員的信息之外是否可訪問原始數(shù)據(jù)特征。在聚類集成研究中，第2種建模方式對原始數(shù)據(jù)的依賴度更低，亦被更廣泛采用[1-10]；本文的聚類集成研究按照第2種建模方式進行，即以聚類集合Π為輸入，不要求訪問原始數(shù)據(jù)特征，依此得到最終聚類結(jié)果π*。

2.2決策加權(quán)

(1)

每個聚類成員包含一定數(shù)量的連接決策；聚類成員的可靠度估計與加權(quán)問題，可視作是對聚類成員連接決策的可靠度估計與加權(quán)問題。我們在實例研究中發(fā)現(xiàn)，聚類成員的可靠度與其連接決策總數(shù)存在顯著的負(fù)相關(guān)關(guān)系。

具體地，我們以MNIST數(shù)據(jù)集[18]為例。該數(shù)據(jù)集包含5 000個數(shù)據(jù)點。我們使用k均值聚類算法為該數(shù)據(jù)集生成100個聚類成員，每次生成均采用隨機聚類個數(shù)及隨機初始化。如果兩個數(shù)據(jù)點xi和xj在聚類成員πm中被劃分在同一個簇，并且這兩個數(shù)據(jù)點在MNIST數(shù)據(jù)集的真實類別中也屬于同一個類，那么稱聚類成員πm對數(shù)據(jù)點xi和xj作出了一個正確決策，并將πm作出的正確決策的數(shù)量記作#CorrectDecisions(πm)。我們將聚類成員πm作出的所有連接決策中正確決策所占的比例，稱為正確決策率，記作RatioCD(πm)，計算公式為

(2)

圖1顯示了MNIST數(shù)據(jù)集的100個聚類成員的連接決策數(shù)與正確決策率之間的關(guān)系。對每一個聚類成員，根據(jù)式(1)計算其連接決策數(shù)，根據(jù)式(2)計算其正確決策率，從而在圖1中描出對應(yīng)的坐標(biāo)點。由圖1可以看到，聚類成員的連接決策數(shù)與其正確決策率存在顯著的負(fù)相關(guān)關(guān)系。此實驗結(jié)論的直觀理解在于，若一個聚類成員作出的連接決策數(shù)量越小(即越稀有)，則其正確率往往越高(即越寶貴)；若其連接決策數(shù)量越大，則其決策出錯的比例往往越高。當(dāng)一個聚類成員將全體數(shù)據(jù)點都?xì)w入同一個簇時，其連接決策數(shù)達(dá)到最大值，此時該聚類成員的連接決策失去意義。

圖1　對于MNIST數(shù)據(jù)集，各聚類成員的連接決策數(shù)與正確決策率之間的關(guān)系Fig.1　The relation between #Decisions and RatioCD for the MNIST dataset

進而可得：

(3)

由定義可知，全體聚類成員的權(quán)值之和為1，即

2.3二部圖構(gòu)造與聚類集成

在聚類成員可靠度分析與權(quán)值分配的基礎(chǔ)上，我們將進一步將聚類集成問題構(gòu)造為一個二部圖模型。在所構(gòu)造的二部圖模型中，聚類集合中各個聚類成員的簇與數(shù)據(jù)點同時作為節(jié)點。簇節(jié)點與簇節(jié)點之間不存在連接邊；數(shù)據(jù)點節(jié)點與數(shù)據(jù)點節(jié)點之間亦不存在連接邊。兩個節(jié)點之間存在連接邊，當(dāng)且僅當(dāng)其中一個節(jié)點是數(shù)據(jù)點節(jié)點，另一個節(jié)點是簇節(jié)點，并且該數(shù)據(jù)點位于該簇之內(nèi)。邊的權(quán)值由該簇所在的聚類成員的權(quán)值決定(見式(3))。由此，可得到一個二部圖結(jié)構(gòu)，其左部為數(shù)據(jù)點節(jié)點的集合，右部為簇節(jié)點的集合。我們將該二部圖結(jié)構(gòu)表示為

式中：U=X表示左部節(jié)點集(數(shù)據(jù)點集合)，V=C表示右部節(jié)點集(簇集合)，E表示邊的集合。給定兩個節(jié)點ui和vj，兩者之間的邊的權(quán)值定義為

接下來，利用圖G的二部圖結(jié)構(gòu)，我們采用Tcut算法[19]將圖G快速地分割為若干塊，進而將每一塊中數(shù)據(jù)點集合作為最終聚類的一個簇，由此可以得到最終聚類結(jié)果。

2.4時間復(fù)雜度

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

在本節(jié)中，我們將在多個實際數(shù)據(jù)集中進行實驗，與若干現(xiàn)有聚類集成算法進行對比分析，以驗證本文方法的有效性及運算效率。

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

本文的實驗一共使用了8個實際數(shù)據(jù)集，分別是Glass、 Ecoli、 Image Segmentation(IS)、 MNIST、 ISOLET、 Pen Digits(PD)、 USPS以及Letter Recognition(LR)。其中，除MNIST數(shù)據(jù)集來自于文獻(xiàn)[18]之外，其他7個數(shù)據(jù)集均來自于UCI機器學(xué)習(xí)數(shù)據(jù)倉庫(UCI machine learning repository)[20]。所用的測試數(shù)據(jù)集的具體情況如表1所示。

表1　實驗數(shù)據(jù)集

3.2實驗設(shè)置與評價指標(biāo)

我們將聚類成員個數(shù)M稱為聚類集成規(guī)模；將數(shù)據(jù)集的數(shù)據(jù)點數(shù)N稱為數(shù)據(jù)規(guī)模。在后續(xù)實驗中，我們首先固定聚類集成規(guī)模M=10，接下來分別進行本文方法與聚類成員以及與其他聚類集成方法的對比實驗，并進一步測試在不同聚類集成規(guī)模M下各個聚類集成方法的聚類表現(xiàn)。最后，將對比測試各個聚類集成方法的運算效率。在本文實驗中，采用標(biāo)準(zhǔn)互信息量(normalized mutual information，NMI)[1]作為評價指標(biāo)。NMI可根據(jù)兩個聚類之間的互信息量來度量其相似性，是聚類研究中被廣泛應(yīng)用的一個評價指標(biāo)。一個聚類結(jié)果(與真實聚類比較)的NMI值越大，則表示其聚類質(zhì)量越好。

3.3與聚類成員的對比實驗

聚類集成的目標(biāo)是融合多個聚類成員的信息以期得到一個更優(yōu)聚類。在本節(jié)中，我們將本文方法的聚類集成結(jié)果，與聚類成員進行對比實驗。在每個數(shù)據(jù)集上均測試10次；每次測試均隨機生成一個包含M個聚類成員的聚類集合，然后在此聚類集合上運行本文算法以得到一個集成聚類結(jié)果。由此，得到本文方法在10次運行測試中的平均表現(xiàn)以及聚類成員的平均表現(xiàn)(以NMI度量)。如圖2所示。

圖2　本文方法與聚類成員的性能對比Fig.2　Comparison between our method and the base clusterings

本文方法可取得比聚類成員更好的聚類結(jié)果；尤其是在Glass、Ecoli、 IS、MNIST、PD、

USPS等數(shù)據(jù)集，本文方法相較聚類成員優(yōu)勢更顯著。

3.4聚類集成方法的對比實驗

本節(jié)將所提出方法與6個現(xiàn)有的聚類集成方法進行對比實驗。這6個對比方法分別是evidence accumulation clustering(EAC)[4]、hybrid bipartite graph formulation(HBGF)[3]、SimRank similarity based method(SRS)[21]、weighted connected triple based method(WCT)[22]、weighted evidence accumulation clustering(WEAC)[8]以及graph partitioning with multi-granularity link analysis(GP-MGLA)[8]。

在每一個數(shù)據(jù)集中，每個聚類集成方法均運行10次，每次運行根據(jù)第3.2節(jié)所述隨機生成聚類成員，進而得到每個算法在每個數(shù)據(jù)集的平均NMI得分及其標(biāo)準(zhǔn)差。在表2中，在每一個數(shù)據(jù)集中，最高NMI得分以粗體顯示。如表2所示，本文方法在8個數(shù)據(jù)集上均取得了優(yōu)于其他聚類集成方法的聚類效果，特別是在Glass、MNIST和USPS數(shù)據(jù)集上，本文方法取得的平均NMI得分比其他方法高出10%左右。表2的對比實驗結(jié)果驗證了本文方法在聚類集成效果上的優(yōu)勢。

表2　本文方法與其他聚類集成方法的對比實驗

3.5在不同聚類集成規(guī)模下的對比實驗

接下來，我們進行本文方法與其他對比方法在不同聚類集成規(guī)模(即聚類成員個數(shù))下的對比實驗。當(dāng)聚類集成規(guī)模由M=10增長到50時，各個聚類集成方法在10次運行中的平均NMI得分如圖3所示。在Ecoli數(shù)據(jù)集中，WCT方法取得了與本文方法基本相當(dāng)?shù)男阅鼙憩F(xiàn)。除了Ecoli數(shù)據(jù)集之外，在其他7個數(shù)據(jù)集中，本文方法在不同聚類集成規(guī)模下的聚類表現(xiàn)均顯著優(yōu)于其他方法。圖3的實驗結(jié)果驗證了本文方法在不同聚類集成規(guī)模下表現(xiàn)出比其他聚類集成方法更好的魯棒性。

3.6運行時間

在本節(jié)中，我們進行各個聚類集成方法的運行時間對比實驗。所有實驗均在MATLAB 2014b下運行，所使用的工作站配置具體如下：Windows Server 2008 R2 64位操作系統(tǒng)；英特爾八核心2.4 GHz中央處理器；96 GB內(nèi)存。為求客觀對比各個算法運行的CPU時間，所有實驗均在單線程模式下運行。

(a)Glass

(b)Ecoli

(c)IS

(d)MNIST

(e)ISOLET

(f)PD

(g)USPS

(h)LR圖3　各個方法的聚類集成性能Fig.3　The performances of different clustering ensemble methods with varying ensemble sizes

(h)LR圖4　各個聚類集成方法在不同數(shù)據(jù)規(guī)模下的運行時間對比Fig.4　Execution time of different methods with varying data sizes

3結(jié)束語

為解決聚類集成研究中的聚類成員可靠度估計與加權(quán)問題，本文提出了一個基于二部圖結(jié)構(gòu)與決策加權(quán)機制的聚類集成方法。我們將每個聚類成員視作一個包含若干連接決策的集合，并為每個聚類成員的決策集合分配一個單位的可信度。該可信度由聚類成員內(nèi)的各個決策共同分享。進一步地，我們提出基于可信度分享的決策加權(quán)機制，并將之整合至一個統(tǒng)一的二部圖模型中。因其二部圖結(jié)構(gòu)，該圖模型可利用Tcut算法進行快速分割，從而得到最終聚類集成結(jié)果。本文在8個實際數(shù)據(jù)集中進行了實驗，將所提出方法與聚類成員以及6個現(xiàn)有方法進行了對比分析。實驗結(jié)果驗證了本文方法在聚類質(zhì)量及運算效率上的顯著優(yōu)勢。

參考文獻(xiàn):

[1]STREHL A, GHOSH J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. The journal of machine learning research, 2003, 3(3): 583-617.

[2]CRISTOFOR D, SIMOVICI D. Finding median partitions using information-theoretical-based genetic algorithms[J]. Journal of universal computer science, 2002, 8(2): 153-172.

[3]FERN X Z, BRODLEY C E. Solving cluster ensemble problems by bipartite graph partitioning[C]//Proceedings of the 21st International Conference on Machine Learning. New York, NY, USA, 2004.

[4]FRED A L N, JAIN A K. Combining multiple clusterings using evidence accumulation[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(6): 835-850.

[5]WANG Xi, YANG Chunyu, ZHOU Jie. Clustering aggregation by probability accumulation[J]. Pattern recognition, 2009, 42(5): 668-675.

[6]SINGH V, MUKHERJEE L, PENG Jiming, et al. Ensemble clustering using semidefinite programming with applications[J]. Machine learning, 2010, 79(1/2): 177-200.

[7]HUANG Dong, LAI Jianhuang, WANG Changdong. Exploiting the wisdom of crowd: a multi-granularity approach to clustering ensemble[C]//Proceedings of the 4th International Conference on Intelligence Science and Big Data Engineering. Beijing, China, 2013: 112-119.

[8]HUANG Dong, LAI Jianhuang, WANG Changdong. Combining multiple clusterings via crowd agreement estimation and multi-granularity link analysis[J]. Neurocomputing, 2015, 170: 240-250.

[9]HUANG Dong, LAI Jianhuang, WANG Changdong. Ensemble clustering using factor graph[J]. Pattern recognition, 2016, 50: 131-142.

[10]HUANG Dong, LAI Jianhuang, WANG Changdong. Robust ensemble clustering using probability trajectories[J]. IEEE transactions on knowledge and data engineering, 2016, 28(5): 1312-1326.

[11]LI Tao, DING C. Weighted consensus clustering[C]//Proceedings of the 2008 SIAM International Conference on Data mining. Auckland, New Zealand, 2008: 798-809.

[12]KARYPIS G, KUMAR V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of parallel and distributed computing, 1998, 48(1): 96-129.

[13]NG A Y, JORDAN M I, WEISS Y. On spectral clustering: Analysis and an algorithm[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2001.

[14]TOPCHY A, JAIN A K, PUNCH W. Clustering ensembles: models of consensus and weak partitions[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(12): 1866-1881.

[15]VEGA-PONS S, CORREA-MORRIS J, RUIZ-SHULCLOPER J. Weighted partition consensus via kernels[J]. Pattern recognition, 2010, 43(8): 2712-2724.

[16]VEGA-PONS S, RUIZ-SHULCLOPER J, GUERRA-GANDóN A. Weighted association based methods for the combination of heterogeneous partitions[J]. Pattern recognition letters, 2011, 32(16): 2163-2170.

[17]徐森, 周天, 于化龍, 等. 一種基于矩陣低秩近似的聚類集成算法[J]. 電子學(xué)報, 2013, 41(6): 1219-1224.

XU Sen, ZHOU Tian, YU Hualong, et al. Matrix low rank approximation-based cluster ensemble algorithm[J]. Acta electronica sinica, 2013, 41(6): 1219-1224.

[18]LECUN Y, BOTTOU L, BENGIO Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324.

[19]LI Zhenguo, WU Xiaoming, CHANG S F. Segmentation using superpixels: a bipartite graph partitioning approach[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI, USA, 2012: 789-796.

[20]BACHE K, LICHMAN M. UCI machine learning repository[EB/OL]. (2013-04-04). http://archive.ics.uci.edu/ml.

[21]IAM-ON N, BOONGOEN T, GARRETT S. Refining pairwise similarity matrix for cluster ensemble problem with cluster relations[C]//Proceedings of the 11th International Conference on Discovery Science. Budapest, Hungary, 2008: 222-233.

[22]IAM-ON N, BOONGOEN T, GARRETT S, et al. A link-based approach to the cluster ensemble problem[J]. IEEE transactions on pattern analysis and machine intelligence, 2011, 33(12): 2396-2409.

黃棟，男，1987年生，講師，主要研究方向為數(shù)據(jù)挖掘與模式識別，發(fā)表學(xué)術(shù)論文10余篇。

王昌棟，男，1984年生，講師，主要研究方向為非線性聚類、社交網(wǎng)絡(luò)、大數(shù)據(jù)分析，發(fā)表學(xué)術(shù)論文40余篇。

賴劍煌，男，1964年生，教授，博士生導(dǎo)師，博士，廣東省圖象圖形學(xué)會理事長，中國圖象圖形學(xué)會常務(wù)理事，主要研究方向為生物特征識別、數(shù)字圖像處理、模式識別和機器學(xué)習(xí)。主持國家自然科學(xué)基金與廣東聯(lián)合重點項目、科技部科技支撐課題各1項，主持國家自然科學(xué)基金項目4項。發(fā)表學(xué)術(shù)論文近200篇。

中文引用格式：黃棟，王昌棟，賴劍煌，等.基于決策加權(quán)的聚類集成算法[J]. 智能系統(tǒng)學(xué)報， 2016, 11(3): 418-424.

英文引用格式：HUANG Dong，WANG Changdong，LAI Jianhuang，et al. Clustering ensemble by decision weighting[J]. CAAI Transactions on Intelligent Systems, 2016,11(3): 418-424.

Clustering ensemble by decision weighting

HUANG Dong1， WANG Changdong2,3， LAI Jianhuang2,3， LIANG Yun1， BIAN Shan1， CHEN Yu1

(1. College of Mathematics and Informatics, South China Agricultural University, Guangzhou 510640, China; 2. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China; 3. Guangdong Key Laboratory of Information Security Technology, Guangzhou 510006, China)

Abstract：The clustering ensemble technique aims to combine multiple base clusterings to achieve better and more robust clustering results.To evaluate the reliability of the base clusterings and weight them accordingly, in this paper, we propose a new clustering ensemble approach based on a bipartite graph formulation and decision weighting strategy. Each base clustering is treated as a bag of decisions, and is assigned one unit of credit. This credit is shared (divided) by all the decisions in one clustering. Using the credit sharing concept, we propose weighting the decisions in the base clusterings with regard to the credit they have. Then, the clustering ensemble problem is formulated into a bipartite graph model that incorporates the decision weights, and the final clustering is obtained by rapidly partitioning the bipartite graph. Experimental results have demonstrated the superiority of the proposed algorithm in terms of both effectiveness and efficiency.

Keywords：clustering; clustering ensemble; decision weighting; bipartite graph formulation; graph partitioning; base clustering; credit sharing; weighted clustering ensemble

作者簡介：

中圖分類號：TP18

文獻(xiàn)標(biāo)志碼：A

文章編號：1673-4785(2016)03-0418-08

通信作者：王昌棟. E-mail：changdongwang@hotmail.com.

基金項目：國家自然科學(xué)基金項目(61573387, 61502543); 廣東省自然科學(xué)基金杰出青年項目(16050000051);廣東省自然科學(xué)基金博士啟動項目(2016A030310457, 2015A030310450, 2014A030310180); 廣東省科技計劃項目(2015A020209124, 2015B010108001);廣州市科技計劃項目(201508010032); 中央高校基本科研業(yè)務(wù)費專項項目(16lgzd15);華南農(nóng)業(yè)大學(xué)青年科技人才培育專項基金項目.

收稿日期：2016-03-18.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.2016030

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0921.020.html