Usha A Kumar, IIT Bombay

CLUSTER ANALYSIS
CLUSTER ANALYSIS
 Cluster analysis is a set of tools for building
clusters from multivariate data objects.

Usha A Kumar, IIT Bombay

 Cluster analysis involves categorization: dividing
a large group of observations into smaller groups
so that the observations within each group are
relatively similar (i.e they possess largely the
same characteristics) and the observations in
different groups are relatively dissimilar.
 For (e.g), if p different types of tests are used to
group scores of individuals into different clusters,
people with high verbal ability might tend to

Usha A Kumar, IIT Bombay

cluster into one group while people with high
abstract reasoning ability or with high artistic
ability might tend to cluster into other groups.
 How close should test scores be before people are
grouped into the same cluster is the question of
degree of homogeneity desired, and how many
clusters there ought to be is the question of the
degree of heterogeneity desired.
APPLICATIONS
 Market Segmentation
It is difficult to design products or plan

Usha A Kumar, IIT Bombay

marketing campaigns when the individuals in
the target market differ with respect to their
needs and their response behaviours. Marketers
try to solve this problem by segmenting the
market – that is, dividing the market into
smaller groups that are more homogeneous and
therefore more easily served by a particular type
of product or a particular promotional campaign.
APPLICATIONS
 An insurance company might be interested in the
distinction among classes of potential customers
so that it can derive optimal prices for its

Usha A Kumar, IIT Bombay

services.
 Various companies could be classified according
to their organizational structures, technologies
and types.
 In Psychology, it is used to find types of
personalities on the basis of questionnaires.
 In Archaeology, it is used to classify art objects in
different time periods.
THE FUNDAMENTAL STEPS:
 Choice of a Similarity measure:
Each pair of observation is checked for the
similarity of their values. A similarity measure is

Usha A Kumar, IIT Bombay

defined to measure the “closeness” of the objects.
The “closer” they are, the more homogeneous
they are.

 Choice of group-building algorithm:

On the basis of the similarity measures the
objects are assigned to groups so that differences
between groups become large and observations in
a group become as close as possible.
SIMILARITY MEASURES
 The nature of the observations plays an
important role in the choice of proximity
measure.

Usha A Kumar, IIT Bombay

➢ Nominal values in general lead to similarity
measure.
➢ Metric values lead to distance measure.
BINARY VARIABLES

Usha A Kumar, IIT Bombay

Item k Totals
1 0
Item i 1 a b a+b
0 c d c+d
Totals a+c b+d p=a+b+c+d
SIMILARITY COEFFICIENTS
 (a+d)/p
 2(a+d)/(2(a+d)+b+c)

Usha A Kumar, IIT Bombay

 a/p

 a/(a+b+c)

 a/(b+c)
DISTANCE MEASURE

 The Euclidean distance dij between two

cases i and j with variable values

Usha A Kumar, IIT Bombay

( x1i , x2i ,...x pi ) ( x1 j , x2 j ,...x pj )

dij = ( x1i − x1 j )2 + ( x2i − x2 j )2 + ... + ( x pi − x pj ) 2

CLUSTERING ALGORITHMS
 Hierarchical Algorithms
 Non Hierarchical or Partitioning algorithms.

Usha A Kumar, IIT Bombay

HIERARCHICAL ALGORITHMS
 Agglomerative technique
This starts with each cluster comprising exactly
one object and then progressively agglomerating

Usha A Kumar, IIT Bombay

(combining) the two nearest clusters according to
their similarities until there is just one cluster
left consisting of all the objects.

 Divisive technique
This starts with all the objects in one cluster and
divides and sub-divides them until all objects are
in their own single-object cluster.
DENDROGRAM
A graphical representation of the
sequence of clustering is called a
dendrogram.

Usha A Kumar, IIT Bombay

 It displays the observations, the sequence
