Date : 2023
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : anglais / English
Apprentissage non supervisé (intelligence artificielle)
Résumé / Abstract : Plusieurs méthodes d'apprentissage non supervisé de clusterings de données multidimensionnelles nécessitent la spécification du nombre souhaité de clusters ou le nombre d'éléments des clusters. Ces paramètres introduisent donc un certain degré d'arbitrarité qui remet en question la qualité du clustering. Pour résoudre ce problème, nous introduisons une nouvelle approche adaptée aux ensembles de données tensorielles d'ordre 3 et qui étudient les tranches matricielles de ces données tensorielles. Nous présentons différentes méthodes, notamment, le Clustering Multi-Tranches (Multi-Slice Clustering - MSC), son extension pour la détermination de plusieurs clusters, et le Clustering Multi-Directionnel via Matrice d'Affinité (Multiway Clustering via Affinity Matrix - MCAM). La méthode MSC vise à trouver les tranches signal qui se trouvent dans un sous-espace de dimension inférieure, et qui modélise ces tranches similaires. Notre algorithme MSC pour les tenseurs de rang-1 est corroboré par une preuve théorique. Nous analysons chaque dimension, ou chaque mode des données, indépendamment les unes des autres, et effectuons une décomposition spectrale de chaque tranche de notre tenseur. Puis, nous définissons une mesure de similarité entre les tranches. Cette mesure sera bornée par un seuil de précision à partir duquel nous identifierons un cluster. Le produit cartésien de deux clusters de deux differents modes fournit le biclustering et le produit cartesien de tous les clusters des trois modes fournit le triclustering. L'efficacité de cet algorithme est démontrée sur des ensembles de données synthétiques et réelles. Une deuxième résultat à signaler est la méthode MSC-DBSCAN qui est une version améliorée de la méthode MSC. Elle estplus performante pour les ensembles de données qui ont des rangs quelconques (r = 1) selon la décomposition dite CP (restant sur des tenseurs d'ordre 3). L'algorithme est capable d'identifier plusieurs clusters parmi les tranches signal. La méthode MCAM recherche la partition complète des données tensorielles d'ordre 3, en traitant chaque mode indépendamment. Une fois de plus, le modèle est basé sur la similarité entre les tranches du tenseur en étudiant l'étalement des données de chaque tranche. La méthode construit une matrice d'affinité/similarité sur laquelle nous appliquonsdes méthodes avancées de clustering. Il existe plusieurs algorithmes performants de clustering qui peuvent être appliqués à la matrice de similarité pour y identifier des groupes similaires. La combinaison des clusters des trois modes permet d'obtenir le clustering multidirectionnel souhaité. Notre algorithme est testé sur des ensembles de données synthétiques et réelles. Nous comparons ses performances avec d'autres algorithmes connus et prouvons sa pertinence.Pour le passage à l'échelle, nous introduisons la version parallèle de l'algorithme MSC avec un système de mémoire distribuée. En raison de la manière particulière dont il est mis en oeuvre, le MSC s'adapte bien à ces calculs de performances en utilisant Messages-Passing Interface (MPI) pour la communication entre les processeurs. Nous trouvons une méthodepour distribuer les jeux de données tensorielles qui nous permet d'avoir une performance significative. Nos expériences confirment alors un strict gain de temps/performance pour des données de grandes tailles. Ceci est un autre point fort de notre travail. La nouvelle méthode devrait s'exporter à nos autres algorithmes qui s'avèrent également tous adaptésau passage à l'échelle, et pourrait s'appliquer sûrement à d'autres encore au-delà de notre schéma.
Résumé / Abstract : Several unsupervised learning methods of clustering of multidimensional datasets require the specification of the desired number of clusters, or the set of cluster sizes. They therefore introduce a certain degree of arbitrariness which questions the clustering quality. To address this issue, we introduce novel approaches tailored for 3rd-order tensor datasets and which deal with matrix slices of data within the tensors. We present several methods, including Multi-Slice Clustering (MSC) and its extension to address multiple clusters, as well as Multiway Clustering via Affinity Matrix (MCAM). The MSC method aims to find the signal slices that lie in a low dimensional subspace with a cluster modeling these similar slices. The resulting MSC algorithm stands with a theoretical proof for rank-1 tensors. We analyse each dimension or tensor mode, and perform a spectral decomposition of each tensor slice, i.e. a matrix. Then, we define a similarity measure between matrix slices. This measure will be bounded by a threshold (precision) parameter, and we will identify a cluster based on that. The Cartesian product of two partial clusters provides the desired tensor biclustering, and the Cartesian product of all clustersgives the triclustering. The effectiveness of this algorithm is shown on both synthetic and real-world data sets. A second result to report consists in the MSC-DBSCAN method which improves the MSC. It has high performance for datasets that are sums of r > 1 rank-1 tensors (still of 3rd-order). The ensuing algorithm finds multiple clusters among the signal slices. The MCAM method seeks the full partition of 3rd-order datasets, treating each mode independently. Once again, the model is based on the similarity between the tensor slices and the spread of information of each slice. The method builds an affinity/similarity matrix on which we apply advanced clustering methods. There are several advanced clusteringalgorithms that can be applied to the similarity matrix for identifying similar groups. Combining the three mode clusters delivers the desired multiway clustering. Our algorithm is tested on both synthetics and real-world datasets. We compare its performance with other known algorithms and prove its significance.In order to achieve scalability, we introduce a parallel version of the MSC algorithm with a distributed memory system. The MSC fits well with such performance calculations because of the way it is implemented, which uses Message-Passing Interface (MPI) for communication between processors. We find a method to distribute the tensorial datasets that allows us to achieve relevant performance. Our experiments confirm a strict performance gain for large data sets. This is yet another strength of our work. The new method should be exported to our other scalable algorithms which are also all suited to scaling, and could surely be applied to others beyond our scheme.