Unsupervised Extra Trees: a stochastic approach to compute similarities in heterogeneous data.

Kevin Dalleau 1, 2 Miguel Couceiro 3 Malika Smail-Tabbone 2
2 CAPSID - Computational Algorithms for Protein Structures and Interactions
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
3 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : In this paper we present a method to compute similarities on unlabeled data, based on extremely randomized trees. The main idea of our method, Unsu-pervised Extremely Randomized Trees (UET) is to randomly split the data in an iterative fashion until a stopping criterion is met, and to compute a similarity based on the co-occurrence of samples in the leaves of each generated tree. Using a tree-based approach to compute similarities is interesting, as the inherent We evaluate our method on synthetic and real-world datasets by comparing the mean similarities between samples with the same label and the mean similarities between samples with different labels. These metrics are similar to intracluster and intercluster similarities, and are used to assess the computed similarities instead of a clustering algorithm's results. Our empirical study shows that the method effectively gives distinct similarity values between samples belonging to different clusters, and gives indiscernible values when there is no cluster structure. We also assess some interesting properties such as in-variance under monotone transformations of variables and robustness to correlated variables and noise. Finally , we performed hierarchical agglomerative clustering on synthetic and real-world homogeneous and heterogeneous datasets using UET versus standard similarity measures. Our experiments show that the algorithm outperforms existing methods in some cases, and can reduce the amount of preprocessing needed with many real-world datasets.
Document type :
Preprints, Working Papers, ...
Liste complète des métadonnées

https://hal.inria.fr/hal-01982232
Contributor : Kevin Dalleau <>
Submitted on : Tuesday, January 15, 2019 - 3:04:52 PM
Last modification on : Wednesday, April 3, 2019 - 1:23:15 AM
Document(s) archivé(s) le : Tuesday, April 16, 2019 - 2:31:22 PM

File

UET_paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01982232, version 1

Citation

Kevin Dalleau, Miguel Couceiro, Malika Smail-Tabbone. Unsupervised Extra Trees: a stochastic approach to compute similarities in heterogeneous data.. 2019. ⟨hal-01982232⟩

Share

Metrics

Record views

78

Files downloads

155