Clustering

•Cluster: a collection of data objects

• Similar to one another within the same cluster
• Dissimilar to the objects in other clusters
•Cluster analysis
• Natural grouping a set of data objects into
clusters
•Clustering is unsupervised classification: no
predefined classes /class label
What Is Good Clustering?

• High intra-class similarity &

Low inter-class similarity
• Appropriateness of
method for dataset, The
(dis)similarity measure
used & its implementation.
• Ability to discover some or
all of the hidden patterns.
Applications of Clustering Algorithm
• Pattern Recognition
• Spatial Data Analysis, like create thematic maps in GIS
by clustering feature spaces
• Image Processing
• Business applications, like customer segmentation etc.
• Web applications like, Document classification, Cluster
Weblog data to discover groups of similar access
patterns
Data Structures
Data matrix Dissimilarity matrix
𝑥11 . . . 𝑥1𝑓 ... 𝑥1𝑝 0
... ... ... ... ... 𝑑(2,1) 0
𝑥𝑖1 . . . 𝑥𝑖𝑓 ... 𝑥𝑖𝑝
𝑑(3,1) 𝑑(3,2) 0
... ... ... ... ...
: : :
𝑥𝑛1 . . . 𝑥𝑛𝑓 ... 𝑥𝑛𝑝
𝑑(𝑛, 1) 𝑑(𝑛, 2) . . . ... 0
Nominal (categorical)
• A generalization of the binary variable in that it can take
more than 2 states, e.g., red, yellow, blue, green
• Method: Simple matching
• m: # of matches, p: total # of variables

𝑝−𝑚
𝑑(𝑖, 𝑗) =
𝑝
Ordinal (numerical)
• An ordinal variable can be discrete or continuous
• order is important, e.g., rank 𝑟𝑖𝑓 ∈ {1, . . . , 𝑀𝑓 }
• map the range of each variable onto [0, 1] by replacing i-th
object in the f-th variable by
𝑟𝑖𝑓 − 1
𝑧𝑖𝑓 =
𝑀𝑓 − 1

• compute the dissimilarity using methods for interval-scaled

variables
 Binary Variables
• A contingency table for binary data
• Simple matching coefficient
(invariant, if the binary variable is
symmetric):
• Jaccard coefficient (noninvariant if
the binary variable is asymmetric):
In cases where the two binary 𝑏+𝑐
𝑆𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐: 𝑑(𝑖, 𝑗) =
states are not equally important, 𝑎+𝑏+𝑐+𝑑
such as in the asymmetric type of
binary data, the positive matches
𝑏+𝑐
are usually more significant than 𝐴𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐: 𝑑(𝑖, 𝑗) =
𝑎+𝑏+𝑐
the negative matches
Dissimilarity between Binary Variables
Name Fever Cough Test-1 Test-2 Test-3 Test-4
Example
Jack Y N P N N N
• the attributes Mary Y N P N P N
Jim Y P N N N N
are asymmetric
binary 0+1
𝑑(𝑗𝑎𝑐𝑘, 𝑚𝑎𝑟𝑦) = = 0.33
• let the values Y 2+0+1
and P be set to 1+1
1, and the value 𝑑(𝑗𝑎𝑐𝑘, 𝑗𝑖𝑚) = = 0.67
1+1+1
N be set to 0
1+2
𝑑(𝑗𝑖𝑚, 𝑚𝑎𝑟𝑦) = = 0.75
1+1+2
Example: Calculating the values of a similarity coefficient,
Suppose five individuals possess the following characteristics
• The scores for individuals 1 and 2 on the p = 6 binary variables are

• and the number of matches and mismatches are indicated in the

two-way array
• Employing similarity Note: Similarity
coefficient 1, which gives is computed
equal weight to matches, here instead of
dissimilarity

• Calculate the remaining

similarity for pairs of
individuals
• Based on the magnitudes
of the similarity
coefficient, individuals 2
and 5 are most similar
and individuals 1 and 5
are least similar.
Similarity and Dissimilarity Between Objects

• Distances are normally used to measure the similarity or dissimilarity between two
data objects (Generally Standardized or Normalized before computing distances)
• Some popular ones include: Minkowski distance:
𝑞
𝑑(𝑖, 𝑗) = (|𝑥𝑖1 − 𝑥𝑗1 |𝑞 + |𝑥𝑖2 − 𝑥𝑗2 |𝑞 +. . . +|𝑥𝑖𝑝 − 𝑥𝑗𝑝 |𝑞 )

where i = (xi1, xi2, …, xip) and j = (xj1, xj2, …, xjp) are two p-dimensional data objects,
and q is a positive integer
• If q = 1, d is Manhattan distance

