Transcript Hierarchical Model-Based Clustering of Large Datasets

Hierarchical Model-Based
Clustering of Large Datasets
Through Fractionation and
Refractionation
Jeremy Tantrum,
Department of Statistics,
University of Washington
joint work with
Alejandro Murua
Insightful Corporation
&
Werner Stuetzle
University of Washington
This work has been supported by NSA grant 62-1942
Motivating Example
• Consider clustering documents
• Topic Detection and Tracking corpus
• 15,863 news stories for one year from Reuters
and CNN
• 25,000 unique words
• Possibly many topics
• Large numbers of observations
• High dimensions
• Many groups
74
76
78
80
82
84
Goal of Clustering
40
45
50
55
Detect that there are 5 or 6 groups
Assign Observations to groups
0.0
0.05
0.10
0.15
NonParametric Clustering
| | | ||||||||||||||||||||| ||||||| | || ||
-10
-5
|| |||||||| |||||| ||| ||| | |
0
| | | |||||||| ||||| ||||||||||||||||||| ||||||||| ||
5
10
Premise:
• Observations are sampled from a density p(x)
• Groups correspond to modes of p(x)
0.0
0.02
0.04
0.06
0.08
0.10
0.12
NonParametric Clustering
| | | |||||||||||| ||||||||| ||||||| | || ||
-10
-5
|| |||||||| |||||| ||| ||| | |
0
| | | |||||||| |||| ||||||||||||||||||| ||||||||| ||
5
10
Fitting:
Estimate p(x) nonparametrically and find significant modes
of the estimate
0.0
0.05
0.10
0.15
Model Based Clustering
| | | ||||||||||||||||||||| ||||||| | || ||
-10
-5
|| |||||||| |||||| ||| ||| | |
0
| | | |||||||| ||||| ||||||||||||||||||| ||||||||| ||
5
10
Premise:
• Observations are sampled from a mixture density
p(x) =  pg pg(x)
• Groups correspond to mixture components
0.0
0.05
0.10
0.15
Model Based Clustering
| | | ||||||||||||||||||||| ||||||| || ||
-10
-5
|| |||||||| |||||| ||| ||| | |
0
| | | ||||||| ||||| ||||||||||||||||||| ||||||||| ||
5
Fitting:
Estimate pg and parameters of pg(x)
10
Model Based Clustering
Fitting a Mixture of Gaussians
• Use the EM algorithm to maximize the log
likelihood
– Estimates the probabilities of each observation
belonging to each group
– Maximizes likelihood given these probabilites
– Requires a good starting point
Model Based Clustering
Hierarchical Clustering
• Provides a good starting point for EM
algorithm
• Start with every point being it’s own cluster
• Merge the two closest clusters
– Measured by the decrease in likelihood when
those two clusters are merged
– Uses the Classification Likelihood – not the
Mixture Likelihood
• Algorithm is quadratic in the number of
observations
Likelihood Distance
Merge gives big decrease in likelihood
p (x)
p1(x)
p2(x)
|
|||||||||| | | |||||||||||| || |
| |
|
|
||| |||| |||||||||||||||||||| |||||||||||||||| ||
|| | |
Merge gives small decrease in likelihood
p (x)
p1(x)
p2(x)
|
|
| |||
| | |||
||
|||| ||||
||| |
||| ||
||||
|||||
| ||
|
||
|||||
|
|
|
||| |||
||
|| ||| | |||||| |
||| |
||
|| | |
Bayesian Information Criterion
• Choose number of clusters by maximizing
the Bayesian Information Criterion
– r is the number of parameters
– n is the number of observations
• Log likelihood penalized for complexity
Fractionation
Invented by Cutting, Karger, Pederson and Tukey for
nonparametric clustering of large datasets.
M is the largest number of observations for which a hierarchical
O(M2) algorithm is computationally feasible
Original Data – size n
n/M fractions of size M
Partition each fraction into aM clusters
a<1
an clusters
If an >M
(meta-obervations, mi)
Fractionation
– an meta-observations after the first round
– a2n meta-observations after the second round
– ain meta-observations after the ith round
• For the ith pass, we have ai-1n/M fractions
taking O(M2) operations each
• Total number of operations is:
• Total running time is linear in n!
Model Based Fractionation
• Use model based clustering
• Meta-observations contain all sufficient
statistics – (ni, mi, Si)
– ni is the number of observations – size
– mi is the mean – location
– Si is the covariance matrix – shape and volume
Model Based Fractionation
The Final Clusters Chosen by BIC
10
10
meta-observations
meta-observations
The 40
Meta-observations
from
from
the
the
fourth
third
fraction
fraction
10
An
meta-observations
example,
Observations
400
observations
infrom
the
from
first
thesecond
fraction
first
in 4 fraction
groups
10
meta-observations
the
fraction
0.5
0.5
1.0
1.5
2.0
2.5
Success!
•
•• •
•
•
••••••• • •• ••
•
•
•
•
••••• • ••• • •
•
•• •• • ••• •••
••••••• •••• •• •• •• • • ••••••• ••••• •••
•
•
• • • ••••••••••••••• ••
••••• ••••••••••••• ••• •
• • • • •• ••••••••••• • •
• • ••••••• ••••••••
• • • • • •• ••
• •• • •• ••
• • ••••
•
•
•
• • ••
• • • •• • •
•• •••• ••• •• •• • •
•
• • •••• •••• •••••••• •
• ••
• • ••• •••••••••••••••••••••
• • •••• • • ••
•
• •
•
•
•• •
•• •
•
• •• •
•••••• •• ••••••• •• •
•••• ••••••••••••••••••••••••••
• ••• ••
••• ••••• ••
••• •••••• ••
•
••
••• •
•
1.0
1.5
2.0
2.0
Example 2
The clusters chosen by BIC
10
10
10
10
The
meta-observations
meta-observations
meta-observations
meta-observations
dataObservations
The
– 400
40 meta-observations
observations
from
from
from
from
in fraction
the
the
the
thesecond
in
fourth
third
first
25
1 groups
fraction
fraction
fraction
fraction
1
2
3
4
5
Fractionation fails!
•• •••••••••••••••••
•• ••• ••
•• •••••
•• •••••••••••
•• ••• ••••
•• ••••••••••••••••
•••••• ••••• ••
••
• ••
••
•
•••• ••••••••••••••• ••
••
•• ••
•
•
••••• • •• • ••••••• ••••••
•••
•• •••
•
•
•• ••
•
••
••• •••••••••••• ••
••••••••
•• • ••• •••• •••••
•
•
• •• ••
•
•
••• •• •• •••••• ••••••••••••••••••••••• ••
••
•• •••
•••
•
•
• •••
• •••• •
•
•
• • ••
• •
•
•
•
•• ••
• • ••
•• • •
•
•
1
2
••
•
•
•
••
••
•••
••••••••••••••••••••• ••• •••• •• ••••••• •• •• •••••••••••• ••
••
••••• ••• •••• •• ••
•
•
•
•
•
• •••
•
•
• •
••• ••
••••••••••••• ••
•
•
•
•
•••
• ••••
• • •••
•
•
•
•
•
•
•
•
•
• •••• •• ••
•• •• ••••• ••••
• •••
•• •
•• ••
••• •• •
• ••
•
•
•
•
•
•
•• • • •••••• •••• •••••••••• •• •
•••
•••
••
•
•
• • ••••••
•
•
•• •••• •••••
••••••••• •
••
•• •
•• ••• •
••
• •• •
•
•
•
•••••••••••••••• •••••••••••••••••••••••••• ••••••••••• •••••••••
•
••• ••
•••
••
•••• •• •
•
•
•
•
•
•
•
•
••••••• •
•••••• ••••••• •
•
••••••••••••••••••••
•
•
•
•
•
••
• •••••
••••••••
•• ••••
•• •
3
4
5
Refractionation
Problem:
• If the number of meta-observations generated from a
fraction is less than the number of groups in that fraction
then two or more groups will be merged.
• Once observations from two groups are merged they can
never be split again.
Solution:
• Apply fractionation repeatedly.
• Use meta-observations from the previous pass of
fractionation to create “better” fractions.
Example 2 Continued
1
2
3
4
5
The 40
44new
meta-observations
newfractions
clusters
• •••••••
• •• •
• ••
• ••••••
• • ••
• ••••••
•••• ••• •
•• •••
•• •••• • •
••
•
••••• •• • •• ••• •••
••
•• •••
•
•
•
•
••
• •••••• •
••••••••
•• • •• •• ••
•
•
•
•• ••••• •• •••••• •
• ••
•• •••
•
•
••
1
2
•
•
•
••
••••••• • • ••• ••• • • •••••• •
••
••• • •• • •
•
••
•• •
•
•••••• •
• •• •• • •••••• • ••• •• ••••
• ••
• •
• •
• •
••• •
•
•
•
•
•• •••• • ••••• •• •••••••• •
••
••••
•
•
••
•
•
•
•
•
•
•• ••••• ••••••••••• •••••••••
•
•• •
••
•
•• •
•
•
•
•••
••• ••••
•
•••••••••
•
•
••
• ••
•••••
• ••
••
3
4
5
Example 2 – Pass 2
1
2
3
4
5
Observations
Clusters
Clusters
Clusters
Clusters
The
Clusters
40
from
from
from
from
meta-observations
in
chosen
the
the
the
thesecond
fourth
third
first
new
by fraction
BIC
fraction
fraction
fraction1
•• •••••••••••••••••
•• ••• ••
•• •••••
•• •••••••••••
•• ••• ••••
•• ••••••••••••••••
•••••• ••••• ••
•
••
• •
••
•
•••• ••••••••••••••• ••
••
•
•• •
•
•
•
•••••• ••••••
••••• • ••
••••
•• •••
•
•
•• ••
•
••
••• •••••••••••• ••
••••••••
•• • ••• •••• •••••
•
•
• •• ••
•
•
••• •• •• •••••• ••••••••••••••••••••••• ••
••
•• •••
•••
•
•
• •••
• •••• •
•
•
• • ••
• •
•
•
•
•• ••
• • ••
•• • •
•
•
1
2
••
•
•
•
••
••
•••
••••••••••••••••••••••• ••• •••• •• ••••••• •• •• •••••••••••• ••
••
••••• ••• •••• •• ••
•
•
•
•
•
•
• •
•
•
• •
•••• ••
••••••••••••• ••
•
•
•
•
•••
••
•••
• • •
••
•
•
•
•
•
•
•
•
•
•
• •••• •• ••
•• •• ••••• ••••
• •••
•• •
•• ••
••• •• •
•
• •
•
•
•
•
•
•
••• •
•••
•• •
••
••
• ••
••••••••• ••• •
• ••
•
•
•••
• ••
• •
•
•
•
•
•
•
•
•
•
•
• •• ••••
••••••••• •
•• •
•• •
•• ••• •
••
••
•
• •
•
•
••••••••••••• ••• •••••••••••••••••••••••••• ••••••••••• •••••••••
•
••• ••
•••
••
•• •• •• •
•
•
•
•
•
•
•
•
•••••• ••••••• •
••••
• •
•
••••••••••••••••••••
•
•
••
•
•
•
•
•
•
••
• •••••
•••••••••••
•• ••••
•• •
3
4
5
Example 2 – Pass 3
Clusters chosen by BIC
The 40 meta-observations
Observations
Clusters
Clusters
Clusters
Clusters
The 40
from
4from
4from
from
new
meta-observations
new
inthe
the
the
fractions
the
clusters
of
second
fourth
third
first
new
passfraction
fraction
2fraction
fraction
of fractionation
1
1
2
3
4
5
Refractionation Succeeds
•• •••••••••••••••••
•• ••• ••
•• •••••
•• •••••••••••
•• ••• ••••
•• ••••••••••••••••
•••••• ••••• ••
••
• ••
••
•
•••• ••••••••••••••• ••
••
•• ••
•
•
••••• • •• • ••••••• ••••••
•••
•• •••
•
•
•• ••
•
••
••• •••••••••••• ••
••••••••
•• • ••• •••• •••••
•
•
• •• ••
•
•
••• •• •• •••••• ••••••••••••••••••••••• ••
••
•• •••
•••
•
•
• •••
• •••• •
•
•
• • ••
• •
•
•
•
•• ••
• • ••
•• • •
•
•
1
2
••
•
•
•
••
••
•••
••••••••••••••••••••• ••• •••• •• ••••••• •• •• •••••••••••• ••
••
••••• ••• •••• •• ••
•
•
•
•
•
• •••
•
•
• •
••• ••
••••••••••••• ••
•
•
•
•
•••
• ••••
• • •••
•
•
•
•
•
•
•
•
•
• •••• •• ••
•• •• ••••• ••••
• •••
•• •
•• ••
••• •• •
• ••
•
•
•
•
•
•
•• • • •••••• •••• •••••••••• •• •
•••
•••
••
•
•
• • ••••••
•
•
•• •••• •••••
••••••••• •
••
•• •
•• ••• •
••
• •• •
•
•
•
•••••••••••••••• •••••••••••••••••••••••••• ••••••••••• •••••••••
•
••• ••
•••
••
•••• •• •
•
•
•
•
•
•
•
•
••••••• •
•••••• ••••••• •
•
••••••••••••••••••••
•
•
•
•
•
••
• •••••
••••••••
•• ••••
•• •
3
4
5
Realistic Example
• 1100 documents from the TDT corpus
partitioned by people into 19 topics
– Transformed into 50 dimensional space using Latent
Semantic Indexing
•
• •• ••• •
• •••
•• •
• ••• •••
•• •
• •••• •• •
• •• ••• •
• ••• • •
•••• •
•
• •• • •• •
•
••• •• • •••
•
• •••• •• • •
•• •••••••••••••••••••• ••••• •• •
•• • •
• •••
•••• •••••••••••••••••••••••••••••••••
•
•
•
•• ••••• ••••••
••••••• •••
•• •••
••••••••••••• • •
•
•
•
•
•
••••••• ••••••••••••••••••••••••••••••••••••••••••••••
•
• •• •••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• •••
•
•
• ••••••• •••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• • •
•
• ••••••••••••••••• •••••••••••••••••••••••••• ••••••••••••••••••••••••••••• •••••••••• •••••••
•• •
•
• •
••• ••••••••••••••••••••••
••• • ••••••••••••••••••••••• ••••••• • • • •••••••••••• • • •
• ••
•
•
•
•
• ••••• •• •
• •• • •• ••
••••• ••
•
•
•
•
•
•
•••• • •
•• • •
•
• •• ••• •••
•••• ••••
•
•••••••• ••
•
•
•
• • •• •
•
•
•
•
•
•
•
•
•
• ••••• • ••
•
• •• •••••••• •••••••••••••••••
• •• • ••
• ••••• ••••••••••••••
••• ••••• ••
•
••• •••••••••••••••••••••••••••••••••••••••
•••• ••••••••••• •
•• ••••• •
• •• ••••
••••
Projection of the data
onto a plane – colors
represent topics
•
•
•
••
••• ••••••••••••• ••• • •
• • ••• • •• • •• •
• •••••• •• • ••• •• •
•••••••••••••••••••••••••••••• •
• ••• • ••
• • ••
Realistic Example
Want to create a dataset with more observations and more
groups
Idea: Replace each group with a scaled and transformed
version of the entire data set.
Realistic Example
Want to create a dataset with more observations and more
groups
Idea: Replace each group with a scaled and transformed
version of the entire data set.
Realistic Example
To measure similarity of clusters to groups:
Fowlkes-Mallows index
• Geometric average of:
– Probability of 2 randomly chosen observations from
the same cluster being in the same group
– Probability of 2 randomly chosen observations from
the same group being in the same cluster
• Fowlkes–Mallows index near 1 means clusters
are good estimates of the groups
• Clustering the 1100 documents gives a Fowlkes–
Mallows index of 0.76 – our “gold standard”
Realistic Example
• 19£19=361 clusters, 19£1100=20900 observations in
50 dimensions
• Fraction size¼1000 with 100 metaobservations per
fraction
• 4 passes of fractionation choosing 361 clusters
Number of
fractions
Pass Min Median Max nf
1 270
289
296 20
2 18
88
150 18
3 18
19
60
17
4 19
19
58
16
Distribution of the number of groups per fraction.
Realistic Example
• 19£19=361 clusters, 19£1100=20900 observations in
50 dimensions
• Fraction size¼1000 with 100 metaobservations per
fraction
• 4 passes of fractionation choosing 361 clusters
Pass Fowlkes Purity of
Mallows the clusters
1 0.325
1729
2 0.554
908
3 0.616
671
4 0.613
651
The sum of the
number of groups
represented in each
cluster:
• 361 is perfect
Realistic Example
• 19£19=361 clusters, 19£1100=20900 observations in
50 dimensions
• Fraction size¼1000 with 100 metaobservations per
fraction
• 4 passes of fractionation choosing 361 clusters
Refractionation:
• Purifies fractions
• Successfully deals with the case where the number of
groups is greater than aM, the number of metaobservations
Contributions
• Model Based Fractionation
– Extended fractionation idea to parametric setting
• Incorporates information about size, shape and volume
of clusters
• Chooses number of clusters
– Still linear in n
• Model Based ReFractionation
– Extended fractionation to handle larger number of
groups
Extensions
• Extend to 100,000s of observations – 1000s
of groups
– Currently the number of groups must be less
than M
• Extend to a more flexible class of models
– With small groups in high dimensions, we need
a more constrained model (fewer parameters)
than the full covariance model
– Mixture of Factor Analyzers
Fowlkes-Mallows Index
true
clusters
Groups
1
2
…
I
Total
1
n11
n12
…
n1I
2
n21
n22
…
n2I
n1 ¢
…
…
…
…
…
J
nJ1
nj2
…
nJI
Total
n¢ 1
n¢ 2
…
n¢ I
Pr(2 documents in same group |
they are in the same cluster)
n1 ¢
…
n1 ¢
n
Pr(2 documents in same cluster |
they are in the same group)