Module-5 Cluster Analysis

Module - 5: Clustering Analysis

Overview, Types of Clustering, Type of Clusters, K-Means, Agglomerative Hierarchical Clustering, Density-
Based Clustering, Graph-Based Clustering, Cluster Evaluation.
I-Overview
Cluster  Cluster is a collection of data objects.
 Similar to one another within the same cluster.
 Dissimilar to the object in other clusters.
Cluster  Finding similarities between data according to the characteristics found in the data
Analysis and grouping similar data objects into clusters
 The process of grouping a set of abstract objects into classes of similar objects is
called clustering.
 Clustering is an example of unsupervised learning.
 Clustering is a form of learning by observation, rather than learning by
examples.
Qualities of  A good clustering method will produce high quality clusters with
Good 1. high intra-class similarity
Clustering 2. low inter –class similarity
 The quality of a clustering result depends on both the similarity measure used by
the method and its implementation.
 The quality of a clustering method is also measured by its ability to discover some
or all the hidden patterns.
Measuring the 1. Similarity/Dissimilarity metric: Similarity is expresses in terms of a distance
Quality of function, typically metric: d(i,j)
Clustering 2. There is a separate quality function that measures the goodness of a cluster
3. The definitions of distance functions are usually very different for interval-scaled,
Boolean, categorical, ordinal, ratio, and vector variables.
4. Weight should be associated with different variables based on applications and
data semantics.
It is hard to defines similar enough or good enough the answer is typically highly
subjective
Desirable 1. Scalability Pin terms of both time and space
Properties of a 2. Ability to deal with different data types
Clustering 3. Minimal requirements for domain knowledge to determine input parameters
Algorithm 4. Able to deal with noise and outliers
5. Insensitive to order of input records
6. Incorporation of user-specified constraints
7. Interpretability and usability
8. High dimensionality
Ability to handle dynamic data
Applications of • Understanding
Cluster – Group related documents for browsing, group genes and proteins that have similar
Analysis functionality, or group stocks with similar price fluctuations
• Utility
– Reduce the size of large data sets
Differences between Classification and Clustering (***)
• Classification is the process of classifying the data with the help of class labels. On the other hand,
Clustering is similar to classification but there are no predefined class labels.
• Classification is geared with supervised learning. As against, clustering is also known as
unsupervised learning.
• Training sample is provided in classification method while in case of clustering training data is not
provided.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 1

Module-5 Cluster Analysis

No Classification Clustering
1 Supervised data Unsupervised data
2 Does highly value training sets Does not highly value training sets
3 Involves both unlabeled and labeled data Works solely with unlabeled data
Aims to identify similarities among
4 Aims to verify where a datum belongs to
data
5 Does not specify required improvement Specifies required change
6 Has two phases Has a single phase
Identifying the boundary conditions is Determining boundary conditions is
7
essential in executing the phases not paramount
8 Deals with prediction Doesn’t generally deal with prediction
Mainly employs two types of
9 Has a number of probable algorithms to use
algorithms
10 Process is more complex Process is less complex

Table-1: Differences between Classification and Clustering

II-Types of Clustering
The fundamental distinction between clustering types lies in whether the clusters
are nested (hierarchical) or non-nested (partitional).

Partitional Clustering
 Divides data into non-overlapping subsets.
 Un-nested clustering
 Each data object belongs to exactly one cluster.
Partitional  Provides a single flat partition of the data.
1 versus  Examples: k-means, k-medoids, etc.
Hierarchical  In Figure 1 (b–d), each illustration shows a valid partitional clustering with
2, 4, and 6 clusters respectively.

Figure-1: Different ways of clustering the same set of points.

Hierarchical Clustering
 Nested clustering structure.
 Produces a tree-like structure (dendrogram) of clusters.
 Each node (cluster) is a union of its sub-clusters.
 The root contains all objects, and the leaves may be individual data points.
 Allows viewing the data at different levels of granularity.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 2

Module-5 Cluster Analysis

 In Figure 1 (a–d):

If we allow clusters to be nested, then one interpretation of Figure 1(a) is that it

