谷鵬花， 楊 燕， 王紅軍

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

0 引 言

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

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

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

雖然目前有很多的聚類算法，但是并沒有一個萬能的方法可以對任何數(shù)據(jù)集都適用［3－4］，其主要原因是對數(shù)據(jù)的形狀、密度及分布狀況等［5－7］不了解。若數(shù)據(jù)集的維數(shù)較高就更難了解，有些不相關(guān)的特征會導致類的結(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｝，聚類簇數(shù)為3，現(xiàn)已經(jīng)產(chǎn)生了3個聚類成員ε（1）、ε（2）、ε（3），見表1所列。3個聚類成員用超圖表示的結(jié)果見表2所列。

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

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

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

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

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

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

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

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

圖2 類提取結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 聚類成員類提取流程

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

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

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

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

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

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

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

4 結(jié)束語

本文提出一種基于數(shù)據(jù)關(guān)聯(lián)的聚類集成方法，該算法主要先提取出每個聚類成員的聚類結(jié)果，組成一個矩陣；然后對矩陣進行處理，提取出同屬一類的閾值的數(shù)據(jù)對象組成新的類；對這些結(jié)果再次聚類得到最終的集成結(jié)果。算法在人工和UCI數(shù)據(jù)集上進行實驗，取得了較好的結(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］.計算機科學，2010，37（11）：234－238.

［3］李玲玲，方 帥，辛 浩.改進的基于層次聚類的模糊聚類算法［J］.合肥工業(yè)大學學報：自然科學版，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.