of clusters and the distances between the
clusters. The horizontal axis displays the
indices of the points, whereas the vertical
axis gives the distance between the
clusters. Large distances indicate the
clustering of heterogeneous groups. Thus,
if we choose to “cut the tree” at a desired
level, the branches describe the
corresponding clusters.
AGGLOMERATIVE ALGORITHM
 Start with the finest partition (no. of
clusters = no. of observations)

Usha A Kumar, IIT Bombay

 Compute the distance matrix D.

 Do
❖ Find the two clusters with the closest distance.
❖ Put those two clusters into one cluster.
❖ Compute the distance between the new groups
and obtain a reduced distance matrix D.
UNTIL all clusters are agglomerated.
 Usha A Kumar, IIT Bombay
LINKAGE METHODS
 Usha A Kumar, IIT Bombay
ILLUSTRATION
SINGLE LINKAGE
⚫ The inputs to a single linkage algorithm can be
distances or similarities between pairs of objects.
Groups are formed from the individual entities by

Usha A Kumar, IIT Bombay

merging nearest neighbors, where the term nearest
neighbor means the smallest distance or largest
similarity.
Initially, we must find the smallest distance in
D = {dik} and merge the corresponding
objects, say, U and V, to get the cluster ( UV))
SINGLE LINKAGE

 The distances between ( UV) and any other

cluster W are computed by

Usha A Kumar, IIT Bombay

dUV (W ) = min dUW , dVW 

Here the quantities duw and dvw are the

distances between the nearest neighbors of
clusters U and W and clusters V and W,
respectively.
COMMENTS
 Since single linkage joins clusters by the
shortest link between them, the technique

Usha A Kumar, IIT Bombay

cannot discern poorly separated cluster.
 On the other hand, single linkage is one of
the few clustering methods that can delineate
nonellipsoidal clusters.
 The tendency of single linkage to pick out
long string like cluster is known as chaining.
 Chaining can be misleading if items at
opposite ends of the chain are, in fact, quite
dissimilar.
COMPLETE LINKAGE

 At each stage, the distance (similarity)

between clusters is determined by the
distance (similarity) between the two

Usha A Kumar, IIT Bombay

elements, one from each cluster, that are
most distant. Thus, complete linkage
ensures that all items in a cluster are
within some maximum distance (or
minimum similarity) of each other.
 The general agglomerative algorithm
again starts by finding the minimum
entry in D = {dik} and merging the
corresponding objects such as U and V, to
get cluster (UV).
COMPLETE LINKAGE

 The distances between (UV) and any

other cluster W are computed by
d(UV)W = Max {dU,W , dv,w }

Usha A Kumar, IIT Bombay

 Here dUW and dvw are the distances
between the most distant members of
clusters U and W and clusters V and
W, respectively.
AVERAGE LINKAGE

•Average linkage treats the distance between

two clusters as the average distance between all
pairs of items where one member of a pair

Usha A Kumar, IIT Bombay

belongs to each cluster.

•We begin by searching the distance matrix

D = {dik} to find the nearest objects for example,
U and V. These objects are merged to form the
cluster (UV).
AVERAGE LINKAGE

▪ Distances between ( UV) and the other cluster W

are determined by

Usha A Kumar, IIT Bombay

 d ik
dUV (W ) = i k

N (UV ) NW

where dik is the distance between object i in the cluster

(UV) and object k in the cluster W, and N(uv) and Nw are
the number of items in clusters (UV) and W, respectively.
NUMERALS IN ELEVEN LANGUAGES

Usha A Kumar, IIT Bombay

MEASURING THE SIMILARITY
 We might compare languages by looking at the
first letters of the numbers.

Usha A Kumar, IIT Bombay

 If the first letters are the same in two different
languages for the same number, they are said to
be concordant and discordant, otherwise.
 This way, we compute the frequencies of
matching first letter and create the similarity
matrix.
SIMILARITY MATRIX
 Concordant First Letters for Numbers

