1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\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 '17 at 20:08
  • 1
    $\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$ – Anony-Mousse Nov 18 '17 at 12:20
2
$\begingroup$

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!

$\endgroup$
  • $\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 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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