k-Center-Greedy algorithm

greedy.py

# demo for https://arxiv.org/pdf/1708.00489.pdf and Fig. 3 of https://arxiv.org/pdf/2106.08265.pdf
import matplotlib.pyplot as plt
import numpy as np
from tqdm import tqdm

sample_num = 1000
x_sample = np.random.uniform(-1, 1, sample_num)
y_sample = np.random.uniform(-1, 1, sample_num)
dataset = np.stack([x_sample, y_sample], axis=1)

percent = 0.1


def k_greed(dataset, percentage: float):
    s = [dataset[0]]
    remain_data = [x for x in dataset[1:]]
    d_func = lambda x, y: ((x - y) ** 2).sum()
    indicator = tqdm()
    with indicator:
        while True:
            max_index = None
            max_distance = 0
            for i, data in enumerate(remain_data):
                distance = min([d_func(data, _s) for _s in s])
                if distance > max_distance:
                    max_distance = distance
                    max_index = i
            s.append(remain_data[max_index])
            del remain_data[i]
            indicator.update()
            if float(len(s) / len(dataset)) > percentage:
                return np.stack(s, axis=0)


plt.figure(0)
m_set = k_greed(dataset, percent)
plt.scatter(dataset[:, 0], dataset[:, 1])
plt.scatter(m_set[:, 0], m_set[:, 1], color="r")

plt.figure(1)
r_set = dataset[np.random.permutation(range(len(dataset)))[: int(len(dataset) * percent)]]
plt.scatter(dataset[:, 0], dataset[:, 1])
plt.scatter(r_set[:, 0], r_set[:, 1], color="r")

plt.show()