【机器学习】SUCE基于聚类集成的半监督二分类方法

第13卷第6期 智能系统学报 Vol.13 No.6 2018年12月 CAAI Transactions on Intelligent Systems Dec.2018 D0:10.11992/tis.201711027 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180411.1021.006html SUCE:基于聚类集成的半监督二分类方法 闵帆，王宏杰，刘福伦，王轩 (西南石油大学计算机科学学院，四川成都610500) 摘要：半监督学习和集成学习是目前机器学习领域中的重要方法。半监督学习利用未标记样本，而集成学习 综合多个弱学习器，以提高分类精度。针对名词型数据，本文提出一种融合聚类和集成学习的半监督分类方 法SUCE。在不同的参数设置下，采用多个聚类算法生成大量的弱学习器：利用已有的类标签信息，对弱学习 器进行评价和选择；通过集成弱学习器对测试集进行预分类，并将置信度高的样本放入训练集；利用扩展的训 练集，使用ID3、Nave Bayes、kNN、C4.5、OneR、Logistic等基础算法对其他样本进行分类。在UCI数据集上的 实验结果表明，当训练样本较少时，本方法能稳定提高多数基础算法的准确性。 关键词：集成学习；聚类；聚类集成；半监督；二分类 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)06-0974-07 中文引用格式：闵帆，王宏杰，刘福伦，等.SUCE:基于聚类集成的半监督二分类方法J.智能系统学报，2018,13(6)： 974-980. 英文引用格式：MIN Fan,WANG Hongjie,LIUFulun,.et al.SUCE:semi-supervised binary classification based on clustering en semble[J].CAAI transactions on intelligent systems,2018,13(6):974-980. SUCE:semi-supervised binary classification based on clustering ensemble MIN Fan,WANG Hongjie,LIU Fulun,WANG Xuan (School of Computer Science,Southwest Petroleum University,Chengdu 610500,China) Abstract:Semi-supervised learning and ensemble learning are important methods in the field of machine learning. Semi-supervised learning utilize unlabeled samples,while ensemble learning combines multiple weak learners to im- prove classification accuracy.This paper proposes a new method called Semi-sUpervised classification through Cluster- ing and Ensemble learning(SUCE)for symbolic data.Under different parameter settings,a number of weak learners are generated using multiple clustering algorithms.Using existing class label information the weak learners are evaluated and selected.The test sets are pre-classified by weak learners ensemble.The samples with high confidence are moved to the training set,and the other samples are classified through the extended training set by using the basic algorithms such as ID3,Nave Bayes,kNN,C4.5,OneR,Logistic and so on.The experimental on the UCI datasets results show that SUCE can steadily improve the accuracy of most of the basic algorithms when there are fewer training samples. Keywords:ensemble learning;clustering,clustering ensemble;semi-supervised;binary classification 在机器学习领域中，半监督学习2和集成 用少量已标记样本进行学习，那么训练得到的分 学习是当前的研究热点。它们被广泛应用于智 类模型通常会造成过度拟合9。为此，Merz等1o 能信息处理、图像处理、生物医学四等领域。 于1992年提出半监督分类，它不依赖外界交互， 在许多大数据场景中，样本属性的获取容易且廉 充分利用未标记样本，有效提高分类模型的稳定 性和精度。 价，而其标签的获取则困难且昂贵⑧。如果只使 集成学习是指先构建多个学习器，再采用某 收稿日期：2017-11-21.网络出版日期：2018-04-11. 基金项目：国家自然科学基金项目(61379089)】 种集成策略进行结合，最后综合各个学习器的结 通信作者：闵帆.E-mail:minfanphd@I63.com, 果输出最终结果。集成学习中的多个学习器可以

DOI: 10.11992/tis.201711027 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180411.1021.006.html SUCE：基于聚类集成的半监督二分类方法 闵帆，王宏杰，刘福伦，王轩 （西南石油大学 计算机科学学院，四川 成都 610500） 摘 要：半监督学习和集成学习是目前机器学习领域中的重要方法。半监督学习利用未标记样本，而集成学习 综合多个弱学习器，以提高分类精度。针对名词型数据，本文提出一种融合聚类和集成学习的半监督分类方 法 SUCE。在不同的参数设置下，采用多个聚类算法生成大量的弱学习器；利用已有的类标签信息，对弱学习 器进行评价和选择；通过集成弱学习器对测试集进行预分类，并将置信度高的样本放入训练集；利用扩展的训 练集，使用 ID3、Nave Bayes、 kNN、C4.5、OneR、Logistic 等基础算法对其他样本进行分类。在 UCI 数据集上的 实验结果表明，当训练样本较少时，本方法能稳定提高多数基础算法的准确性。 关键词：集成学习；聚类；聚类集成；半监督；二分类 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)06−0974−07 中文引用格式：闵帆, 王宏杰, 刘福伦, 等. SUCE：基于聚类集成的半监督二分类方法[J]. 智能系统学报, 2018, 13(6): 974–980. 英文引用格式：MIN Fan, WANG Hongjie, LIU Fulun, et al. SUCE: semi-supervised binary classification based on clustering en￾semble[J]. CAAI transactions on intelligent systems, 2018, 13(6): 974–980. SUCE: semi-supervised binary classification based on clustering ensemble MIN Fan，WANG Hongjie，LIU Fulun，WANG Xuan (School of Computer Science, Southwest Petroleum University, Chengdu 610500, China) Abstract: Semi-supervised learning and ensemble learning are important methods in the field of machine learning. Semi-supervised learning utilize unlabeled samples, while ensemble learning combines multiple weak learners to im￾prove classification accuracy. This paper proposes a new method called Semi-sUpervised classification through Cluster￾ing and Ensemble learning (SUCE) for symbolic data. Under different parameter settings, a number of weak learners are generated using multiple clustering algorithms. Using existing class label information the weak learners are evaluated and selected. The test sets are pre-classified by weak learners ensemble. The samples with high confidence are moved to the training set, and the other samples are classified through the extended training set by using the basic algorithms such as ID3, Nave Bayes, kNN, C4.5, OneR, Logistic and so on. The experimental on the UCI datasets results show that SUCE can steadily improve the accuracy of most of the basic algorithms when there are fewer training samples. Keywords: ensemble learning; clustering; clustering ensemble; semi-supervised; binary classification 在机器学习[1]领域中，半监督学习[2-3]和集成 学习[4]是当前的研究热点。它们被广泛应用于智 能信息处理[5] 、图像处理[6] 、生物医学[7]等领域。 在许多大数据场景中，样本属性的获取容易且廉 价，而其标签的获取则困难且昂贵[8]。如果只使 用少量已标记样本进行学习，那么训练得到的分 类模型通常会造成过度拟合[9]。为此，Merz 等 [10] 于 1992 年提出半监督分类，它不依赖外界交互， 充分利用未标记样本，有效提高分类模型的稳定 性和精度。 集成学习是指先构建多个学习器，再采用某 种集成策略进行结合，最后综合各个学习器的结 果输出最终结果。集成学习中的多个学习器可以 收稿日期：2017−11−21. 网络出版日期：2018−04−11. 基金项目：国家自然科学基金项目 (61379089). 通信作者：闵帆. E-mail：minfanphd@163.com. 第 13 卷第 6 期 智 能 系 统 学 报 Vol.13 No.6 2018 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2018

