def __compute_new_cluster_centroids(labels, items, distance_matrix):
    """The new centroids are the items with minimum average distance to all other items in their cluster"""
    new_centroid_indices = []
    for old_centroid_index in labels:
        cluster = labels[old_centroid_index]
        min_average_dist = float('inf')
        new_centroid = -1
        for item_index in cluster:
            distance = 0
            for i_i in cluster:
                distance += distance_matrix[item_index, i_i]
            average_dist = distance / len(cluster)
            if average_dist < min_average_dist:
                min_average_dist = average_dist
                new_centroid = item_index
        new_centroid_indices.append(new_centroid)
    return new_centroid_indices
