Chosing optimal k and optimal distance-metric for k-means

Question

I have a data-set with roughly 20-dimensions and millions of points which I want to cluster.

The goal is to find a set of clusters which:

• Are as distinct as possible from each other (minimum coupling) between clusters, i.e. maximum average distance between centroids
• With instances as similar as possible (maximum cohesion) inside the clusters, i.e. minimum average distance between the points within each cluster.

Without considering the domain, is there a good metric to help determine the optimal $k$ I should choose?

Intuitively, I would pick $k=\sqrt{N}$ for a data-set in two dimensions, and $k=\sqrt[M]{N}$ for a data-set with $M$ dimensions and $N$ data-points, but I have a hunch that there are better methods.

A related and complementary question is which distance metric to use. Due to the curse of dimensionality, I know that euclidean distance becomes a poor choice as the number of dimensions increases.

Note that this question is different than Choosing optimal K for KNN (this one asks about clustering rather than k-NN classification)

Answer 1

There is plenty of literature on choosing k, such as the silhouette plot. This question has also been asked a dozen times.

• How to decide on the correct number of clusters?
• Determining number of clusters K-means
• Elbow criteria to determine number of cluster
• How to define number of clusters in K-means clustering?
• How to determine optimal number of clusters?

Same for your second question - asked several times before:

• Using k-means with other metrics
• Why does k-means clustering algorithm use only Euclidean distance metric?
• Distance function for categories in K-means
• Is it possible to specify your own distance function using scikit-learn K-Means Clustering?
• k-means implementation with custom distance matrix in input
• Perform K-means (or its close kin) clustering with only a distance matrix, not points-by-features data

Do not use k-means with other distance functions than sum-of-squares. It may stop converging. k-means is not distance based. It minimizes the very classic sum of squares. The mean function is an L2 estimator of centrality - if you want to use a different distance function, you need to choose cluster centers differently. This has been done, see k-medoids aka PAM.

Don't forget to spend a lot of time preprocessing your data and visualizing your results. People tend to neglect that, and get really bad results without noticing... again, see other questions here on k-means.