Skip to main content

Overview

Clustering

Until now every data point came with a label. From this week on it does not.

In unsupervised learning we only have inputs. We look for structure in them.

Pages

k-means The algorithm, its failure modes, choosing k
Hierarchical clustering Dendrograms and linkage
Mixtures and density Gaussian mixture models and DBSCAN
Exercises

Goals

The goal of this week is to

  1. understand and learn how to use k-means clustering,
  2. understand and learn how to use hierarchical clustering, and
  3. see a comparison of k-means clustering, hierarchical clustering and DBSCAN.

Data generating processes again

In supervised learning we thought of the data as coming from \(P(X, Y) = P(Y|X)P(X)\), and we learned about the conditional part.

Now there is no \(Y\). We only have samples from \(P(X)\), and we try to say something about \(P(X)\) itself.

Clustering proposes that \(P(X)\) is a mixture. The data comes from a few groups, and each point belongs to one of them. Which group is not observed.

A warning

There is no test set here, and no label to be right or wrong about. Almost any method will return clusters, whether or not the data has any.

So the question is never only which clustering is best. It is also whether there is cluster structure at all. If two methods disagree strongly, that is information.

Notation

We write \(k\) for the number of clusters and \(C_1, \dots, C_k\) for the sets of indices in each cluster. The centroid of cluster \(j\) is \(\mu_j\).