# Corrected AIC (AICC) for k-means

I want to calculate the $AIC_c$ (corrected $AIC$) for k-means to decide on the number of clusters, but there is an overfitting problem that I don't know how to solve. Let's say that I have $n$ data points of $d$ dimensions each, and I want to cluster those $n$ points into $c$ clusters. The Akaike Information Criterion ($AIC$) is $-2ln(L)+ 2k$ where $k$ is the number of free parameters, and for k-means, it is $c(d+1)$. And for $AIC_c$, the formula becomes $-2ln(L)+ 2kn/(n-k-1)$.

Now, let's say $n=1000$, $d=200$, $c=10$, then the number of parameters is $k=2010$. Then the denominator in the penalty term of $AIC_c$ becomes negative, which means a negative penalty in the formula. And when $c$ increases, the penalty decreases, resulting in $AIC_c$'s supporting the models with the maximum number of clusters (when $c=n$).

I think I am missing or I have misunderstood a point about $AIC_c$. What is that? Thanks in advance.

• The point is that they don't use AICc for k-means. AICc was designed mostly for regression modeling. K-means clustering is not regression problem and is not a modeling at all, in the straightforward sense. You may still use AIC, though. – ttnphns Feb 9 '14 at 6:04
• Kmeans is Gaussian mixtures with assumed equal covariances across all clusters, so the covariances are excluded from the parameters. So this means that each cluster now only has a weight (its a pdf, so it has to sum to 1.0) and a mean. I would think this means that k = count_of_weights + count_of_means*number_of_dimensions. – EngrStudent Oct 12 '18 at 13:59

The form of $AICc$ of

$$AICc = AIC + \frac{2k(k+1)}{n-k-1}$$

was proposed by

Hurvich, C. M.; Tsai, C.-L. (1989), "Regression and time series model selection in small samples", Biometrika 76: 297–307

specifically for a linear regression model with normally distributed errors. For different models, a different correction will need to be derived.

These derivations are often difficult and the resulting correction may be challenging to calculate. For instance

Hurvich, Clifford M., Jeffrey S. Simonoff, and Chih‐Ling Tsai. "Smoothing parameter selection in nonparametric regression using an improved Akaike information criterion." Journal of the Royal Statistical Society: Series B (Statistical Methodology) 60, no. 2 (1998): 271-293.

propose a correction to be used in the case of nonparametric regression models which takes the form

$$AICc = -2ln(L) + n^2\int_0^1(1-t)^{r/2-2}\prod_{j=1}^{r}(1-t+2d_j)^{-1/2}dt+n\int_0^{\infty}\sum_{i=1}^n\frac{c_{ii}}{1+2d_it}\prod_{i=1}^n(1+2d_it)^{-1/2}dt$$

I will not go into the details here as they are largely irrelevant but I wanted to illustrate the complexity involved. Actual calculation of this value involves eigen-analysis and numerical integration.

For reasons like this, many authors such as

Burnham, K. P.; Anderson, D. R. (2002), Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach (2nd ed.), Springer-Verlag, ISBN 0-387-95364-7

suggest to use the form

$$AICc = AIC + \frac{2k(k+1)}{n-k-1}$$

regardless of model. Even Hurvich et al. (1998) despite deriving their complicated $AICc$ for nonparametric regression ultimately conclude that you might as well use the much simpler version for linear regression.

Generally this advice seems to work well, giving practically useful results. However there are circumstances, such as the one you've highlighted where it doesn't work. You would need to find an appropriate $AICc$ for k-means, or derive one yourself, or simply use $AIC$ which is more generally applicable.

• Thanks a lot for the explanation. $AIC$ selects a higher value for $c$ than I expected (and needed). And since $AIC_c$ is suggested when $n<<k$, I wanted to use $AIC_c$ hoping that it would penalize the models with high number of parameters more than $AIC$ does. But learning that it would not work for k-means is very good to know. I also tried $BIC$, but opposite to $AIC$, it selects a smaller $c$ than I expected. Are there any other criterion that you suggest using? (I would not prefer cross-validation since my data is much bigger than the one I gave as the example.) – user5054 Feb 10 '14 at 5:08
• @user5054 It sounds like you have certain expectations about the "true" number of clusters in the data set. Is there some reason you need to use a model selection criterion at all? – M. Berk Feb 10 '14 at 8:56
• I am doing a biological application (clustering genes into pathways), and biologically, 40-50 genes in a pathway is reasonable. However, I cannot explain this in terms of application purposes to a machine learning or statistics person (paper reviewer). In order to convince them that I chose the cluster count in a fair way, I need to use some statistical criterion to choose the model order. That's why I need a criterion that would choose the "reasonable" cluster count :) – user5054 Feb 10 '14 at 11:10
• @user5054 There are other approaches you could consider such as scree/elbow plot or gap statistic. However, I think you should be able to successfully argue that "We chose the number of clusters which yielded the most biologically consistent results". Especially if the ideal number of clusters by your interpretation has almost the optimal AIC... – M. Berk Feb 10 '14 at 11:32
• ...It is not always the best idea to blindly take the model which has the optimal AIC - other considerations are important including interpretability. To help argue your case, I would definitely point out that AIC only holds asymptotically and your sample size is small. If you show an appreciation for these statistical nuances then you should be able to satisfy the reviewer. – M. Berk Feb 10 '14 at 11:33