Как ускорить этот процесс между массивами?[Питон, Numpy]

Question

Наличие двух числовых массивов ( выборок против кластеров ):

data(n_samples, n_featuers)
clusters(n_clusters, n_features)

Цель состоит в том, чтобы вычислить числовой массив индексов ближайших кластеров для каждой выборки:

new_assignments(n_samples)

Ниже приведен код:

def assign_clusters_to_samples(data, clusters, assignments):
    # clusters-array of clusters, sample-single sample from the database
    def get_index_from_euclidean_distances(clusters, sample):
        e_distances = np.sqrt(np.sum(np.power(np.subtract(clusters,sample),2), axis=1))
        # return index with the minimal distance
        return np.where(e_distances==np.min(e_distances))[0]

    new_assignments = np.empty((0,1), int)
    # iterate through all samples
    for i in range(data.shape[0]):
        new_assignments = np.append(new_assignments, get_index_from_euclidean_distances(clusters,data[i]))
    # return new assignments and True if there is a difference to last assignments, False otherwise
    return new_assignments, find_difference(new_assignments, assignments)

Однако он очень медленный.Как сделать процесс быстрее?Есть ли другие оптимальные способы решения проблемы?

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

Мой код выше является основной частью алгоритма кластеризации k-средних, который отвечает за 99,9% времени выполнения.Я создаю его с нуля в образовательных целях, и с вашими ответами я получил то, что мне было нужно. (Извините за более раннее редактирование и путаницу, это мой первый вопрос, будущие вопросы будут более конкретными и предоставят всю информацию и данные, необходимые для отладки ивоспроизводимость проблемы)

Спасибо Sobek .Применение np.apply_along_axis улучшенной производительности с оригинального до apply_along_axis .

Я продолжу строить решение, предложенное Эли Корвиго .

Большое спасибо!

Answer 1

Очень сложно прочитать euclidean_distances, потому что вы используете не математические операторы, а простые методы.Использование numpy.append очень медленное, потому что каждый раз нужно копировать весь массив.

def assign_clusters_to_samples(data, clusters, assignments):
    # clusters-array of clusters, sample-single sample from the database
    def euclidean_distances(clusters, sample):
        e_distances = np.sum((clusters - sample)**2, axis=1)
        # return index with the minimal distance
        return np.argmin(e_distances)

    new_assignments = [
        euclidean_distances(clusters,d)
        for d in data
    ]
    # return new assignments and True if there is a difference to last assignments, False otherwise
    return new_assignments, find_difference(new_assignments, assignments)

Answer 2

Редактировать

Предположим, у вас есть набор C точек центроида (clusters) в N-мерном векторном пространстве с евклидовой метрикой и набором Q точек запроса (samples) в одном и том же пространстве.Теперь, если вы хотите найти ближайший центроид для каждой точки запроса, вы можете использовать дерево поиска (например, KD tree ), чтобы сделать это примерно за O(QlogC), тогда как ваш текущий подход - O(Q**2).

In [1]: import numpy as np

In [2]: from sklearn.neighbors import DistanceMetric, KDTree

In [3]: clusters = np.array([
   ...:     [0, 1],
   ...:     [10, 5]
   ...: ])

In [4]: tree = KDTree(clusters, metric=DistanceMetric.get_metric('euclidean'))

In [5]: samples = np.array([
    ...:     [0, 2],
    ...:     [10, 6]
    ...: ])

In [6]: tree.query(samples, return_distance=False)
Out[6]: 
array([[0],
       [1]])

Оригинальный ответ (включая постскриптум)

Я вижу np.append вызовов внутри цикла, которые обычно считаются красным флагом для плохо оптимизированныхкод, потому что массивы NumPy не являются динамическими: np.append должен перераспределять и копировать свои операнды на каждой итерации.Вам будет намного лучше собирать массивы в списке и вызывать np.concatenate в результирующем списке.

def assign_clusters_to_samples(data, clusters, assignments):
    # clusters-array of clusters, sample-single sample from the database
    def euclidean_distances(clusters, sample):
        e_distances = np.sqrt(np.sum(np.power(np.subtract(clusters,sample),2), axis=1))
        # return index with the minimal distance
        return np.where(e_distances==np.min(e_distances))[0]

    # iterate through all samples
    acc = [euclidean_distances(clusters, data[i]).flatten() for i in range(data.shape[0])]
    new_assignments = np.concatenate(acc)
    # return new assignments and True if there is a difference to last assignments, False otherwise
    return new_assignments, find_difference(new_assignments, assignments)

PS

1. Я не уверен, что вы звоните np.append без преднамеренного указания axis (в конце концов, ваш исходный объект new_assignments явно не плоский): ваша функция (и, соответственно, мое решение) выравнивает возвращаемые значения с euclidean_distances перед добавлением / объединением.
2. Ваш алгоритм не особенно эффективен.Любая структура данных дерева дистанционного поиска значительно улучшила бы сложность по времени.

3. В плане дизайна, я не думаю, что вам следует вызывать find_difference внутри этой функции.Вот более чистое (с моей точки зрения) решение:

   def assign_clusters_to_samples(data, clusters):
       # clusters-array of clusters, sample-single sample from the database
       def euclidean_distances(clusters, sample):
           distances = np.sum((clusters - sample)**2, axis=1)
           # return index with the minimal distance
           return np.where(distances==np.min(distances))[0]
   
       return [euclidean_distances(clusters, sample) for sample in data]