I am trying to implement k-means clustering algorithm, but I am confused about calculating the distance and update(move) cluster centroids. For example, let's say that I have 2 features. One of them is weight={2,4,6,8,11,14,21} and the other one is height={4,6,7,8,9,12,14}. So, in the coordinate system my points are x1={2,4},x2={4,6},x3={6,7} and so on. Then, I initialize the cluster centroids randomly, doesn't matter how many there are for now, but they have coordinates too. Let's say μ1={4,2}. At this point, I understand how do I calculate distance with Euclidean distance.

enter image description here

My code for calculating distance:

def get_distance(x1,x2,s1,s2):
      return np.sqrt(np.power(s1-x1,2)+np.power(s2-x2,2))

Now I get a distance.

My first question is how cluster assignment step(first step in loop) will know which centroid assign to c(i).I mean,am I supposed to look at each centroid for understand which sample(x(i)) is close to it and then I should assign centroid to c(i), right?

My second question, let's say I got distances and I have c(1,2..,n) array now. Second step in algorithm which is called move(update) centroid step, we are calculate μ. According to formula, this μ is the average of points assigned to clusters so for example μ1=[x(3) + x(4) + x(6)] / 3. However, here our μ was a point in coordinate system, right? I mean, μ1 was {4,2}. How can this be possible? It's a point not a variable. It has coordinates. Well, if it will become a variable let's say μ1=5, how can I subtract ||x(i)-μ|| then? x is a coordinate.

My last question is very simple. For this example, I have two features weight and height. What is the maximum number of features that we can use in k-mean? Is it possible to use k-mean algorithms for many many features? For instance, my first feature is height and the second is weight and the third is width fourth and so on.

I hope, I explained my problem clearly. If not, sorry for the bad English. I think these three questions are independent questions, so you can answer one of them.



1 Answer 1


Wikipedia says: "Assign each observation to the cluster whose mean yields the least within-cluster sum of squares (WCSS)"

I think in your case, this is translatable to: $c_i$ is assigned to the closest centroid by euclidean distance.

For your second question, the centroid should $\mu$ should have the same number of dimensions as each training point $x_i$. They are both points in the co-ordinate system.

You can use a high number of features with K-means, for example, text analytics might reduce a corpora of news articles to 10,000+ dimensions. Depending on the package you use these might be represented as a sparse matrix.

  • $\begingroup$ for my second question,you said μ and x(i) must be same dimension,but when you are calculating μ , you are using a formula which is find an average of samples and it's giving to you an average ,you know.How do I subtract x-μ then? $\endgroup$
    – Mus
    Commented Aug 4, 2016 at 21:21
  • $\begingroup$ @Mus, The centroid should also be a co-ordinates in a space that is the same dimension as each example $\endgroup$ Commented Aug 5, 2016 at 18:00

Your Answer

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

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