Bi-Stochastic Scaling of Matrices for Block Structure Detection and Applications
Équilibrage bi-stochastique des matrices pour la détection de structures par blocs et applications
Résumé
The detection of block structures in matrices is an important challenge. First in data analysis where matrices are a key tool for data representation, as data tables or adjacency matrices. Indeed, for the first one, finding a co-clustering is equivalent to finding a row and column block structure of the matrix. For the second one, finding a structure of diagonal dominant blocks leads to a clustering of the data. Moreover, block structure detection is also usefull for the resolution of linear systems. For instance, it helps to create efficient Block Jacobi precoditioners or to find groups of rows that are strongly decorrelated in order to apply a solver such as Block Cimmino. In this dissertation, we focus our analysis on the detection of dominant diagonal block structures by symmetrically permuting the rows and columns of matrices. Lots of algorithms have been designed that aim to highlight such structures. Among them, spectral algorithms play a key role. They can be divided into two kinds. The first one consists of algorithms that first project the matrix rows onto a low-dimensional space generated by the matrix leading eigenvectors, and then apply a procedure such as a k-means on the reduced data. Their main drawbacks is that the knowledge of number of clusters to uncover is required. The second kind consists of iterative procedures that look for the k-th best partition into two subblocks of the matrix at step k. However, if the matrix structure shows more than two blocks, the best partition into two blocks may be a poor fit to the matrix groundtruth structure. Hence, we propose a spectral algorithm that deals with both issues described above. To that end, we preprocess the matrix with a doubly-stochastic scaling, which leverages the blocks. First we show the benefits of using such a scaling by using it as a preprocessing for the Louvain's algorithm, in order to uncover community structures in networks. We also investigate several global modularity measures designed for quantifying the consistency of a block structure. We generalise them to make them able to handle doubly-stochastic matrices, and thus we remark that our scaling tends to unify these measures. Then, we describe our algorithm that is based on spectral elements of the scaled matrix. Our method is built on the principle that leading singular vectors of a doubly-stochastic matrix should have a staircase pattern when their coordinates are sorted in the increasing order, under the condition that the matrix shows a hidden block structure. Tools from signal processing-that have been initially designed to detect jumps in signals-are applied to the sorted vectors in order to detect steps in these vectors, and thus to find the separations between the blocks. However, these tools are not specifically designed to this purpose. Hence procedures that we have implemented to answer the encountered issues are also described. We then propose three applications for the matrices block structure detection. First, community detection in networks, and the design of efficient Block Jacobi type preconditioners for solving linear systems. For these applications, we compare the results of our algorithm with those of algorithms that have been designed on purpose. Finally, we deal with the dialogue act detection in a discorsre, using the STAC database that consists in a chat of online players of " The Settlers of Catan ". To that end we connect classical clustering algorithms with a BiLSTM neural network taht preprocesses the dialogue unities. Finally, we conclude by giving some preliminary remarks about the extension of our method to rectangular matrices.
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.
Origine : Version validée par le jury (STAR)
Loading...