Clustering

1
 What is Cluster Analysis?
• Finding groups of objects such that the objects in a group will be
similar (or related) to one another and different from (or
unrelated to) the objects in other groups
Applications of Cluster Analysis

• Understanding Discovered Clusters

Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN,
Industry Group

• Group related documents for 1 Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,

DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN,
Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,
Technology1-DOWN
browsing, group genes and Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN,
Sun-DOWN
proteins that have similar Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN,

functionality, or group stocks 2 ADV-Micro-Device-DOWN,Andrew-Corp-DOWN,

Computer-Assoc-DOWN,Circuit-City-DOWN,
Compaq-DOWN, EMC-Corp-DOWN, Gen-Inst-DOWN,
Technology2-DOWN

with similar price fluctuations Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWN

Fannie-Mae-DOWN,Fed-Home-Loan-DOWN,

3 MBNA-Corp-DOWN,Morgan-Stanley-DOWN Financial-DOWN
Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,

• Summarization 4 Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP,
Schlumberger-UP
Oil-UP

• Reduce the size of large data

sets

Clustering precipitation
in Australia
What is not Cluster Analysis?

• Supervised classification
• Have class label information

• Simple segmentation
• Dividing students into different registration groups alphabetically,
by last name

• Results of a query
• Groupings are a result of an external specification

• Graph partitioning
• Some mutual relevance and synergy, but areas are not identical
Notion of a Cluster can be Ambiguous

How many clusters? Six Clusters

Two Clusters Four Clusters

Types of Clusterings

• A clustering is a set of clusters

• Important distinction between hierarchical and partitional sets of

clusters

• Partitional Clustering
• A division data objects into non-overlapping subsets (clusters) such
that each data object is in exactly one subset

• Hierarchical clustering
• A set of nested clusters organized as a hierarchical tree
Partitional Clustering

Original Points A Partitional Clustering

Hierarchical Clustering

p1
p3 p4
p2
p1 p2 p3 p4
Traditional Hierarchical Clustering Traditional Dendrogram

p1
p3 p4
p2
p1 p2 p3 p4
Non-traditional Hierarchical Clustering Non-traditional Dendrogram
Other Distinctions Between Sets of Clusters

• Exclusive versus non-exclusive

• In non-exclusive clusterings, points may belong to multiple clusters.
• Can represent multiple classes or ‘border’ points
• Fuzzy versus non-fuzzy
• In fuzzy clustering, a point belongs to every cluster with some
weight between 0 and 1
• Weights must sum to 1
• Probabilistic clustering has similar characteristics
• Partial versus complete
• In some cases, we only want to cluster some of the data
• Heterogeneous versus homogeneous
• Cluster of widely different sizes, shapes, and densities
Types of Clusters

• Well-separated clusters

• Center-based clusters

• Contiguous clusters

• Density-based clusters

• Property or Conceptual

• Described by an Objective Function

Types of Clusters: Well-Separated

• Well-Separated Clusters:
• A cluster is a set of points such that any point in a cluster is closer
(or more similar) to every other point in the cluster than to any
point not in the cluster.

3 well-separated clusters
Types of Clusters: Center-Based

• Center-based
• A cluster is a set of objects such that an object in a cluster is closer
(more similar) to the “center” of a cluster, than to the center of any
other cluster
• The center of a cluster is often a centroid, the average of all the
points in the cluster, or a medoid, the most “representative” point
of a cluster

4 center-based clusters
Types of Clusters: Contiguity-Based

• Contiguous Cluster (Nearest neighbor or Transitive)

• A cluster is a set of points such that a point in a cluster is closer (or
more similar) to one or more other points in the cluster than to any
point not in the cluster.

8 contiguous clusters
Types of Clusters: Density-Based

• Density-based
• A cluster is a dense region of points, which is separated by low-
density regions, from other regions of high density.
• Used when the clusters are irregular or intertwined, and when noise
and outliers are present.

6 density-based clusters
Types of Clusters: Conceptual Clusters

• Shared Property or Conceptual Clusters

• Finds clusters that share some common property or represent a
particular concept.
.

2 Overlapping Circles
Types of Clusters: Objective Function

• Clusters Defined by an Objective Function

