2 added 42 characters in body edited Mar 28 '16 at 8:53 ttnphns 40.8k1717 gold badges154154 silver badges340340 bronze badges I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances [between data points and cluster centres]. The only comment from the documentation I can see about that is: Distance measure, in p-dimensional space, used for minimization, specified as the comma-separated pair consisting of 'Distance' and a string. kmeans computes centroid clusters differently for the different, supported distance measures. This table summarizes the available distance measures. In the formulae, x is an observation (that is, a row of X) and c is a centroid (a row vector). Then a list of functions of c and x follows. Thus, considering that p is the dimensionality of the input data, it seems that no Euclidean embedding is performed beforehand. BTW in the past I've been using Matlab's k-means with correlation distance and it (unsurprisingly) did what it was supposed to do. I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances. The only comment from the documentation I can see about that is: Distance measure, in p-dimensional space, used for minimization, specified as the comma-separated pair consisting of 'Distance' and a string. kmeans computes centroid clusters differently for the different, supported distance measures. This table summarizes the available distance measures. In the formulae, x is an observation (that is, a row of X) and c is a centroid (a row vector). Then a list of functions of c and x follows. Thus, considering that p is the dimensionality of the input data, it seems that no Euclidean embedding is performed beforehand. BTW in the past I've been using Matlab's k-means with correlation distance and it (unsurprisingly) did what it was supposed to do. I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances [between data points and cluster centres]. The only comment from the documentation I can see about that is: Distance measure, in p-dimensional space, used for minimization, specified as the comma-separated pair consisting of 'Distance' and a string. kmeans computes centroid clusters differently for the different, supported distance measures. This table summarizes the available distance measures. In the formulae, x is an observation (that is, a row of X) and c is a centroid (a row vector). Then a list of functions of c and x follows. Thus, considering that p is the dimensionality of the input data, it seems that no Euclidean embedding is performed beforehand. BTW in the past I've been using Matlab's k-means with correlation distance and it (unsurprisingly) did what it was supposed to do. 1 answered Mar 23 '16 at 14:21 Francesco Napolitano 20122 silver badges22 bronze badges I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances. The only comment from the documentation I can see about that is: Distance measure, in p-dimensional space, used for minimization, specified as the comma-separated pair consisting of 'Distance' and a string. kmeans computes centroid clusters differently for the different, supported distance measures. This table summarizes the available distance measures. In the formulae, x is an observation (that is, a row of X) and c is a centroid (a row vector). Then a list of functions of c and x follows. Thus, considering that p is the dimensionality of the input data, it seems that no Euclidean embedding is performed beforehand. BTW in the past I've been using Matlab's k-means with correlation distance and it (unsurprisingly) did what it was supposed to do.