Nearest Neighbor

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

dx_dy

Forum-Anfänger


	Beiträge: 18

	Anmeldedatum: 06.11.12

	Wohnort: ---

	Version: ---

Verfasst am: 28.01.2013, 22:00 Titel: Nearest Neighbor

Hallo,

ich suche zu einer Matrix mit 27 xy -Punkten aus einer Messdaten jeweils den nächsten Nachbarn.

Es handelt sich hierbei um "Double" -Werte.

Zu dem nächstgelegenem Punkt brauche ich jeweils auch in welcher Zeile der Matrix sich der gesuchte Punkt befindet.

Ich habe folgendes probiert:

Code:

A=A';

Messwerte=[x y];

C = kNearestNeighbors(A,Messwerte,1);

Funktion ohne Link?

Response:

Undefined function or method
'kNearestNeighbors' for input arguments
of type 'double'

Vllt. gibt es auch eine ganz andere Möglichkeit und ich denke nur zu kompliziert. Ist ja auch schon spät Smile

Gruß
_________________

Mark Twain didn't actually say half the shit the Internet says he did. ~Mark Twain

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 28.01.2013, 23:18 Titel:

Hallo,

woher soll die Funktion kNearestNeighbors denn kommen? In MATLAB ist es jedenfalls nicht enthalten, und sowas fällt ja nicht vom Himmel.

Ein Ansatz wäre:

Code:

for I = 1:27
- Punkt I fixieren
- Abstand aller anderen Punkte zu Punkt I berechnen
- Minimum der Abstände finden und speichern
end

Funktion ohne Link?

Grüße,
Harald

dx_dy

Themenstarter

Forum-Anfänger


	Beiträge: 18

	Anmeldedatum: 06.11.12

	Wohnort: ---

	Version: ---

Verfasst am: 28.01.2013, 23:21 Titel:

Ja, hast recht. Habs auch gerade gemerkt.

Hab in einem Forum ein bisschen unaufmerksam gelesen.

Auf Dein Ansatz bin ich auch gekommen, nur bei knapp 7.000.000 dauert das zum Teil gang schön lange.

Suche nach einer eleganteren und schnelleren Lösung.
_________________

Mark Twain didn't actually say half the shit the Internet says he did. ~Mark Twain

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 28.01.2013, 23:35 Titel:

Hallo,

du hast ja zuerst von 27 Punkten gesprochen, und da ist Performance ziemlich uninteressant.
x und y sollen also Vektoren mit je knapp 7 Mio. Einträgen sein?

Eine Hilfe kann knnsearch (Statistics Toolbox) sein.
Kommt aber auf den Versuch an, ob das für diese Datenmenge geeignet ist.

Poste doch auch mal deinen bisherigen Ansatz; vielleicht sieht ja jemand Verbesserungspotential.

Grüße,
Harald

dx_dy

Themenstarter

Forum-Anfänger


	Beiträge: 18

	Anmeldedatum: 06.11.12

	Wohnort: ---

	Version: ---

Verfasst am: 29.01.2013, 02:33 Titel:

Hallo Harald.
Eigentlich geht es darum 27*300.000 Messpunkte zu durchsuchen.

D.h. aus 300.000 Punkten jeweils den nächsten Nachbarn der einzelnen 27 Pkts finden.

Darum erst die Idee mit NN.

Da es nur ein sehr kleiner Teil in der Auswertungskette ist, will ich daraus keine programmiertechnische Raffinesse machen. Es soll nur korrekt laufen und nicht allzu viel Performance beanspruchen.

Gruß
_________________

Mark Twain didn't actually say half the shit the Internet says he did. ~Mark Twain

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 29.01.2013, 10:10 Titel:

Hallo,

okay, also die dritte Problemvariante. Und, hast du knnsearch versucht?

Grüße,
Harald

MaFam

Forum-Meister


	Beiträge: 799

	Anmeldedatum: 02.05.12

	Wohnort: ---

	Version: R2009b

Verfasst am: 29.01.2013, 11:48 Titel:

Hallo,

wie lautet hier eigentlich die Definition eines "nächsten Nachbarn"?

Grüße, Marc

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 29.01.2013, 12:36 Titel:

Hallo dx_dy,

Ich nehme mal an, dass "xy Punkte" heißt, dass die Koordinaten in 2D sind. Dann:

Code:

