We had a case where we wanted to use Levenshtein distance instead of the usual euclidean_distances. We ended monkey-patching the cluster module.

I think it'll be nice to add another parameter to KMeans class which is a user defined distance function. If it's not defined then the code will default to usual euclidean_distances.