ACTUALITÉ SCIENTIFIQUE
ET INNOVATION DE L'ÉTS
SLK : un algorithme de partitionnement performant - Par : Imtiaz Masud Ziko, Éric Granger, Ismail Ben Ayed,

SLK : un algorithme de partitionnement performant


Imtiaz Masud Ziko
Imtiaz Masud Ziko Profil de l'auteur(e)
Imtiaz Masud Ziko est étudiant au doctorat en apprentissage machine au Département d’ingénierie des systèmes de l’ÉTS.

Éric Granger
Éric Granger est professeur au Département de génie des systèmes de l’ÉTS. Ses recherches portent sur l’apprentissage machine, la reconnaissance de formes, la vision par ordinateur, et les systèmes adaptatifs et intelligents.

Ismail Ben Ayed
Ismail Ben Ayed Profil de l'auteur(e)
Ismail Ben Ayed est professeur au Département de génie des systèmes de l’ÉTS. Son travail se concentre sur la conception d’algorithmes efficaces pour le traitement, l’analyse et l’interprétation des images médicales.

Apprentissage machine

Achetée sur Istock.com. Droits d’auteur

RÉSUMÉ:

L’apprentissage machine sans supervision au moyen d’exemples s’appelle l’apprentissage non supervisé. L’analyse de partitionnement (cluster) est une méthode d’apprentissage non supervisée très courante qui vise à grouper des instances similaires à partir d’un ensemble de donnés non étiquetées. Dans les scénarios à grande échelle, les solutions de partitionnement et l’évolutivité peuvent s’avérer problématiques. Nous proposons ici une méthode efficace nommée K-modes laplacien évolutif (Scalable Laplacian K-modes, SLK) qui combine deux objectifs de partitionnement basés sur centroïdes et par paires dans une même formulation pour optimiser efficacement et rapidement l’algorithme distribué en offrant une meilleure performance que la plupart des méthodes existantes.

Organiser une énorme quantité de données

Les progrès des technologies d’acquisition de données par Internet, médias numériques, réseaux sociaux, vidéosurveillance et les secteurs commerciaux en croissance ont produit des quantités massives de données de grandes dimensions. Afin de créer un modèle ingénieux relativement aux applications qui s’y rapportent, il faut pouvoir manipuler ces énormes volumes de données. Il est donc nécessaire de faire l’analyse automatique des données. La littérature dénombre une grande quantité d’algorithmes de partitionnement, outils permettant d’analyser des données par l’extraction de modèles similaires de distribution des données, de manière non supervisée.  Ces techniques ont servi à un large éventail d’applications en analyse de données commerciales, de marché, de réseaux sociaux et beaucoup d’autres liées à l’IA. Cependant, organiser une grande quantité de données hautement dimensionnelles en groupes significatifs est très difficile en raison de problèmes d’évolutivité et d’efficacité. C’est le cas par exemple des sites de partage de photos populaires comme Facebook ou Instagram, où il faut gérer le téléchargement de millions de photos par jour.

Algorithme de partitionnement pour classifier les images

Images classées par caractéristiques similaires

