KNN-Algorithmus, die 2 oder mehr nächste Nachbarn

Question

Zum Beispiel habe ich einen Vektor x und a ist es am nächsten Nachbar. Dann ist b es der nächste nächste Nachbar. Gibt es ein Paket in Pyton oder R, das etwas wie [a, b] ausgibt, was bedeutet, dass a sein nächster Nachbar ist (vielleicht durch Mehrheitswahl), während b der zweitnächste Nachbar ist.

Answer 1

Das ist genau das, wofür diese Metric-Bäume gebaut werden.

Ihre Frage lautet, wie Sie für etwas so einfach wie das mit sklearn der KDTree (man denke BallTree je nach Metrik im Spiel) fragen:

import numpy as np 
from sklearn.neighbors import KDTree 

X = np.array([[1,1],[2,2], [3,3]]) # 3 points in 2 dimensions 
tree = KDTree(X) 
dist, ind = tree.query([[1.25, 1.35]], k=2) 
print(ind) # indices of 2 closest neighbors 
print(dist) # distances to 2 closest neighbors 

Out:

[[0 1]] 
[[ 0.43011626 0.99247166]] 

Und nur um klar sein: KNN normalerweise bezieht sich auf einige Pre-Build-Algorithmus auf metrischen Bäumen (KDTree, BallTree) für die Aufgabe der Klassifizierung basiert. Oft sind die Datenstrukturen das einzige, was man interessiert ist.

bearbeiten

Wenn ich Ihren Kommentar richtig zu interpretieren, können Sie die manhattan/taxicab/l1 metric verwenden möchten.

Look here für die Kompatibilitätslisten dieser räumlichen Bäume.

Sie würden es einfach so verwenden:

X = np.array([[1,1],[2,2], [3,3]]) # 3 points in 2 dimensions 
tree = KDTree(X, metric='l1')           # !!! 
dist, ind = tree.query([[1.25, 1.35]], k=2) 
print(ind) # indices of 2 closest neighbors 
print(dist) # distances to 2 closest neighbors 

Out:

[[0 1]] 
[[ 0.6 1.4]]