6.1.2.1. K-Means Clustering

• A centroid-based algorithm that partitions the dataset into K clusters. • Each cluster is represented by the centroid, which is the mean of the data points in that cluster.

K-Means Clustering is an algorithm used in machine learning to group data points into K distinct clusters. It starts by choosing K initial points, called centroids, which act as the centers of the clusters. Each data point is then assigned to the nearest centroid based on distance, resulting in different groupings. After the initial assignment, the centroids are recalculated by finding the mean of all points assigned to each cluster.

Imagine you are trying to organize a group of friends into K small gatherings based on their preferences. You start by randomly assigning gathering spots, then see which friends feel closest to each gathering. Over time, as you adjust the spots (centroids) to be more central to the friends who prefer them, you end up with more cohesive groups.

Algorithm Steps:

1. Initialize K centroids randomly.
2. Assign each data point to the nearest centroid.
3. Update centroids as the mean of the assigned points.
4. Repeat steps 2 and 3 until convergence.

The K-Means algorithm follows a simple iterative process. First, it selects K initial centroids randomly from the data points. Next, it assigns each point to the closest centroid based on a distance metric, usually Euclidean distance. After assigning all points, it recalculates the centroids of the newly formed clusters by averaging the points in each cluster. This process repeats until the assignments no longer change, indicating convergence.

Think of a teacher assigning students to study groups based on their reading skills. Initially, the teacher randomly places students into groups. After observing their performance, the teacher may adjust by moving students in and out to ensure each group has a balanced average skill level. This process continues until the groups stabilize.

Mathematical Objective: Minimize the within-cluster sum of squares (WCSS): 𝑘 ∑ ∑ ∥𝑥 −𝜇 ∥² 𝑗 𝑖 𝑖=1 𝑥 ∈𝐶𝑗 𝑖 Where: • 𝐶𝑖: set of points in cluster 𝑖 • 𝜇: centroid of cluster 𝑖

The goal of K-Means is to minimize the within-cluster sum of squares (WCSS), which measures how compact the clusters are. WCSS is calculated by summing the squared distances between each data point and its cluster centroid. This objective aims to create clusters where the points are as close to each other as possible, thereby improving the overall quality of the clustering.

Imagine you are trying to pack a suitcase with shirts. You want to make sure that similar shirts (maybe the same color) are packed together to reduce wrinkles. The closer you keep similar shirts to one another, the less space they will take up, leading to a compact and neat suitcase.

Pros: • Simple and fast. • Works well with spherical clusters. Cons: • Requires pre-defining K. • Sensitive to outliers and initial values.

K-Means Clustering has several advantages. It is simple to understand and implement, making it suitable for various applications. It is also computationally efficient, allowing it to handle large datasets quickly. However, it does have drawbacks. One major limitation is that the number of clusters, K, must be specified beforehand, which can be challenging. Furthermore, K-Means can be sensitive to outliers, which may significantly distort the clusters.

Consider an art class where students are grouped by painting style. The teacher finds it easy to group students with similar techniques, making the process straightforward and quick. However, if a student prefers an entirely different style that isn't captured in the teacher's initial groupings, their presence can disrupt the overall balance, making it hard to find a suitable group for them.

--