Skip to content
返回搜索结果

半监督K近邻

提出者
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
年份
2002 (semi-supervised extension); 1967 (KNN base)
类型
Semi-supervised classifier / label propagation
类别
Machine learning

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

半监督K近邻(Semi-supervised KNN)算法是对经典的K近邻算法的扩展,它能够利用大量未标记数据和少量标记数据。通过在所有观测数据上构建K近邻图,并沿着图的边传播已知标签,该方法可以在无需昂贵的手动标注每个样本的情况下推断出未标记点的标签。

方法背后的直觉

想象一个教室,只有少数学生戴着名牌,其余的都是匿名的。标准的K近邻算法只能通过查看附近少数有标记的邻居来对匿名学生进行分类。而半监督K近邻算法则将整个教室映射成一个网络——每个学生都与其最近的邻居相连——然后像墨水在湿纸上扩散一样,从有标记的学生那里向外传播标签。由于该网络捕捉了数据的整体结构,标签能够以一种尊重底层几何结构的方式传播到未标记点,而不是忽略占多数的未标记数据。

历史学

基于Vapnik的转导支持向量机(Transductive SVM)和早期的基于图的扩散思想,Zhu和Ghahramani于2002年系统化了K近邻图上的标签传播。该框架在MIT出版社的著作《半监督学习》(Chapelle等,2006)中得到巩固,该书至今仍是标准参考。后来的可扩展近似K近邻库(FAISS, Annoy)使得该方法在数百万个数据点上变得实用,并且它仍然是半监督图像和文本分类的一个强大基线。

何时使用

当您拥有少量标记数据和来自同一分布的大量未标记数据,数据位于相对低维空间(特征数少于约50个),并且您相信邻近点属于同一类别时,可以使用半监督K近邻。它非常适合图像块分类、带有稀疏标注的文本分类以及专家标注成本高昂的医学筛查任务。当标记和未标记数据来自不同分布(协变量偏移)、特征空间非常高维(K近邻图变得不可靠)、数据集足够小以至于完全监督的K近邻已足够,或者类别边界与数据的局部密度结构不一致时,应避免使用它。

局限与注意事项

  • 除非使用近似最近邻方法,否则图的构建会随着数据集大小呈二次方扩展。
  • 在距离度量失去区分能力的が高维空间中,性能会急剧下降。
  • 假设标记和未标记数据来自同一分布;协变量偏移会破坏该方法。
  • 需要仔细调整k值、边权重带宽和传播混合参数。
  • 标签传播可能会将初始标注错误放大到图的大部分区域。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 利用廉价的未标记数据来提高准确性,使其超越仅使用标记数据所能达到的水平。
  • 无参数模型假设:仅依赖于局部邻域几何。
  • 自然地处理多类别问题而无需修改。
  • K近邻图的构建是透明且易于检查的。
  • 当类别在特征空间中形成紧凑、分离良好的簇时效果很好。

应用

  • 图像分类,使用少量标记图像和大量未标记语料库。
  • 文本和文档分类,其中手动标注成本高昂。
  • 病历或病理切片分类,具有有限的专家标注。
  • 欺诈检测,当只有少量已确认的欺诈案例可用时。
  • 工业物联网环境中的传感器数据标记,具有稀疏的地面真实事件。

使用方式

使用方式

1

在所有标记和未标记的观测数据上构建一个图。每个节点对应一个数据点,有向或无向的边将每个节点连接到其在特征空间中的k个最近邻。k的选择控制着标签传播的局部性或全局性:较小的k值使传播保持紧密;较大的k值允许标签跨越更大的间隙。

2

边权重捕捉连接节点之间相似性的强度,通常通过应用于特征向量之间欧氏距离的高斯(RBF)核函数来实现。带宽参数sigma控制相似性随距离衰减的速度。较强的边在传播过程中更容易传递标签。

公式
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

标签从标记节点迭代地传播到未标记的邻居。在每次迭代中,每个节点都将其软标签分布更新为其邻居当前分布的加权组合以及其自身的初始标签(如果已标记)。混合参数alpha平衡了图结构的影响与硬标签的影响,迭代持续进行直到分布收敛。

公式
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

传播收敛后,每个未标记节点被赋予其收敛分布中具有最高软标签分数的类别。已标记节点在整个过程中被固定为其真实标签,因此已知标签永远不会被覆盖。

公式
\hat{y}_i = \arg\max_c F_{ic}

常见陷阱

  • 在未对特征进行归一化的情况下构建K近邻图,导致高方差特征主导距离计算。
  • 将k设置得过大,会平滑掉真实的类别边界并产生过度平滑的标签分布。
  • 忽略了未标记数据相对于标记数据可能属于不同分布的可能性。
  • 将未标记节点的准确性报告为无偏测试集估计——未标记节点已渗入图的训练过程中。
  • 跳过收敛检查,使用固定的、任意数量的传播迭代。

常见问题

如何选择k?

从k值在5-15的范围内开始,并通过保留的标记验证集准确率进行调整。较小的k值产生更清晰、更局部的边界;较大的k值允许标签传播得更远,但有跨越真实类别边界的风险。

当大部分数据未标记时,我能诚实地评估该方法吗?

保留一个专用的标记测试集,该测试集绝不添加到图中。图中的节点——即使是未标记的节点——都是训练的一部分,因此任何参与图构建的标记节点都不能同时作为测试点。

如果我的数据集太大,无法构建完整的K近邻图怎么办?

使用近似最近邻库,如FAISS或Annoy,以O(n log n)而不是O(n^2)的时间复杂度构建图,然后对稀疏的近似图应用标签传播。

半监督K近邻是否总是优于监督K近邻?

不一定。如果未标记数据来自不同分布或特征空间非常高维,图就会变得嘈杂,传播可能会损害性能。在声称未标记数据带来好处之前,务必与监督K近邻基线进行比较。

这与scikit-learn中的标签传播(label spreading)或标签传播(label propagation)相同吗?

密切相关。scikit-learn的LabelPropagation和LabelSpreading使用K近邻或RBF核图实现了Zhu和Ghahramani的框架,因此它们是此处描述方法的直接实现。

相关方法

参考文献

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    打开出版物文献
    已复制。
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN:978-0-262-03358-9
    已复制。