·230· 智能系统学报 第15卷 质量可靠，本着“宁缺毋滥”的原则，因此我们需 众包集C,专家集 要计算出噪声比例的上限。 P,参数=5 由式(1)可计算贴标者错误率为g,通过投票 法整合J个标记者，超过半数正确则集成结果正 众包标签集多数投票形成 标签集Lc 确。在这里，各个标记者错误率可视为相互独立， 可由Hoeffding不等式推导出集成错误率的上限： 由式(1)、(6)计算噪声数 0= ()1-g≤ 量上限noise num (5) ep-21-2g =Omax N M≤MR noise_num=Qmax·I= exp-1-2q)).1 (6) 分别取第1、2、…、J个标记者所标记的数据训练 按a大小对所有实例进行降序排序，我们可 模型，对专家集和原始数据集扩维，用扩维后的专 家集训练模型并对扩维后的原始数据集进行预测 以将集成标签集分为两部分：前noise_num个标 签为待进一步处理的含噪声集，其余为可靠的保 留集。 与集成标签比较，由式(2)计算c,并形成辅助集H 2.4噪声校正部分 目前，关于噪声校正的研究数量较少，且一些 实验也证明校正噪声是比较困难的。一种直接的 由式(4)计算a,将所有实例按a,降序排列，前 noise num为含噪声集，其余为保留集 思路是，在分离出含噪声的集合后，用高质量集 直接训练模型对噪声集进行校正，但效果不理想。 为了提高分离出的高质量集所训练的模型的 分别取第1、2、·、M个辅助集训练模型，对保留集 和含噪声集扩维，用扩维后的保留集训练模型并对扩维 泛化能力，我们再次使用扩维的方法：噪声识别 后的含噪声集进行预测，重复轮 过程中，每轮扩维预测后，每个实例i均获得一个 标签l,若l=,则将实例i加入辅助集Hm中，共 对个校正结果进行投票，作为校正结果，与保留集 获得M个辅助集{H1,H2,…,Hw。和识别部分类似，用 合并，返回最终结果 之前得到的辅助集{H,H2,…,Hw}分别训练得到 图2算法流程图 模型2，促，…，h必)，对噪声集和保留集扩维并进 Fig.2 Flowchart of the proposed method 行预测，重复M轮，用投票法整合所得的M个标 签集合，作为对噪声集的校正结果。把校正后的 3实验结果分析 结果和保留集合并为最终结果。 由上文所述，众包通常关注于两个结果：1)标 2.5完整框架 签本身质量：2)训练所得模型的质量。因此在这 该算法主要时间消耗在于对专家集扩维、对 里分别进行实验。基础的学习模型均采用决策 保留集扩维两个部分，且与所选择的基础算法￡ 树，由python的sklearn库实现，参数均取默认值， 有关。设基础学习算法对实例数为n的众包集训 取M=5 练及预测的时间复杂度为T(),则本方法的时间 3.1实验数据 复杂度为M[J.T(n)+T(nr]+M[M.T(')+T(m"], 实验数据来自UCI机器学习库的8个数据 其中，M为预设重复轮数，J为众包者数量，r为专 集，它们具有不同的数量的实例，不同的类分布， 家集比例，n'为辅助集实例数，n"为噪声集实例 不同数量的特征及其类型，以便验证本方法在不 数，以上均为常数，且Mn,J≤n,0<r<1,n'<n, 同情况下的适用性。其中4个为较小规模数据 n"<n。由此可见本方法的时间复杂度取决于所选 集，4个为较大规模数据集。在模拟实验中不对 择的基础算法时间复杂度。完整流程图如图2 数据集本身做任何特征处理。数据集具体情况如 所示。 表1。质量可靠，本着“宁缺毋滥”的原则，因此我们需 要计算出噪声比例的上限。 由式 (1) 可计算贴标者错误率为 q，通过投票 法整合 J 个标记者，超过半数正确则集成结果正 确。在这里，各个标记者错误率可视为相互独立， 可由 Hoeffding 不等式推导出集成错误率的上限[15] ： Q = ∑ ⌊J/2⌋ k=0 ( J k ) q J−k (1−q) k ⩽ exp( − 1 2 J(1−2q) 2 ) = Qmax (5) noise_num = Qmax ·I = exp( − 1 2 J(1−2q) 2 ) ·I (6) 按 αi 大小对所有实例进行降序排序，我们可 以将集成标签集分为两部分：前 noise_num 个标 签为待进一步处理的含噪声集，其余为可靠的保 留集。 2.4 噪声校正部分 目前，关于噪声校正的研究数量较少，且一些 实验也证明校正噪声是比较困难的。一种直接的 思路是，在分离出含噪声的集合后，用高质量集 直接训练模型对噪声集进行校正，但效果不理想。 li = yˆi {H1,H2,··· ,HM} {H1,H2,··· ,HM} { h 1 C ,h 2 C ,··· ,h M C } 为了提高分离出的高质量集所训练的模型的 泛化能力，我们再次使用扩维的方法：噪声识别 过程中，每轮扩维预测后，每个实例 i 均获得一个 标签 li，若 ，则将实例 i 加入辅助集 Hm 中，共 获得M个辅助集 。和识别部分类似，用 之前得到的辅助集 分别训练得到 模型 ，对噪声集和保留集扩维并进 行预测，重复 M 轮，用投票法整合所得的 M 个标 签集合，作为对噪声集的校正结果。把校正后的 结果和保留集合并为最终结果。 2.5 完整框架 L M [J ·T (n)+T (nr)]+ M [M ·T (n ′ )+T (n ′′)] M ≪ n J ≪ n 该算法主要时间消耗在于对专家集扩维、对 保留集扩维两个部分，且与所选择的基础算法 有关。设基础学习算法对实例数为 n 的众包集训 练及预测的时间复杂度为 T(n)，则本方法的时间 复杂度为 ， 其中，M 为预设重复轮数，J 为众包者数量，r 为专 家集比例，n'为辅助集实例数，n''为噪声集实例 数，以上均为常数，且 ， ，0<r<1，n'<n， n''<n。由此可见本方法的时间复杂度取决于所选 择的基础算法时间复杂度。完整流程图如图 2 所示。 众包集C，专家集 P，参数m=5 众包标签集多数投票形成 标签集LC 由式（1）、（6）计算噪声数 量上限noise_num M≤M? 分别取第1、2、…、J个标记者所标记的数据训练 模型，对专家集和原始数据集扩维，用扩维后的专 家集训练模型并对扩维后的原始数据集进行预测 与集成标签比较，由式（2）计算ci，并形成辅助集Hm 由式（4）计算ai，将所有实例按ai降序排列，前 noise_num为含噪声集，其余为保留集 分别取第1、2、…、M个辅助集训练模型，对保留集 和含噪声集扩维，用扩维后的保留集训练模型并对扩维 后的含噪声集进行预测，重复M轮 对M个校正结果进行投票，作为校正结果，与保留集 合并，返回最终结果 Y N 图 2 算法流程图 Fig. 2 Flowchart of the proposed method 3 实验结果分析 由上文所述，众包通常关注于两个结果：1) 标 签本身质量；2) 训练所得模型的质量。因此在这 里分别进行实验。 基础的学习模型均采用决策 树，由 python 的 sklearn 库实现，参数均取默认值， 取 M=5。 3.1 实验数据 实验数据来自 UCI 机器学习库的 8 个数据 集，它们具有不同的数量的实例，不同的类分布， 不同数量的特征及其类型，以便验证本方法在不 同情况下的适用性。其中 4 个为较小规模数据 集，4 个为较大规模数据集。在模拟实验中不对 数据集本身做任何特征处理。数据集具体情况如 表 1。 ·230· 智 能 系 统 学 报 第 15 卷