K-vecinos más cercanos semi-supervisado
- Propuesto por
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Año
- 2002 (semi-supervised extension); 1967 (KNN base)
- Tipo
- Semi-supervised classifier / label propagation
- Familia
- Machine learning
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El KNN semi-supervisado (Semi-supervised KNN) extiende el algoritmo clásico de K-vecinos más cercanos para explotar grandes conjuntos de datos sin etiquetar junto con un pequeño conjunto etiquetado.
Al construir un grafo KNN sobre todas las observaciones y propagar las etiquetas conocidas a través de los bordes del grafo, el método infiere etiquetas para puntos sin etiquetar sin requerir la costosa anotación manual de cada muestra.
La intuición detrás del método
Imagine un aula donde solo un puñado de estudiantes tienen etiquetas con sus nombres y el resto son anónimos. El KNN estándar solo puede clasificar a un estudiante anónimo observando el puñado de vecinos etiquetados cercanos. El KNN semi-supervisado, en cambio, mapea toda la sala como una red —cada estudiante conectado a sus vecinos más cercanos— y propaga las etiquetas desde los estudiantes etiquetados como tinta que se extiende por papel mojado. Debido a que la red captura la estructura general de los datos, las etiquetas llegan a los puntos sin etiquetar de una manera fundamentada que respeta la geometría subyacente en lugar de ignorar a la mayoría sin etiquetar.
Historia
La propagación de etiquetas en grafos KNN fue sistematizada por Zhu y Ghahramani en 2002, basándose en el SVM transductivo de Vapnik y las ideas anteriores de difusión basadas en grafos. El marco se consolidó en el volumen de MIT Press "Semi-Supervised Learning" (Chapelle et al., 2006), que sigue siendo la referencia estándar. Las bibliotecas escalables de KNN aproximado (FAISS, Annoy) hicieron que el enfoque fuera práctico para millones de puntos, y continúa utilizándose como una línea base sólida para la clasificación semi-supervisada de imágenes y texto.
Cuándo usarlo
Utilice KNN semi-supervisado cuando tenga un pequeño conjunto etiquetado y un gran conjunto sin etiquetar de la misma distribución, los datos residan en un espacio de dimensiones relativamente bajas (menos de aproximadamente 50 características), y crea que los puntos vecinos comparten la misma clase. Es adecuado para la clasificación de parches de imágenes, la categorización de texto con anotaciones dispersas y tareas de cribado médico donde el etiquetado experto es costoso. Evítelo cuando los datos etiquetados y sin etiquetar provengan de distribuciones diferentes (cambio de covariables), el espacio de características sea de muy alta dimensión (el grafo KNN se vuelve poco fiable), el conjunto de datos sea lo suficientemente pequeño como para que el KNN completamente supervisado ya sea suficiente, o los límites de clase no se alineen con la estructura de densidad local de los datos.
Limitaciones y consideraciones
- La construcción del grafo escala cuadráticamente con el tamaño del conjunto de datos a menos que se utilicen métodos de vecinos más cercanos aproximados.
- El rendimiento se degrada drásticamente en espacios de alta dimensión donde las métricas de distancia pierden poder discriminatorio.
- Asume que los datos etiquetados y sin etiquetar provienen de la misma distribución; el cambio de covariables invalida el método.
- Requiere un ajuste cuidadoso de k, el ancho de banda del peso de los bordes y el parámetro de mezcla de propagación.
- La propagación de etiquetas puede amplificar los errores de etiquetado iniciales en grandes porciones del grafo.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Explota datos sin etiquetar de bajo costo para mejorar la precisión más allá de lo que es posible solo con el conjunto etiquetado.
- No hay suposiciones de modelos paramétricos: se basa únicamente en la geometría del vecindario local.
- Maneja naturalmente problemas de múltiples clases sin modificaciones.
- La construcción del grafo KNN es transparente y fácil de inspeccionar.
- Funciona bien cuando las clases forman clústeres compactos y bien separados en el espacio de características.
Aplicaciones
- Clasificación de imágenes con un pequeño conjunto de imágenes etiquetadas y un gran corpus sin etiquetar.
- Categorización de texto y documentos donde el etiquetado manual es costoso.
- Clasificación de registros médicos o diapositivas de patología con anotaciones expertas limitadas.
- Detección de fraude cuando solo se dispone de un pequeño número de casos de fraude confirmados.
- Etiquetado de datos de sensores en entornos de IoT industrial con eventos de "ground-truth" dispersos.
Cómo funciona
Cómo funciona
Se construye un grafo sobre todas las observaciones, tanto etiquetadas como sin etiquetar. Cada nodo corresponde a un punto de datos, y los bordes dirigidos o no dirigidos conectan cada nodo con sus k vecinos más cercanos en el espacio de características. La elección de k controla cuán local o globalmente se propagarán las etiquetas: un k pequeño mantiene la propagación ajustada; un k grande permite que las etiquetas salten a través de brechas más grandes.
Los pesos de los bordes capturan la fuerza de similitud entre nodos conectados, típicamente mediante un kernel Gaussiano (RBF) aplicado a la distancia euclidiana entre vectores de características. Un parámetro de ancho de banda sigma controla qué tan rápido decae la similitud con la distancia. Los bordes más fuertes transmiten las etiquetas más fácilmente durante la propagación.
Fórmula
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Las etiquetas se propagan iterativamente desde los nodos etiquetados a los vecinos sin etiquetar. En cada iteración, cada nodo actualiza su distribución de etiquetas "blandas" como una combinación ponderada de las distribuciones actuales de sus vecinos y su propia etiqueta inicial (si está etiquetado). Un parámetro de mezcla alpha equilibra la influencia de la estructura del grafo frente a las etiquetas "duras", y la iteración continúa hasta que las distribuciones convergen.
Fórmula
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YUna vez que la propagación converge, a cada nodo sin etiquetar se le asigna la clase con la puntuación de etiqueta "blanda" más alta en su distribución convergida. Los nodos etiquetados se fijan a sus etiquetas verdaderas en todo momento, por lo que las etiquetas conocidas nunca se sobrescriben.
Fórmula
\hat{y}_i = \arg\max_c F_{ic}Errores comunes
- Construir el grafo KNN sin normalizar las características, lo que hace que las características de alta varianza dominen los cálculos de distancia.
- Establecer k demasiado grande, lo que suaviza los límites de clase genuinos y produce distribuciones de etiquetas excesivamente suavizadas.
- Ignorar la posibilidad de que los datos sin etiquetar estén fuera de distribución en relación con el conjunto etiquetado.
- Reportar la precisión en nodos sin etiquetar como si fuera una estimación imparcial del conjunto de prueba — los nodos sin etiquetar se filtraron en el grafo durante el entrenamiento.
- Omitir las comprobaciones de convergencia y usar un número fijo y arbitrario de iteraciones de propagación.
Preguntas frecuentes
¿Cómo elijo k?
Comience con k en el rango 5-15 y ajústelo mediante la precisión de validación etiquetada retenida. Un k más pequeño produce límites más nítidos y locales; un k más grande permite que las etiquetas se propaguen más, pero corre el riesgo de cruzar los límites de clase verdaderos.
¿Puedo evaluar el método honestamente cuando la mayoría de los datos no están etiquetados?
Reserve un conjunto de prueba etiquetado dedicado que nunca se agregue al grafo. Los nodos en el grafo —incluso los no etiquetados— son parte del entrenamiento, por lo que cualquier nodo etiquetado que participe en la construcción del grafo no debe servir también como punto de prueba.
¿Qué pasa si mi conjunto de datos es demasiado grande para construir un grafo KNN completo?
Utilice bibliotecas de vecinos más cercanos aproximados como FAISS o Annoy para construir el grafo en O(n log n) en lugar de O(n^2), luego aplique la propagación de etiquetas en el grafo aproximado disperso.
¿El KNN semi-supervisado siempre supera al KNN supervisado?
No necesariamente. Si los datos sin etiquetar están fuera de distribución o el espacio de características es de muy alta dimensión, el grafo es ruidoso y la propagación puede perjudicar el rendimiento. Siempre compare con una línea base de KNN supervisado antes de afirmar un beneficio de los datos sin etiquetar.
¿Es esto lo mismo que la propagación de etiquetas o la difusión de etiquetas en scikit-learn?
Estrechamente relacionado. Las implementaciones de LabelPropagation y LabelSpreading de scikit-learn implementan el marco de Zhu y Ghahramani utilizando un grafo de kernel KNN o RBF, por lo que son implementaciones directas del método aquí descrito.
Métodos relacionados
Fuentes
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Abrir referencia de la publicaciónCopiado.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiado.