Pattern

Classification

All materials in these slides were taken from

Pattern Classification (2nd ed) by R. O.
Duda, P. E. Hart and D. G. Stork, John Wiley
& Sons, 2000
with the permission of the authors and the
publisher
 Chapter 10
Unsupervised Learning & Clustering
•Introduction
•Mixture Densities and Identifiability
•ML Estimates
•Application to Normal Mixtures
•K-means algorithm
•Unsupervised Bayesian Learning
•Data description and clustering
•Criterion function for clustering
•Hierarchical clustering
•The number of cluster problem and cluster validation
•On-line clustering
 2
Introduction
• Previously, all our training samples were labeled: these
samples were said “supervised”

• Why are we interested in “unsupervised” procedures

which use unlabeled samples?

1) Collecting and Labeling a large set of sample patterns can

be costly

2) We can train with large amounts of (less expensive)

unlabeled data
Then use supervision to label the groupings found, this is
appropriate for large “data mining” applications where
Pattern the contents
Classification,
of a large database are not known beforehand
 3

3) Patterns may change slowly with time

Improved performance can be achieved if classifiers
running in a unsupervised mode are used

4) We can use unsupervised methods to identify

features that will then be useful for categorization
‘smart’ feature extraction

5) We gain some insight into the nature (or

structure) of the data
which set of classification labels?
Pattern Classification,
 4
Mixture Densities & Identifiability

• Assume:
• functional forms for underlying probability densities are known
• value of an unknown parameter vector must be learned
• i.e., like chapter 3 but without class labels

• Specific assumptions:
• The samples come from a known number c of classes
• The prior probabilities P(ωj) for each class are known (j = 1, …,c)
• Forms for the P(x | ωj, θj) (j = 1, …,c) are known
Pattern Classification,
 5

• The PDF for the samples is:

• This density function is called a mixture density

• Our goal will be to use samples drawn from this
mixture density to estimate the unknown
parameter vector θ.
• Once θ is known, we can decompose the mixture
into its components and use a MAP classifier
Pattern on
Classification,
 6

• Can θ be recovered from the mixture?

• Consider the case where:
• Unlimited number of samples
• Use nonparametric technique to find p(x|θ ) for every x
• If several θ result in same p(x|θ ) can’t find unique
solution

This is the issue of solution identifiability.

• Definition: Identifiability
A density P(x | θ) is said to be identifiable if Classification,
Pattern
 7
As a simple example, consider the case where x is binary
and
P(x | θ) is the mixture:

Assume that:
P(x = 1 | θ) = 0.6 ⇒ P(x = 0 | θ) = 0.4
We know P(x | θ) but not θ
We can say: θ1 + θ2 = 1.2 but not what θ1 and θ2 are.

Thus, we have a case in which the mixture distribution is

completely unidentifiable, and therefore unsupervised
learning is impossible.
Pattern Classification,
 8

• In the discrete distributions too many components can

be problematic
• Too many unknowns
• Perhaps more unknowns than independent equations
identifiability can become a serious problem!

Pattern Classification,
 9
• While it can be shown that mixtures of normal densities are
usually identifiable, the parameters in the simple mixture density

cannot be uniquely identified if P(ω1) = P(ω2)

(we cannot recover a unique θ even from an infinite amount of
data!)
• θ = (θ1, θ2) and θ = (θ2, θ1) are two possible vectors that can be
interchanged without affecting P(x | θ).
• Identifiability can be a problem, we always assume that the
densities we are dealing with are identifiable!

Pattern Classification,
 1
0
ML Estimates
Suppose that we have a set D = {x1, …, xn} of n
unlabeled samples drawn independently from
the mixture density:

(θ is fixed but unknown!)

The MLE is:

Pattern Classification,
 1
1
ML Estimates

Then the log-likelihood is:

And the gradient of the log-likelihood is:

Pattern Classification,
 1
2
Since the gradient must vanish at the value of θi

that maximizes l ,