has two sub-clusters (Figure 1(b)), each of which, in turn, has three sub-clusters
(Figure 1(d)). The clusters shown in Figure-1 (a–d), when taken in that order,
also form a hierarchical (nested) clustering with, respectively, 1, 2, 4, and 6
clusters on each level.
Relationship between the Two
 A hierarchical clustering can be seen as a sequence of partitional
clusterings at various levels.
 A partitional clustering is simply one level of the hierarchical tree (a "cut"
across the dendrogram).

Exclusive Clustering:
 In exclusive clustering, each object is assigned to exactly one cluster. This
is the most straightforward form of clustering where clusters do not overlap,
and each data point has a unique assignment.

Example: The clusters in Figure 1 are all exclusive since each data object is
placed into a single cluster, with no overlap.

Overlapping (Non-Exclusive) Clustering:

 In overlapping clustering, objects can belong to multiple clusters
simultaneously. This approach is used in situations where an object naturally
Exclusive fits into more than one category.
versus
2 Overlapping Example: Consider a person at a university who could be both a student and an
versus employee. In such cases, overlapping clustering allows the person to be a part
Fuzzy of both clusters (student and employee).
Clustering
Application: Overlapping clustering is also useful when an object is situated
between multiple clusters and could reasonably belong to any of them. For
instance, a point that lies halfway between two clusters in Figure 1 might be
assigned to both clusters rather than making an arbitrary choice.

Fuzzy Clustering:
 Fuzzy clustering is a method where every object has a degree of belonging
to every cluster, represented by a membership weight that ranges from 0 (not
belonging at all) to 1 (completely belonging).
 Mathematically, fuzzy clustering treats clusters as fuzzy sets, where each
object has a membership weight associated with each cluster. The sum of the
membership weights for an object typically equals 1.

Example: In a fuzzy clustering scenario, each data object in Figure 1 would

have a fractional membership in every cluster. For instance, a point might
belong to Cluster A with a weight of 0.6 and to Cluster B with a weight of 0.4.

 In practice, fuzzy clustering results are often converted into an exclusive

clustering by assigning each object to the cluster for which it has the highest
membership weight.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 3

Module-5 Cluster Analysis

Complete Clustering:

In this approach, every object in the dataset is assigned to a cluster, ensuring

that no data point is left ungrouped.

This is useful in scenarios where the goal is to organize all available data into
distinct categories, such as organizing documents for browsing. The requirement
here is that every document or data point must be accessible within the clusters,
Complete making it essential that the clustering method covers the entire dataset.
3 versus Partial
Partial Clustering:
Unlike complete clustering, partial clustering allows for the exclusion of certain
objects from any cluster.

This is motivated by the recognition that not all objects may fit neatly into a
cluster, often due to noise, outliers, or less relevant background data. For
example, when analyzing newspaper articles to find significant topics like global
warming, partial clustering can help focus on tightly related groups of articles,
while disregarding those that are more generic or irrelevant to the primary
themes of interest.

III-Different Types of Clusters

• Clustering involves identifying and categorizing groups of similar objects in a dataset, with the nature of
the clusters varying based on the goals of the analysis. Below are different types of clusters, illustrated using
two-dimensional points:
• To visually illustrate the differences among these types of clusters, we use two- dimensional points.

i) Well-Separated Clusters

 Clusters where each data point is closer to its own cluster than to any other cluster.
 Points within a well-separated cluster are much more similar to each other than to points in other
clusters.
 The distance between any two points in different groups is larger than the distance between any two
points within a group.

These groups are well-separated clusters. Figure 2(a) shows an example of well separated clusters.

Figure 2(a) Well-separated cluster. Each point is closer to all the points in its cluster than to any point in
another cluster
[

ii) Prototype based

• A cluster is a set of objects in which each object is closer (more similar) to the prototype of its cluster than
to the prototype of any other cluster.
• For many types of data, the prototype can be regarded as the most central point, and in such instances,
we commonly refer to prototype based clusters as Center-based clusters.
• For data with continuous attributes, the prototype of a cluster is often a Centroid.
• When a centroid is not meaningful, such as when the data has Categorical attributes, the prototype is
often a Medoid.
• Figure 2(b) shows an example of center-based clusters.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 4

Module-5 Cluster Analysis

