Équilibrage bi-stochastique des matrices pour la détection de structures par blocs et applications

La detection de structures par blocs dans les matrices est un enjeu important. D'abord en analyse de donnees, ou les matrices sont classiquement utilisees pour representer des donnees, par exemple via les tables de donnees ou les matrices d'adjacence. Dans le premier cas, la detection d'une structure par blocs de lignes et de colonnes permet de trouver un co-clustering. Dans le second cas, la detection d'une structure par blocs diagonaux dominants fournit un clustering. En outre, la detection d'une structure par blocs est aussi utile pour la resolution de systemes lineaires car elle permet, notamment, de rendre efficace des preconditionneurs type Block Jacobi, ou de trouver des groupes de lignes fortement decorreles en vue de l'application d'un solveur type Block Cimmino. Dans cette these, nous centrons notre analyse sur la detection de blocs diagonaux dominants par permutations symetriques des lignes et des colonnes. De nombreux algorithmes pour trouver ces structures ont ete crees. Parmi eux, les algorithmes spectraux jouent un role crucial, et se divisent en deux categories. La premiere est composee d'algorithmes qui projettent les lignes de la matrice dans un espace de faible dimension compose des vecteurs propres dominants avant d'appliquer une procedure de type k-means sur les donnees reduites. Ces algorithmes ont le desavantage de necessiter la connaissance du nombre de classes a decouvrir. La deuxieme famille est composee de procedures iteratives qui, a chaque iteration, cherchent la k-ieme meilleure partition en deux blocs. Mais pour les matrices ayant plus de deux blocs, la partition optimale en deux blocs ne coincide en general pas avec la veritable structure. Nous proposons donc un algorithme spectral repondant aux deux problemes evoques ci-dessus. Pour ce faire, nous pretraitons notre matrice via un equilibrage bi-stochastique permettant de stratifier les blocs. D'abord, nous montrons les benefices de cet equilibrage sur la detection de structures par blocs en l'utilisant comme pretraitement de l'algorithme de Louvain pour detecter des communautes dans des reseaux. Nous explorons aussi plusieurs mesures globales utilisees pour evaluer la coherence d'une structure par blocs. En adaptant ces mesures a nos matrices bi-stochastiques, nous remarquons que notre equilibrage tend a unifier ces mesures. Ensuite, nous detaillons notre algorithme base sur les elements propres de la matrice equilibree. Il est construit sur le principe que les vecteurs singuliers dominants d'une matrice bi-stochastique doivent presenter une structure en escalier lorsque l'on reordonne leurs coordonnees dans l'ordre croissant, a condition que la matrice ait une structure par blocs. Des outils de traitement du signal, initialement concus pour detecter les sauts dans des signaux, sont appliques aux vecteurs pour en detecter les paliers, et donc les separations entre les blocs. Cependant, ces outils ne sont pas naturellement adaptes pour cette utilisation. Des procedures, mises en place pour repondre a des problemes rencontres, sont donc aussi detaillees. Nous proposons ensuite trois applications de la detection de structures par blocs dans les matrices. D'abord la detection de communautes dans des reseaux, et le preconditionnement de type Block Jacobi de systemes lineaire. Pour ces applications, nous comparons les resultats de notre algorithme avec ceux d'algorithmes specifiquement concus a cet effet. Enfin, la detection des actes de dialogues dans un discours en utilisant la base de donnees STAC qui consiste en un chat de joueurs des "Colons de Catane" en ligne. Pour ce faire nous couplons des algorithmes de clustering non supervises avec un reseau de neurones BiLSTM permettant de pretraiter les unites de dialogue. Enfin, nous concluons en entamant une reflexion sur la generalisation de notre methode au cas des matrices rectangulaires.