B.4.5 newknn

This is an implementation of a fast Ball-tree based Classifier with binary-valued input attributes. We rely on the fact that these two questions are not the same: (a)``Find me the $k$ nearest neighbors.'' and (b) ``How many of the $k$-nearest neighbors are in the positive class?'' Answering (b) exactly does not necessarily require us to answer (a).

newknn attacks the problem by building two ball trees: one ball tree is built from all the positive points in the dataset, another ball tree is built from all negative points. Then it is time to classify a new target point t, we compute $q$, the number of k nearest neighbors of t that are in the positive class, in the following fashion:

• Step 1. Find the $k$ nearest positive class neighbors of t (and their distances to t) using conventional ball tree search.

• Step 2. Do sufficient search of the negative tree to prove that the number of positive data points among $k$ nearest neighbor is $q$ for some value of $q$.

We expect newknn can achieve a good speed up for the dataset with much more negative output than positive ones.

Keyword	Arg Type	Arg Vals	Default
Common
k	int	[0,$\infty$)	9
rmin	int	[1,$\infty$)	5
mbw	float	[1e-7,$\infty$)	0.01

Common keywords and arguments:

• k int: number of nearest neighbor you are interested.

• rmin int: the maximum number of points that will be allowed in a tree node. Sometimes it saves memory to use rmin $>$ 1. It even seems to speed things up, possibly because of L1/L2 cache effects.

• mbw float:"min_ball_width" = a node will not be split if it finds that all its points are within distance "mbw" of the node centroid. It will not be split (and will hence be a leaf node).