• Finds clusters that minimize or maximize an objective function.
• Enumerate all possible ways of dividing the points into clusters and
evaluate the `goodness' of each potential set of clusters by using the given
objective function. (NP Hard)
• Can have global or local objectives.
• Hierarchical clustering algorithms typically have local objectives
• Partitional algorithms typically have global objectives
• A variation of the global objective function approach is to fit the data to a
parameterized model.
• Parameters for the model are determined from the data.
• Mixture models assume that the data is a ‘mixture' of a number of statistical
distributions.
Types of Clusters: Objective Function …

• Map the clustering problem to a different domain and solve a related

problem in that domain
• Proximity matrix defines a weighted graph, where the nodes are the points
being clustered, and the weighted edges represent the proximities between
points

• Clustering is equivalent to breaking the graph into connected components,

one for each cluster.

• Want to minimize the edge weight between clusters and maximize the edge
weight within clusters
Characteristics of the Input Data Are
Important

• Type of proximity or density measure

• This is a derived measure, but central to clustering
• Sparseness
• Dictates type of similarity
• Adds to efficiency
• Attribute type
• Dictates type of similarity
• Type of Data
• Dictates type of similarity
• Other characteristics, e.g., autocorrelation
• Dimensionality
• Noise and Outliers
• Type of Distribution
Clustering Algorithms

• K-means and its variants

• Hierarchical clustering

• Density-based clustering
K-means Clustering

• Partitional clustering approach

• Each cluster is associated with a centroid (center point)
• Each point is assigned to the cluster with the closest centroid
• Number of clusters, K, must be specified
• The basic algorithm is very simple
K-means Clustering – Details

• Initial centroids are often chosen randomly.

• Clusters produced vary from one run to another.
• The centroid is (typically) the mean of the points in the cluster.
• ‘Closeness’ is measured by Euclidean distance, cosine similarity,
correlation, etc.
• K-means will converge for common similarity measures
mentioned above.
• Most of the convergence happens in the first few iterations.
• Often the stopping condition is changed to ‘Until relatively few points
change clusters’
• Complexity is O( n * K * I * d )
• n = number of points, K = number of clusters,
I = number of iterations, d = number of attributes
Two different K-means Clusterings
3

3
2.5

2.5

2
2
Original Points
1.5

y
1.5
1

y
1
0.5

0.5
0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

-2 -1.5 -1 -0.5 0 x 0.5 1 1.5 2

x

3 3

3 3
2.5 2.5

2.5 2.5
2 2

2 2
1.5 1.5
y

y
1.5 1.5
1 1
y

y
1 1
0.5 0.5

0.5 0.5
0 0

0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

-2 -1.5 -1 -0.5 0 x 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 x 0.5 1 1.5 2

Optimalx Clustering x
Sub-optimal Clustering
Optimal Clustering Sub-optimal Clustering
Importance of Choosing Initial Centroids

Iteration 6
1
2
3
4
5
3

2.5

1.5
y

0.5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x
 Importance of Choosing Initial Centroids
Iteration 1 Iteration 2 Iteration 3
3 3 3

2.5 2.5 2.5

2 2 2

1.5 1.5 1.5

y

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x

Iteration 4 Iteration 5 Iteration 6

3 3 3

2.5 2.5 2.5

2 2 2

1.5 1.5 1.5

y

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x
Evaluating K-means Clusters

• Most common measure is Sum of Squared Error (SSE)

• For each point, the error is the distance to the nearest cluster
• To get SSE, we square these errors and sum them.
K
SSE   dist 2 ( mi , x )
i 1 xCi

• x is a data point in cluster Ci and mi is the representative point for

cluster Ci
• can show that mi corresponds to the center (mean) of the cluster
• Given two clusters, we can choose the one with the smallest error
• One easy way to reduce SSE is to increase K, the number of clusters
• A good clustering with smaller K can have a lower SSE than a poor
clustering with higher K
Importance of Choosing Initial Centroids …

Iteration 5
1
2
3
4
3

2.5

1.5
y

0.5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x
 Importance of Choosing Initial Centroids …

Iteration 1 Iteration 2
3 3

2.5 2.5

2 2

1.5 1.5
y

y
1 1

0.5 0.5

0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x x

Iteration 3 Iteration 4 Iteration 5

3 3 3

2.5 2.5 2.5

2 2 2

1.5 1.5 1.5

y

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x
Problems with Selecting Initial Points

• If there are K ‘real’ clusters then the chance of selecting one centroid from each
cluster is small.
• Chance is relatively small when K is large
• If clusters are the same size, n, then

• For example, if K = 10, then probability = 10!/1010 = 0.00036

• Sometimes the initial centroids will readjust themselves in ‘right’ way, and
sometimes they don’t
• Consider an example of five pairs of clusters
10 Clusters Example
Iteration 4
1
2
3
8

2
y

-2

-4

-6

0 5 10 15 20
x
Starting with two initial centroids in one cluster of each pair of clusters
10 Clusters Example
Iteration 1 Iteration 2
8 8

6 6

4 4

2 2
y

y
0 0

-2 -2

-4 -4

-6 -6

0 5 10 15 20 0 5 10 15 20
x x
Iteration 3 Iteration 4
8 8

6 6

4 4

2 2
y

y
0 0

-2 -2

-4 -4

-6 -6

0 5 10 15 20 0 5 10 15 20
x x

Starting with two initial centroids in one cluster of each pair of clusters
10 Clusters Example
Iteration 4
1
2
3
8

2
y

-2

-4

-6

0 5 10 15 20
x
Starting with some pairs of clusters having three initial centroids, while other have only
one.
10 Clusters Example
Iteration 1 Iteration 2
8 8

6 6

4 4

2 2
y

y
0 0

-2 -2

-4 -4

-6 -6

0 5 10 15 20 0 5 10 15 20
Iteration
x 3 Iteration
x 4
8 8

6 6

4 4

2 2
y

y
0 0

-2 -2

-4 -4

-6 -6

0 5 10 15 20 0 5 10 15 20
x x

Starting with some pairs of clusters having three initial centroids, while other have only
one.
Solutions to Initial Centroids
Problem
• Multiple runs
• Helps, but probability is not on your side
• Sample and use hierarchical clustering to determine initial centroids
• Select more than k initial centroids and then select among these
initial centroids
• Select most widely separated
• Postprocessing
• Bisecting K-means
• Not as susceptible to initialization issues
Handling Empty Clusters

• Basic K-means algorithm can yield empty clusters

• Several strategies
• Choose the point that contributes most to SSE
• Choose a point from the cluster with the highest SSE
• If there are several empty clusters, the above can be repeated several times.
Updating Centers Incrementally

• In the basic K-means algorithm, centroids are updated after all points
are assigned to a centroid

• An alternative is to update the centroids after each assignment

(incremental approach)
• Each assignment updates zero or two centroids
• More expensive
• Introduces an order dependency
• Never get an empty cluster
• Can use “weights” to change the impact
Bisecting K-means

• Bisecting K-means algorithm

• Variant of K-means that can produce a partitional or a
hierarchical clustering
Bisecting K-means Example
Limitations of K-means

• K-means has problems when clusters are of differing

• Sizes
• Densities
• Non-globular shapes

• K-means has problems when the data contains outliers.

Limitations of K-means: Differing Sizes

Original Points K-means (3 Clusters)

Limitations of K-means: Differing Density

Original Points K-means (3 Clusters)

Limitations of K-means: Non-globular Shapes

Original Points K-means (2 Clusters)

Overcoming K-means Limitations

Original Points K-means Clusters

One solution is to use many clusters.

Find parts of clusters, but need to put together.
Overcoming K-means Limitations

Original Points K-means Clusters

Overcoming K-means Limitations

Original Points K-means Clusters

Hierarchical Clustering

• Produces a set of nested clusters organized as a hierarchical tree

• Can be visualized as a dendrogram
• A tree like diagram that records the sequences of merges or splits

6 5
0.2
4
3 4
0.15 2
5
2
0.1

1
0.05
3 1

0
1 3 2 5 4 6
Strengths of Hierarchical Clustering

• Do not have to assume any particular number of clusters

• Any desired number of clusters can be obtained by ‘cutting’ the dendogram
at the proper level

• They may correspond to meaningful taxonomies

• Example in biological sciences (e.g., animal kingdom, phylogeny
reconstruction, …)
Hierarchical Clustering

• Two main types of hierarchical clustering

• Agglomerative:
• Start with the points as individual clusters
• At each step, merge the closest pair of clusters until only one cluster (or
k clusters) left

• Divisive:
• Start with one, all-inclusive cluster
• At each step, split a cluster until each cluster contains a point (or there
are k clusters)

• Traditional hierarchical algorithms use a similarity or

distance matrix
• Merge or split one cluster at a time
Hierarchical Clustering Methods

• The partition of data is not done at a single step.

• There are two varieties of hierarchical clustering algorithms
• Agglomerative – successively fusions of the data into groups
• Divisive – separate the data successively into finer groups

48
Dendrogram

• Hierarchic grouping can be represented by two-dimensional diagram

known as a dendrogram.

Dendrogram 3
4
5
2
1

5.0 4.0 3.0 2.0 1.0 0

Distance
49
Distance

• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

50
Single Linkage

• Also, known as the nearest neighbor technique

• Distance between groups is defined as that of the
closest pair of data, where only pairs consisting of
one record from each group are considered

Cluster B
Cluster A

51
 1 2 3 4 5
(12) 3 4 5
1  0.0 
 
2  2.0 0.0  (12)  0.0 
 
3
 6.0 5.0 0.0  3  5.0 0.0 
   9.0 4.0 0.0 
4  10.0 9.0 4.0 0.0  4
 
 9.0  8.0 5.0 3.0 0.0 
5  8.0 5.0 3.0 0.0  5  
Dendrogram

2
1

5.0 4.0 3.0 2.0 1.0 0 52

Distance
 (12) 3 4 5

(12)  0.0 
 
3  5.0 0.0 
 9.0 4.0 0.0 
4
 
 8.0 5.0 3.0 0.0 
5  
Dendrogram

2
1

5.0 4.0 3.0 2.0 1.0 0 53

Distance
 (12) 3 4 5
(12) 3 (4 5)
(12)  0.0 
  (12)  0.0 
3  5.0 0.0   
 9.0 4.0 0.0  3  5.0 0.0 
4
  (4 5)
 8.0 4.0 0.0 
 8.0 5.0 3.0 0.0   
5  
Dendrogram 5
4

2
1

5.0 4.0 3.0 2.0 1.0 0 54

Distance
 (12) 3 (4 5)
(12)  0.0 
 
3  5.0 0.0 
(4 5)
 8.0 4.0 0.0 
 

Dendrogram 5
4

2
1

5.0 4.0 3.0 2.0 1.0 0 55

Distance
 (12) 3 (4 5)
(12) (3 4 5)
(12)  0.0 
  (12)  0 .0 
3  5.0 0.0   
 8.0 4.0 0.0  (3 4 5)  5.0 0.0 
(4 5)  

Dendrogram 5
4
3
2
1

5.0 4.0 3.0 2.0 1.0 0 56

Distance
 (12) (3 4 5)
(12)  0 .0 
 
(3 4 5)  5.0 0.0 

Dendrogram 5
4
3
2
1

5.0 4.0 3.0 2.0 1.0 0 57

Distance
 (12) (3 4 5)
(12)  0 .0 
 
(3 4 5)  5.0 0.0 

Dendrogram 5
4
3
2
1

5.0 4.0 3.0 2.0 1.0 0 58

Distance
Distance

• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

59
Complete Linkage

• The distance between two clusters is given by the distance between

their most distant members

Cluster B
Cluster A

60
 1 2 3 4 5
(12) 3 4 5
1  0.0 
 
2  2.0 0.0  (12)  0.0 
 
3
 6.0 5.0 0.0  3  6.0 0.0 
   10.0 4.0 0.0 
4  10.0 9.0 4.0 0.0  4
 
 9.0  9.0 5.0 3.0 0.0 
5  8.0 5.0 3.0 0.0  5  
Dendrogram

2
1

10.0 8.0 6.0 4.0 2.0 0 61

Distance
 (12) 3 4 5

(12)  0.0 
 
3  6.0 0.0 
 10.0 4.0 0.0 
4
 
 9.0 5.0 3.0 0.0 
5  
Dendrogram

2
1

10.0 8.0 6.0 4.0 2.0 0 62

Distance
 (12) 3 4 5
(12) 3 (4 5)
(12)  0.0 
  (12)  0.0 
3  6.0 0.0   
 10.0 4.0 0.0  3  6.0 0.0 
4
   10.0 5.0 0.0 
 9.0 5.0 3.0 0.0  (4 5)  
5  

Dendrogram 5
4

2
1

10.0 8.0 6.0 4.0 2.0 0 63

Distance
 (12) 3 (4 5)

(12)  0.0 
 
3  6.0 0.0 
 10.0 5.0 0.0 
(4 5)  

Dendrogram 5
4

2
1

10.0 8.0 6.0 4.0 2.0 0 64

Distance
 (12) 3 (4 5)
(12) (3 4 5)
(12)  0.0 
  (12)  0.0 
3  6.0 0.0   
 10.0 5.0 0.0  (3 4 5)  10.0 0.0 
(4 5)  

Dendrogram 5
4
3
2
1

10.0 8.0 6.0 4.0 2.0 0 65

Distance
 (12) (3 4 5)

(12)  0.0 
 
(3 4 5)  10.0 0.0 

Dendrogram 5
4
3
2
1

10.0 8.0 6.0 4.0 2.0 0 66

Distance
 (12) (3 4 5)

(12)  0.0 
 
(3 4 5)  10.0 0.0 

Dendrogram 5
4
3
2
1

10.0 8.0 6.0 4.0 2.0 0 67

Distance
Distance

• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

68
 Group Average Clustering

• The distance between two clusters is defined as the average of the

distances between all pairs of records (one from each cluster).
• dAB = 1/6 (d13 + d14 + d15 + d23 + d24 + d25)

Cluster B
3
Cluster A 4
5
2
1 69
Distance

• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

70
Centroid Clustering

• The distance between two clusters is defined as

the distance between the mean vectors of the
two clusters.
• dAB = dab
• where a is the mean vector of the cluster A and
b is the mean vector of the cluster B.
Cluster B

Cluster A b

a
71
Distance

• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

72
Median Clustering

• Disadvantage of the Centroid Clustering: When a large

cluster is merged with a small one, the centroid of the
combined cluster would be closed to the large one, ie.
The characteristic properties of the small one are lost
• After we have combined two groups, the mid-point of the
original two cluster centres is used as the centre of the
newly combined group

Cluster B
Cluster A

a
b

73
Divisive Methods

• In a divisive algorithm, we start with the

assumption that all the data is part of one cluster.
• We then use a distance criterion to divide the
cluster in two, and then subdivide the clusters until
a stopping criterion is achieved.
• Polythetic – divide the data based on the values by all
attributes
• Monothetic – divide the data on the basis of the
possession of a single specified attribute

74
 Polythetic Approach

• Distance
• Single Linkage
• Complete Linkage
• Group Average Linkage
• Centroid Linkage
• Median Linkage

75
 Polythetic Approach

1 2 3 4 5 6 7 D(1, *) = 26.0
1  0 
  D(2, *) = 22.5
2  10 0 
3 7 7 0 
  D(3, *) = 20.7
4  30 23 21 0 
5  29 25 22 7 0  D(4, *) = 17.3
 
6  38 34 31 10 11 0 
D(5, *) = 18.5
 
7  42 36 36 13 17 9 0 
D(6, *) = 20.7
A = {1 }

B = {2, 3, 4, 5, 6, 7} D(7, *) = 20.0

76
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 10
 0 
 
2  10 0  D(3, A) = 7
3 7 7 0 
 
4  30 23 21 0  D(4, A) = 30

5  29 25 22 7 0 
  D(5, A) = 29
6  38 34 31 10 11 0 
  D(6, A) = 38
7  42 36 36 13 17 9 0 

A = {1 } D(7, A) = 42

B = {2, 3, 4, 5, 6, 7}
77
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 10 D(2, B) = 25.0
 0 
 
2  10 0  D(3, A) = 7 D(3, B) = 23.4
3 7 7 0 
 
4  30 23 21 0  D(4, A) = 30 D(4, B) = 14.8

5  29 25 22 7 0 
  D(5, A) = 29 D(5, B) = 16.4
6  38 34 31 10 11 0 
  D(6, A) = 38 D(6, B) = 19.0
7  42 36 36 13 17 9 0 

A = {1 } D(7, A) = 42 D(7, B) = 22.2

B = {2, 3, 4, 5, 6, 7}
78
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 10 D(2, B) = 25.0 2 = 15.0
 0 
 
2  10 0  D(3, A) = 7 D(3, B) = 23.4 3 = 16.4
3 7 7 0 
 
4  30 23 21 0  D(4, A) = 30 D(4, B) = 14.8 4 = -15.2

5  29 25 22 7 0 
  D(5, A) = 29 D(5, B) = 16.4 5 = -12.6
6  38 34 31 10 11 0 
  D(6, A) = 38 D(6, B) = 19.0 6 = -19.0
7  42 36 36 13 17 9 0 

A = {1, 3 } D(7, A) = 42 D(7, B) = 22.2 7 = -19.8

B = {2, 3, 4, 5, 6, 7}
79
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 10 D(2, B) = 25.0 2 = 15.0
 0 
 
2  10 0  D(3, A) = 7 D(3, B) = 23.4 3 = 16.4
3 7 7 0 
 
4  30 23 21 0  D(4, A) = 30 D(4, B) = 14.8 4 = -15.2

5  29 25 22 7 0 
  D(5, A) = 29 D(5, B) = 16.4 5 = -12.6
6  38 34 31 10 11 0 
  D(6, A) = 38 D(6, B) = 19.0 6 = -19.0
7  42 36 36 13 17 9 0 

A = {1, 3 } D(7, A) = 42 D(7, B) = 22.2 7 = -19.8

B = {2, 3, 4, 5, 6, 7}
80
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 8.5
 0 
 
2  10 0  D(4, A) = 25.5
3 7 7 0 
 
4  30 23 21 0  D(5, A) = 25.5

5  29 25 22 7 0 
  D(6, A) = 34.5
6  38 34 31 10 11 0 
 
7  42 36 36 13 17 9 0  D(7, A) = 39.0

A = {1, 3 }

B = {2, 4, 5, 6, 7}
81
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 8.5 D(2, B) = 29.5
 0 
 
2  10 0  D(4, A) = 25.5 D(4, B) = 13.2
3 7 7 0 
 
4  30 23 21 0  D(5, A) = 25.5 D(5, B) = 15.0

5  29 25 22 7 0 
  D(6, A) = 34.5 D(6, B) = 16.0
6  38 34 31 10 11 0 
 
7  42 36 36 13 17 9 0  D(7, A) = 39.0 D(7, B) = 18.9

A = {1, 3 }

B = {2, 4, 5, 6, 7}
82
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 8.5 D(2, B) = 29.5 2 = 21.0
 0 
 
2  10 0  D(4, A) = 25.5 D(4, B) = 13.2 4 = -12.3
3 7 7 0 
 
4  30 23 21 0  D(5, A) = 25.5 D(5, B) = 15.0 5 = -10.5

5  29 25 22 7 0 
  D(6, A) = 34.5 D(6, B) = 16.0 6 = -18.5
6  38 34 31 10 11 0 
 
7  42 36 36 13 17 9 0  D(7, A) = 39.0 D(7, B) = 18.9 7 = -20.3

A = {1, 3 , 2 }

B = {2, 4, 5, 6, 7}
83
 Polythetic Approach

1 2 3 4 5 6 7
1 D(2, A) = 8.5 D(2, B) = 29.5 2 = 21.0
 0 
 
2  10 0  D(4, A) = 25.5 D(4, B) = 13.2 4 = -12.3
3 7 7 0 
 
4  30 23 21 0  D(5, A) = 25.5 D(5, B) = 15.0 5 = -10.5

5  29 25 22 7 0 
  D(6, A) = 34.5 D(6, B) = 16.0 6 = -18.5
6  38 34 31 10 11 0 
 
7  42 36 36 13 17 9 0  D(7, A) = 39.0 D(7, B) = 18.9 7 = -20.3

A = {1, 3 , 2 }

B = {2, 4, 5, 6, 7}
84
 Polythetic Approach

1 2 3 4 5 6 7
1  0 
  D(4, A) = 24.7
2  10 0 
3 7 7 0  D(5, A) = 25.3
 
4  30 23 21 0 
 29  D(6, A) = 34.3
5 25 22 7 0
 
6  38 34 31 10 11 0  D(7, A) = 38.0
 
7  42 36 36 13 17 9 0 

A = {1, 3 , 2 }

B = {4, 5, 6, 7}
85
 Polythetic Approach

1 2 3 4 5 6 7
1  0 
  D(4, A) = 24.7 D(4, B) = 10.0
2  10 0 
3 7 7 0  D(5, A) = 25.3 D(5, B) = 11.7
 
4  30 23 21 0 
 29  D(6, A) = 34.3 D(6, B) = 10.0
5 25 22 7 0
 
6  38 34 31 10 11 0  D(7, A) = 38.0 D(7, B) = 13.0
 
7  42 36 36 13 17 9 0 

A = {1, 3 , 2 }

B = {4, 5, 6, 7}
86
 Polythetic Approach

1 2 3 4 5 6 7
1  0 
  D(4, A) = 24.7 D(4, B) = 10.0 4 = -14.7
2  10 0 
3 7 7 0  D(5, A) = 25.3 D(5, B) = 11.7 5 = -13.6
 
4  30 23 21 0 
 29  D(6, A) = 34.3 D(6, B) = 10.0 6 = -24.3
5 25 22 7 0
 
6  38 34 31 10 11 0  D(7, A) = 38.0 D(7, B) = 13.0 7 = -25.0
 
7  42 36 36 13 17 9 0 

A = {1, 3 , 2 } All differences are

negative. The process
B = {4, 5, 6, 7} would continue on each
subgroup separately. 87
 Monothetic

It is usually used when the data consists

of binary variables.

A B C
1 0 1 1
2 1 1 0
3 1 1 1
4 1 1 0
5 0 0 1
88
 Monothetic

A
It is usually used when the data consists
B 1 0
of binary variables. 1 a=3 b=1
A B C 0 c=0 d=1
1 0 1 1 Chi-Square Measure

2 1 1 0 (ad  bc) 2 N
3 1 1 1  AB 2 
(a  b)(a  c)(b  d )(c  d )
4 1 1 0 
(3  0) 2 5
4 3 2 1
5 0 0 1
= 1.875
89
 A
B 1 0
Monothetic
1 a=3 b=1
0 c=0 d=1
Chi-Square Measure
It is usually used when the data consists
of binary variables.

A B C
1 0 1 1
2 1 1 0 (ad  bc) 2 N
3 1 1 1  AB 2 
(a  b)(a  c)(b  d )(c  d )
4 1 1 0 
(3  0) 2 5
4 3 2 1
5 0 0 1
= 1.875
90
 A
B 1 0 Attr AB
Monothetic
1 a=3 b=1 .
0 c=0 d=1 a 3
Chi-Square Measure b 1
It is usually used when the data consists c 0
of binary variables.
d 1
A B C N2 5
1 0 1 1 1.8
2 1 1 0 7  bc) 2 N
(ad
3 1 1 1  AB 2 
(a  b)(a  c)(b  d )(c  d )
4 1 1 0 
(3  0) 2 5
4 3 2 1
5 0 0 1
= 1.875
91
 A
B 1 0 Attr AB AC BC
1 Monothetic
a=3 b=1 .
0 c=0 d=1 a 3 1 2
Chi-Square Measure b 1 2 1
It is usually used when the data consists c 0 2 2
of binary variables.
d 1 0 0
A B C N2 5 5 5
1 0 1 1 1.8 2.2 0.8
For attribute A,
2 1 1 0 2
 AB   AC 2
7 2 3
= 4.09
3 1 1 1 For attribute B,
2 2
4 1 1 0  AB   BC = 2.70
For attribute C,
5 0 0 1  AC 2   BC 2 = 3.05
92
 A
B 1 0 Attr AB AC BC
1 Monothetic
a=3 b=1 .
0 c=0 d=1 a 3 1 2
Chi-Square Measure b 1 2
We choose attribute A for
1
It is usually used when the data consists c
dividing 0
the data2into two2
of binary variables. groups.
d 1and {1,05} 0
{2, 3, 4},
A B C
N2 5 5 5
1 0 1 1 1.8 2.2 0.8
For attribute A,
2 1 1 0 2 2
 AB   AC = 4.09 7 2 3
3 1 1 1 For attribute B,
2 2
4 1 1 0  AB   BC = 2.70
For attribute C,
5 0 0 1  AC 2   BC 2 = 3.05
93
Other Clustering
Techniques
What we learnt

• K-mean
• Dendrogram
Why Clustering?

• Clustering for Understanding

• Applications
• Biology
• Group different species
• Information Retrieval
• Group webpages
• E.g., “movie”  reviews, trailers, stars and theaters
• Psychology and Medicine
• Group medicine
• Business
• Group different customers for marketing
• Network
• Group different types of traffic patterns
• Software
• Group different programs for data analysis
Other Clustering Models

•Model-Based Clustering
•EM Algorithm
•Density-Based Clustering
•DBSCAN
•Scalable Clustering Method
•BIRCH
EM Algorithm

• Drawback of the K-means/Dendrogram

• Each point belongs to a single cluster
• There is no representation that a point can belong to different clusters with
different probabilities
• Use probability density to associate to each point
EM Algorithm

• Assume that we know there are k clusters

• Each cluster follows a distribution (e.g., Gaussian
Distribution)
• 1D Gaussian Distribution
• Mean 
• Standard derivation 

( x  )2
1 
2 2
p(x| <, >) e
= 2 
EM Algorithm

• Since there are k clusters, we have k distributions.

• Cluster 1
• Gaussian Distribution
• Mean 1
• Standard derivation 1
• Cluster 2
• Gaussian Distribution
• Mean 2
• Standard derivation 2
•…
• Cluster k
• Gaussian Distribution
• Mean k
• Standard derivation k
EM Algorithm

• EM Algorithm
• Expectation-Maximization
• Algorithm
• Step 1 (Parameter Initialization)
• Initialize all i and i One possible
• Step 2 (Expectation) implementation:
p(x|<i, i>)
• For each point x,
• For each cluster i, p(xCi) =jp(x|<j, j>)
• Calculate the probability that x belongs cluster i
• Step 3 (Maximization)
• For each cluster i,
• Calculate the mean i according to the probabilities that all points belongs to
cluster I
• Repeat Step 2 and Step 3
until the parameters converge
One possible
implementation:

.
Other Clustering Models

•Model-Based Clustering
•EM Algorithm
•Density-Based Clustering
•DBSCAN
•Scalable Clustering Method
•BIRCH
DBSCAN

• Traditional Clustering
• Can only represent sphere clusters
• Cannot handle irregular shaped clusters
• DBSCAN
• Density-Based Spatial Clustering of Applications with Noise
DBSCAN

• DBSCAN is a density-based algorithm.

• Density = number of points within a specified radius (Eps)

• A point is a core point if it has more than a specified number of

points (MinPts) within Eps
• These are points that are at the interior of a cluster

• A border point has fewer than MinPts within Eps, but is in the
neighborhood of a core point

• A noise point is any point that is not a core point or a border

point.
 c d
b
DBSCAN a
e

• According to -neighborhood of point p, we

classify all points into three types
• core points Given a point p and a non-negative
integer MinPts, if the size of N(p) is
at least MinPts, then p is said to be
• border points a core point.

Given a point p, p is said to be a

border point if it is not a core point
• noise points but N(p) contains at least one core
point.
Given a point p, p is said to be a
noise point if it is neither a core
point nor a border point.
 c d
b
DBSCAN a
e

• Principle 1: Each cluster contains at least one core point.

• Principle 2: Given any two core points p and q, if N(p) contains q
(or N(q) contains p), then p and q are in the same cluster.
• Principle 3: Consider a border point p to be assigned to one of
the clusters formed by Principle 1 and Principle 2. Suppose N(p)
contains multiple core points. A border point p is assigned
arbitrarily to one of the clusters containing these core points
(formed by Principle 1 and Principle 2).
• Principle 4: All noise points do not belong to any clusters.
DBSCAN: Core, Border, and Noise Points
 DBSCAN Algorithm
• Eliminate noise points
• Perform clustering on the remaining points
DBSCAN: Core, Border and Noise Points

Original Points Point types: core,

border and noise

Eps = 10, MinPts = 4

When DBSCAN Works Well

Original Points Clusters

• Resistant to Noise
• Can handle clusters of different shapes and sizes
When DBSCAN Does NOT Work Well

(MinPts=4, Eps=9.75).

Original Points

• Varying densities
• High-dimensional data
(MinPts=4, Eps=9.92)
DBSCAN: Determining EPS and MinPts

• Idea is that for points in a cluster, their kth nearest

neighbors are at roughly the same distance
• Noise points have the kth nearest neighbor at farther
distance
• So, plot sorted distance of every point to its kth nearest
neighbor
 c d
b
DBSCAN a
e

• Given a point p and a non-negative real number ,

• the -neighborhood of point p, denoted by N(p), is the set of points q (including
point p itself) such that the distance between p and q is within .
Other Clustering Models

•Model-Based Clustering
•EM Algorithm
•Density-Based Clustering
•DBSCAN
•Scalable Clustering Method
•BIRCH
BIRCH

• Disadvantage of Previous Algorithms

• Most previous algorithms cannot handle update
• Most previous algorithms are not scalable
• BIRCH
• Balanced Iterative Reducing and Clustering Using Hierarchies
BIRCH

• Advantages
• Incremental
• Scalable
BIRCH

• Each cluster has the following three

terms. n

• Mean  x i
 i 1

n
Average distance from
n
member objects to the
 (x  ) 2

• Radius R i 1
i
mean
n

n n

  (x  x ) 2

• Diameter D
i 1 j 1
i j

n(n  1)
Average pairwise
distance within a
cluster
BIRCH

• L is to store a list of clusters

• Idea of the Algorithm
• L  {}
• When there is a new data point x
• If L = {}
• Create cluster C containing x only
• Insert C into L
• Else
• Find the closest cluster C from x
• Insert x into C
• If C has diameter D greater than a given threshold,
• Split cluster C into two sub-clusters C1 and C2
• Remove C from L
• Insert C1 and C2 into L