1 of 29

�

Data Mining_Anoop Chaturvedi

1

Swayam Prabha

Course Title

Multivariate Data Mining- Methods and Applications

Lecture 30

Partition around medoids (PAM) Clustering Algorithm

By

Anoop Chaturvedi

Department of Statistics, University of Allahabad

Prayagraj (India)

Slides can be downloaded from https://sites.google.com/view/anoopchaturvedi/swayam-prabha

2 of 29

Chaining in clustering ⇒ A series of connected clusters resembling a chain

Occurs when the clustering algorithm is not able to properly distinguish between different clusters.

What causes Chaining?

Data points are densely packed or if there is significant overlap between clusters.
Inappropriate choice of number of clusters, distance metric, linkage method, etc.
Presence of noise or outliers in the data.

Data Mining_Anoop Chaturvedi

2

3 of 29

Solutions

Adjust clustering parameters (number of clusters, distance matric, linkage etc.
Normalize or standardize the data, remove outliers, or apply dimensionality reduction techniques to simplify the data structure
Test different clustering algorithms. Select one that best suits the data distribution and effectively separates clusters without chaining.

Data Mining_Anoop Chaturvedi

3

4 of 29

PAM Clustering Algorithm

PAM ⇒ Partition around medoids

It is a modification of K-medoids/K-mean clustering algorithm.

A medoid is a most centrally located data point in the Cluster or whose average dissimilarity to all the objects is minimal.

Unlike centroids, which may not necessarily be actual data points, medoids are always real data points in the dataset.

Algorithm searches for K “representative objects” (or medoids) among the items in the data set.

Data Mining_Anoop Chaturvedi

4

5 of 29

Data Mining_Anoop Chaturvedi

5

6 of 29

Data Mining_Anoop Chaturvedi

6

7 of 29

Data Mining_Anoop Chaturvedi

7

8 of 29

Data Mining_Anoop Chaturvedi

8

9 of 29

Data Mining_Anoop Chaturvedi

9

10 of 29

Data Mining_Anoop Chaturvedi

10

11 of 29

Data Mining_Anoop Chaturvedi

11

12 of 29

Data Mining_Anoop Chaturvedi

12

13 of 29

"Ward.D" and "Ward.D2“: Specific methods for calculating the distance between clusters in hierarchical clustering.

Ward.D ⇒ Distance between clusters is calculated using the increase in the sum of squared distances resulting from merging two clusters. This increase is known as the "error sum of squares" (ESS). Generally produces more compact clusters

Ward.D2 ⇒ Distance between clusters is computed as the increase in the sum of squared distances divided by the total number of observations in the merged clusters. Clusters are easier to differentiate.

Data Mining_Anoop Chaturvedi

13

14 of 29

Example: Wards Clustering for IRIS data⇒ Dendrogram

Data Mining_Anoop Chaturvedi

14

15 of 29

Data Mining_Anoop Chaturvedi

15

16 of 29

Data Mining_Anoop Chaturvedi

16

Alternate visualization: Plot the similarities and differences in two-dimensional space.

Two components (sepal length, sepal width) express 95.81% of the point variability. One can try different combinations.

17 of 29

Assignment of clusters to data points

Data Mining_Anoop Chaturvedi

17

18 of 29

Data Mining_Anoop Chaturvedi

18

19 of 29

k-means clustering

Needs to prespecify the number of clusters.

But How?

Use criterion such as BIC, and “elbow method”, along with other plots to select appropriate number of clusters.

Covariance types:

Covariance matrix describes the geometry (volume, shape, orientation) of the clusters.

Data Mining_Anoop Chaturvedi

19

20 of 29

For allowing the flexibility in clustering following constraints are added to the covariance matrix

Constrains:

Volume ⇒ Each cluster has approximately same number of observations

Shape ⇒ Each cluster has approximately the same variance (distribution is spherical)

Orientation ⇒ Each cluster is axis-aligned.

Various covariance parameters capture unique clustering structures in data.

Data Mining_Anoop Chaturvedi

20

21 of 29

Data Mining_Anoop Chaturvedi

21

Model	Family	Volume	Shape	Orientation	Identifier
1	Spherical	Equal	Equal	NA	EII
2	Spherical	Variable	Equal	NA	VII
3	Diagonal	Equal	Equal	Axes	EEI
4	Diagonal	Variable	Equal	Axes	VEI
5	Diagonal	Equal	Variable	Axes	EVI
6	Diagonal	Variable	Variable	Axes	VVI
7	General	Equal	Equal	Equal	EEE
8	General	Equal	Variable	Equal	EVE
9	General	Variable	Equal	Equal	VEE
10	General	Variable	Variable	Equal	VVE
11	General	Equal	Equal	Variable	EEV
12	General	Variable	Equal	Variable	VEV
13	General	Equal	Variable	Variable	EVV
14	General	Variable	Variable	Variable	VVV

The table gives parameterizations of the covariance matrix based on various combinations of the above constraints:

22 of 29

Data Mining_Anoop Chaturvedi

22

23 of 29

Uncertainty plot and Density plots

Component assignment for each observation based on the largest probability.
Observations near the center indicate small uncertainty (high probability) of being from that cluster.
Observations far from the center indicate more uncertainty (low probability) of being from that cluster.

Data Mining_Anoop Chaturvedi

23

24 of 29

Uncertainty Plot:

Data Mining_Anoop Chaturvedi

24

25 of 29

Density plot:

Data Mining_Anoop Chaturvedi

25

26 of 29

Selecting Number of Clusters:

Total within-cluster sum of square (wss) ⇒Measures compactness of the clustering

Algorithm to define the optimal clusters:

Compute clustering algorithm for different values of k
Calculate WSS for each k
Plot WSS against number of clusters k.
Location of a bend (knee) in the plot is an indicator of the appropriate number of clusters.

Data Mining_Anoop Chaturvedi

26

27 of 29

Data Mining_Anoop Chaturvedi

27

28 of 29

Average Silhouette Method

Measures how well each object lies within its cluster, i.e., the quality of a clustering.

High average silhouette width ⇒ Good clustering.

Average silhouette computes the average silhouette of observations for different values of k.

Optimal number of clusters k is the one that maximizes the average silhouette over a range of possible values for k.

Data Mining_Anoop Chaturvedi

28

29 of 29

Data Mining_Anoop Chaturvedi

29