一種基于數(shù)據(jù)關(guān)聯(lián)的聚類集成方法

谷鵬花， 楊 燕， 王紅軍

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031）

0 引 言

集成學(xué)習(xí)，尤其是選擇性集成學(xué)習(xí)已成為統(tǒng)計(jì)機(jī)器學(xué)習(xí)研究的一個(gè)熱門主題［1］。目前，關(guān)于聚類集成技術(shù)的研究主要是集中在以下2個(gè)方面［2］：

（1）產(chǎn)生更高質(zhì)量的聚類成員使得組成的聚類集體集成后能得到更有效的結(jié)果。

（2）設(shè)計(jì)聚類集體集成算法，使得能得到更統(tǒng)一更準(zhǔn)確的結(jié)果。

雖然目前有很多的聚類算法，但是并沒有一個(gè)萬能的方法可以對任何數(shù)據(jù)集都適用［3－4］，其主要原因是對數(shù)據(jù)的形狀、密度及分布狀況等［5－7］不了解。若數(shù)據(jù)集的維數(shù)較高就更難了解，有些不相關(guān)的特征會導(dǎo)致類的結(jié)構(gòu)愈發(fā)模糊［8］。因此，研究者提出了聚類集成這一思想，目前，已有許多關(guān)于聚類集成算法的研究?，F(xiàn)有的聚類集成算法大致可分為以下5類：① 基于互聯(lián)合矩陣的方法；② 基于互信息理論的方法；③ 基于超圖的方法；④ 基于有限混合模型的方法；⑤ 基于投票的方法。本文提出了一種基于數(shù)據(jù)關(guān)聯(lián)的聚類集成算法（Clustering Ensemble Based Data Relevant，簡稱CEBDR）。

1 算法的基本思想

假設(shè)有一數(shù)據(jù)集 X＝｛x1，x2，x3，x4，x5，x6，x7｝，聚類簇?cái)?shù)為3，現(xiàn)已經(jīng)產(chǎn)生了3個(gè)聚類成員ε（1）、ε（2）、ε（3），見表1所列。3個(gè)聚類成員用超圖表示的結(jié)果見表2所列。

表1 聚類成員ε（1）、ε（2）、ε（3）

表2 聚類成員超圖表示結(jié)果

表2中，H（1）、H（2）、H（3）分別 為表 1 中ε（1）、ε（2）、ε（3）的超圖表示結(jié)果，每個(gè)H 包含3個(gè)h是因?yàn)閿?shù)據(jù)集被分成了3類，1表示數(shù)據(jù)對象在該成員中屬于同一類，0表示不屬于同一類。

表2的結(jié)果示意圖如圖1所示，圖1中，以區(qū)間的右坐標(biāo)作為代表，如區(qū)間（0，1），則表示第1個(gè)數(shù)據(jù)對象x1；區(qū)間（1，2），則表示第1個(gè)數(shù)據(jù)對象x2；標(biāo)有相同顏色表示這些成員在同一個(gè)聚類成員中是屬于同一類的。

圖1 聚類成員結(jié)果圖

由于表1中的結(jié)果是未經(jīng)過統(tǒng)一類標(biāo)簽的，經(jīng)過標(biāo)簽對應(yīng)轉(zhuǎn)換后的聚類成員結(jié)果見表3所列。

表3 統(tǒng)一類標(biāo)簽后的ε（1）、ε（2）、ε（3）

根據(jù)圖1提取在3個(gè)聚類成員中都屬于同一類的對象｛1，？，1，2，？，3，2｝，則可分得3類：｛x1，x3｝、｛x4，x7｝、｛x6｝，其中x2，x5為不確定類對象，其類提取出的結(jié)果如圖2所示。

圖2 類提取結(jié)果

提取出3類后，對于剩下的x2、x5再根據(jù)最短距離法判斷它們離哪個(gè)類最近再做出決斷。另一個(gè)例子見表4所列。

