# Predicting SSE in k-means clustering

Given any number of clusters, is it possible to estimate the Sum of Squares Error (SSE) for the Clusters after adding noise to the clustering?

The type of noise generated will be supplied as a parameter. Any method(s) must be able to cater for Gaussian and Uniform noise.

• Do you simply want to calculate SSE or also different types of measures for the Cluster Cohesion? A quick idea might be to obtain a sample from you data and calculate the SSE (or other measure) based on that sample - would such an approach be ok? A better description of what you want to achieve would help - do you want an estimate before actually identifying the clusters? or do you want a performance speed up? May 7 '12 at 10:55
• My problem is I got the data points clustered and calculated the SSE. I added one noise point. I wish to predict the SSE after adding the noise point, without calculating. With this, I come to know, how far the noise point is influencing the cluster cohesion. Can you please help on this.. May 8 '12 at 6:36
• So your question should read: What is the expected value of the SSE after adding a single noise point? (Of course you will have to specify what type of noise you will use. Am I understanding you correctly? May 8 '12 at 8:38
• yes, you are right. I will give as input, how many noise points to add and what are they... May 9 '12 at 5:39

After your latest comment I would opt for a Monte-Carlo estimate. What you would do is create the noise you want (a large number of times) randomly and then create an estimate of the expected value of the SSE after noise based on your results.

Some links that can get you started on Monte-Carlo simulation and estimates:

Edit

In response to the OP's comment.

What you do in order to get an estimate using the Monte Carlo is to actually add the amount of noise of the type you require an check the change in the SSE.

You repeat this again, and get another value for the change in the SSE.

You keep on repeating several times (perhaps a few thousands, maybe a few hundreds of thousands or even more) and you start to notice that the mean of the change in the SSE will start to converge to some value. This value is your expected mean.

The advantages of using the Monte Carlo approach is that it is easy to understand (at least to the level you require) and implement while giving you good results and it is flexible enough to allow you to modify the initial problem and reuse (after performing the test again from scratch!).

The only downside is that you need to calculate the change in SSE many times - but with today's computational power I do not foresee that this should be a problem.

• So you basically say, for every iteration one adds the random noise of interest and calculates the resulting SSE by rerunning the complete cluster algorithm including the noise datapoints ? May 9 '12 at 12:50
• or just adding the datapoint to the correct cluster and then calculating SSE (without reclustering ?) May 9 '12 at 12:52
• @steffen "So you basically say, for every iteration one adds the random noise of interest and calculates the resulting SSE by rerunning the complete cluster algorithm including the noise datapoints ? " is the correct interpretation of my answer. Jun 3 '12 at 22:03

As a rule of thumb, "squared errors" and "predict/estimate" don't go together very well.

A single object with a large error can dominate the overall result. If your prediction/estimation misses this object, the prediction will be way off.

Are you trying to optimize k-means with this, or do are you needing this value during evaluation of k-means results? In the latter case, try keeping track of this value during running k-means. You already have to compute the distances there, just compute the SSE value, too. In the first case, the estimated gain by estimating SSE is very small, as it is fairly cheap to compute.