Centre Universitaire d'Informatique

M. Eniko Szekely soutiendra, en vue de l'obtention du grade de docteur ès sciences, mention informatique, sa thèse intitulée

Dimension reduction for clustered high-dimensional data

Abstract :

The need for knowledge discovery from data has always represented a main challenge in many domains. Recent times have witnessed the transition towards a significantly larger scale both in the number of samples and the number of attributes characterising real-world data. It is this latter aspect, the dimensionality of the data, that is at the center of the present thesis.

In high-dimensional representation spaces, data exhibits specific behaviours that are not common in spaces of lower dimensionality. In this thesis, we first concentrate on studying the behaviour of distances in high dimensions. We analyse the evolution of the distance contrast with increasing dimensionality and emphasise its dual character: absolute vs. relative. This duality is a key aspect of high-dimensional data and plays an important role in understanding and assessing the significance of distances in high dimensions.

Our second focus is on clustered structures, still in the context of high-dimensional data. Clustering high-dimensional data is a challenging task due to the complex structure of real-world data. In this context, dimension reduction emerged as a powerful solution to the analysis of high-dimensional data. Instead of performing the analysis in the high-dimensional space, a lower-dimensional space is found through dimension reduction and further analysis is performed in this reduced space. Our aim in this thesis is to find low-dimensional embeddings with strong discriminative power. In a first contribution, the High-Dimensional Multimodal Distribution Embedding, we exploit distance distributions in high dimensions and propose a distance-based embedding method. The strength of the method is due to a distance transformation that we apply prior to embedding and that increases the cluster preservation capability of the low-dimensional space. Next, the Cluster Space projects points in the space of the clusters using the probabilities obtained from a Gaussian mixture model. The intrinsic relationship of the Cluster Space with the quadratic discriminant function justifies its strong discriminative power.

Overall, the current thesis addresses the study of the behaviour of distances in high dimensions and the dimension reduction as a solution for finding discriminant and structure preserving low-dimensional embeddings.

Date: Jeudi 31 mars 2011 à 14h30

Lieu: Site de Battelle (bât. A, auditoire rez-de-chaussée) - 7 route de Drize - 1227 Carouge

À la Une