Understanding Clustering with k-Means Algorithm Basics

Introduction

Welcome to the fascinating landscape of Unsupervised Learning and Clustering. In this course, we'll explore the popular k-Means clustering algorithm, a simple yet powerful form of clustering. Although clustering might seem technical, if you've ever sorted your clothes into piles based on their colors or types, you've unknowingly performed a form of "clustering" — grouping similar items into different categories or clusters. Intrigued? Let's get started!

Understanding Clustering

Supervised learning is like learning with a teacher. In this type of machine learning, you provide the computer with labeled data, which means the algorithm is given the input data and the correct answers. The aim is to find a model that makes the best predictions based on the given examples. Unsupervised learning, on the other hand, is like learning on your own. In this type, the algorithm is given data but no specific directions about what it should be looking for. The computer is expected to explore the data and find its own patterns or structures. It is called 'unsupervised' because there are no correct answers and no teacher. Algorithms for unsupervised learning, like clustering, aim to group objects so that objects in the same group (a cluster) are more similar to each other than to those in other groups. Consider an example: you have a list of fruits with their corresponding weight and volume, and want to group them into two groups, but you don’t know what the fruits are. You can perform clustering, to segment the data into 2 clusters. Although we don’t know what the fruits are, we could predict that data points in the same cluster are the same type of fruit. Given data for a new piece of fruit, you could attempt to classify which group it belongs to by seeing which cluster center it is closest to. This lesson will focus on the widely used k-Means clustering method.

k-Means Clustering

The k-Means clustering algorithm aims to partition n observations into k clusters, where each observation belongs to the cluster with which it shares the most similarity. The steps involved are: Initialization : Random initialization of k centroids. Assignment : Allocation of each data point to the closest centroid. Update : Updating each centroid by computing the mean of all points allocated to its cluster. We repeat steps 2 and 3 until the centroids cease to change significantly. For now, we will manually set k, the number of clusters.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Now, let's translate this algorithm into Python code, using a dataset of 2D points for visual demonstration. Let's begin!

First, we initialize a simple dataset and define the number of clusters, k. We set k=2 and randomly initialize our cluster centroids from our data points.

# Toy dataset with 2D points
data = [(2,3), (5,3.4), (1.3,1), (3,4), (2,3.5), (7,5)]

# k-Means settings
k = 2  
centers = random.sample(data, k)

Next, we create a distance() function to calculate the Euclidean distance between two points. This concept is integral to the k-Means algorithm, and the formula for Euclidean distance is:

\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}

for points $(x_1, y_1)$ and $(x_2, y_2)$ .

# Definition of Euclidean distance
def distance(point1, point2):
    return ((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2)**0.5

Implementing k-Means: Algorithm

Now, we proceed to implement the k-Means algorithm. This code begins by setting up the clusters, assigning each data point to the nearest centroid, and then updating the centroid based on the mean of all points in its cluster. The process is repeated until the centroids stabilize.

Python

# k-Means algorithm
def k_means(data, centers, k):
    while True:
        clusters = [[] for _ in range(k)] 

        # Assign data points to the closest center
        for point in data:
            distances = [distance(point, center) for center in centers]
            index = distances.index(min(distances)) 
            clusters[index].append(point)

        # Update centers to be the mean of points in a cluster
        new_centers = []
        for cluster in clusters:
            center = (sum([point[0] for point in cluster])/len(cluster), 
                      sum([point[1] for point in cluster])/len(cluster)) 
            new_centers.append(center)

        # Break loop if centers don't change significantly
        if max([distance(new, old) for new, old in zip(new_centers, centers)]) < 0.0001:
            break
        else:
            centers = new_centers
    return clusters, centers

# k-Means algorithm
def k_means(data, centers, k):
    while True:
        clusters = [[] for _ in range(k)] 

        # Assign data points to the closest center
        for point in data:
            distances = [distance(point, center) for center in centers]
            index = distances.index(min(distances)) 
            clusters[index].append(point)

        # Update centers to be the mean of points in a cluster
        new_centers = []
        for cluster in clusters:
            center = (sum([point[0] for point in cluster])/len(cluster), 
                      sum([point[1] for point in cluster])/len(cluster)) 
            new_centers.append(center)

        # Break loop if centers don't change significantly
        if max([distance(new, old) for new, old in zip(new_centers, centers)]) < 0.0001:
            break
        else:
            centers = new_centers
    return clusters, centers

In the loop, initially, an empty list of clusters is created for each cluster to collect the points that belong to that cluster.

Then, for each data point, the distance to each centroid is calculated using a helper distance function. The index of the smallest distance is found, which represents the nearest centroid. That data point is then added to the cluster represented by that centroid.

Once all the points are assigned to their nearest centroid and all the clusters are filled, the centroids are updated. Each new centroid is recalculated as the mean (average) of all the points in its respective cluster.

It's finally time to run our k-Means clustering algorithm and witness it perform its magic!

Python

clusters, centers = k_means(data, centers, k)

# Let's print the cluster centers
for i, center in enumerate(centers):
    print(f"Cluster{i+1} center is : {center}")
# Cluster1 center is : (2.66, 2.98)
# Cluster2 center is : (7.0, 5.0)

# Let's print the clusters
for i, cluster in enumerate(clusters):
    print(f"Cluster{i+1} points are : {cluster}")
# Cluster1 points are : [(2, 3), (5, 3.4), (1.3, 1), (3, 4), (2, 3.5)]
# Cluster2 points are : [(7, 5)]

clusters, centers = k_means(data, centers, k)

# Let's print the cluster centers
for i, center in enumerate(centers):
    print(f"Cluster{i+1} center is : {center}")
# Cluster1 center is : (2.66, 2.98)
# Cluster2 center is : (7.0, 5.0)

# Let's print the clusters
for i, cluster in enumerate(clusters):
    print(f"Cluster{i+1} points are : {cluster}")
# Cluster1 points are : [(2, 3), (5, 3.4), (1.3, 1), (3, 4), (2, 3.5)]
# Cluster2 points are : [(7, 5)]

Our output consists of cluster centers and clusters. Cluster centers, or 'means,' are centroids representing the central point of each cluster. Each point in our dataset is assigned to the cluster closest to it. While versatile, k-Means performs optimally when cluster densities are approximately equal.

Let's see the obtained clusters on the plot using the following code:

Python

import matplotlib.pyplot as plt

colors = ['r', 'g', 'b', 'y', 'c', 'm']
fig, ax = plt.subplots()

# Plot points
for i, cluster in enumerate(clusters):
    for point in cluster:
        ax.scatter(*point, color=colors[i])

# Plot centers
for i, center in enumerate(centers):
    ax.scatter(*center, color='black', marker='x', s=300)

ax.set_title('Clusters and their centers')
plt.show()

import matplotlib.pyplot as plt

colors = ['r', 'g', 'b', 'y', 'c', 'm']
fig, ax = plt.subplots()

# Plot points
for i, cluster in enumerate(clusters):
    for point in cluster:
        ax.scatter(*point, color=colors[i])

# Plot centers
for i, center in enumerate(centers):
    ax.scatter(*center, color='black', marker='x', s=300)

ax.set_title('Clusters and their centers')
plt.show()

Here is the resulting image. Crosses represent the cluster centers, and points of different colors belong to different clusters:

We have set the number of clusters equal to 2; hence, the algorithms separated the data into two clusters.

Congratulations on successfully navigating the core aspects of clustering and implementing the k-Means algorithm! Moving forward, practice exercises are available to help solidify these concepts. I look forward to seeing you in the next lesson!

Introduction