Intelligent Systems Lecture Notes

16 November 2011 • Clustering

---

Outline

• Unsupervised learning.
  • Expectation maximization.
  • Hard clustering.
  • Soft clustering.

In The Doctor’s Office

• You’re a doctor in an unfamiliar place.
• Your patients are showing unusual symptom combinations.
  • But there appears to be some regularity between patient symptoms.
• How do you figure out
  • The illnesses afflicting your patients?
  • The illness afflicting each patient?

WWJSD?

A Symptom Map

Unsupervised Learning

• Unsupervised learning (or clustering) involves training sets without target features.
• Find a natural categorization to predict feature values.
• Partition the training set into clusters or classes.
• Partition the training set to minimize the prediction error.
• Hard vs soft clustering: a distinct result vs. a probability distribution.

General Approach

• Clustering uses the Expectation-Maximization (EM) algorithm.
  • The E step: Determine the expected feature values for a given clustering.
  • The M step: reconfigure the clustering to minimize the estimation error.

  

EM Inputs

• The inputs to the EM algorithm are
  • The example set E = { (\(I\)₁, …, \(I\)_n), \(\ldots\) }.
    • val(e, \(I\)_j) is \(I\)_j’s value in example e.
  • k, the number of clusters.
    • Alternatively, the algorithm could iterate over k to find the best value.

k-Means Clustering

• k-means clustering provides hard clustering.
• The outputs are
  • A example-set partitioning into clusters.
    • cluster: E \(\rightarrow\) { 1, …, k }.
  • Feature-value predictions for each cluster.
    • pval(c, \(I\)_j) is feature \(I\)_j’s predicted value in cluster c.

Error Minimization

• The sum-of-squares error minimized is

  \(\sum\)_{e \(\in\) E} \(\sum\)_j (pval(cluster(e), \(I\)_j) - val(e, \(I\)_j))²

• Finding a true, global minimum requires exponential work.
• Settle for a search into a local minimum.
  • Repeated runs with random initialization produce different results.

General k-mean Algorithm

• Assign examples randomly to clusters.
• E step: Given cluster(), the pval() minimizing the sum-of-squares error is the mean value for the cluster.
• M step: Given pval(), assign each example e to a cluster minimizing the error for e.
• Repeat the E and M steps until nothing changes.

k-Means E Step

• E: For each cluster i and feature \(I\)_j,

  

  

k-Means M Step

• M: assign examples to clusters to minimize

  \(\sum\)_j (pval(i, \(I\)_j) - val(e, \(I\)_j))²

  

Example Set

Random Cluster Assignment

• k = 2.

Closest Mean Assignment

Re-assign to Means

Using k-Means Results

• k = 3

k-Means Properties

• When the iterations stop changing, the assignment is stable.
• The algorithm converges to a stable local minimum.
• Stability is permutation invariant.
• The algorithm finds a local minimum, but not necessarily a global one.
• It is sensitive to the relative dimensions scale.
• Larger k values decrease errors.

Soft Clustering

• Hard clustering assigns specific values to categories or features.
  • This illusion of certainty may be inappropriate in some circumstances.
• Soft clustering assigns probability distributions to category and feature values.
  • Soft clustering provides grist for further deliberation.

Soft Clustering Model

• Soft clustering models a naive Bayesian classifier over discrete features.
• Category is a k-valued random variable C.

  Model		Data		Probabilities
  	+	\(I\)1 \(I\)2 \(I\)3 \(I\)4 t f t t f t t f f f t t \(\vdots\)	=	Pr(C) Pr(\(I\)1 | C) Pr(\(I\)2 | C) Pr(\(I\)3 | C) Pr(\(I\)4 | C)

Augmented Input

• Input features are augmented with two new features:
  • The category C indicating membership and
  • The count indicating probability.
• Each original example is replicated k times, one for each category value.
• The sum of the counts for the replicas is 1.0.

Example

Original		Augmented
\(I\)1 \(I\)2 \(I\)3 \(I\)4 \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) t f t t \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)	\(\rightarrow\)	\(I\)1 \(I\)2 \(I\)3 \(I\)4 C count \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) t f t t 1 0.4 t f t t 2 0.1 t f t t 3 0.5 \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)

• Assuming three category values.

Soft-Clustering Algorithm

• Using the EM algorithm again.
  • Sometimes called the c-means algorithm.

  \(I\)1 \(I\)2 \(I\)3 \(I\)4 C count \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) t f t t 1 0.4 t f t t 2 0.1 t f t t 3 0.5 \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)

  Pr(C) Pr(\(I\)1 | C) Pr(\(I\)2 | C) Pr(\(I\)3 | C) Pr(\(I\)4 | C)

Soft-Clustering EM

• Initialize Pr(C) and Pr(\(I\)_j | C) randomly.
• E-step: give the expected number of data points for the unobserved variables based on the discovered probabilities.
• M-step: infer the maximum-likelihood probabilities from the data.
• Repeat the E- and M-steps until nothing changes.

The EM Steps

• The E step.

  

• The M step.

  

Summary

• Unsupervised learning works without target values.
  • One task is to discover the target as a latent variable.
• Hard clustering returns deterministic answers.
• Soft clustering returns probability distributions.
• The EM algorithm discovers both hard and soft clusters.

References

• Neural Networks (Part 3): Self-Organizing Systems (Chapter 15) in Intelligent Systems by Robert Schalkoff, Jones and Bartlett, 2011.
• Learning Probabilistic Models (Chapter 20) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.

Credits

• John Snow’s picture from Wikipedia, in the public domain.
• John Snow’s cholera map from Wikipedia, in the public domain.

---

This page last modified on 2011 November 16.