Why is the clustering cost function called "distortion"?

Question

Andrew Ng's excellent ML course on Coursera describes the k-means clustering algorithm and its cost function (roughly, the points' distance from their cluster centre), which he says is called "distortion". Why is it called that?

Answer 1

Eureka! For a two-dimensional analogy, imagine a horizontal rubber sheet that is fixed at certain points representing the input samples. Get hold of the sheet at one of the cluster centroids and stretch or "distort" it by pulling that point horizontally away from the true centroid. The amount of distortion you introduce is like the cost function that the clustering algorithm tries to minimise.

Answer 2

Do you ask for a definition? A colloquial answer would be, it is called distortion, because the information, where the dominating centroid lies, is hidden or 'defeatured' at first. By using kmeans, you are trying randomly different clusters to get some 'order' (not a real order) to the chaos you see. You have a lot of unlabelled data points, and to bring light to the dark (distortion) you try to minimize this, by choosing a starting centroid and shift and shift and shift until kmeans see no longer purpose on shifting the centroid.

A more scientific definition:

The k-means algorithm tries to minimize distortion, which is defined as the sum of the squared distances between each observation vector and its dominating centroid. Each step of the k-means algorithm refines the choices of centroids to reduce distortion. The change in distortion is used as a stopping criterion: when the change is lower than a threshold, the k-means algorithm is not making sufficient progress and terminates. One can also define a maximum number of iterations.

https://docs.scipy.org/doc/scipy-0.14.0/reference/cluster.vq.html