Using AIC to Measure Clustering Quality, how many k to account for Variance Parameter(s)?

Question

I have written a custom clustering function which takes a vector of initial position estimates of k cluster centres (a 1 dimensional vector). Internally the function then "calibrates" the final clustering result using a minimum distance measure over weighted data, based on this input. Each cluster centre k has its own variance associated with the points it clusters. There is no random initialisation and between cluster distance/disimilarity is irrelevant although, conceptually, the function can be thought of as being similar to kmeans in 1 dimension. The initial position estimate is the model.

I would like to use AIC to select the best of several different possible initial position estimates (models) post calibration, but I am confused as to how I should count the parameters k for the model AIC score. Obviously each given cluster centre counts as 1 parameter, but what about the variance? If I have, e.g. 5 cluster centres, do I count parameters for AIC as 5 plus 1 for a total global variance, or 5 plus 5 for individual variances?

Answer 1

This depends on whether your clustering procedure uses individually different variances from all centres, in which case you need to use the number of individual variances. Note that this is not k-means in 1-d; k-means implicitly assumes that all variances (or in higher d covariance matrices) are the same. If you do it like this (i.e., if you compute the clustering without actually using the different individual variances), you don't even have to count a single variance parameter, because the clustering doesn't rely on it.

That said, k-means-like procedures are not based on statistical mixture models but on models in which the cluster assignment of every observation can be seen as an individual discrete parameter. My experience (and probably also the experience of others; BIC is usually preferred to AIC in clustering and even BIC may choose the number of clusters too high easily) is that AIC doesn't work very well in such a setting. Surely any theoretical justification of AIC will not apply.