Everything begins to look like an outlier as the dimensionality grows.
There are many options to solve your problem, but given that you didn't discuss your particular application, I will recommend a pipeline I have used before. It's a two-stage process: 1) project the data into a lower space with random projections, and 2) apply your favourite low-dimensional clustering algorithm in this space (e.g. k-means).
Random projections are an algorithm for projecting datasets into lower-dimensional spaces. In the projected space, the distance between instances is preserved (with high probability), so clustering in the lower-dimensional space then has a clear link to clustering in the higher dimensional space, Random projections can sometimes be unstable' depending on the datasets (especially when sparse), so researchers often use ensembles of random projections when performing this kind of technique.
The two links expand on these points. The second discusses a cluster ensemble technique. The third link points to a python library that implements random projections.
http://papers.nips.cc/paper/3901-random-projections-for-k-means-clustering.pdf
http://www.aaai.org/Papers/ICML/2003/ICML03-027.pdf
http://scikit-learn.org/stable/modules/random_projection.html
For high-dimensional data, one of the most common ways to cluster is to first project it onto a lower dimension space using a technique like Principle Components Analysis (PCA), Non-negative Matrix Factorization (NMF), or something nonlinear like Diffusion Maps. You then take the axes which capture a large proportion of the variation in your data (for PCA, these are the axes with the largest eigenvalues and you truncate after some chosen threshold) and use this as your lower dimensional dataset. On this transformed version of the data you then apply standard clustering techniques.
Depending on application we have seen successes in hierarchical clustering as well as density based clustering (DBSCAN) among other methods.
We have recently devised a method that generalizes k-means. Instead of points, in our formulation the central objects can be higher dimensional possibly nonconvex polytopes. Central polytopes are still lower dimensional from the dataset itself, to prevent overfitting. Thus, it can deal with curse of dimensionality. It effectively performs dimensionality reduction on its own, and no preprocessing is needed as some others suggested.
There is an attached demo of using 1-dimensional polytopes (a connected union of line-segments) on a 2d dataset.
Here is a link to the article: Article K-polytopes: A superproblem of k-means
The well known "curse of dimensionality" can be faced by using either a feature selection or feature extraction approaches.
The choice of using one method instead of another depends whether or not you want to preserve the information on the feature space.
Indeed, the former tends to preserve these information and I would recommend the following reading: https://www.cse.msu.edu/~tangjili/publication/feature_selection_for_classification.pdf
Differently, the second methodology (PCA, LDA, CCA, etc) tends to loose such information due to particular transformations/projections of the current feature space to a new sub-space.
First try feature selection with e.g. the Pearson Correlation Coefficient. If that does not work as your features are not correlated and therefore none can be neglected, try dimensionality reduction with e.g. PCA or UMAP or t-SNE. However, look if your data is suitable for dimensionality reduction by e.g. for PCA looking at the Kaiser-Meyer-Olkin criterium and the bartlett test for sphericity. After feature selection and / or dimensionality reduction you can use a normal clustering algorithm like k-means, mean-shift or DBSCAN.
If your data is not suitable for dimensionality reduction you can try specific clustering algorithms for high dimensional data. These algorithms are summarized as Subspace Clustering, Pattern-Based Clustering and Correlation Clustering (see Kriegel et al. "Clustering High-Dimensional Data: A Survey on Subspace Clustering, Pattern-Based Clustering, and Correlation Clustering"). An example would be the CLIQUE algorithm.
- Badges
- Science topic