Density-Connected Subspace Clustering for High-Dimensional Data

By K. Murthy, Hans-Peter Kriegel, Peer Kröger. SDM, 2004

458 citations recorded by the source corpus.

Several application domains such as molecular biology and geography produce a tremendous amount of data which can no longer be managed without the help of efficient and effective data mining methods. One of the primary data mining tasks is clustering. However, traditional clustering algorithms often fail to detect meaningful clusters because most real-world data sets are characterized by a high dimensional, inherently sparse data space. Nevertheless, the data sets often contain interesting clusters which are hidden in various subspaces of the original feature space. Therefore, the concept of subspace clustering has recently been addressed, which aims at automatically identifying subspaces of the feature space in which clusters exist. In this paper, we introduce SUBCLU (density-connected Subspace Clustering), an effective and efficient approach to the subspace clustering problem. Using the concept of density-connectivity underlying the algorithm DBSCAN [EKSX96], SUBCLU is based on a formal clustering notion. In contrast to existing grid-based approaches, SUBCLU is able to detect arbitrarily shaped and positioned clusters in subspaces. The monotonicity of density-connectivity is used to efficiently prune subspaces in the process of generating all clusters in a bottom up way. While not examining any unnecessary subspaces, SUBCLU delivers for each subspace the same clusters DBSCAN would have found, when applied to this subspace separately.

Subfields: Artificial Intelligence, Molecular Biology, Signal Processing

View Paper: https://www.semanticscholar.org/paper/4779073eac80c3d4d0c13f5c1910402faa92c5a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Signal Processing

Citations in the corpus

Density-based Projected Clustering over High Dimensional Data Streams (2012, methodology): “Although there exist methods for density-based clustering over full dimensional data streams, e.g., [7, 8], and density-based clustering over high dimensional static data, e.g., [6,18], there is no algorithm that simultaneously tackles both the high dimensionality and the stream aspects of the data.”
Swarm (2010, unknown): “Works on subspace clustering [15, 3] can be also applied to find sub-trajectory clusters.”
Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization (2017, background): “There is a large number of clustering algorithms in literature, which can be grouped into different perspectives, such as hierarchical [9, 51], centroid-based [20, 3, 27], graphbased [38, 28, 48, 25], sequential (temporal) [11, 37, 66], regression model based [7, 47], and subspace clustering models ”
Density‐based clustering (2019, methodology): “The density-based approach has been applied to search for clusters in axis-parallel subspaces, for example, by Kailing, Kriegel, and Kröger (2004), Böhm, Kailing, Kriegel, and Kröger (2004), and Assent, Krieger, Müller, and Seidl (2007, 2008) and in arbitrarily oriented subspaces, for example, by Bö”
Subspace clustering (2012, methodology): “Further examples for subspace clustering in this narrower sense include Refs 44–47 as variants of CLIQUE and Ref 48 as a density-based approach also implementing the downward-closure property and an APRIORI-style search of subspaces.”
Density‐based clustering (2011, methodology): “The density-based approach has been applied successfully to search for clusters in axis-parallel subspaces (e.g. Refs 33–35) and arbitrarily oriented subspaces (e.g. Refs 36–38).”
Evaluating Clustering in Subspace Projections of High Dimensional Data (2009, methodology): “cell-based CLIQUE [3] fixed threshold, fixed grid, pruning by monotonicity property cell-based DOC [29] fixed result size, fixed threshold, variable hypercubes, randomized, partitioning cell-based MINECLUS [32] enhances DOC by FP-tree structure [15] resulting in more efficient mining cell-based SCHI”
dbscan: Fast Density-Based Clustering with R (2019, background): “While certainly useful in many applications, parametric approaches naturally assume clusters will exhibit some type convex (generally hyper-spherical or hyper-elliptical) shape.”
Density-Based Projected Clustering of Data Streams (2012, methodology): “The subspace clusters are generated in a bottom-up way and for the sake of efficiency, a monotonicity criteria [14] is used.”