K-Means Introduction

Lesson 9 of 19 in Coddy's Introduction to Machine Learning course.

K-means is one of the simplest and most widely used clustering algorithms. It aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (centroid), serving as a prototype of the cluster. Let's say you have a bunch of different fruits and you want to sort them into baskets based on their type, but you don't have the labels. K-means helps you do just that but with data points instead of fruit!

Incheol, CC BY-SA 4.0, via Wikimedia Commons

How Does K-Means Work?

The algorithm follows a simple and efficient iterative procedure to divide a dataset into k clusters.

Initialize Centroids: First, choose k points as the initial centroids from the dataset. These points can be selected randomly or based on a specific strategy.
Assign Clusters: For each point in the dataset, find the nearest centroid (using distance measures such as Euclidean distance) and assign the point to that cluster.
Update Centroids: Once all points are assigned to clusters, recalculate the centroids by taking the mean of all points in each cluster.
Repeat Steps 2 and 3: The above steps are repeated until the centroids no longer change significantly. This means the algorithm has converged, and the clusters are stable.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

Challenge

Easy

Determining the optimal number of clusters, k, is a crucial step. There are various methods for this, with the Elbow Method being one of the most popular.

This technique involves running K-means continuously iterate for k=1 to k=n. For every value of k, we calculate the within-cluster sum of squares (WCSS) value.

Each cluster has a centroid, the WCSS is the sum of all distances from the centroid squared.

Create a function named wcss that receives a list of data points (of the same cluster) and returns the wcss of the cluster. Follow these steps:

Find the centroid - A centroid is a point that represents the average position of all the points in a cluster:

For example here is a list of two 3D points: (1, 2 ,3), (4, 5, 6). The centroid is:
```
(1 + 4) / 2 = 2.5,
(2 + 5) / 2 = 3.5,
(3 + 6) / 2 = 4.5,
>> (2.5, 3.5, 4.5)
```
Calculate the Euclidian distance between each point to the centroid
Return the sum of all distances divided by the number of points

Try it yourself

def euclidian_distance(point_a, point_b):
    return (sum([(point_a[i] - point_b[i])**2 for i in range(len(point_a))]))**0.5

def wcss(points):
    # Write code here