Unsupervised extra trees: a stochastic approach to compute similarities in heterogeneous data

In this paper, we present a method to compute similarities on unlabelled data, based on extremely randomised trees. The main idea of our method, unsupervised extremely randomised 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 instances in the leaves of each generated tree. We evaluate our method on synthetic and real-world datasets by comparing the mean similarities between instances with the same label and the mean similarities between instances with different labels. These metrics are analogous to intracluster and intercluster similarities, and they 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 instances belonging to different clusters and gives indiscernible values when there is no cluster structure. We also assess some interesting properties such as invariance under monotonic transformations of variables and robustness to correlated variables and noise. Finally, we perform hierarchical agglomerative clustering on synthetic and both real-world homogeneous and heterogeneous datasets and compare the results obtained by using UET and by using standard similarity measures. Our experiments show that our approach based on UET outperforms existing methods in some cases and reduces the amount of preprocessing typically needed when dealing with real-world datasets.