the ML estimate must satisfy the conditions

Pattern Classification,
 1
3

The MLE for P(ωi) and must satisfy:

Pattern Classification,
 1
4
Applications to Normal Mixtures
p(x | ωi, θi) ~ N(μi, Σi)

Case μi Σi P(ωi) c
1 ? x x x
2 ? ? ? x
3 ? ? ? ?

Case 1 = Simplest case

Case 2 = more realistic case
Pattern Classification,
 1
5
Case 1: Multivariate Normal, Unknown mean vectors
μi = θi ∀ i = 1, …, c, The likelihood is for the ith mean is:

ML estimate of μ = (μi) is:

Where is the fraction of those samples

having value xk that come from the ith class, and is the average
of the samples coming from the i-th class.

Pattern Classification,
 1
6

•Unfortunately, equation (1) does not give

explicitly

•However, if we have some way of obtaining good

initial estimates for the unknown means,
equation (1) can be seen as an iterative process
for improving the estimates

Pattern Classification,
 1
7
• This is a gradient ascent for maximizing the
log-likelihood function

• Example:
Consider the simple two-component one-dimensional
normal mixture

ω1 ω2
(2 clusters!)
Let’s set μ1 = -2, μ2 = 2 and draw 25 samples
sequentially from this mixture. The log-likelihood
function is:

Pattern Classification,
 1
8

The maximum value of l occurs at:

(which are not far from the true values: μ1 = -2 and μ2

= +2)

There is another peak at

which has almost the same height as can be seen
from the following figure.
This mixture of normal densities is identifiable
When the mixture density is not identifiable, the ML
solution is not unique
Pattern Classification,
 1
9

Pattern Classification,
 2
0
Case 2: All parameters unknown

• No constraints are placed on the covariance

matrix

• Let p(x | μ, σ2) be the two-component normal

mixture:

Pattern Classification,
 2
Suppose μ = x1, therefore: 1

For the rest of the samples:

Finally,

The likelihood is therefore large and the

maximum-likelihood solution becomes singular.
Pattern Classification,
 2
2
• Assumption: MLE is well-behaved at local maxima.
• Consider the largest of the finite local maxima of
the likelihood function and use the ML estimation.
• We obtain the following local-maximum-likelihood
estimates:

Iterative
scheme

Pattern Classification,
 2
3

Where:

Pattern Classification,
 2
4
K-Means Clustering

• Goal: find the c mean vectors μ1, μ2, …, μc

• Replace the squared Mahalanobis distance

• Find the mean nearest to xk and approximate

as:

• Use the iterative scheme to find

Pattern Classification,
 2
5

• If n is the known number of patterns and c the desired

number of clusters, the k-means algorithm is:

Begin
initialize n, c, μ1, μ2, …, μc(randomly
selected)
do classify n samples according to
nearest μi
recompute μi
until no change in μi
return μ1, μ2, …, μc
End

Complexity is O(ndcT) where d is the # features, T the # iterations

Pattern Classification,
 2
6
• K-means cluster on data from previous figure

Pattern Classification,
 2
7
Unsupervised Bayesian Learning

• Other than the ML estimate, the Bayesian estimation

technique can also be used in the unsupervised case
(see chapters ML & Bayesian methods, Chap. 3 of the
textbook)
• number of classes is known
• class priors are known
• forms of class-conditional probability densities P(x|ωj, θj) are
known
• However, the full parameter vector θ is unknown
• Part of our knowledge about θ is contained in the prior p(θ)
• rest of our knowledge of θ is in the training samples
• We compute the posterior distribution usingPattern Classification,
the training
 2
8
• We can compute p(θ|D) as seen previously

P(ωi|D) = P(ωi) since selection of ωi is independent of previous samples

and passing through the usual formulation introducing the
unknown parameter vector θ.

• Hence, the best estimate of p(x|ωi) is obtained by

averaging p(x|ωi, θi) over θi.
• The goodness of this estimate depends on p(θ|D); this is
the main issue of the problem.
Pattern Classification,
 2
