CHAPTER 4

CLUSTERING
Introduction:
• Clustering is an unsupervised Machine Learning-based Algorithm that comprises a
group of data points into clusters so that the objects belong to the same group.

• Clustering helps to splits data into several subsets. Each of these subsets contains data
similar to each other, and these subsets are called clusters.

• Now that the data from our customer base is divided into clusters, we can make an
informed decision about who we think is best suited for this product.
[Link] Example
Let's understand this with an example, suppose we are a market manager, and we have a
new tempting product to sell. We are sure that the product would bring enormous profit,
as long as it is sold to the right people. So, how can we tell who is best suited for the
product from our company's huge customer base? So here is where clustering plays an
important role.
Cluster
• Cluster is a group of objects that belongs to the same class. In other words, similar objects
are grouped in one cluster and dissimilar objects are grouped in another cluster.
• Dissimilarities and similarities are assessed based on the attribute values describing the
objects and often involve distance measures.

Cluster Analysis :
• Cluster Analysis in data mining means that to find out the group of objects which are
similar to each other in the group but are different from the object in other groups.
• A good clustering algorithm aims to obtain clusters whose:
(a) The intra-cluster similarities are high. It implies that the data present inside the cluster is
similar to one another.
(b) The inter-cluster similarity is low. It means each cluster holds data that is not similar to
other data.
Applications:

• In many applications, clustering analysis is widely used, such as

data analysis, market research, pattern recognition, and image
processing.
• It assists marketers to find different groups in their client base and
based on the purchasing patterns. They can characterize their
customer groups.
• It helps in allocating documents on the internet for data discovery.
• Clustering is also used in tracking applications such as detection of
credit card fraud.
• As a data mining function, cluster analysis serves as a tool to gain
insight into the distribution of data to analyze the characteristics of
each cluster.
• In terms of biology, it can be used to determine plant and animal
taxonomies, categorization of genes with the same functionalities
and gain insight into structure inherent to populations.
• It helps in the identification of areas of similar land that are used
in an earth observation database and the identification of house
groups in a city according to house type, value, and geographical
location.
Requirements of Clustering in Data Mining:

The following points throw light on why clustering is required in data mining:
•Scalability: We need highly scalable clustering algorithms to deal with large databases.
•Ability to deal with different kinds of attributes: Algorithms should be capable to be
applied on any kind of data such as interval-based (numerical) data, categorical, and
binary data.
•Discovery of clusters with attribute shape: The clustering algorithm should be capable
of detecting clusters of arbitrary shape. They should not be bounded to only distance
measures that tend to find spherical cluster of small sizes.
•High dimensionality: The clustering algorithm should not only be able to handle low-
dimensional data but also the high dimensional space.
•Ability to deal with noisy data: Databases contain noisy, missing or erroneous data.
Some algorithms are sensitive to such data and may lead to poor quality clusters.
•Interpretability: The clustering results should be interpretable, comprehensible and
usable.
Sr. No. Classification Clustering
Classification is the process of
In clustering, there are no predefined
1 classifying the data with the
class labels.
help of class labels.
Classification is supervised
2 Clustering is unsupervised learning.
learning.
In classification, algorithms In clustering, algorithms like k-means, k-
3 like Decision trees, Bayesian medoids, Expectation-Maximization is
classifiers are used. used.
Classification has prior The cluster doesn't have any prior
4
knowledge of classes. knowledge of classes.
Example: classification
5 Example: discovery of patterns.
between gender.
1. Data Matrix(object by variables matrix)
A data matrix is one of the most common ways to represent data in
clustering.
It consists of:
n objects (rows): Each row represents an object (e.g., a person, house, or
country).
p variables (columns): Each column represents a variable/attribute
describing the object (e.g., age, height, weight, gender, race).

Structure
•It is usually written as an n × p matrix:
• n = number of objects
• p = number of variables/attributes
•Looks like a relational table in databases.
Why Two-Mode Matrix?
•Called a two-mode matrix because:
• Rows represent objects.
• Columns represent variables.
• Thus, two types of entities (objects and attributes) are represented.
 •Here:
• n = 3 (persons)
• p = 4 (attributes)
So, this is a 3 × 4 Data Matrix.

• The Data Matrix is a structured table (n × p) used in clustering where

objects are represented by their attributes.
2. Dissimilarity Matrix(object by object matrix)

•A Dissimilarity Matrix is used to store pairwise differences (or distances) between

objects.
•Instead of storing attributes like in a data matrix, it directly records how similar or
different two objects are.
Structure
•It is represented as an n × n table where:
• n = number of objects
• Each cell d(i, j) represents the dissimilarity (or distance) between object i and
object j.
Why One-Mode Matrix?
•Both rows and columns represent the same set of entities (objects).
•That’s why it’s called a one-mode matrix, unlike the Data Matrix which is two-mode (objects
× variables).

• A Dissimilarity Matrix is an n × n table storing pairwise distances between objects.

