Должен ли np.linalg.norm быть квадратным при реализации алгоритма кластеризации k-средних? - PullRequest
Новая
       7

Должен ли np.linalg.norm быть квадратным при реализации алгоритма кластеризации k-средних?

0 голосов
/ 14 апреля 2019

Цель алгоритма кластеризации k-средних состоит в том, чтобы найти:

a

Я рассмотрел несколько его реализаций в python, и в некоторых из них норма не в квадрате.

Например (взято из здесь ): 

def form_clusters(labelled_data, unlabelled_centroids):
    """
    given some data and centroids for the data, allocate each
    datapoint to its closest centroid. This forms clusters.
    """
    # enumerate because centroids are arrays which are unhashable
    centroids_indices = range(len(unlabelled_centroids))

    # initialize an empty list for each centroid. The list will
    # contain all the datapoints that are closer to that centroid
    # than to any other. That list is the cluster of that centroid.
    clusters = {c: [] for c in centroids_indices}

    for (label,Xi) in labelled_data:
        # for each datapoint, pick the closest centroid.
        smallest_distance = float("inf")
        for cj_index in centroids_indices:
            cj = unlabelled_centroids[cj_index]
            distance = np.linalg.norm(Xi - cj)
            if distance < smallest_distance:
                closest_centroid_index = cj_index
                smallest_distance = distance
        # allocate that datapoint to the cluster of that centroid.
        clusters[closest_centroid_index].append((label,Xi))
    return clusters.values()

И дать противоположную, ожидаемую реализацию (взято из здесь ; этоэто просто вычисление расстояния): 

import numpy as np
from numpy.linalg import norm

def compute_distance(self, X, centroids):
        distance = np.zeros((X.shape[0], self.n_clusters))
        for k in range(self.n_clusters):
            row_norm = norm(X - centroids[k, :], axis=1)
            distance[:, k] = np.square(row_norm)
        return distance

Теперь я знаю, что есть несколько способов вычислить норму \ расстояние, но я смотрел только на реализации, которые использовали np.linalg.norm с ord=None или ord=2и, как я уже сказал, в некоторых из них норма не возводится в квадрат, но они правильно группируются.

Почему?

1 Ответ

0 голосов
/ 14 апреля 2019

Опыт показывает, что использование нормы или квадрата нормы в качестве целевой функции алгоритма оптимизации дает аналогичные результаты.Минимальное значение объективной функции изменится, но полученные параметры будут такими же.Я всегда догадывался, что внутренний продукт порождает квадратичную функцию, а корень этого продукта изменил только величину, но не топологию объективной функции.Более подробный ответ можно найти здесь.https://math.stackexchange.com/questions/2253443/difference-between-least-squares-and-minimum-norm-solution Надеюсь, это поможет.

...