# Why is clustering data with many categorical variables so slow?

I am trying to cluster a set of 160 points using 260,000 categorical variables (each variable has three possible values). I am trying to use the k-modes algorithm from the klaR package in R. It works fine when I use only several thousand categorical variables, but it takes about 2.5 min per 1000 categorical variables used (for 10 iterations, which is the default). So it would probably take something like 11 hours to run, if I tried to use all the variables. Do you consider this calculation time normal? Why would it be so slow?

• Do you consider this calculation time normal? Well, 260 thousand features isn't trifle... – ttnphns Aug 9 '15 at 19:44

(Note that this isn't my area of specialty, but I think I can guess what is going on here.)

The $k$-modes algorithm is a simple extension of the $k$-means algorithm. In each iteration a new set of modes is selected, and the distance of every row in your dataset to every mode needs to be calculated. If you have $160$ rows and you try to partition them into $2$ clusters, that is $320$ distance calculations for each iteration (i.e., $3,\!200$ total). If the distance calculations are slow (because you have $260,\!000$ columns), that's going to take up a lot of time.

An alternative is to use a clustering algorithm that can operate over a distance matrix. Then you can calculate the distances only once. If you are looking for something that is analogous to $k$-modes / $k$-means, the $k$-medians / Partitioning Around Medoids (PAM) algorithm may be a reasonable choice for you. Using Gower's distance with all columns coded as nominal and all distances calculated as symmetrical will give you the same simple matching distance that $k$-modes uses. Since the modes in your dataset are highly likely to be sets of values that correspond to an existing row, the results are actually likely to be identical to what you would have gotten via $k$-modes.

Here is a quick R demonstration of the time savings:

library(cluster)  # we'll use these packages
library(klaR)

set.seed(8417)    # this makes the simulation exactly reproducible
data = as.data.frame(matrix(rbinom(30*90, size=1, prob=.5), nrow=30))

system.time(pam(daisy(data, metric="gower", type=list(symm=1:90)), k=2))
# user  system elapsed
# 0.01    0.00    0.02
system.time(kmodes(data, modes=2))
# user  system elapsed
# 0.91    0.00    0.90


I have a rather thorough demonstration of this sort of clustering here: How to use both binary and continous variables together in clustering?