Articles - Cluster Validation Essentials

Choosing the Best Clustering Algorithms

Choosing the best clustering method for a given data can be a hard task for the analyst. This article describes the R package clValid (Brock et al. 2008), which can be used to compare simultaneously multiple clustering algorithms in a single function call for identifying the best clustering approach and the optimal number of clusters.

We’ll start by describing the different measures in the clValid package for comparing clustering algorithms. Next, we’ll present the function clValid(). Finally, we’ll provide R scripts for validating clustering results and comparing clustering algorithms.


Contents:


Related Book:

Measures for comparing clustering algorithms

The clValid package compares clustering algorithms using two cluster validation measures:

  1. Internal measures, which uses intrinsic information in the data to assess the quality of the clustering. Internal measures include the connectivity, the silhouette coefficient and the Dunn index as described in Chapter @ref(cluster-validation-statistics) (Cluster Validation Statistics).

  2. Stability measures, a special version of internal measures, which evaluates the consistency of a clustering result by comparing it with the clusters obtained after each column is removed, one at a time.

Cluster stability measures include:

  • The average proportion of non-overlap (APN)
  • The average distance (AD)
  • The average distance between means (ADM)
  • The figure of merit (FOM)

The APN, AD, and ADM are all based on the cross-classification table of the original clustering on the full data with the clustering based on the removal of one column.

  • The APN measures the average proportion of observations not placed in the same cluster by clustering based on the full data and clustering based on the data with a single column removed.

  • The AD measures the average distance between observations placed in the same cluster under both cases (full data set and removal of one column).

  • The ADM measures the average distance between cluster centers for observations placed in the same cluster under both cases.

  • The FOM measures the average intra-cluster variance of the deleted column, where the clustering is based on the remaining (undeleted) columns.

The values of APN, ADM and FOM ranges from 0 to 1, with smaller value corresponding with highly consistent clustering results. AD has a value between 0 and infinity, and smaller values are also preferred.

Note that, the clValid package provides also biological validation measures, which evaluates the ability of a clustering algorithm to produce biologically meaningful clusters. An application is microarray or RNAseq data where observations corresponds to genes.

Compare clustering algorithms in R

We’ll use the function clValid() [in the clValid package], which simplified format is as follow:

clValid(obj, nClust, clMethods = "hierarchical", 
        validation = "stability", maxitems = 600,
        metric = "euclidean", method = "average")
  • obj: A numeric matrix or data frame. Rows are the items to be clustered and columns are samples.
  • nClust: A numeric vector specifying the numbers of clusters to be evaluated. e.g., 2:10
  • clMethods: The clustering method to be used. Available options are “hierarchical”, “kmeans”, “diana”, “fanny”, “som”, “model”, “sota”, “pam”, “clara”, and “agnes”, with multiple choices allowed.
  • validation: The type of validation measures to be used. Allowed values are “internal”, “stability”, and “biological”, with multiple choices allowed.
  • maxitems: The maximum number of items (rows in matrix) which can be clustered.
  • metric: The metric used to determine the distance matrix. Possible choices are “euclidean”, “correlation”, and “manhattan”.
  • method: For hierarchical clustering (hclust and agnes), the agglomeration method to be used. Available choices are “ward”, “single”, “complete” and “average”.

For example, consider the iris data set, the clValid() function can be used as follow.

We start by cluster internal measures, which include the connectivity, silhouette width and Dunn index. It’s possible to compute simultaneously these internal measures for multiple clustering algorithms in combination with a range of cluster numbers.

library(clValid)
# Iris data set:
# - Remove Species column and scale
df <- scale(iris[, -5])
# Compute clValid
clmethods <- c("hierarchical","kmeans","pam")
intern <- clValid(df, nClust = 2:6, 
              clMethods = clmethods, validation = "internal")
# Summary
summary(intern)
##  Length   Class    Mode 
##       1 clValid      S4

It can be seen that hierarchical clustering with two clusters performs the best in each case (i.e., for connectivity, Dunn and Silhouette measures). Regardless of the clustering algorithm, the optimal number of clusters seems to be two using the three measures.

The stability measures can be computed as follow:

# Stability measures
clmethods <- c("hierarchical","kmeans","pam")
stab <- clValid(df, nClust = 2:6, clMethods = clmethods, 
                validation = "stability")
# Display only optimal Scores
optimalScores(stab)
##       Score       Method Clusters
## APN 0.00327 hierarchical        2
## AD  1.00429          pam        6
## ADM 0.01609 hierarchical        2
## FOM 0.45575          pam        6

For the APN and ADM measures, hierarchical clustering with two clusters again gives the best score. For the other measures, PAM with six clusters has the best score.

Summary

Here, we described how to compare clustering algorithms using the clValid R package.

References

Brock, Guy, Vasyl Pihur, Susmita Datta, and Somnath Datta. 2008. “ClValid: An R Package for Cluster Validation.” Journal of Statistical Software 25 (4): 1–22. https://www.jstatsoft.org/v025/i04.