聚类集成算法中度量方法

展金梅 陈君涛

（1.琼台师范学院 海南省海口市 571127）

（2.海南经贸职业技术学院 海南省海口市 571127）

现代信息技术快速发展的新形势背景环境下，如何在复杂多变的数据中搜索具有有价值意义的信息，成为了研究学者们较为关切的研究内容。聚类集成算法能够适用于不同的行业，帮助客户细分应用场景，不仅弥补了传统客户细分技术的不足，还更科学合理的划分客户。聚类集成算法可以将多个聚类成员以科学合理的方式进行划分，确保了结果的稳定性和准确率。

1 聚类集成的概况

1.1 聚类定义及方法

聚类是在不知道分类的情况下，将数据模式、特征向量，与其他数据样本，根据某种相似性度量标准分成不同的分组，确保同一组中的成员相似，实现不同组成员的差异性最大化。聚类的目标就是从无类标签数据组合的群集中找寻内在结构。通常一个好的聚类算法可以产生高质量的聚类，其中聚类内部的相似度最大，而聚类间的相似度则最低。

从统计学分析，聚类运用数据建模的方法，使数据变得更简单。

当前越来越多的聚类方法被开发和利用，我们从不同角度对各种分类系统进行定义。例如，从不同的假设方法、不同数据类型的算法等角度。关于聚类方法我们主要分为五个方法：

（1）基于分区的聚类方法。遵循优化一个目标划分的准则，将D分成K个分区，其中K-均值聚类是最特殊的分区划分方法；

（2）基于分层的聚类方法，这种方法是在D的不同粒度级别上，通过建立一个层级聚类或者在指定粒度级别上设置层次阈值，从而获得一个特定的聚类。

（3）基于密度的聚类方法。指的是在D上构建聚类采集密度的概念，低密度区域分割后的聚类就是高密度样本区域，基于密度的聚类方法最具有代表性的就是DBSCAN。

（4）基于网格的聚类方法，是指在多分辨率的网格数据结构下，将D量化成若干个有限的单元格，构建成一个网格结构，其中最典型的基于网格的聚类方法是STING。

（5）基于模型的聚类方法，这种方法假设用一个数字模型表示D的特性，实现聚类优化数据与基本模型之间的契合度，高斯混合模型聚类（GMM）是模型聚类方法的典型代表[1]。

1.2 聚类集成定义

聚类集成最早在2002年提出，通过运行基聚类算法划分数据集，而后经过组合方法对数据进行划分。聚类集成是运用若干个基聚类结果，以探索出一个新型数据划分模式来共享信息。其算术描述如下：

例如，假设给定N个数据模式的一个集合，O={O1,O2,O3,…ON}，聚类运行H次后获得H个划分结合，第h个划分结果表示为其中πh(O1)的第h个划分中，第i个模式的类标签号。

相比单个的聚类算法，聚类集成的优势主要表现为四个方面：

（1）稳健性，可以针对不同的领域和不同的数据集，相比性能来说聚类集成更具有优势。

（2）聚类集成的新颖性，凡是单聚类算法无法得到的结果聚类集成算法都可以探索得到结果。

（3）与单个聚类算法相比，聚类集成算法融合不同算法在处理噪声、孤立点及样本差异时，更具稳定性和可信估计，可以通过集成的分布情况评估聚类的不确定性。

（4）聚类集成算法通过将多个数据子集并行聚类，而获得组合结果，将不同数据源的数据融合在一起，具有并行性和规模性的优势。

此外，聚类集成算法还可以保护隐私，对单个构造器达到知识重用的效果[2]。

1.3 聚类集成算法的构成

聚类集成算法主要包括三部分，分别是基聚类器的生成、共识函数、聚类结果的质量评估构成。

（1）基聚类器的生成，指的是通过实验验证，采用误差不同的基聚类器构建的聚类集成算法最为有效，如果采用完全一致或者相似的基聚类器所得到的结果，将无法改善所构建的聚类集成算法的性能。关于基聚类器的生成方法主要包括同构集成方法、K均值聚类方法、数据子空间采样方法和异构集成方法等。

（2）共识函数的应用，当基聚类器获得以后就可以应用各种共识函数，对基聚类器的结果重新整合，进而获得最终的聚类结果。关于共识函数一般分为成对相似性、基于图、基于特征及投票等共识函数种类。

（3）聚类集成结果质量的评估，可以使用不同类型的有效性测量表对结果质量进行评估，一般按照内部评估指标和外部评估指标两个指标对结果进行评估。其中内部评估指标包括：Compactness，Davies-Bouldin与Dunn，外部评估指标包括RI，AR、标准化交互信息（NMI）。

2 聚类集成的分类

聚类集成算法的分类主要分为五种，每种分类算法各有特点。

2.1 基于相似的聚类集成算法

基于相似的聚类集成算法是将基聚类学习器组织成一个共识相似矩阵Mmxm，在并在这个基础上生成最终的聚类集成结果。基于相似度聚类集成算法又分为Crisp聚类集成算法和软聚类集成算法，不过这一类算法的效率是其最大的缺点。因此，它只用于处理中小型规模的问题，一旦遇到大规模数据处理就存在一定的难度[3]。

