Evaluation of k-means output for >3D I'm implementing the k-means algorithm (in R Map-Reduce) and I wanted to verify if the output I'm getting is close enough to the true centroids of the cluster. This is how I'm verifying with a 2D dataset currently:
I plot both the dataset and the centroids I've got as output and see if the centroids are close to the centre of the clusters visually. I think I can do that for 3D data too. But I don't know how to verify this with higher dimensional data that cannot be plotted.
It looks really stupid to plot the data and visually verify each time, right? So let me tell you why I'm doing this:

The centroids don't come in a particular order. The 1st centroid in this trial might be in the 2nd position in the next, so I can't find the distance between the matrix of my output and the matrix of, say, the R's default kmeans output (if I'm verifying my output with R's kmeans). Sorting with respect to any one dimension to compare sounds stupid, since any dimension can be a lot more sensitive to the data when compared to another.

So, for now, I'm verifying 2D data visually. Do I have to use dimensionality reduction? Does someone have ideas about how I can verify higher dimension data?
 A: You can give the induced clusters some arbitrary labeling (as A, B, C) and give the true clusters a labeling (say 1, 2, 3). And plot the "classification" in a confusion matrix. You'll get something like this
$$ \left( \begin{array}{c|ccc}
 & A & B & C \\
\hline
1 & 0.01 & 0.2 & 0.79 \\
2 & 1 & 0 &  0 \\
3 & 0.08 & 0.92 & 0 \end{array} \right)$$ 
If the clustering algorithm performs well, you won't get high values on the diagonal, but you will see an obvious way to relabel to put the high values on the diagonal. 
If this isn't enough of an indication by itself, you can use a measure based on the confusion matrix (symmetric error, precision/recall) and just use the relabeling that optimizes that value. If the algorithm performs well, then the optimal relabeling is obvious anyway, and if it doesn't, then taking the optimal relabeling won't help performance.
The cluster analysis page on wikipedia has some other methods for evaluating a clustering against a gold standard, but I think this one fits your use case best.
A: How about computing the distances between the means in one result and the means of the other result, compared to the total variance?
But note that running k-means in R with different random seeds / initial means will yield different results on nontrivial data.