第6期 闵帆，等：SUCE:基于聚类集成的半监督二分类方法 ·975· 是同种类型的弱学习器，也可以是不同类型的弱 数对x∈U,的k个预测标签进行集成，得到一个 学习器，基于这些弱学习器进行集成后获得一个 统一的集成标签h(x)。 精度更高的“强学习器以。 基于聚类的分类算法是指先进行数据聚类)， 聚类 然后根据类簇和标签信息进行分类。其优点是需 学习器C 要的标签较少，但单一算法的聚类效果不稳定或 聚类 一致性 数据集U 学习器C P: 函数 聚类结果 不符合类标签分布时，分类效果受到严重影响。 2002年Strehl等1提出“聚类集成”，使用不同类 型的聚类算法构造不同的学习器，结合这些学习 器可得到更可靠更优的聚类结果；Fred等u提出 聚类 学习器C. 通过对同一种聚类算法选取不同参数来构造学习 器；Zhou6利用互信息设定权重，采用基于投票、 图1聚类集成过程示意图 加权投票进行聚类集成学习；Zhangl提出一种无 Fig.1 The diagram of clustering ensemble 标签数据增强集成学习的方法UDEED,能够同时 集成学习中，学习器之间的差异性被认为是 最大化基分类器在有标签数据上的精度和无标签 影响集成结果的关键因素之一0。聚类集成的第 数据上的多样性。 一步是通过不同类型聚类基学习器产生多个聚类 本文针对名词型数据分类问题，在半监督学 结果，从不同的方面反映数据集的结构，有利于 习的框架之下，融合聚类和集成学习技术，提出 集成2。在本文中，k-Means'22、EM2、Farthest- 一种新的半监督分类算法(semi-supervised binary First2和HierarchicalClusterer24个聚类算法将作 classification based on clustering ensemble,SUCE) 为聚类集成的基础学习算法，并且每次运行都设 通过在UCI4个数据集上的实验表明，该方法比 置不同的参数。k-Means原理简单运行速度较 传统的D3、kNN、C4.5等算法的分类效果要好。 快，但依赖于初始参数设置使得聚类结果存在不 而且，当标签较少时，其分类优势更为明显。 稳定性，并且不能有效针对非凸形状分布数据聚 类。EM不需要事先设定类别数目，计算结果稳 1基本概念 定、准确，但算法相对复杂，收敛较慢不适用于大 分类问题的基础数据为决策系统。 规模数据集和高维数据。HierarchicalClusterer没 定义1例决策系统S为一个三元组： 有任何目标函数，簇合并后不可逆转，将局部最 S=(U.C.d) (1) 优作为全局最优解，聚类结果依赖于主观获得。 式中：U是对象集合也称为论域；C是条件属性集 FarthestFirst在迭代过程中减少待聚类样本数和类 合；d是决策属性。本文只研究名词型数据的二 别数，具有精简聚类结果的效果。每个算法各有 分类问题，所以决策属性只有两个属性值即 优劣，适用的场景不同：因此需要对它们进行集 Ψ=2。一般假设所有的条件属性值已知，而仅有 成化来实现优势互补。因为本文只研究名词型数 部分样本决策属性值已知。这些对象构成了训练 据的二分类问题，所以在聚类时，聚簇的数量直 集U,而U=U-U,构成了测试集。实际上，在半 接设为类别数量，在实验中，本文将所有聚类算 监督学习中，测试集的对象也参与了训练模型的 法的聚簇数量设定为2。 构建。 聚类效果的主要评价指标有JC系数、FM指 聚类问题不涉及决策属性d。聚类集成是指 数、DB指数和DI指数等。本文通过聚类方法研 关于一个对象集合的多个划分组合成为一个统 究二分类问题，使用U,的聚类纯度对聚类结果进 聚类结果的方法，目标就是要寻找一个聚类，使 行评估。通常来说，聚类纯度越高则表明聚类效 其对于所有的输入聚类结果来说，尽可能多地 果越好。 符合四。 定义2聚类纯度(purity of cluster,PC) 如图1所示，聚类集成的过程为：首先对U= 设数据集U=U,UU,对于任意聚类学习器 {x1,2,…,xm,通过集成学习器集合C={C1,C2,…,Ck, C∈C的聚类结果t(U=[t(U)t(U,】,其中t(U,)= 得到P={p1,P2,…,p},其中p:i=1,2,…,k为第i个 [c)t)…t(l,用d(U,)=[dc)d2)…d(l 聚类学习器得到的聚类结果。最后通过一致性函 表示x,∈U,的真实标签

是同种类型的弱学习器，也可以是不同类型的弱 学习器，基于这些弱学习器进行集成后获得一个 精度更高的“强学习器” [11-12]。 基于聚类的分类算法是指先进行数据聚类[13] ， 然后根据类簇和标签信息进行分类。其优点是需 要的标签较少，但单一算法的聚类效果不稳定或 不符合类标签分布时，分类效果受到严重影响。 2002 年 Strehl 等 [14]提出“聚类集成”，使用不同类 型的聚类算法构造不同的学习器，结合这些学习 器可得到更可靠更优的聚类结果；Fred 等 [15]提出 通过对同一种聚类算法选取不同参数来构造学习 器；Zhou[16]利用互信息设定权重，采用基于投票、 加权投票进行聚类集成学习；Zhang[17]提出一种无 标签数据增强集成学习的方法 UDEED，能够同时 最大化基分类器在有标签数据上的精度和无标签 数据上的多样性。 本文针对名词型数据分类问题，在半监督学 习的框架之下，融合聚类和集成学习技术，提出 一种新的半监督分类算法 (semi-supervised binary classification based on clustering ensemble，SUCE)。 通过在 UCI 4 个数据集上的实验表明，该方法比 传统的 ID3、kNN、C4.5 等算法的分类效果要好。 而且，当标签较少时，其分类优势更为明显。 1 基本概念 分类问题的基础数据为决策系统。 定义 1 [18] 决策系统 S 为一个三元组： S = (U,C,d) (1) 式中：U 是对象集合也称为论域；C 是条件属性集 合；d 是决策属性。本文只研究名词型数据的二 分类问题，所以决策属性只有两个属性值即 |Vd |=2。一般假设所有的条件属性值已知，而仅有 部分样本决策属性值已知。这些对象构成了训练 集 Ur，而 Ut=U–Ur 构成了测试集。实际上，在半 监督学习中，测试集的对象也参与了训练模型的 构建。 聚类问题不涉及决策属性 d。聚类集成是指 关于一个对象集合的多个划分组合成为一个统一 聚类结果的方法，目标就是要寻找一个聚类，使 其对于所有的输入聚类结果来说，尽可能多地 符合[19]。 U = {x1, x2,··· , xm} C = {C1,C2,··· ,Ck} P = {p1, p2,··· , pk} pi(i = 1,2,··· , k) 如图 1 所示，聚类集成的过程为：首先对 ，通过集成学习器集合 ， 得到 ，其中 为第 i 个 聚类学习器得到的聚类结果。最后通过一致性函 数对 x∈Ut 的 k 个预测标签进行集成，得到一个 统一的集成标签 h(x)。 数据集U 聚类 学习器C2 一致性 函数 聚类结果 聚类 学习器C1 聚类 学习器Cn … pn p2 p1 图 1 聚类集成过程示意图 Fig. 1 The diagram of clustering ensemble 集成学习中，学习器之间的差异性被认为是 影响集成结果的关键因素之一[20]。聚类集成的第 一步是通过不同类型聚类基学习器产生多个聚类 结果，从不同的方面反映数据集的结构，有利于 集成[21]。在本文中，k-Means[22] 、EM[23] 、Farthest￾First[24]和 HierarchicalClusterer[25] 4 个聚类算法将作 为聚类集成的基础学习算法，并且每次运行都设 置不同的参数。k-Means 原理简单运行速度较 快，但依赖于初始参数设置使得聚类结果存在不 稳定性，并且不能有效针对非凸形状分布数据聚 类。EM 不需要事先设定类别数目，计算结果稳 定、准确，但算法相对复杂，收敛较慢不适用于大 规模数据集和高维数据。HierarchicalClusterer 没 有任何目标函数，簇合并后不可逆转，将局部最 优作为全局最优解，聚类结果依赖于主观获得。 FarthestFirst 在迭代过程中减少待聚类样本数和类 别数，具有精简聚类结果的效果。每个算法各有 优劣，适用的场景不同；因此需要对它们进行集 成化来实现优势互补。因为本文只研究名词型数 据的二分类问题，所以在聚类时，聚簇的数量直 接设为类别数量，在实验中，本文将所有聚类算 法的聚簇数量设定为 2。 聚类效果的主要评价指标有 JC 系数、FM 指 数、DB 指数和 DI 指数等。本文通过聚类方法研 究二分类问题，使用 Ur 的聚类纯度对聚类结果进 行评估。通常来说，聚类纯度越高则表明聚类效 果越好。 定义 2 聚类纯度 (purity of cluster, PC) C ∈ C t(U) = [t(Ut) t(Ur)] t(Ur) = [ t(x1) t(x2) ··· t ( x|Ur| )] d (Ur)= [ d (x1) d (x2) ··· d ( x|Ur| )] 设数据集 U=Ut∪Ur，对于任意聚类学习器 的聚类结果 ，其中 ，用 表示 xi∈Ur 的真实标签。 第 6 期 闵帆，等：SUCE：基于聚类集成的半监督二分类方法 ·975·

