1
2
Clustering is the process of grouping a set of data objects into
multiple groups or clusters so that objects within a cluster
have high similarity, but are very dissimilar to objects in other
clusters.
Cluster analysis or simply clustering is the process of
partitioning a set of data objects (or observations) into
subsets. Each subset is a cluster, such that objects in a cluster
are similar to one another, yet dissimilar to objects in other
clusters. The set of clusters resulting from a cluster analysis
can be referred to as a clustering.
3
4
Clustering is a kind of unsupervised learning.
Clustering is a method of grouping data that share similar
trend and patterns.
Clustering of data is a method by which large sets of data is
grouped into clusters of smaller sets of similar data.
◦ Example:
After
clustering:
Thus, we see clustering means grouping of data or dividing a large
data set into smaller data sets of some similarity.
5
Cluster analysis has been widely used in many applications such
as business intelligence, image pattern recognition, Web search,
biology, and security.
Some engineering sciences such as pattern recognition, artificial
intelligence have been using the concepts of cluster analysis.
Typical examples to which clustering has been applied include
handwritten characters, samples of speech, fingerprints, and
pictures.
In the life sciences (biology, botany, zoology, entomology, cytology,
microbiology), the objects of analysis are life forms such as plants,
animals, and insects. The clustering analysis may range from
developing complete taxonomies to classification of the species
into subspecies.
Clustering analysis is also widely used in information, policy and
decision sciences. The various applications of clustering analysis to
documents include votes on political issues, survey of markets,
survey of products, survey of sales programs, and R & D.
6
Following are the typical requirements of clustering in data mining:
Scalability
Ability to deal with different types of attributes
Discovery of clusters with arbitrary shape
Requirements for domain knowledge to determine input
parameters
Ability to deal with noisy data
Incremental clustering and insensitivity to input order
Capability of clustering high-dimensional data
Constraint-based clustering
Interpretability and usability
7
The major fundamental clustering methods can be classified
into the following categories:
Partitioning Methods
Hierarchical Method
Density-based Methods
Grid-based Methods
8
Given a set of n objects, a partitioning method constructs k
partitions of the data, where each partition represents a
cluster and k <= n.
It divides the data into k groups such that each group must
contain at least one object.
In other words, partitioning methods conduct one-level
partitioning on data sets.
Most partitioning methods are distance-based. Given k, the
number of partitions to construct, a partitioning method
creates an initial partitioning. It then uses an iterative
relocation technique that attempts to improve the
partitioning by moving objects from one group to another.
9
The general criterion of a good partitioning is that objects in
the same cluster are “close” or related to each other,
whereas objects in different clusters are “far apart” or very
different.
10
A hierarchical method creates a hierarchical decomposition
of the given set of data objects.
A hierarchical method can be classified as being either
agglomerative or divisive, based on how the hierarchical
decomposition is formed .
The agglomerative approach, also called the bottom-up
approach, starts with each object forming a separate group. It
successively merges the objects or groups close to one
another, until all the groups are merged into one (the topmost
level of the hierarchy), or a termination condition holds.
11
The divisive approach, also called the top-down approach,
starts with all the objects in the same cluster. In each
successive iteration, a cluster is split into smaller clusters, until
eventually each object is in one cluster, or a termination
condition holds.
Hierarchical clustering methods can be distance-based or
density- and continuity based.
12
The general idea is to continue growing a given cluster as
long as the density (number of objects or data points) in the
neighborhood” exceeds some threshold.
For example, for each data point within a given cluster, the
neighborhood of a given radius has to contain at least a
minimum number of points.
Such a method can be used to filter out noise or outliers and
discover clusters of arbitrary shape.
13
Grid-based methods quantize the object space into a finite
number of cells that form a grid structure.
All the clustering operations are performed on the grid
structure (i.e., on the quantized space).
The main advantage of this approach is its fast-processing
time, which is typically independent of the number of data
objects and dependent only on the number of cells in each
dimension in the quantized space.
Using grids is often an efficient approach to many spatial
data mining problems, including clustering. Therefore, grid-
based methods can be integrated with other clustering
methods such as density-based methods and hierarchical
methods.
14
15
The simplest and most fundamental version of cluster analysis
is partitioning, which organizes the objects of a set into
several exclusive groups or clusters.
Formally, given a data set, D, of n objects, and k, the number
of clusters to form, a partitioning algorithm organizes the
objects into k partitions (k<=n), where each partition
represents a cluster.
16
The k-means algorithm defines the centroid of a cluster as
the mean value of the points within the cluster.
It proceeds as follows:
❑ First, it randomly selects k of the objects in D, each of which
initially represents a cluster mean or center.
❑ For each of the remaining objects, an object is assigned to
the cluster to which it is the most similar, based on the
Euclidean distance between the object and the cluster mean.
❑ The k-means algorithm then iteratively improves the within-
cluster variation.
17
For each cluster, it computes the new mean using the objects
assigned to the cluster in the previous iteration.
All the objects are then reassigned using the updated means
as the new cluster centers.
The iterations continue until the assignment is stable, that is,
the clusters formed in the current round are the same as
those formed in the previous round.
18
Algorithm: k-means. 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.
19
Method:
(1) arbitrarily choose k objects from D as the initial cluster
centers;
(2) Repeat
(3) (re)assign each object to the cluster to which the object is
the most similar, based on the mean value of the objects in
the cluster;
(4) update the cluster means, that is, calculate the mean value
of the objects for each cluster;
(5) until no change;
20
21
22
23
24
25
26
27
28
29
30
31
32
k-means is stochastic, and does not guarantee to find the
global optimum solution for clustering.
In fact, the algorithm can be very sensitive to outliers and
noisy data: the quality of the final clustering can be highly
dependent on the position of the initial cluster centroids.
In other words, k-means will regularly discover a local rather
than global minimum.
33
Suppose that the data mining task is to cluster points ( with
(x, y) representing location) into three clusters.
The points are A1(2, 10), A2(2, 5), A3(8, 4), B1(5,
8), B2(7, 5), B3(6, 4), C1(1, 2), C2(4, 9).
The distance function is Euclidean distance.
Suppose initially we assign A1, B1, and C1 as the center of
each cluster respectively.
Find out the final three clusters using k-Means algorithm.
34
Partitioning Around Medoids or the K- medoids algorithm is
a partitional clustering algorithm which is slightly modified
from the K-means algorithm.
They both attempt to minimize the squared-error but the K-
medoids algorithm is more robust to noise than K-means
algorithm.
In K-means algorithm, they choose means as the centroids
but in the K-medoids, data points are chosen to be the
medoids.
A medoid can be defined as that object of a cluster, whose
average dissimilarity to all the objects in the cluster is
minimal.
35
The difference between k-means and k-medoids is analogous
to the difference between mean and median: where mean
indicates the average value of all data items collected, while
median indicates the value around that which all data items
are evenly distributed around it.
36
The PAM algorithm is based on the search for k
representative objects or medoids among the observations
of the data set.
After finding a set of k medoids, clusters are constructed by
assigning each observation to the nearest medoid.
Next, each selected medoid and each non-medoid data point
are swapped and the objective function is computed.
The objective function corresponds to the sum of the
dissimilarities of all objects to their nearest medoid.
The SWAP step attempts to improve the quality of the
clustering by exchanging selected objects (medoids) and non-
selected objects.
37
If the objective function can be reduced by interchanging a
selected object with an unselected object, then the swap is
carried out. This is continued until the objective function can
no longer be decreased.
The goal is to find k representative objects which minimize
the sum of the dissimilarities of the observations to their
closest representative object.
The dissimilarity of the medoid(Ci) and object(Pi) is calculated
by using E = |Pi - Ci|
38
1. Initialize: select k random points out of the n data points as
the medoids.
2. Associate each data point to the closest medoid by using
any common distance metric methods.
3. While the cost decreases:
For each medoid “m”, for each data point “o” which is not
a medoid:
a) Swap m and o, associate each data point to the
closest medoid, recompute the cost.
b) If the total cost is more than that in the
previous step, undo the swap.
39
The algorithm proceeds in two steps:
BUILD-step: This step sequentially selects k "centrally
located" objects, to be used as initial medoids.
SWAP-step: If the objective function can be reduced by
interchanging (swapping) a selected object with an
unselected object, then the swap is carried out. This is
continued till the objective function can no longer be
decreased.
40
Build phase:
1. Select k objects to become the medoids, or in case these
objects were provided use them as the medoids.
2. Calculate the dissimilarity matrix if it was not provided.
3. Assign every object to its closest medoid.
Swap phase:
4. For each cluster search if any of the object of the cluster
decreases the average dissimilarity coefficient; if it does,
select the entity that decreases this coefficient the most as
the medoid for this cluster;
5. If at least one medoid has changed go to (3), else end the
algorithm.
41
45
Step 3: randomly select one non-medoid point and
recalculate the cost.
Let the randomly selected point be (8, 4). The dissimilarity of
each non-medoid point with the medoids : C1 (4, 5) and
C2 (8, 4) is calculated and tabulated.
Each point is assigned to that cluster whose dissimilarity is
less. So, the points 1, 2, 5 go to cluster C1 and 0, 3, 6, 7, 8 go
to cluster C2.
The New cost = (3 + 4 + 4) + (2 + 2 + 1 + 3 + 3) = 22
Swap Cost = New Cost – Previous Cost = 22 – 20 and 2 >0 .
As the swap cost is not less than zero, we undo the swap.
Hence ( 4, 5 ) and ( 8, 5 ) are the final medoids. The clustering
would be in the following way.
47
It is simple to understand and easy to implement.
K-Medoid Algorithm is fast and converges in a fixed number of
steps.
PAM is less sensitive to outliers than other partitioning algorithms.
Disadvantages:
➢ The main disadvantage of K-Medoid algorithms is that it is not
suitable for clustering non-spherical (arbitrary shaped) groups of
objects.
➢ This is because it relies on minimizing the distances between the
non-medoid objects and the medoid (the cluster centre) – briefly, it
uses compactness as clustering criteria instead of connectivity.
➢ k-Medoid works efficiently for small data sets but does not scale
well for large data sets.
➢ It may obtain different results for different runs on the same
dataset because the first k medoids are chosen randomly.
The PAM algorithm works with a matrix of dissimilarity, and to
compute this matrix the algorithm can use two metrics:
The Euclidean distances, that are the root sum-of-squares of
differences;
And, the Manhattan distance that are the sum of absolute
distances.
We should get similar results most of the time, using either
Euclidean or Manhattan distance.
If your data contains outliers, Manhattan distance should give
more robust results, whereas Euclidean would be influenced
by unusual values.
A hierarchical clustering method works by grouping data
objects into a tree of clusters.
A hierarchical method creates a hierarchical decomposition
of the given set of data objects.
Hierarchical clustering methods can be distance-based or
density- and continuity based.
Hierarchical clustering methods can be further classified as
either agglomerative or divisive, depending on whether the
hierarchical decomposition is formed in a bottom-up
(merging) or top-down (splitting) fashion.
50
The agglomerative approach, also called the bottom-up
approach, starts with each object forming a separate group. It
successively merges the objects or groups close to one
another, until all the groups are merged into one (the topmost
level of the hierarchy), or a termination condition holds.
Most hierarchical clustering methods belong to this category.
They differ only in their definition of intercluster similarity.
51
52
53
This top-down strategy does the reverse of agglomerative
hierarchical clustering by starting with all objects in one
cluster.
It subdivides the cluster into smaller and smaller pieces,
until each object forms a cluster on its own or until it
satisfies certain termination conditions, such as a desired
number of clusters is obtained or the diameter of each cluster
is within a certain threshold.
54
55
56
When an algorithm uses the minimum distance, dmin(Ci, Cj), to
measure the distance between clusters, it is sometimes called
a nearest-neighbor clustering algorithm.
Moreover, if the clustering process is terminated when the
distance between nearest clusters exceeds an arbitrary
threshold, it is called a single-linkage algorithm.
57
58
59
60
61
62
63
64
66
67
68
69
70
71
72
73
74
75
76
77
78
For each data point within a given cluster, the
neighborhood of a given radius has to contain at least a
minimum no. of points
Such a method can be used to filter out noise or outliers
& discover clusters of arbitrary shape
79
Clustering based on density
Major features:
◦ Discover clusters of arbitrary shape
◦ Handle noise
◦ One scan
Several interesting studies:
◦ DBSCAN
◦ OPTICS
◦ DENCLUE
◦ CLIQUE
80
Two parameters:
◦ Eps: Maximum radius of the neighbourhood
◦ MinPts: Min. no. of points in an Eps- neighbourhood of
that point
◦ Directly Density Reachable: Points inside the circle of
radius Eps
p MinPts = 5
Eps = 1 cm
q
81
Density-reachable:
◦ A point p is density-reachable from p
a point q w.r.t. Eps, MinPts if there
p1
is a chain of points p1, …, pn, p1 = q
q, pn = p such that pi+1 is directly
density-reachable from pi
82
Core Point, Border Point & Noise Point
Make a circle on a given Point with radius = Eps
◦ If the Points inside the circle >= MinPts
The given point is a Core Point
◦ Else it is a Noise Point
◦ A Noise Point can become a Border Point
The circle to which it belongs contains a Core Point
83
Discovers clusters of arbitrary shape in spatial databases
with noise
Outlier
Border
Eps = 1cm
Core MinPts = 5
84
Arbitrary select a point p
Retrieve all points density-reachable from p w.r.t. Eps
and MinPts
If p is a core point, a cluster is formed
If p is a border point, DBSCAN visits the next point of
the database
Continue the process until all of the points have been
processed
85