Gonzalez algorithm

Question

I'm getting confused about implementing the Gonzalez algorithm for k-center clustering.

The algorithm is :

• let $S$ be a data set
• Choose $z_1 \in S$ arbitrarily. Number $z$ is center. (In general let $Z_i = \{z_1, \dots, z_i\}$).
• for i = 2 to k do
  • Set $z_i = \operatorname{argmax}_{x\in S} d(x, \phi (Z_{i−1})(x))$

The formula of $\phi(Z)(x)= \operatorname{argmin} _{z\in Z} d(x, z)$.

I should implement this in Python. There used to be functions for clustering in Python, is there any function in Python for this algorithm?

Answer 1

The input for the Gonzalez algorithm is a set of elements to cluster and the distance between every pair of them. The first step of the Gonzalez algorithm is to select an element at random, this will be your first center (lets call it c_1). Since you already have a center, you must compute the distance from every element to c_1. Next, select as a new center the farthest element to c_1. In the remaining steps (k-2) you must keep computing the distance from every element to the set of already selected centers and just select as center the farthest element. The important thing here is that, in this context, the distance from an element e to a set of centers C, distance(e,C), is defined as the distance from e to its nearest center in C. I give you a general sketch for the Gonzalez algorithm, where matrix[i][j] stores the distance from element i to element j. I'm new at python, so my code is not optimal but gives you an idea.

def gon():
    C = []
    global distance = []
    for i in range(0,n):
        distance.append(float("inf"))
    f = random.randint(0, n-1)
    C.append(f)
    update_distance(C, 0)
    for i in range(1, k):
        f = farthest_element()
        C.append(f)
        update_distance(C, i)
    size = solution_size()
    out = [size, C]
    return out

# Update the distance of every element to the set of added centers
def update_distance(centers, max_index):
    global distance
    for i in range(0, n):
        if matrix[i][centers[max_index]] < distance[i]:
            distance[i] = matrix[i][centers[max_index]]

# Get the farthest element
def farthest_element():
    max_dist = 0
    max_dist_element = 0
    global distance
    for i in range(0,n):
        if distance[i] > max_dist:
            max_dist = distance[i]
            max_dist_element = i
    return max_dist_element