·976· 智能系统学报 第13卷 那么基学习器C对于U的聚类纯度可表示为 若C1的预测标签d,'(U,)=[10),若C2的预测标签 1 d2'(U)=[11,若C的预测d3(U,)=[10]。 PC(U,)= (t(xi),d(xi)) (2) 对U,=y1,y2的结果为 式中： 因为∑d0)=1g=3,所以h0yFl; 1 c(a,b)=0, a=b 其他 (3) 因为∑d02)=2,所以02上-1。 另外，聚类集成学习存在一个必须要解决的 人 问题：簇标签与真实标签的对应。 2 算法设计与分析 定义3（标签对应）任意聚类基学习器 C∈C,根据对训练集U,上的聚类纯度PC(U),得 本节首先描述算法的总体框架，然后进行算 到x∈U,中样本的聚类标签。标签对应函数 法伪代码描述，最后分析算法复杂度。 A(U)可定义为 2.1算法总体方案 normal(,), PC(U,)>0 基于集成的半监督分类方法主要是通过集成 A(U,)= covert(U,),PC(U,)0时，即表示聚类标签与类标签相匹配， 如图2所示，基于聚类集成的半监督分类过 将调用normal(U)函数，并直接把聚类标签作为 程为：第1个分图说明，首先通过聚类集成，将 预测标签；当PC(U,)>0时，即表示聚类标签与类 B中部分没有类别样本C的类标签预测出来；达 标签相反，将调用covert(U)函数，把聚类标签取 到“扩大”有类别的样本集合(A变成了A+C),“缩 反后作为预测标签；当PC(U,)介于1-0和0之 小”了未标记类别集合(B变成了B)。第2个分图 间，即认为聚类结果不适于指导标签预测，调用 说明，对于扩大后的集合(4+C)利用分类模型，完 reset(U)函数，用-l表示xeU,的预测标签。 成预测没有类别的样本B。 例1对U,={1,x2,x3,U,=y1,2,有U=U,UU 且d(U,)=[101,0=0.9。 B=B'+C 1)如果(U)=[10110],PC(U,)=1>0,所以 未标记 未标记 聚类集 已标记 已预测标 未标记 d'(U,)=normal(U,)=[10]; 数据A 数据B 数据4 记数据C 数据B· 2)如果t(U)=[01001],PC(U)=0<1-0,所以 d'(U,)=convert(U,)=[10]; 3)如果tU=[00001],1-PC(U)=0<1-0,所 训练集 d'(U,)=reset(U,)=[-1 -1]o 未标记 聚类集成 分类模型 分类 未标记 聚类学习器集合C将给样本x∈U,标记C个 记数据C 数据B 数据B 聚类标签，并根据定义(2)和定义(3)得到C个预 图2 基于聚类集成的半监督分类示意图 测标签。 Fig.2 The diagram of semi-supervised classification based 定义4（一致性）聚类学习器C:∈C对x∈U, on clustering ensemble 上的预测标签d(),且d(x)∈0,1，那么集成标签 2.2算法描述 hx)的值为 在训练阶段，本算法将依次对数据集进行 4步处理，从而生成分类器： d'(x) d(x)=0 h(x)= (5) l)通过getLabel(U,)获取训练集U,的标签 其他 Lu,。然后，利用remove(U)对U,去标签得到U 例2采用与例1中相同的U,和U,且C=3, 并将UUU,得到无标签U

