On Perfect Clustering of High Dimension, Low Sample Size Data

Soham Sarkar
IEEE COMPUTER SOC, 2020
Article

Résumé

Popular clustering algorithms based on usual distance functions (e.g., the Euclidean distance) often suffer in high dimension, low sample size (HDLSS) situations, where concentration of pairwise distances and violation of neighborhood structure have adverse effects on their performance. In this article, we use a new data-driven dissimilarity measure, called MADD, which takes care of these problems. MADD uses the distance concentration phenomenon to its advantage, and as a result, clustering algorithms based on MADD usually perform well for high dimensional data. We establish it using theoretical as well as numerical studies. We also address the problem of estimating the number of clusters. This is a challenging problem in cluster analysis, and several algorithms are available for it. We show that many of these existing algorithms have superior performance in high dimensions when they are constructed using MADD. We also construct a new estimator based on a penalized version of the Dunn index and prove its consistency in the HDLSS asymptotic regime. Several simulated and real data sets are analyzed to demonstrate the usefulness of MADD for cluster analysis of high dimensional data.

Official source

https://infoscience.epfl.ch/record/279533?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Soham Sarkar
IEEE COMPUTER SOC, 2020
Article

Résumé

Official source

https://infoscience.epfl.ch/record/279533?ln=fr

À propos de ce résultat

Concepts associés (21)

Le terme dimension, du latin dimensio « action de mesurer », désigne d’abord chacune des grandeurs d’un objet : longueur, largeur et profondeur, épaisseur ou hauteur, ou encore son diamètre si c'est

vignette|Représentation du jeu de données Iris sur ses quatre dimensions|420x420px Un jeu de données (en anglais dataset ou data set) est un ensemble de valeurs « organisées » ou « contextualisées » (

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points

Afficher plus

Concepts associés

Chargement

Publications associées (28)

Publications associées

Chargement

On some graph-based two-sample tests for high dimension, low sample size data

Soham Sarkar

Testing for equality of two high-dimensional distributions is a challenging problem, and this becomes even more challenging when the sample size is small. Over the last few decades, several graph-based two-sample tests have been proposed in the literature, which can be used for data of arbitrary dimensions. Most of these test statistics are computed using pairwise Euclidean distances among the observations. But, due to concentration of pairwise Euclidean distances, these tests have poor performance in many high-dimensional problems. Some of them can have powers even below the nominal level when the scale-difference between two distributions dominates the location-difference. To overcome these limitations, we introduce some new dissimilarity indices and use them to modify some popular graph-based tests. These modified tests use the distance concentration phenomenon to their advantage, and as a result, they outperform the corresponding tests based on the Euclidean distance in a wide variety of examples. We establish the high-dimensional consistency of these modified tests under fairly general conditions. Analyzing several simulated as well as real data sets, we demonstrate their usefulness in high dimension, low sample size situations.

SPRINGER2020

Chargement

Tests of mutual independence among several random vectors using univariate and multivariate ranks of nearest neighbours

Soham Sarkar

Testing mutual independence among several random vectors of arbitrary dimensions is a challenging problem in Statistics, and it has gained considerable interest in recent years. In this article, we propose some nonparametric tests based on different notions of ranks of nearest neighbour. These proposed tests can be conveniently used for high dimensional data, even when the dimensions of the random vectors are larger than the sample size. We investigate the performance of these tests on several simulated and real data sets and also use them in identifying causal relationships among the random vectors. Our numerical results show that they can outperform state-of-the-art tests in a wide variety of examples.

TAYLOR & FRANCIS LTD2021

Chargement

Modélisation et analyse numérique de problèmes de réaction-diffusion provenant de la solidification d'alliages binaires

In this work, we are interested in elaborating models and numerical methods in order to study some phenomena which arise in the solidification of binary alloys. We propose two distinct models based on the mass and energy conservation laws as well as on classical thermodynamics. The first model is based on the irreversible process theory and therefore requires the computation of the entropy of the system to complete the description. To obtain this quantity, we develop a formalism and a method which yields numerical results. This construction is made so that the entropy function inherits some interesting mathematical properties from physical requirements. These properties allow us to elaborate and analyze mathematically an original scheme using a time discretization depending on a real parameter to solve the solidification problem. In particular, we are able to prove that the scheme is stable for all values of the time step if the parameter is chosen correctly. Furthermore, we give some numerical results to support the theory. The second model, called phase-field model, is used to describe dendrites' formation during the solidification of binary alloys. The nature of the problem constrains us to use very fine meshes in some physical regions. To reduce the number of discrete unknowns, we develop an adaptive mesh strategy based on an ad-hoc error estimator. We make numerical tests showing that the method converges on regular meshes and that the estimator is in good agreement with the true error. We also show that the mesh refinement strategy gives good results in academic and physical cases.

EPFL1999

Chargement