Блог

Я выполняю анализ данных с использованием алгоритма k-ближайшего соседа в Matlab. Мои данные состоят примерно из матрицы данных 11795 x 88, где строки являются наблюдениями, а столбцы — переменными.

Моя задача — найти k ближайших соседей для n выбранных контрольных точек. В настоящее время я делаю это по следующей логике:

ДЛЯ всех тестовых точек

    LOOP all the data and find the k-closest neighbors (by euclidean distance)
  

Другими словами, я перебираю все n контрольных точек. Для каждой контрольной точки я ищу данные (которые исключают саму контрольную точку) для k ближайших соседей по евклидову расстоянию. Для каждой контрольной точки это занимает приблизительно k x 11794 итераций. Таким образом, весь процесс занимает около n x k x 11794 итераций. Если n = 10000 и k = 7, это будет приблизительно 825,6 миллионов итераций.

Есть ли более эффективный способ вычисления k ближайших соседей? Большая часть вычислений теперь будет потрачена впустую, потому что мой алгоритм просто:

вычисляет евклидово расстояние до всех остальных точек, выбирает ближайшую и исключает ближайшую точку из дальнейшего рассмотрения -> вычисляет евклидово расстояние до всех остальных точек и выбирает ближайшую -> и т.д. -> и т.д.

Есть ли разумный способ избавиться от этого «вычисления отходов»?

В настоящее время этот процесс занимает около 7 часов на моем компьютере (3,2 ГГц, 8 ГБ ОЗУ, 64-разрядная версия Win 7) … : (

Вот часть логики, проиллюстрированной явно (это не весь мой код, но это та часть, которая съедает производительность):

 for i = 1:size(testpoints, 1) % Loop all the test points 
    neighborcandidates = all_data_excluding_testpoints; % Use the rest of the data excluding the test points in search of the k-nearest neighbors 
    testpoint = testpoints(i, :); % This is the test point for which we find k-nearest neighbors
    kneighbors = []; % Store the k-nearest neighbors here.
    for j = 1:k % Find k-nearest neighbors
        bdist = Inf; % The distance of the closest neighbor
        bind = 0; % The index of the closest neighbor
        for n = 1:size(neighborcandidates, 1) % Loop all the candidates
            if pdist([testpoint; neighborcandidates(n, :)]) < bdist % Check the euclidean distance
                bdist = pdist([testpoint; neighborcandidates(n, :)]); % Update the best distance so far
                bind = n; % Save the best found index so far
            end
        end
        kneighbors = [kneighbors; neighborcandidates(bind, :)]; % Save the found neighbour
        neighborcandidates(bind, :) = []; % Remove the neighbor from further consideration 
    end
end
  

Использование pdist2 :

 A = rand(20,5);             %// This is your 11795 x 88
B = A([1, 12, 4, 8], :);    %// This is your n-by-88 subset, i.e. n=4 in this case
n = size(B,1);

D = pdist2(A,B);
[~, ind] = sort(D);
kneighbours = ind(2:2 k, :);
  

Теперь вы можете использовать kneighbours для индексации строки A . Обратите внимание, что столбцы kneighbours соответствуют строкам B

Но поскольку вы уже погружаетесь в панель инструментов статистики pdist , почему бы просто не использовать Matlab knnsearch ?

 kneighbours_matlab = knnsearch(A,B,'K',k 1);
  

обратите внимание, что kneighbours это то же самое, что kneighbours_matlab(:,2:end)'

Я не знаком с конкретными функциями matlab, но вы можете удалить k из своей формулы.

Существует хорошо известный алгоритм выбора, который

1. принимает массив A (размера n) и номер k в качестве входных данных.
2. Дает перестановку массива A таким образом, что k-й самый большой / самый маленький элемент находится на k-м месте.
3. Меньшие элементы находятся слева, большие — справа.

например

 A=2,4,6,8,10,1,3,5,7,9; k=5

output = 2,4,1,3,5,10,6,8,7,9
  

Это выполняется за O (n) шагов и не зависит от k.

EDIT1: вы также можете предварительно вычислить все расстояния, поскольку похоже, что это место, где вы проводите большую часть вычислений. Это будет примерно 800-миллиметровая матрица, так что это не должно быть проблемой на современных машинах.

Я не уверен, ускорит ли это код, но он удаляет два внутренних цикла

 for i = 1:size(testpoints, 1) % //Loop all the test points 
    temp = repmat(testpoints(i,:),size(neighborcandidates, 1),1);
    euclead_dist = (sum((temp - neighborcandidates).^2,2).^(0.5));
    [sort_dist ind] = sort(euclead_dist);
    lowest_k_ind = ind(1:k);
    kneighbors = neighborcandidates(lowest_k_ind, :);
    neighborcandidates(lowest_k_ind, :) = [];
end
  

Разве это не сработает?

 adjk = adj;

for i=1:k-1 
adj_k = adj_k*adj; 
end

kneigh = find(adj_k(n,:)>0)
  

учитывая узел n и индекс k?

Возможно, это более быстрый код в контексте Matlab. Вы также можете попробовать параллельные функции, индексы данных и приближенные алгоритмы ближайшего соседа, чтобы быть теоретически более эффективными.

 % a slightly faster way to find k nearest neighbors in matlab
% find neighbors for data Y from data X

m=size(X,1);
n=size(Y,1);
IDXs_out=zeros(n,k);

distM=(repmat(X(:,1),1,n)-repmat(Y(:,1)',m,1)).^2;
for d=2:size(Y,2)
    distM=distM (repmat(X(:,d),1,n)-repmat(Y(:,d)',m,1)).^2;
end
distM=sqrt(distM);
for i=1:k
    [~,idx]=min(distM,[],1);
    id=sub2ind(size(distM),idx',(1:n)');
    distM(id)=inf;
    IDXs_out(:,i)=idx';
end