那么基学习器 C 对于 Ur 的聚类纯度可表示为 PC(Ur) = 1 |Ur | |Ur ∑ | i=1 σ(t(xi),d (xi)) (2) 式中： σ(a,b) = { 1, a = b 0, 其他 (3) 另外，聚类集成学习存在一个必须要解决的 问题：簇标签与真实标签的对应。 C ∈ C A 定 义 3 (标签对应 ) 任意聚类基学习器 ，根据对训练集 Ur 上的聚类纯度 PC(Ur )，得 到 x∈Ut 中样本的聚类标签。标签对应函数 (Ut ) 可定义为 A(Ut) =    normal(Ut), PC(Ur) > θ covert(Ut), PC(Ur) θ 时，即表示聚类标签与类标签相匹配， 将调用 normal(Ut ) 函数，并直接把聚类标签作为 预测标签；当 PC(Ur )>θ 时，即表示聚类标签与类 标签相反，将调用 covert(Ut ) 函数，把聚类标签取 反后作为预测标签；当 PC(Ur ) 介于 1−θ 和 θ 之 间，即认为聚类结果不适于指导标签预测，调用 reset(Ut ) 函数，用−1 表示 x∈Ut 的预测标签。 Ur ={x1, x2, x3} Ut ={y1, y2} U = Ur ∪Ut d (Ur) = [1 0 1] 例 1 对 ， ，有 ， 且 ，θ=0.9。 d ′ (Ut) = normal(Ut) = [1 0] 1) 如果 t(U)=[1 0 1 10], PC(Ur )=1>θ，所以 ； d ′ (Ut) = convert(Ut) = [1 0] 2) 如果 t(U)=[0 1 0 0 1]，PC(Ur )=0<1−θ，所以 ； d ′ (Ut) = reset(Ut) = [−1 −1] 3) 如果 t(U)=[0 0 0 0 1]，1-θ<PC(Ur )=0<1−θ，所 以 。 C C C 聚类学习器集合 将给样本 x∈Ut 标记| |个 聚类标签，并根据定义 (2) 和定义 (3) 得到| |个预 测标签。 Ci ∈ C di ′ (x) di ′ (x) ∈ {0,1} 定义 4 (一致性) 聚类学习器 对 x∈Ut 上的预测标签 ，且 ，那么集成标签 h(x) 的值为 h(x) =    d ′ (x), ∑ |C| i=1 di ′ (x) = |C| or ∑ |C| i=1 di ′ (x) = 0 −1, 其他 (5) 例 2 采用与例 1 中相同的 Ut 和 Ur，且| C |=3， d1 ′ (Ut) = [1 0] d2 ′ (Ut) = [1 1] d3 ′ (Ut) = [1 0] 若 C1 的预测标签 ，若 C2 的预测标签 ，若 C3 的预测 。 对 Ut = {y1, y2} 的结果为 ∑3 i=1 d ′ i 因为 (y1) = |C| = 3 ，所以 h(y1 )=1； ∑3 i=1 d ′ i 因为 (y2) = 2 ，所以 h(y2 )=−1。 2 算法设计与分析 本节首先描述算法的总体框架，然后进行算 法伪代码描述，最后分析算法复杂度。 2.1 算法总体方案 基于集成的半监督分类方法主要是通过集成 学习控制无标记样本的标注过程来减少未标记的 不确定性[12]。然而，目前在利用集成学习辅助半 监督学习方面的方法研究较少，主要是存在如下 矛盾：半监督学习适用于标记样本不足的情况， 然而传统的集成学习本身就需要大量的标记样本 进行训练[12]。针对上述问题，SUCE 综合聚类集 成与半监督学习，在已知标签较少的情况下，有 效提高分类器的精度。 如图 2 所示，基于聚类集成的半监督分类过 程为：第 1 个分图说明，首先通过聚类集成，将 B 中部分没有类别样本 C 的类标签预测出来；达 到“扩大”有类别的样本集合 (A 变成了 A+C)，“缩 小”了未标记类别集合 (B 变成了 B')。第 2 个分图 说明，对于扩大后的集合 (A+C) 利用分类模型，完 成预测没有类别的样本 B'。 未标记 数据A 未标记 数据B 已预测标 记数据C 已标记 数据A 未标记 数据B’ 未标记 数据B’ 聚类集成 聚类集成 分类 B=B’+C 已预测标 记数据C 未标记 数据B’ 分类模型 训练集 半监督学习监督学习 图 2 基于聚类集成的半监督分类示意图 Fig. 2 The diagram of semi-supervised classification based on clustering ensemble 2.2 算法描述 在训练阶段，本算法将依次对数据集进行 4 步处理，从而生成分类器： LUr 1) 通过 getLabel(Ur ) 获取训练集 Ur 的标签 。然后，利用 remove(Ur ) 对 Ur 去标签得到 Ur ′； 并将 Ur ′∪Ut 得到无标签 U。 ·976· 智 能 系 统 学 报 第 13 卷

第6期 闵帆，等：SUCE:基于聚类集成的半监督二分类方法 ·977· 2)通过多个基于EM、K-Means、Farthest- 26)end if First和HierarchicalClusterer等聚类算法的个体学 27)end for 习器对U进行全局聚类。根据已获取的Lu,计算 28)Lu.=classifier(UnU):∥分类 第i个聚类学习器L在U,上的聚类纯度PC()。 29)Lo,=getLabel(U); 如果PC()高于阈值O,L将继续参加集成学习， 30)Lu=combine(Lv,,Lu,); 并将L移入到学习器集合E中即EUL1。 2.3复杂度分析 3)对测试集的预测标签进行集成学习。通 为方便讨论，假设训练集U,的对象数量为n, 过h(x)一致性函数依次对测试集每个样本 条件属性数量为c,测试集U,的对象数量为m。 x∈U,的预测标签进行一致性处理。如果E中所 基学习器数量为E,迭代次数为1、聚类簇数为 有学习器对x的预测标签均一致，将预测标签 k。SUCE算法细分为以下4个阶段。 d(x)赋给x得到x'=(x,d(x)。x移人到训练集 1)对数据集进行去标签化预处理。在隐藏 U,U{x,同时在测试集中将其删除U{x}。 U,类标签之前，需先记录其真实类标签，如第 4)对扩大规模后的U,进行学习，再对缩减规 2)行所示再隐藏U,中的类标签，如第(3)行所 模后的U,进行分类Lu,=classifier(Un,U)得到U,的 示。至此，需要对U,进行两次遍历，共执行2n次 类标签Lu,;然后，获取U,的标签Lu,=getLabel(U,)o 计算。接下来是合并去标签后的U,和U构建无 最终得到U类标签Lu=combine(L,Lu,)o 标签论域U。第1阶段，计算机将共执行3n+m SUCE:基于集成聚类的半监督分类算法 次运算，故该阶段的时间复杂度为O(+m)。 算法SUCE 2)分别通过基于K-Means、EM、Farthest- 输入训练集U,测试集U,阈值； First和HierarchicalClusterer基学习器对U进行全 输出U,的类标签向量Lu,。 局聚类，如第5)~8)行所示。其时间复杂度分别 优化目标：最大化分类精度； 为O(k1(n+m)、O(ci(n+m)、O(k(n+m)、O(n+m) 1)U=0,E=0:1/初始化 lg(+m),然后计算基学习器的聚类纯度，并对其 2)Lu,=getLabel(U)/获取U,类标签 进行筛选，共执行×E次运算，如第913)行所示。 3)U;=remove(U,);1/隐藏U,类标签 所以，第2阶段的时间复杂度为O(n+m)(ct+(n+m) 4)U=UUU,: lg(m+m)。 5)L KMeans(U); 3)对U,中的对象进行一致化处理。遍历 6)L2=EM(U): U,中对象，共执行m次处理，如第14)-20)行所 7)L3=FarthestFirst(U); 示。然后将U,中置信度高的对象移入到U,如 8)L=HierarchicalCluster(U); 第21)~27)行所示，共执行2m次计算，故时间复 9)for(i=0,i<4;+)do1/筛选基学习器 杂度为O(m)。 10)if(PC(i)0)then 4)对扩展后的U,进行学习，并对U,进行分 11)EUL 类。该阶段的时间复杂度根据所采用的具体分类 12)end if 算法变化而变化。 13)end for 综上，因为第1、3、4阶段的时间复杂度远小 l4)for(eachxeU)do/标签一致性处理 于第2阶段。所以，SUCE的时间复杂度为 15)if (h(x)=d'(x))then O(n+m)(ct+(n+m)lg(+m)。为方便表述，数据 16)Lu,m=d'(x: 集规模n+m改写成U八，SUCE的时间复杂度为 17)else then OIUI(ct+IUllg(IUD)。 18)Lu,a=-1; 3实验及分析 19)end if 20)end for 本节通过实验回答以下3个问题：1)如何设 21)for(eachx∈U)do/扩充训练集 置合适的0阈值；2)SUCE应用于哪些基础算法 22)if (L.!=-1)then 效果更好；3)相比于流行的分类算法，SUCE能否 23)x=(x,d(x) 提高分类器的精度。 24)U,U{x: 3.1实验设置 25)U-{x: 实验采用了UCI数据库中的Sonar、Iono-

