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

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

(1.華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣東 廣州 510640； 2.中山大學(xué) 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣東 廣州 510006； 3.廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室, 廣東 廣州 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é)與計(jì)算機(jī)學(xué)院，廣東 廣州 510006； 3.廣東省信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室, 廣東 廣州 510006)

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

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

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

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

1相關(guān)研究

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

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

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

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

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

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

2.1問題建模

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

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

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

2.2決策加權(quán)

(1)

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

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

(2)

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

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

進(jìn)而可得：

(3)

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

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

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

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

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

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

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

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

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

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

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

3.2實(shí)驗(yàn)設(shè)置與評價(jià)指標(biāo)

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

3.3與聚類成員的對比實(shí)驗(yàn)

聚類集成的目標(biāo)是融合多個(gè)聚類成員的信息以期得到一個(gè)更優(yōu)聚類。在本節(jié)中，我們將本文方法的聚類集成結(jié)果，與聚類成員進(jìn)行對比實(shí)驗(yàn)。在每個(gè)數(shù)據(jù)集上均測試10次；每次測試均隨機(jī)生成一個(gè)包含M個(gè)聚類成員的聚類集合，然后在此聚類集合上運(yùn)行本文算法以得到一個(gè)集成聚類結(jié)果。由此，得到本文方法在10次運(yùn)行測試中的平均表現(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聚類集成方法的對比實(shí)驗(yàn)

本節(jié)將所提出方法與6個(gè)現(xiàn)有的聚類集成方法進(jìn)行對比實(shí)驗(yàn)。這6個(gè)對比方法分別是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]。

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

表2　本文方法與其他聚類集成方法的對比實(shí)驗(yàn)

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

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

3.6運(yùn)行時(shí)間

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

(a)Glass

(b)Ecoli

(c)IS

(d)MNIST

(e)ISOLET

(f)PD

(g)USPS

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

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

3結(jié)束語

為解決聚類集成研究中的聚類成員可靠度估計(jì)與加權(quán)問題，本文提出了一個(gè)基于二部圖結(jié)構(gòu)與決策加權(quán)機(jī)制的聚類集成方法。我們將每個(gè)聚類成員視作一個(gè)包含若干連接決策的集合，并為每個(gè)聚類成員的決策集合分配一個(gè)單位的可信度。該可信度由聚類成員內(nèi)的各個(gè)決策共同分享。進(jìn)一步地，我們提出基于可信度分享的決策加權(quán)機(jī)制，并將之整合至一個(gè)統(tǒng)一的二部圖模型中。因其二部圖結(jié)構(gòu)，該圖模型可利用Tcut算法進(jìn)行快速分割，從而得到最終聚類集成結(jié)果。本文在8個(gè)實(shí)際數(shù)據(jù)集中進(jìn)行了實(shí)驗(yàn)，將所提出方法與聚類成員以及6個(gè)現(xiàn)有方法進(jìn)行了對比分析。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法在聚類質(zhì)量及運(yùn)算效率上的顯著優(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é)報(bào), 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年生，講師，主要研究方向?yàn)閿?shù)據(jù)挖掘與模式識別，發(fā)表學(xué)術(shù)論文10余篇。

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

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

中文引用格式：黃棟，王昌棟，賴劍煌，等.基于決策加權(quán)的聚類集成算法[J]. 智能系統(tǒng)學(xué)報(bào)， 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.

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

收稿日期：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