KD-Baum: Bedeutung des Parameters "leafsize"
Ich sehe mir die KD Tree-Implementierung von SciPy an . Ich bin verwirrt von dem leafsizeParameter, der sein soll
Die Anzahl der Punkte, an denen der Algorithmus auf Brute-Force umschaltet. Standard: 16.
Ist dies die Anzahl der Blätter in der BST? Wenn ja, bedeutet dies standardmäßig, dass der KD-Baum nicht mehr als 32 Punkte enthält. Dies erscheint unangemessen klein, insbesondere für meinen Anwendungsfall von k = 2. Interpretiere ich den Parameter falsch?
Antworten
Der Parameter leafsizesteuert nicht die maximale Anzahl von Blättern im Baum (die nicht begrenzt ist), sondern die Anzahl von Eingabepunkten, die einem einzelnen Blatt im Baum zugeordnet sind. Betrachten Sie 64 Punkte, die einem Baum hinzugefügt werden. Wenn jeder Punkt einem einzelnen Blatt zugeordnet wird, erhalten Sie einen vollständigen Baum mit einer Tiefe von sieben Ebenen. Bei jeder Verarbeitung, die einen Punkt erfordert, werden diese sieben Ebenen herabgestuft, um ihn zu finden. Wenn die Blattgröße 16 beträgt, erhalten Sie alternativ einen Baum, der nur 3 Ebenen tief ist und jedem Blatt im Baum 16 Punkte zugeordnet sind. Um einen Punkt zu verarbeiten, müssen Sie drei Ebenen des Baums absteigen und dann jeden der 16 Punkte im Blatt testen (da sie ungeordnet sind). Dieser Wert kann auf Leistung abgestimmt werden. Empirisch hängt der beste Wert davon ab, wie genau der Baum verwendet wird.
Konzeptionell ist hier ein Beispiel für die Bäume, die für unterschiedliche leafsizeWerte erstellt werden.
Sie können sehen, wie der leafsizeParameter den Baumbildungsprozess im scipy-Quellcode kurzschließt . Dadurch bleiben zwischen leafsize/2und leafsizePunkte in den Blättern des Baums ungeordnet.