9
From Bayes we get:

where independence of the samples yields the likelihood

or alternately (denoting Dn the set of n samples) the recursive

form:

• If p(θ) is almost uniform in the region where p(D|θ) peaks,

then p(θ|D) peaks in the same place.
Pattern Classification,
 3
0
• If the only significant peak occurs at and the peak is
very sharp, then

and

• Therefore, the ML estimate is justified.

• Both approaches coincide if large amounts of data are
available.
• In small sample size problems they can agree or not,
depending on the form of the distributions
• The ML method is typically easier Pattern Classification,
 3
1
• Formal Bayesian solution: unsupervised learning of the
parameters of a mixture density is similar to the supervised
learning of the parameters of a component density.
• Significant differences: identifiability, computational
complexity
• The issue of identifiability
• With SL, the lack of identifiability means that we do not obtain a
unique vector, but an equivalence class, which does not present
theoretical difficulty as all yield the same component density.
• With UL, the lack of identifiability means that the mixture cannot be
decomposed into its true components
⇒ p(x | Dn) may still converge to p(x), but p(x |ωi, Dn) will not in
general converge to p(x |ωi), hence there is a theoretical barrier.

• The computational complexity

Pattern Classification,
 3
2
• With UL, samples comes from a mixture density and
there is little hope of finding simple exact solutions for
p(D | θ). n samples results in 2n terms. (Corresponding
to the ways in the which the n samples can be drawn
from the 2 classes.)

• Another way of comparing the UL and SL is to

consider the usual equation in which the mixture
density is explicit

Pattern Classification,
 3
3
From
Previous
slide

• If we consider the case in which P(ω1)=1 and all

other prior probabilities as zero, corresponding to
the supervised case in which all samples comes
from the class ω1, then we get

Pattern Classification,
 3
4

Eqns From
Previous
slide

• Comparing the two eqns, we see that observing an additional sample

changes the estimate of θ.
• Ignoring the denominator which is independent of θ, the only significant
difference is that
• in the SL, we multiply the “prior” density for θ by the component density p(xn
|ω1, θ1)
• in the UL, we multiply the “prior” density by the whole mixture

• Assuming that the sample did come from class ω1, the effect of not knowing this
category is to diminish the influence of xn in changing θPattern Classification,
for category 1..
 3
5
Data Clustering
• Structures of multidimensional patterns are important
for clustering
• If we know that data come from a specific distribution,
such data can be represented by a compact set of
parameters (sufficient statistics)

• If samples are considered

coming from a specific
distribution, but actually they
are not, these statistics is a
misleading representation of
the data

Pattern Classification,
 3
6

• Aproximation of density functions:

• Mixture of normal distributions can approximate arbitrary
PDFs

• In these cases, one can use parametric methods

to estimate the parameters of the mixture density.
• No free lunch dimensionality issue!

• Huh?

Pattern Classification,
 3
7
Caveat
• If little prior knowledge can be assumed, the
assumption of a parametric form is meaningless:
• Issue: imposing structure vs finding structure

• use non parametric method to estimate the

unknown mixture density.

• Alternatively, for subclass discovery:

• use a clustering procedure
• identify data points having strong internal similarities
Pattern Classification,
 3
8
Similarity measures
• What do we mean by similarity?
• Two isses:
• How to measure the similarity between samples?
• How to evaluate a partitioning of a set into clusters?

• Obvious measure of similarity/dissimilarity is the

distance between samples

• Samples of the same cluster should be closer to

Pattern Classification,
 3
9
• Euclidean distance is a possible metric:
• assume samples belonging to same cluster if their
distance is less than a threshold d0

• Clusters defined by Euclidean distance are

invariant to translations and rotation of the feature
space, but not invariant to general transformations
Pattern Classification,
that distort the distance relationship
 4
0

• Achieving invariance:
• normalize the data, e.g., such that they all have zero
means and unit variance,
• or use principal components for invariance to rotation
• A broad class of metrics is the Minkowsky metric

