5 / 6

Clustering Analysis

Explores clustering types (partitional vs. hierarchical), cluster definitions (well-separated, center-based, density-based), and key algorithms including agglomerative hierarchical clustering, K-Means, and DBSCAN.

The purpose of clustering analysis is to find groups of objects which are related to each other. The definition of a cluster can be ambiguous, as we need to define what we consider a cluster.

Types of clustering

There are two kinds of clustering:

  1. Partitional clustering, it's the division of data into non overlapping clusters, so that a single data object is only in one subset
  2. Hierarchical clustering, the set of nested clusters which are organized in a hierarchical tree
Clustering Procedures Hierarchical Nonhierarchical Agglomerative Divisive Linkage Methods Variance Methods Centroid Methods Ward’s Method Single Linkage Complete Linkage Average Linkage Sequential Threshold Parallel Threshold Optimizing Partitioning

we can then also specialize the clusters into:

  • Well-centered clusters
  • Center-based clusters
  • Contiguous clusters
  • Density-based clusters
  • Property or Conceptual
  • Described by an objective function

Well-Separated cluster

In the Well-separated cluster, a cluster is a set of points such that any point in cluster is closer (or more similar) to every other point in the cluster, than to any other point not in the cluster

Center-based cluster

In the center-based cluster, a cluster is a set of objects such that an object in a cluster is closer (or more similar) to the "center" of it's cluster, than it is to the center of any other cluster. The center of the cluster is called centroid and it is the average of all points in the cluster, or alternatively, we use the medoid which is the point that is most "representative" of the cluster

Contiguity-based cluster

In the contiguity-based cluster, a cluster is a set of points such that a point in a cluster is closer (or more similar) to one or more points in the cluster than to any other point not in the cluster Pasted image 20231213154355.png

Density-based clusters

In density-based clusters, a cluster is a dense region of points, which are separated by low density regions, and then again higher density regions. It is mostly used when clusters are irregular and intertwined, and when noise and outliers are present

Conceptual clusters

In conceptual clusters, a cluster is a set of objects that share a common propriety or particular concept (sub-space)

Hierarchical clustering

This is a typical clustering analysis approach which partitions data set sequentially. It constructs nested partitions layer by layer via grouping objects in a tree of clusters.

There are two approaches when building hierarchical clusters:

  • Agglomerative, a bottom up strategy where initially, each data object is it's own atomic cluster, then we merge those clusters into larger and larger clusters
  • Divisive, is a top down strategy where initially, all objects are in a single cluster, and we try to subdivide them into smaller and smaller clusters
Step 0 Step 1 Step 2 Step 3 Step 4 Step 4 Step 3 Step 2 Step 1 Step 0 AgglomerativeDivisive a b c d e a b a b c d e c d e d e

There are also different methods to compare the distance between clusters:

  • Single link: the smallest distance between an element in one cluster and an element in another cluster. d(Ci,Cj)=min{d(xip,xjp)}d(C_i, C_j) = min\{d(x_{ip}, x_{jp})\}
  • Complete link: the largest distance between an element in one cluster and an element in another cluster. d(Ci,Cj)=max{d(xip,xjp)}d(C_i, C_j) = max\{d(x_{ip}, x_{jp})\}
  • Average: the average distance between elements in one cluster and elements in another. d(Ci,Cj)=avg{d(xip,xjp)}d(C_i, C_j) = avg\{d(x_{ip}, x_{jp})\} Pasted image 20231213155533.png

Example: Given a data set of five objects characterized by a single continuous feature, assume that there are two clusters: C1: {a, b} and C2: {c, d, e}.

abcde
Feature12456
  1. Calculate the distance matrix;
  2. Calculate three cluster distances between C1 and C2.
abcde
a01345
b10234
c32012
d43101
e54210

Single link

dist(C1,C2)=min⁡{d(a,c),d(a,d),d(a,e),d(b,c),d(b,d),d(b,e)}=min⁡{3,4,5,2,3,4}=2\begin{aligned} \mathrm{dist}(C_1,C_2) &= \min\{d(a,c), d(a,d), d(a,e), d(b,c), d(b,d), d(b,e)\} \\ &= \min\{3, 4, 5, 2, 3, 4\} = 2 \end{aligned}

