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?


2 Answers 2


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 20.50000
2 32.18317
  • $\begingroup$ 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. $\endgroup$
    – Vermillion
    Nov 17, 2017 at 20:08
  • 4
    $\begingroup$ 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! $\endgroup$ Nov 18, 2017 at 12:20
  • $\begingroup$ Related post how this could be done in Python: stats.stackexchange.com/q/603689/269684 $\endgroup$
    – user269684
    Jan 30 at 21:07

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!

  • $\begingroup$ 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? $\endgroup$
    – Vermillion
    Nov 18, 2017 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.