# How to determine which method is the most valid, reasonable clustering results?

Method 1: Cluster by K-means with initial centroid {27, 67.5}

Method 2: Cluster by K-means with initial centroid {22.5, 60}

Method 3: Agglomerative Clustering

How can I know which method gives a more reasonable or valid clustering results? What could be the approaches?

• What does it mean for one set of clustering results to be "more reasonable" than another? – gung - Reinstate Monica Nov 10 '13 at 4:26
• I should say which clustering method is preferable – user34582 Nov 10 '13 at 15:06
• – ttnphns Jun 24 '16 at 18:38

Wang, Kaijun, Baijie Wang, and Liuqing Peng. "CVAP: Validation for cluster analyses." Data Science Journal 0 (2009): 0904220071.:

To measure the quality of clustering results, there are two kinds of validity indices: external indices and internal indices.

An external index is a measure of agreement between two partitions where the first partition is the a priori known clustering structure, and the second results from the clustering procedure (Dudoit et al., 2002).

Internal indices are used to measure the goodness of a clustering structure without external information (Tseng et al., 2005).

For external indices, we evaluate the results of a clustering algorithm based on a known cluster structure of a data set (or cluster labels).

For internal indices, we evaluate the results using quantities and features inherent in the data set. The optimal number of clusters is usually determined based on an internal validity index.

(Dudoit et al., 2002): Dudoit, S. & Fridlyand, J. (2002) A prediction-based resampling method for estimating the number of clusters in a dataset. Genome Biology, 3(7): 0036.1-21.

(Tseng et al., 2005): Thalamuthu, A, Mukhopadhyay, I, Zheng, X, & Tseng, G. C. (2006) Evaluation and comparison of gene clustering methods in microarray analysis. Bioinformatics, 22(19):2405-12.

In your case, you need some internal indices since you have no a priori clustering structure. There exist tens of internal indices, like:

• Silhouette index (implementation in MATLAB)
• Davies-Bouldin
• Calinski-Harabasz
• Dunn index (implementation in MATLAB)
• R-squared index
• Hubert-Levin (C-index)
• Krzanowski-Lai index
• Hartigan index
• Root-mean-square standard deviation (RMSSTD) index
• Semi-partial R-squared (SPR) index
• Distance between two clusters (CD) index
• weighted inter-intra index
• Homogeneity index
• Separation index

Each of them have pros and cons, but at least they'll give you a more formal basis for your comparison. The MATLAB toolbox CVAP might be handy as it contains many internal validity indices.

# The sound method

... is to ask an expert. There is no objective mathematical criterion. Each has drawbacks. And probably the best criterion is to have an expert say "wow, this is interesting. let me check ... yes, this is right, I didn't know".

# The reference method

If you have annotated data, you can compare the algorithm output to these annotations. This if referred to as external validation, and there are a number of measures such as the Adjusted Rand Index (ARI).

# The optimization criterion method

Furthermore, you can test whether some mathematical property is improved, such as the within-cluster sum-of-squares. This is easiest, as you do not need to have labeled data. But it can also be very misleading, because it is biased by how measures and algorithms are related to each other.

For example, if you use the within-cluster sum-of-squares, k-means WILL be best (by definition of k-means), and it will improve with k. But the results tend to get more and more meaningless.

This approach has a risk of overfitting and bias, but it can reasonably be used to rank different results based on the same assumptions (in particular, using the same algorithm)

# Conclusions

1. If you can afford to do so, ask an expert.

2. If you have labeled data and compare different algorithms, use external validation

3. If you compare the same algorithm (e.g. multiple runs, or different parameters), choosing an internal measure that is not correlated with the algorithm may work well. For example, comparing different k-means results using the Silhouette coefficient.