基于簇间连接的元聚类集成算法

doi:10.13232/j.cnki.jnju.2023.06.006

基于簇间连接的元聚类集成算法

杜淑颖¹^,², 丁世飞^,¹, 邵长龙¹

1.中国矿业大学计算机科学与技术学院，徐州，221116

2.徐州生物工程职业技术学院信息管理学院，徐州，221000

Link based meta⁃clustering algorithm

Du Shuying¹^,², Ding Shifei^,¹, Shao Changlong¹

1.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, 221116, China

2.School of Information Management, Xuzhou Vocational College of Bioengineering, Xuzhou, 221000, China

通讯作者: E⁃mail：dingsf@cumt.edu.cn

收稿日期: 2023-10-27

基金资助:

国家自然科学基金. 62276265. 61976216
江苏高校“青蓝工程”，江苏省高等职业院校专业带头人高端研修资助项目. 2021GRFX074

Received: 2023-10-27

摘要

聚类集成已经成为数据挖掘和机器学习中的热门研究课题，尽管近年来取得了重大进展，但目前聚类集成的研究仍存在两个具有挑战性的问题.首先，大部分集成算法倾向于在对象的层面研究相似度，缺乏发掘簇层面信息的能力；其次，目前许多集成算法仅仅关注簇内对象的直接共现，忽略了簇与簇之间的关系.针对这两个问题，提出一种基于簇间连接的元聚类集成算法，首先根据Jaccard相似度构造一个簇相似度矩阵，然后利用连接三元组细化这个相似度矩阵，最后通过图划分和成员分配得到最后的结果.理论分析和实验测试表明，提出的算法不仅能产生较好的聚类结果，而且受聚类集成规模的影响较小.

关键词： 簇间相似性 ; 聚类集成 ; 聚类 ; 连接三元组 ; 元聚类

Abstract

Clustering ensemble has become a popular research topic in data mining and machine learning. Despite significant progress in recent years，there are still two challenging problems in current researches on clustering ensemble. Firstly，most ensemble algorithms tend to study similarity at the object level，lacking the ability to mine cluster⁃level information. Secondly，many current ensemble algorithms focus only on the direct co⁃occurrence of objects within clusters，ignoring the relationship between clusters. To address these two problems，this paper proposes a link based meta⁃clustering algorithm (L⁃MCLA) which constructs a cluster similarity matrix based on Jaccard similarity，then refines this similarity matrix using connecting triples，and finally obtains the final result through graph partitioning and membership assignment. Theoretical analysis and experimental testing show that the proposed algorithm not only produces good clustering results，but also is less affected by the scale of clustering ensemble.

Keywords： inter⁃cluster similarity ; clustering ensemble ; clustering ; connecting triples ; meta⁃clustering algorithm (MCLA)