where q≥1 is a selectable parameter:

q = 1 ⇒ Manhattan or city block metric
q = 2 ⇒ Euclidean metric
• One can also used a nonmetric similarity function
Pattern Classification,
 4
1

• It is typically a symmetric function whose value is

large when x and x’ are similar.
• For example, the inner product

• In case of binary-valued features, we have, e.g.:

Tanimoto distance

Pattern Classification,
 4
2
Clustering as optimization
• The second issue: how to evaluate a partitioning of
a set into clusters?

• Clustering can be posed as an optimization of a

criterion function
• The sum-of-squared-error criterion and its variants
• Scatter criteria
• The sum-of-squared-error criterion
• Let ni the number of samples in Di, and mi the mean of
those samples Pattern Classification,
 4
3
• The sum of squared error is defined as

• This criterion defines clusters by their mean vectors mi

it minimizes the sum of the squared lengths of the error x - mi.

• The minimum variance partition minimizes Je

• Results:
• Good when clusters form well separated compact clouds
• Bad with large differences in the number of samples in different
clusters.

Pattern Classification,
 4
4

• Scatter criteria
• Scatter matrices used in multiple discriminant analysis,
i.e., the within-scatter matrix SW and the
between-scatter matrix SB
ST = SB +SW

• Note:
• ST does not depend on partitioning
• In contrast, SB and SW depend on partitioning
• Two approaches:
• minimize the within-cluster
• maximize the between-cluster scatter
Pattern Classification,
 4
5

The trace (sum of diagonal elements) is the

simplest scalar measure of the scatter matrix

• proportional to the sum of the variances in the

coordinate directions
• This is the sum-of-squared-error criterion, Je.

Pattern Classification,
 4
6

• As tr[ST] = tr[SW] + tr[SB] and tr[ST] is independent from

the partitioning, no new results can be derived by
minimizing tr[SB]

• However, seeking to minimize the within-cluster criterion

Je=tr[SW], is equivalent to maximise the between-cluster
criterion

where m is the total mean vector:

Pattern Classification,
 4
7
Iterative optimization

• Clustering discrete optimization problem

• Finite data set finite number of partitions

• What is the cost of exhaustive search?

cn/c! For c clusters. Not a good idea

• Typically iterative optimization used:

• starting from a reasonable initial partition
Pattern Classification,
 4
8

• consider an iterative procedure to minimize the

sum-of-squared-error criterion Je

where Ji is the effective error per cluster.

• Moving sample from cluster Di to Dj, changes

the errors in the 2 clusters by:

Pattern Classification,
 4
9
• Hence, the transfer is advantegeous if the
decrease in Ji is larger than the increase in Jj

Pattern Classification,
 5
0
• Alg. 3 is sequential version of the k-means alg.
• Alg. 3 updates each time a sample is reclassified
• k-means waits until n samples have been reclassified
before updating

• Alg 3 can get trapped in local minima

• Depends on order of the samples
• Basically, myopic approach
• But it is online!

Pattern Classification,
 5
1

• Starting point is always a problem

• Approaches:
1. Random centers of clusters
2. Repetition with different random initialization
3. c-cluster starting point as the solution of the
(c-1)-cluster problem plus the sample farthest from
the nearer cluster center

Pattern Classification,
 5
2
Hierarchical Clustering
• Many times, clusters are not disjoint, but a cluster
may have subclusters, in turn having
sub-subclusters, etc.
• Consider a sequence of partitions of the n
samples into c clusters
• The first is a partition into n cluster, each one
containing exactly one sample
• The second is a partition into n-1 clusters, the third
into n-2, and so on, until the n-th in which there is only
one cluster containing all of the samples
• At the level k in the sequence, c = n-k+1.
Pattern Classification,
 5
3
• Given any two samples x and x’, they will be grouped
together at some level, and if they are grouped a level k,
they remain grouped for all higher levels
• Hierarchical clustering ⇒ tree representation called
dendrogram

