Clustering - k-means & SOM

Chapters

• General Terms and tools
• PCA
  • PCA
  • Hebbian Learning
  • Kernel-PCA
• Source Separation
  • ICA
  • Infomax ICA
  • Second Order Source Separation
  • FastICA
• Stochastic Optimization
• Clustering
  • k-means Clustering
  • Pairwise Clustering
  • Self-Organising Maps
  • Locally Linear Embedding
• Estimation Theory
  • Density Estimation
    • Kernel Density Estimation
    • Parametric Density Estimation
  • Mixture Models - Estimation Models

K-means Clustering

K-means Clustering is good at finding equally sized clusters of data points.

Parameters

• Distance Function (Usually Euclidean)
• Number of clusters

Drawbacks

• ???Cannot cope with clusters of different sizes???
• Cannot automatically select the number of clusters (resolution)

Two algorithms

• Batch K-Means
• Online K-Means

Online K-Means is superior because it is less likely to converge to local minima and can be used for streaming data (that’s why it’s ‘online’)

Batch K-Means

$q$ is the index of the prototype

$\underset{―}{w}$ is the vector containing the assignments. Every datapoint can only be assigned to one prototype.

$m_q^{(\alpha )}$ is our assignment vector of the datapoints.

• initialize prototypes randomly around center of mass
• loop arbitrarily
  • Assign all data points to their closest prototype $m_q$

  • choose a ${\underset{―}{w}}_q$ that minimizes the error function. –> In case of Euclidian Distance this means the center of mass

    $${\underset{―}{w}}_q=\frac{\sum _{\alpha }^p{m}_q^{(\alpha )}{\underset{―}{x}}^{(\alpha )}}{\sum _{\alpha }^p{m}_q^{(\alpha )}}$$

    The sum of all datapoints in the cluster divided by the number of datapoints in the cluster.

  • Set new ${\underset{―}{w}}_q$
• end loop

Problem

Batch K-Means is not a Convex optimization problem. A convex optimization problem would guarantee that a local minimum is a global minimum. This means that we are note certain to converge to the optimum.

Online K-Means

• Initialize all $w_q$ randomly around first data point
• Select learning rate $\epsilon$
• for ${\underset{―}{x}}^{(\alpha )}$ in $\underset{―}{x}$
  • find closest prototype ${\underset{―}{w}}_q$

  • nudge prototype a bit in the direction of the data point

    $$\mathrm{\Delta }{\underset{―}{w}}_q=\epsilon (x^{(\alpha )}-{\underset{―}{w}}_q)$$

Online K-Means is less likely to be stuck in a local minimum.

Robustness

Labels are not ordered

A good choice of number of clusters $M$ should be stable/repeatable. Therefore K-Means can be tried with a different number of clusters each to see which number $M$ of clusters is stable (with different initializations of course).

Validation

TODO: page 19

The following is likely wrong, better read it up in the original paper¹:

Algorithm:

for m in range(m_min,m_max):
  for i, x_split in enumerate(split_in_pieces(x,r)):
    Y[split] = find_clusters(x_split, m)
    # TODO Compute dissimilarities
    dissimilarity(Y2, Y1)

Pairwise Clustering

Pairwise Clustering is the clustering we are used to (e.g. $m$ partitions), but instead of the original data points, only the distances are available to us. The distances are collected in a matrix $p\times p$. This could happen e.g. when a kernel trick was used or the measurements taken were already dissimilarity measurements.

Mean-Field Approximation(not very relevant)

• simulated annealing(slow)
• mean-field approximation(good and fast, robust against locoal optima)

Soft-K-means clustering (Euclidean distances) (Very Relevant)

Algorithm

• choose number of partitions $M$
• Choose parameters:
  • initial noise (${\beta }_0$)
  • final noise (${\beta }_f$)
  • annealing factor $\eta$
  • convergence criterion $\theta$
• initialize prototypes

• while $\beta <{\beta }_f$
  • repeat EM until
  $$|{\underset{―}{w}}_q^{new}-{\underset{―}{w}}_q^{old}|<\theta \mathrm{\forall }q$$
  • compute assignment probabilities (look up formular)
  • Compute new prototypes ${\underset{―}{w}}_q^{new}=\frac{\sum _{\alpha }^p(m_q^{(\alpha )}{)}_Q{\underset{―}{x}}^{(\alpha )}}{\sum _{\alpha }^p(m_q^{(\alpha )}{)}_Q}\mathrm{\forall }q$
  • $$\beta \stackrel{+}{=}\eta \beta$$

Self-Organising Maps (SOM)

Self-Organizing Maps are useful in dimensionality reduction while preserving neighborhood. At the same time it is a clustering method as opposed to LLE, which projects all data points into the lower dimensional space(see below).

Parameters

• $M$ partitions/neurons
• annealing schedule learning rate $\epsilon$ and annealing factor $\sigma$
• prototypes ${\underset{―}{w}}_{\underset{―}{q}}$ center of mass $\pm$ random noise

Algorithm

• for x_a in random(x)
  • get closest prototype
  $$\underset{―}{p}=\underset{\underset{―}{r}}{\text{argmin}}|{\underset{―}{x}}^{(\alpha )}-{\underset{―}{w}}_{\underset{―}{r}}|$$

  Note: $p$ is in the map space while ${\underset{―}{x}}^{(\alpha )}$ is in data space

  • Change all prototypes using:
  $$\mathrm{\Delta }{\underset{―}{w}}_{\underset{―}{q}}=\epsilon h(\underset{―}{q},\underset{―}{p})({\underset{―}{x}}^{(\alpha )}-{\underset{―}{w}}_{\underset{―}{q}})\text{ for all q}$$

Example choice of $h(\underset{―}{q},\underset{―}{p})$

Annealing $\sigma$

• Decrease $\sigma$ slowly over time

This algorithm would be similar to k-means if one were to update only $\underset{―}{q}\text{ given that }\underset{―}{q}=\underset{―}{p}$ with $\sigma =0$. It would mean that only the closest prototype would be updated by the squared error. Also the exponential is not contained in k-Means.

Locally Linear Embedding

“locally linear embedding (LLE), an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data.”² In Locally Linear Embedding the idea is to split up the data into small patches and then for each patch and data point there are the weights $\underset{―}{W}$that allow an optimal reconstruction of the data points as well as a embedding coordinates $\underset{―}{U}$

Algorithm

Parameters $K,M$

1. find K nearest neighbours of $KNN({\underset{―}{x}}^{(\alpha )})=\{{\beta }_1^{(\alpha )},...,{\beta }_K^{(\alpha )}\mathrm{\forall }\alpha =1,...,p\}$
2. calculate reconstruction weights $\underset{―}{W}$
3. calculate embedding coordinates $\underset{―}{U}$

2. Cost function

$E$ is our error function. $p$ is the number of data points. $W_{\alpha \beta }$ are the weights

LLE is very good at preserving neighboorhoods in high dimensional data. Is Convex

Footnotes