2016-04-01 17 views
1

Ich habe ein Array von (n_sample x 2) und ich möchte sie mit KDTree in sklearn.neighbors.KDTree Cluster.Clusterint 2D Punkte mit sklearn KDTree

Ich habe dieses Beispiel Stück Code:

from sklearn.neighbors import KDTree 
import numpy as np 
np.random.seed(0) 
X = np.random.random((10, 2)) 
tree = KDTree(X, leaf_size=2) 

Jetzt möchte ich die Punkte in den Blättern des Baumes zu extrahieren, so dass jedes Blatt ein Cluster sein kann. Punkte, die sich in demselben Blatt befinden, gehören zu demselben Cluster.

Im obigen Beispiel, weil die maximale leaf_size 2 ist, werden wir etwa 10/2 = 5 Cluster haben.

Was ich begehre, ist, dass ein Punkt in X (z. B. X [0]) der Baum mir den Index des Blattes des Baumes geben kann, zu dem die Punkte gehören.

+1

Der kd-Baum ist nicht gut für das Clustering geeignet. –

+0

Nicht in meinem Fall ist KD-Baum gut für die Art von Clustering geeignet, die ich brauche. Wie in diesem Papier erwähnt http://aclweb.org/anthology/P15-2104. – Ash

+1

Ich würde den Begriff "Clustering" dafür nicht verwenden. Es ist ein adaptives Gitter; Sie erwähnen nicht, was sie mit Nicht-Blatt-Benutzern tun; und es ist einfach, dies auszudrücken und zu implementieren, ohne einen kd-Baum einfach mit Median Splitting. –

Antwort

1

Die maximale Blattgröße 2 bedeutet, dass Sie von n bis n/2 Benutzer pro Blatt haben können. Aber Sie haben die Nicht-Blatt-Knoten vergessen.

Ein kd-Baum hat 1 Element in der Wurzel, 2 in der zweiten Schicht (das sind nicht schließen), und dann haben Sie 4 Blattknoten mit den verbleibenden 7 Objekten. Wenn Sie nur auf die Blätter schauen, haben Sie drei Objekte verloren.

Ein kd-Baum versucht nicht, Punkte zu sammeln. Es ist vollkommen richtig, dass ein kd-Baum genau dieselben Koordinaten in zwei Knoten hat! Die Referenz, die Sie angegeben haben, verwendete den kd-Baum nur, um ein adaptives Gitter zu erhalten. Ich denke nicht, dass es ein sehr guter Ansatz ist, aber es ist sehr einfach. Sie sollten es nur selbst implementieren, damit Sie nicht den vollständigen Baum erstellen und keine Objekte in Nicht-Blatt-Knoten einfügen.

0

Es ist dieses Paket kdtree in Python, die von installiert werden kann:

pip install --user kdtree 

und kann für Clustering 2D-Punkte verwendet werden.