Clustering high-dimensional data

Clustering high-dimensional data is the cluster analysis of data with anywhere from a few dozen to many thousands of dimensions. Such high-dimensional spaces of data are often encountered in areas such as medicine, where DNA microarray technology can produce many measurements at once, and the clustering of text documents, where, if a word-frequency vector is used, the number of dimensions equals the size of the vocabulary. Four problems need to be overcome for clustering in high-dimensional data: Multiple dimensions are hard to think in, impossible to visualize, and, due to the exponential growth of the number of possible values with each dimension, complete enumeration of all subspaces becomes intractable with increasing dimensionality. This problem is known as the curse of dimensionality. The concept of distance becomes less precise as the number of dimensions grows, since the distance between any two points in a given dataset converges. The discrimination of the nearest and farthest point in particular becomes meaningless: A cluster is intended to group objects that are related, based on observations of their attribute's values. However, given a large number of attributes some of the attributes will usually not be meaningful for a given cluster. For example, in newborn screening a cluster of samples might identify newborns that share similar blood values, which might lead to insights about the relevance of certain blood values for a disease. But for different diseases, different blood values might form a cluster, and other values might be uncorrelated. This is known as the local feature relevance problem: different clusters might be found in different subspaces, so a global filtering of attributes is not sufficient. Given a large number of attributes, it is likely that some attributes are correlated. Hence, clusters might exist in arbitrarily oriented affine subspaces. Recent research indicates that the discrimination problems only occur when there is a high number of irrelevant dimensions, and that shared-nearest-neighbor approaches can improve results.

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

On Perfect Clustering of High Dimension, Low Sample Size Data

Soham Sarkar

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.

IEEE COMPUTER SOC2020

Prediction of Survival and Risk Assessment Using Joint Analysis of Microarray Gene Expression Data

Haleh Yasrebi

Gene expression profiles have been widely used in molecular classification, diagnosis and prediction, particularly in the area of oncology where accurate and early diagnosis is needed for appropriate treatment. Avoiding under-/over-treatment when it is not necessary can extend a patient's survival and prevent disease recurrence. These high-throughput assay technologies have generated terabytes of data exploited extensively to provide insights on cancer biology and the underlying mechanism of disease progression. The ultimate goal is to identify possibly tailored treatment and therapy for personalized medicine. Analysis of microarray data is constrained by the following characteristics: (i) noisy due to missing or erroneous values; (ii) high dimensional due to a large number of genes versus a few number of samples in which their expression levels are measured; (iii) costly due to expensive microarray experiments. Abundant microarray gene expression data should be processed by appropriate computational and statistical learning methodologies such as machine learning techniques. These methods are robust to noisy data and have a great capacity to analyze high dimensional data. Their computational power is nevertheless limited to sample size based on which these methods are built. These algorithms have been widely applied to microarray gene expression data to identify a set of genes known as a gene signature whose expressions are highly correlated to a target value or outcome such as disease status, tumor subtype, a patient's survival time, risk of mortality or cancer relapse. Prediction of survival time and a patient's risk which is unknown at diagnosis presents a more challenging task for machine learning methods than tumor subtype or disease classification, which is already established by oncologists. The properties of microarray data cited above, the limitation of the number of samples in cancer patients and dependency of the machine learning methods' performance on sample size justify joint analysis of microarray data to increase the number of samples. We applied joint analysis methods to breast and lung cancer data sets to improve survival prediction and risk assessment. In overall, no significant improvement or deterioration of the performance accuracy was obtained with joint analysis. However, increasing sample size helped to identify robust or stable gene signatures predictive of survival time and risk assessment. Our achievements and learned-lessons from joint analysis of microarray gene expression data can be used as a guideline for future research studies in classification and prediction.

EPFL2010

Prediction of Survival and Risk Assessment Using Joint Analysis of Microarray Gene Expression Data

Haleh Yasrebi

EPFL2010