# How does the Nearest Centroid method work?

I have read this Wikipedia article.

But, the idea is still very fuzzy to me.

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?

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.

• 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]. – foobar Jul 24 '17 at 11:53

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.

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