Pool = rand(3e5, 2);
Search = rand(27, 2);
Index = zeros(1, size(Search, 1)); % [EDITED, was "size(Search, 2)"]
for iS = 1:length(Index)
v_1 = Pool(:,1) - Search(iS, 1);
v_2 = Pool(:,2) - Search(iS, 2);
[value, match] = min(v_1 .* v_1 + v_2 .* v_2); [EDITED, ".*" instead of "*"]
Index(iS) = match;
end

Funktion ohne Link?

Die Verwendung von NORM würde das teure SQRT einschließen, aber das ändert nichts am Index des Minimums.

Gruß, Jan

Zuletzt bearbeitet von Jan S am 04.02.2013, 23:39, insgesamt einmal bearbeitet

dx_dy

Themenstarter

Forum-Anfänger


	Beiträge: 18

	Anmeldedatum: 06.11.12

	Wohnort: ---

	Version: ---

Verfasst am: 04.02.2013, 15:19 Titel:

Hallo Jan,

danke für Deine Antwort.

Leider versteh ich Deinen Code nicht ganz, könntest Du Ihn mir bitte ein wenig erläutern.

Gruß

Patrick
_________________

Mark Twain didn't actually say half the shit the Internet says he did. ~Mark Twain

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 04.02.2013, 23:34 Titel:

Hallo dx_dy,

Eine konkrete Frage ist immer effizienter, da ich dann nicht die Zeilen erklären müsste, die Du schon längst verstehst.

Hattest Du schon den Bug entdeckt, dass es statt "v_1 * v_1 + v_2 * v_2" heißen muss: "v_1 .* v_1 + v_2 .* v_2"?

Code:

Pool = rand(3e5, 2); % Test-Daten, ich habe Deine Zahlen ja nicht
Search = rand(27, 2); % Test-Daten, ich habe Deine Zahlen ja nicht
Index = zeros(1, size(Search, 1)); % Pre-allocation, Ausgabe
for iS = 1:length(Index) % Schleife über Zeilen von "Search"
v_1 = Pool(:,1) - Search(iS, 1); % Differenz der 1.ten Komponente
v_2 = Pool(:,2) - Search(iS, 2); % Differenz der 2.ten Komponente
tmp = v_1 *. v_1 + v_2 *. v_2; % Quadrierte Euklidische Distanz
[value, match] = min(tmp); % Index des kleinsten Wertes
Index(iS) = match; % Speichern in Ausgabe
end

Funktion ohne Link?

Gruß, Jan

dx_dy

Themenstarter

Forum-Anfänger


	Beiträge: 18

	Anmeldedatum: 06.11.12

	Wohnort: ---

	Version: ---

Verfasst am: 05.02.2013, 12:16 Titel:

So, macht es Sinn. Danke!

Da ich etwas unter Zeitdruck war habe ich mich jetzt erst mal für die "quick & dirty" -Dampfhammermethode entschieden.

Code:

% Nächster Nachbar zu Footprint + Zeilenindex
distanz=zeros(27,2);

Footprint=Footprint';

for k=1:1:27

beste_distanz = 1000;
index = 0;

for i=1:1:size(C_xyz,1)

% i=i
% k=k
temp_distanz=sqrt((Footprint(k,1)-C_xy(i,1))^2+(Footprint(k,2)-C_xy(i,2))^2);

if (temp_distanz < beste_distanz)
beste_distanz = temp_distanz;
index = i;
end

end
distanz(k,1)=beste_distanz;
distanz(k,2)=index;
end

Funktion ohne Link?

Die Berechnung dauert ca. 10s. Ist für mich imo noch hinnehmbar.

Danke für Deinen Vorschlag mit der eleganten Lösung. Wenn ich wieder Luft habe werde ich wohl Deinen Ansatz ausprobieren und implementieren.

Gruß

Patrick
_________________

Mark Twain didn't actually say half the shit the Internet says he did. ~Mark Twain

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 05.02.2013, 13:28 Titel:

Hallo dx_dy,

Wie bereits erklärt, verschwendet SQRT hier nur Zeit. Wenn SQRT(a) < SQRT(b), dann gilt auch a < b. Also:

Code:

...
beste_distanz = 1000 ^2;
index = 0;
for i = 1:size(C_xyz,1)
temp_distanz = (Footprint(k,1)-C_xy(i,1))^2 + ...
(Footprint(k,2)-C_xy(i,2))^2;

if (temp_distanz < beste_distanz)
beste_distanz = temp_distanz;
index = i;
end
end
distanz(k,1)=sqrt(beste_distanz); % Nur hier *einmal*
distanz(k,2)=index;
end

Funktion ohne Link?

Das sollte merkbar schneller sein.
Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.