nagdmc kdtree

NAG DMC

Nearest Neighbours: nagdmc kdtree
Purposenagdmc kdtree computes a k-d tree for use with the nearest neighbour functions nagdmc knnc andnagdmc knnp.

Declaration#include <nagdmc.h>void nagdmc kdtree(long rec1, long nvar, long nrec, long dblk, double data[],long nxvar, long xvar[], long yvar, long ng, long nig[],
long *iproot, int *info);

Parameters1:

rec1 – longInput

On entry: the index in the data of the first data record used in the analysis.
Constraint: rec1 ≥ 0.
2:

nvar – long

Input

On entry: the number of variables in the data.
Constraint: nvar > 1.
3:

nrec – long

Input

On entry: the number of consecutive records, beginning at rec1, used in the analysis.
Constraint: nrec > 1.
4:

dblk – long

Input

On entry: the total number of records in the data block.
Constraint: dblk ≥ rec1 + nrec.
5:

data[dblk ∗ nvar] – double

Input

On entry: the data values for the jth variable (for j = 0, 1, . . . , nvar−1) are stored in data[i∗nvar+j],
for i = 0, 1, . . . , dblk − 1.
6:nxvar – long

Input

On entry: the number of independent variables. If nxvar = 0 then all variables in the data,excluding yvar, are treated as independent variables.
Constraint: 0 ≤ nxvar < nvar.
7:

xvar[nxvar] – long

Input

On entry: the indices indicating the position in data in which values of the independent variables
are stored. If nxvar = 0 then xvar must be 0, and the indices of independent variables are given byj = 0, 1, . . . , nvar − 1; j 6= yvar.
Constraints: if nxvar > 0, 0 ≤ xvar[i] < nvar, for i = 0, 1, . . . , nxvar − 1; otherwise xvar must be0.
8:yvar – long

Input

On entry: the index in data in which values of the dependent variable are stored.
Constraints: 0 ≤ yvar < nvar; if nxvar > 0, yvar 6= xvar[i], for i = 0, 1, . . . , nxvar − 1.
9:ng – long

Input

On entry: the number of groups in the dependent variable. If the dependent variable is continuous,
set ng equal to −1.
Constraint: if ng 6= −1, ng > 1.

nagdmc kdtree.1

nagdmc kdtree

NAG DMC10:

nig[ng] – long
Input
On entry: if ng 6= −1, the number of data records in each group on the dependent variable;
otherwise nig must be 0.
Constraints: nig[i] ≥ 1, for i = 0, 1, . . . , ng − 1; and the elements of nig must sum equal to nrec.

11:

iproot – long *On exit: an integer cast of the root of the k-d tree.

Output12:

info – int *On exit: info gives information on the success of the function call:

Output0: the function successfully completed its task.
i; i = 1, 2, 3, 4, 6, 7, . . . , 10: the specification of the ith formal parameter was incorrect.
99: the function failed to allocate enough memory.
100: an internal error occurred during the execution of the function.

Notation
nrec
datayvar

the number of data records, n.
the set of data records, X.
the dependent variable in the data, y.

Description
A k-d tree is a lattice that represents k-dimensional data values in a binary tree (see Figure 1).
AB

DCE

Figure 1: Example of a binary tree lattice. Ellipses are used to represent nodes in thetree and parent nodes are linked by line segments to their child nodes in the lattice.
Nodes without children are known as leaf nodes (nodes C, D and E in the figure). The
single node without a parent node is (node A in the figure) is called the root node.
Let X be a set of n data records xi for i = 1, 2, . . . , n that we wish to represent in a binary treelattice. Each node in the lattice is associated with a set of data records. In general, let Zi be theset of data records associated with node k. If node k is not a leaf node it is associated with a test
that partitions Zk , i.e., sends each member of Zk to either its left or right child node; otherwise it
stores values of the dependent variable, y, in Zk .
The process of calculating a k-d tree is initiated by associating a root node with the n data reocrds
in X and is halted when Zk cannot be partitioned, i.e., |Zk | = 1 or all members of Zk are the same.
The test used to partition data records at node k is the condition:
xij ≤ u,where xij is the value of variable j for a data record belonging to Zk ; u is the median of variable jin Zk ; and j is the variable with the highest range for data records belonging to Zk .

nagdmc kdtree.2

NAG DMC

nagdmc kdtree

References and Further Reading
Bentley J L (1975) Multi-dimensional binary search trees used for associative searching
Communications of the ACM 18(9) 509–517.
Storer J A and Cohn M (1993) Algorithms for fast vector quantization Proc. Data Compression
Conference 381–390 IEEE Computer Society Press.

See Also
nagdmc knnc.pdf
calculates nearest neighbour classifications.
nagdmc knnp.pdf
calculates nearest neighbour approximations.
knnc ex.cthe example calling program for a categorical dependent variable.
knnp ex.cthe example calling program for a continuous dependent variable.

nagdmc kdtree.3