Toggle navigation

.rst .pdf

Contents

Clustering

KMeans([n_clusters, init, ...])	Scalable KMeans for clustering
SpectralClustering([n_clusters, ...])	Apply parallel Spectral Clustering

The dask_ml.cluster module implements several algorithms for clustering unlabeled data.

Spectral Clustering

Spectral Clustering finds a low-dimensional embedding on the affinity matrix between samples. The embedded dataset is then clustered, typically with KMeans.

Typically, spectral clustering algorithms do not scale well. Computing the $n\mathrm{\_}samples\times n\mathrm{\_}samples$ affinity matrix becomes prohibitively expensive when the number of samples is large. Several algorithms have been proposed to work around this limitation.

In dask-ml, we use the Nyström method to approximate the large affinity matrix. This involves sampling n_components rows from the entire training set. The exact affinity is computed for this subset ( $n\mathrm{\_}components\times n\mathrm{\_}components$ ), and between this small subset and the rest of the data ( $n\mathrm{\_}components\times (n\mathrm{\_}samples-n\mathrm{\_}components)$ ). We avoid the direct computation of the rest of the affinity matrix.

Let $S$ be our $n\times n$ affinity matrix. We can rewrite that as

$$\begin{array}{r}{S}_d=\left[\begin{array}{}A& B\\ B^T& C\end{array}\right]\end{array}$$

Where $A$ is the $n\times n$ affinity matrix of the $n\mathrm{\_}components$ that we sampled, and $B$ is the $n\times (n-n\mathrm{\_}components)$ affinity matrix between the sample and the rest of the dataset. Instead of computing $C$ directly, we approximate it with $B^T{A}^{-1}B$.

See the spectral clustering benchmark for an example showing how dask_ml.cluster.SpectralClustering scales in the number of samples.

previous

Incremental Learning

next

API Reference