一种基于数据关联的聚类集成方法

谷鹏花， 杨 燕， 王红军

（西南交通大学 信息科学与技术学院，四川 成都 610031）

0 引 言

集成学习，尤其是选择性集成学习已成为统计机器学习研究的一个热门主题［1］。目前，关于聚类集成技术的研究主要是集中在以下2个方面［2］：

（1）产生更高质量的聚类成员使得组成的聚类集体集成后能得到更有效的结果。

（2）设计聚类集体集成算法，使得能得到更统一更准确的结果。

虽然目前有很多的聚类算法，但是并没有一个万能的方法可以对任何数据集都适用［3－4］，其主要原因是对数据的形状、密度及分布状况等［5－7］不了解。若数据集的维数较高就更难了解，有些不相关的特征会导致类的结构愈发模糊［8］。因此，研究者提出了聚类集成这一思想，目前，已有许多关于聚类集成算法的研究。现有的聚类集成算法大致可分为以下5类：① 基于互联合矩阵的方法；② 基于互信息理论的方法；③ 基于超图的方法；④ 基于有限混合模型的方法；⑤ 基于投票的方法。本文提出了一种基于数据关联的聚类集成算法（Clustering Ensemble Based Data Relevant，简称CEBDR）。

1 算法的基本思想

假设有一数据集 X＝｛x1，x2，x3，x4，x5，x6，x7｝，聚类簇数为3，现已经产生了3个聚类成员ε（1）、ε（2）、ε（3），见表1所列。3个聚类成员用超图表示的结果见表2所列。

表1 聚类成员ε（1）、ε（2）、ε（3）

表2 聚类成员超图表示结果

表2中，H（1）、H（2）、H（3）分别 为表 1 中ε（1）、ε（2）、ε（3）的超图表示结果，每个H 包含3个h是因为数据集被分成了3类，1表示数据对象在该成员中属于同一类，0表示不属于同一类。

表2的结果示意图如图1所示，图1中，以区间的右坐标作为代表，如区间（0，1），则表示第1个数据对象x1；区间（1，2），则表示第1个数据对象x2；标有相同颜色表示这些成员在同一个聚类成员中是属于同一类的。

图1 聚类成员结果图

由于表1中的结果是未经过统一类标签的，经过标签对应转换后的聚类成员结果见表3所列。

表3 统一类标签后的ε（1）、ε（2）、ε（3）

根据图1提取在3个聚类成员中都属于同一类的对象｛1，？，1，2，？，3，2｝，则可分得3类：｛x1，x3｝、｛x4，x7｝、｛x6｝，其中x2，x5为不确定类对象，其类提取出的结果如图2所示。

图2 类提取结果

提取出3类后，对于剩下的x2、x5再根据最短距离法判断它们离哪个类最近再做出决断。另一个例子见表4所列。

表4 聚类成员λ（1）、λ（2）、λ（3）

从表4可以看出，｛x1，x2，x3｝、｛x6，x7，x8｝、｛x11，x12，x13｝在所有成员中均属于同一类，而x4，x5，x9，x10，x14，x15数据点在3个聚类成员中并没有明确其所属类，且分布在每个类中的概率相等，为1／3，则在给这些数据点分配类时均是随机的，而从表4可以看出，x4与x5、x9与x10、x14与x15总是属于同一类的，若随机分配，将它们拆开的可能性较大。

本文采用的方法是将全部同类的提取出后，再提出剩下同类组成新的类，最后通过再次聚类将这些类聚成3类。

当真实的聚类成员较多时，并不一定所有的聚类成员都同意将某2个或几个数据对象分为同一类，这时也可以设置一个阈值，即当成员中同意将它们分配在一起的意见超过了阈值，即可将它们归为一类。

2 基于数据关联的聚类集成算法

一个数据集 X＝｛x1，x2，…，xN｝，其中有 N个数据对象，每个数据对象有w维，要将这个数据集分成k类，根据产生不同聚类成员的方法进行多次聚类得到L个聚类成员，组成聚类集体Π＝｛π1，π2，…，πL｝，即

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

倘若其中的数据对象在所有的聚类成员中都同属一类或超过了某一个阈值，则提取出该类成员组成一个类。其判别方法为：

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

（2）式为判断2个数据对象被分为同一类的次数。判断在同一个聚类成员中第s个数据对象和第t个数据对象是否分在同一类，若是，则δ（πis，πit）＝1；否则δ（πis，πit）＝0。count是计算所有聚类成员中第s个数据对象和第t个数据对象分在同一类的次数。分在同一类概率的计算公式为：

其中，acount为计算第s个数据对象和第t个数据对象在所有成员中属于同一类的概率，acount∈［0，1］，如有设定阈值p，当acount≥p时，则判定它们聚为同一类。判断多个数据对象的方法也可依此类推。

当把所有的归为同类的数据对象提取出后，会剩下一些不确定的单个数据对象，可将它们单独作为一个类，以下为对这些类进行再次聚类的过程。

现假设提取出单个类 A＝｛a1，a2，…，ai，…，aH｝，其中ai＝｛xi1，xi2，…，xif，…，xim｝，i＝1，2，…，H，xif∈X。先计算每个类的中心点Cai，计算公式为：

根据上述方法求出所有类的中心CA＝｛Ca1，Ca2，…，CaH｝，然后计算两两中心的间距。

D（i，j）是一个对称矩阵，即dij＝dji，且当i＝j时，dij＝0，该对称矩阵为：

根据（5）式可用最短聚类法将所有类聚类成预打算聚类的簇数。

聚类成员类提取的流程如图3所示。

图3 聚类成员类提取流程

图3中，L为聚类成员个数；矩阵M 是用来存放L个聚类成员，矩阵X的每行是用来记录第f个成员不同类标签的下标，并且该矩阵是追加保存的，即第f＋1个成员是接着在X中记录的；矩阵Y为从X中提取出某个成员在X中记录的结果；矩阵H为矩阵Y与矩阵X中的成员结果求交集所得到的结果，全部循环后的矩阵H即为最终的类提出结果。

3 实验结果及分析

为了测试提出的新算法的效果，本实验采用的数据集见表5所列，其中前2个为人工数据集，其余的为UCI标准测试数据集。这些数据集的样本集大小、数据对象的维数、聚类的数目均大不相同。

表5 实验数据集

采用不同方法得到的结果如图4所示，有K－means基聚类的结果，有聚类集成Majority Vote和CSPA的结果以及本文中提出的新集成算法CEBDR的聚类结果。

图4 不同聚类方法的结果

从图4可看出，一般聚类集成的结果都要比单个聚类器的结果好，本文提出的新方法与其他算法相比，只有个别数据集F－measure值没有提高，但对于其他的数据集，新集成方法CEBDR的集成效果比其他的聚类集成方法有较大的提高。

4 结束语

本文提出一种基于数据关联的聚类集成方法，该算法主要先提取出每个聚类成员的聚类结果，组成一个矩阵；然后对矩阵进行处理，提取出同属一类的阈值的数据对象组成新的类；对这些结果再次聚类得到最终的集成结果。算法在人工和UCI数据集上进行实验，取得了较好的结果，证明了算法的有效性。

［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］罗会兰，危 辉.一种基于聚类集成技术的混合型数据聚类算法 ［J］.计算机科学，2010，37（11）：234－238.

［3］李玲玲，方 帅，辛 浩.改进的基于层次聚类的模糊聚类算法［J］.合肥工业大学学报：自然科学版，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.