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.

Traitement Automatique du Langage Naturel avec MALLET

mallet

MALLET est une bilbiothèque JAVA pour traitement statistique des langues naturelles, la classification de document, la classification non-supervisée, le « topic modeling » , le tagging de séquence (Part of Speech), l’extraction d’information et encore d’autres applications sur le traitement et la classification de texte.

Cette bibliothèque a été principalement développé par Andrew McCallum, un des scientifique très renommé dans le domaine de la classification de texte. La version 2.0 de la bibliothèque date de 2008.

 

Extraction d’information des pdf avec CERMINE

http://cermine.ceon.pl/cermine/about.html

http://cermine.ceon.pl/cermine/about.html

CERMINE (Content ExtRactor and MINEr)  est une bibliothèque Java (GitHub) et un web service (http://cermine.ceon.pl/index.html) permettant d’extraire des meta-données  et du contenu depuis des PDF d’articles scientifiques créés numériquement.

Le système analyse le contenu du PDF et tente d’extraire des informations telles que le titre de l’article, le journal dans lequel il a été publié, la bibliographie (volume, pages, etc.), les auteurs et leurs affiliations, les mots-clés, le résumé…

Pour l’instant à l’étape de prototype, le projet reste expérimental mais très intéressant. Le code source étant disponible sur Github et le web service permet de tester le programme directement avec ses propres documents !

J’ai découvert cette technique lors de la conférence internationale DAS (Document Analysis System)

Référence :

Dominika Tkaczyk, Pawel Szostek, Piotr Jan Dendek, Mateusz Fedoryszak and Lukasz Bolikowski. CERMINE – automatic extraction of metadata and references from scientific literature. In 11th IAPR International Workshop on Document Analysis Systems, 2014.

Récolter les images de Flickr pour la reconstruction 3D

Lors de la conférence Electronic Imaging de 2013 organisée par l’IS&T/SPIE, Steve Seitz qui travaille à l’université de Washington et chez Google a présenté une keynote très intéressante intitulée « a trillion photos ».

Le principe est d’exploiter les millions d’images présentes dans les bases de données telles que Flickr. L’objectif du projet Building Rome in a Day est de récolter un maximum d’image en tapant simplement le mot clé « Rome » ou « Venise » dans Flickr. Une grande partie des images seront inexploitables car elles ne peuvent pas être mise en correspondance avec d’autres images, par exemple une photo de famille, d’un restaurant, etc. En revanche, les lieux les plus touristiques telles que la place « San Marco » sont prises en photos sous de nombreux angles différents. En utilisant une chaine de traitement classique telles que j’ai utilisé pendant ma thèse (SIFT+FLANN+RANSAC) il est possible de mettre en correspondance les images puis de faire la reconstruction 3D.

Dans cette vidéo de démonstration, les pyramides filiformes représentent les positions estimées de chaque prise de vue. La reconstruction a été faite en utilisant 14 079 photos. La reconstruction de Venise c’est fait en utilisant 250 000 images, 496 cœurs de calcul, 27h sont nécessaires pour la mise en correspondance et 38h pour la reconstruction.

 

 

 

Comprendre comment marchent les sacs de mots visuels

Depuis 10 ans [1], les sacs de mots visuels (aussi appelés bags of visual words, bags of features ou bags of keypoints) sont très largement utilisés dans la communauté de vision par ordinateur pour la classification et la reconnaissance d’image.

Calculer la similarité entre deux images est compliqué car ils y a beaucoup de pixels dans une image. Habituellement, on chercher à extraire des caractéristiques telles que la couleur, la forme ou la texture pour comparer des images. Une difficulté est de calculer des caractéristiques robustes aux rotations, zooms, changements d’illumination, bruit et occlusions. La plupart des techniques nécessitent de segmenter les images avant de décrire les objets à reconnaitre.

Les points d’intérêt tels que SIFT, SURF, etc. résolvent la plupart de ces problèmes : ils sont robuste aux transformations et n’ont pas besoin de segmentation, il est donc très facile de les utiliser. Extraire des points d’intérêt pour comparer des images est une bonne idée. Après l’extraction des points, il y a principalement des options : 1) mettre en correspondance les points d’une image avec les points d’une autre image pour faire la reconstruction de panorama, la reconnaissance et la localisation des objets ou 2) faire une description statistique des images en comptant les différents « genres » de points d’intérêt contenus dans l’image. C’est la technique des sacs de mots visuels (BoVW). Les BoVW sont utilisés pour la classification d’images.

Comment fonctionnent les sacs de mots visuels?

Voici le principe en 4 étapes :

  1. Extraire les points d’intérêt des images avec SURF par exemple.
  2. Créer un dictionnaire visuel  en partitionnant les points d’intérêt. Pour cela on peut utiliser k-means et fixer k entre 200 et 2 000.
  3. Pour une image, il faut vérifier dans quelle partition est chaque point d’intérêt. Un histogramme à 1 000 bins est alors construit, où chaque bin correspond à une partition. La valeur d’un bin est égale au nombre de point d’intérêt de l’image qui sont la partition correspondante.
  4. Chaque image est décrite par un vecteur, la classification peut être faite par un algorithme de classification supervisé tel que les SVM.

bovw

[1] Csurka, G., Dance, C., Fan, L., Willamowski, J., & Bray, C. (2004, May). Visual categorization with bags of keypoints. In Workshop on statistical learning in computer vision, ECCV (Vol. 1, No. 1-22, pp. 1-2).