De nombreux algorithmes de partitionnement sont proposés dans la littérature. Toutefois, un algorithme de partitionnement particulier convenant à une application précise ne réussit pas nécessairement dans des applications connexes. Nous proposons le SLK (Scalable Laplacian K-modes: une méthode de partitionnement qui combine deux modèles bien connus et fournit une manière intelligente d’optimisation pour obtenir un algorithme distribué rapide et offrant une meilleure performance que la plupart des méthodes existantes. Ce travail de recherche a été qualifié d’article vedette par NeurIPS (Neural Information Processing Systems), considéré sans contredit comme la plus grande conférence d’IA et d’apprentissage machine.

Partionnement par K-modes laplacien évolutif (SLK)

K-modes laplacien évolutif (Scalable Laplacian K-modes)

Comme nous l’avons dit, le SLK combine deux modèles : K-modes et le bien connu laplacien. Les K-modes repèrent le mode de chaque grappe, comme dans la très populaire méthode de l’écart moyen. Le terme « mode » désigne en gros l’échantillon le plus représentatif du sommet d’une distribution. Le terme « laplacien » apporte de la cohérence dans les grappes en imposant les mêmes attributions pour les échantillons de données proches et aide ainsi à trouver des grappes structurées multiples comme les spirales illustrées ci-dessous.

partionnement en spirale

 

Bien que prometteur, ce modèle pose un problème d’optimisation très complexe en raison de contraintes discrètes et laplaciennes. Nous proposons une relaxation concave-convexe de la formulation et une méthode d’optimisation itérative qui résout la parallèle du problème de partitionnement à chaque itération. Cette solution fournit également le mode représentatif de chaque grappe comme sous-produit en complexité de temps linéaire, que nous appelons SLK-BO. Cette approche rend l’algorithme plus rapide que la variante SLK-MS qui repère le mode avec un algorithme itératif. 

Nous avons effectué des expériences élaborées sur divers ensembles de données contenant pour la plupart des images ou des données numériques. Nous utilisons le NMI (Normalized Mutual Information) et l’ACC (clustering ACCuracy) comme mesures de performance. Plus les valeurs sont élevées, meilleures sont les performances. Nous évaluons également le temps en secondes nécessaire à l’organisation des données. Plus le temps est bas, meilleure est la performance.

Résultats de partitionnement pour différentes banques de données

Tableau : NMI/ACC obtenus, partie supérieure; temps écoulé moyen en secondes, partie inférieure.

D’après le tableau, on peut observer que la méthode SLK-MS/SLK-BO est supérieure en précision et en rapidité. Par exemple, dans l’ensemble de données MNIST, colonne (code), 95 % des images ont été organisées correctement, de façon automatique, en fonction de leur similarité, et sans supervision. Également, pour ce qui est de la synchronisation, SLK est beaucoup plus rapide que les autres méthodes, en particulier pour les ensembles de données de grandes dimensions comme LabelMe (GIST) et YTF, et évolutif pour ce qui est des grands ensembles de données Reuters. 

Informations supplémentaires

Les détails techniques sur le groupement SLK (SLK clustering) sont décrits dans l’article de Neurips : https://papers.nips.cc/paper/8208-scalable-laplacian-k-modes.pdf

Le langage Python est décrit à : https://github.com/imtiazziko/SLK

Imtiaz Masud Ziko

Profil de l'auteur(e)

Imtiaz Masud Ziko est étudiant au doctorat en apprentissage machine au Département d’ingénierie des systèmes de l’ÉTS.

Programme : Génie de la production automatisée 

Chaire de recherche : Chaire de recherche ÉTS sur l’intelligence artificielle en imagerie médicale 

Laboratoires de recherche : LIVIA – Laboratoire d'imagerie, de vision et d'intelligence artificielle 

Profil de l'auteur(e)

Éric Granger

Profil de l'auteur(e)

Éric Granger est professeur au Département de génie des systèmes de l’ÉTS. Ses recherches portent sur l’apprentissage machine, la reconnaissance de formes, la vision par ordinateur, et les systèmes adaptatifs et intelligents.

Programme : Génie de la production automatisée 

Laboratoires de recherche : LIVIA – Laboratoire d'imagerie, de vision et d'intelligence artificielle  LiNCS – Laboratoire en ingénierie cognitive et sémantique 

Profil de l'auteur(e)

Ismail Ben Ayed

Profil de l'auteur(e)

Ismail Ben Ayed est professeur au Département de génie des systèmes de l’ÉTS. Son travail se concentre sur la conception d’algorithmes efficaces pour le traitement, l’analyse et l’interprétation des images médicales.

Programme : Génie de la production automatisée 

Chaire de recherche : Chaire de recherche ÉTS sur l’intelligence artificielle en imagerie médicale 

Laboratoires de recherche : LIVIA – Laboratoire d'imagerie, de vision et d'intelligence artificielle 

Profil de l'auteur(e)


commentaires

    Laisser un commentaire

    Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *