張棟超,蔡江輝,楊海峰,鄭愛宇

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,山西 太原 030024)

0 引 言

聚類是統(tǒng)計多元分析、數(shù)據(jù)挖掘和機器學(xué)習(xí)中的一個重要問題。聚類的目標(biāo)是將一組對象分組成簇,以便同一簇中的對象與其他簇中的對象高度相似但顯著不同。在過去幾十年中,已經(jīng)開發(fā)了大量聚類算法,包括分區(qū)[1]、分層[2]、基于密度[3]和基于網(wǎng)格[4]的聚類等。但沒有一種算法能夠處理實踐中遇到的所有聚類問題,即無法發(fā)現(xiàn)具有不同大小、形狀和噪聲水平的所有聚類。給定一個數(shù)據(jù)集,不同的算法通常返回不同的結(jié)果。事實上,由具有不同初始化和參數(shù)的相同算法返回的聚類結(jié)果通常是不同的。因此,用戶可能會困惑于選擇最合適的方法來解決他們的問題。集成聚類方法已成為克服這一問題的有力工具。

集成聚類是聚類的一個重要分支。聚類集成根據(jù)多個聚類結(jié)果找到一個最終的數(shù)據(jù)劃分,該劃分最大程度地共享了所有基聚類的信息。目前已經(jīng)開發(fā)了幾種類型的聚類集成方法,其中基于相似性的聚類集成方法受到很多研究者的青睞。很多學(xué)者通過尋找初始對象之間的相似性來構(gòu)建共協(xié)矩陣[5],然后通過該矩陣獲得最終聚類劃分。

在矩陣元素的相似性計算過程中,大部分研究者將基聚類信息看的同等重要,而原始對象中往往會有一些噪聲,導(dǎo)致基聚類結(jié)果變差,并影響了最終聚類結(jié)果,而且傳統(tǒng)的共協(xié)矩陣空間復(fù)雜度往往是O(n2),在數(shù)據(jù)量較大時內(nèi)存占用極大。因此,該文提出了一個基于簇間相似性的聚類集成方法。首先,設(shè)計了一種基于證據(jù)積累模型的相似度計算方法,將相似度大的樣本點暫時劃分為小簇;然后,提出一種新的相似度計算方法,將劃分好的小簇作為相似矩陣的構(gòu)成對象,構(gòu)建相似矩陣;最后,通過對相似矩陣的切圖,形成最終的聚類劃分。

主要貢獻(xiàn)如下:

(1)設(shè)計了一種基于證據(jù)積累模型的相似性計算方法,有效地將初始對象形成初始簇劃分。

(2)提出一種簇間相似性計算方法,用簇來構(gòu)建相似矩陣,該方法相比直接使用原始對象構(gòu)建共協(xié)矩陣,大大節(jié)省了空間復(fù)雜度。

1 相關(guān)知識

目前,聚類集成有兩個重要任務(wù):

(1)如何生成不同的基聚類并保證其多樣性;

(2)如何將多個不同的基聚類融合生成最終一致聚類。

第一個任務(wù)已經(jīng)提出了幾種不同的方法,大致可以分為以下3類:

(1)使用相同的方法(參數(shù)不同)來生成基聚類。比如用k-means作為基聚類器用不同的聚類數(shù)來生成聚類集[5];隨機選擇不同的聚類中心使用k-means[6];使用不同的核參數(shù)運行譜聚類算法[7]等;

(2)運行不同類型的聚類算法以生成基本聚類。比如使用多個層次聚類和k-均值生成聚類集[8];將具有不同目標(biāo)函數(shù)的多個聚類算法作為基本聚類,并將聚類集成問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題[9];Yu等人研究了如何整合多種類型的模糊聚類[10]等;

(3)在數(shù)據(jù)集中的不同子空間或子樣本上運行一個或多個聚類算法。比如應(yīng)用bootstrap方法獲得了多個數(shù)據(jù)子集[11];使用隨機映射的方法獲得多個特征子空間[12];使用不同的核函數(shù)來描述數(shù)據(jù)[13];結(jié)合boosting和bagging的優(yōu)點,提出一種新的簇集合混合采樣方法[14]等。

第二個任務(wù)開發(fā)了幾種類型的聚類集成方法,大致可以分為以下4類:

