KNN

Let $\text{A1=(3,8), A2=(9,4), A3=(4,9), A4=(2,2), A5=(10,5), A6=(2,4), A7=(6,8), A8=(4,3), A9=(4,7)}$

In this problem we will use $K=3$

Goal: Find member and centroid of each cluster

Step

1. Choose K-centroid randomly (It can be any points)

$$\begin{array}{r}{a}_1=(4,9)\\ a_2=(2,2)\\ a_3=(9,4)\end{array}$$

2. Find the nearest centroid $c_j$ for each point and assign each point to those centroid

$$argmi{n}_j(\text{Distance}(x_i,c_j))$$

In this problem we use Euclidean Distance

$$\text{Distance}(A,B)=\sqrt{(A_X-B_X{)}^2+(A_Y-B_Y{)}^2}$$

Let assume that we have assigned each point to its nearest centroid using Euclidean distance as a matric distance and get this result.

• j1 has [A1, A3, A7, A9]
• j2 has [A4, A6, A8]
• j3 has [A2, A5]

3. Find new centroid $c_j$ and see if cluster member change or not

• If cluster member remain the same : Finish!
• If cluster member change : Find new centroid again!

from j = 1 to K

$$\begin{array}{r}{c}_j(X)=\frac{1}{n}\sum _{i=1}^n{x}_i\\ c_j(Y)=\frac{1}{n}\sum _{i=1}^n{y}_i\\ \\ c_j=(c_j(X),c_j(Y))\end{array}$$

where

$$\begin{array}{r}n=\text{Number of points in cluster with centroid }{c}_j\\ x_i=\text{X coordinate of Point in cluster with centroid }{c}_j\\ y_i=\text{Y coordinate of Point in cluster with centroid }{c}_j\end{array}$$

Example

j	$c_j(X)$	$c_j(Y)$	centroid $c_j$
1	$\frac{3+4+5+6}{4}=4.25$	$\frac{8+9+8+7}{4}=8$	$(4.25,8)$
2	$\frac{2+2+4}{3}=2.667$	$\frac{4+3+2}{3}=3$	$(2.667,3)$
3	$\frac{10+9}{2}=9.5$	$\frac{4+5}{2}=4.5$	$(9.5,4.5)$

• j1 has [A1, A3, A7, A9]
• j2 has [A4, A6, A8]
• j3 has [A2, A5]

Member of cluster is not changed so FINISH!

Result