LogoLogo

Le Gorrec, Luce. Équilibrage bi-stochastique des matrices pour la détection de structures par blocs et applications

Le Gorrec, Luce (2019). Équilibrage bi-stochastique des matrices pour la détection de structures par blocs et applications.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
13Mb

Résumé en francais

La détection de structures par blocs dans les matrices est un enjeu important. D'abord en analyse de données, où les matrices sont classiquement utilisées pour représenter des données, par exemple via les tables de données ou les matrices d'adjacence. Dans le premier cas, la détection d'une structure par blocs de lignes et de colonnes permet de trouver un co-clustering. Dans le second cas, la détection d'une structure par blocs diagonaux dominants fournit un clustering. En outre, la détection d'une structure par blocs est aussi utile pour la résolution de systèmes linéaires car elle permet, notamment, de rendre efficace des préconditionneurs type Block Jacobi, ou de trouver des groupes de lignes fortement décorrélés en vue de l'application d'un solveur type Block Cimmino. Dans cette thèse, nous centrons notre analyse sur la détection de blocs diagonaux dominants par permutations symétriques des lignes et des colonnes. De nombreux algorithmes pour trouver ces structures ont été créés. Parmi eux, les algorithmes spectraux jouent un rôle crucial, et se divisent en deux catégories. La première est composée d'algorithmes qui projettent les lignes de la matrice dans un espace de faible dimension composé des vecteurs propres dominants avant d'appliquer une procédure de type k-means sur les données réduites. Ces algorithmes ont le désavantage de nécessiter la connaissance du nombre de classes à découvrir. La deuxième famille est composée de procédures itératives qui, à chaque itération, cherchent la k-ième meilleure partition en deux blocs. Mais pour les matrices ayant plus de deux blocs, la partition optimale en deux blocs ne coïncide en général pas avec la véritable structure. Nous proposons donc un algorithme spectral répondant aux deux problèmes évoqués ci-dessus. Pour ce faire, nous prétraitons notre matrice via un équilibrage bi-stochastique permettant de stratifier les blocs. D'abord, nous montrons les bénéfices de cet équilibrage sur la détection de structures par blocs en l'utilisant comme prétraitement de l'algorithme de Louvain pour détecter des communautés dans des réseaux. Nous explorons aussi plusieurs mesures globales utilisées pour évaluer la cohérence d'une structure par blocs. En adaptant ces mesures à nos matrices bi-stochastiques, nous remarquons que notre équilibrage tend à unifier ces mesures. Ensuite, nous détaillons notre algorithme basé sur les éléments propres de la matrice équilibrée. Il est construit sur le principe que les vecteurs singuliers dominants d'une matrice bi-stochastique doivent présenter une structure en escalier lorsque l'on réordonne leurs coordonnées dans l'ordre croissant, à condition que la matrice ait une structure par blocs. Des outils de traitement du signal, initialement conçus pour détecter les sauts dans des signaux, sont appliqués aux vecteurs pour en détecter les paliers, et donc les séparations entre les blocs. Cependant, ces outils ne sont pas naturellement adaptés pour cette utilisation. Des procédures, mises en place pour répondre à des problèmes rencontrés, sont donc aussi détaillées. Nous proposons ensuite trois applications de la détection de structures par blocs dans les matrices. D'abord la détection de communautés dans des réseaux, et le préconditionnement de type Block Jacobi de systèmes linéaire. Pour ces applications, nous comparons les résultats de notre algorithme avec ceux d'algorithmes spécifiquement conçus à cet effet. Enfin, la détection des actes de dialogues dans un discours en utilisant la base de données STAC qui consiste en un chat de joueurs des "Colons de Catane" en ligne. Pour ce faire nous couplons des algorithmes de clustering non supervisés avec un réseau de neurones BiLSTM permettant de prétraiter les unités de dialogue. Enfin, nous concluons en entamant une réflexion sur la généralisation de notre méthode au cas des matrices rectangulaires.

Sous la direction du :
Directeur de thèse
Ruiz, Daniel
Mouysset, Sandrine
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Recherche en Informatique de Toulouse (IRIT), UMR 5505
Mots-clés libres :Équilibrage bi-stochastique - Méthodes spectrales - Classification non supervisée - Détection de communautés - Traitement automatique du langage naturel
Sujets :Informatique
Déposé le :07 Feb 2020 15:58