(1)成對相似性方法。利用所有數(shù)據(jù)對象兩兩之間的相似關(guān)系來聚合多個聚類。比如Fred和Jain[5]提出了一種基于證據(jù)積累的集成算法,并構(gòu)造了一個相似度矩陣;Iam On等人定義了一個基于鏈接的相似度矩陣,該矩陣充分考慮了集群之間的相似度[15];Huang等人提出了一種增強的共協(xié)矩陣[16],該矩陣能夠同時捕獲聚類中的對象共現(xiàn)關(guān)系以及多尺度集群關(guān)系。薛紅艷等人[17]以及邵長龍等人[18]用信息熵對共協(xié)矩陣加權(quán)以達(dá)到更好的聚類效果。

(2)基于圖的方法。將基礎(chǔ)聚類信息表達(dá)為一個無向圖,通過圖劃分得到集合聚類。比如Strehl和Ghosh提出了3種超圖集成算法[19]:基于聚類的相似性劃分算法(CSPA)、超圖劃分算法(HGPA)和元聚類算法(MCLA)。CSPA創(chuàng)建一個相似圖(對象視為頂點,相似度做邊)。HGPA構(gòu)建了一個超圖,其中頂點代表對象,而相同的加權(quán)超邊代表簇。MCLA生成一個圖,其中頂點代表聚類,而邊的權(quán)重反映聚類之間的相似性。Bai等人[20]提出了從基聚類中提取可信度標(biāo)簽,通過聚類的關(guān)系構(gòu)建形成圖,最后通過歸一化譜聚類獲得最終聚類結(jié)果。

(3)基于重標(biāo)記的方法。將基本聚類信息表示為標(biāo)簽向量,然后通過標(biāo)簽對齊聚類。其代表性方法有硬標(biāo)簽對齊和軟標(biāo)簽對齊。比如將重標(biāo)記問題轉(zhuǎn)化為最小成本的一對一分配問題[21];使用交替優(yōu)化策略來解決軟標(biāo)簽對齊問題[22];Rathore等人提出了一個有效的模糊集合框架[23],該框架使用累積一致方案來聚集模糊聚類。

(4)基于特征的聚類方法,將聚類集成問題作為分類數(shù)據(jù)的聚類。比如整合信息論和遺傳算法來尋找最一致的聚類[24];Topchyet 等人提出了一個概率框架[25],并使用EM算法來尋找共識聚類等。

除了以上4種,近年來也有部分學(xué)者提出使用加權(quán)的方法。與現(xiàn)有的方法不同,筆者研究的對象被指定用k-means算法做基聚類器。首先,對原始對象進行相似度計算,形成多個小簇;然后,用另一種方法計算簇與簇之間的相似度;最后,通過NCUT[26]切圖的方式得到最終聚類劃分,來實現(xiàn)多弱等于強的目的。

2 文中算法

2.1 相關(guān)定義

設(shè)X={X1,X2,…,Xn}是對象的集合,其中,

xi={xi1,xi2,…,xid}

d為維度,n為數(shù)據(jù)對象的個數(shù)。聚類集成方法首先要在數(shù)據(jù)集X上產(chǎn)生M個聚類結(jié)果,即:

∏={π1,π2,…,πM}

其中,

πh={Ch1,Ch2,…,Chl}

是第h個基聚類,Chl表示第h個基聚類的第l個簇。該文主要使用的符號如表1所示。

表1 常用符號

2.2 聚類集成方法

(1)

其中,vhl表示第h個基分區(qū)中第l個簇的中心點,d(xi,vhl)是目標(biāo)點(xi)到聚類中心點(vhl)的歐氏距離。

基于證據(jù)積累模型,該文提出一個相似度計算方法,用來將相似度高的一些對象預(yù)先劃分為簇,隨后將剩余的相似度較低等異常點進行歸并處理。

(2)

相似度量方法如公式(2)所示,其中,

部分對象的基聚類結(jié)果如圖1所示。

π1π2π3π4π5π6x1111111x2222232x3111111x4111113x5222222x6221222x7333323x8232321

圖1中,x1～x8是數(shù)據(jù)集中的8個對象,π1～π6是6次基聚類結(jié)果,表中元素代表x屬于第幾類。以圖1中的對象為例,通過公式(2)計算相似度得知x1與x3的相似度為1,x1與x4相似度為5/6,因此S1={x1,x3,x4}將3個對象劃分為1個簇;同理S2={x2,x5,x6},x7,x82個對象與其他對象間相似度較小,因此暫設(shè)為異常點S3={x7},S4={x8}。該過程每個對象只經(jīng)過1次運算,其時間復(fù)雜度為O(N)。使用數(shù)據(jù)集(S)設(shè)置得到以下相似矩陣,如圖2所示。

