SUBCLU is an algorithm for clustering high-dimensional data by Karin Kailing, Hans-Peter Kriegel and Peer Kröger. It is a subspace clustering algorithm that builds on the density-based clustering algorithm DBSCAN. SUBCLU can find clusters in axis-parallel subspaces, and uses a bottom-up, greedy strategy to remain efficient.

Approach

SUBCLU uses a monotonicity. However, a density-connected set.

This downward-closure property is utilized by SUBCLU in a way similar to the Apriori algorithm attributes. After pruning irrelevant candidates, DBSCAN is applied to the candidate subspace to find out if it still contains clusters. If it does, the candidate subspace is used for the next combination of subspaces. In order to improve the runtime of DBSCAN-dimensional cluster anyway.

Pseudocode

, which serve the same role as in DBSCAN. In a first step, DBSCAN is used to find 1D-clusters in each subspace spanned by a single attribute:

1. -dimensional ones:

is chosen to minimize the runs of DBSCAN (and the number of points that need to be considered in each run) for finding the clusters in the candidate subspaces.

Candidate subspaces are generated much alike the Apriori algorithm-dimensional subspace that does not contain a cluster. Hence, these candidates are removed in a second step:

1. // Pruning of irrelevant candidate subspaces

Availability

An example implementation of SUBCLU is available in the ELKI framework.

References