[MUSIC]
Well, luckily the answer is yes, or often yes.
And we're going to discuss a few different ways of doing this.
And the first thing that we're going to talk about are KD-trees.
And KD-trees are a specific data structure for efficiently representing our data.
In particular, KD-trees provide an organization of
our documents in terms of this partitioning of our space.
We're going to be making these access aligned cuts,
and maintaining lists of points that fall into each one of these different bins.
And what this structure allows us to do as we're going to show,
is efficiently prune our search space so
that we don't have to visit every single data point, For every query, necessarily,
sometimes we'll have to but hopefully in many cases we won't have to.
And these methods, these KD-trees work really well in low to medium dimensions
meaning how many features we have and we'll return to this idea a bit later.
To start with, let's talk about the KD-tree construction.
So what we're going to do is we're going to take our data table.
So we have in this example just two different features.
So we have feature one, and this is feature two.
So maybe this is just the first word in our vocabulary and
this is the second word, and then here are the indices of our data points.
So these are our observation indices.
And these points are displayed just in r2 here.
So this is, Feature 1 and
this is, Feature 2.
Okay, so the first thing that we do is we're going to split our
data table into two different groups.
And the way we are going to do that is by choosing a split dimension.
So which feature are we splitting on and the split value so
what's the threshold for the split.
So here in this example we chose split value as 0.5 and
we are splitting on the first feature.
So everything to the right are cases where this first feature
takes values greater than 0.5, and everything to the left are cases where
the first feature takes values less than or equal to 0.5.
Okay, so if we look at datapoint, and the first feature has a value
greater than 0.5, we're going to place it in the yes table, the table to right,
otherwise it's going to go into the no table, the table to the left.
Then, what we're going to do is we're simply going to recurse
on each of these different groups separately.
So we're going to continue to split into two groups on each side.
So remember this was 0.5 looking at our split.
Now what we're going to do is we're going to choose a new split.
Where first we choose a split dimension where in this case we're choosing
feature two.
And a split value in this case we're choosing the value 0.1.
So here's the value 0.1 and here, these are cases
where the second feature is greater than 0.1,
and here, these are cases where the second feature is less than or equal to 0.1.
And so to be clear, all of these points here will appear on this list here.
They're the ones were x1 is less than 0.5 they
fall on the left hand side of this first vertical line.
And they also points where x2 at second feature dimension,
is less than 0.1, so they fall below that horizontal cut that we made.
So the answers to these questions were no, no, and so they fall into this table here.
Okay, so we continue doing this process, splitting, splitting,
splitting, splitting, and this creates a binary structured tree.
So, at the leaf
nodes of this tree we're going to have a list of points that fall within that bin.
Okay so, there's going to be list of points in each of this leaf nodes
representing the different observation within each bin.
So to be clear, if we trace our way down the tree to
any given leaf node the points that appear here will satisfy all conditions.
That were specified at each one
of the splits above along the path so
points here satisfy all conditions
down the tree to this point.
So we are going to keep one extra piece of information, that's going to be very
helpful when we are going to do our nearest neighbor search.
So just to be clear at any given
node in a tree we are going to store the following information.
First we're going to store which dimension we split on.
We're also going to store the split value.
So, where did we set that split threshold.
And the third thing we're going to store is the Titus bounding box, so the box
that's as small as possible that contains all observations within that node
or that satisfy the conditions to that node.
So this will be bounding
box that is as small
as possible while
containing points.
Okay, so that's this.
This is number three, above.
Okay, so hopefully that's clear.
It's a very, very intuitive type of structure for storing the data.
But there are lots of important choices,
it's kind of been the theme of this module.
And it continues to be true even when we're talking about these data structures
like KD-trees.
So examples include how are we going to figure out which dimension to split on,
what value to split on, and when are we going to stop splitting?
And in practice people just use heuristics for this.
So one example for
which dimension to split on we can split on the one that's the widest dimension.
So if we think about any box and we're looking at it let's say it's just a box in
r2 We look at how big x2 is versus x1,
and if x1 is bigger than x2, then maybe we choose to split on x1.
Or, you can think about alternating dimensions.
Then, when we think about what value we split at, One option is to split
at the median value of the observations that are contained in that box.
Or you could split at the center point of the box,
ignoring the spread of data within the box.
Then a question is when do you stop?
And here, there are a couple of choices that we have.
One is you can stop if there are fewer than a given number of points in the box.
Let's say m data points left, or
alternatively, if a minimum width to the box has been achieved.
So again, this second criteria would ignore the actual data in the box.
Whereas the first one uses facts about the data to drive the stocking criterion.
So as an example of how important theses choices can be,
here's an example where depending on the distribution of data in the space
whether we look at this median heuristic, for where to put this weak point or
we just use a center-of-range can give new and really different data structures.
And we're going to show how this can have an implications for the number of
searches that we have to do when we're doing our nearest neighbor search.
[MUSIC]