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