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. Problems. Four problems need to be overcome for clustering in high-dimensional data: 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. Approaches. Approaches towards clustering in axis-parallel or arbitrarily oriented affine subspaces differ in how they interpret the overall goal, which is finding clusters in data with high dimensionality. An overall different approach is to find clusters based on pattern in the data matrix, often referred to as biclustering, which is a technique frequently utilized in bioinformatics. Subspace clustering. The adjacent image shows a mere two-dimensional space where a number of clusters can be identified. In the one-dimensional subspaces, the clusters formula_2 (in subspace formula_3 ) and formula_4, formula_5, formula_6 (in subspace formula_7) can be found. formula_5 cannot be considered a cluster in a two-dimensional (sub-)space, since it is too sparsely distributed in the formula_9 axis. In two dimensions, the two clusters formula_10 and formula_11 can be identified. The problem of subspace clustering is given by the fact that there are formula_12 different subspaces of a space with formula_13 dimensions. If the subspaces are not axis-parallel, an infinite number of subspaces is possible. Hence, subspace clustering algorithms utilize some kind of heuristic to remain computationally feasible, at the risk of producing inferior results . For example, the "downward-closure property" (cf. association rules) can be used to build higher-dimensional subspaces only by combining lower-dimensional ones, as any subspace T containing a cluster, will result in a full space S also to contain that cluster (i.e. S ⊆ T), an approach taken by most of the traditional algorithms such as CLIQUE, SUBCLU. It is also possible to define a subspace using different degrees of relevance for each dimension, an approach taken by iMWK-Means, EBK-Modes and CBK-Modes. Projected clustering. Projected clustering seeks to assign each point to a unique cluster, but  clusters may exist in different subspaces. The general approach is to use a special distance function together with a regular clustering algorithm. For example, the PreDeCon algorithm checks which attributes seem to support a clustering for each point, and adjusts the distance function such that dimensions with low variance are amplified in the distance function. In the figure above, the cluster formula_5 might be found using DBSCAN with a distance function that places less emphasis on the formula_9-axis and thus exaggerates the low difference in the formula_16-axis sufficiently enough to group the points into a cluster. PROCLUS uses  a similar approach with a k-medoid clustering. Initial medoids are guessed, and for each medoid the subspace spanned by attributes with low variance is determined. Points are assigned to the medoid closest, considering only the subspace of that medoid in determining the distance. The algorithm then proceeds as the regular PAM algorithm. If the distance function weights attributes differently, but never with 0 (and hence never drops irrelevant attributes), the algorithm is called a ""soft"-projected clustering algorithm". Projection-based clustering. Projection-based clustering is based on a nonlinear projection of high-dimensional data into a two-dimensional space. Typical  projection-methods like t-distributed stochastic neighbor embedding (t-SNE), or neighbor retrieval visualizer (NerV) are used to project data explicitly into two dimensions disregarding the subspaces of higher dimension than two and preserving only relevant neighborhoods in high-dimensional data. In the next step, the Delaunay graph between the projected points is calculated, and each vertex between two projected points is weighted with the high-dimensional distance between the corresponding high-dimensional data points. Thereafter the shortest path between every pair of points is computed using the Dijkstra algorithm. The shortest paths are then used in the clustering process , which involves two choices depending on the structure type in the high-dimensional data. This Boolean choice can be decided by looking at the topographic map of high-dimensional structures. In a benchmarking of 34 comparable clustering methods, projection-based clustering was the only algorithm that always was able to find the high-dimensional distance or density-based structure of the dataset. Projection-based clustering is accessible in the open-source R package "ProjectionBasedClustering" on CRAN. Hybrid approaches. Not all algorithms try to either find a unique cluster assignment for each point or all clusters in all subspaces; many settle  for a result in between, where a number of possibly overlapping, but not necessarily exhaustive set of clusters are found. An example is FIRES, which is from its basic approach a subspace clustering algorithm, but uses a heuristic too aggressive to credibly produce all subspace clusters. Another hybrid approach is to include a human-into-the-algorithmic-loop: Human domain expertise can help to reduce an exponential search space through heuristic selection of samples. This can be beneficial in the health domain where, e.g., medical doctors are confronted with high-dimensional descriptions of patient conditions and measurements on the success  of certain therapies. An important question in such data is to compare and correlate patient conditions and therapy results along with combinations of dimensions. The number of dimensions is often very large, consequently one needs to map them to a smaller number of relevant dimensions to be more amenable for expert analysis. This is because irrelevant, redundant, and conflicting dimensions can negatively affect effectiveness and efficiency of the whole analytic process. Correlation clustering. Another type of subspaces is considered in Correlation clustering (Data Mining).