Big Data : comment gérer les grands volumes de données pour le calcul de similarité

Les volumes de données numériques augmentant considérablement (des milliards d’images, de vidéo, de documents, de tweets, …), la problématique du Big data est de donner des moyens techniques pour traiter des bases de données de plus en plus grandes et de moins en moins structurées.

L’objectif est de mettre au point des algorithmes permettant d’accélérer la comparaison des données afin de créer des regroupements, de calculer la similarité entre les données ou encore de segmenter ou partitionner les données. Les applications sont nombreuses : systèmes de recommandation (achats, .musique, vidéo…), de prédiction (en analysant les tweets, il est possible de détecter qu’un événement est en train d’avoir lieu), etc.

Pour pouvoir effectuer se genre de tâche ou tout autres opération de data mining, le traitement des données se fait en 2 étapes principales : 1) représenter les données et 2) calcul de distances ou de similarités.

Représenter les données

Avant toutes choses, il faut extraire des caractéristiques. Si j’analyse des images, je vais extraire des informations sur la couleur, les formes, les textures, etc. Chaque image sera alors décrit par un vecteur de caractéristique à plusieurs dimensions. Plus ces caractéristiques sont pertinentes pour la tâche à effectuer mieux ce sera. Moins il y aura de dimension et plus il sera facile de traiter le problème. Si le nombre de dimension devient très grand, cela va rendre plus difficile le calcul de similarité et la fouille de données. En effet, le calcul de distance est sensible aux nombre de dimensions, c’est ce qu’on appelle la « curse of dimensionality ».  Plus le nombre de dimensions augmente et plus la distance entre les données augmentent également, ce qui à implique que chaque données tend à être à la même distance que toutes les autres. Il devient alors impossible de regrouper les données par ressemblance puisqu’elles sont toutes dissimilaires.

Similarité, distance, voisinage et topologie

Les calculs des similarité et de distances permettent de découvrir la topologie d’un espace de données, de comprendre la structure qui émerge entre une données et ses données voisines. Quand une nouvelle donnée apparait, on souhaite explorer ses données voisines afin de se faire une idée au sujet de cette nouvelle donnée. Pour cela on utilise un algorithme de recherche de Plus Proches Voisins (k-PPV).

La recherche « basique » de k-PPV est longue car exhaustive. Pour une donnée, on calcule sa distance par rapport à toutes les autres données. On peux alors connaitre quelles sont les « k » données les plus proches (par exemple les 5-PPV). Ces 5 PPV vont m’informer de la nature de la donnée que je suis en train d’étudier. Si je fais de la classification, je peux faire voter les 5-PPV pour estimer la classe de la donnée étudiée.

Il existe de nombreuses astuces pour accélérer ce temps de calcul basée sur une structuration/segmentation de l’espace de données : arbres KD, k-means récursifs, tables de hashage, LSH… DG Lowe a publié en 2009 un article très intéressant sur l’algorithme FLANN qui regroupe à la fois la méthode basée sur les arbres KD et les k-means récursifs. Ces algorithmes sont adaptables au Big Data, mais ne sont pas conçues originellement pour traiter des grand volumes de données.

Je vais m’intéresser ici à la technique « Permutation Based Indexing » qui est plus récente (j’en ai entendu parlé par le professeur Stéphan Marchang-Maillet en 2014) et plus à même d’être utiliser dans un contexte de Big Data. Le principe consiste à choisir un certain nombre de données parmi toutes les données comme « points de référence ». Ensuite, au lieu de chercher les k-PPV parmis toutes les données, on va simplement calculer la distance entre la donnée et les points de référence. Si le nombre de points de référence est grand, on peux se limiter au calcul des plus proches points de référence. On créé alors une liste ordonnée des plus proches points de référence. Pour comparer deux données, je comparerai ces deux listes.

Par analogie, on peux comparer le « Permutation Based Indexing » à la localisation d’un bateau en pleine mer. En donnant les balises les plus proches que le bateau voie, on peux estimer sa position. Le nombre de données nécessaires est beaucoup plus faible que pour les techniques classiques ce qui permettra d’être applicable à des grand volumes de données.