This is a question about k-means clustering algorithm. I have the following points and clustering of data S1. Can anyone tell me how to calculate the total error associated with this clustering? I know it's not a strictly programming question, but I need it for my algorithm. I think the answer should be 4/3 but I have no idea how to calculate this. Can anyone help me?
x1= (2.0,1.0)
x2= (2.0,2.0)
x3= (1.0,2.0)
S1={ x1, x2, x3 }
There are many ways to calculate the error. Here's one.
First calculate the centroid of the set, C1 = (x1+x2+x3)/3. Then calculate the error as the sum of the distances from the centroid: E1 = d(C1-x1) + d(C1-x2) + d(C1-x3).
I had to search for something similar in the past couple of weeks. As with most things, finding the correct name helped greatly. You are looking for a Cluster Validity Index. I found a useful source for algorithms (and related maths) to be Chapter 17 of "Data Clustering Theory, Algorithms, and Applications" by Gan, Ma, and Wu. Not cheap at $100+ from Amazon but I will find the rest of the book useful. Although it covers a lot of these indices, it lacks a good discussion of the strengths and weaknesses, so you need some online searching.
In the end I tried the Davies Bouldin Index and Dunn's Index. Dunn worked better but was very slow to compute to I settled on a simplified version which used centroid-centroid distances (rather than component point-point distances) and max radius from centroid, rather than true diameter. So far this is working well for me.
most of the various indices use measures of cluster size and separation.