Determining Optimal K using Grid Search and Applying K-Means

 

Experiment

Determining Optimal K using Grid Search and Applying K-Means Clustering on Randomly Generated Data

---

🎯 Objective

To generate a sample dataset containing five clusters, determine the optimal number of clusters (K) using a Grid Search approach, and apply K-Means clustering using the identified value of K.

---

📘 Theory

🔹 K-Means Clustering

K-Means is an unsupervised learning algorithm that partitions data into K clusters such that points within a cluster are more similar than points in different clusters.

---

🔹 Need for Selecting Optimal K

K-Means requires the number of clusters (K) to be specified beforehand.

Problems:

• Small K → different groups may merge
• Large K → a single group may split into many clusters

Hence, we need a method to determine the best K.

---

🔹 Grid Search for K Selection

Grid Search means:

1. Try multiple values of K
2. Train K-Means for each K
3. Compute evaluation metric
4. Select K giving best performance

In this experiment:

• K values tested: 2 to 10
• Metric used: Silhouette Score

---

🔹 Silhouette Score Formula

$s(i)=\frac{b(i)-a(i)}{\max(a(i),b(i))}$

Where:

• $a(i)$ → average distance within same cluster
• $b(i)$ → average distance to nearest cluster

Interpretation:

Score	Meaning
Near +1	Well separated clusters
Near 0	Overlapping clusters
Less than 0	Poor clustering

🔹Elbow Method

The Elbow Method determines the optimal K by computing Within Cluster Sum of Squares (WCSS) for different values of K.

Initially:

• WCSS decreases rapidly

Later:

• Reduction becomes smaller

The point where this change occurs forms an elbow.

🔹 WCSS Formula

$WCSS=\sum_{i=1}^{K}\sum_{x\in C_i}(x-\mu_i)^2$

Where:

• $K$ = Number of clusters
• $C_i$ = Cluster i
• $\mu_i$ = Cluster centroid 

---

🧾 Dataset Description

Random data will be generated with:

• Total samples = 500
• Number of actual clusters = 5
• Features = 2

---

💻 Program

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

# ----------------------------------
# Step 1: Generate random dataset
# ----------------------------------

X, y = make_blobs(
            n_samples=500,
            centers=5,
            n_features=2,
            cluster_std=1.0,
            random_state=42
          )

# ----------------------------------
# Step 2: Visualize original data
# ----------------------------------

plt.figure()

plt.scatter(X[:,0],X[:,1])

plt.title("Generated Dataset")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")

plt.show()

# ----------------------------------
# Step 3: Grid Search for K
# ----------------------------------

k_values = range(2,11)

sil_scores=[]
inertia_values=[]

best_score=-1
best_k=0

for k in k_values:

    kmeans=KMeans(
                    n_clusters=k,
                    init='k-means++',
                    random_state=42
                  )

    labels=kmeans.fit_predict(X)

    score=silhouette_score(X,labels)

    sil_scores.append(score)

    inertia_values.append(kmeans.inertia_)

    print("K=",k,
          " Silhouette=",round(score,3),
          " Inertia=",round(kmeans.inertia_,2))

    if score>best_score:
        best_score=score
        best_k=k

print("\nBest K =",best_k)

# ----------------------------------
# Step 4: Apply K-Means using best K
# ----------------------------------

final_model=KMeans(
                    n_clusters=best_k,
                    random_state=42
                  )

final_labels=final_model.fit_predict(X)

centroids=final_model.cluster_centers_

# ----------------------------------
# Step 5: Plot Silhouette scores
# ----------------------------------

plt.figure()

plt.plot(
            k_values,
            sil_scores,
            marker='o'
         )

plt.xlabel("K")
plt.ylabel("Silhouette Score")
plt.title("Grid Search using Silhouette Score")

plt.show()

# ----------------------------------
# Step 6: Plot Inertia values
# ----------------------------------

plt.figure()

plt.plot(
            k_values,
            inertia_values,
            marker='o'
         )

plt.xlabel("K")
plt.ylabel("Inertia")

plt.title("Inertia vs K")

plt.show()

# ----------------------------------
# Step 7: Final clustering result
# ----------------------------------

plt.figure()

plt.scatter(
            X[:,0],
            X[:,1],
            c=final_labels
           )

plt.scatter(
            centroids[:,0],
            centroids[:,1],
            marker='X',
            color='red',
            s=300
           )

plt.title(
        f"K-Means Clustering (K={best_k})"
        )

plt.xlabel("Feature 1")
plt.ylabel("Feature 2")

plt.show()

# ----------------------------------
# Step 8: Print centroids
# ----------------------------------

print("\nCentroids:\n")
print(centroids)

---

📊 Output

Example:

K= 2  Silhouette= 0.594  Inertia= 14726.12
K= 3  Silhouette= 0.708  Inertia= 3648.76
K= 4  Silhouette= 0.733  Inertia= 1543.39
K= 5  Silhouette= 0.679  Inertia= 924.1
K= 6  Silhouette= 0.575  Inertia= 856.8
K= 7  Silhouette= 0.52  Inertia= 776.02
K= 8  Silhouette= 0.423  Inertia= 721.07
K= 9  Silhouette= 0.353  Inertia= 647.1
K= 10  Silhouette= 0.362  Inertia= 592.39

Best K = 4

---

📈 Graph Interpretation

Silhouette Score Graph

• Score increases initially
• Maximum value occurs at:

K = 4

Hence:

Optimal K = 4

Inertia Graph

• Inertia decreases continuously
• Reduction becomes smaller after K=5

---

📌 Result

The Grid Search approach successfully determined the optimal number of clusters for the generated dataset. The highest silhouette score occurred at:

K = 4

K-Means clustering was then applied using the selected value of K.

• Grid Search systematically tests multiple values of K.
• Silhouette score helps identify cluster quality.
• K-Means successfully discovered the five naturally occurring clusters.