A random tree-based approach to compute dissimilarities : an application to clustering on diverse data structures
Une approche stochastique à base d’arbres aléatoires pour le calcul de dissimilarités : application au clustering pour diverses structures de données
Résumé
The notion of distance, and more generally of dissimilarity, is an important one in data mining, especially in unsupervised approaches. The algorithms belonging to this class of methods aim at grouping objects in an homogeneous way, and many of them rely on a notion of dissimilarity, in order to quantify the proximity between objects. The choice of algorithms as well as that of dissimilarities is not trivial. Several elements can motivate these choices, such as the type of data – homogeneous data or not –, their representation – feature vectors, graphs –, or some of their characteristics – highly correlated, noisy, etc. –. Although many measures exist, their choice can become complex in some specific settings. This leads to additional complexity in data mining tasks. In this thesis, we present a new approach for computing dissimilarities based on random trees. It is an original approach, which has several advantages such as a great versatility. Indeed, using different dissimilarity calculation modules that we can plug to the method, it becomes possible to apply it in various settings. In particular, we present in this document two modules, enabling the computation of dissimilarities - and, in fine, clustering - on data structured as feature vectors, and on data in the form of graphs. We discuss the very promising results obtained by this approach, as well as the numerous perspectives that it opens, such as the computation of dissimilarity in the framework of attributed graphs, through a unified approach.
La notion de distance, et plus généralement de dissimilarité, est une notion importante en fouille de données, tout particulièrement dans les approches non supervisées. Les algorithmes de cette classe de méthodes visant à regrouper de manière homogène des objets, nombre d’entre eux s’appuient sur une notion de dissimilarité, afin de quantifier la proximité entre objets. Le choix des algorithmes ainsi que celui des dissimilarités n’est cependant pas trivial. Plusieurs éléments peuvent motiver ces choix, tels que le type de données – données homogènes ou non –, leur représentation – vecteurs d’attributs, graphes –, ou encore certaines de leurs caractéristiques – fortement corrélées, bruitées, etc. –. Bien que de nombreuses mesures existent, leur choix peut devenir complexe dans certains cadres spécifiques. Ceci entraîne une complexité supplémentaire dans les tâches d’exploration et de fouille des données. Nous présentons dans cette thèse une nouvelle approche permettant le calcul de dissimilarités, basée sur des arbres aléatoires. Il s’agit d’une approche originale dont nous montrons plusieurs avantages, parmi lesquels l’on retrouve une grande versatilité. En effet, par le biais de différents modules de calcul de dissimilarités que nous accolons à la méthode, il devient possible de l’appliquer dans divers cadres. Nous présentons notamment dans ce document deux modules, permettant le calcul de dissimilarités — et, in fine, le clustering — sur des données structurées sous forme de vecteur d’attributs, et sur des données sous forme de graphes. Nous discutons des résultats très prometteurs obtenus par cette approche, ainsi que des nombreuses perspectives ouvertes par cette dernière, telle que le calcul de dissimilarité dans le cadre des graphes attribués, par le biais d’une approche unifiée.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|