表4 聚類成員λ（1）、λ（2）、λ（3）

從表4可以看出，｛x1，x2，x3｝、｛x6，x7，x8｝、｛x11，x12，x13｝在所有成員中均屬于同一類，而x4，x5，x9，x10，x14，x15數(shù)據(jù)點(diǎn)在3個(gè)聚類成員中并沒有明確其所屬類，且分布在每個(gè)類中的概率相等，為1／3，則在給這些數(shù)據(jù)點(diǎn)分配類時(shí)均是隨機(jī)的，而從表4可以看出，x4與x5、x9與x10、x14與x15總是屬于同一類的，若隨機(jī)分配，將它們拆開的可能性較大。

本文采用的方法是將全部同類的提取出后，再提出剩下同類組成新的類，最后通過再次聚類將這些類聚成3類。

當(dāng)真實(shí)的聚類成員較多時(shí)，并不一定所有的聚類成員都同意將某2個(gè)或幾個(gè)數(shù)據(jù)對象分為同一類，這時(shí)也可以設(shè)置一個(gè)閾值，即當(dāng)成員中同意將它們分配在一起的意見超過了閾值，即可將它們歸為一類。

2 基于數(shù)據(jù)關(guān)聯(lián)的聚類集成算法

一個(gè)數(shù)據(jù)集 X＝｛x1，x2，…，xN｝，其中有 N個(gè)數(shù)據(jù)對象，每個(gè)數(shù)據(jù)對象有w維，要將這個(gè)數(shù)據(jù)集分成k類，根據(jù)產(chǎn)生不同聚類成員的方法進(jìn)行多次聚類得到L個(gè)聚類成員，組成聚類集體Π＝｛π1，π2，…，πL｝，即

其中，πij∈｛1，2，…，k｝。

倘若其中的數(shù)據(jù)對象在所有的聚類成員中都同屬一類或超過了某一個(gè)閾值，則提取出該類成員組成一個(gè)類。其判別方法為：

其中，s∈｛1，2，…，N｝，t∈｛1，2，…，N｝，且s≠t。

（2）式為判斷2個(gè)數(shù)據(jù)對象被分為同一類的次數(shù)。判斷在同一個(gè)聚類成員中第s個(gè)數(shù)據(jù)對象和第t個(gè)數(shù)據(jù)對象是否分在同一類，若是，則δ（πis，πit）＝1；否則δ（πis，πit）＝0。count是計(jì)算所有聚類成員中第s個(gè)數(shù)據(jù)對象和第t個(gè)數(shù)據(jù)對象分在同一類的次數(shù)。分在同一類概率的計(jì)算公式為：

其中，acount為計(jì)算第s個(gè)數(shù)據(jù)對象和第t個(gè)數(shù)據(jù)對象在所有成員中屬于同一類的概率，acount∈［0，1］，如有設(shè)定閾值p，當(dāng)acount≥p時(shí)，則判定它們聚為同一類。判斷多個(gè)數(shù)據(jù)對象的方法也可依此類推。

當(dāng)把所有的歸為同類的數(shù)據(jù)對象提取出后，會剩下一些不確定的單個(gè)數(shù)據(jù)對象，可將它們單獨(dú)作為一個(gè)類，以下為對這些類進(jìn)行再次聚類的過程。

現(xiàn)假設(shè)提取出單個(gè)類 A＝｛a1，a2，…，ai，…，aH｝，其中ai＝｛xi1，xi2，…，xif，…，xim｝，i＝1，2，…，H，xif∈X。先計(jì)算每個(gè)類的中心點(diǎn)Cai，計(jì)算公式為：

根據(jù)上述方法求出所有類的中心CA＝｛Ca1，Ca2，…，CaH｝，然后計(jì)算兩兩中心的間距。

D（i，j）是一個(gè)對稱矩陣，即dij＝dji，且當(dāng)i＝j(luò)時(shí)，dij＝0，該對稱矩陣為：

