Расчет расстояния по матрице с использованием NumPy - PullRequest
Новая
       14

Расчет расстояния по матрице с использованием NumPy

1 голос
/ 12 января 2012

Я пытаюсь реализовать алгоритм K-средних в Python (я знаю, что для этого есть библиотеки, но я хочу научиться реализовывать его сам.) Вот функция, с которой у меня проблема: 

def AssignPoints(points, centroids):
    """
    Takes two arguments:
    points is a numpy array such that points.shape = m , n where m is number of examples,
    and n is number of dimensions.

    centroids is numpy array such that centroids.shape = k , n where k is number of centroids.
    k < m should hold.

    Returns:
    numpy array A such that A.shape = (m,) and A[i] is index of the centroid which points[i] is assigned to.
    """

    m ,n = points.shape
    temp = []
    for i in xrange(n):
        temp.append(np.subtract.outer(points[:,i],centroids[:,i]))
    distances = np.hypot(*temp)
    return distances.argmin(axis=1)

Назначение этой функции, учитывая m точек в n-мерном пространстве и k центроидов в n-мерном пространстве, формирует массив Numpy (x1 x2 x3 x4 ... xm), где x1 - индекс центроидаближе всего к первой точке.Это работало нормально, пока я не попробовал это на четырехмерных примерах.Когда я пытаюсь поместить 4-мерные примеры, я получаю эту ошибку: 

  File "/path/to/the/kmeans.py", line 28, in AssignPoints
    distances = np.hypot(*temp)
ValueError: invalid number of arguments

Как я могу это исправить или, если я не могу, как вы предлагаете мне рассчитать то, что я пытаюсь вычислить здесь?

Мой ответ 

def AssignPoints(points, centroids):
    m ,n = points.shape
    temp = []
    for i in xrange(n):
        temp.append(np.subtract.outer(points[:,i],centroids[:,i]))
    for i in xrange(len(temp)):
        temp[i] = temp[i] ** 2
    distances = np.add.reduce(temp) ** 0.5
    return distances.argmin(axis=1)

Ответы [ 2 ]

4 голосов
/ 12 января 2012

Попробуйте: 

np.sqrt(((points[np.newaxis] - centroids[:,np.newaxis]) ** 2).sum(axis=2)).argmin(axis=0)

Или: 

diff = points[np.newaxis] - centroids[:,np.newaxis]
norm = np.sqrt((diff*diff).sum(axis=2))
closest = norm.argmin(axis=0)

И не спрашивайте, что он делает: D

Редактировать: нет, просто шучу.В центре вещания (points[np.newaxis] - centroids[:,np.newaxis]) "делается" два 3D-массива из оригинальных.Результат таков, что каждая «плоскость» содержит разность между всеми точками и одним из центроидов.Давайте назовем это diffs.

Затем мы выполним обычную операцию для вычисления евклидова расстояния (квадратный корень из квадратов разностей): np.sqrt((diffs ** 2).sum(axis=2)).В итоге получается матрица (k, m), где в строке 0 содержатся расстояния до centroids[0] и т. Д. Итак, .argmin(axis=0) дает желаемый результат.

0 голосов
/ 12 января 2012

Вам нужно определить функцию расстояния, где вы используете гипотезу. Обычно в К-значит это Расстояние = сумма ((точка-медиан) ^ 2) Вот код Matlab, который делает это ... Я могу портировать его, если вы не можете, но попробуйте. Как вы сказали, единственный способ учиться. 

function idx = findClosestCentroids(X, centroids)
%FINDCLOSESTCENTROIDS computes the centroid memberships for every example
%   idx = FINDCLOSESTCENTROIDS (X, centroids) returns the closest centroids
%   in idx for a dataset X where each row is a single example. idx = m x 1 
%   vector of centroid assignments (i.e. each entry in range [1..K])
%

% Set K
K = size(centroids, 1);

[numberOfExamples numberOfDimensions] = size(X);
% You need to return the following variables correctly.
idx = zeros(size(X,1), 1);


% Go over every example, find its closest centroid, and store
%               the index inside idx at the appropriate location.
%               Concretely, idx(i) should contain the index of the centroid
%               closest to example i. Hence, it should be a value in the 
%               range 1..K
%
for loop=1:numberOfExamples
    Distance = sum(bsxfun(@minus,X(loop,:),centroids).^2,2);
    [value index] = min(Distance);
    idx(loop) = index;
end;


end

UPDATE

Это должно вернуть расстояние, обратите внимание, что приведенный выше код matlab просто возвращает расстояние (и индекс) ближайшего центроида ... Ваша функция возвращает все расстояния, как и приведенное ниже. 

def FindDistance(X,centroids):
K=shape(centroids)[0]
examples, dimensions = shape(X)
distance = zeros((examples,K))
for ex in xrange(examples):
    distance[ex,:] = np.sum((X[ex,:]-centroids)**2,1)
return distance
...