The k-means implemented in scikit-learn precomputes distances but I don't how these distances are used. In its standard version, k-means is known to compute only the distances between the points and the centers. I am wondering if a pariwise distance matrix is useful to k-means.

Thank you for your help.

  • 1
    $\begingroup$ This was actually answered here stats.stackexchange.com/q/81481/3277 (see also further links there in) $\endgroup$ – ttnphns Jul 23 '18 at 9:22
  • $\begingroup$ @ttnphns do you mean this bit: "It is possible to program K-means in a way that it directly calculate on the square matrix of pairwise Euclidean distances, of course. But it will work slowly, and so the more efficient way is to convert the distances into scalar products and then create data for that distance matrix - the pass that is described in the previous paragraph - and then apply standard K-means procedure to that dataset"? I think this warrants further explanation, it's not intuitive to me (a) why the scalar products are needed and (b) how the precomputed distances are used for this. $\endgroup$ – Dan Jul 24 '18 at 14:59
  • $\begingroup$ This concrete topic is away from clustering field. It is Multidimensional Scaling. It takes matrix of distances or dissimilarities (not anyhow "precomputed" - you mistook it) and creates data (space coordinates) for these points. Naturally, one can use this dataset (points x "features") as input to usual k-means procedure. So, in order to answer you last questions yourself just follow my link (in my answer) explaining some sides of Torgerson's MDS. $\endgroup$ – ttnphns Jul 24 '18 at 15:16