K-Mean Clustering

K-Means is a partition-based Clustering algorithm that assigns points to the nearest of $k$ centroids and updates centroids to the mean of their members.

Algorithm

1. choose the number of clusters k
2. Init k centroids randomly
3. Repeat until convergence:
   1. assign each data point to the nearest centroid
   2. update each centroid to the mean of the assigned data points
      1. distance metrics: typically use Euclidean Distance, but can use others like Manhattan Distance. It really depends on the data and task

Cons & Pros

Initialization of the centroids will affects the clustering results

Convergence

K-mean always converges but can’t guarantee the global optimum

Time complexity: $O(nkm)$:
$n$ is # of points
$k$ is # of clusters
$m$ is # of interations

Explain to Others

given point, 1, 2, 4, implement algorithm, given k = 2 :

• select 1, 2 as centroids
• calculate distance(distance metrics) between each point with centroid points
  • 1,1
  • 1,2
  • 1,4

References

1. Visualizing K-Means Clustering
2. can study more with codes from Visualizing Clustering Algorithms: K-Means and DBSCAN