LUr Ll Ll Ll Ll 2) 通过多个基于 EM、K-Means、Farthest￾First 和 HierarchicalClusterer 等聚类算法的个体学 习器对 U 进行全局聚类。根据已获取的 ，计算 第 i 个聚类学习器 在 Ur 上的聚类纯度 PC(i)。 如果 PC(i) 高于阈值 θ， 将继续参加集成学习， 并将 移入到学习器集合 E 中即 E∪ 。 3) 对测试集的预测标签进行集成学习。通 过 h ( x ) 一致性函数依次对测试集每个样 本 x∈Ut 的预测标签进行一致性处理。如果 E 中所 有学习器对 x 的预测标签均一致，将预测标签 d'(x) 赋给 x 得到 x'=(x, d'(x))。x'移入到训练集 Ur∪{x'}，同时在测试集中将其删除 Ut -{x}。 LUt LUt LUr LU LUt LUr 4) 对扩大规模后的 Ur 进行学习，再对缩减规 模后的 Ut 进行分类 =classifier(Ur , Ut ) 得到 Ut 的 类标签 ；然后，获取 Ur 的标签 =getLabel(Ur )。 最终得到 U 类标签 =combine( , )。 SUCE：基于集成聚类的半监督分类算法 算法 SUCE 输入 训练集 Ur，测试集 Ut，阈值； 输出 Ut 的类标签向量 LUt。 优化目标：最大化分类精度； 1）U=Ø，E=Ø；//初始化 2） LUr=getLabel(Ur ) //获取 Ur 类标签 U ′ 3） r = remove (Ur) ； //隐藏 Ur 类标签 U = U ′ 4） r ∪Ut； 5） L1 = KMeans(U) ； 6） L2 = EM(U) ； 7） L3 = FarthestFirst(U) ； 8） L4 = HierarchicalCluster(U) ； 9）for (i=0; iθ) then 11）E∪ Ll 12）end if 13）end for 14）for (each x∈Ut ) do //标签一致性处理 h(x) = d ′ 15）if ( (x) ) then LUt(x) = d ′ 16） (x) ； 17）else then 18） LUt(x) = −1 ； 19）end if 20）end for 21）for (each x∈Ut ) do //扩充训练集 22）if ( LUt(x)! = −1 ) then 23）x'=(x, d'(x)) 24）Ur∪{x'}; 25）Ut -{x}; 26）end if 27）end for 28） LUt=classifier(Ur , Ut )；//分类 29） LUr=getLabel(Ur )； 30） LU =combine( LUt LUr , )； 2.3 复杂度分析 为方便讨论，假设训练集 Ur 的对象数量为 n， 条件属性数量为 c，测试集 Ut 的对象数量为 m。 基学习器数量为|E|， 迭代次数为 t、聚类簇数为 k。SUCE 算法细分为以下 4 个阶段。 1) 对数据集进行去标签化预处理。在隐藏 Ur 类标签之前，需先记录其真实类标签，如第 2) 行所示再隐藏 Ur 中的类标签，如第 (3) 行所 示。至此，需要对 Ur 进行两次遍历，共执行 2n 次 计算。接下来是合并去标签后的 Ur 和 Ut，构建无 标签论域 U。第 1 阶段，计算机将共执行 3n+m 次运算，故该阶段的时间复杂度为 O(n+m)。 O((n+m) (ct+(n+m) lg(n+m) )) 2) 分别通过基于 K-Means、EM、Farthest￾First 和 HierarchicalClusterer 基学习器对 U 进行全 局聚类，如第 5)~8) 行所示。其时间复杂度分别 为 O(kt(n+m))、O(ct(n+m))、O(k(n+m))、O((n+m) 2 lg(n+m))，然后计算基学习器的聚类纯度，并对其 进行筛选，共执行 n×|E|次运算，如第 9)~13) 行所示。 所以，第 2 阶段的时间复杂度为 。 3) 对 Ut 中的对象进行一致化处理。遍历 Ut 中对象，共执行 m 次处理，如第 14)-20) 行所 示。然后将 Ut 中置信度高的对象移入到 Ur，如 第 21)~27) 行所示，共执行 2m 次计算，故时间复 杂度为 O(m)。 4) 对扩展后的 Ur 进行学习，并对 Ut 进行分 类。该阶段的时间复杂度根据所采用的具体分类 算法变化而变化。 O ( (n+m) ( ct+(n+m)lg(n+m) )) O ( |U| ( ct+|U|lg(|U|) )) 综上，因为第 1、3、4 阶段的时间复杂度远小 于 第 2 阶段。所以， SUCE 的时间复杂度为 。为方便表述，数据 集规模 n+m 改写成|U|，SUCE 的时间复杂度为 。 3 实验及分析 本节通过实验回答以下 3 个问题：1) 如何设 置合适的 θ 阈值；2) SUCE 应用于哪些基础算法 效果更好；3) 相比于流行的分类算法，SUCE 能否 提高分类器的精度。 3.1 实验设置 实验采用了 UCI 数据库中的 Sonar、Iono- 第 6 期 闵帆，等：SUCE：基于聚类集成的半监督二分类方法 ·977·

·978· 智能系统学报 第13卷 sphere、Wdbc和Voting4个数据集。Sonar、Wd- 达14%的精度提升。然而，SUCE对Naive Bayes bc是连续型数据，因此通过Weka应用默认方法 算法的改进不明显。 对其进行离散化处理。 根据UCI数据集的样本数量，实验设置的训 0.78 练集规模分别为2%、4%、6%、8%、10%、12%、 0.76 0.74 14%和16%。在测试集中，样本标签不可见，直 0.72 到所有的未分类样本都得到预测标签。为减小实 0.70 0.68 验随机误差，每个结果均为200次相同实验的平 0.66 均值。所有（对比）实验均采用上述相同的实验 0.14 0.10 参数，如表1所示。 训练集比例 0.06 0020700.7万000.8500 阙值0 (a)Sonar 表1数据集的描述 Table 1 Description of the data set 序号 数据集 样本数 特征数 类别数 1 Sonar 208 61 2 0.85 0.83 2 Wdbc 569 31 2 0.8 3 lonosphere 351 35 2 0.77 Voting 435 1> 0.14 0.10 3.2实验结果与分析 训练集比例 .06 02508008090 0.020.7 阀值0 图3显示了Sonar、Wdbc、Ionosphere和Vot- (b)lonosphere ing数据集在不同阈值0和训练集规模下的平均 分类精度变化。通过实验数据观察发现，=0.8左 右时，SUCE在4个数据集上均能取得最好的分 0.93 类效果。在Sonar和Voting数据集上，对于不同 的0取值，随着训练集规模的扩大，平均分类精度 09 会呈现出先增加后趋于稳定的趋势。因为随着阈 0.905 0.14 0.90 值0的提高，筛选过后还保留的个体学习器通常 0.10 0.85 会变得更少，所以获得的样本标签并没有提高， 调练集比例 0.80 0.06 0.75 0.020.70 阀值0 从而导致分类效果没有提升。对于Ionosphere和 (c)Wdbc Wdbc,训练集规模并不太影响平均分类精度。 表2显示了SUCE作用在ID3、J48、Bayes、 0.90 kNN、Logistic、OneR等基础算法上，并对Sonar、 0.88 0.86 Wdbc、Ionosphere和Voting数据集进行半监督分 0.84 类的分类结果。实验参数设置为：0=0.8，训练集 0.82 0.80 比例=4%。Win值的计算如下：在某一数据集上， 0.78 如果某种算法效果比其对比算法精度高1%以 0.76 0.14 上，则该算法得1分；否则两种算法效果相当且均 0.10 不得分。 训练集比例 .06 002070075080085090 阙值0 (d)Voting 通过表2可以统计发现，SUCE获胜14次，打 图3SUCE-D3在不同数据集上的分类比较 平5次，失败5次。在Sonar、Wdbc和Ionosphere Fig.3 The diagram of comparison of SUCE-ID3 classifica- 数据集上的分类效果要优于基础算法。但SUCE tion on different datasets 在Voting数据集上对基础算法分类效果的提升 现在可以回答本节提出的问题。1)取为 不明显。 0.8左右较合适；2)SUCE应用于ID3、C4.5、OneR SUCE更适用于ID3、C4.5、OneR等基础算 等基础算法效果更好；3)相比基础算法，SUCE通 法。例如，在Sonar数据上，SUCE-C4.5获得了高 常可以提高分类器的精度

