# Are there cluster evaluation measures that when plotted against k, are monotonic on either side of the global maxima or minima?

I want to find the optimal number of clusters (k) for some clustering algorithm (agglomerative hierarchical, if that matters). I want to evaluate the quality of clustering based on some metric for each possible cluster (k=1, 2, 3, ...). Since the number of possible k's can be as large as the number of data points, it is not practical to check the evaluation metric for each k. Therefore, if there exists a metric which when plotted against k, is independently monotonic on either side of the most "optimal" k (i.e., the k for which the metric's value is highest), then it would be possible to ask the question, "Can we reduce the search space for k?". That is, instead of evaluating the metric for all k, is it possible to identify a subset or neighbourhood where the best k is guaranteed to be present?

If such a metric exists, the graph would look something like this:

I tried different metrics that I could find by online search: C-index, Dunn index, Davies-Bouldin index, Calinski-Harabasz index, Silhouette Width. But none of them have guarantee on independent monotonicity on either side of the optimal k for ALL datasets - maybe some of them behave like this on some data, but not on other data. For example:

So, does such a metric exist? Or is it possible to construct one?

• 1) No such indices exist because the curve shape depends on the data. 2) No such index is needed because it is normal to expect that in your dataset may, say, k=4 is the best, k=6 is much worse, but k=7 is again better. There can be more than one internally good clustering solutions with different k. 3) Internal clustering criterions are heuristic devices. Pay attention to elbows also or rather than to absolute maxima (or minima). Jun 28, 2017 at 9:53
• (cont.) 4) Typically, we want few clusters. Clustering criterions such as AIC or BIC explicitly penalize for excessive k; they also tend to produce quite smooth curves - that might please you, perhaps. Jun 28, 2017 at 9:54
• @ttnphns I see. How about external evaluation criteria? Could they be constructed to guarantee independent monotonicity on either side of the best k? Jun 28, 2017 at 9:58
• External validation is another approach in cluster validation, it is "supervised". So strange why you decided now to move from one to another. Jun 28, 2017 at 10:02
• The very question of yours is strange. It is silly, I'd say, to think there is always must be one best k in a cluster structure, except when clusters are very clear and far apart - which is very seldom in practice. Jun 28, 2017 at 10:08