一种用于多标签分类的进化式伪标记方法

《Applied Soft Computing》：False flag: An evolutionary false labeling approach for multilabel classification

　　

多标签分类（multilabel classification）用于处理每个样本可同时属于多个二元类别（binary classes，即标签）的情形。与单标签分类相比，多标签数据集的学习任务更为困难。除其内在复杂性外，低标签密度数据集、标签噪声以及标签间复杂关系均使该问题变得极具挑战性。论文提出一种新的方法——伪标记（false flag labeling），其核心是通过修改训练集中实例的标签，构造新的训练集，以提升分类模型的性能。研究人员假设，在训练集中为实例添加新的相关标签，或移除其中已有的相关标签，可能改善学习算法的结果，使分离超曲面（separation surfaces）的搜索更为容易。该方法并不假设新增标签一定对应于数据集标注过程中被遗漏的真实标签，也不假设被移除的标签一定对应于错误标注的实例。研究采用进化算法（evolutionary algorithm）将伪标记过程建模为一个优化过程。基于50个数据集和7种分类模型的大规模比较实验表明，该方法具有优越的性能。

该文发表于《Applied Soft Computing》，围绕多标签分类（multilabel classification）中训练集标签配置是否可以被主动优化这一核心问题，提出了“伪标记学习（false flag learning）”框架。研究背景在于，多标签学习要求单个样本同时关联多个标签，较单标签二分类或多分类具有更高的结构复杂性；与此同时，现实数据中还常见标签密度低、标签缺失（missing labels）、标签噪声（label noise）、类别不平衡（class imbalance）以及候选标签冗余等问题，这些因素共同削弱了分类器对判别边界的学习能力。现有研究虽然分别讨论了缺失标签恢复、部分类多标签学习（partial multilabel learning）、过采样/欠采样及伪标签（pseudo-label）策略，但通常都建立在“恢复真实标签”或“删除错误标签”的前提上。该研究的重要出发点在于，不再将训练标签视为不可更改的固定真值，而是将其视作可为提升泛化性能而进行受控重构的对象，从而为多标签模型训练提供新的优化维度。

研究人员提出的方法并不试图判定新增标签是否就是样本的真实漏标标签，也不要求被删除标签一定是误标标签；其目标仅在于构造一个更有利于分类器学习的训练集，使在原始测试标签体系下的最终预测性能得到提升。基于这一思想，研究将训练集每个实例—标签对是否翻转表示为一个二元矩阵，并据此诱导出新的训练集。由于该优化问题的搜索空间规模极大，研究人员采用进化算法（evolutionary algorithm）进行求解，并以分类器在相应训练集上的性能作为适应度（fitness）驱动搜索。论文通过50个真实世界多标签数据集、7类多标签分类器及多种评价指标开展了系统实验，结果表明该方法在多数场景中都优于直接使用原始训练集，尤其在缺失标签、标签噪声、类别不平衡和部分类多标签学习相关情形中表现突出。这一结论说明，训练集标签层面的微量、稀疏、性能导向式编辑，能够成为提升多标签学习性能的通用策略。

从方法层面看，研究主要采用以下关键技术。首先，构建伪标记矩阵，将训练集中每个实例对每个标签的状态修改形式化为二元优化变量；其次，采用CHC遗传算法（Cross-generational elitist selection, heterogeneous recombination, and Cataclysmic mutation）进行全局搜索，使用HUX交叉（Half Uniform Crossover）与灾变式重初始化抑制早熟收敛；再次，设计两类适应度评估方式，即基于修改后训练集或原始训练集进行评估，并进一步引入正则项约束伪标记比例；最后，为提升可扩展性，引入平衡k-means（balanced k-means）数据划分与近似适应度评估（approximate fitness evaluation）机制。实验样本来源于50个真实世界公开多标签数据集，并采用10折交叉验证（10-fold cross-validation）完成比较。

以下结合论文主体结果，对各部分内容进行凝练解读。

一、False flag learning for multilabel classification
该部分给出了方法的形式化定义。研究人员首先将多标签问题表示为由实例集合及其标签集合组成的数据集，并将伪标记过程表示为二维二元数组。数组元素为1时表示对相应实例—标签对进行翻转，即若原先标签相关则移除，若原先不相关则添加；元素为0则保持原始状态不变。基于该定义，任一二元矩阵都对应一个新的训练集。研究将目标定义为寻找能够使分类器性能最优的矩阵。由于搜索空间达到2^n×q量级，因此难以通过穷举实现。为此，论文引入CHC遗传算法，在尽可能简单的进化框架下验证该思想的可行性。研究还设置初始化概率ρ，用以控制初始个体中伪标记出现的概率，并指出良好的初始分类器通常要求伪标记比例较低，这也说明该方法偏向于稀疏修改而非大规模重标注。

