USML2

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# Generate sample 2D data
X, _ = make_blobs(n_samples=300, centers=1, cluster_std=1.5, random_state=42)

def kmeans(X, k=2, max_iters=100):
    centroids = X[np.random.choice(len(X), k, replace=False)]
    for _ in range(max_iters):
        labels = np.argmin(np.linalg.norm(X[:, np.newaxis] - centroids, axis=2), axis=1)
        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    return centroids, labels

def calculate_sse(X, labels, centroids):
    sse = 0.0
    for i in range(len(centroids)):
        cluster_points = X[labels == i]
        sse += np.sum((cluster_points - centroids[i]) ** 2)
    return sse

def bisecting_kmeans(X, final_k=4, max_iters=100):
    clusters = [X]
    labels_list = [np.zeros(len(X), dtype=int)]

    while len(clusters) < final_k:
        # Choose the cluster with the highest SSE to split
        sse_list = [calculate_sse(clusters[i], labels_list[i], [clusters[i].mean(axis=0)]) for i in range(len(clusters))]
        idx_to_split = np.argmax(sse_list)

        cluster_to_split = clusters.pop(idx_to_split)
        _ = labels_list.pop(idx_to_split)

        # Run standard k-means with k=2 on the selected cluster
        centroids, labels = kmeans(cluster_to_split, k=2, max_iters=max_iters)

        # Split the cluster into two
        clusters.append(cluster_to_split[labels == 0])
        labels_list.append(np.full(np.sum(labels == 0), len(clusters) - 1))

        clusters.append(cluster_to_split[labels == 1])
        labels_list.append(np.full(np.sum(labels == 1), len(clusters) - 1))

    # Create final labels
    final_labels = np.zeros(len(X), dtype=int)
    current_idx = 0
    for cluster_idx, cluster in enumerate(clusters):
        for point in cluster:
            final_labels[np.all(X == point, axis=1)] = cluster_idx

    return final_labels, clusters

# Run bisecting k-means
k = 4
labels, clusters = bisecting_kmeans(X, final_k=k)

# Plot the result
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='tab10', s=30)
plt.title(f"Bisecting K-Means Clustering (k={k})")
plt.show()