08_K_Means_Clustering

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

K-Means Clustering is an unsupervised learning algorithm that partitions a dataset into $k$ distinct, non-overlapping subgroups (clusters).

◇Details / Theory

8. K-Means Clustering Reviewer

◇Overview

K-Means Clustering is an unsupervised learning algorithm that partitions a dataset into $k$ distinct, non-overlapping subgroups (clusters).

◇Goal

To group similar data points together such that:

1. Data points within the same cluster are as similar as possible (minimize intra-cluster distance).
2. Data points in different clusters are as different as possible (maximize inter-cluster distance).

◇Algorithm Steps

1. Initialize: Choose $k$ (the number of clusters). Select $k$ random data points as initial centroids (center of the cluster).
2. Assign: For every data point in the dataset, calculate its distance to each centroid. Assign the point to the cluster with the nearest centroid.
3. Update: Recalculate the new centroids. The new centroid of a cluster is the mean (average) position of all points assigned to that cluster.
4. Repeat: Repeat steps 2 and 3 until convergence:
   Centroids do not change position.
   Or points do not change clusters.
   Or a maximum number of iterations is reached.

◇Solved Example: 1-Dimensional Clustering

Dataset: Points on a line: $2, 3, 10, 11, 12$.
K = 2.

Iteration 1:

1. Initialize Centroids: Randomly pick $C_1 = 2$ and $C_2 = 10$.
2. Assign Points:
   Point 2: $|2-2|=0$ (Near $C_1$), $|2-10|=8$. $\to$ Cluster 1.
   Point 3: $|3-2|=1$ (Near $C_1$), $|3-10|=7$. $\to$ Cluster 1.
   Point 10: $|10-2|=8$, $|10-10|=0$ (Near $C_2$). $\to$ Cluster 2.
   Point 11: $|11-2|=9$, $|11-10|=1$ (Near $C_2$). $\to$ Cluster 2.
   Point 12: $|12-2|=10$, $|12-10|=2$ (Near $C_2$). $\to$ Cluster 2.
   Clusters: $K_1=\{2, 3\}$, $K_2=\{10, 11, 12\}$.
3. Update Centroids:
   New $C_1 = \text{mean}(2, 3) = 2.5$.
   New $C_2 = \text{mean}(10, 11, 12) = 11$.

Iteration 2:

1. Assign Points (using new centroids 2.5 and 11):
   Point 2: $|2-2.5|=0.5$, $|2-11|=9$. $\to$ Cluster 1.
   Point 3: $|3-2.5|=0.5$, $|3-11|=8$. $\to$ Cluster 1.
   Point 10: $|10-2.5|=7.5$, $|10-11|=1$. $\to$ Cluster 2.
   Point 11: $|11-2.5|=8.5$, $|11-11|=0$. $\to$ Cluster 2.
   Point 12: $|12-2.5|=9.5$, $|12-11|=1$. $\to$ Cluster 2.
2. Check Convergence:
   Clusters are still $K_1=\{2, 3\}$ and $K_2=\{10, 11, 12\}$.
   No change in assignment. Converged!

Final Clusters: $\{2, 3\}$ and $\{10, 11, 12\}$.

◇Distance Measures

How do we measure "nearest"?
Euclidean Distance: The straight-line distance between two points. Most common.
$d(p, q) = \sqrt{\sum\_{i=1}^{n} (q_i - p_i)^2}$ Manhattan Distance: The sum of absolute differences. Used for grid-like paths.
$d(p, q) = \sum\_{i=1}^{n} |q_i - p_i|$

◇Choosing K (Elbow Method)

How do we know the best number of clusters ($k$)?

1. Run K-Means for a range of $k$ values (e.g., 1 to 10).
2. Calculate the Inertia (Sum of Squared Errors - SSE) for each $k$. This measures how spread out the clusters are (lower is better).
3. Plot Inertia vs. $k$.
4. Look for the "Elbow": The point where the inertia starts decreasing slowly. This is usually the optimal $k$.

---

◇Common Pitfalls

Sensitive to initial centroid placement — different initializations can yield different clusters. Assuming K-Means works well with non-spherical or unequal-variance clusters — it assumes roughly equal-sized, spherical clusters. Choosing $k$ arbitrarily — use the Elbow Method (plot SSE vs. $k$) to find a reasonable number of clusters.

◇Summary

TL;DR — K-Means iteratively assigns points to the nearest centroid (using Euclidean or Manhattan distance) and updates centroids as cluster means until convergence. Use the Elbow Method to select $k$.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇Naive Bayes
• Next Topic: ◇MDP
• Related Notes: ◇K-Means Clustering