Vue d’ensemble

L'algorithme des k plus proches voisins (kNN) est une technique de classification qui classe le "node" cible en fonction des classifications de ses k "nodes" les plus proches (les plus similaires). kNN a été proposé par T.M. Cover et P.E. Hart en 1967 et est depuis devenu l'un des algorithmes de classification les plus simples et les plus utilisés :

• T.M. Cover, P.E. Hart, Nearest Neighbor Pattern Classification (1967)

Bien que contenant le mot voisin dans son nom, kNN ne considère pas explicitement les "edges" entre "nodes" lors du calcul de la similarité. Au lieu de cela, il se concentre uniquement sur les "properties" des "nodes".

Concepts

Mesure de Similarité

L'algorithme kNN d'Ultipa calcule la similarité cosinus entre le "node" cible et tous les autres "nodes" dans le "graph", puis sélectionne les k "nodes" avec la plus grande similarité par rapport au "node" cible.

Vote sur la Classification

Une "property" de "node" est sélectionnée comme étiquette de classe. Après avoir trouvé les k "nodes" les plus proches pour le "node" cible, attribuez l'étiquette majoritaire parmi les k "nodes" au "node" cible.

Si plusieurs étiquettes apparaissent avec la même fréquence maximale, l'étiquette du "node" avec la plus grande similarité sera sélectionnée.

Syntaxe

• Commande : algo(knn)
• Paramètres :

Exemples

Le "graph" d'exemple possède 6 "nodes" d'image (les "edges" sont ignorés), et chaque "node" possède les "properties" d1, d2, d3, d4 et type:

File Writeback

algo(knn).params({
  node_id: 1,
  node_schema_property: ['d1', 'd2', 'd3', 'd4'],
  top_k: 4,
  target_schema_property: @image.type
}).write({
  file:{
    filename: "knn"
    }
})

Résultats : Fichier knn

Gold
top k : image4,0.538975
image3,0.705072
image6,0.841922
image2,0.85516

Direct Return

algo(knn).params({
  node_id: 1,
  node_schema_property: ['d1', 'd2', 'd3', 'd4'],
  top_k: 4,
  target_schema_property: @image.type
}) as a1, a2 
return a1, a2

Résultats : a1 et a2

Stream Return

algo(knn).params({
  node_id: 2,
  node_schema_property: ['@image.d1', '@image.d2', '@image.d3', '@image.d4'],
  top_k: 5,
  target_schema_property: @image.type
}).stream() as label
find().nodes({_uuid == 2}) as target
return case
  when target.type == label.attribute_value then 'True'
  else 'false'
end

Résultats : false

find().nodes({@image}) as images
call {
    with images._uuid as target
    algo(knn).params({
      node_id: target,
      node_schema_property: ['d1', 'd2', 'd3', 'd4'],
      top_k: 3,
      target_schema_property: 'type'
    }).stream() as label
    return label
}
return table(images._id, label.attribute_value)

Résultats : table(images._id, label.attribute_value)