3-Approxmation Clustering Algorithm

clustering.py

from scipy.stats import random_correlation
from typing import List, Set
import seaborn as sb
import numpy as np
import matplotlib.pyplot as plt

plt.rcParams["figure.figsize"] = (10, 10)

# --- Specifying correlation matrix distribution and shape ---
rng = np.random.default_rng()
SIZE = 10
eigs = np.random.uniform(size=SIZE)
eigs /= np.sum(eigs) / SIZE
x = random_correlation.rvs(eigs, random_state=rng)
heatmap_configs = dict(vmin=-1, vmax=1, cmap="Blues")
# Visualize it
sb.heatmap(x, square=True, **heatmap_configs)

# --- Clustering algorithm ---
def cluster(vertices: List[int]):
    new_idx = np.random.choice(vertices)
    new_cluster = {new_idx}
    for node in vertices:
        if x[new_idx, node] > 0:
            new_cluster.add(node)
    leftovers = list(set(vertices) - new_cluster)
    new_cluster = list(new_cluster)
    return [new_cluster] if not leftovers else cluster(leftovers) + [new_cluster]

# --- Assigning clusters ---  
clusters = cluster(list(range(SIZE)))
order = list(itertools.chain.from_iterable(clusters))

reordered_x = x[:, order][order, :]
sb.heatmap(reordered_x, square=True, **heatmap_configs)
mask = np.zeros_like(x)
plt.show()

# --- Evaluating clustering ---
current_cluster_idx = 0
for cluster in clusters:
    cluster_size = len(cluster)
    mask_idx = np.arange(cluster_size) + current_cluster_idx
    mask[np.ix_(mask_idx, mask_idx)] = 1
    current_cluster_idx += cluster_size

sb.heatmap(reordered_x, square=True, mask=1 - mask, **heatmap_configs)
print("Loss: ", np.sum(reordered_x * (1 - mask)) - np.sum(reordered_x * mask))