第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 ensemble[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 improve classification accuracy. This paper proposes a new method called Semi-sUpervised classification through Clustering 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] 、FarthestFirst[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,)<1-0 (4) 学习控制无标记样本的标注过程来减少未标记的 reset(U,),1-0<PC(U,)<0 不确定性。然而，目前在利用集成学习辅助半 式中： 监督学习方面的方法研究较少，主要是存在如下 normal(U)=[o(d(x)t(x》…r(d(xw)r(, convert(U,)=[o(d()1-1(x》…c(d(）1-1(ul, 矛盾：半监督学习适用于标记样本不足的情况， reset(U,)=-lu,xt,且x∈U,i=1,2,…,lUlo 然而传统的集成学习本身就需要大量的标记样本 本文用t(x)和d(x)分别表示样本xeU,的聚 进行训练。针对上述问题，SUCE综合聚类集 类标签和预测标签。0是用户设置的阈值，当 成与半监督学习，在已知标签较少的情况下，有 效提高分类器的精度。 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) < 1−θ reset(Ut), 1−θ < PC(Ur) < θ (4) normal(Ut) = [ σ(d ′ (x1) t(x1)) ··· σ ( d ′ ( x|Ut | ) t ( x|Ut | ))], convert(Ut) = [ σ(d ′ (x1) 1−t(x1)) ··· σ ( d ′ ( x|Ut | ) 1−t ( x|Ut | ))], reset(Ut) = −1Ut×1 ,且xi ∈ Ut ,i = 1,2,··· ,|Ut | 式中： 。 本文用 t(x) 和 d'(x) 分别表示样本 x∈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、FarthestFirst 和 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<4; i++) do //筛选基学习器 10） if (PC(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、FarthestFirst 和 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、Wdbc 是连续型数据，因此通过 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 和 Voting 数据集在不同阈值 θ 和训练集规模下的平均 分类精度变化。通过实验数据观察发现，θ=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 classification on different datasets 现在可以回答本节提出的问题。 1 ) 取 为 0.8 左右较合适；2) SUCE 应用于 ID3、C4.5、OneR 等基础算法效果更好；3) 相比基础算法，SUCE 通 常可以提高分类器的精度。 ·978· 智 能 系 统 学 报 第 13 卷