J'ai un ensemble de point (x, y) sur un plan 2D. Compte tenu d'un point (X0, Y0) et du nombre K, comment trouver le k-the voisin le plus proche de (x0, x0) dans le jeu de points. En détail, l'ensemble de points est représenté par deux matrices: x et y. Le point (x0, y0) est donné par l'index i0. Cela signifie x0 = x (i0) et y0 = y (i0).
Y a-t-il une fonction ou quelque chose à Matlab m'aide ce problème. Si MATLAB n'a pas ce type de fonction, pouvez-vous suggérer d'autres moyens efficaces.
edit : Je dois calculer ce type de distance pour chaque point (X0, Y0) dans l'ensemble. La taille de l'ensemble est d'environ 1000. La valeur de K devrait être à propos de SQRT (1500). La pire chose est que je fais cela plusieurs fois. À chaque itération, les changements définis et je calcule à nouveau les distances. Donc, le temps de fonctionnement est un problème critique.
5 Réponses :
Si vous avez la boîte à outils statistiques, vous pouvez utiliser la fonction KnnSearch .
Knnsearch semble être une solution mais je ne suis pas sûr de savoir comment appliquer KnnSearch à mon problème exactement. Je vais le trouver. Quoi qu'il en soit, pouvez-vous me donner plus de détails sur le chemin en utilisant KnnSearch. Merci beaucoup.
Avez-vous regardé l'aide MATLAB (ajout de lien vers ma réponse ci-dessus)?
J'ai lu le document en ligne sur KnnSearch, mais c'est un peu compliqué pour moi et je n'ai vraiment pas beaucoup de temps pour comprendre et l'utiliser. J'ai essayé l'approche plus simple. Il faut plus de temps de courir mais je vais essayer d'abord cette approche. Merci de votre aide.
Un algorithme de force brute serait quelque chose comme ceci:
L'approche de la force brute ressemble à quelque chose comme ceci:
%Create some points
n = 10;
x = randn(n,1);
y = randn(n,1);
%Choose x0
ix0 = randi(n);
%Get distances
d = sqrt(...
(x - x(ix0) ).^2 + ...
(y - y(ix0) ).^2 );
%Sort distances
[sorted_Dstances, ixSort] = sort(d);
%Get kth point
k = 3;
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.
Ne devriez-vous pas retirer l'élément lui-même? Pensez à l'affaire K = 1
Bon point. Je n'aime généralement pas changer les tailles des vecteurs de match comme celui-ci. Peut-être ajouter un '+1' à l'indexation finale. EDIT: Bien que cela laisse une lacune s'il y a un point identique au point initial. Si vous souhaitez garantir la réponse est un point différent, même lorsque certains points pourraient être égaux, alors plus de travail est nécessaire.
@Pursuit Il n'a pas de sens de supprimer également les points égaux. Si vous avez 5 points égaux au point que vous recherchez, la 3ème distance doit être 0
Merci beaucoup! Mais je dois calculer ce genre de distance avec chaque point de l'ensemble. Donc, il semble que cette approche soit un peu plus simple que prévu. Je suis désolé de ne pas clarifier plus tôt.
Le libre et opensource Vlfeat Toolbox contient une implémentation de KD-Tree, parmi d'autres choses utiles.
Si vous effectuez cette vérification pour de nombreux points, vous souhaiterez peut-être construire un tableau de distance inter-point d'abord
squareform(pdist([x y]))
Oui. Je vais le faire pour chaque point de l'ensemble. Donc, une sorte de table de distance aiderait à sauver l'heure de fonctionnement. Je vais savoir comment fonctionne la fonction Squareform dans mon problème. Merci beaucoup.
La fonction est un pdist en fait, SAREFORD fait simplement la matrice carrée de la sortie de vecteur de pdist
Mais seulement si vous avez la boîte à outils de statistiques.
ça marche pour moi. Peut-être que ce n'est pas la meilleure approche, mais c'est simple à mettre en œuvre et à utiliser. Pour être honnête, je n'ai pas beaucoup de temps pour terminer le code. Merci beaucoup.
Ceci est O (n ^ 2), où n est le nombre de points, avec chaque requête puis être O (n lg n). Un arbre KD, mentionné ci-dessous, et également utilisé dans certaines conditions par KnnSearch , est généralement beaucoup plus rapide, prenant O (n lg ^ 2 n) à construire, O (LG N) pour 1 voisin le plus proche , et, je suppose que, autour de O (k (lg k) (LG N)) pour les voisins les plus proches les plus proches lorsque k est petit et avec un jeu de données favorable (pensée: via la recherche binaire). (Ce qui signifie, par exemple, que si vous avez 10000 points, il devrait être quelque 100 à 1 000 fois plus vite.) Par conséquent, KnnSearch est très préféré .