sphere、Wdbc 和 Voting4 个数据集。Sonar、Wd￾bc 是连续型数据，因此通过 Weka 应用默认方法 对其进行离散化处理。 根据 UCI 数据集的样本数量，实验设置的训 练集规模分别为 2%、4%、6%、8%、10%、12%、 14% 和 16%。在测试集中，样本标签不可见，直 到所有的未分类样本都得到预测标签。为减小实 验随机误差，每个结果均为 200 次相同实验的平 均值。所有 (对比) 实验均采用上述相同的实验 参数，如表 1 所示。 表 1 数据集的描述 Table 1 Description of the data set 序号 数据集 样本数 特征数 类别数 1 Sonar 208 61 2 2 Wdbc 569 31 2 3 Ionosphere 351 35 2 4 Voting 435 17 2 3.2 实验结果与分析 图 3 显示了 Sonar、Wdbc、Ionosphere 和 Vot￾ing 数据集在不同阈值 θ 和训练集规模下的平均 分类精度变化。通过实验数据观察发现，θ=0.8 左 右时，SUCE 在 4 个数据集上均能取得最好的分 类效果。在 Sonar 和 Voting 数据集上，对于不同 的 θ 取值，随着训练集规模的扩大，平均分类精度 会呈现出先增加后趋于稳定的趋势。因为随着阈 值 θ 的提高，筛选过后还保留的个体学习器通常 会变得更少，所以获得的样本标签并没有提高， 从而导致分类效果没有提升。对于 Ionosphere 和 Wdbc，训练集规模并不太影响平均分类精度。 表 2 显示了 SUCE 作用在 ID3、J48、Bayes、 kNN、Logistic、OneR 等基础算法上，并对 Sonar、 Wdbc、Ionosphere 和 Voting 数据集进行半监督分 类的分类结果。实验参数设置为：θ=0.8，训练集 比例=4%。Win 值的计算如下：在某一数据集上， 如果某种算法效果比其对比算法精度高 1% 以 上，则该算法得 1 分；否则两种算法效果相当且均 不得分。 通过表 2 可以统计发现，SUCE 获胜 14 次，打 平 5 次，失败 5 次。在 Sonar、Wdbc 和 Ionosphere 数据集上的分类效果要优于基础算法。但 SUCE 在 Voting 数据集上对基础算法分类效果的提升 不明显。 SUCE 更适用于 ID3、C4.5、OneR 等基础算 法。例如，在 Sonar 数据上，SUCE-C4.5 获得了高 达 14% 的精度提升。然而，SUCE 对 Naive Bayes 算法的改进不明显。 0.66 0.68 0.70 0.72 0.74 0.76 0.78 平均分类精度 0.77 0.79 0.81 0.83 0.85 平均分类精度 0.905 0.915 0.925 0.935 平均分类精度 0.76 0.78 0.80 0.82 0.84 0.86 0.88 0.90 (d) Voting 0.70 0.75 0.80 0.85 0.90 0.02 0.06 0.10 0.14 阈值 θ 训练集比例 (c) Wdbc 0.70 0.75 0.80 0.85 0.90 0.02 0.06 0.10 0.14 阈值 θ 训练集比例 (b) Ionosphere 0.70 0.75 0.80 0.85 0.90 0.02 0.06 0.10 0.14 阈值 θ 训练集比例 (a) Sonar 0.70 0.75 0.80 0.85 0.90 0.02 0.06 0.10 0.14 阈值 θ 训练集比例 平均分类精度 图 3 SUCE-ID3 在不同数据集上的分类比较 Fig. 3 The diagram of comparison of SUCE-ID3 classifica￾tion on different datasets 现在可以回答本节提出的问题。 1 ) 取 为 0.8 左右较合适；2) SUCE 应用于 ID3、C4.5、OneR 等基础算法效果更好；3) 相比基础算法，SUCE 通 常可以提高分类器的精度。 ·978· 智 能 系 统 学 报 第 13 卷