Usha A Kumar, IIT Bombay

DISTANCE MATRIX
 To create the distance matrix, we subtract the
concordances from the perfect agreement figure
of 10 that each language has with itself.

Usha A Kumar, IIT Bombay

SINGLE LINKAGE DENDROGRAM

Usha A Kumar, IIT Bombay

COMPLETE LINKAGE DENDROGRAM

Usha A Kumar, IIT Bombay

AVERAGE LINKAGE DENDROGRAM

Usha A Kumar, IIT Bombay

OBSERVATIONS
 Comparing single linkage and complete linkage
dendrograms, both the methods result in
English-Norwegian- Danish and the French-

Usha A Kumar, IIT Bombay

Italian-Spanish groups. Also both methods merge
Hungarian and Finnish only at the penultimate
stage. However, the two methods handle German
and Dutch differently.
 The average linkage results in groups very
similar to single linkage method though the
mergers take place at different levels.
WARD'S HIERARCHICAL
CLUSTERING METHOD
 Rather than joining two closest clusters in
terms of distance relation, this method seeks

Usha A Kumar, IIT Bombay

to join the two clusters whose merger leads to
the smallest within- cluster sum of squares.
(i.e minimum Error sum of squares ESS).
 First, for a given cluster k, let ESSk be the sum
of the squared deviations of every item in the
cluster from the cluster mean (centroid).
WARD'S HIERARCHICAL
CLUSTERING METHOD
CTND…

 Ifthere are currently K clusters, define ESS as

ESS = ESS1 + ESS2 + ... + ESSK.
 At each step in the analysis, the union of every

Usha A Kumar, IIT Bombay

possible pair of clusters is considered, and the
two clusters whose combination results in the
smallest increase in ESS are joined.
 Initially, each cluster consists of a single item,
and, if there are N items, ESSk = 0, k = 1,2,..., N,
so ESS = 0.
 The results of Ward's method can be displayed as
a dendrogram. The vertical axis gives the values
of ESS at which the mergers occur. (SAS provides

Usha A Kumar, IIT Bombay

semi partial R2 on the vertical axis – the decrease in the
proportion accounted by joining the two clusters)
 Ward's method is based on the notion that the
clusters of multivariate observations are expected
to be roughly elliptically shaped.
 It is a hierarchical precursor to nonhierarchical
clustering methods that optimize some criterion
for dividing data into a given number of elliptical
groups.
FINAL COMMENTS -
HIERARCHICAL PROCEDURES
 Agglomerative hierarchical clustering procedures are
sensitive to outliers.
 In hierarchical clustering, there is no provision for a

Usha A Kumar, IIT Bombay

reallocation of objects that may have been "incorrectly"
grouped at an early stage. Consequently, the final
configuration of clusters should always be carefully
examined to see whether it is sensible.
 For a particular problem, it is a good idea to try several
clustering methods and, within a given method, a
couple of different ways of assigning distances
(similarities).
FINAL COMMENTS -
HIERARCHICAL PROCEDURES
CTND…

 If the outcomes from the several methods are

consistent with one another, perhaps a natural
grouping exists.

Usha A Kumar, IIT Bombay

 The stability of a hierarchical solution can sometimes
be checked by applying the clustering algorithm before
and after small errors (perturbations) have been added
to the data units. If the groups are fairly well
distinguished, the clusterings before perturbation and
after perturbation should agree.
 NONHIERARCHICAL CLUSTERING
METHODS
 Nonhierarchical clustering techniques are designed to
group items into a collection of K clusters.
 The number of clusters, K, may either be specified in
advance or determined as part of the clustering

Usha A Kumar, IIT Bombay

procedure.
 Because a matrix of distances (similarities) does not
have to be determined, and the basic data do not have to
be stored during the computer run, nonhierarchical
methods can be applied to much larger data sets than
can hierarchical techniques.
 Nonhierarchical methods start from either (a) an initial