2.2 基于图的聚类集成算法

基于图的聚类集成算法，这一算法是通过构图整合基聚类器所传递的聚类信息，然后通过执行图的图划分，鉴定集成聚类。基于图的聚类集成算法对生成聚类集成算法的图划分过于依赖，划分聚类由于是图划分过程中的副产品，由此极容易影响聚类集成的结果。当内在数据聚类高度不平衡的情况下，那么最终聚类集成算法将会变得不适用。

2.3 基于重新标记的聚类集成算法

通过对齐或者重新标记所有基聚类器的聚类标签，表现整个基聚类器中相似性的聚类，根据对齐标签推导出最后的聚类集成算法。这一方法最大的缺点是当基聚类器之间没有合理的对应时，就不能够很好的工作[4]。

2.4 基于变换的聚类集成算法

通过将各个实例表示成r元组，其中r是基聚类器的数量，第q个元素表明其聚类被分配给第q个聚类器，并在转换以后的r元组上进行聚类分析。这一方法的缺点是，变换后的数据无法对原始数据中的信息进行完整的编码，从而无法保证所得到的集成聚类结果与原始基聚类器上的结果具有相似性。

2.5 基于连接的聚类集成算法

基于连接的聚类集成算法的提出，是为了提高标准相似方法的性能，基于链接的相似性测量准则，完善数据点之间的相似性值。基于连接的聚类集成算法使用K-mean算法生成同构的基聚类器，并将各个聚类中心随机进行初始化[5]。

3 聚类集成算法中度量方法

聚类集成算法中的相似性可以用数据之间的相似度或者相异度来描述。

3.1 聚类集成算法中的相似性度量方法

一般相似系数与距离相反，相似系数越大，那么对象间的相似性也就越大。一般在传统的聚类分析中，将对象中每个属性在聚类过程中的贡献当作是相同的。

3.2 聚类集成算法中的差异性度量方法

假设每个对象有M个属性，可以将一个对象视作M维空间的一个点，那么对两个M维的数据对象Xi=(xi1，xi2，…，xim)和Xj=(xj1，xj2，…，xjm)，通常采用欧式距离公式是较为常用的差异性度量方法。

在聚类集成算法中欧式距离公式是较为常用的距离度量方法，而K-means则是一种简单且较容易实现的聚类算法。

4 聚类集成算法中度量方法的分析研究

4.1 聚类集体差异性与聚类集成准确度之间的关系

为直观的表现聚类集成差异性与聚类集成准确度之间存在的关系，主要通过模拟生成聚类集体的方法，生成一个30大小的一维矢量，来表现数据规模为30的真实聚类，以10个数据点为一簇。例如，采用10个1、10个2、10个3，将真实的聚类以[1，1，…，1，2，…，2，3，…，3…]来表示，并在此基础上随机改变30x（1-P)个点的簇标签，以此模拟准确度的P聚类。如果将第一个点的簇标签改为2，那么聚类生成为[2，1，…，1，2…，2，3，…，3]。只要采用这个方法，我们就能构成300个大小为3、平均准确度为0.6的聚类集体，聚类集体差异性度量值的计算通常使用CSPA算法。

在计算聚类集体差异性度量值之所以运用CSPA算法，那是因为在以往的聚类集成对比实验研究中，这一算法有着较为稳定性的性能，且准确度比较高的优势。

4.2 不同平均聚类成员准确度情况下，集体差异性度量与集成准确度之间的关系

我们通过运用试验方法产生的平均成员准确度的方法，验证集体差异性度量与集成性能之间的关系是否收到平均成员准确度的影响。例如，我们将每个准确度生成30个大小为3的集体，通过计算着30个集体产生的差异性，判断与CSPA集成准确度之间的关系，并对此过程重复20次，从而得出相关系数的平均值。实验最后得出的结论指出，随着聚类成员平均准确度的不断增加，集体差异性度量与集成性能之间系数的绝对值，也随之不断增加。一般各种差异性度量与集成性能之间的相关性在成员聚类准确度≤0.6时会很低。当平均成员的准确度>0.6时，差异性度量与集成性能之间的关系属于正相关。

4.3 不同集体大小情况下，各种差异性度量与CSPA集成准确度的相关性研究

为探索和研究聚类集成大小是否影响到差异性度量与集成准确度之间的关系，我们通过实验计算：在不同的聚类集体大小情况下，平均成员的准确度P=0.65的集体30个，在不同集体大小情况下，分析和计算集体的差异性与集成准确度的相关系数。实验表示，差异性与集成准确度之间的关系确实受到集体大小的影响，在集体大小不断增大的情况下，平均CSPA集成准确度虽然增加，但是差异性度量与集成性能之间的相关性却不一定会增加。一般当集体大小在15-20时，差异性度量与集成性能之间呈现出最强的相关性[6]。

5 结论

综上可见，运用聚类集成算法对在信息数据海量化背景下，提高了搜索信息的高效性和准确性。对此，本文分析聚类集成的概况，具体介绍聚类集成算法的分类，详细分析和研究了聚类集成算法中的度量算法，以便充分利用聚类集成算法的优势，洞察和分析数据的内在本质特点，为数据预处理和挖掘有价值的数据信息提供卓越、有效的探索工具。