第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·