Complete link

dist(C1,C2)=max⁡{d(a,c),d(a,d),d(a,e),d(b,c),d(b,d),d(b,e)}=max⁡{3,4,5,2,3,4}=5\begin{aligned} \mathrm{dist}(C_1,C_2) &= \max\{d(a,c), d(a,d), d(a,e), d(b,c), d(b,d), d(b,e)\} \\ &= \max\{3, 4, 5, 2, 3, 4\} = 5 \end{aligned}

Average

dist(C1,C2)=d(a,c)+d(a,d)+d(a,e)+d(b,c)+d(b,d)+d(b,e)6=3+4+5+2+3+46=216=3.5\begin{aligned} \mathrm{dist}(C_1,C_2) &= \frac{d(a,c) + d(a,d) + d(a,e) + d(b,c) + d(b,d) + d(b,e)}{6} \\ &= \frac{3+4+5+2+3+4}{6} = \frac{21}{6} = 3.5 \end{aligned}

Agglomerative Algorithm

  1. Convert all object features into a distance matrix
  2. Set each object as a cluster (thus if we have N objects, we will have N clusters at the beginning)
  3. Repeat until number of cluster is one (or known # of clusters)
    • Merge two closest clusters
    • Update "distance matrix"
Start Objects and their measured features Compute Distance matrix Set Object as Cluster Number of cluster = 1 Merge 2 closest clusters Update Distance matrix End Yes No

Agglomerative algorithm example:

Problem: clustering analysis with agglomerative algorithm

X1X1X2X20022446600112233445566ABCDEF

Data matrix

X1X2
A11
B1.51.5
C55
D34
E44
F33.5

Euclidean distance

dAB=((1−1.5)2+(1−1.5)2)12=12=0.7071d_{AB} = \left((1-1.5)^2 + (1-1.5)^2\right)^{\frac{1}{2}} = \sqrt{\tfrac{1}{2}} = 0.7071 dDF=((3−3)2+(4−3.5)2)12=0.5d_{DF} = \left((3-3)^2 + (4-3.5)^2\right)^{\frac{1}{2}} = 0.5

Distance matrix

DistABCDEF
A0.000.715.663.614.243.20
B0.710.004.952.923.542.50
C5.664.950.002.241.412.50
D3.612.922.240.001.000.50
E4.243.541.411.000.001.12
F3.202.502.500.501.120.00

(Iteration 1) Merge two closest clusters

X1X1X2X20022446600112233445566ABCDEF
DistABCDEF
A0.000.715.663.614.243.20
B0.710.004.952.923.542.50
C5.664.950.002.241.412.50
D3.612.922.240.001.000.50
E4.243.541.411.000.001.12
F3.202.502.500.501.120.00
DistABCD, FE
A0.000.715.66?4.24
B0.710.004.95?3.54
C5.664.950.00?1.41
D, F???0.00?
E4.243.541.41?0.00

(Iteration 1) Update the distance matrix with the now merged D,F cluster

DistABCDEF
A0.000.715.663.614.243.20
B0.710.004.952.923.542.50
C5.664.950.002.241.412.50
D3.612.922.240.001.000.50
E4.243.541.411.000.001.12
F3.202.502.500.501.120.00
DistABCD, FE
A0.000.715.66?4.24
B0.710.004.95?3.54
C5.664.950.00?1.41
D, F???0.00?
E4.243.541.41?0.00
d(D,F)→A=min⁡(dDA,dFA)=min⁡(3.61,3.20)=3.20d_{(D,F)\to A} = \min(d_{DA}, d_{FA}) = \min(3.61, 3.20) = 3.20 d(D,F)→B=min⁡(dDB,dFB)=min⁡(2.92,2.50)=2.50d_{(D,F)\to B} = \min(d_{DB}, d_{FB}) = \min(2.92, 2.50) = 2.50 d(D,F)→C=min⁡(dDC,dFC)=min⁡(2.24,2.50)=2.24d_{(D,F)\to C} = \min(d_{DC}, d_{FC}) = \min(2.24, 2.50) = 2.24 dE→(D,F)=min⁡(dED,dEF)=min⁡(1.00,1.12)=1.00d_{E\to(D,F)} = \min(d_{ED}, d_{EF}) = \min(1.00, 1.12) = 1.00

Min Distance (Single Linkage)

DistABCD, FE
A0.000.715.663.204.24
B0.710.004.952.503.54
C5.664.950.002.241.41
D, F3.202.502.240.001.00
E4.243.541.411.000.00

(Iteration 2) Merge the two closest clusters

X1X1X2X20022446600112233445566ABCDEF

Min Distance (Single Linkage)

DistABCD, FE
A0.000.715.663.204.24
B0.710.004.952.503.54
C5.664.950.002.241.41
D, F3.202.502.240.001.00
E4.243.541.411.000.00
DistA,BC(D, F)E
A,B0???
C?02.241.41
(D, F)?2.2401.00
E?1.411.000

(Iteration 2) Update the distance matrix

Min Distance (Single Linkage)

DistABCD, FE
A0.000.715.663.204.24
B0.710.004.952.503.54
C5.664.950.002.241.41
D, F3.202.502.240.001.00
E4.243.541.411.000.00
DistA,BC(D, F)E
A,B0???
C?02.241.41
(D, F)?2.2401.00
E?1.411.000
dC→(A,B)=min⁡(dCA,dCB)=min⁡(5.66,4.95)=4.95d_{C\to(A,B)} = \min(d_{CA}, d_{CB}) = \min(5.66, 4.95) = 4.95 d(D,F)→(A,B)=min⁡(dDA,dDB,dFA,dFB)=min⁡(3.61,2.92,3.20,2.50)=2.50\begin{aligned} d_{(D,F)\to(A,B)} &= \min(d_{DA}, d_{DB}, d_{FA}, d_{FB}) \\ &= \min(3.61, 2.92, 3.20, 2.50) = 2.50 \end{aligned} dE→(A,B)=min⁡(dEA,dEB)=min⁡(4.24,3.54)=3.54d_{E\to(A,B)} = \min(d_{EA}, d_{EB}) = \min(4.24, 3.54) = 3.54

Min Distance (Single Linkage)

DistA,BC(D, F)E
A,B04.952.503.54
C4.9502.241.41
(D, F)2.502.2401.00
E3.541.411.000

(Iteration 3) Merge two closest clusters and update distance matrix

X1X1X2X20022446600112233445566ABCDEF

Min Distance (Single Linkage)

Dist(A,B)C(D, F)E
(A,B)04.952.503.54
C4.9502.241.41
(D, F)2.502.2401.00
E3.541.411.000

Min Distance (Single Linkage)

Dist(A,B)C(D, F), E
(A,B)0.004.952.50
C4.950.001.41
(D, F), E2.501.410.00

(Iteration 4) Merge two clusters and update distance matrix

X1X1X2X20022446600112233445566ABCDEF

Min Distance (Single Linkage)

Dist(A,B)C(D, F), E
(A,B)0.004.952.50
C4.950.001.41
(D, F), E2.501.410.00

Min Distance (Single Linkage)

Dist(A,B)((D, F), E),C
(A,B)0.002.50
((D, F), E),C2.500.00

(Iteration 5) Final iteration, merge the last two clusters, termination condition We construct the Dendrogram tree of the cluster

lifetimeDFECAB1.02.00.51.52.52\mathbf{2}4\mathbf{4}5\mathbf{5}3\mathbf{3}6\mathbf{6}
  1. In the beginning we have 6 clusters: A, B, C, D, E and F
  2. We merge clusters D and F into cluster (D, F) at distance 0.50
  3. We merge cluster A and cluster B into (A, B) at distance 0.71
  4. We merge clusters E and (D, F) into ((D, F), E) at distance 1.00
  5. We merge clusters ((D, F), E) and C into (((D, F), E), C) at distance 1.41
  6. We merge clusters (((D, F), E), C) and (A, B) into ((((D, F), E), C), (A, B)) at distance 2.50
  7. The last cluster contain all the objects, thus conclude the computation
  • The Lifetime of a cluster, as the difference between the proximity level moment the cluster was created, and the proximity level of when it was merged with any of the other clusters.
    Taking the example of before: the lifetime of A, B, C, D, E, F are: 0.71, 0.71, 1.41, 0.50, 1.00, 0.50, and the lifetime of (A,B) is 2.50−0.71=1.792.50 - 0.71 = 1.79
  • The K-cluster lifetime is the distance from that K clusters merge to that of K clusters vanish due to the reduction to k-1 clusters

K-Mean clustering

link to demo Given a KK, find a partition of KK clusters to optimize the chosen partition criterion, in respect to a cost function. The KK-means algorithm is a heuristic method where each cluster is represented by the center of the cluster and the algorithm converges to stable centroids of clusters. It is the simplest and most used clustering analysis algorithm. It works by:

  1. Set centroids points randomly
  2. Assign each object to the cluster of the nearest seed point measured with a specific distance metric
  3. Compute new centroids points of the current partition
  4. GOTO step 1, stop when there is no more new assignment, so each clusters does not change This algorithm has a computational complexity of O(tKn)O(tKn) where n is the number of objects, K is the number of clusters, and t is the number of iterations

The problem with this algorithm is that it is sensitive to the initial seed points, and could fall into an unwanted local optimum. It also has the drawback of having to specify the number of clusters KK in advance, it can't handle (properly) noisy data and it is not suitable for clustering with non convex shapes. It is applicable only when the centroids are "definable"

Choosing the initial centroids

The chance of selecting one centroid from each cluster is really small, considering clusters of the same size then the probability of this is:

P=#ways to select one centroid from each cluster#ways to select K centroids=K!nK(Kn)K=K!KKP = \dfrac{\#ways \, to \, select \, one \,centroid \, from \,each \, cluster}{\#ways \, to \, select \, K \, centroids} = \dfrac{K!n^K}{(Kn)^K} = \dfrac{K!}{K^K}

which even for K = 10, the probability is 0.00036. Sometimes the centroids will readjust themselves, other times they wont.

This is an example of a good first centroid choice Pasted image 20231215152241.png While this is a bad example for the first centroid Pasted image 20231215152329.png There are ways to mitigate this, such as:

  • Using multiple runs, but the probability is not that much higher
  • Use hierarchical clustering to determine the initial centroids
  • Select more than KK initial centroids and then select the most widely separated ones, and apply some post processing to merge clusters together

K-Means limitations

Differing sizes

Pasted image 20231215153001.png Can be solved by using more k-means clusters and then merging them Pasted image 20231215153146.png

Differing density

Pasted image 20231215153024.png Can be solved by using more k-means clusters and merging them Pasted image 20231215153249.png

Non globular shapes

Pasted image 20231215153049.png Can be solved by using more k-means clusters and merging them Pasted image 20231215153304.png

K-means example

Suppose we have 4 kinds of medicines, each has two attributes (PH and weight index), our goal is to group those objects into K=2 groups of medicines. We start off with this data set:

MedicineWeightpH-Index
A11
B21
C43
D54
attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.5ABCD
  1. Use initial seed points for partitioning

iteration 0

attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.5ABCD

c1=A,c2=Bc_1 = A, c_2 = B

D0=[013.615102.834.24]c1=(1,1)group-1c2=(2,1)group-2D^0 = \begin{bmatrix} 0 & 1 & 3.61 & \textcolor{red}{5} \\ 1 & 0 & 2.83 & \textcolor{red}{4.24} \end{bmatrix} \quad \begin{aligned} c_1 &= (1,1) \quad \textit{group-1} \\ c_2 &= (2,1) \quad \textit{group-2} \end{aligned}

Euclidean distance

ABCD\begin{matrix} A & B & C & D \end{matrix} [12451134]XY\begin{bmatrix} 1 & 2 & 4 & 5 \\ 1 & 1 & 3 & 4 \end{bmatrix} \begin{matrix} X \\ Y \end{matrix} d(D,c1)=(5−1)2+(4−1)2=5d(D,c2)=(5−2)2+(4−1)2=4.24\begin{aligned} d(D, c_1) &= \sqrt{(5-1)^2 + (4-1)^2} = 5 \\ d(D, c_2) &= \sqrt{(5-2)^2 + (4-1)^2} = 4.24 \end{aligned}

Assign each object to the cluster with the nearest seed point

  1. Compute new centroids based off the current partitions

iteration 1

attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.5

Knowing the members of each cluster, now we compute the new centroid of each group based on these new memberships.

c1=(1, 1)c_1 = (1,\ 1) c2=(2+4+53, 1+3+43)=(113, 83)c_2 = \left(\dfrac{2+4+5}{3},\ \dfrac{1+3+4}{3}\right) = \left(\dfrac{11}{3},\ \dfrac{8}{3}\right)

Now modify the new membership of items based off the new centroids

iteration 1

attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.5ABCD12

Compute the distance of all objects to the new centroids

D1=[013.6153.142.360.471.89]c1=(1,1)group-1c2=(113,83)group-2D^1 = \begin{bmatrix} 0 & 1 & 3.61 & 5 \\ 3.14 & 2.36 & 0.47 & 1.89 \end{bmatrix} \quad \begin{aligned} c_1 &= (1,1) \quad \textit{group-1} \\ c_2 &= \left(\tfrac{11}{3}, \tfrac{8}{3}\right) \quad \textit{group-2} \end{aligned} ABCD\begin{matrix} A & B & C & D \end{matrix} [12451134]XY\begin{bmatrix} 1 & 2 & 4 & 5 \\ 1 & 1 & 3 & 4 \end{bmatrix} \begin{matrix} X \\ Y \end{matrix}

Assign the membership to objects

C1=?C_1 = ? \qquad C2=?C_2 = ?

  1. Repeat the first two steps until its convergence

iteration 2

attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.512

Knowing the members of each cluster, now we compute the new centroid of each group based on these new memberships.

c1=(1+22, 1+12)=(112, 1)c_1 = \left(\dfrac{1+2}{2},\ \dfrac{1+1}{2}\right) = \left(1\dfrac{1}{2},\ 1\right) c2=(4+52, 3+42)=(412, 312)c_2 = \left(\dfrac{4+5}{2},\ \dfrac{3+4}{2}\right) = \left(4\dfrac{1}{2},\ 3\dfrac{1}{2}\right)

iteration 2

attribute 1 (X): weight indexattribute 2 (Y): pH00112233445566000.50.5111.51.5222.52.5333.53.5444.54.5

Compute the distance of all objects to the new centroids

D2=[0.50.53.204.614.303.540.710.71]c1=(112,1)group-1c2=(412,312)group-2D^2 = \begin{bmatrix} 0.5 & 0.5 & 3.20 & 4.61 \\ 4.30 & 3.54 & 0.71 & 0.71 \end{bmatrix} \quad \begin{aligned} c_1 &= \left(1\tfrac{1}{2}, 1\right) \quad \textit{group-1} \\ c_2 &= \left(4\tfrac{1}{2}, 3\tfrac{1}{2}\right) \quad \textit{group-2} \end{aligned} ABCD\begin{matrix} A & B & C & D \end{matrix} [12451134]XY\begin{bmatrix} 1 & 2 & 4 & 5 \\ 1 & 1 & 3 & 4 \end{bmatrix} \begin{matrix} X \\ Y \end{matrix}

Stop due to no new assignment. Membership in each cluster no longer change

DB-Scan

link to demo It is a Density Based Clustering algorithm. It needs two parameters:

  • ϵ\epsilon to decide the size of the circle of each point whose nearby nodes are to be considered neighbors
  • MinNumMinNum which is the minimum number of points to consider a point as a rootroot point During the execution, points are labeled in one of three types:
  1. Core points: those are the points which have at least MinNumMinNum of points inside of it's ϵ\epsilon radius
  2. Boarder points: those are nodes which have a core point as neighbor but doesn't have enough neighbors to surpass the MinNumMinNum requirement
  3. Noise points: are points that don't have any ϵ\epsilon neighbors

It executes by finding the first core points and then propagating the classification

NABC

It has the advantage of:

  • not requiring the number of KK clusters
  • Can find any arbitrarily shaped clusters, even ones that are englobed by different clusters
  • It is robust against outliers
  • It is designed to be used in databases using R* trees

And disadvantages of:

  • It is not deterministic, a border point which is reachable from more than one cluster could be part of either, depending in which order the data is processed
  • The quality of the DBScan is dependent on the distance measure
  • It is not very good at clustering data sets with large differences in density Pasted image 20231215155703.png