Figure 2b: Center-based clusters. Each point is closer to the center of its cluster than to the center of any other
cluster.

Continuous attributes are numeric values that can take Categorical attributes are variables that represent
an infinite number of values within a given range. distinct categories or groups.
These attributes have a finite number of distinct values
Examples: or categories, and these categories are often not
Height: A person’s height can be 170.5 cm, 172.3 cm, numerical (though they can be coded as numbers).
etc. Examples:
Weight: A person’s weight might be 65.2 kg, 67.8 kg, etc. Color: Categories like red, blue, green.
Type of Animal: Categories like dog, cat, bird.

iii) Graph-Based

• If the data is represented as a graph in which group of objects are connected to one another, but that
have no connection to objects outside the group.

• An important example of graph-based clusters are Contiguity-based clusters, where two objects
are connected only if they are within a specified distance of each other. This implies that each
object in a contiguity-based cluster is closer to some other object in the cluster than to any point in a
different cluster.

• Figure- 2(c) shows an example of such 4 clusters for two-dimensional points.

Figure 2(c): contiguity based clusters [4] each point is closer to at least one point in its cluster than to any
point in another cluster.

• This definition of a cluster is useful when clusters are irregular or intertwined. However, this approach
can have trouble when noise is present since, as illustrated by the two spherical clusters of Figure -
2(c), a small bridge of points can merge two distinct clusters.

iv) Density-Based

• Density based clusters are the regions of high density separated by a region of low density.
• A density based definition of a cluster is often employed when the clusters are irregular or intertwined,
and when noise and outliers are present.
• By contrast, a contiguity based definition of a cluster would not work well for the data since the noise
would tend to form bridges between clusters.
• Figure-2(d) shows few density-based clusters created by adding noise to the data of Figure-2(c).

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 5

 Module-5 Cluster Analysis

Figure (2d) Density-Based clusters: Clusters are regions of high density separated by regions of low density.

Note: The two circular clusters are not merged, as in Figure 2(c), because the bridge between them fades into the noise.
Likewise, the curve that is present in Figure-2(c) also fades into the noise and does not form a cluster in Figure-2(d).

v) Shared-Property (Conceptual Clusters)

• Cluster as a set of objects that share some property
– Objects in a center-based cluster share the property that they are all closest to the same centroid
or medoid.
• Shared-property approach also includes new types of clusters.
• Clustering algorithm would need a very specific concept of a cluster to successfully detect these
clusters. The process of finding such clusters is called Conceptual clustering.

Figure-2(e) Conceptual clusters. Points in a cluster share some general property that derives from the entire
set of points. (Points in the intersection of the circles belong to both.)

IV- K - Means
K-means defines a prototype in terms of a centroid, which is usually the mean of a group of points, and is
typically applied to objects in a continuous n-dimensional space.
• K-medoid defines a prototype in terms of a medoid, which is the most representative point for a group
of points, and can be applied to a wide range of data since it requires only a proximity measure for a pair
of objects.
The Basic K-means Algorithm
The k-means algorithm for partitioning, where each cluster’s center is represented by the mean value of the
objects in the cluster.
Input K: the number of clusters,
D: a data set containing n objects
Output A set of k clusters
Algorithm

Table1 : Basic K-means algorithm.

Explanation:
 First choose K initial centroids, where K is a user specified parameter, namely, the
number of clusters desired.
 Each point is then assigned to the closest centroid, and each collection of points
assigned to a centroid is a cluster.
 The centroid of each cluster is then updated based on the points assigned to the
cluster.
 Repeat the assignment and update steps until no point changes clusters, or
equivalently, until the centroids remain the same.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 6

 Module-5 Cluster Analysis

Figure-3:Using the K-means algorithm to find three clusters in sample data.