第6期 闵帆，等：SUCE:基于聚类集成的半监督二分类方法 ·979· 表2SUCE与基础算法分类精度对比 Table 2 Comparing the classification accuracy of SUCE and basic algorithms 算法 数据库 Sonar Wdbc Ionosphere Voting Win Initial 0.63475±0.01427 0.87889±0.00173 0.74881±0.006820.8785940.00506 0 ID3 SUCE-ID3 0.75938±0.00660 0.92642±0.00002 0.82184±0.00264 0.87136±0.00301 3 Initial 0.61256±0.01841 0.86316±001400 0.75089±0.01118 0.90419±0.00678 1 C4.5 SUCE-C4.5 0.75213±0.00691 0.91545±0.00001 0.81990±0.00232 0.86992±0.00358 3 Initial 0.77182±0.00596 0.94954±0.00003 0.88413±0.00226 0.89318±0.00138 1 Naive Bayes SUCE-Bayes 0.78388±0.00593 0.94269±0.00002 0.87540±0.00182 0.86502±0.00074 1 Initial 0.68625±0.01037 0.92989±0.00005 0.82418±0.00209 0.90371±0.00197 1 kNN SUCE-ANN 0.78438±0.00766 0.93565±0.00004 0.86175±0.00203 0.85701±0.00088 2 Initial 0.66652±0.00933 0.91316±0.00002 0.84911±0.00183 0.89115±0.00207 1 Logistic SUCE-Logistic 0.77988±0.00703 0.92916±0.00002 0.84113±0.00181 0.84803±0.00127 2 Initial 0.62755±0.01424 0.877150.00124 0.75890±0.00550 0.90586±0.00647 1 OneR SUCE-OneR 0.76213±0.00612 0.90896±0.00004 0.82674±0.00205 0.87232±0.00403 3 4结束语 hidden Markov models[J].Journal of visual languages and computing,2009,20(3):188-195 本文提出的基于集成聚类的半监督二分类算 [8]SHAHSHAHANI B M,LANDGREBE D A.The effect of 法SUCE解决了样本过少情况下的分类效果较差 unlabeled samples in reducing the small sample size prob- 的问题。优点在于通过集成聚类的学习充分挖掘 lem and mitigating the Hughes phenomenon[J].IEEE 大量未标记样本中的重要信息，而不需要去求助 transactions on geoscience and remote sensing,1994, 外界来解决，降低了学习的成本。在未来的工作 32(5):1087-1095 中，进一步研究以下3个方向：1)由目前只能解 [9]梁吉业，高嘉伟，常瑜.半监督学习研究进展[U.山西大 决二分类问题过渡到多分类问题；2)加入更多学 学学报：自然科学版，2009,32(4)：528-534 习能力强的聚类算法，扩大集成学习个体学习器 LIANG Jiye,GAO Jiawei,CHANG Yu.The research and 的规模；3)引入代价敏感，增强集成学习的能力。 advances on semi-supervised learning[J].Journal of Shanxi university:natural science edition,2009,32(4):528-534. 参考文献： [10]MERZ C J,ST CLAIR D C,BOND W E.Semi-super- [1]MITCHELL T M.机器学习M.曾华军，张银奎，译.北 vised adaptive resonance theory (SMART2)[Cl//Proceed- 京：机械工业出版社.2003. ings of 1992 International Joint Conference on Neural [2]ZHU Xiaojin.Semi-supervised learning literature Networks.Baltimore,USA,1992:851-856. survey[R].Madison:University of Wisconsin,2008: [11]VEGA-PONS S,RUIZ-SHULCLOPER J.A survey of 63-77. clustering ensemble algorithms[J].International journal of [3]张晨光，张燕半监督学习M.北京：中国农业科学技术 pattern recognition and artificial intelligence,2011,25(3): 出版社.2013. 337-372 [4]周志华.机器学习M).北京：清华大学出版社，2016 [12]蔡毅，朱秀芳，孙章丽，等.半监督集成学习综述U.计 [5]NIGAM K,MCCALLUM A K,THRUN S,et al.Text 算机科学，2017,44(6A:7-13. classification from labeled and unlabeled documents using CAI Yi,ZHU Xiufang,SUN Zhangli,et al.Semi-super- EM[J].Machine learning,2000,39(2/3):103-134 vised and ensemble learning:a review[J].Computer sci- [6]SONG Yangqiu,ZHANG Changshui,LEE J,et al.Semi- ence,2017,446A):7-13. supervised discriminative classification with application to [13]曾令伟，伍振兴，杜文才.基于改进自监督学习群体智 tumorous tissues segmentation of MR brain images[J].Pat- 能(ISLCI)的高性能聚类算法.重庆邮电大学学报： tern analysis and applications,2009,12(2):99-115. 自然科学版，2016,28(1)：131-137 [7]FENG Wei,XIE Lei,Zeng Jia,et al.Audio-visual human ZENG Lingwei,WU Zhenxing,DU Wencai.Improved recognition using semi-supervised spectral learning and Self supervised learning collection intelligence based high

4 结束语 本文提出的基于集成聚类的半监督二分类算 法 SUCE 解决了样本过少情况下的分类效果较差 的问题。优点在于通过集成聚类的学习充分挖掘 大量未标记样本中的重要信息，而不需要去求助 外界来解决，降低了学习的成本。在未来的工作 中，进一步研究以下 3 个方向：1) 由目前只能解 决二分类问题过渡到多分类问题；2) 加入更多学 习能力强的聚类算法，扩大集成学习个体学习器 的规模；3) 引入代价敏感，增强集成学习的能力。 参考文献： MITCHELL T M. 机器学习[M]. 曾华军, 张银奎, 译. 北 京: 机械工业出版社, 2003. [1] ZHU Xiaojin. Semi-supervised learning literature survey[R]. Madison: University of Wisconsin, 2008: 63–77. [2] 张晨光, 张燕. 半监督学习[M]. 北京: 中国农业科学技术 出版社, 2013. [3] [4] 周志华. 机器学习[M]. 北京: 清华大学出版社, 2016. NIGAM K, MCCALLUM A K, THRUN S, et al. Text classification from labeled and unlabeled documents using EM[J]. Machine learning, 2000, 39(2/3): 103–134. [5] SONG Yangqiu, ZHANG Changshui, LEE J, et al. Semi￾supervised discriminative classification with application to tumorous tissues segmentation of MR brain images[J]. Pat￾tern analysis and applications, 2009, 12(2): 99–115. [6] FENG Wei, XIE Lei, Zeng Jia, et al. Audio-visual human recognition using semi-supervised spectral learning and [7] hidden Markov models[J]. Journal of visual languages and computing, 2009, 20(3): 188–195. SHAHSHAHANI B M, LANDGREBE D A. The effect of unlabeled samples in reducing the small sample size prob￾lem and mitigating the Hughes phenomenon[J]. IEEE transactions on geoscience and remote sensing, 1994, 32(5): 1087–1095. [8] 梁吉业, 高嘉伟, 常瑜. 半监督学习研究进展[J]. 山西大 学学报: 自然科学版, 2009, 32(4): 528–534. LIANG Jiye, GAO Jiawei, CHANG Yu. The research and advances on semi-supervised learning[J]. Journal of Shanxi university: natural science edition, 2009, 32(4): 528–534. [9] MERZ C J, ST CLAIR D C, BOND W E. Semi-super￾vised adaptive resonance theory (SMART2)[C]//Proceed￾ings of 1992 International Joint Conference on Neural Networks. Baltimore, USA, 1992: 851–856. [10] VEGA-PONS S, RUIZ-SHULCLOPER J. A survey of clustering ensemble algorithms[J]. International journal of pattern recognition and artificial intelligence, 2011, 25(3): 337–372. [11] 蔡毅, 朱秀芳, 孙章丽, 等. 半监督集成学习综述[J]. 计 算机科学, 2017, 44(6A): 7–13. CAI Yi, ZHU Xiufang, SUN Zhangli, et al. Semi-super￾vised and ensemble learning: a review[J]. Computer sci￾ence, 2017, 44(6A): 7–13. [12] 曾令伟, 伍振兴, 杜文才. 基于改进自监督学习群体智 能 (ISLCI) 的高性能聚类算法[J]. 重庆邮电大学学报: 自然科学版, 2016, 28(1): 131–137. ZENG Lingwei, WU Zhenxing, DU Wencai. Improved Self supervised learning collection intelligence based high [13] 表 2 SUCE 与基础算法分类精度对比 Table 2 Comparing the classification accuracy of SUCE and basic algorithms 算法 数据库 Sonar Wdbc Ionosphere Voting Win ID3 Initial 0.634 75±0.014 27 0.878 89±0.001 73 0.748 81±0.006 82 0.878 59±0.005 06 0 SUCE-ID3 0.759 38±0.006 60 0.926 42±0.000 02 0.821 84±0.002 64 0.871 36±0.003 01 3 C4.5 Initial 0.612 56±0.018 41 0.863 16±0014 00 0.750 89±0.011 18 0.904 19±0.006 78 1 SUCE-C4.5 0.752 13±0.006 91 0.915 45±0.000 01 0.819 90±0.002 32 0.869 92±0.003 58 3 Naive Bayes Initial 0.771 82±0.005 96 0.949 54±0.000 03 0.884 13±0.002 26 0.893 18±0.001 38 1 SUCE-Bayes 0.783 88±0.005 93 0.942 69±0.000 02 0.875 40±0.001 82 0.865 02±0.000 74 1 kNN Initial 0.686 25±0.010 37 0.929 89±0.000 05 0.824 18±0.002 09 0.903 71±0.001 97 1 SUCE-kNN 0.784 38±0.007 66 0.935 65±0.000 04 0.861 75±0.002 03 0.857 01±0.000 88 2 Logistic Initial 0.666 52±0.009 33 0.913 16±0.000 02 0.849 11±0.001 83 0.891 15±0.002 07 1 SUCE-Logistic 0.779 88±0.007 03 0.929 16±0.000 02 0.841 13±0.001 81 0.848 03±0.001 27 2 OneR Initial 0.627 55±0.014 24 0.877 15±0.001 24 0.758 90±0.005 50 0.905 86±0.006 47 1 SUCE-OneR 0.762 13±0.006 12 0.908 96±0.000 04 0.826 74±0.002 05 0.872 32±0.004 03 3 第 6 期 闵帆，等：SUCE：基于聚类集成的半监督二分类方法 ·979·

