Création d’un graphique de similarité avec l’algorithme approximatif des voisins les plus proches de Neo4j

Dans la version 3.5.11.0 de la bibliothèque d’algorithmes de graphes Neo4j, nous avons ajouté la procédure Approximate Nearest Neighbours ou ANN.

ANN utilise des algorithmes de similarité pour trouver efficacement des éléments plus semblables. Dans cet article, nous examinerons notre motivation pour créer cet algorithme, où il peut être utilisé, et montrerons comment l’utiliser à l’aide d’un exemple concret.

Vous pouvez télécharger la bibliothèque d’algorithmes de graphes à partir du centre de téléchargement Neo4j ou l’installer dans Neo4j Desktop via l’application Graph Algorithms Playground Graph

Cela fait maintenant presque un an que nous avons ajouté des algorithmes de similarité à la bibliothèque d’algorithmes de graphes Neo4j, et ils sont rapidement devenus parmi les plus largement utilisés dans la bibliothèque.

Un cas d’utilisation courant est la création d’un graphique < du voisin le plus proche ou d’un graphique de similarité. Un tel graphe contient des relations entre deux nœuds a et b si la distance entre a et b fait partie des k-ièmes plus petites distances entre a et tous les autres nœuds.

La distance entre les nœuds serait calculée en utilisant l’un des algorithmes de similarité pour comparer des attributs tels que les écoles fréquentées, les films évalués ou le produit acheté en commun.

Ce graphique peut ensuite être utilisé dans le cadre d’un système de recommandation. Nous pouvons faire des recommandations dans les domaines suivants:

OK, cela semble utile, mais pourquoi avons-nous besoin de ce truc ANN?

Bien que cette approche fonctionne, elle est coûteuse en calcul.

Nous devons comparer chaque élément avec tous les autres éléments, ce qui nous donne une complexité O (n ^ 2) ou des calculs (numberOfNodes * numberOfNodes-1) / 2 . Il s’agit d’une approche de force brute.

Par exemple, si nous voulions calculer la similitude de 10 000 éléments, nous devrons faire:

10 000 * 9 999/2 = 49 995 000 calculs

Cela ne semble pas trop mal, mais que se passe-t-il si nous l’augmentons d’un facteur 10 et que nous voulons maintenant calculer la similitude de 100 000 éléments? Nous devons maintenant faire:

100 000 * 99 9999 2 = 4 999 950 000 calculs, qui prendraient beaucoup de temps.

Présentation des voisins les plus proches approximatifs (ANN)

L’algorithme Approximate Nearest Neighbours réduit la quantité de calcul nécessaire pour créer un graphique de similarité car nous ne comparons plus chaque nœud avec tous les autres nœuds.

Nous avons implémenté un algorithme appelé NN-Descent, qui est décrit dans l’article Construction efficace du graphique du voisin K-le plus proche pour les mesures de similarité génériques.

Le document décrit un algorithme simple mais efficace pour créer des graphiques de similarité des plus proches voisins.

Le pseudo-code de l’algorithme peut être vu dans le diagramme ci-dessous:

Le compromis avec cet algorithme est que nous calculons les voisins les plus proches approximatifs, plutôt que les voisins les plus proches absolus comme avec l’approche de la force brute.

Cela dit, nous avons constaté que nous obtenons un taux de rappel de 90% ou plus sur les ensembles de données de test sur lesquels nous avons essayé l’algorithme.

Quand ne devrions-nous pas l’utiliser?

Comme pour la plupart des choses, ANN n’est pas une solution miracle, nous ne voulons donc pas l’utiliser partout.

Si nous essayons de calculer un graphique des voisins les plus proches pour un petit ensemble de données, l’approche de la force brute a toujours du sens. Sur de très petits ensembles de données contenant 10s de nœuds, l’approche ANN nécessitera plus de calculs et produira de pires résultats.

De même, si nous prenons des décisions importantes, par exemple si vous essayez d’estimer une prédiction médicale, vous pourriez être très sensible aux faux positifs et le temps de calcul plus long de l’approche par force brute serait acceptable.

Voyons cela en action

Le référentiel ANN Benchmarks GitHub contient des ensembles de données que nous pouvons utiliser pour tester notre algorithme.

Nous utiliserons l’ensemble de données Fashion-MNIST, qui contient 60 000 images d’articles de Zalando.

Chaque exemple comporte une incrustation de 784 chiffres qui représente les pixels de l’image.

Importation de mode MNIST

Les données sont au format HDF5, nous devrons donc les convertir au format CSV avant de pouvoir les importer davantage dans Neo4j. Nous utiliserons ensuite la procédure apoc.load.csv pour créer un nœud représentant chaque image et stocker l’incorporation dans la propriété embedding sur le nœud.

Création d’un graphique des voisins les plus proches de force brute

Une fois les données importées, nous sommes prêts à créer le graphique de similarité de nos voisins les plus proches. Nous allons commencer par l’approche de la force brute, que nous pouvons faire en exécutant l’algorithme Euclidean Distance Similarity:

Nous avons utilisé certains paramètres de configuration dans cet appel de procédure. Explorons-les:

Construction d’un graphique approximatif des voisins les plus proches

Et maintenant, faisons la même chose en utilisant notre nouvelle procédure Approximate Nearest Neighbours:

Il y a quelques options de configuration intéressantes dans cet appel de procédure:

Évaluation du graphique approximatif des voisins les plus proches

Nous allons maintenant comparer notre graphique approximatif des voisins les plus proches avec la variante de force de bruce. La requête suivante:

Nous créons un graphique des voisins les plus proches approximatifs en utilisant différentes fréquences d’échantillonnage, et le tableau suivant montre le nombre de calculs, le temps de calcul, ainsi que le rappel pour chacune de ces configurations:

Résumé

Dans cet article, nous avons appris à utiliser l’algorithme approximatif du plus proche voisin dans la bibliothèque d’algorithmes de graphes Neo4j.

Si vous avez aimé apprendre à appliquer des algorithmes graphiques pour donner un sens aux données, vous aimerez peut-être le livre sur les algorithmes graphiques O’Reilly qu’Amy Hodler et moi avons écrit.

Vous pouvez télécharger une copie gratuite à partir de neo4j.com/graph-algorithms-book