基于Seeds集和成对约束的半监督三支聚类集成_姜春茂.pdf

2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1481-1488ISSN 1001-9081CODEN JYIIDUhttp：/基于Seeds集和成对约束的半监督三支聚类集成姜春茂1，吴鹏2，李志聪2*（1.福建工程学院 计算机科学与数学学院，福州 350118；2.哈尔滨师范大学 计算机科学与信息工程学院，哈尔滨 150025）（通信作者电子邮箱）摘要：聚类集成使用合适的策略融合多个具有差异性的基聚类成员，能够有效提高聚类结果的稳定性、鲁棒性和准确率。当前聚类集成的研究较少利用已知的先验信息，面对复杂数据时难以刻画对象与类簇之间明确的归属关系。因此，提出一种基于Seeds集和成对约束的半监督三支聚类集成方法。首先，基于已有的标签信息提出一种新的三支标签传播算法构造基聚类成员；其次，提出一种半监督三支聚类集成框架集成基聚类成员，构造出一致性相似矩阵，并利用成对约束信息对该矩阵进行优化调整；最后，将三支谱聚类作为一致性函数对相似矩阵进行聚类，得到最终集成结果。在多个 UCI 真实数据集上的实验结果表明，与基于类簇的相似分区算法（CSPA）、超图分区算法（HGPA）、元类簇算法（MCLA）、标签传播算法（LPA）、Cop-Kmeans等半监督聚类集成算法相比，所提方法的归一化互信息（NMI）、调整兰德系数（ARI）和F测度在绝大多数据集上取得了最优值，获得了相对更好的聚类集成结果。关键词：三支决策；聚类集成；三支聚类；成对约束；半监督；Seeds集中图分类号：TP391 文献标志码：ASemi-supervised three-way clustering ensemble based on Seeds set and pairwise constraintsJIANG Chunmao1，WU Peng2，LI Zhicong2*（1.School of Computer Science and Mathematics，Fujian University of Technology，Fuzhou Fujian 350118，China；2.College of Computer Science and Information Engineering，Harbin Normal University，Harbin Heilongjiang 150025，China）Abstract:Using appropriate strategies，clustering ensemble can effectively improve the stability，robustness and precision of clustering results by fusing multiple base cluster members with differences.Current research on the clustering ensemble rarely uses known priori information，and it is difficult to describe belonging relationships between objects and clusters when facing complex data.Therefore，a semi-supervised three-way clustering ensemble method was proposed on the basis of Seeds set and pairwise constraints.Firstly，based on the existing label information，a new three-way label propagation algorithm was proposed to construct the base cluster members.Secondly，a semi-supervised three-way clustering ensemble framework was designed to integrate the base cluster members to construct a consistent similarity matrix，and this matrix was optimized by using pairwise constraint information.Finally，the three-way spectral clustering was employed as a consistency function to cluster the similarity matrix to obtain the final clustering results.Experimental results on several real datasets in UCI show that compared with the semi-supervised clustering ensemble algorithms including Cluster-based Similarity Partitioning Algorithm（CSPA），HyperGraph Partitioning Algorithm（HGPA），Meta-CLustering Algorithm（MCLA），Label Propagation Algorithm（LPA）and Cop-Kmeans，the proposed method achieves the best results on most of the datasets in terms of Normalized Mutual Information（NMI），Adjusted Rand Index（ARI）and F-measure.Key words:three-way decision;clustering ensemble;three-way clustering;pairwise constraint;semi-supervised;Seeds set0 引言 聚类分析是一种典型的无监督机器学习方法。聚类分析因为不需要给定样本的标签信息，仅通过衡量数据之间的关系就能识别数据中潜在的结构特征而受到广泛的关注。但单一的聚类算法往往采用某种理想化的数据分布假设，如K-means算法假设样本均匀分布在球形的样本空间中，当样本分布不均匀或存在较多的噪点时，聚类效果不佳。不同的聚类算法往往存在较大的差异性，即使相同的聚类算法在参数不同时，聚类结果也往往存在差异。这限制了聚类分析的适用性。聚类集成旨在融合多个不同的基聚类成员，从而获得一个统一的数据划分。研究表明，相较于单一的聚类算法，聚文章编号：1001-9081（2023）05-1481-08DOI：10.11772/j.issn.1001-9081.2022071094收稿日期：2022-07-19；修回日期：2022-10-03；录用日期：2022-11-04。基金项目：黑龙江省自然科学基金资助项目（LH2020F031）；福建工程学院科研启动基金资助项目（GY-Z220212）。作者简介：姜春茂（1972），男，辽宁庄河人，教授，博士，CCF 高级会员，主要研究方向：三支决策与三支计算、云计算、大数据挖掘；吴鹏（1997），男，山东烟台人，硕士研究生，主要研究方向：三支决策；李志聪（1972），男，黑龙江绥化人，副教授，硕士，CCF会员，主要研究方向：数据挖掘。第 43 卷计算机应用类集成能够有效提高聚类结果的稳定性、鲁棒性和准确率。Strehl等1将集成学习引入聚类分析中，提出了聚类集成的概念。由于缺乏先验的标签信息，聚类集成的研究要比分类集成更加困难，其中的关键问题是如何生成多个具有差异性的基聚类，以及如何对多个基聚类结果进行融合，获得更好的聚类集成结果。Strehl等将超图划分引入聚类集成，提出了三种基于超图划分的聚类集成算法，分别是基于类簇的相似 分 区 算 法（Cluster-based Similarity Partitioning Algorithm，CSPA）、元类簇算法（Meta-CLustering Algorithm，MCLA）和超图 分 区 算 法（HyperGraph Partitioning Algorithm，HGPA）。Zhou 等2提出了基于投票的聚类集成方法。Fred 等3提出了证据积累的概念，通过在基聚类结果中构建共协关系矩阵，分析对象间的相似性，并利用层次聚类得到了聚类结果。Wang等4将传统的成对约束（即必须链接或不能链接）扩展为模糊成对约束，进而提出了一种带有模糊配对约束的半监督 模 糊 聚 类（Semi-Supervised Fuzzy clustering with Pairwise Constraints，SSFPC）。当前聚类集成的研究以非监督聚类集成为主，未能充分利用已知的先验信息，导致难以得到更加优质的聚类集成结果。半监督聚类集成利用少量已知的先验信息，如少量标签信息或成对约束信息等提高聚类集成的质量。Ma等5利用共识函数中的约束信息，提出了基于Chameleon的半监督选择性聚类集成（Semi-supervised Selective Clustering Ensemble based on Chameleon，SSCEC）和基于Ncut的半监督选择性聚类 合 集（Semi-supervised Selective Clustering Ensemble based on Ncut，SSCEN）方法。SSCEC 使用 Chameleon 算法作为共识函数，并在子图分割和子图组合中处理约束信息；SSCEN使用归一化切割算法作为共识函数，并在图的二分法过程中处理约束信息。实验结果表明，这两种半监督成员选择聚类组合算法优于其他半监督算法。Xiao等6设计了一种基于贝叶斯网络的半监督聚类集成模型，并通过变分法对模型进行了推理和求解。这些研究推动了半监督聚类集成的发展，但有一个值得注意的问题是：当前关于半监督聚类集成的研究依然以硬聚类为主。在硬聚类的结果中，对象与类簇之间存在明确的归属关系，即对象确定属于该类簇或对象确定不属于该类簇。在现实的复杂数据中，对象与类簇之间的关系通常是模糊和不确定性的，对象与类簇之间缺乏明确的归属关系。当可用信息不足时，强制将对象划分到某一类簇容易引起较高的误分类代价。因此现有的聚类集成算法难以精确地刻画类簇的结构特征。Yu等7将三支决策的思想引入聚类分析，并提出了三支聚类算法。不同于传统的硬聚类结果，三支聚类通过一对集合呈现一个类簇，即核心域和边界域。核心域中的数据表示确定属于该类簇，边界域中的数据表示可能属于该类簇。琐碎域表示核心域和边界域并集的补集，用来描述确定不属于该类簇的对象。三支聚类能够更加精确地刻画类簇边界模糊的现象，能够有效描述对象与类簇之间的不确定性关系。自三支聚类提出以来，多种研究成果已经涌现。如 Wang等8借鉴数学形态学中的收缩和扩张思想，提出了一种基于数学形态学的三支聚类算法；Yu 等9将证据理论引入聚类分析中，提出了一种基于证据理论的密度峰值三支聚类算法；Afridi等10针对含有缺失值的数据，提出了一种基于博弈粗糙集的三支聚类算法；Yu等11将低秩矩阵和主动学习引入多视图聚类中，提出了一种基于低秩表示的多视图主动三支聚类算法；Jiang等12利用阴影集和多粒度粗糙集的思想提出了一种三支聚类集成方法，在众多 UCI（University of California，Irvine）数据集上的实验效果良好。在聚类集成中，标签信息和成对约束信息有助于改善集成效果，然而，很少有人考虑或同时考虑这两种类型的先验知识。此外，传统的基聚类结果是二支聚类，难以精确地刻画类簇的结构特征，使得在集成阶段可能丢失一些重要信息。为了解决上述问题，本文提出了一种基于Seeds集和成对约束的半监督三支聚类集成（Seeds-set based Three-Way Clustering Ensemble，STWCE）方法。首先，基于标签传播算法（Label Propagation Algorithm，LPA），STWCE方法利用标签信息构建具有差异性的基聚类成员集合；然后提出一种新的方法来构建一致性相似矩阵，并利用成对约束信息对相似矩阵进行调整；最后，使用三支谱聚类对相似矩阵聚类，得到最终集成后的聚类结果。本文主要工作总结如下：1）将三支决策理论引入半监督聚类集成，利用不同类型的先验信息设计了一种三支标签传播算法来生成基聚类成员。2）通过在均匀的成对空间中比较不同区域的对象来区别基聚类成员所做出的贡献，即采用一种新的规则对基聚类成员进行不同的权重表示；并通过将不同基聚类成员结果进行统一表示，有效解决了未对齐的问题。3）使用基于三支决策思想的谱聚类方法对一致性相似矩阵进行聚类，使集成结果收敛于全局最优解。每个类簇由一对集合进行表示，更好地表现出对象与类簇之间的归属关系。1 相关工作 1.1聚类集成给定一组数据U=x1，x2，xn，n表示数据样本的个数。聚类集成通过在数据U上重复执行m次聚类得到一组基聚类结果=1，2，m，式中i=Ci1，Ci2，Cik是第i次基聚类的结果，Cij表示第i次基聚类的第j个类簇。聚类集成主要包括两个步骤：基聚类的生成和一致性函数的设计。在第一步中，主要工作是使用不同的生成机制生成一组不同的聚类结果，例如不同参数下的同一算法12、选择不同算法13和选择不同的对象子集14-15等；第二步是聚类集成的关键步骤，对得到的基聚类成员进行集成来得到最终的聚类结果。现有的聚类集成方法主要分为三类：基于图的方法16、基于数据点间相似度的方法17和基于特征的方法18。基于图的方法将聚类集成问题表示成超图的形式，并调用图划分算法求解；基于数据点间相似度的方法通过建立样本间的相似矩阵，再基于相似度聚类的方法来得到聚类结果；基于特征的方法则使用每个基聚类成员内各样本的聚类标签作为新的特征来得到最后的聚类结果。1.2三支聚类的基本形式传统的聚类算法是一种硬聚类或者说二支聚类的结果，即对象和类簇之间的关系是明确的，对象确定属于该类簇或对象确定不属于该类簇。给定一组数据U=x1，x2，xn，二支聚类通过单个集合Ci表示一个类簇。所划分的类簇内具有较高的相似性，而类簇间具有较高的相异性。给定一组1482第 5 期姜春茂等：基于Seeds集和成对约束的半监督三支聚类集成类簇集合C=C1，C2，Ck，将U中所有的对象划分到k个类簇中，并且k个类簇满足如下条件：1）类簇不能为空，即每个类簇至少包含一个对象：Ci(i=1，2，k)；2）有的类簇的并集为对象的集合：i=1kCi=U；3）每一个对象只能属于一个类簇，即类簇之间的交集为空：Ci Cj=(i j)。不同于二支聚类，三支聚类将每个类簇用一对集合进行表示：Ci=Co(Ci)，Fr(Ci)，即类簇Ci由核心域Co(Ci)和边界域Fr(Ci)两个子集组成。类簇Ci的琐碎域表示为Tr(Ci)=U-Co(Ci)-Fr(Ci)，表示由确定不属于类簇Ci的对象组成的集合。类簇Ci的三个域满足如下条件：1）Co(Ci)Fr(Ci)Tr(Ci)=OB；2）Co(Ci)Fr(Ci)=；3）Co(Ci)Tr(Ci)=；4）Fr(Ci)Tr(Ci)=。上述4个条件说明任何一个类簇的核心域、边界域和琐碎域之间的并集为论域OB，且核心域、边界域和琐碎域两两互不相交。三支聚类的k个类簇满足如下条件：1）Co(Ci)=(i=1，2，k)；2）i=1k()Co(Ci)Fr(Ci)=OB；3）Co(Ci)Co(Cj)=。上述三个条件说明任意一个类簇的核心域不为空，所有类簇的核心域和边界域的并集为论域OB，任意两个类簇的核心域的交集为空。1.3半监督聚类按照不同的监督信息，半监督聚类可分为基于成对约束信息的半监督聚类和基于标签信息的半监督聚类。成对约束信息有 must-link 和 cannot-link：must-link 指两个对象属于同一个类别；cannot-link指两个对象不属于同一个 类 别。Wagstaff 等19将 成 对 约 束 的 思 想 运 用 到 传 统K-means算法中，提出了Cop-Kmeans算法；Zheng等20将成对约束思想引入层次聚类算法，在层次聚类中也可以使用成对约束；Yang等21通过对cannot-link进行广度搜索来解决Cop-Kmeans 中的约束冲突问题，并通过 MapReduce 降低计算复杂度。相较于成对约束信息，标签信息可以直接判断数据点的类别。Qin等22系统性回顾了半监督聚类，尤其是对基于约束信息的半监督聚类方法；Zhou等23提出了标签传播算法，该算法是基于图的半监督聚类的代表性算法；Yu等24同时考虑特征空间和样本空间的渐进式子空间的方法以获得更准确的半监督聚类结果；Fang 等25提出了一种基于低秩表示的半监督子空间聚类方法，将低秩表示框架与高斯场和谐函数结合，通过融合标签信息完成相似矩阵的构造和子空间聚类。半监督聚类算法在很多领域等都有着广泛的应用。在以上研究中，只使用了单一的监督信息来辅助聚类。然而，先验信息不仅有成对约束，还存在标签信息，不同类型的先验信息具有不同的意义，因此，如何融合不同类型的先验信息达到聚类结果的目的有着重要的研究意义。2 基于Seeds集和成对约束的半监督三支聚类集成方法 本章首先阐述了基于Seeds集和成对约束的半监督三支聚类集成（STWCE）方法的基本思想，然后详细介绍了该方法的关键步骤。2.1STWCE的基本思想图 1 给出了 STWCE 方法的基本框架，其中：p为打标问询次数，P为最大问询次数。由图 1 可知，该方法首先采用LPA 生 成 多 个 具 有 差 异 性 的 基 聚 类 集 合，即=1，2，m。每个节点的标签更新取决于其邻居节点，更新效果受节点初始输入和标签更新顺序的影响，因此每次结果存在不确定性，强制将不确定的对象分配到某一类可能会降低聚类的结果，而三支决策思想正是解决聚类算法结果不稳定和不精确问题的重要方法之一。通过将每个类由两个集合进行表示，减少由于强制分类而带来的聚类效果的降低，更好地呈现出对象与类簇之间的关系。在得到基聚类集合后，共协关系矩阵可能只得到了部分点的相似关系，例如，对象x在不同基聚类结果中可能有不同的归属关系。另外，不同的基聚类成员聚类后的标签可能并不对应，因此，定义一组规则来统一表示不同基聚类成员的结果，并针对不同区域的对象采用不同的策略进行集成，以更好地描述对象间的相似关系，并利用成对约束信息优化调整一致性相似矩阵。最后通过三支谱聚类方法对一致性相似矩阵聚类，得到最终的集成结果。2.2基聚类成员生成基聚类成员的产生方法多种多样，如采用不同的聚类算法、采用不同参数下同一聚类算法、在特征子空间进行聚类和在数据子空间进行聚类等。然而，这些成员生成方法未考虑到数据集中已有的标签信息，本文设计了一种三支标签传播算法（TW-LPA），利用已有标签信息构成的Seeds集对原始数据集进行聚类。LPA 只需利用少量的标签信息指导就可以发现未标记图1STWCE方法的框架Fig.1Framework of STWCE method1483第 43 卷计算机应用数据的内在特性、分布规律，进而预测和传播未标记数据的标签，合并到标记的数据集中。LPA通过相似节点之间的标签的传递来学习如何进行聚类，所以它不受数据分布的限制。算法具有线性时间复杂度，广泛应用于大规模数据处理和挖掘。然而，该算法每个节点的标签更新取决于其邻居节点，更新效果受节点初始输入和标签更新顺序的影响。因此，LPA的每次结果存在不确定性，而三支决策思想正是解决聚类算法结果不稳定和不精确的重要方法之一。为此，将多次运行的LPA的结果作为基聚类的结果。给定原始数据集U=x1，x2，xn，用=1，2，K表示基聚类成员集合，i表示第i个基聚类的结果。数据集中前l个对象带有数据类标签，后n-l个对象不带数据类标签。给定已知对象的标签集合Y=y1，y2，yl，集合U的前l个对象在Y中一一对应。给定图结构G=(U，W)，其中：U为数据集合在图G中的节点；W代表节点之间的相似性关系，即节点间的权重。计算节点间权重Wij：Wij=exp()-xi-xj2 22（1）定义一个n n的概率传播矩阵P，节点i的标签传递给节点j的概率Pij为：Pij=P(i j)=wij k=1nwik（2）其中：Pij表示节点i的标签传递给节点j的概率。通过概率传递，使概率分布集中于给定类别，然后通过边 的 权 重 值 来 传 递 节 点 标 签。在 通 过 LPA 得 到C=C1，C2，Ck时，可能会得到如图 2的结果：将每个类簇用一个集合进行表示，x1与x2分别被聚类到C1和C2中，但从图2中可以看到强制性划分到一个类中可能是错误的。因此，引入三支聚类，并借鉴 k近邻的思想，设计一种三支标签传播算法（TW-LPA），将LPA的结果进行再次划分，采用Dist(x)（距离该点最近的t个点组成的集合）对每个类别的对象进行划分，将每个类簇进一步划分为核心域Co(Ci)和边界域Fr(Ci)两个子集，更好地展现对象与类簇的归属关系，从而减少在基聚类阶段由于强制划分某些对象带来的信息丢失导致聚类效果的降低。首先，考虑对象xi的Dist(xi)，xi Ci，设arg max Dist(xi)代 表 距 离 该 点 最 近 的t个 对 象 中 数 量 最 多 的 集 合，若arg max Dist(xi)Ci t，将xi分 配 到 该 类 的 核 心 域，即xi Co(Ci)，否则，xi Fr(Ci)。此外，对于对象xj Ci，如果arg max Dist(xj)Ci=，将xi分配到边界域，即xj Fr(Ci)。在进行n次之后，得到了新的标签传播结果。运行 TW-LPA获得集合=1，2，K。具体流程见算法1。算法1 基于TW-LPA的基聚类成员生成。输入 数 据 集U=x1，x2，xn，Y=y1，y1，yl，参数t；输出 =1，2，K。For m=1 to K doxi Y=y1，y1，ylWij exp()-xi-xj2 22 While存在对象x没有划分类 doP(i j)wij k=1nwikEnd while/根据Dist(x)规则获得三支聚类结果For x and C doCompute Dist(xi)If arg max Dist(xi)Ci t and xi Cixi Co(Ci)Elsexi Fr(Ci)Compute Dist(xj)If arg max Dist(xj)Ci and xj Ci xi Fr(Ci)End forEnd forReturn =1，2，K2.3半监督三支聚类集成在得到由 TW-LPA 产生的具有不同差异的基聚类成员集合=1，2，K后，将构建一致性相似矩阵，并利用成对约束信息对一致性相似矩阵进行优化调整。最后利用三支谱聚类对调整后的相似矩阵聚类，得到最终的集成结果。2.3.1半监督三支聚类集成利用无类属数据内部存在的结构先验信息，同时结合成对约束信息汇总来自基聚类成员集合 的信息构造相似矩阵。对于每个基聚类成员d(1 d K)的结果，将它的每个类利用核心域Co(Ci)和边界域Fr(Ci)两个集合进行表示。相较于传统的硬聚类和软聚类表示方法，三支聚类的表示更加直观地展示了对象与类簇之间的归属关系，位于核心域中的对象比边界域的对象更具有可信度。此外，不同基聚类通过聚类得到的结果可能是不对齐的，与监督学习不同，聚类后的结果仅表示数据的聚类特征，将不同的聚类结果直接进行比较并不可行。例如，如图3所示，对象x在不同的基聚类成员中可能有不同的归属关系。定义以下规则用来统一表示不同基聚类成员的结果。设P=P(i，j)是一个n n的矩阵，其中，P(i，j)是xi和xj之间的相似度。1）如 果 对 象xi和 对 象xj属 于 同 一 个 类Ci，同 时 有xi Co(Ci)和xj Co(Ci)，则P(i，j)=+；2）如 果 对 象xi和 对 象xj属 于 同 一 个 类Ci，同 时 有xi Co(Ci)和xj Fr(Ci)，则P(i，j)=；3）如 果 对 象xi和 对 象xj属 于 同 一 个 类Ci，同 时 有xi Fr(Ci)和xj Fr(Ci)，则P(i，j)=-。图 2对象与类簇的归属关系Fig.2Belonging relationships between objects and class clusters1484第 5 期姜春茂等：基于Seeds集和成对约束的半监督三支聚类集成P(i，j)=|+，xi Co(Ci)xj Co(Ci)，xi Co(Ci)xj Fr(Ci)-，xi Fr(Ci)xj Fr(Ci)1，其他（3）其中，0 -+1。根据式（3），将不同的基聚类成员结果进行统一表示。根据所提出的表示方法，当有K个基聚类成员进行集成时，可以将每个基聚类成员的结果保存到一个n n的成对矩阵中。设P=PtKt=1是来自K个基聚类成员的一组成对矩阵，其中，Pt=Pt(i，j)是用来保存来自第t个基聚类成员的n n的成对矩阵。在给定基聚类成员集合=1，2，K的情况下，可以找到所有基聚类成员间的一致性相似矩阵S的元素S(i，j)如下：S(i，j)=t=1KPt(i，j)K（4）得到相似矩阵S后，利用成对约束信息优化调整相似矩阵S，使对象xi和xj在一个类簇中更紧凑，在不同类簇中更离散。对象xi和xj的相似性由Sij和Sji表示，Sij和Sji是相似矩阵S中的元素。如果对象xi和xj标记在同一个类簇中，满足must-link 关系，即(xi，xj)ML，相似矩阵S中相应的元素更新为1；相反，如果xi和xj不属于同一个类簇，满足cannot-link关系，即(xi，xj)CL，相似矩阵S中相应的元素更新为0。采用以下的策略进行对S()i，j进行调整：Sij=Sji=1，(xi，xj)ML0(xi，xj)CL（5）算法2 相似矩阵构造算法。输入 基聚类成员集合=1，2，K，成对约束集合ML和CL；输出 相似矩阵S。/*构造一致相似矩阵*/For t=1 to K do根据式（3）计算Pt(i，j)S(i，j)Pt(i，j)End forS(i，j)S(i，j)K/*使用成对约束信息进行修改相似矩阵*/For i=1 to ML doIf(xi，xj)MLS(i，j)=1 End forFor i=1 to CL doIf(xi，xj)CLS(i，j)=0End forReturn S(i，j)2.3.2三支谱聚类在上一步处理中得到了一致性相似矩阵，现在将定义一个划分准则，目的是使同一类簇的对象更紧凑，不同类簇的对象更分散。由于求图划分的最优解是一个NP难的问题，一个很好的解决方法是考虑问题的连续放松形式，将原问题转换为求图的Laplacian矩阵的谱分解。谱聚类是一种基于图划分理论的方法，能对任意形状的数据进行划分且收敛于全局最优解。三支谱聚类是将三支决策思想和谱聚类方法相结合，将每个类簇由一对集合进行表示Ci=Co(Ci)，Fr(Ci)，核心域Co(Ci)和边界域Fr(Ci)两个子集构成该类簇的上界。三支谱聚类算法主要过程分为两步：1）对一致性相似度矩阵通过谱聚类方法获得每个类簇的上界；2）借助于三支决策思想，基于q邻域将每个类簇的上界进一步划分为核心域Co(Ci)和边界域Fr(Ci)两个子集。基本流程如算法3所示。算法3 三支谱聚类。输入 一致性相似矩阵S(i，j)，类簇个数K，参数q；输出 最终聚类结果C：C=()Co(C1)，Fr(C1)，(Co(C2)，)Fr(C2)，()Co(CK)，Fr(CK)/*谱聚类获得每个类簇的上界*/令dii=j=1nSij，dij=0(i j)，得到矩阵D=i=1n j=1ndij令L=D-1/2SD-1/2，得到矩阵L计算L的K个最大的特征值所对应的特征向量x1，x2，xK，构造X=x1，x2，xK Rn K对X的每一行进行单位化处理，即Zij=Xij jXij对矩阵Z使用K-means算法，若Z的第i行分到Cj类，则将数据对象xi分到Cj类/*划分核心域和边界域*/For i=1 to K doCo(Ci)=；Fr(Ci)=End forFor i=1 to K doUcSet=U-CiFor j=1 to UcSet doIf Dis(xj)Ci Fr(Ci)=xjEnd forFor j=1 to Ci doIf Dis(xi)Ci=Co(Ci)=xiElseFr(Ci)=xjEnd forEnd forReturn C=()Co(C1)，Fr(C1)，()Co(C2)，Fr(C2)，()Co(CK)，Fr(CK)图 3对象x在不同的基聚类成员中的归属关系Fig.3Belonging relationships of object x in different base cluster members1485第 43 卷计算机应用2.4复杂性分析基聚类算法阶段：设基聚类算法的个数为(2)，第i(i 1，)个基聚类算法的复杂度为i，则所有的基聚类算法的复杂度为O()i=1i。集成阶段：计算一个基聚类成员n n的成对关系矩阵复杂度为O(n2)，那么计算整个基聚类成员集合的复杂度是O(n2k)。构建基于成对约束信息监督矩阵对CTS（Connected-Triple-based Similarity）矩阵进行修改的复杂度为O(n2)。谱聚类阶段：进行谱聚类的时间复杂度为O(n3)，构造核心域和边界域的时间复杂度为O(n2k)。所以，STWCE算法的复杂度约为：O()i=1i+n2k+n2+n3+n2k3 实验与结果分析 3.1实验数据与评价标准采用UCI数据中的7个数据集进行实验。其中3个是二类的，4个是多类的，维度分布有高有低。表1给出了这些数据集的相关信息描述。实验采用目前三种广泛使用的聚类性能评价指标：1）归一化互信息（Normalized Mutual Information，NMI）。NMI用于评价对数据集聚类后的结果与数据集的真实结果之间的相似程度。设C为对数据集聚类后的结果，Y为数据集的真实结果，NMI计算公式如下：RNMI=2I()C；YH()C+H()K式中：I(X；Y)=H(X)-H(|X Y)，反映了两个变量X和Y之间的互信息；H(X)表示变量X的香农熵；H(|X Y)表示基于给定Y的情况下X的条件熵。RNMI 0，1，值越大代表聚类效果越好。2）调整兰德系数（Adjusted Rand Index，ARI）。ARI衡量的是两个数据分布的相似性。ARI计算公式如下：RRI=(a+b)Cnsamples2RARI=RRI-E|RRImax(RRI)-E|RRI其中：a表示在C与Y中都是同类别的元素对数，b表示在C与Y中都是不同类别的元素对数；Cnsamples2表示数据集中可以组成的对数。RARI 1，1，值越大意味着聚类结果与真实情况越吻合。3）F 测度（F-Measure）。该指标综合了精确率和召回率评估标准，反映了任意一对样本的正确归类的准确性。F-Measure的值越高越好，它的计算公式如下：RF-Measure=2PR(P+R)其中：P表示精确率，R表示召回率。3.2实验结果与分析3.2.1算法性能比较实验首先选取 LPA 作为基聚类器，运行 20 次。由于LPA的不稳定性，将会得到20个有差异性的基聚类结果；然后通过本文方法构造一致性相似矩阵，利用成对约束信息对一致性相似矩阵进行调整，再经过三支谱聚类得到集成后的结果C。实验中采取的对比算法有 CSPA1、HGPA1、MCLA1、LPA23、Cop-Kmeans算法19、限制性投射半监督的谱聚类集成（Constraint Projections for Semi-Supervised Spectral Clustering Ensemble，CPSSSCE）算法25。为了公平对比，从每一类数据集中抽取5%的标签样本，标签样本作为基聚类算法的 Seeds 集；同时从每一类 Ground-Truth 的成对约束信息中选出 20%的必连信息和 20%的不连信息，作为成对约束的先验知识。本文中的-、和+分别设置为 0.3、0.5和0.7。表24分别概括了7个数据集上给予不同类别相同比例的监督信息下，本文方法STWCE以及对比的6种方法的ARI值、NMI值和F-Measure值，加粗表示最优值。从实验结果可以看出，这7种方法在不同的数据集上都获得了不同程度的聚类效果，而 STWCE的三个评价指标在绝大多数据集上都获得了相对较好的聚类集成效果，说明综合考虑标签信息和成对约束信息的融合以及本文所提出的集成策略能够改善聚类效果。表3不同算法的NMI值Tab.3NMI values of different algorithms数据集SegmentIrisWineGlassIonosphereBankSonarCSPA0.8340.8160.7460.4380.3050.7470.141HGPA0.8430.7770.6940.3960.3530.7430.105MCLA0.8430.8700.8240.4700.2120.8930.109LPA0.8240.7450.7220.4350.3310.6830.130Cop-Kmeans0.6910.7950.8470.3560.3600.1390.096CPSSSCE0.5940.8050.8410.4270.4160.9090.158STWCE0.8520.8700.8240.5000.4320.9190.182表1实验数据集相关信息描述Tab.1Information description of experimental datasets数据集GlassWineIrisSegmentIonosphereBankSonar样本数2141781502 3103511 372208属性数91341934460分类数6337222表2不同算法的ARI值Tab.2ARI values of different algorithms数据集SegmentIrisWineGlassIonosphereBankSonarCSPA0.8030.8330.7620.3180.3390.7930.183HGPA0.8230.7700.7810.2780.3870.7900.136MCLA0.8160.8100.8630.4340.1700.9390.122LPA0.7910.7140.7120.2670.3100.7640.114Cop-Kmeans0.6910.8010.8640.2480.2570.1930.129CPSSSCE0.5040.8300.8530.2770.4730.8620.209STWCE0.8250.8850.8630.4770.4760.9510.2271486第 5 期姜春茂等：基于Seeds集和成对约束的半监督三支聚类集成3.2.2一致性相似矩阵分析为了更好地说明本文提出的半监督三支聚类集成方法构成一致性相似矩阵的效果，在不同的数据集上使用不同比例的先验信息，采用三种指标与传统的 CO-association（CO）矩阵和CTS矩阵算法进行对比。不同算法采用相同的基聚类算法并在给予相同比例的先验信息下进行实验，部分结果如图4所示。从图4可以看出：随着给予的先验信息的比例增大，三种评价指标都有逐渐增加的趋势；但是当提供的先验信息达到一定值之后，这些指标的增长趋势都略显减缓。此外，在大部分的数据集上，在先验信息不足的情况下，可以看出本文方法相较于另外两个算法有更好的集成效果。这说明相对于传统方法，三