Расстояния Минковского рассчитываются с помощью linalg.norm с необычным временем

Question

Это часть моей реализации алгоритма K-medoids. Я тестировал алгоритм с небольшими изображениями, которые я генерирую случайным образом, и отлично работает (6X6). Проблема возникает, когда я использую реальное изображение (620x412), алгоритм все еще сходится, но занимает примерно 5 минут на итерацию. После профилирования моего кода я обнаружил, что узкое место вызывает np.linalg.norm, но я не уверен, что я здесь делаю не так

                                                                        Call count  Time(ms)    Own Time(ms)
<method 'reduce' of 'numpy.ufunc' objects>                                88329       70672         70672
norm                                                                      44164      152196         46999
<method 'astype' of 'numpy.ndarray' objects>                              44165       38445         38445
manhattan_distance                                                        44159      199809         37795
<built-in method numpy.core._multiarray_umath.implement_array_function>   88334      166973          9512
update_medoids                                                                1      103862           658

Это моя реализация update_medoids и манхэттенского расстояния

def manhattan_distance(pixels, medoids):
    """
    :param pixels:  Array of RGB  pixels
    :param medoids: pixels  selected as medoids. It can be a  (3,) array (single medoid), or  a vector (k, 3) for
    multiple medoidss
    :return:
    """
    if len(medoids.shape) == 1:
        medoids = medoids.reshape(1, len(medoids))
        distance = np.linalg.norm(pixels - medoids, ord=1, axis=1)
    else:
        distance = np.zeros((pixels.shape[0], len(medoids)))
        for medoid_idx in range(len(medoids)):
            medoid = medoids[medoid_idx].reshape(1, len(medoids[medoid_idx]))
            distance[:, medoid_idx] = np.linalg.norm(pixels - medoid, ord=1, axis=1)

    return distance

функция обновления medoids:

def update_medoids(pixels, medoids, distance):
    '''
    :param pixels: Array of RGB  pixels
    :param medoids: vector (k, 3) of pixels  selected as medoids. 
    :param distance: distance function used in algorithm
    :return: new vector of medoids with swapped members, if any.
    '''

    distances = distance(pixels, medoids)
    labels = assign_labels(distances)
    new_medoids = medoids

    for cluster in set(labels):
        cluster_dissimilarity = np.sum(distance(pixels, medoids[cluster]))
        cluster_points = pixels[labels == cluster]

        for data_point in cluster_points:
            hypothesis_medoid = data_point
            temp_cluster_dissimilarity = np.sum(distance(pixels, hypothesis_medoid))

            if temp_cluster_dissimilarity < cluster_dissimilarity:
                cluster_dissimilarity = temp_cluster_dissimilarity
                new_medoids[cluster] = hypothesis_medoid

    return new_medoids

Мое подозрение находится в np.linalg.norm(pixels - medoid, ord=1, axis=1), но я только предполагаю, что широковещательная передача замедляет вычисление, хотя это не кажется реалистичным c. мысли?

РЕДАКТИРОВАТЬ

входные образцы

пикселей - это вектор пикселей, который получается путем изменения матричного представления изображение, то есть

[[[232  10  22] [213  76 156] [156 232 103]]
[[116 160  12] [115 188 118] [ 74  42 106]]] 
[[157  30  36] [ 98  89 173] [142  76 225]]]

, преобразуется в вектор, который выглядит следующим образом:

[[232  10  22]
 [213  76 156]
 [156 232 103]
 [116 160  12]
 [115 188 118]
 [ 74  42 106]
 [157  30  36]
 [ 98  89 173]
 [142  76 225]]

medoids - это подмножество пикселей и действуют как представители каждого кластера.