K-Means Clustering

Tags: #◇Computer Science #◇CSINTSY #◇K-Means Clustering #◇Problem Solving #◇M4

---

◇Overview

K-Means Clustering is an unsupervised machine learning algorithm designed to partition a dataset into $k$ distinct, non-overlapping groups (clusters) based on feature similarity. It is particularly effective with numerical features where distance metrics can be applied. The number of clusters $k$ is a hyperparameter that must be manually defined prior to running the algorithm.

Algorithm Steps:

1. Decide the number of clusters, $k$.
2. Initialize $k$ random centroids.
3. Assign each data point to the cluster of the nearest centroid (using Euclidean distance).
4. Recompute the centroids by taking the mean of all points assigned to each cluster.
5. Repeat steps 3 and 4 until convergence (i.e., until assignments no longer change).

Choosing $k$:
A higher $k$ is not necessarily better. Strategies for selecting an appropriate $k$ include: Utilizing domain knowledge. The Elbow Method, where the model's Inertia is plotted against various $k$ values, and the "elbow" point is chosen as the optimal $k$.

◇Important Formulas

Inertia (Within-Cluster Sum of Squares):
A metric to measure cluster quality (lower is better, meaning tighter clusters).
$\text{Inertia} = \sum_{i=1}^{k} \sum_{x \in C_i} (x - \mu_i)^2$
Where $C_i$ is cluster $i$ and $\mu_i$ is the centroid of $C_i$.

◇Worked Examples

Algorithm Walkthrough:
Imagine a dataset with numerical features for temperature and humidity. Initialize $k=2$ random points in this 2D space. Calculate the Euclidean distance of all data points to these two centroids. Assign points to the closest centroid. Shift the centroids to the average position of their respective assigned points. Repeat the assignment and shifting until the centroids no longer move. The final groupings represent the clusters.

◇References & Navigation

• Previous Topic: ◇Naive Bayes
• Next Topic: ◇Expert Systems Overview
• Related Notes: ◇K Means Clustering, ◇Clustering