
1. Seeing what a kd-tree looks like
==================================================

 NOTE: for this to work you'll need to have kmeans compiled in "debug"
mode. If you don't understand the last statement, don't worry -- you
probably have a version of kmeans which is fine for this purpose.

1) Run the program "./showtree"

 What you see is a dataset of 8000 randomly-generated points, from a
5-gaussian distribution. You should see the underlying gaussians. The blue
boundary denotes the "root" kd-node. It encompasses all of the points.

2) Hit enter
 You see the children of the root node. Each is a rectangle, with the
splitting line parallel to the Y axis about half-way through.

3) Hit enter
 Now you see the grand-children of the root. Each one is a split of its
parent, along the X-axis this time.

4) Keep hitting enter to see the first 10 levels, and the the first 7 levels
combined.



2. Looking at k-means at work, and the fast way to do it
========================================================

1) Run the program "./show-kmeans". We see the 8000 points. In addition,
k-means has selected 5 random points for class centers. This are the fat
blue, green, red, black, and purple points. Notice that, as chance has it,
they do not correspond to the underlying Gaussians (as a matter of fact I
had to coerce the program to produce those "bad" initial points --- it is
fairly good at getting the initial points "right").

 Now, the program goes over datapoints, associating each one with the class
center closest to it. The points you see are colored according to the center
they're associated with. Notice the blue-green boundary at the top
right-hand corner. This (theoretical) line of points which are equidistant
from the green and blue centers determines which point belongs where.

 The next step of the algorithm is to re-position the class centers. The
green center will be placed at the center of mass of all green points, and
so on. As it turns out, the green center will shift to the right and
upwards. The black line going out from the green center shows this. Notice
the black and red centers each share about half of the gaussian on the left
(and about a half of the gaussian they're in), so they both "race" to the
left. The purple center's movement is very small.

2) Hit enter
 The program moved the centers, and re-colored all points according to which
center is closest to each. Since the green center has moved, the blue-green
boundary passes "outside" of the gaussian on the top-right-hand corner. And
is probably somewhere in the unpopulated area between blue and green. We
want this kind of thing to happen.

 By looking at the movement vectors, you can see the black and red will
continue racing to the left, and the purple now dominates a good part of its
surroundings. Notice the "orphan" gaussian between purple and green. This
happened because black and red reside in the same gaussian, so we're "short"
one centroid.

3) Hit enter
 The green-purple boundary shifts upward and to the right; looks like green
is going to own just "its" points and purple will own two gaussians. On the
bottom left-hand corner, it looks like red had lost the race to black
(black is more to the left).

4) Hit enter
5) Hit enter
 Now the blue-green and green-purple boundaries are pretty much set (to what
they should be). Notice that red will shift, ever so slightly, to the right.
6) Red has gone to the right. So it gained more purple points. Since all of
the purple points are to its right, this effect intensifies. Consequently,
purple is losing points to the red, and moves right (and up) as well.

7) Hit enter
8) Hit enter
9) Hit enter
10) Hit enter
 The red has completed its journey, gaining control over a gaussian
previously owned by purple. Black gets to own the entire gaussian on the
left. K-means has found the "correct" partition. Since this is a stable
configuration, the next iterations will not move the centers too much.

11) Hit enter

All the explanations above were true for traditional kmeans. "Traditional"
means that when you go out and decide which center is closest to each point
(ie, determine colors), you do it the naive way: for each point, compute
distances to all the centers and find the minimum. Our program is much
smarter then that. It first builds a kd-tree for the points (the one you saw
earlier). Now assume that some kd-node is ENTIRELY owned by some
center. This means that the next center movement will be affected by the
center of mass of the points in that kd-node (and their number). So, by
pre-computing the center of mass of each kd-node, and storing it in the
node, we can save a lot of work. [showing that some node is entirely owned
by a center can also be done efficiently -- see the paper].

 This kind of fast computation has been going on behind the scenes
throughout this demo. Whenever a node was proven to be fully owned by a
center, the program drew that node's rectangle. For visualization purposes
it also drew the points inside it, but a "real" program doesn't need to do
that. It just uses a very small constant number of arithmetic operations to
compute the effect a certain kd-node will have. This is opposed to summing
the coordinates of each and every point inside that rectangle, that is, a
cost which is linear in the number of points in the rectangle.

 Notice how easy it was to compute the black and blue centers-of-mass. The
black took just two nodes, and around 50 individual points. The blue took 5
nodes, plus around 10 points. Compare this with the roughly 8000/5 = 1600
points each one has (and doing 5 distances for each!).

 Another interesting thing to notice is how these rectangles get smaller as
we approach the theoretical boundary line we talked about before. Watch the
red-purple boundary. As we get closer to it, it's harder and harder for big,
fat nodes to be owned entirely by either red or purple. If you think about
it, they can't be owned entirely by either center if this boundary
intersects them. So, as closer we get to the boundary, the smaller the
rectangles. And it's pretty much individual points very close to the
boundary.


12) keep hitting enter till program exits.
