K-Nearest Neighbors (KNN)

Índice

• O que é
• Como Funciona
  • Similaridade de Cosseno
  • HNSW — Busca Aproximada Eficiente
  • Geração dos Embeddings
  • Parâmetros do KNN no Entity Linking
  • KNN no Contexto do Duplo Diamante
• Demonstração / Exemplos
• ADR's Relacionadas

O que é

K-Nearest Neighbors (KNN) é um algoritmo de aprendizado de máquina supervisionado aplicado geralmente para classificação ou regressão. Para isso, ele busca os K elementos de um conjunto mais próximos a uma consulta, segundo uma métrica de distância e retorna uma classificação ou previsão de acordo com o que a maioria dos vizinhos apresenta. No contexto do Kairos, foi aplicado apenas a heurísitica do KNN de encontrar os K elementos mais próximos, no caso, as K competências da ESCO mais próximas a uma competência extraída, operando no espaço vetorial de embeddings: cada competência ESCO e competência extraída é representada como um vetor de 768 dimensões, e a busca retorna as K competências cujos vetores têm maior similaridade de cosseno com o vetor da competência consultada.

Consulta: embedding("Open-Source Projects")  → vetor de 768 dimensões
KNN:      Top-10 nós (:Skill) mais próximos no espaço vetorial
Resultado: ["programar software de código-fonte aberto", "modelo open source", ...]

O KNN é o primeiro estágio do Diamante de Expansão no algoritmo de Entity Linking — seu objetivo é maximizar o recall, trazendo todos os candidatos ESCO semanticamente relevantes antes que o PPR faça a convergência.

Como Funciona

Similaridade de Cosseno

A distância usada não é a euclidiana, mas a similaridade de cosseno — que mede o ângulo entre dois vetores, ignorando sua magnitude:

cosine_similarity(A, B) = (A · B) / (||A|| × ||B||)

Valores próximos de 1.0 indicam vetores apontando na mesma direção semântica. Valores próximos de 0.0 indicam vetores ortogonais (sem relação semântica).

A similaridade de cosseno é preferível à distância euclidiana para embeddings de texto porque o comprimento do vetor varia com a norma do modelo, mas a direção semântica permanece consistente.

HNSW — Busca Aproximada Eficiente

Calcular a similaridade de cosseno entre a consulta e todos os ~34.000 nós (:Skill) da ESCO a cada linking seria inviável em produção. O Kairos usa o índice HNSW (Hierarchical Navigable Small World) do Neo4j, que implementa busca aproximada de vizinhos mais próximos (ANN) em tempo sub-linear.

Como o HNSW funciona

O HNSW organiza os vetores em um grafo de camadas hierárquicas:

A busca começa pelas camadas superiores (menos nós, navegação rápida) e afunila para a camada base (alta densidade, resultado preciso). Isso garante complexidade O(log N) ao invés de O(N).

Configuração do índice no Neo4j

O índice vetorial é criado durante a ingestão da ESCO pelo loader-esco:

CREATE VECTOR INDEX esco_skills FOR (n:Skill) ON (n.embedding)
OPTIONS {
  indexConfig: {
    `vector.dimensions`: 768,
    `vector.similarity_function`: 'cosine'
  }
}

Geração dos Embeddings

Para que a busca faça sentido, a consulta e os documentos indexados precisam ser gerados pelo mesmo modelo de embedding e com representações de texto equivalentes.

Embeddings dos nós ESCO (indexados)

Gerados pelo loader-esco no boot, usando o formato raw merged newlines (ADR-043):

f"{preferred_label}\n {description}\n {alt_labels}"

Exemplo para a competência "gestão ágil de projetos":

gestão ágil de projetos
 Aplicar metodologias ágeis para gestão de projetos, como Scrum ou Kanban...
 agile project management|gestão de projetos ágeis|...

Embeddings das consultas (runtime)

Gerados pelo processor-entity-linker para cada competência candidata recebida, usando o mesmo formato e modelo (embeddinggemma via Ollama).

Parâmetros do KNN no Entity Linking

O threshold de 0.72 descarta candidatos com baixa relevância semântica antes de ser utilizado no PPR como semente, evitando influenciar esse algoritmo com competências irrelevantes.

KNN retorna 10 candidatos
→ 3 ficam abaixo de 0.72 (não influenciam o PPR como os demais do top-K)
→ 7 entram no PPR como sementes

KNN no Contexto do Duplo Diamante

O KNN é o responsável por reduzir falsos negativos, maximizando o recall. Falsos Positivos são aceitos no Top-K, pois prefere-se aceitá-los a perder candidatos corretos antes de eles chegarem ao estágio de convergência no PPR como sementes.

Demonstração / Exemplos

Os exemplos abaixo ilustram o comportamento do KNN com os parâmetros top_k = 10 e knn_threshold = 0.72.

Skill com Alta Cobertura Semântica

"Gerenciamento de Projetos" retorna múltiplos candidatos acima do threshold, demonstrando que o KNN captura variantes terminológicas distintas para o mesmo domínio:

Consulta: embedding("Gerenciamento de Projetos")

Top-K retornados pelo HNSW e já filtrados pelo threshold:
  1. "dirigir, supervisionar e coordenar projetos"          → 0.821 ✓
  2. "gestão de projetos informáticos"                      → 0.818 ✓
  3. "gestão ágil de projetos"                              → 0.816 ✓
  4. "gestão de projetos lean"                              → 0.815 ✓
  5. "metodologias de gestão de projetos de informática"    → 0.797 ✓
  6. "gestão de projetos Prince2"                           → 0.792 ✓
  7. "gestão de processos"                                  → 0.791 ✓
  8. "gerir projetos de desenvolvimento de conteúdos"       → 0.787 ✓
→ 8 acima de 0.72 → entram no PPR como sementes

Skill com Threshold Eliminando Candidatos

"Open-Source Projects" retorna candidatos com scores mais baixos, onde menos avançam ao PPR como sementes:

Consulta: embedding("Open-Source Projects")

Top-K retornados pelo HNSW e já filtrados pelo threshold:
  1. "programar software de código-fonte aberto"          → 0.760 ✓
  2. "modelo open source"                                 → 0.756 ✓
  3. "dirigir, supervisionar e coordenar projetos"        → 0.725 ✓
→ apenas 3 candidatos entram no PPR como sementes

Skill Ausente na ESCO

"TensorFlow" não consta na ontologia ESCO. Por ser hard skill, passa primeiro pelo fuzzy match, mas não se encontra nenhum candidato válido. Indo para o KNN, também acontece de nenhum candidato superar o threshold. Logo, a competência será marcada como não reconhecida (SkillCustom):

Consulta: embedding("TensorFlow")

Top-K retornados pelo HNSW:
  1. "aprendizagem de máquina"   → 0.681 ✗
  2. "redes neurais artificiais" → 0.659 ✗
  ...

→ 0 candidatos passam pelo threshold → SkillCustom

ADR's Relacionadas