·980· 智能系统学报 第13卷 performance data clustering approach[J].Journal of YANG Yumei.Improved K-means dynamic clustering al- Chongqing university of posts and telecommunications: gorithm based on information entropy[J].Journal of natural science edition,2016,28(1):131-137. Chongqing university of posts and telecommunications: [14]STREHL A.GHOSH J.Cluster ensembles-a know- natural science edition,2016,28(2):254-259. ledge reuse framework for combining partitionings[J]. [23]JAMSHIDIAN M,JENNRICH R I.Standard errors for Journal of machine learning research,2002,3:583-617. EM estimation[J].Journal of the royal statistical society. [15]FRED A L N,JAIN A K.Data clustering using evidence series B.2000,62(2):257-270. accumulation[C]//Proceedings of the 16th International [24]DEEPSHREE A V,YOGISH H K.Farthest first cluster- Conference on Pattern Recognition.Quebec,Canada, ing in links reorganization[J].International journal of web 2002:276-280. and semantic technology,2014,5(3):17-24. [16]ZHOU Zhihua.Ensemble Methods:Foundations and Al- [25]RASHEDI E,MIRZAEI A.A hierarchical clusterer en- gorithms[M].Boca Raton:Taylor and Francis Group, semble method based on boosting theory[J].Knowledge- 2012:135-156. based systems,2013,45:83-93. [17]ZHANG Minling,ZHOU Zhihua.Exploiting unlabeled 作者简介： data to enhance ensemble diversity[J].Data mining and 闵帆，男，1973年生，教授，博士 knowledge discovery,2013,26(1):98-129. 生导师，主要研究方向为粒计算、代价 [18]MIN Fan,HU Qinghua,ZHU W.Feature selection with 敏感学习、推荐系统，主持国家自然科 test cost constraint[J].International journal of approxim- 学基金1项。发表学术论文100余 ate reasoning,2014,55(1:167-179. 篇，被SCI检索30余篇。 [19]GIONIS A,MANNILA H,TSAPARAS P.Clustering ag- gregation[M]//SAMMUT C,WEBB G I.Encyclopedia of Machine Learning.Boston:Springer,2011. 王宏杰，男，1992年生，硕士研究 [20]罗会兰，孔繁胜，李一啸.聚类集成中的差异性度量研 生，主要研究方向为粒计算、代价敏感 究.计算机学报，2007,30(8)：1315-1324. 学习。发表学术论文7篇，其中被 EI检索1篇。 LUO Huilan,KONG Fansheng,LI Yixiao.An analysis of diversity measures in clustering ensembles[J].Chinese journal of computers,2007,30(8):1315-1324 [21]杨草原，刘大有，杨博，等.聚类集成方法研究刀.计算 机科学，2011,38(2)：166-170. 刘福伦，男，1993年生，硕士研究 YANG Caoyuan,LIU Dayou,YANG Bo,et al.Research 生，主要研究方向为代价敏感学习、粗 糙集。发表学术论文5篇，其中被 on cluster aggregation approaches[J].Computer science, SCI检索2篇，被EI检索1篇。 2011,38(2):166-170. [22]杨玉梅.基于信息嫡改进的K-means动态聚类算法[]， 重庆邮电大学学报：自然科学版，2016,28(2：254-259

performance data clustering approach[J]. Journal of Chongqing university of posts and telecommunications: natural science edition, 2016, 28(1): 131–137. STREHL A, GHOSH J. Cluster ensembles—a know￾ledge reuse framework for combining partitionings[J]. Journal of machine learning research, 2002, 3: 583–617. [14] FRED A L N, JAIN A K. Data clustering using evidence accumulation[C]//Proceedings of the 16th International Conference on Pattern Recognition. Quebec, Canada, 2002: 276–280. [15] ZHOU Zhihua. Ensemble Methods: Foundations and Al￾gorithms[M]. Boca Raton: Taylor and Francis Group, 2012: 135–156. [16] ZHANG Minling, ZHOU Zhihua. Exploiting unlabeled data to enhance ensemble diversity[J]. Data mining and knowledge discovery, 2013, 26(1): 98–129. [17] MIN Fan, HU Qinghua, ZHU W. Feature selection with test cost constraint[J]. International journal of approxim￾ate reasoning, 2014, 55(1): 167–179. [18] GIONIS A, MANNILA H, TSAPARAS P. Clustering ag￾gregation[M]//SAMMUT C, WEBB G I. Encyclopedia of Machine Learning. Boston: Springer, 2011. [19] 罗会兰, 孔繁胜, 李一啸. 聚类集成中的差异性度量研 究[J]. 计算机学报, 2007, 30(8): 1315–1324. LUO Huilan, KONG Fansheng, LI Yixiao. An analysis of diversity measures in clustering ensembles[J]. Chinese journal of computers, 2007, 30(8): 1315–1324. [20] 杨草原, 刘大有, 杨博, 等. 聚类集成方法研究[J]. 计算 机科学, 2011, 38(2): 166–170. YANG Caoyuan, LIU Dayou, YANG Bo, et al. Research on cluster aggregation approaches[J]. Computer science, 2011, 38(2): 166–170. [21] 杨玉梅. 基于信息熵改进的 K-means 动态聚类算法[J]. 重庆邮电大学学报: 自然科学版, 2016, 28(2): 254–259. [22] YANG Yumei. Improved K-means dynamic clustering al￾gorithm based on information entropy[J]. Journal of Chongqing university of posts and telecommunications: natural science edition, 2016, 28(2): 254–259. JAMSHIDIAN M, JENNRICH R I. Standard errors for EM estimation[J]. Journal of the royal statistical society. series B, 2000, 62(2): 257–270. [23] DEEPSHREE A V, YOGISH H K. Farthest first cluster￾ing in links reorganization[J]. International journal of web and semantic technology, 2014, 5(3): 17–24. [24] RASHEDI E, MIRZAEI A. A hierarchical clusterer en￾semble method based on boosting theory[J]. Knowledge￾based systems, 2013, 45: 83–93. [25] 作者简介： 闵帆，男，1973 年生，教授，博士 生导师，主要研究方向为粒计算、代价 敏感学习、推荐系统，主持国家自然科 学基金 1 项。发表学术论文 100 余 篇，被 SCI 检索 30 余篇。 王宏杰，男，1992 年生，硕士研究 生，主要研究方向为粒计算、代价敏感 学习。发表学术论文 7 篇，其中被 EI 检索 1 篇。 刘福伦，男，1993 年生，硕士研究 生，主要研究方向为代价敏感学习、粗 糙集。发表学术论文 5 篇，其中被 SCI 检索 2 篇，被 EI 检索 1 篇。 ·980· 智 能 系 统 学 报 第 13 卷