2
$\begingroup$

I have read this Wikipedia article.

enter image description here

But, the idea is still very fuzzy to me.

enter image description here

Suppose, k=5.

Then, we have,

$X_5 = \{A, B, C, D, E\}$

$Y_2 = \{Triangle, Square\}$

$R_5 = \{9, 8, 5, 1, 4 \}$ (just assumed)

Now, $\mu_{Triangle} = \frac{5}{2} = 2.50$

and, $\mu_{Square} = \frac{22}{3} = 7.33$

Since, $\mu_{Triangle} < \mu_{Square}$, $class(?) == Triangle$.

Am I correct?

$\endgroup$
5
$\begingroup$

You are making a mistake regarding what is given: during training, you don't have a radius $R$. You have the coordinates $\vec{x}$ and the label $y$ for each point: $$ \vec{x}_1 = [-2;1] \quad \vec{x}_2 = [1;2] \quad \vec{x}_3 = [0;-1] \quad \vec{x}_4 = [1;0] \quad \vec{x}_5 = [1;1] $$ and $$ y_1 = T \quad y_2=T \quad y_3=T \quad y_4=S \quad y_5=S $$ with that, your "trained" centroids are $$ \mu_T = \frac 13 [-2 + 1 + 0; 1 + 2 - 1] = \left[-\frac 13, \frac 23\right] $$ $$ \mu_S = \frac 12 [1 + 1; 0 + 1] =\left[1, \frac 12\right]$$ You calculate these centroids before you get any test values.

Then, for testing, for your observed point $\vec{x} = [1,1]$, you calculate the Euclidean distance between the point $\vec{x}$ and the centroids $\mu_T$ and $\mu_S$: $$ \| \vec{x} - \mu_T \| = \left\| [1;1] - \left[-\frac 13; \frac 23\right] \right\| = \left\| \left[\frac 43; \frac 13\right] \right\| = 1.37 $$ $$ \| \vec{x} - \mu_S \| = \left\| [1;1] - \left[1; \frac 12\right] \right\| = \left\| \left[0; \frac 12 \right] \right\| = 0.5$$ Finally, the term $\hat{y} = \arg\min_{l \in \mathbf{Y}} \|\vec{x}-\mu_l\|$ is used to find the estimated class $\hat{y}$ (the hat symbol is to denote that this is an estimated $y$, not one we knew before.). $\arg\min$, means that you find the minimum value - which is 0.5 in our case, and chose which "argument", i.e. which class, leads to that minimum value. In our case, the class which leads to the minimal distance is $S$, so the result is $\hat{y} = S$, and our test point is a square.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Shouldn't mu_t second part be (1 + 2 -1) /3 = 2/3 instead of 1/3? Since x_2 is [1; 2] not [1; 1]. $\endgroup$ – foobar Jul 24 '17 at 11:53
0
$\begingroup$

What the prediction function does is:

  1. Computes the centroid for each class

  2. Measures the distance ( generally Euclidean ) of the data point X to the centroid of each class.

  3. If the distance is of X and the centroid of a particular class is minimum then it assigns that class to the data point X ( The argmin statement in the picture you have provided ) i.e Y predicts the centroid closest to the point X

This is the technique used in K means clusterings well ( though not exactly the same). I suggest you read this article for a more intuitive understanding.

Hope this helps.

| improve this answer | |
$\endgroup$
  • $\begingroup$ OK. But, can you complete my given example? $\endgroup$ – user9232 Nov 21 '16 at 1:44
  • $\begingroup$ I think the answer that you have is correct, and the reasoning can be followed from the answer above. $\endgroup$ – Sarthak Khanna Nov 21 '16 at 1:49
  • $\begingroup$ But, what does it mean by $\hat y = arg min ...$? And how does that match with my example? $\endgroup$ – user9232 Nov 21 '16 at 1:51
  • $\begingroup$ it means that Y = minimum of distances betwen the data point X and the centroids. $\endgroup$ – Sarthak Khanna Nov 21 '16 at 1:54
  • $\begingroup$ So which ever centroid is closest to the point X, that is the one that Y will predict $\endgroup$ – Sarthak Khanna Nov 21 '16 at 1:55

Your Answer

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