SUBCLU

Template:One source 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 criteria: if a cluster is found in a subspace $S$, then each subspace $T\subseteq S$ also contains a cluster. However, a cluster $C\subseteq DB$ in subspace $S$ is not necessarily a cluster in $T\subseteq S$, since clusters are required to be maximal, and more objects might be contained in the cluster in $T$ that contains $C$. However, a density-connected set in a subspace $S$ is also a density-connected set in $T\subseteq S$.

This downward-closure property is utilized by SUBCLU in a way similar to the Apriori algorithm: first, all 1-dimensional subspaces are clustered. All clusters in a higher-dimensional subspace will be subsets of the clusters detected in this first clustering. SUBCLU hence recursively produces $k+1$-dimensional candidate subspaces by combining $k$-dimensional subspaces with clusters sharing $k-1$ 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, only the points known to belong to clusters in one $k$-dimensional subspace (which is chosen to contain as little clusters as possible) are considered. Due to the downward-closure property, other point cannot be part of a $k+1$-dimensional cluster anyway.

Pseudocode

SUBCLU takes two parameters, $ϵ$ and $MinPts$, 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:

$𝚂𝚄𝙱𝙲𝙻𝚄(DB,eps,MinPts)$

$S_1:=\mathrm{\varnothing }$

$C_1:=\mathrm{\varnothing }$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑a\in Attributes$

$C^{\{a\}}=𝙳𝙱𝚂𝙲𝙰𝙽(DB,\{a\},eps,MinPts)$

$𝚒𝚏(C^{\{a\}}\ne \mathrm{\varnothing })$

$S_1:=S_1\cup \{a\}$

$C_1:=C_1\cup C^{\{a\}}$

$𝚎𝚗𝚍𝚒𝚏$

$𝚎𝚗𝚍𝚏𝚘𝚛$

// In a second step, $k+1$-dimensional clusters are built from $k$-dimensional ones:

$k:=1$

$𝚠𝚑𝚒𝚕𝚎(C_k\ne \mathrm{\varnothing })$

${𝙲𝚊𝚗𝚍𝚂}_{k+1}:=𝙶𝚎𝚗𝚎𝚛𝚊𝚝𝚎𝙲𝚊𝚗𝚍𝚒𝚍𝚊𝚝𝚎𝚂𝚞𝚋𝚜𝚙𝚊𝚌𝚎𝚜(S_k)$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑cand\in {𝙲𝚊𝚗𝚍𝚂}_{k+1}$

$𝚋𝚎𝚜𝚝𝚂𝚞𝚋𝚜𝚙𝚊𝚌𝚎\mathtt{:=}\underset{s\in S_k\wedge s\subset cand}{\min }\sum _{C_i\in C^s}|C_i|$

$C^{cand}:=\mathrm{\varnothing }$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑𝚌𝚕𝚞𝚜𝚝𝚎𝚛cl\in C^{𝚋𝚎𝚜𝚝𝚂𝚞𝚋𝚜𝚙𝚊𝚌𝚎}$

$C^{cand}:=C^{cand}\cup 𝙳𝙱𝚂𝙲𝙰𝙽(cl,cand,eps,MinPts)$

$𝚒𝚏(C^{cand}\ne \mathrm{\varnothing })$

$S_{k+1}:=S_{k+1}\cup cand$

$C_{k+1}:=C_{k+1}\cup C^{cand}$

$𝚎𝚗𝚍𝚒𝚏$

$𝚎𝚗𝚍𝚏𝚘𝚛$

$𝚎𝚗𝚍𝚏𝚘𝚛$

$k:=k+1$

$𝚎𝚗𝚍𝚠𝚑𝚒𝚕𝚎$

$𝚎𝚗𝚍$

The set $S_k$ contains all the $k$-dimensional subspaces that are known to contain clusters. The set $C_k$ contains the sets of clusters found in the subspaces. The $bestSubspace$ 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 generates the frequent itemset candidates: Pairs of the $k$-dimensional subspaces are compared, and if they differ in one attribute only, they form a $k+1$-dimensional candidate. However, a number of irrelevant candidates are found as well; they contain a $k$-dimensional subspace that does not contain a cluster. Hence, these candidates are removed in a second step:

$𝙶𝚎𝚗𝚎𝚛𝚊𝚝𝚎𝙲𝚊𝚗𝚍𝚒𝚍𝚊𝚝𝚎𝚂𝚞𝚋𝚜𝚙𝚊𝚌𝚎𝚜(S_k)$

${𝙲𝚊𝚗𝚍𝚂}_{k+1}:=\mathrm{\varnothing }$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑s_1\in S_k$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑s_2\in S_k$

$𝚒𝚏(s_1𝚊𝚗𝚍s_2𝚍𝚒𝚏𝚏𝚎𝚛𝚒𝚗𝚎𝚡𝚊𝚌𝚝𝚕𝚢𝚘𝚗𝚎𝚊𝚝𝚝𝚛𝚒𝚋𝚞𝚝𝚎)$

${𝙲𝚊𝚗𝚍𝚂}_{k+1}:={𝙲𝚊𝚗𝚍𝚂}_{k+1}\cup \{s_1\cup s_2\}$

$𝚎𝚗𝚍𝚒𝚏$

$𝚎𝚗𝚍𝚏𝚘𝚛$

$𝚎𝚗𝚍𝚏𝚘𝚛$

// Pruning of irrelevant candidate subspaces

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑cand\in {𝙲𝚊𝚗𝚍𝚂}_{k+1}$

$𝚏𝚘𝚛𝚎𝚊𝚌𝚑k\mathtt{\text{-𝚎𝚕𝚎𝚖𝚎𝚗𝚝}}s\subset cand$

$𝚒𝚏(s\in ̸S_k)$

${𝙲𝚊𝚗𝚍𝚂}_{k+1}={𝙲𝚊𝚗𝚍𝚂}_{k+1}\setminus \{cand\}$

$𝚎𝚗𝚍𝚒𝚏$

$𝚎𝚗𝚍𝚏𝚘𝚛$

$𝚎𝚗𝚍𝚏𝚘𝚛$

$𝚎𝚗𝚍$

Availability

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