K-means • Initial centroids are often chosen randomly.
Clustering – • Clusters produced vary from one run to another.
Details • The centroid is (typically) the mean of the points in the cluster.
• ‘Closeness’ is measured by Euclidean distance, correlation.
• K-means will converge for common similarity measures.
• Most of the convergence happens in the first few iterations.
• Often the stopping condition is changed to ‘Until relatively few points change clusters’
or some measure of clustering doesn’t change.
• Complexity is O( n * K * I * d )
• n -> #points, K -> #Clusters, I -> #iterations, d -> #attributes
Advantages • With a large number of variables, k-means nay be computationally faster than
hierarchical clustering (if k is small).
• K-means may produce tighter clusters than hierarchical clustering, especially if the
clusters are globular.
Disadvantages • Difficult in comparing the quality of the clusters produced.
• Applicable only when mean is defined.
• Need to specify k, the number of clusters, in advance.
• Unable to handle noisy data and Outliers.
• Not suitable to discover cluster with non-convex shapes.
• Finally, K-means is restricted to data for which there is a notion of a center (centroid). A
related technique, K-medoid clustering, does not have this restriction, but is more
expensive.
Common
choices for
proximity,
centroids,
and
objective
functions.
for K-means

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 7

 Module-5 Cluster Analysis

Bisecting K-means
– The bisecting K-means algorithm is a straightforward extension of the basic K-means algorithm that is based
on a simple idea:
– To obtain K clusters, split the set of all points into two clusters, select one of these clusters to split, and so
on, until K clusters have been produced.
Bisecting K-
means
Algorithm.

Explanation

Figure-4: Two pairs of clusters with a pair of initial centroids within each pair of clusters.

To illustrate that bisecting K-means is less susceptible to initialization problems, we show, in

Figure-5, how bisecting K-means finds four clusters in the data set originally shown in
Figure-4. In iteration 1, two pairs of clusters are found; in iteration 2, the rightmost pair of
clusters is split; and in iteration 3, the leftmost pair of clusters is split. Bisecting K-means has
less trouble with initialization because it performs several trial bisections and takes the one
with the lowest SSE, and because there are only two centroids at each step.

Finally, by recording the sequence of clustering’s produced as K-means bisects clusters, we

can also use bisecting K-means to produce a hierarchical clustering.

Figure-5: Bisecting K-means on the four clusters example

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 8

Module-5 Cluster Analysis

V-Hierarchical Clustering
Hierarchical clustering techniques are a second important category of clustering methods. As with K-means,
these approaches are relatively old compared to many clustering algorithms, but they still enjoy widespread
use. There are two basic approaches for generating a hierarchical clustering
1. Agglomerative: Start with the points as individual clusters and, at each step, merge the closest pair of
clusters. This requires defining a notion of cluster proximity.
2. Divisive : Start with one, all-inclusive cluster and, at each step, split a cluster until only singleton clusters
of individual points remain. In this case, we need to decide which cluster to split at each step and how to
do the splitting.
Agglomerative 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

Steps in agglomerative hierarchical clustering

1. Compute the proximity matrix.
2. Let each data point be a cluster
3. Repeat
4. Merge the two closest clusters.
5. Update the proximity matrix
6. Until only a single cluster remains

Basic Agglomerative Hierarchical Clustering Algorithm

Figure-5: Basic agglomerative hierarchical clustering algorithm.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 9

Module-5 Cluster Analysis

Key Issues in Hierarchical Clustering:

– Lack of a Global Objective Function.
– Ability to Handle Different Cluster Sizes.
– Merging Decisions Are Final.

VI-Graph-based Clustering
Cluster Proximity Definitions - Graph-based

1) Min (single Link):

MIN defines cluster proximity as the proximity between the closest two points that are in
different clusters, or using graph terms, the shortest edge between two nodes in different
subsets of nodes. This yields contiguity-based clusters.

2) MAX (Complete Link or CLIQUE):

MAX takes the proximity between the farthest two points in different clusters to be the cluster
proximity, or using graph terms, the longest edge between two nodes in different subsets of
nodes.

If our proximities are distances, then the names, MIN and MAX, are short and suggestive.
3) Group Average:

Group average defines cluster proximity to be the average pairwise proximities (average length
of edges) of all pairs of points from different clusters

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 10

Module-5 Cluster Analysis

Example: Consider 6 two-dimensional data points

Set of 6 two-dimensional points. (x,y) coordinates of 6 points.

Figure : Euclidien distance matrix for 6 points.

1) Min (single Link):

