Chosing optimal k and optimal distance-metric for k-means 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)
 A: 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.
