Clustering weighted data with k clusters

Question

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?

Answer 1

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.

## Your data
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

Answer 2

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!