Distance between points 3 and 6 is 0.11, and that is the height at which they are joined into
one cluster in the Dendrogram.
Distance between clusters {3, 6} & {2, 5} is given by:
dist({3, 6}, {2, 5}) = min{dist(3, 2), dist(6, 2), dist(3, 5), dist(6, 5)}
= min(0.15, 0.25, 0.28, 0.39) = 0.15.

Figure: Single link clustering of the six points

2) MAX (Complete Link or CLIQUE):

As with single link, points 3 and 6 are merged first. However, {3, 6} is merged with {4}, instead of {2, 5}
or {1} because:
dist({3, 6}, {4}) = max(dist(3, 4), dist(6, 4))
dist({3, 6}, {2, 5}) = max(dist(3, 2), dist(6, 2), dist(3, 5), dist(6, 5))
dist({3, 6}, {1}) = max(dist(3, 1), dist(6, 1))
Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 11
Module-5 Cluster Analysis

dist({3, 6}, {4}) = max(dist(3, 4), dist(6, 4)) = max(0.15, 0.22) = 0.22.
dist({3, 6}, {2, 5}) = max(dist(3, 2), dist(6, 2), dist(3, 5), dist(6, 5)) = max(0.15, 0.25, 0.28, 0.39) = 0.39.
dist({3, 6}, {1}) = max(dist(3, 1), dist(6, 1)) = max(0.22, 0.23) = 0.23.

Figure: Complete link clustering of the six points

3) Group Average:

dist({3, 6, 4}, {1}) = (0.22 + 0.37 + 0.23)/(3 ∗ 1) = 0.28

dist({2, 5}, {1}) = (0.2357 + 0.3421)/(2 ∗ 1) = 0.2889
dist({3, 6, 4}, {2, 5})= (0.15 + 0.28 + 0.25 +0.39 +0.20 + 0.29)/(3∗ 2)= 0.26
Because dist({3, 6, 4}, {2, 5}) is smaller than dist({3, 6, 4}, {1}) and dist({2, 5}, {1}), clusters {3, 6, 4} and
{2, 5} are merged at the fourth stage.

MIN & MAX: Comparison

• MIN Strength: Can handle non-elliptical shapes.
• MIN Drawback: Sensitive to Noise & Outliers.
• MAX Strength: Less susceptible to Noise & Outliers.
• MAX Drawback: Tends to break large clusters & is biased toward globular clusters.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 12

Module-5 Cluster Analysis

VII- Density-based clustering

Density-based clustering locates regions of high density that are separated from one another by regions
of low density.

Classification of Points According to Center-Based Density: The center-based approach to density allows
us to classify a point as being
(1) in the interior of a dense region (a core point),
(2) on the edge of a dense region (a border point), or
(3) In a sparsely occupied region (a noise or background point).

Figure-7 graphically illustrates the concepts of core, border, and noise points using a collection of two-
dimensional points.

Figure-7: Core, border, and noise points.

Two parameters are required to define the core, border and noise points
i) Eps: Maximum radius of the neighborhood.
NEps(p): {q belongs to D | dist(p,q) ≤ Eps}

ii) MinPts: Minimum number of points in an Eps-neighbourhood of that point.

Core points
• These points are in the interior of a density-based cluster.
• A point is a core point if the number of points within a given neighborhood around the point as
determined by the distance function
– User specified distance parameter, Eps, exceeds a certain threshold, MinPts, which is also a user-
specified parameter.
• A point is a core point if there are at least MinPts within a distance of Eps, where MinPts and Eps are
user-specified parameters. In Figure 7, point A is a core point for the radius (Eps) if MinPts ≥ 7.
Border points
– A border point is not a core point, but falls within the neighborhood of a core point.
– A border point can fall within the neighborhoods of several core points.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 13

 Module-5 Cluster Analysis

– In Figure 7, point B is a border point. A border point can fall within the neighborhoods of several
core points.
Noise points
 A noise point, is any point that is neither a core point nor a border point.
 In Figure 7, point C is a noise point.

Two Definitions
i) Density-reachable:
A point p is density-reachable from a point q w.r.t. Eps, MinPts if there is a chain of points p1, …, pn,
p1 = q, pn = p such that pi+1 is directly density-reachable from pi i.e. if
– p belongs to NEps(q)
– core point condition: |NEps (q)| ≥ MinPts