Pattern Classification,
 5
4
• Are groupings natural or forced: check similarity values
• Evenly distributed similarity no justification for grouping

• Another representation is based on set, e.g., on the Venn

diagrams

Pattern Classification,
 5
5

• Hierarchical clustering can be divided in

agglomerative and divisive.

• Agglomerative (bottom up, clumping): start with n

singleton cluster and form the sequence by
merging clusters

• Divisive (top down, splitting): start with all of the

samples in one cluster and form the sequence by
successively splitting clusters

Pattern Classification,
 5
6
Agglomerative hierarchical clustering

• The procedure terminates when the specified

number of cluster has been obtained, and returns
the cluster as sets of points, rather than the mean
or a representative vector for each cluster
Pattern Classification,
 5
7
• At any level, the distance between nearest clusters
can provide the dissimilarity value for that level
• To find the nearest clusters, one can use

which behave quite similar of the clusters are

hyperspherical and well separated.
• The computational complexity is O(cn 2 2
d ),Classification,
Pattern n>>c
 5
8
Nearest-neighbor algorithm (single linkage)
• dmin is used

• Viewed in graph terms, an edge is added to the

nearest nonconnected components

• Equivalent of Prims minimum spanning tree

algorithm

• Terminates when the distance between nearest

clusters exceeds an arbitrary threshold
Pattern Classification,
 5
9
• The use of dmin as a distance measure and the
agglomerative clustering generate a minimal
spanning tree

• Chaining effect: defect of this distance measure

(right) Pattern Classification,
 6
0
The farthest neighbor algorithm (complete linkage)
• dmax is used

• This method discourages the growth of elongated

clusters

• In graph theoretic terms:

• every cluster is a complete subgraph
• the distance between two clusters is determined by the
most distant nodes in the 2 clusters

• terminates when the distance between nearest

Pattern Classification,
 6
1
• When two clusters are merged, the graph is
changed by adding edges between every pair of
nodes in the 2 clusters

• All the procedures involving minima or maxima are

sensitive to outliers. The use of dmean or davg are
natural compromises Pattern Classification,
 6
2
The problem of the number of clusters

• How many clusters should there be?

• For clustering by extremizing a criterion function
• repeat the clustering with c=1, c=2, c=3, etc.
• look for large changes in criterion function
• Alternatively:
• state a threshold for the creation of a new cluster
• useful for on line cases
• sensitive to order of presentation of data.
Pattern Classification,
 6
3
Graph-theoretic methods
• Caveat: no uniform way of posing clustering as a
graph theoretic problem
• Generalize from a threshold distance to arbitrary
similarity measures.
• If s0 is a threshold value, we can say that xi is
similar to xj if s(xi, xj) > s0.
• We can define a similarity matrix S = [sij]

Pattern Classification,
 6
4
• This matrix induces a similarity graph, dual to S, in
which nodes corresponds to points and edge joins
node i and j iff sij=1.
• Single-linkage alg.: two samples x and x’ are in the
same cluster if there exists a chain x, x1, x2, …, xk,
x’, such that x is similar to x1, x1 to x2, and so on
⇒ connected components of the graph
• Complete-link alg.: all samples in a given cluster
must be similar to one another and no sample can
be in more than one cluster.
• Neirest-neighbor algorithm is a method to find the
minimum spanning tree and vice versa
• Removal of the longest edge produce Pattern
a 2-cluster
Classification,
grouping, removal of the next longest edge produces a
 6
5
• This is a divisive hierarchical procedure, and
suggest ways to dividing the graph in subgraphs
• E.g., in selecting an edge to remove, comparing its
length with the lengths of the other edges incident the
nodes

Pattern Classification,
 6
6

• One useful statistic to be estimated from the

minimal spanning tree is the edge length
distribution
• For instance, in the case of 2 dense cluster
immersed in a sparse set of points:

Pattern Classification,