二、Fitness evaluation and scalability of the approach
该部分讨论适应度函数设计与可扩展性问题。研究人员将适应度定义为使用伪标记训练集训练分类器后所获得的性能，并在实验中主要采用F1指标驱动搜索。论文比较了两种评估策略：其一，用原始训练集评估分类器，使新增或删除的标签必须与原始标签体系相协调；其二，用修改后的训练集评估，使伪标记系统内部保持自洽。进一步地，研究引入带惩罚项的正则化适应度函数，以抑制过多标签修改，并仅保留真正对模型性能有贡献的标签编辑。针对计算代价高的问题，论文提出两种扩展策略：一是将较大训练集以平衡k-means划分为多个近似等规模子集，并分别执行伪标记搜索后再合并结果；二是在进化早期仅使用小规模子集近似评估个体适应度，并随代数增加逐步扩大评估集，同时用指数均值平滑个体历史适应度。这些设计共同保证了方法在大型数据集和高代价分类器上的可用性。

三、Experimental setup
该部分给出实验设计。研究使用50个多标签真实数据集，覆盖文本、图像、生物信息学、化学信息学及问答平台等多类应用场景，数据在实例数、特征维数、标签数、标签基数（cardinality）和标签密度（density）上差异显著。所有实验均采用10折交叉验证，且伪标记仅作用于训练集，测试集始终保留原始标签。进化算法使用100个个体，最多运行1000代，并受10,000 s时间约束。统计分析采用Wilcoxon检验、Iman-Davenport检验及Nemenyi事后比较，显著性水平设为0.05。评价方面，研究以accuracy、F1、F1-macro、F1-micro和average precision为主，同时在补充分析中加入coverage、ranking loss、one-error、label-wise auROC和auPRC等指标，从分类与排序两个角度考察方法稳定性。

四、Performance comparison for MLC-DWkNN
在基于实例的多标签分类器MLC-DWkNN上，伪标记方法整体优于原始训练集方案。研究发现，对于accuracy，采用原始数据集评估并结合正则化的版本表现最佳；对于F1，则多种伪标记版本均表现出色，且使用修改后数据集评估常更优。Wilcoxon检验显示，该方法在F1上所有版本都优于标准训练方式。F1-macro呈现相近趋势，而F1-micro上的优势相对较弱，但average precision依旧支持小比例伪标记的有效性。进一步分析表明，进化结果中的最终伪标记比例始终较低，说明方法倾向于通过少量标签调整获得性能提升，而非依赖激进重构。

五、Performance comparison for ML-DT
在多标签决策树（ML-DT）上，各评价指标表现较为一致。正则化结合原始或修改数据集评估都能取得最佳结果，初始化概率0.025略优。多数伪标记配置在统计上显著优于原始训练集。该结果说明，对树模型而言，适度标签编辑能够改善节点划分结构，使标签空间中的局部模式更易被学习。

六、Performance comparison for LP
在标签幂集（label powerset, LP）模型上，最佳策略是使用原始数据集进行个体评估，而正则化并未进一步提升结果。研究人员指出，LP将标签组合视作新类别，因此伪标记可能生成训练集中原本不存在的新标签集（labelsets）；若直接用修改后的数据评估，可能引入有害的虚假标签集。原始数据评估机制能抑制这种风险。实验还专门统计了新生成标签集的比例，结果显示其占比很小，且整体收益超过潜在损害，从而证明该方法对powerset类模型尤为有效。

七、Other models
在HOMER-B、IBLR-ML+和RAkEL-D三种计算成本更高的模型上，研究同时测试了标准版本与快速近似版本。结果显示，HOMER-B中快速版本通常不如标准版本；而总体上，正则化与原始数据集评估组合仍较稳健。对于IBLR-ML+，带正则化且采用原始数据评估的伪标记版本最佳，并在多数指标上显著优于标准方法。对于RAkEL-D，使用修改数据集评估且不加正则化的版本表现最好，但FF(R)(O)也保持较强竞争力。整体而言，这一部分证明伪标记框架对不同机制的多标签分类器具有良好的模型无关性。

八、Additional performance metrics
在one-error、coverage、ranking loss、auPRC和auROC等附加指标上，伪标记方法继续显示出一致优势。特别是在auROC上，六种分类器均因FF而获得性能改善，多数组态均优于对应标准分类器。这表明该方法的增益并非局限于特定单一指标，而是跨越分类精度、排序能力与标签层面综合判别能力。

