K-Vizinhos Mais Próximos Semi-supervisionado
- Proposto por
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Ano
- 2002 (semi-supervised extension); 1967 (KNN base)
- Tipo
- Semi-supervised classifier / label propagation
- Família
- Machine learning
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O K-Vizinhos Mais Próximos (KNN) semi-supervisionado estende o algoritmo clássico de K-vizinhos mais próximos para explorar grandes conjuntos de dados não rotulados juntamente com um pequeno conjunto rotulado.
Ao construir um grafo KNN sobre todas as observações e propagar rótulos conhecidos através das arestas do grafo, o método infere rótulos para pontos não rotulados sem exigir anotação manual dispendiosa de cada amostra.
A intuição por trás do método
Imagine uma sala de aula onde apenas um punhado de alunos tem crachás de identificação e os restantes são anônimos. O KNN padrão só consegue classificar um aluno anônimo olhando para o punhado de vizinhos identificados próximos. O KNN semi-supervisionado, em vez disso, mapeia toda a sala como uma rede — cada aluno conectado aos seus vizinhos mais próximos — e inunda rótulos para fora dos alunos identificados como tinta se espalhando em papel molhado. Como a rede captura a estrutura geral dos dados, os rótulos chegam a pontos não rotulados de forma principiada que respeita a geometria subjacente em vez de ignorar a maioria não rotulada.
História
A propagação de rótulos em grafos KNN foi sistematizada por Zhu e Ghahramani em 2002, baseando-se na SVM transdutiva de Vapnik e em ideias anteriores de difusão baseada em grafos. O framework foi consolidado no volume da MIT Press Semi-Supervised Learning (Chapelle et al., 2006), que permanece a referência padrão. Bibliotecas escaláveis de KNN aproximado (FAISS, Annoy) posteriormente tornaram a abordagem prática em milhões de pontos, e ela continua a ser usada como uma forte linha de base para classificação semi-supervisionada de imagens e texto.
Quando usar
Use KNN semi-supervisionado quando você tem um pequeno conjunto rotulado e um grande conjunto não rotulado da mesma distribuição, os dados residem em um espaço de dimensionalidade relativamente baixa (menos de cerca de 50 características), e você acredita que pontos vizinhos compartilham a mesma classe. É bem adequado para classificação de patches de imagem, categorização de texto com anotações esparsas e tarefas de triagem médica onde a rotulagem por especialistas é cara. Evite-o quando os dados rotulados e não rotulados vêm de distribuições diferentes (desvio de covariável), o espaço de características é de dimensionalidade muito alta (o grafo KNN torna-se não confiável), o conjunto de dados é pequeno o suficiente que o KNN totalmente supervisionado já é suficiente, ou os limites de classe não se alinham com a estrutura de densidade local dos dados.
Limitações e considerações
- A construção do grafo escala quadraticamente com o tamanho do conjunto de dados, a menos que métodos aproximados de vizinhos mais próximos sejam usados.
- O desempenho degrada acentuadamente em espaços de alta dimensionalidade onde as métricas de distância perdem poder discriminatório.
- Assume que dados rotulados e não rotulados são extraídos da mesma distribuição; o desvio de covariável quebra o método.
- Requer ajuste cuidadoso de k, a largura de banda do peso da aresta e o parâmetro de mistura de propagação.
- A propagação de rótulos pode amplificar erros de rotulagem iniciais em grandes porções do grafo.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Explora dados não rotulados baratos para melhorar a precisão além do que é possível apenas com o conjunto rotulado.
- Sem suposições de modelo paramétrico: depende apenas da geometria do vizinho local.
- Naturalmente lida com problemas multiclasse sem modificação.
- A construção do grafo KNN é transparente e fácil de inspecionar.
- Funciona bem quando as classes formam clusters compactos e bem separados no espaço de características.
Aplicações
- Classificação de imagens com um pequeno conjunto de imagens rotuladas e um grande corpus não rotulado.
- Categorização de texto e documentos onde a rotulagem manual é cara.
- Classificação de registros médicos ou lâminas de patologia com anotações limitadas de especialistas.
- Detecção de fraudes quando apenas um pequeno número de casos de fraude confirmados está disponível.
- Rotulagem de dados de sensores em ambientes IoT industriais com eventos esparsos de verdade fundamental.
Como funciona
Como funciona
Um grafo é construído sobre todas as observações — rotuladas e não rotuladas. Cada nó corresponde a um ponto de dados, e arestas direcionadas ou não direcionadas conectam cada nó aos seus k vizinhos mais próximos no espaço de características. A escolha de k controla quão local ou globalmente os rótulos serão propagados: k pequeno mantém a propagação restrita; k grande permite que os rótulos saltem através de lacunas maiores.
Os pesos das arestas capturam a força da similaridade entre nós conectados, tipicamente através de um kernel Gaussiano (RBF) aplicado à distância Euclidiana entre os vetores de características. Um parâmetro de largura de banda sigma controla quão rapidamente a similaridade decai com a distância. Arestas mais fortes carregam rótulos mais prontamente durante a propagação.
Fórmula
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Os rótulos são espalhados iterativamente de nós rotulados para vizinhos não rotulados. Em cada iteração, cada nó atualiza sua distribuição de rótulos suaves como uma combinação ponderada das distribuições atuais de seus vizinhos e seu próprio rótulo inicial (se rotulado). Um parâmetro de mistura alpha equilibra a influência da estrutura do grafo versus os rótulos duros, e a iteração continua até que as distribuições convirjam.
Fórmula
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YUma vez que a propagação converge, cada nó não rotulado é atribuído à classe com a maior pontuação de rótulo suave em sua distribuição convergida. Nós rotulados são fixados em seus rótulos verdadeiros durante todo o processo, de modo que rótulos conhecidos nunca são substituídos.
Fórmula
\hat{y}_i = \arg\max_c F_{ic}Erros comuns
- Construção do grafo KNN sem normalizar características, fazendo com que características de alta variância dominem os cálculos de distância.
- Definir k muito grande, o que suaviza os limites de classe genuínos e produz distribuições de rótulos excessivamente suavizadas.
- Ignorar a possibilidade de que os dados não rotulados estejam fora da distribuição em relação ao conjunto rotulado.
- Relatar a precisão em nós não rotulados como se fosse uma estimativa imparcial do conjunto de teste — nós não rotulados vazaram para o grafo durante o treinamento.
- Pular verificações de convergência e usar um número fixo e arbitrário de iterações de propagação.
Perguntas frequentes
Como escolho k?
Comece com k na faixa de 5-15 e ajuste pela precisão de validação rotulada retida. k menor dá limites mais nítidos e locais; k maior permite que os rótulos se propaguem mais longe, mas arrisca cruzar os limites de classe verdadeiros.
Posso avaliar o método honestamente quando a maioria dos dados não é rotulada?
Retenha um conjunto de teste rotulado dedicado que nunca é adicionado ao grafo. Nós no grafo — mesmo os não rotulados — fazem parte do treinamento, portanto, qualquer nó rotulado que participe da construção do grafo não deve servir também como ponto de teste.
E se meu conjunto de dados for muito grande para construir um grafo KNN completo?
Use bibliotecas de vizinhos mais próximos aproximados como FAISS ou Annoy para construir o grafo em O(n log n) em vez de O(n^2), em seguida, aplique a propagação de rótulos no grafo aproximado esparso.
O KNN semi-supervisionado sempre supera o KNN supervisionado?
Não necessariamente. Se os dados não rotulados estiverem fora da distribuição ou o espaço de características for de alta dimensionalidade, o grafo é ruidoso e a propagação pode prejudicar o desempenho. Sempre compare com uma linha de base de KNN supervisionado antes de reivindicar um benefício dos dados não rotulados.
Isso é o mesmo que espalhamento de rótulos ou propagação de rótulos no scikit-learn?
Estreitamente relacionado. LabelPropagation e LabelSpreading do scikit-learn implementam o framework de Zhu e Ghahramani usando um grafo de kernel KNN ou RBF, portanto, são implementações diretas do método descrito aqui.
Métodos relacionados
Fontes
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Abrir referência da publicaçãoCopiado.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiado.