Comment effectuer un calcul efficace du voisin k le plus proche dans Matlab - performances, algorithme, matlab, voisin le plus proche

Je fais l’analyse de données en utilisant l’algorithme k-voisin le plus proche dans Matlab. Mes données se composent d’environ 11795 x 88 matrices de données, où les lignes sont des observations et les colonnes sont des variables.

Ma tâche consiste à trouver les k-voisins les plus proches pour n points de test sélectionnés. Actuellement, je le fais avec la logique suivante:

POUR tous les points de test

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

En d'autres termes, je boucle tous les n points de test. Pour chaque point de test, je recherche dans les données (qui exclut le point de test lui-même) les k-voisins les plus proches par distance euclidienne. Cela prend environ k x 11794 itérations pour chaque point de test. Donc tout le processus prend environ n x k x 11794 itérations. Si n = 10000 et k = 7, cela représenterait environ 825,6 millions d'itérations.

Existe-t-il un moyen plus efficace de calculer les k-voisins les plus proches? La plupart des calculs vont maintenant être perdus, car mon algorithme se contente de:

calcule la distance euclidienne à tous lesautres points, sélectionne le plus proche et exclut le point le plus proche -> calcule la distance euclidienne par rapport à tous les autres points et sélectionne le plus proche -> etc. -> etc.

Existe-t-il un moyen intelligent de se débarrasser de ce "calcul des déchets"?

Actuellement, cette procédure prend environ 7 heures sur mon ordinateur (3,2 GHz, 8 Go de RAM, Windows 7 64 bits) ... :(

Voici une partie de la logique illustrée explicitement (ce n’est pas tout mon code, mais c’est la partie qui mange les performances):

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

Réponses:

3 pour la réponse № 1

En utilisant 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, :);

Maintenant, vous pouvez utiliser kneighbours indexer une ligne dans A. Notez que les colonnes de kneighbours correspondent aux rangées de B

Mais puisque vous "plongez déjà dans la boîte à outils statistiques avec pdist pourquoi ne pas simplement utiliser Matlab "s knnsearch?

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

Notez que kneighbours est le même que kneighbours_matlab(:,2:end)"

---

1 pour la réponse № 2

Je ne connais pas les fonctions spécifiques de matlab, mais vous pouvez supprimer k de votre formule.

Il existe un algorithme de sélection bien connu qui

1. prend le tableau A (de taille n) et le nombre k en entrée.
2. Donne la permutation du tableau A tel que le k-ième élément le plus grand / le plus petit soit à la k-ième place.
3. Les plus petits éléments sont à gauche, les plus grands sont à droite.

par exemple.

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

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

Ceci est fait en O (n) étapes et ne dépend pas de k.

EDIT1: Vous pouvez également précalculer toutes les distances car il semble que ce soit l'endroit où vous passez la majeure partie des calculs. Ce sera approximativement une matrice de 800M, donc cela ne devrait pas être le problème sur les machines modernes.

---

1 pour la réponse № 3

Je ne suis pas sûr que cela accélérera le code, mais cela supprime les deux boucles internes.

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

---

1 pour la réponse № 4

Ne serait-ce pas ce travail?

adjk = adj;

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

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

étant donné un noeud n et un index k?

---

0 pour la réponse № 5

Peut-être que c'est un code plus rapide dans le contexte de Matlab. Vous pouvez également essayer des fonctions parallèles, un index de données et des algorithmes approximatifs du plus proche voisin pour être théoriquement plus efficaces.

% 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

---