KD Tree Algorithim
The KD Tree Algorithm is one of the most commonly used Nearest Neighbor Algorithms. The data points are split at each node into two sets. Like the previous algorithm, the KD Tree is also a binary tree algorithm always ending in a maximum of two nodes. The split criteria chosen are often the median. On the right side of the image below, you can see the exact position of the data points, on the left side the spatial position of them.
Data points and their position in a coordinate system.
The KD-Tree Algorithm uses first the median of the first axis and then, in the second layer, the median of the second axis. We’ll start with axis X.
The in ascending order sorted x-values are: 1,2,3,4,4,6,7,8,9,9. Followingly, the median is 6.
The data points are then divided into smaller and bigger equal to 6. This leads to (1,2) (2,3) (3,4) (4,5) (4,6) on the left side and (6,5) (7,9) (8,7) (9,6) (9,1) on the cluster of the other side. Drawing the median of 6 in the coordinate system shows us, the two visualized clusters.
Drawing the x-median of 6 into the coordinate system.
Now we’re going to use the Y-Axis. We have already two clusters, so we need to take a look at them separately. On the left side, we got the sorted y-values: 2,3,4,5,6. The median is then 4. This leads to a separation line at value 4 and the coordinate system looks like:
The median 4 separates the data points on the left side of the X-Median (=6).
The values are followingly separated at 4 and the first cluster contains (2,3) (1,2). The second cluster contains the points (4,6) (3,4) (4,5).
On the other side of the x-median of 4 are currently 5 points (including the point (5,6)). In sorted order, the y-values are 6,7,8,9,9. This leads to a median of 8 and the first cluster contains (9,1) and (6,5). The second cluster contains (8,7)(7,9)(9,6).
The resulting final coordinate system can be seen below. The data points have been divided into 4 clusters with a depth of 2 (X and Y).
previous image
The final spatial separation.
But, how does the tree look like? Let’s see how the resulting tree is divided.
The KD tree.