2）激勵機制缺乏。雖然我國已對綠色建筑提出了各類政策，但建設(shè)單位對綠色建筑的落實的積極性不高，難以推動綠色建筑的發(fā)展。例如，政府雖然制定了鼓勵綠色建筑發(fā)展的各項策略，但是由于成本及運營維護等方面的經(jīng)濟與技術(shù)問題的制約，導(dǎo)致其激勵作用難以發(fā)揮，使建設(shè)單位及施工方的積極性不高[2]。

S1S2S3S4S111/271/181/9S211/97/18S311/2S41

簇間相似度計算如公式(3)所示,其中p,q為簇(S)中對象的個數(shù)。

(3)

其中,

接著以圖1為例,S1={x1,x3,x4},S4={x8}。x1和x8在π6同屬一類,x3和x8在π6同屬一類,所以按公式(3)所得,S1和S4的相似度為2/(1×3×6)=1/9,其余相似度同理可得。該過程的時間復(fù)雜度為O(pqTN),qpT

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

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

該方法在8個數(shù)據(jù)集上進行了測試,其中4個是合成的數(shù)據(jù)集,4個是真實的數(shù)據(jù)集,合成數(shù)據(jù)集可從https://github.com/deric/clustering下載,真實數(shù)據(jù)集為UCI,其下載地址也在下方給出(http://www.ics.uci.edu/mlearn/MLRepository.html)。這8個數(shù)據(jù)集的詳細(xì)說明如表2所示:數(shù)據(jù)對象數(shù)(N)、維度數(shù)(D)、集群數(shù)(K)。

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

3.2 評價標(biāo)準(zhǔn)

采用CA和NMI來衡量聚類結(jié)果與真實數(shù)據(jù)分區(qū)之間的相似性。

(4)

CA是通過計算錯誤率來衡量聚類結(jié)果的另一個外部標(biāo)準(zhǔn)。

(5)

3.3 對比實驗

為了正確檢驗所提算法的性能,將其與以下幾種經(jīng)典的聚類集成算法進行了比較。這些比較算法的代碼是開放的和可訪問的。選擇了基于鏈接的相似性方法和基于圖的集成方法。

基于鏈路的相似性方法:由Iam On等人提出的[15]加權(quán)鏈接三元組(WCT),加權(quán)三重質(zhì)量(WTQ),組合相似性度量(CSM)。

表3和表4分別展示了不同算法在8個數(shù)據(jù)集上的CA和NMI結(jié)果,每列最好的結(jié)果進行了加粗顯示。

表3 不同方法在8個不同數(shù)據(jù)集的CA結(jié)果

表4 不同方法在8個不同數(shù)據(jù)集的NMI結(jié)果

3.4 時間效率分析

在這部分,將分析文中算法與對比算法的時間效率。選用KDD-CUP’99數(shù)據(jù)集進行本次時間效率分析,該數(shù)據(jù)集共有500萬條數(shù)據(jù),41個特征,從中選取了一部分進行時間效率分析實驗。選用基于鏈接的聚類集成算法(WCT)、基于圖的聚類集成算法(CSPA)與CSCE進行比較,參數(shù)設(shè)置與對比實驗部分相同。不斷增加數(shù)據(jù)集,記錄不同算法的運行時間,結(jié)果如圖3所示。其中X軸為對象數(shù)量,Y軸為運行時間(s)。從實驗結(jié)果可以看出,與其他算法相比,文中算法非常有效。這表明CSCE在對大規(guī)模數(shù)據(jù)集進行聚類時有很好的效果。

圖3 不同算法的時間比較

4 結(jié)束語

該文提出了一種基于簇間相似性的聚類集成方法。首先,通過計算樣本相似性暫時劃分為多個小簇,然后,計算對象集之間的相似性并形成對象集的相似矩陣,最后,通過NCUT切圖的方法得到最終聚類劃分。該方法形成的相似矩陣對比傳統(tǒng)的共協(xié)矩陣,有效地縮減了空間復(fù)雜度,提升了聚類的性能,并能夠快速得到最終聚類結(jié)果。