九、Overtraining study
考虑到训练集标签被主动修改，方法可能存在过拟合风险。为此，研究加入额外验证集，跟踪进化过程中训练集、验证集与测试集上最佳个体性能。结果表明，验证集性能随进化稳步提升，测试集性能亦同步提高，虽存在一定过学习现象，但总体处于机器学习常见范围内，并未抵消伪标记带来的泛化收益。

十、Instance selection
论文进一步将实例选择（instance selection）与伪标记联合建模，在个体编码中增加实例保留/删除二元串，并将压缩率纳入适应度。基于MLC-DWkNN的实验表明，联合方法在保留不足10%样本的情况下，仍能在accuracy、F1、F1-micro等指标上优于全量训练，且通常优于单独的进化式实例选择。其显著特征是约90%以上的数据压缩率，显示标签编辑可帮助算法找到更紧凑且更有判别力的训练子集。

十一、Missing labels
虽然该方法并非专为缺失标签问题设计，但由于其具备向样本添加相关标签的能力，因此对缺失标签场景具有天然适配性。研究通过人为删除不同概率的标签进行模拟，发现FF在accuracy、F1及average precision等指标上保持或扩大了相较原始数据的优势，尤其在F1上，0.05缺失标签比例下依然显著优于标准方法。这表明伪标记策略在标签不完整条件下具有稳定鲁棒性。

十二、Class-imbalance methods
与ROS、RUS、MLUL、MLSOL、REMEDIAL和MLSMOTE等多标签类别不平衡处理方法比较时，FF在七类分类器上多数情况下均占优。已有方法中，过采样策略通常优于欠采样，而RUS往往显著差于原始数据。该结果说明，虽然FF并非专门的不平衡学习方法，但其通过改变训练集标签分布与局部判别结构，能够有效缓解多标签不平衡带来的学习困难。

十三、Classification in the presence of noise
在加入1%、5%、10%、20%人工标签噪声后，FF整体性能仍保持稳定。除MLC-DWkNN在部分噪声比例下统计显著性减弱外，ML-DT、LP、PPT、HOMER-B、RAkEL-D与IBLR-ML+等模型大多在噪声条件下继续保持对标准方法的优势。特别是PPT在较高噪声下反而显示出更明显增益，说明伪标记策略对噪声训练标签具有一定适应性。

十四、Partial multi-label learning
在部分类多标签学习（PML）场景下，训练样本包含相关标签与无关候选标签的混合集合。尽管FF并非为该任务而设计，但与多种PML先进方法比较时，研究选取的FF IBLR-ML+版本在one-error上平均排名第一，在其余三项指标上排名第二，整体性能与最佳方法相当。这说明“通过训练集标签编辑提升泛化能力”这一思想在弱监督多标签学习中同样具有潜力。

十五、Discussion of results
讨论部分强调了该方法的几项核心优势：其一，分类器在方法框架中仅作为参数，因此FF可与算法适配类和问题转换类模型普遍兼容；其二，在50个真实数据集与7种分类器上的系统实验确认了其稳健有效性；其三，在缺失标签、类别不平衡、部分多标签学习等与标签质量密切相关的任务上展现出额外优势。研究还指出，powerset类方法受益尤为明显，而MLC-DWkNN相对较弱，可能与时间预算内可执行进化代数较少有关。关于方法配置，正则化总体上有利，但“使用原始数据评估”与“使用修改数据评估”并不存在绝对单向优势。初始化比例1%、2.5%、5%、10%整体差异不大，其中10%通常略差，说明稀疏伪标记更加合理。论文同时坦陈其主要局限在于进化优化带来的计算代价，但数据划分与近似评估已在较大程度上缓解了这一问题。

最后，论文结论部分可译述如下：
研究提出了一种新的多标签学习方法，通过修改实例的相关标签集合来提升多标签分类模型的性能。该方法利用进化算法对训练集进行编辑，在不预设应添加或删除哪些标签的前提下，以纯粹由性能驱动的方式生成新的训练集。基于50个真实世界数据集和7种分类方法的系统实验表明，该方法在多种多标签评价指标下均具有良好效果。研究还在实例选择任务以及缺失标签场景中验证了其适用性，结果显示该方法优于标准方法。该工作为多输出分类（multioutput classification）、层次多标签分类（hierarchical multilabel classification）、半监督学习（semi-supervised learning）、主动学习（active learning）、多标签集成学习（multilabel ensemble learning）以及针对标签修改型数据投毒（data poisoning）的安全防护等方向开辟了进一步研究空间。