根據(jù)（5）式可用最短聚類法將所有類聚類成預(yù)打算聚類的簇?cái)?shù)。

聚類成員類提取的流程如圖3所示。

圖3 聚類成員類提取流程

圖3中，L為聚類成員個(gè)數(shù)；矩陣M 是用來存放L個(gè)聚類成員，矩陣X的每行是用來記錄第f個(gè)成員不同類標(biāo)簽的下標(biāo)，并且該矩陣是追加保存的，即第f＋1個(gè)成員是接著在X中記錄的；矩陣Y為從X中提取出某個(gè)成員在X中記錄的結(jié)果；矩陣H為矩陣Y與矩陣X中的成員結(jié)果求交集所得到的結(jié)果，全部循環(huán)后的矩陣H即為最終的類提出結(jié)果。

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

為了測試提出的新算法的效果，本實(shí)驗(yàn)采用的數(shù)據(jù)集見表5所列，其中前2個(gè)為人工數(shù)據(jù)集，其余的為UCI標(biāo)準(zhǔn)測試數(shù)據(jù)集。這些數(shù)據(jù)集的樣本集大小、數(shù)據(jù)對象的維數(shù)、聚類的數(shù)目均大不相同。

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

采用不同方法得到的結(jié)果如圖4所示，有K－means基聚類的結(jié)果，有聚類集成Majority Vote和CSPA的結(jié)果以及本文中提出的新集成算法CEBDR的聚類結(jié)果。

圖4 不同聚類方法的結(jié)果

從圖4可看出，一般聚類集成的結(jié)果都要比單個(gè)聚類器的結(jié)果好，本文提出的新方法與其他算法相比，只有個(gè)別數(shù)據(jù)集F－measure值沒有提高，但對于其他的數(shù)據(jù)集，新集成方法CEBDR的集成效果比其他的聚類集成方法有較大的提高。

4 結(jié)束語

本文提出一種基于數(shù)據(jù)關(guān)聯(lián)的聚類集成方法，該算法主要先提取出每個(gè)聚類成員的聚類結(jié)果，組成一個(gè)矩陣；然后對矩陣進(jìn)行處理，提取出同屬一類的閾值的數(shù)據(jù)對象組成新的類；對這些結(jié)果再次聚類得到最終的集成結(jié)果。算法在人工和UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，取得了較好的結(jié)果，證明了算法的有效性。

［1］Kuncheva L I，Hadjitodorov S T.Using diversity in cluster ensembles［C］／／Proceedings of the IEEE International Conference on Systems， Man and Cybernetics，2004：1214－1219.

［2］羅會蘭，危 輝.一種基于聚類集成技術(shù)的混合型數(shù)據(jù)聚類算法 ［J］.計(jì)算機(jī)科學(xué)，2010，37（11）：234－238.

［3］李玲玲，方 帥，辛 浩.改進(jìn)的基于層次聚類的模糊聚類算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（6）：859－862.

［4］Al－Shaqsi J，Wang Wenjia.A clustering ensemble method for clustering mixed data［C］／／Proceedings of the International Joint Conference on Neural Networks（IJCNN），2012：1－8.

［5］Topchy A，Jain A K，Punch W F.Clustering ensembles：models of consensus and weak partitions［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（12）：1866－1881.

［6］Al－Razgan M，Domeniconi C.Weighted clustering ensembles［C］／／Proceedings of the SIAM International Conference on Data Mining，2007：258－269.

［7］Li Kai，Han Yanxia.Study of selective ensemble learning method and its diversity based on decision tree and neural network［C］／／Control and Decision Conference（CCDC），2010Chinese，2010：1310－1315.

［8］Gullo F，Domeniconi C，Tagarelli A.Projective clustering ensembles［C］／／Proceedings of the Ninth IEEE International Conference on Data Mining，2009：794－799.