UNIVERSITE NATIONALE DU VIETNAM, HANOI INSTITUT FRANCOPHONE INTERNATIONAL VŨ VIẾT MINH MISE EN PLACE D'UN APPRENTISSAGE DE METRIQUE POUR DU CLUSTERING SEMI-SUPERVISE INTERACTIF D'IMAGES THIẾT LẬP MỘT THUẬT TOÁN HỌC TỰ ĐỘNG CÁC CHỈ SỐ PHỤC VỤ CHO PHÂN LOẠI ẢNH TỰ ĐỘNG VÀ TƯƠNG TÁC MEMOIRE DE FIN D’ETUDES DU MASTER INFORMATIQUE HANOI – 2015 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com UNIVERSITE NATIONALE DU VIETNAM, HANOI INSTITUT FRANCOPHONE INTERNATIONAL VŨ VIẾT MINH MISE EN PLACE D'UN APPRENTISSAGE DE METRIQUE POUR DU CLUSTERING SEMI-SUPERVISE INTERACTIF D'IMAGES THIẾT LẬP MỘT THUẬT TOÁN HỌC TỰ ĐỘNG CÁC CHỈ SỐ PHỤC VỤ CHO PHÂN LOẠI ẢNH TỰ ĐỘNG VÀ TƯƠNG TÁC Spécialité: Systèmes Intelligents Multimédia Code: Programme pilote MEMOIRE DE FIN D’ETUDES DU MASTER INFORMATIQUE Sous la direction de: Mme Muriel Visani, Maître de Conférences HDR, Laboratoire L3i - Département Informatique, Université de La Rochelle HANOI – 2015 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ATTESTATION SUR L’HONNEUR J’atteste sur l’honneur que ce mémoire a été réalisé par moi-même et que les données et les résultats qui y sont présentés sont exacts et n’ont jamais été publiés ailleurs. La source des informations citées dans ce mémoire a été bien précisée. LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác.
Các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Signature de l’étudiant LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Table des gures iii Liste de Tableaux iv 1 Introduction 1 1.1 Problématique et Motivation .2 Objectifs et Principales Contributions. 2 2 Clustering semi-supervisé interactif incrémental 4 2.2 Clustering non-supervisé .1 Diérents types de méthodes .2 Présentation des méthodes de clustering non-supervisé utilisées .3 Clustering semi-supervisé .1 Diérents types de méthodes .2 Présentation de HMRF-KMeans .4 Modèle de clustering semi-supervisé interactif de LAI Hien Phuong .1 Introduction et Motivation .3 Stratégies de déduction des contraintes .4 Méthode de clustering semi-supervisé interactif incrémental. 23 3 Apprentissage de métrique 25 3.2 Distance de Mahalanobis .2 Diérents types d'approches d'apprentissage de métrique .3 Choix d'une méthode d'apprentissage de métrique dans notre contexte.
31 4 Intégration de l'apprentissage de métrique dans le système existant 34 4.2 Présentation de la méthode .2 Implémentation de la méthode. 38 i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Contents ii 4.2 Analyses des résultats obtenus .4 Discussion et Conclusion. 47 5 Conclusion 50 A Illustration des méthodes de clustering non-supervisé 53 B Mesures de qualité de clustering 55 C Résultat expérimental de l'algorithme MPCKMeans 57 D Résultats détaillés de quelques méthodes d'apprentissage de métrique 58 Bibliographie 62 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des gures 2.1 Illustration des méthodes de clustering non-supervisé hiérarchiques 1 .2 Illustration des méthodes basées sur les grilles .3 Comparaison des méthodes de clustering non supervisé .4 L'algorithme BIRCH : Construction de l'arbre CF-Tree .5 L'interface interactive du système de LAI Hien Phuong .6 Les résultats de la méthode de LAI Hien Phuong avec 6 stratégies diérentes 24 3.1 Une vue globale de l'apprentissage de métrique .2 Un exemple de la distance de Mahalanobis .3 Illustration de la méthode LMNN 2 .1 La méthode Baseline .2 MPCKMEANS_GLOBAL_DIAGONAL avec la distance Euclidienne .3 MPCKMEANS_GLOBAL_DIAGONAL avec la distance de Mahalanobis 46 4.4 Comparaison du temps d'exécution de toutes les méthodes .5 Comparaison de la performance .1 Illustration de l'algorithme BIRCH 3 .1 L'algorithme MPCKMeans appliqué sur la base Wang .2 Comparaison avec la méthode Baseline (DistE) .3 Comparaison avec la méthode Baseline (DistE et DistM). 61 iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste de Tableaux 2.1 Résumé des 6 stratégies de déduction de contraintes .1 Les méthodes pour l'expérimentation sur la base Wang .2 Les résultats expérimentaux sur la base Wang (1) .3 Les résultats expérimentaux sur la base Wang (2).
43 iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 1 Introduction Ce stage en recherche d'information multimédia, se place dans la suite de la thèse de LAI Hien Phuong, qui traite de l'analyse d'images par le contenu, et plus précisément du clustering semi-supervisé interactif d'images en vue de l'utilisation d'outils de navigation dans des bases d'images, ou de recherche par exemple. Son travail dans sa thèse est une étude complète sur les méthodes de clustering non-supervisé et semi-supervisé. Elle a proposé une nouvelle méthode de clustering semi-supervisé interactif dans le but de combler le fossé sémantique entre les concepts de haut niveau perçus par l'utilisateur dans la collection d'images, et les signatures de bas niveau extraites à partir des images originales. Dans un contexte interactif incrémental, sa méthode implique l'utilisateur dans la phase de clustering pour qu'il puisse interagir avec le système a n d'améliorer les résultats fournis par le modèle de clustering semi-supervisé automatique.
Son système convertit en contraintes entre paires de groupes d'images les informations supervisées fournies par l'utilisateur et procède itérativement au reclustering semi-supervisé en pénalisant ces contraintes. Tout d'abord, son système construit un modèle de clustering non-supervisé hiérarchique grâce à l'algorithme BIRCH pour représenter des images d'entrée dans une structure hiérarchique où les images similaires sont automatiquement regroupées dans des groupes compacts et représentatifs. Ensuite, les résultats de ce modèle de clustering non-supervisé sont présentés de façon visuelle à l'utilisateur pour qu'il puisse donner ses retours via des clics positifs et négatifs sur les images a chées ou via le déplacement des images entre des clusters. Beaucoup de stratégies de déduction des contraintes à partir des retours de l'utilisateur sont étudiées et expérimentées.
En tenant compte des contraintes par paires générées par ce moteur de déduction, le système réorganise la structure hiérarchique des données et refait le clustering en béné ciant d'une méthode de 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Introduction 2 clustering semi-supervisé. La boucle d'interaction peut être répétée jusqu'à la satisfaction de l'utilisateur.1 Problématique et Motivation Les mesures de la similarité et de la distance entre des observations jouent un rôle impor- tant dans les processus cognitifs humains et les systèmes arti ciels pour la reconnaissance et la catégorisation. La question de comment mesurer de manière appropriée la distance ou la similarité est cruciale pour la performance de nombreuses méthodes d'apprentis- sage et de fouille de données. La tâche principale dans tous les algorithmes de clustering est de déterminer à quel cluster appartient un point de données, c'est-à-dire que l'on a besoin d'une mesure de similarité / dissimilarité entre des points dans un ensemble de données.
La distance Euclidienne est une mesure de dissimilarité qui est largement utilisée. Mais cette distance géométrique n'est pas toujours parfaite, par exemple dans l'espace de données non-sphériques ou hétérogènes. Lorsque l'on travaille avec des don- nées multidimensionnelles, la distance Euclidienne traite toutes les dimensions de façon égale, mais dans quelques situations, on doit considérer quelques dimensions en priorité, on a donc besoin d'une métrique paramétrable. L'apprentissage de métrique qui uti- lise systématiquement la distance de Mahalanobis est une solution prometteuse.
L'idée principale des algorithmes d'apprentissage de métrique est d'apprendre un ensemble de paramètres qui contrôle une fonction de distance particulière, et le cas échéant de mettre à jour incrémentalement ces paramètres en fonction de nouvelles informations. Cette idée est compatible avec le système interactif incrémental où les nouvelles informations supervisées (sous forme de retours de l'utilisateur) sont fournies dans chaque itération et sont utilisées pour entraîner la métrique pour rendre le résultat du modèle de clustering plus satisfaisant pour l'utilisateur.2 Objectifs et Principales Contributions L'objectif principal du stage est de mettre en place un apprentissage de métrique grâce aux informations données incrémentalement par l'utilisateur, a n d'améliorer la per- formance de la phase de clustering. Ce travail de stage a pour principale contribution d'enrichir une méthode existante de clustering semi-supervisé dans un contexte interactif incrémental par des méthodes d'apprentissage de métrique. Les activités réalisées dans ce stage sont les suivantes : (1)Étude de l'état de l'art et du système existant proposé dans le contexte de la thèse de LAI Hien Phuong.
(2) Choix de l'algorithme d'appren- tissage de métrique à mettre en ÷uvre, et de la manière de l'articuler avec le système LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Introduction 3 existant. Après une étude sur les méthodes de clustering non-supervisé, semi-supervisé et semi-supervisé interactif et sur diérentes approches d'apprentissage de métrique, l'al- gorithme MPCKMeans (présenté dans la section 3. (3) L'implémentation d'un prototype permettant d'intégrer l'algorithme d'apprentissage de métrique dans le système existant. L'adaptation de l'algorithme MPCKMeans sur la structure de données hiérarchique qui est disponible dans le système existant est proposée.
Les résultats ex- périmentaux de cet algorithme avec diérentes con gurations sont analysés et comparés avec la méthode existante de LAI Hien Phuong. Les autres chapitres dans ce mémoire sont organisés comme suit : Le chapitre 2 présente l'état de l'art des méthodes de clustering non-supervisé, semi-supervisé et la méthode de clustering semi-supervisé interactif récemment proposée par LAI Hien Phuong. Le chapitre 3 présente l'état de l'art des algorithmes d'apprentissage de métrique et le choix d'une méthode adaptée à notre contexte applicatif. Le chapitre 4 présente l'intégration de la méthode d'apprentissage de métrique choisie dans le système existant et les résultats expérimentaux.
Le chapitre 5 termine ce travail par une conclusion. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 2 Clustering semi-supervisé interactif incrémental 2.1 Introduction L'apprentissage non supervisé consiste à inférer des connaissances sur les données. Car aucune information n'est fournie sur l'appartenance des données à telle ou telle classe, on souhaite trouver des groupes compacts et bien séparés et aecter à chaque observation une étiquette de classe (label). Les techniques de clustering non supervisé qui cherchent à décomposer un ensemble d'individus en plusieurs sous ensembles les plus homogènes possible sont présentées dans la section 2.
Quand on ajoute des informations supervisées incomplètes comme les étiquettes de quelques points ou des relations explicites entre quelques points, on s'oriente vers des méthodes de clustering semi-supervisé (cf. Comme dans la méthode semi-supervisée on a plus de connaissances données, on souhaite améliorer le résultat du clustering non-supervisé. LAI Hien Phuong a proposé un nouveau modèle de clustering semi-supervisé interactif incrémental (cf. Dans son système, les connaissances fournies par l'utilisateur qui interagit avec le système sont utilisées dans les itérations suivantes pour améliorer la performance du modèle.
Le dernier point que l'on doit clari er avant d'étudier les méthodes précisées, c'est le concept de "Incrémental versus non-incrémental" : Une méthode incrémentale va être exécutée de façon continue, et va intégrer les données au fur et à mesure de leur arrivée dans l'algorithme. C'est-à-dire, après chaque itération interactive, si on a des nouvelles données (peut être des informations supplémentaires, ou des retours d'utilisateur, .) elles seront utilisées dans l'itération suivante. À l'inverse, une méthode non-incrémentale va considérer un ensemble de données fournies en entrée, et sera exécutée sur cet ensemble. 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Clustering semi-supervisé interactif incrémental 5 Si, par la suite, une nouvelle donnée est fournie, celle-ci devrait être relancée en repartant de zéro.2 Clustering non-supervisé En général, le clustering automatique d'objets se base sur une mesure de similarité (ou distance) pour grouper les données.
Le clustering non supervisé est une analyse multi- dimensionnelle qui vise à partitionner l'ensemble des objets sans besoin d'informations supervisées comme des étiquettes des objets. Une partition ou bien un cluster est une division de l'ensemble en sous-ensembles, telle que chaque objet appartienne à un seul groupe. Les principales méthodes de clustering non supervisé comprennent : 1. Méthodes par partitionnement : Construire K partitions et les corriger jusqu'à obtenir une similarité satisfaisante.
Méthodes hiérarchiques : Créer une décomposition hiérarchique par agglomération ou division de groupes similaires ou dissimilaires. Méthodes basées sur la densité : Grouper les objets tant que la densité de voisinage excède une certaine limite.