Density-connected:
A point p is density-connected to a point q w.r.t. Eps, MinPts if there is a point o such that both, p and q are
density-reachable from o w.r.t. Eps and MinPts

DBSCAN Algorithm

Figure: DBSCAN Algorithm

 Given the previous definitions of core points, border points, and noise points, the DBSCAN
algorithm can be informally described as follows.
 Any two core points that are close enough—within a distance Eps of one another—are put in
the same cluster.
 Likewise, any border point that is close enough to a core point is put in the same cluster as the
core point. (Ties need to be resolved if a border point is close to core points from different
clusters.)
 Noise points are discarded. The formal details are given in the above Algorithm.
 This algorithm uses the same concepts and finds the same clusters as the original DBSCAN,
but is optimized for simplicity, not efficiency.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 14

Module-5 Cluster Analysis

PROBLEM: Apply the DBSCAN algorithm to the given data points and create the clusters
with min_samples = 4 and epsilon (ϵ) = 1.9 p1 (3,7) p2(4,6) p3(5,5) p4(6,4) p5(7,3)
p6(6,2) p7(7, 2) p8(8,4) p9(3,3) p10(2,6) p11(3,5) p12(2,4)

Solution: Calculate the distance between each points using Euclidian distance

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 15

Module-5 Cluster Analysis

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 16

Module-5 Cluster Analysis

Requirements of Clustering in Data Mining

• Scalability
• Ability to deal with different types of attributes
• Ability to handle dynamic data
• Discovery of clusters with arbitrary shape
• Minimal requirements for domain knowledge to determine input parameters
• Able to deal with noise and outliers & insensitive to order of input records
• High dimensionality
• Incorporation of user-specified constraints
• Interpretability and usability

Typical Alternatives to Calculate the Distance between Clusters

• Single link: smallest distance between an element in one cluster and an element in the
other, i.e., dis(Ki, Kj) = min(tip, tjq)
• Complete link: largest distance between an element in one cluster and an element in the
other, i.e., dis(Ki, Kj) = max(tip, tjq)
• Average: avg distance between an element in one cluster and an element in the other,
i.e., dis(Ki, Kj) = avg(tip, tjq)
• Centroid: distance between the centroids of two clusters, i.e., dis(Ki, Kj) = dis(Ci, Cj)
• Medoid: distance between the medoids of two clusters, i.e., dis(Ki, Kj) = dis(Mi, Mj)
– Medoid: one chosen, centrally located object in the cluster

Comparing Various Algorithms

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 17

Module-5 Cluster Analysis

CLUSTER EVALUATION or CLUSTER VALIDATION

In supervised classification, the evaluation of the classification model is an integral part of the
process of developing a classification model, and there are well-accepted evaluation measures
and procedures, e.g., accuracy and cross-validation, respectively.

However, because of its very nature, cluster evaluation is not a well-developed or

commonly used part of cluster analysis. Nonetheless, cluster evaluation, or cluster
validation is important.

There might be some confusion as to why cluster evaluation is necessary.

Many times, cluster analysis is conducted as a part of an exploratory data analysis. Hence,
evaluation seems to be an unnecessarily complicated addition to what is supposed to be an
informal process.

Furthermore, because there are a number of different types of clusters—in some sense, each
clustering algorithm defines its own type of cluster—it can seem that each situation might
require a different evaluation measure. For instance, K-means clusters might be evaluated in
terms of the SSE, but for density-based clusters, which need not be globular, SSE would not
work well at all.

Nonetheless, cluster evaluation should be a part of any cluster analysis. A key motivation is
that almost every clustering algorithm will find clusters in a data set, even if that data set has
no natural cluster structure.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 18

Module-5 Cluster Analysis

Figure-8: Clustering of 100 uniformly distributed points.

For instance, consider Figure 8, which shows the result of clustering 100 points that are
randomly (uniformly) distributed on the unit square.

The original points are shown in Figure 8(a), while the clusters found by DBSCAN, K-means,
and complete link are shown in Figures 8(b), 8(c), and 8(d), respectively.