It’s symmetric, diagonal values are zero, and it is widely used in distance-based
clustering methods like hierarchical cl
•Here:
• d(A,B)=200d(A, B) = 200d(A,B)=200 km
• d(B,C)=150d(B, C) = 150d(B,C)=150 km
• d(A,C)=400d(A, C) = 400d(A,C)=400 km
This matrix helps clustering algorithms group objects based on closeness (similarity)
or farness (dissimilarity
 Types of Data in Cluster Analysis → Interval-Scaled Variables.

1. Interval-Scaled Variables
Definition
•Interval-scaled variables are continuous numeric measurements taken on a linear
scale.
•These values can be ordered, and the differences between them are meaningful.

Examples
Physical measures: weight, height, temperature.
Geographical data: latitude, longitude (e.g., when clustering houses by location).
Environmental data: weather readings.
Impact of Units
• The choice of measurement unit can influence clustering results.
• Example: If you measure height in meters vs inches, the numerical values
change drastically.
• Similarly, weight in kilograms vs pounds.
• Larger numerical ranges can dominate the clustering process, leading to biased
results.

General Rule
•If a variable is expressed in smaller units, its numerical values become larger,
which gives it more weight in clustering.
•That means it can distort the clustering structure unless data is normalized
(scaled).
Example
Suppose you cluster people based on height and weight:
•Person A: 1.7 m (170 cm), 65 kg
•Person B: 1.8 m (180 cm), 70 kg

If you use meters for height:

•Height difference = 0.1
•Weight difference = 5 • This shows why normalization (scaling all
Here, weight dominates. variables to a common range) is important
before clustering.
If you use centimeters for height:
•Height difference = 10
•Weight difference = 5
Now, height dominates.
• To help avoid dependence on the choice of measurement units, the data should be
standardized. Standardizing measurements attempts to give all variables an equal weight.
• This is especially useful when given no prior knowledge of the data. However, in some
applications, users may intentionally want to give more weight to a certain set of variables
than to others.
• For example, when clustering basketball player candidates, we may prefer to give more
weight to the variable height.
• Distances are normally used to measure the similarity or dissimilarity between two data
objects.
• One of the popular distance measure is Minkowski distance.
2. Binary Variables
Definition
•A binary variable is a variable that takes only two possible values:
• Usually coded as 0 and 1.
•Example:
• Gender (Male/Female)
• Answer (Yes/No)
• Switch (On/Off)

• Contingency Table for Binary Data

To analyze binary variables, we often use a contingency table (cross-tabulation).
This table compares the binary values between two objects (say object i and object j).
Where:
•a = number of attributes where both i and j are 1
•b = number of attributes where i = 1, j = 0
•c = number of attributes where i = 0, j = 1
•d = number of attributes where both i and j are 0
•p = a + b + c + d = total number of attributes

• Interpretation
•a (1,1 matches) → Both objects have the attribute (e.g., both are male).
•b (1,0 mismatch) → Object i has it, but j doesn’t.
•c (0,1 mismatch) → Object j has it, but i doesn’t.
•d (0,0 matches) → Both objects lack the attribute.
This table is used to compute similarity or dissimilarity between binary data
objects.
•Binary variables take values 0 or 1.
•A contingency table (a, b, c, d) is used to compare two objects.
•Depending on whether variables are symmetric or asymmetric, different
similarity measures (SMC, Jaccard) are applied in clustering.

Example: Gender (male/female). Both values are equally important.

Example: Disease test (1 = has disease, 0 = no disease). Two people both having "no
disease" (0,0) doesn’t carry useful similarity information.
 Example: Market-basket data
•"1" means item purchased, "0" means not purchased.
•Jaccard focuses only on purchased items (1’s).
•Symmetric → counts both matches of 1’s and 0’s.
•Asymmetric → counts only matches of 1’s, ignores 0’s.
•Jaccard → similarity measure (a / (a+b+c)), often used in text mining, market-basket analysis,
bioinformatics.
3. Nominal or Categorical Variables
• A generalization of the binary variable in that it can take more than 2 states, e.g., red,
yellow, blue, green.
• Method 1: Simple matching
• The dissimilarity between two objects i and j can be computed based on the simple
matching.
Example

Imagine two objects, A and B, each described by three nominal attributes (e.g., Color,
Shape, Pattern):
•Object A: {Color: Red, Shape: Circle, Pattern: Stripes}
•Object B: {Color: Blue, Shape: Circle, Pattern: Polka Dots}

[Link] (m): Only the 'Shape' attribute matches (Circle). So, m = 1.

[Link] Attributes (p): There are 3 attributes in total. So, p = 3.
[Link] (d(A, B)): (3 - 1) / 3 = 2 / 3.

Therefore, the dissimilarity between object A and object B, using simple matching, is 2/3.
5. Ratio-scaled Variables
•A positive measurement on a nonlinear scale, approximately at exponential
scale, such as

•Method
•Treat them like interval-scaled variables.
•Apply logarithmic transformation

•Treat them as continuous ordinal data, treat their rank as interval-scaled.

6. Variables of Mixed Type
• A database may contain all the six types of variables: symmetric binary,
asymmetric binary, nominal, ordinal, interval, and ratio.
• And those combined are called as Mixed-type variables.
Clustering methods can be Classified into following categories:
• Clustering Methods:

Clustering Methods can be classified into following:

Partitioning Method
Suppose we are given a database of n objects and the partitioning
method constructs k partition of data. Each partition will represent
a cluster and k ≤ n. It means that it will classify the data into k
groups, which satisfy the following requirements:
•Each group contains at least one object.
•Each object must belong to exactly one group.
Hierarchical Methods
This method creates a hierarchical decomposition of the given set of data
objects. We can classify hierarchical methods on the basis of how the
hierarchical decomposition is formed. There are two approaches here –
•Agglomerative Approach
•Divisive Approach

Agglomerative Approach
This approach is also known as the bottom-up approach. In this, we start with
each object forming a separate group. It keeps on merging the objects or
groups that are close to one another. It keeps on doing so until all of the groups
are merged into one or until the termination condition holds.