Implementation of K-Means Clustering

 

Experiment

Implementation of K-Means Clustering 

---

🎯 Objective

To implement the K-Means clustering algorithm from scratch using Python and understand its working through iterative centroid updates.

---

📘 Theory

🔹 Clustering

Clustering is an unsupervised learning method that groups similar data points into clusters.

---

🔹 K-Means Algorithm (Manual Implementation)

K-Means divides the dataset into K clusters such that the sum of squared distances between points and their cluster centroid is minimized.

---

🔹 Algorithm Steps

1. Choose number of clusters K
2. Select initial centroids (randomly or manually)
3. For each data point:
   • Compute distance to all centroids
   • Assign it to nearest centroid
4. Update centroids:
   • Take mean of all points in each cluster
5. Repeat steps 3–4 until centroids do not change

---

🔹 Distance Formula (Euclidean Distance)

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

Point	X	Y
P1	1	1
P2	1.5	2
P3	3	4
P4	5	7
P5	3.5	5
P6	4.5	5
P7	3.5	4.5

💻 Program (From Scratch Implementation)

import numpy as np
import matplotlib.pyplot as plt

# Step 1: Dataset
X = np.array([
    [1, 1],
    [1.5, 2],
    [3, 4],
    [5, 7],
    [3.5, 5],
    [4.5, 5],
    [3.5, 4.5]
])

# Step 2: Choose K
K = 2

# Step 3: Initialize centroids manually (first K points)
centroids = X[:K]

# Function to compute Euclidean distance
def distance(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

# K-Means Algorithm
max_iters = 10

for iteration in range(max_iters):
    clusters = [[] for _ in range(K)]
    
    # Step 4: Assign points to nearest centroid
    for point in X:
        distances = [distance(point, centroid) for centroid in centroids]
        cluster_index = np.argmin(distances)
        clusters[cluster_index].append(point)
    
    # Step 5: Update centroids
    new_centroids = []
    for cluster in clusters:
        if len(cluster) > 0:
            new_centroids.append(np.mean(cluster, axis=0))
        else:
            new_centroids.append(centroids[len(new_centroids)])
    
    new_centroids = np.array(new_centroids)
    
    # Check convergence
    if np.all(centroids == new_centroids):
        break
    
    centroids = new_centroids

# Final cluster assignment
labels = []
for point in X:
    distances = [distance(point, centroid) for centroid in centroids]
    labels.append(np.argmin(distances))

# Plotting
colors = ['blue', 'green']
for i in range(K):
    cluster_points = X[np.array(labels) == i]
    plt.scatter(cluster_points[:, 0], cluster_points[:, 1], c=colors[i])

plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='X', s=200)
plt.title("K-Means Clustering (From Scratch)")
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

# Output
print("Final Centroids:\n", centroids)
print("Cluster Labels:", labels)

---

📊 Output

🔹 Final Centroids (Approx)

 [[1.25 1.5 ]
 [3.9  5.1 ]]

🔹 Cluster Labels

[0, 0, 1, 1, 1, 1, 1]

---

📌 Result

The K-Means algorithm was successfully implemented from scratch, and the dataset was partitioned into 2 clusters using iterative centroid updates.

• K-Means works through iterative refinement
• Manual implementation improves conceptual clarity