Clustering weighted data with k clusters

I have a list of 1D values, like this:

x = [20 21 30 31 200 201]

These values have corresponding weights:

w = [100 100 100 100 1 1]

I know that there are $k = 2$ clusters in this dataset. Using regular k-means results in

centroids = [25.5, 200.5]

But I want to take the weights into account, making the values near 200 basically meaningless.

So I want the two cluster centroids to be more like:

centroids = [20.5, 30.5]

I feel that the right clustering algorithm is something like mean shift, which finds that $20.5$ and $30.5$ are the two prominent peaks in the data. But I want it to find exactly 2 clusters, so regular mean shift won't work. Is there a good algorithm that can achieve this?

You could simply make multiple copies of the points proportional to their weights and then run k-means. Here is an R implementation of that.

x = c(20, 21, 30, 31, 200, 201)
w = c(100, 100, 100, 100, 1, 1)

WeightedX = rep(x, w)
kmeans(WeightedX, 2)

Cluster means:
[,1]
1 20.50000
2 32.18317
• Thank you, I couldn't get this to work on Matlab with their kmeans algorithm, but I found that changing the distance metric to the Manhattan distance did the trick. – Vermillion Nov 17 '17 at 20:08
• K-means should only be used with squared Euclidean. Repeating data points is a very stupid hack... it forces you to recompute things that are completely redundant! – Anony-Mousse Nov 18 '17 at 12:20

You can trivially modify k-means to support weights.

When computing the mean, just multiply every point with it's weight, and divide by the weight sum (the usual weighted mean).

$$\mu = \frac{1}{\sum_{i\in C} w_i} \sum_{i\in C} w_i x_i$$

This needs to happen in k-means, at each iteration when it is recomputing the cluster means, to find the best weighted means.

This is probably the easiest possible modification to k-means, fortunately.

But you will need to edit the k-means function, so you need access to the source code of k-means. Don't use a blackbox tools like MATLAB!

• So basically, take the centre of mass of the points, where the points have different mass. Alright I can try that too, thanks. Do you know why my question is being downvoted? – Vermillion Nov 18 '17 at 22:40