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

# 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)

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

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

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)]

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()

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

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)]

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()

Python

# 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)

# 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)

Python

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

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

Python

# 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)

Python

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

Introduction

Understanding Clustering

k-Means Clustering

Join the 1M+ learners on CodeSignal

Implementing k-Means: Setup

Implementing k-Means: Algorithm

Implementing k-Means: Run

Implementing k-Means: Visualization

Lesson Summary and Practice