𝑑(𝑖, 𝑗) = |𝑥𝑖1 − 𝑥𝑗1 | + |𝑥𝑖2 − 𝑥𝑗2 |+. . . +|𝑥𝑖𝑝 − 𝑥𝑗𝑝 |

• If q = 2, d is Euclidean distance:

𝑑(𝑖, 𝑗) = (|𝑥𝑖1 − 𝑥𝑗1 |2 + |𝑥𝑖2 − 𝑥𝑗2 |2 +. . . +|𝑥𝑖𝑝 − 𝑥𝑗𝑝 |2 )

• Properties
• d(i,j)  0
• d(i,i) = 0
• d(i,j) = d(j,i)
• d(i,j)  d(i,k) + d(k,j)

• Also one can use weighted distance, parametric Pearson

product moment correlation, or other similarity measures.
Variables of Mixed Types
• A database may contain mixed types of variables
• One may use a weighted formula to combine their effects.
• f is binary: dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise
• f is interval-based: may use the normalized distance
• f is ordinal: Compute zif from ranks rif and treat as
interval-scaled
Example: Measuring the similarities of 11 languages
The meanings of words change with the course of history.
However, the meaning of the numbers represents one noticeable
exception. Thus, a first comparison of languages might be based
on the numerals alone. Table gives the first 10 numbers in English,
Polish, Hungarian, and eight other modern European languages.
(Only languages that use the Roman alphabet are considered, and
accent marks, cedillas, diereses, etc., are omitted.)
For illustrative purposes, compare languages by looking at the first
letters of the numbers. Two different languages are concordant if
they have the same first letter and discordant if they do not.
 Table suggests that
• First five
languages
(English,
Norwegian,
Danish, Dutch,
and German) are
very much alike.
• French, Spanish,
and Italian are in
closer agreement.
• Hungarian and
• Polish has some of the characteristics of the
Finnish seem to
languages in each of the larger subgroups. be closer.
Hierarchical Clustering
Use distance matrix as clustering criteria. This method does not require the
number of clusters k as an input, but needs a termination condition
Step 0 Step 1 Step 2 Step 3 Step 4
Agglomerative nesting
(AGNES)
a
ab
b
abcde
c
cde
d
de
e
Divisive analysis
Step 4 Step 3 Step 2 Step 1 Step 0 (DIANA)
AGNES (Agglomerative Nesting)
• Introduced in Kaufmann and Rousseeuw (1990)
• Merge nodes that have the least dissimilarity
• Go on in a non-descending fashion
• Eventually all nodes belong to the same cluster
10 10 10

9 9 9

8 8 8

7 7 7

6 6 6

5 5 5

4 4 4

3 3 3

2 2 2

1 1 1

0 0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
Distances between clusters
• Single. Single linkage defines the distance between two objects
or clusters as the distance between the two closest members of
those clusters.
Complete. Complete linkage uses the most distant pair of objects
in two clusters to compute between-cluster distances.

Average. Average linkage averages all distances between pairs of

objects in different clusters to decide how far apart they are.
• Median. Median linkage uses the median distances between pairs
of objects in different clusters to decide how far apart they are.
• Centroid. Centroid linkage uses the average value of all objects in
a cluster (the cluster centroid) as the reference point for distances
to other objects or clusters.
• Ward. Ward's method averages all distances between pairs of
objects in different clusters, with adjustments for covariances, to
decide how far apart the clusters are.
• Weighted. Weighted average linkage uses a weighted average
distance between pairs of objects in different clusters to decide
how far apart they are. The weights used are proportional to the
size of the cluster.
Agglomerative hierarchical clustering algorithm for grouping N objects
Dendrogram
 Graphical representation to show how the Clusters
are merged hierarchically
 A clustering of the data objects is obtained by cutting
the dendrogram at the desired level, then each
connected component forms a cluster.
A Dendrogram
Construct a Dendrogram with the following distance matrix using
(i) Single linkage method
(ii) Complete linkage method
import pandas as pd
df= pd.read_csv("E:/MY DOCUMENTS/Desktop/Python/[Link]")
y = df
[Link](['SL','Companies'], axis=1,inplace=True)
print("Dimension of the data set is : ", [Link])

#Perform Clustering
from [Link] import AgglomerativeClustering
agg=AgglomerativeClustering(n_clusters=5)
ypred=agg.fit_predict(df)
x=agg.labels_
print(x)

#Creating dendrogram
import [Link] as plt
from [Link] import dendrogram, ward
result=ward(df)
dendrogram(result)
[Link]("DENDROGRAM")
[Link]('Observations')
[Link]('Distances')
[Link]()