IML : Unserpervised clustering

Why do we care

Group the input data into clusters that share some characteristics

• Find pattern in the data (data mining problem)
• Visualize the data in a simpler way
• Infer some properties of a given data point based on how it relates to other data point (satistical learning)

Why is it tricky

Belongs to unsupervised learning

• No grounds truth available to learn/evaluate quality of the algorithm

How to assess how much data points are related to each other?

• Which criteria (features) are the most relevant
• Which metrics make the most sense

How to assess the soundness of the resulting cluster? Is it relevant ?

Families of clustering approaches

• Distance-based clustering
  • centroid-based approach (k-mean)
  • connectivity-based approaches (based on distance)
• Density-based clustering
  • set of dense points
• Distribution-based clustering
  • likelihood of point to belong to the same distribution
• Fuzzy clustering
  • Relaxed clustering paradigm where a data point can be assigned to multiple clusters with a quantified degree of belongingness metric (fuzzy
    $c$-means clustering,…).

$k-$means clustering

Partition

$n$ observations

$x_1,...,x_n$ int

$k$ clusters

$C=\{C_1,...,C_k\}$ where each observations

$x_i$ belongs to the cluster

$C_{j\ast }$ whose mean

${\mu }_{j\ast }$ is the closest:

$x_i\in S_{j\ast }$ with

$j^{\ast }=argmi{n}_j\Vert x_i-{\mu }_j{\Vert }_2$

La croix represente le centre, on veut la plus petite distance depuis un centre pour ajouter un point dans un cluster:

• Minimize within-cluster sum of squares (variance)
• Overall optimization problem:

• NP-hard problem, no guarantee to find the optimal value
• Stochastic and very sensitive to initial conditions
• Sensitive to outliers (thank you
  $L_2$ norm)
• Probably the most used clustering algorithm

$k-$means and Voronoi tesselation

Voronoi tesselation
parition of the Euclidean space relatively to discrete points/seeds. Each region/Voronoi cell is composed of all the points in the space that are closer to the cell seed than any other seed

• $k$-mean provides a way to obtain a Voronoi tesselation of the input space, where seeds are the final cluster means
• Alternatively, one case use some pre-computer Voronoi tesselation seeds as initial clusters for
  $k$-means

Determining the optimal number of cluster

Combien de clusters a vue de nez pour cette image ?

2, 3, 4, 14…

Compute explained variance for an increasing number of clusters

$k$

Plot and find the bend of the elbow

Sometimes it does not work :(

Sometimes,

$k$-means works…

But most of the time not as expected.

Probably because the

$L_2$ norm that

$k$-means tries to minimize

• Sensible of curse of dimensionality
• Form "normalized Gaussian" clusters
• Does not adapt to manifold geometry
• Sensible to class imbalance
• Sensible to outliers

Simple Linear Iterative Clustering

A kick-ass image segmentation algorithm using

$k$-means

SLIC superpixels uses a modified

$k$-means clustering in the

$Labxy$ space to produce

$k$ clusters regurlaly sampled and perceptually coherent from a color point of view.

k-medoids clustering

Possible extension to

$k$-means

Cluster centroids are not initial data points

$\Rightarrow$ can be problematic

$\Rightarrow$ Replace centroids by medoid (points with the smallest distance to all other points in the cluster)

$\Rightarrow$

$k$-medoid algorithm

Overall objective: find

$k$ medoids

$m_1,...,m_k$ that minimize the partitioning cost

Fuzzy

$c$-means clustering

$k$-means is a hard clustering method: each data point 100% belongs to the cluster

Soft clustering methods allow each data points to belong to several clusters with various degrees of membership

Gaussian mixture models

$k$-means on steroids

$k$-means works for spherical clusters, but fails in any other cases

$\Rightarrow$ try harder Model probability density function

$f$ of data as a mixture of multivariate Gaussian

Cette courbe est une superposition de plusieurs Gaussiennes:

Il faut pouvoir estimer les facteurs de proportions de ces gaussiennes dans la somme

The EM algorithm

Initialization

• Select
  $k$ random points as initial means
  ${\hat{\mu }}_1,...,{\hat{\mu }}_k$
• Init all covariance matrices
  ${\hat{\sum }}_1,...,{\hat{\sum }}_k$ as whole data sample covariances matrix
  $\hat{\sum }$
• Set uniform mixture weight
  ${\hat{\varphi }}_1,...,{\hat{\varphi }}_k=\frac{1}{k}$

Alternate until convergence

Expectation step
Compute membership weight

${\hat{\gamma }}_{ij}$ of

$x_i$ with respect to

$j^{th}$ component

$\mathcal{N}(x|{\mu }_j,\sum _j)$

Maximization step
Update weights (in that ordre)

Tadaaaa

$k$-means vs GMM

Let the fight begin!

Kernel Density Estimation

Nonparametric estimation

Goal
Estimate probability density function

$f$ based on observations

$x_1,...,x_n$ only, assumed to derive from

$f$ otherwise wtf are we doing here

The kernel density estimator with bandwith

$h$ at given point

$x$ is given by

Exemples

Mean shift clustering

shift each point to the the local density maximum of its KDE, and assign to the same cluster all points that lead to the same maximum

Exemples

On peut faire la meme chose sur les images en couleurs:

DBSCAN

Density-base spatial clustering of applications with noise

• Divide points into 3 categories (core, boundary, outliers) whether there are at least
  $minPts$ in their
  $ϵ$-neighborhood or not
• Find the connected component of core points (ignore all non-core points)
• Assign non-core points to nearby clusters if it is less than
  $ϵ$ away, otherwise assign to noise

Spectral clustering

View clustering task as a min-cut operation in a graph

• Compute similarity graph (but which one?) of data
  $x_1,...,x_n$

• Compute (weighted) adjacency matrix
  $W$, degree matrix
  $D$ and Laplacian matrix
  $L=D-W$
• Perform eigendecomposition of
  $L=(E,\mathrm{△})$

Fact #1
0 is and eigenvalue of

$L$ with multiplicity

$\sim \mathrm{\#}$ connected components in graph, its eigenvectors are identity vectors of those connected components

Fact #2
Eigenvector of smallest non-zero eigenvalue (Fiedler vector) gives the normalized min-cut of graph

• Performs
  $k$-means clustering of the
  $k$ smallest eigenvectors
  $[e_1,...,e_k{]}_{n\times k}$

Hierarchical clustering

A very natural way of handling data

Goal
Generate a sequence of nested clusters and ordre them in a hierarchy, represented by a dendogram

• Leaves the dendogram = initial data
• Inner nodes of the dendogram = clusters

Exemple

Agglomerative vs Divise clustering

Agglomerative: merge clusters from fine to coarse (bottom-up approach)

Divisive clustering: split clusters (top-down approach)

• Needs some heuristics to avoid the
  $O(2^n)$ ways of spitting each cluster…
• Not so used in practice

Bestiarity

Overall comparison of all methods