nagdmc knnp

NAG DMC

Nearest Neighbours: nagdmc knnp
Purposenagdmc knnp computes k-nearest neighbour approximations given a binary tree computed bynagdmc kdtree using training data.

Declaration#include <nagdmc.h>void nagdmc knnp(long rec1, long nvar, long nrec, long dblk, double data[],long iproot, int norm, long k, double res[], long nn[],double dist[], int *info);

Parameters1:

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

Input

2:

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

Input

3:

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

Input

4:

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

Input

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:iproot – long
Input
On entry: the integer value of the root node of a binary tree as returned by nagdmc kdtree.

7:

norm – int
Input
On entry: the norm used to compute distances. If norm = 1, the `1 -norm (or Manhattan distance)
is used; otherwise norm = 2 and the `2 -norm (or Euclidean distance) is used.
Constraint: norm ∈ {1, 2}.

8:

k – longOn entry: the number of nearest neighbours used in the computation.
Constraint: 0 < k < nrec.

9:

res[nrec] – double
OutputOn exit: res[i] contains the k-nearest neighbour approximation for the ith data record, fori = 0, 1, . . . , nrec − 1.

10:nn[nrec∗k] – long
OutputOn exit: if nn is set to 0, it is not referenced; otherwise nn[i ∗ k + j] contains the index in thetraining data for the jth nearest neighbour to the ith data record, for j = 0, 1, . . . , k − 1; fori = 0, 1, . . . , nrec − 1.

11:dist[nrec∗k] – double
OutputOn exit: if dist is set to 0, it is not referenced; otherwise dist[i ∗ k + j] contains the distance fromthe ith data record to its jth nearest neighbour, for j = 0, 1, . . . , k − 1; for i = 0, 1, . . . , nrec − 1.

Input

nagdmc knnp.1

nagdmc knnp

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

Output0: the function successfully completed its task.
i; i = i = 1, 2, 3, 4, 7, 8: the specification of the ith formal parameter was incorrect.
57: information in the binary tree has been corrupted.
99: the function failed to allocate enough memory.
100: an internal error occurred during the execution of the function.
> 100: an error occurred in a function specified by the user.

Notation
nrec
datakresthe number of data records in the analysis, n.
the data values, X.
the number of nearest neighbours used in the calculations, k.
the nearest neighbour approximations ŷi , for i = 1, 2, . . . , n.

Description
Let X be a set of n data records xi , for i = 1, 2, . . . , n, on p independent variables and a continuous
dependent variable y. The ith data record takes a value xij on the jth independent variable.
The k-nearest neighbour approach searches a set of training data records T (i.e., data records withknown values for y) to find the k-nearest data records to xi . Nearest neighbours are found by usinga binary tree search, e.g., see Bentley (1975). The proximity of xi to a member t of T is defined bya distance calculated over the independent variables and can defined by using one of:(a) the `1 -norm or Manhattan distance:pX|xij − tj |,j=1

where | · | denotes the modulus operator;(b) the `2 -norm or Euclidean distance:1/2pX
 (xij − tj )2  .
j=1

Let Si be a set containing the k-nearest neighbours in T to xi . Then the predicted value of y for
xi , ŷi , is given by the mean of its k-nearest neighbours:
1 Xŷi =ty .
k∀t∈Si

References and Further Reading
Bentley J L (1975) Multi-dimensional binary search trees used for associative searchingCommunications of the ACM 18(9) 509–517.
Duda R O and Hart P E (1972) Pattern Classification and Scene Analysis Wiley New York.
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 kdtree
nagdmc free kdtree
nagdmc load kdtree
nagdmc save kdtree
knnp ex.ccomputes a binary tree for a nearest neighbour analysis.
frees the memory containing a binary tree.
loads a binary tree from a file into memory.
writes a binary tree to file.
the example calling program.

nagdmc knnp.2