Since DBSCAN found three clusters (after we set Eps by looking at the distances of the fourth
nearest neighbors), we set K-means and complete link to find three clusters as well. (In Figure
8(b) the noise is shown by the small markers.) However, the clusters do not look compelling
for any of the three methods. In higher dimensions, such problems cannot be so easily detected.

Being able to distinguish whether there is non-random structure in the data is just one
important aspect of cluster validation.

The following is a list of several important issues for cluster validation.

1. Determining the clustering tendency of a set of data, i.e., distinguishing whether non-
random structure actually exists in the data.
2. Determining the correct number of clusters.
3. Evaluating how well the results of a cluster analysis fit the data without reference to
external information.
4. Comparing the results of a cluster analysis to externally known results, such as
externally provided class labels.
5. Comparing two sets of clusters to determine which is better.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 19

Module-5 Cluster Analysis

Notice that items 1, 2, and 3 do not make use of any external information— they are
unsupervised techniques, while item 4 requires external information.

Item 5 can be performed in either a supervised or an unsupervised manner.

A further distinction can be made with respect to items 3, 4, and 5: Do we want to evaluate the
entire clustering or just individual clusters?

The evaluation measures, or indices, that are applied to judge various aspects of cluster
validity are traditionally classified into the following three types.

1. Unsupervised.
Measures the goodness of a clustering structure without respect to external information. An
example of this is the SSE. Unsupervised measures of cluster validity are often further
divided into two classes: measures of cluster cohesion (compactness, tightness), which
determine how closely related the objects in a cluster are, and measures of cluster separation
(isolation), which determine how distinct or well separated a cluster is from other clusters.
Unsupervised measures are often called internal indices because they use only information
present in the data set.
2. Supervised.
Measures the extent to which the clustering structure discovered by a clustering algorithm
matches some external structure. An example of a supervised index is entropy, which
measures how well cluster labels match externally supplied class labels. Supervised
measures are often called external indices because they use information not present in the
data set.
3. Relative.
Compares different clustering’s or clusters. A relative cluster evaluation measure is a
supervised or unsupervised evaluation measure that is used for the purpose of comparison.
Thus, relative measures are not actually a separate type of cluster evaluation measure, but
are instead a specific use of such measures. As an example, two K-means clustering’s can
be compared using either the SSE or entropy.
Unsupervised cluster evaluation, beginning with
(1) measures based on cohesion and separation, and
(2) two techniques based on the proximity matrix

Unsupervised Cluster Evaluation Using Cohesion and Separation

Overall cluster validity for a set of K clusters as a weighted sum of the validity of individual
clusters,

The validity function can be cohesion, separation, or some combination of these quantities. The
weights will vary depending on the cluster validity measure. In some cases, the weights are
simply 1 or the size of the cluster, while in other cases to be discussed a bit later, they reflect a
more complicated property of the cluster.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 20

Module-5 Cluster Analysis

Graph-Based View of Cohesion and Separation

From a graph-based view, the cohesion of a cluster can be defined as the sum of the weights of
the links in the proximity graph that connect points within the cluster. See Figure 9(a). (Recall
that the proximity graph has data objects as nodes, a link between each pair of data objects, and
a weight assigned to each link that is the proximity between the two data objects connected by
the link.) Likewise, the separation between two clusters can be measured by the sum of the
weights of the links from points in one cluster to points in the other cluster. This is illustrated
in Figure 9(b).

Figure-9: Graph-based view of cluster cohesion and separation

Most simply, the cohesion and separation for a graph-based cluster can be expressed using the
following equations respectively.. The proximity function can be a similarity or a
dissimilarity. For similarity, as in Table-1, higher values are better for cohesion while lower
values are better for separation. For dissimilarity, the opposite is true, i.e., lower values are
better for cohesion while higher values are better for separation. More complicated approaches
are possible but typically embody the basic ideas of figure 9a and 9b.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 21

Module-5 Cluster Analysis

Table of graph-based cluster evaluation measures.

Prototype-Based View of Cohesion and Separation

For prototype-based clusters, the cohesion of a cluster can be defined as the sum of the
proximities with respect to the prototype (centroid or medoid) of the cluster. Similarly, the
separation between two clusters can be measured by the proximity of the two cluster
prototypes. This is illustrated in Figure-10, where the centroid of a cluster is indicated by a “+”.