partition of items into groups or (b) an initial set of seed
points, which will form the nuclei of cluster.
K-MEANS METHOD
This method assigns each item to the cluster having
the nearest centroid (mean). The steps are:

1. Partition the items into K initial clusters.

Usha A Kumar, IIT Bombay

2. Proceed through the list of items, assigning an item to
the cluster whose centroid (mean) is nearest. (Distance
is usually computed using Euclidean distance with
either standardized or unstandardized observations.)
Recalculate the centroid for the cluster receiving the
new item and for the cluster losing the item.
3. Repeat Step 2 until no more reassignments take place.
CLUSTERING USING THE K-MEANS
METHOD
 Suppose we measure two variables X1 and X2 for
each of four items A, B, C, and D. The data are
given in the following table:

Usha A Kumar, IIT Bombay

K MEANS METHOD
 For K=2, the objective is to divide these items
into 2 clusters. For this, we arbitrarily partition
the items into two clusters, say, (AB) and (CD).

Usha A Kumar, IIT Bombay

Cluster Coordinates of
centroid
(AB) (2,2)
(CD) (-1,-2)

 We compute the Euclidean distance of each item

from the group centroids.
Cluster Squared distance
A B C D
(AB) 10 10 17 41
(CD) 61 9 4 4
K MEANS METHOD
 As B’s distance to its own mean is larger than the
opposite cluster, it is assigned to the opposite
cluster, resulting in the new partition (A) and

Usha A Kumar, IIT Bombay

(BCD).
Cluster Coordinates of
centroid
(A) (5,3)
(BCD) (-1,-1)

 We compute the Euclidean distance of each item

from the new group centroids.
Cluster Squared distance
A B C D
(A) 0 40 41 89
(BCD) 52 4 5 5
 We observe that each individual is closer to its
own cluster mean and hence no more
reassignments take place and the final clusters

Usha A Kumar, IIT Bombay

are (A) and (BCD).
 If not, iteration continues until no more
reassignments take place.
K-MEANS METHOD CTND…

The final assignment of items to clusters will be, to

some extent, dependent upon the initial partition or the

Usha A Kumar, IIT Bombay

initial selection of seed points.

Selecting the Initial Partition

 One approach is to use K observations from the data as
“seeds” and assign each remaining observation to the
closest “seed”. The seeds can be chosen randomly. Or
the analyst may specify his own set of cluster seeds.
 Another starting point is to use the centroids from an
agglomerative clustering solution such as Ward’s
method or average linkage.
INTERPRETING THE SOLUTION
 Examine the cluster centroids, calculating the mean
value of each variable across the objects assigned to
each cluster. This reveals which clusters are

Usha A Kumar, IIT Bombay

relatively high on some variables and low on others.
 Also examine some measure of the variance in X
accounted for by the clustering solution.
 As a summary measure, we can look either at the
ratio of the between cluster sum of squares to the
total sum of squares (analogous to R 2 ), or the ratio of
the between cluster sum of squares to the within
cluster sum of squares ( R 2 /1 − R 2 ).
 Comparing these values across variables makes it
clear which variables are most important in defining
the differences among clusters.
 ILLUSTRATION
 Data on breakfast cereals produced by three
different American Manufacturers: General Mills
(G), Kellogg (K) and Quaker (Q) is provided.

Usha A Kumar, IIT Bombay

❖ Calculate the Euclidean distances between pairs of
cereal brands.
❖ Cluster the cereals using K means approach.

 Sample data:
Sr Brand Mftr Calories Protein Fat Sodium Fiber Carboh Sugar Potassium Group
ydrates
1 Apple G 110 2 2 180 1.5 10.5 10 70 1
2 Cheerios G 110 6 2 290 2.0 17.0 1 105 1
.
.
.
43 Quaker oatmeal Q 100 5 2 0 2.7 1.0 1 110 3