nagdmc knnc

NAG DMC

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

Declaration#include <nagdmc.h>void nagdmc knnc(long rec1, long nvar, long nrec, long dblk, double data[],long iproot, double prior[], double rho, long uc, int norm,
long k, long res[], long nn[], double dist[], 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:iproot – longInput

On entry: the integer value of the root node of a binary tree as returned by nagdmc kdtree.
7:

prior[c] – double

Input

On entry: if prior is set to 0, uniform priors are used; otherwise prior[i] gives the prior probability
for the ith of c categories on the dependent variable in the analysis, for i = 0, 1, . . . , c − 1.
Constraints: if prior is not 0, prior[i] ≥ 0, for i = 0, 1, . . . , c − 1, and the elements in prior mustsum equal to one.
8:

rho – double

Input

On entry: the value of maximum probability of group membership that must be exceeded forclassification. Each data record with a maximum probability of group membership less than orequal to rho is classified as uc.
Constraint: 0 ≤ rho < 1.
9:

uc – double

Input

On entry: the value that should be assigned to data records if the value of rho is not exceeded.
10:

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}.

nagdmc knnc.1

nagdmc knnc

NAG DMC11:k – long

Input

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

res[nrec] – long

OutputOn exit: res[i] contains the k-nearest neighbour classification of the ith data record, fori = 0, 1, . . . , nrec − 1.
13:nn[nrec∗k] – longOutput

On 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.
14: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.
15:

info – int *OutputOn exit: info gives information on the success of the function call:
0: the function successfully completed its task.
i; i = i = 1, 2, 3, 4, 7, 8, 10, 11: 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.

Notation
nrec
datapriorrhouckresthe number of data records to classify, n.
the data values, X.
the prior probabilities pl , for l = 1, 2, . . . , c.
the threshold for accepting classifications, ρ.
the dummy value representing unclassified data records, z.
the number of nearest neighbours used in the calculations, k.
the nearest neighbour classifications 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 categoricaldependent variable y. The jth value of the ith data record is denoted by xij . Each member of X
is to be classified into one of c categories where the prior probability of the lth category is pl , forl = 1, 2, . . . , c.
The k-nearest neighbour approach searches a set of training data records T (i.e., data records withknown categories for y) to find the k-nearest data records to xi . Nearest neighbours are found byusing a binary tree search, e.g., see Bentley (1975). The proximity of xi to a member t of T isdefined by a 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

nagdmc knnc.2

nagdmc knnc

NAG DMCLet Si be a set containing the k-nearest neighbours in T to xi , and hil be the number of membersof Si belonging to the lth category. The posterior probability θil of xi belonging to the lth category
is given by,pl hil.
m=1 pm him

θil = Pc

Let q denote the index of the maximum value in θil , for l = 1, 2, . . . , c. Given a user-supplied valuefor ρ, xi is classified by setting the ith value of the dependent variable, ŷi , to category value q if
θiq > ρ; otherwise xi is unclassified and ŷi is assigned a dummy value, say z.

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.
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
knnc 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 knnc.3