PDF (595KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

杜淑颖, 丁世飞, 邵长龙. 基于簇间连接的元聚类集成算法. 南京大学学报（自然科学）[J], 2023, 59(6): 961-969 doi:10.13232/j.cnki.jnju.2023.06.006

Du Shuying, Ding Shifei, Shao Changlong. Link based meta⁃clustering algorithm. Journal of nanjing University[J], 2023, 59(6): 961-969 doi:10.13232/j.cnki.jnju.2023.06.006

聚类是数据挖掘领域中热门的研究课题之一，其研究目的是根据相似性的大小把数据分到不同的簇中，使簇内数据之间的相似性尽可能大，簇间数据之间的相似性尽可能小^［1］.目前聚类已被运用在各种领域，如图像处理^［2］、社区发现^［3］、数据挖掘等等^［4］.过去几十年中，人们开发了大量的聚类算法，比较具有代表性的有谱聚类^［5-6］、密度峰值聚类^［7-8］、自适应聚类等^［9-10］，每种聚类算法都有其自身的优点.但目前的聚类算法仍然存在一些问题，如聚类结果很大程度上取决于参数及其初始化、聚类结果不够稳健等.为了解决这些问题，研究者提出了聚类集成算法.

与通常使用单个算法生成单个聚类结果的传统做法不同，聚类集成是整合多个不同的聚类结果来生成更好更稳健聚类结果的过程.聚类集成算法的有效性使其越来越受到关注，许多相关算法被提出.这些算法可分为三大类，即基于共关联矩阵的算法、基于图分区的算法和基于中值聚类的算法.

基于共关联矩阵的算法根据数据点与数据点之间在相同簇中共现的频率得到一个共关联矩阵，以该矩阵作为相似度矩阵，采用层次聚类的算法得到最终结果.Fred and Jain^［11］首次提出共关联矩阵的概念，并据此设计了证据集聚聚类（Evidence Accumulate Clustering，EAC）算法.Wang et al^［12］对EAC算法进行扩展，考虑到簇的大小，提出概率集聚算法.Rathore et al^［13］利用随机投影对高维数据进行降维，并利用共关联矩阵设计了一种针对于模糊聚类的聚类集成算法.Zhong et al^［14］认为删除共关联矩阵值较小的项可以提高聚类效果，并猜想哪些项中可能包含大量噪声.

基于图分区的算法将聚类集成的信息构成一个图结构，再利用图分割算法将图分割成若干块，进而得到最终的聚类结果.Strehl and Ghosh^［15］将聚类成员里的每个簇都作为一个超边缘，构造了三种超图结构，再用METIS算法对其进行图分割，得到最终的聚类结果.Fern and Brodley^［16］将聚类成员构造成二部图，其中对象和簇都表示为图节点，只有当其中一个节点是对象，另一个节点是包含它的簇时，二部图的值才不为0，并用Ncut算法对其进行分割.Huang et al^［17］提出一种针对大规模数据的基于采样的谱聚类算法，并设计了一个二部图对其进行聚类集成.

基于中值聚类的算法将聚类集成问题建模成一个最优化问题，其优化目标是寻找一个与所有聚类成员最相似的聚类结果，这个聚类结果被视为所有聚类成员的中值点.这个问题已经被证明是一个NP难问题，所以在全局聚类空间里寻找最优解在较大的数据集上是不可行的.为此，Cristofor and Simovici^［18］利用遗传算法求聚类集成的近似解，其中聚类被视为染色体.Topchy et al^［19］将中值聚类问题转化为极大似然问题，并用EM （Expectation Maximization）算法求解.Huang et al^［20］将聚类集成问题转化为二元线性规划问题，通过因子图模型进行求解.

尽管取得了重大的进展，但目前的研究仍然存在两个挑战性问题：首先，目前的算法大多是在对象级别对集成信息进行研究，往往无法从簇的层面集成更多的信息；其次，多数聚类集成算法仅仅关注了聚类成员的直接连接，忽略了聚类成员的间接连接.

在聚类集成的过程中，对象间的直接共现是最容易捕捉的信息，Fred and Jain^［11］提出共关联矩阵的概念，用两个对象在同一簇中共现的次数作为它们的相似度.但是现实情况远比此更复杂，图1列出了几种可能出现的情况.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 点之间的关系：(a)在同一簇内；(b)分属两个有公共部分的簇内；(c)分属两个不相连的簇内，但这两个簇均与第三个簇有联系

Fig.1 The relationship between points：(a)within the same cluster，(b)belonging to two clusters with common parts，(c)belonging to two unrelated clusters，while both clusters are related to the third cluster

图1a中，两个对象在同一簇内，则这两个对象可以被认为是同一类.图1b中，两个对象分属于两个有公共部分的簇，可以用Jaccard系数计算两个簇之间的相似度，这两个对象也被认为有一定的可能性在同一类中.图1c中，两个对象分属于两个不相连的簇，但这两个簇均与第三个簇有联系，这种簇间间接相连的情况，很难度量这两个簇之间的相似性，也很难对这两个对象进行分类，这就需要对隐藏在簇间的间接关系进行发掘利用.针对这个问题，本文提出一种基于簇间连接的元聚类集成算法（Link⁃Based Meta⁃Clustering Algorithm，L⁃MCLA）.

1 相关工作

1.1　聚类集成

聚类集成是通过整合多个聚类结果来提高聚类效果的算法，通常可以表述如下.

给定一个具有n个数据对象的数据集 $X = \{x_{1}, x_{2}, \dots, x_{n}\}$ ，对此数据集X使用m次聚类算法，得到m个聚类结果 $P = \{p_{1}, p_{2}, \dots, p_{m}\}$ ，其中， $p_{i} (i = 1,2, \dots, m)$ 为第i个聚类算法得到的聚类结果，又被称为聚类成员或基聚类.具体地，聚类成员的生成有三种算法：

（1）使用一种聚类算法，每次运行时随机设置不同的参数并随机初始化.

（2）使用不同聚类算法产生不同的聚类成员.

（3）对数据集进行采样，得到不同的子集，再对子集进行聚类，得到不同的聚类成员.

每个聚类成员包含若干个簇，记作 $p_{i} = \{C_{i}^{1}, C_{i}^{2}, \dots, C_{i}^{j}\}$ ，其中，j是聚类成员p_i 里包含簇的个数.聚类集成就是对集合P通过一致性函数T进行合并，得到数据集X的最终聚类结果 $P^{*}$ .聚类集成的具体流程如图2所示.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 聚类集成流程示意图

Fig.2 The flowchart of clustering ensemble

1.2　元聚类

2003年，Strehl and Ghosh^［15］提出被称为“元聚类”（Meta⁃Clustering Algorithm，MCLA）的聚类集成算法，其中心思想是对簇进行分类，而不是对对象进行分类，最后，将对象分配到最有可能归属的簇群中.元聚类算法利用Jaccard系数计算簇间的相似度，假设有簇C_i 和C_j，它们之间的Jaccard系数的计算如下：

J (C_{i}, C_{j}) = \frac{|C_{i} ⋂ C_{j}|}{|C_{i} ⋃ C_{j}|}

(1)

其中， $||$ 代表集合中点的个数.

接着，元聚类算法对得到的相似度矩阵利用METIS图划分进行分类.METIS是一种多级的快速图分割技术，在元聚类算法里利用它将簇分成若干个簇群^［21］，每个簇群被称作元簇群（Meta⁃Cluster，MC）.最后，将对象分配到对应的元簇群，得到聚类结果.元聚类算法的四个步骤如下.

（1）构造相似度矩阵：将M个聚类成员包含的全部簇都当作矩阵节点，计算簇和簇之间的Jaccard系数作为矩阵的值，构造相似度矩阵.

（2）生成元图：将矩阵节点当作图节点，将矩阵的值当作图的边，将上一步的相似度矩阵看作一个无向图，称为元图（Meta⁃graph）.

（3）划分元图：使用METIS图划分算法对上一步的元图进行划分，得到K个元簇群，每个元簇群都包含若干簇.

（4）对象分配：将数据对象分配到对应的元簇群得到最终结果.具体地，基于投票法，将对象从属于元簇群中簇的次数与元簇群中簇的总个数的比看作对象从属于这个元簇群的可能性.对于一个对象，将它分配到可能性最大的元簇群中，进而得到最终结果.

Strehl and Ghosh^［15］用一系列实验证明了元聚类算法的优越性和鲁棒性，使其成为一个经典的聚类集成算法.

1.3　连接三元组

元聚类算法虽然优越，但仍有一个缺点，就是利用Jaccard相似度来构建的相似度矩阵仅仅能反映簇与簇之间的直接联系，无法进一步挖掘其中的间接关系.对于那些没有公共部分的簇，它们的相似度只能为0，忽略了它们之间的弱联系性.

2011年，Iam⁃On et al^［22］提出加权连接三元组（Weighted Connected⁃Triple，WCT）的概念来挖掘簇与簇之间隐藏的间接关系，其基本思想是：如果两个节点都与第三个节点有连接，则认为这两个节点之间也有一定的关系，第三个节点被称为这个三元组的中心.通过这种算法可以找到簇与簇之间的间接连接，进一步丰富原来的相似度矩阵包含的信息，进而得到更好的聚类结果.

连接三元组因为其较好的特性被运用在许多研究中.周林等^［23］将连接三元组运用在谱聚类中，提出一种基于谱聚类的聚类集成算法.张恒山等^［24］将其与群体智慧相结合，提出一种新的聚类集成算法.证明使用连接三元组可以有效地挖掘簇之间隐藏的信息，有利于提高聚类结果.

2 L⁃MCLA算法

2.1　构建相似性矩阵

本节利用连接三元组（如图3所示）来构建细化的簇相似性矩阵.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 连接三元组的示意图

Fig.3 The schematic diagram of connecting triples

如图3所示， $P_{1}, P_{2}, P_{3}$ 是三个基聚类，其中 $C_{1}^{1} 和 C_{2}^{1}$ 是 $P_{1}$ 中的簇， $C_{1}^{2}$ 是 $P_{2}$ 中的簇， $C_{1}^{3}$ 是 $P_{3}$ 中的簇. $C_{1}^{1} 和 C_{2}^{1}$ 不相关（即没有公共部分），传统聚类集成算法无法发现其中的关系.但 $C_{1}^{1} 和 C_{1}^{2}$ 有公共点 $x_{1}, C_{2}^{1} 和 C_{1}^{2}$ 有公共点 $x_{2}$ ，故 $C_{1}^{1} 和 C_{1}^{2}$ 相似， $C_{2}^{1} 和 C_{1}^{2}$ 相似， $C_{1}^{1} 和 C_{2}^{1}$ 都与第三方 $C_{1}^{2}$ 相似，由连通三元组理论可知 $C_{1}^{1} 和 C_{2}^{1}$ 也具有一定的相似度.同理， $C_{1}^{1} 和 C_{1}^{3}$ 有公共点 $x_{1}, C_{2}^{1} 和 C_{1}^{3}$ 有公共点 $x_{2}$ ，故 $C_{1}^{1} 和 C_{1}^{3}$ 相似， $C_{2}^{1} 和 C_{1}^{3}$ 相似，所以 $C_{1}^{1} 和 C_{2}^{1}$ 具有一定的相似度.可见，通过这种算法能发现簇之间更多的信息，有利于利用一致性函数进行聚类.

首先，用Jaccard系数计算簇与簇之间的相似度，如式（1）所示.

设 $C_{k} 与 C_{i} 和 C_{j}$ 都有相似度，则 $C_{i} 和 C_{j}$ 之间的连接三元组定义如下：

W C T_{i j}^{k} = m i n (J (C_{i}, C_{k}), J (C_{j}, C_{k}))

(2)

簇 $C_{i}, C_{j}$ 之间的相似度 $S i m^{W C T} (i, j)$ 计算如下：

S i m^{W C T} (i, j) = \frac{\sum_{C_{k} \in C} W C T_{i j}^{k}}{m a x (W C T)}

(3)

其中，C是簇的总集合.

对于簇集合C中任意的两个簇 $C_{i} 和 C_{j}$ ，它们之间的相似度可以定义为：

S i m (i, j) = \{\begin{matrix} 1, i = j \\ S i m^{W C T} (i, j) \times D C, 其他 \end{matrix}

(4)

其中，DC为衰减因子，即为两个不同事物的相似程度的置信水平.

通过式（4）可以构建一个信息更丰富的簇相似度矩阵，有利于后面得到更好的结果.

2.2　一致性函数

一致性函数包含图划分和对象分配两个步骤.首先，将优化后的相似度矩阵S视为邻接矩阵，构建一个无向图G，即：

G = \{V, L\}

(5)

其中， $V = C$ ，将全部的簇看作图像中的点. $L = S i m (i, j)$ ，将簇之间的相似度看作无向图的边，这样就构建了一个无向图.

然后，将这个无向图G通过图分区算法分为K个部分.在图分区算法的选择中，由于归一化割（Normalized Cut，Ncut）^［25］的优越特性，本研究选择它作为图分区算法.

通过Ncut可以得到K个元簇群，每个元簇群都由若干个簇构成.即：

M C = \{M C_{1}, M C_{2}, \dots, M C_{K}\}

(6)

接着，使用投票法将对象分配到对应的元簇群中.对于给定的一个对象 $x_{i}, x_{i}$ 可能属于 $M C_{j}$ 中的零个或多个簇，即可以用对象 $x_{i}$ 从属于 $M C_{j}$ 中簇的次数与 $M C_{j}$ 中簇的总个数的比来定义 $x_{i}$ 属于元簇群 $M C_{j}$ 的可能性.具体地：

\begin{array}{l} S c o r e (x_{i,} M C_{j}) = \frac{1}{|M C_{j}|} \sum_{C_{h} \in M C_{j}} l \\ l = \{\begin{matrix} 1, & i f x_{i} \in C_{h} \\ 0, & 其他 \end{matrix} \end{array}

(7)

其中， $|M C_{j}|$ 代表元簇群 $M C_{j}$ 中簇的个数.

对MC中的每个元簇群 $M C_{j}$ 求得一个分数，将点 $x_{i}$ 分配到得分最高的元簇群里，完成对象分配.

L⁃MCLA算法描述如下.

算法1 L⁃MCLA算法

输入：数据集X，聚类数目K

输出：最终聚类结果Label

Step 1.运用聚类算法生成m个聚类成员 $P = \{P_{1}, P_{2}, \dots, P_{m}\}$ .

Step 2.根据m个聚类成员得到簇集合C，用式（1）计算其中任意两个簇的Jaccard系数，得到由Jaccard系数构成的簇间相似度矩阵Z.

Step 3.根据Z运用式（2）~（4）得到精细的相似度矩阵WCTZ.

Step 4.运用式（5）将相似度矩阵WCTZ看作无向图，运用Ncut算法对其进行图分割，得到K个元簇群MC.

Step 5.运用式（7）将对象分配到对应的元簇群里，得到最终结果Label.

2.3　算法的复杂度分析

首先看时间复杂度.因为第一步生成聚类成员的时间复杂度与基聚类算法有关，在此不做分析.第二步生成相似度矩阵Z的时间复杂度为 $O (N_{C}^{2})$ ，其中， $N_{C}$ 为聚类成员包含的簇的总数.第三步用连接三元组对相似度矩阵Z进行细化，时间复杂度是 $O (m N_{C}^{2})$ ，其中，m为聚类成员的规模.第四步将相似度矩阵WCTZ看作一个无向图G，无向图G包含 $2 N_{C}$ 个节点，使用Ncut算法进行分割的时间复杂度是 $O (K {(2 N_{C})}^{3 / 2})$ ，其中，K是图分割的块数.第五步对对象进行分配，时间复杂度是 $O (K N N_{C})$ ，其中，N为对象个数.所以，本文算法的总的时间复杂度最大为：

O (N_{C}^{2}) + O (m N_{C}^{2}) + O (K {(2 N_{C})}^{3 / 2}) + O (K N N_{C})

生成相似度矩阵的空间复杂度为 $O (N_{C}^{2})$ ，这也是本文算法空间复杂度的主要来源，其余步骤所占空间远小于这个值.故可以认为本文算法的空间复杂度为 $O (N_{C}^{2})$ .

3 实验结果与分析

在多个实际数据集中与现有的聚类集成算法进行对比实验来验证本文算法的有效性，并通过对不同聚类成员规模的比较来证明本文算法的鲁棒性.

3.1　数据集和评价标准

使用UCI （University of California Irvine）机器学习数据库中的八个数据集为实验数据集进行对比实验.表1列出了数据集的详细信息.

表1 实验所用UCI数据集的属性

Table 1 Details of the UCI datasets used in experiment

数据集	样本数	特征数	类别数
Aggregation	788	2	7
Cardiotocography （CTG）	2126	21	10
Diabetes	768	8	2
Ecoli	336	8	8
Ionosphere	351	34	2
Soybean	47	35	4
Thyroid	215	5	3
Yeast	1484	8	10

新窗口打开| 下载CSV

选择ARI （Adjusted Rand Index）和NMI （Normalized Mutual Information）来评价聚类结果.

ARI通过计算样本点对位于同一类簇和不同类簇的数目来度量聚类结果之间的相似程度，计算如下：

A R I = \frac{2 (a d - b c)}{(a + b) (b + d) + (a + c) (c + d)}

(8)

其中，a表示在真实情况下和实验中都属于一个簇的点对数目，b表示在真实情况下是一个簇而在实验中不是一个簇的点对数目，c表示在真实情况下不是一个簇而在实验中是一个簇的点对数目，d表示在真实情况下和实验中都不属于同一个簇的点对数目.ARI的取值范围为 $[- 1,1]$ ，值越大表明和真实结果越吻合，即聚类效果更好.

NMI是常见的聚类有效性的外部评价指标，从信息论的角度评估两个聚类结果的相似性.设实验结果为X，真实结果为Y，NMI的计算如下：

N M I (X, Y) = \frac{I (X, Y)}{\sqrt[]{H (X) H (Y)}}

(9)

其中， $I (X, Y)$ 表示X和Y之间的互信息， $H (X)$ 和 $H (Y)$ 表示变量X和Y的熵.NMI的取值范围为 $[0,1]$ ，值越大表明和真实结果的共享信息越多，即聚类效果越好.

3.2　对比实验和实验设置

使用七种聚类集成算法与L⁃MCLA算法作对比：EAC （Evidence Accumulation Clustering）^［11］，HBGF （Hybird Bipartite Graph Formulation）^［16］，WEAC （Weighted Evidence Accumulation Clustering）^［26］，GP⁃MGLA（Graph Partitioning with Multi⁃Granularity Link Analysis）^［26］，CSPA （Cluster⁃Based Similarity Partitioning Algorithm）^［15］，HGPA （Hypergraph Partitioning Algorithm）^［15］，MCLA （Meta⁃Clustering Algorithm）^［15］

对比算法的选择，首先是本文改进的元聚类算法MCLA以及与其相关的CSPA，HGPA，还有聚类集成领域的经典算法EAC，HBGF以及近年来的新算法WEAC，GP⁃MGLA，这些对比算法使实验结果具有一定的说服力.对比算法的参数按文献给出的参考值进行设置.

实验环境：Windows 7 64位操作系统，英特尔i5 双核 1.7 GHz中央处理器，8 G内存，在MATLAB R2016a中实现.

实验中首先要生成包含m个聚类成员的聚类集合，使用k⁃means算法生成聚类成员，每个聚类成员的生成均采用随机初始化，并在 $[2, \sqrt[]{N}]$ 中随机选取k⁃means的聚类个数k.称聚类成员个数m为聚类集成规模，固定聚类集成规模 $m = 50$ ，分别将本文算法与其他聚类集成算法进行比较，再在不同聚类集成规模下测试本文算法的聚类表现.

3.3　聚类集成算法的对比实验

在每个数据集中每个聚类集成算法均运行20次，每次运行根据3.2随机生成聚类成员，得到聚类结果后计算ARI和NMI的均值及其标准差.实验结果如表2和表3所示，表中黑体字表示结果最优.

表2 不同算法的聚类结果的ARI比较

Table 2 ARI of clustering results by different algorithms

	EAC	HBGF	WEAC	GP⁃MGLA	CSPA	HGPA	MCLA	L⁃MCLA
Aggregation	0.8045(±0.0446）	0.8057(±0.0502)	0.8061(±0.0459)	0.8608(±0.0820)	0.5499(±0.0060)	0.6217(±0.0229)	0.6126(±0.0273)	0.9247(±0.0577)
CTG	0.1330(±0.0071)	0.1306(±0.0084)	0.1296(±0.0081)	0.1378(±0.0042)	0.1158(±0.0035)	0.1172(±0.0106)	0.1202(±0.0048)	0.1404(±0.0055)
Diabetes	0.0516(±0.0272)	0.0441(±0.0285)	0.0188(±0.0135)	0.0071(±0.0117)	-0.0003(±0.0001)	-0.0002(±0.0000)	-0.0003(±0.0002)	0.0609(±0.0323)
Ecoli	0.4958(±0.0699)	0.4164(±0.0154)	0.4681(±0.0594)	0.4719(±0.0491)	0.3004(±0.0134)	0.3338(±0.0265)	0.3678(±0.0306)	0.5422(±0.0533)
Ionosphere	0.1502(±0.0115)	0.1672(±0.0104)	0.1488(±0.0102)	0.1627(±0.0130)	0.1245(±0.0000)	0.0204(±0.0234)	0.1636(±0.0140)	0.1686(±0.0045)
Soybean	0.5519(±0.0065)	0.5479(±0.0058)	0.5534(±0.0099)	0.5473(±0.0045)	0.4836(±0.0292)	0.5433(±0.0134)	0.5526(±0.0082)	0.5679(±0.0290)
Thyroid	0.3704(±0.1824)	0.3783(±0.1781)	0.4974(±0.0533)	0.5584(±0.0310)	0.1292(±0.0372)	0.1041(±0.0257)	0.2714(±0.0706)	0.5874(±0.0363)
Yeast	0.1737(±0.0182)	0.1486(±0.0051)	0.1737(±0.0158)	0.1671(±0.0041)	0.1099(±0.0136)	0.0939(±0.0167)	0.1258(±0.0064)	0.1815(±0.0074)

新窗口打开| 下载CSV

表3 不同算法的聚类结果的NMI比较

Table 3 NMI of clustering results by different algorithms

	EAC	HBGF	WEAC	GP⁃MGLA	CSPA	HGPA	MCLA	L⁃MCLA
Aggregation	0.8686(±0.0273)	0.8675(±0.0314)	0.8689(±0.0277)	0.9002(±0.0478)	0.6886(±0.0082)	0.7484(±0.0140)	0.7463(±0.0151)	0.9315(±0.0379)
CTG	0.2671(±0.0078)	0.2730(±0.0110)	0.2648(±0.0081)	0.2745(±0.0067)	0.2449(±0.0054)	0.2461(±0.0133)	0.2539(±0.0054)	0.2742(±0.0062)
Diabetes	0.0185(±0.0104)	0.0178(±0.0120)	0.0073(±0.0044)	0.0032(±0.0042)	0.0007(±0.0000)	0.0008(±0.0000)	0.0007(±0.0002)	0.0247(±0.0133)
Ecoli	0.5792(±0.0270)	0.5373(±0.0126)	0.5684(±0.0252)	0.5678(±0.0257)	0.4422(±0.0100)	0.4659(±0.0245)	0.5049(±0.0209)	0.6082(±0.0214)
Ionosphere	0.1156(±0.0070)	0.1267(±0.0059)	0.1142(±0.0064)	0.1237(±0.0078)	0.1022(±0.0000)	0.0182(±0.0185)	0.1203(±0.0092)	0.1225(±0.0044)
Soybean	0.7141(±0.0033)	0.7122(±0.0029)	0.7149(±0.0050)	0.7119(±0.0023)	0.6197(±0.0230)	0.7064(±0.0172)	0.7145(±0.0041)	0.7210(±0.0104)
Thyroid	0.3168(±0.0751)	0.3257(±0.1041)	0.3695(±0.0264)	0.4117(±0.0362)	0.1645(±0.0229)	0.1534(±0.0118)	0.2135(±0.0312)	0.4839(±0.0355)
Yeast	0.2649(±0.0124)	0.2576(±0.0062)	0.2673(±0.0113)	0.2737(±0.0052)	0.2068(±0.0154)	0.1918(±0.0209)	0.2260(±0.0051)	0.2900(±0.0079)

新窗口打开| 下载CSV

由表2可见，L⁃MCLA算法在八个数据集上的聚类结果的ARI都是最高的.由表3可见，L⁃MCLA算法在六个数据集上聚类结果的NMI也都是最高的，仅仅在CTG和Ionosphere上略有逊色，不过数值相差不大.

通过以上实验可以证明，本文提出的算法在聚类集成上的优势，和其他的聚类集成算法相比，性能更优.

3.4　聚类集成规模对聚类结果的影响

研究不同的聚类集成规模对L⁃MCLA算法聚类结果的影响.在八个数据集上取不同数量的聚类成员进行集成.聚类成员规模为 $[10,100]$ ，以10递增.聚类成员的生成设置与3.2相同，取10次实验结果的平均值作为最终的结果.图4和图5显示了在不同聚类集成规模下L⁃MCLA算法的ARI和NMI的变化情况.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 当聚类集成规模不同时L⁃MCLA算法在八个数据集上的ARI

Fig.4 ARI of L⁃MCLA on eight datasets with different scales of the clustering ensemble

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 当聚类集成规模不同时L⁃MCLA算法在八个数据集上的NMI

Fig.5 NMI of L⁃MCLA on eight datasets with different scales of the clustering ensemble

图4展示了在聚类集成规模不同时，L⁃MCLA算法在八个数据集上聚类结果的ARI.由图可见，在大部分数据集上，L⁃MCLA算法的聚类结果仅有小幅波动，并在集成规模达到40以后逐渐趋于平稳，只在Thyroid数据集和Soybean数据集上存在不同.在Thyroid数据集上，L⁃MCLA算法的聚类结果的ARI在集成规模为10~20时急剧上升，随后，随着聚类成员的增加呈现一种波动上升的状态.在Soybean数据集上，随着基聚类的增多，L⁃MCLA算法的聚类结果的ARI缓慢下降，但幅度较小.

图5展示了在聚类集成规模不同时，L⁃MCLA算法在八个数据集上聚类结果的NMI.由图可见，除了Thyroid数据集外，L⁃MCLA算法的聚类结果在大部分数据集上的NMI均趋于平稳.在Thyroid数据集上，L⁃MCLA算法的聚类结果的NMI在基聚类为10~40时大幅上升，在40~50时略微下降，随后又上升且逐渐平稳.

通过以上的实验结果和分析可知，聚类集成的规模对L⁃MCLA算法的聚类结果的影响不大，在大多数数据集中，L⁃MCLA算法可以仅仅依靠较少的聚类成员就得到较稳健的结果.

4 结论

本文提出基于簇间连接的元聚类集成算法，利用连接三元组来探寻簇间相似度，进一步丰富了相似度矩阵的信息，再通过Ncut算法和对象分配得到最终的结果.

本文提出的算法的优势如下.

（1）从簇的级别考虑集成信息，充分考虑了簇与簇之间的关系.

（2）利用连接三元组增加相似度矩阵中的信息，使聚类结果更准确.

将本文提出的算法与七种聚类集成算法进行了对比实验，证明本文算法和其他聚类集成算法相比，性能存在优势.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

胡乾坤，丁世飞.

局部相似性优化的P⁃谱聚类算法

计算机科学与探索，2018，12(3)：462-471.