Figure 10:. Prototype-based view of cluster cohesion and separation.

where ci is the prototype (centroid) of cluster Ci and c is the overall prototype (centroid). There
are two measures for separation because, the separation of cluster prototypes from an overall

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 22

Module-5 Cluster Analysis

prototype is sometimes directly related to the separation of cluster prototypes from one another.
(This is true, for example, for Euclidean distance.) Note that Cohesion Equation, is the cluster
SSE if we let proximity be the squared Euclidean distance.

Relationship between Prototype-Based Cohesion and Graph-Based Cohesion

While the graph-based and prototype-based approaches to measuring the cohesion and
separation of a cluster seem distinct, for some proximity measures they are equivalent. For
instance, for the SSE and points in Euclidean space, it can be shown (from the following
equation ) that the average pairwise distance between the points in a cluster is equivalent to the
SSE of the cluster.

Relationship of the Two Approaches to Prototype-Based Separation

When proximity is measured by Euclidean distance, the traditional measure of separation

between clusters is the between group sum of squares (SSB), which is the sum of the squared
distance of a cluster centroid, ci, to the overall mean, c, of all the data points.

It is straightforward to show that the total SSB is directly related to the pairwise distances
between the centroids. In particular, if the cluster sizes are equal, i.e., mi = m/K, then this
relationship takes the simple form given by

Relationship between Cohesion and Separation

For some validity measures, there is also a strong relationship between cohesion and separation.
Specifically, it is possible to show that the sum of the total SSE and the total SSB is a constant;
i.e., that it is equal to the total sum of squares (TSS), which is the sum of squares of the distance
of each point to the overall mean of the data. The importance of this result is that minimizing
SSE (cohesion) is equivalent to maximizing SSB (separation).

Relationship between Graph- and Centroid-Based Cohesion

It can also be shown that there is a relationship between graph- and centroidbased
cohesion measures for Euclidean distance. For simplicity, we once again
assume one-dimensional data.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 23

Module-5 Cluster Analysis

Data in Euclidean Space

Sum of the squared error (SSE): We calculate the error of each data point, i.e., its
Euclidean distance to the closest centroid, and then compute the total sum of the squared
errors.
• Given two different sets of clusters that are produced by two different runs of K-
means, we prefer the one with the smallest squared error since this means that the
prototypes (centroids) of this clustering are a better representation of the points in
their cluster.

Eg: Centroid of a cluster containing the three two-dimensional points:

(1,1), (2,3), and (6,2), is ---> ((1 + 2 + 6)/3, ((1 + 3 + 2)/3) = (3, 2).
Reducing the SSE with Post-Processing
• An obvious way to reduce the SSE is to find more clusters, i.e., to use a larger K.
• In many cases, we would like to improve the SSE, but don’t want to increase the number
of clusters.
• One commonly used approach is to use alternate cluster splitting and merging phases.
• During a splitting phase, clusters are divided, while during a merging phase, clusters
are combined.

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 24

Module-5 Cluster Analysis

Two strategies that decrease the total SSE by increasing the number of clusters are the
following:

• Split a cluster
– The cluster with the largest SSE is usually chosen, but we could also split the
cluster with the largest standard deviation for one particular attribute.

• Introduce a new cluster centroid

– Often the point that is farthest from any cluster center is chosen. We can easily
determine this if we keep track of the SSE contributed by each point. Another
approach is to choose randomly from all points or from the points with the highest
SSE.

Two strategies that decrease the number of clusters, while trying to minimize the increase in
total SSE, are the following:

• Disperse a cluster
– This is accomplished by removing the centroid that corresponds to the cluster and
re-assigning the points to other clusters.
– Ideally, the cluster that is dispersed should be the one that increases the total SSE
the least.

• Merge two clusters

– The clusters with the closest centroids are typically chosen, although another,
perhaps better, approach is to merge the two clusters that result in the smallest
increase in total SSE.
– These two merging strategies are the same ones that are used in the hierarchical
clustering techniques known as the centroid method

Dadapeer, Asst. Prof, Dept. of CSE, BITM Page 25