DEBATTY Thibault

Thesis

Conception et analyse d?algorithmes relatifs aux graphes des k plus proches voisins

Un graphe des k plus proches voisins (graphe k-nn, de l’anglais k-nearest neighbors) est un type de graphe spécifique où chaque point (nœud) possède un lien vers les k autres points les plus semblables du graphe selon une mesure appropriée de similarité. Pour l’analyse de grands volumes de données, un graphe k-nn peut être utilisé comme index, et offre de multiples avantages : 1) il nécessite peu de mémoire, 2) il peut être utilisé avec n’importe quelle mesure de similarité, même non métrique et 3) bien que la construction d’un graphe k-nn soit généralement une opération qui nécessite beaucoup de calcul et de temps, le traitement d’un graphe k-nn est très rapide.

Dans cette thèse, nous étudions l’utilisation de graphes k-nn pour analyser de grands volumes de données. Nous supposons d’ailleurs que le jeu de données est si important qu’il ne peut être traité à l’aide d’un seul ordinateur. Nous proposons donc des algorithmes s’appuyant sur le modèle BSP (bulk synchronous parallel), puis nous les implémentons et évaluons leur performance en utilisant soit le framework Apache Hadoop MapReduce, soit le framework Apache Spark.

Dans la première partie de cette thèse, nous analysons comment construire un graphe k-nn à partir de données textuelles, comment le mettre à jour lorsque des données doivent être ajoutées et supprimées, et comment le partitionner entre plusieurs nœuds de calcul afin d’optimiser le traitement ultérieur du graphe. Dans la deuxième partie, nous montrons que les graphes k-nn peuvent être utilisés avec succès pour effectuer le regroupement de grands ensembles de données textuelles (text clustering) et pour détecter les ordinateurs compromis dans un réseau.