Mathematical formulation

Let be the training set of

p

-dimensional feature vectors, let be the set of class labels, where , . Given

X

,

Y

and the number of nearest neighbors

k

, the problem is to build a model that allows distance computation between the feature vectors in training and inference sets at the inference stage.

Let be the inference set of

p

-dimensional feature vectors. Given

X’

, the model produced at the training stage and the number of nearest neighbors

k

, the problem is to predict the label for each , , by performing the following steps:

Identify the set of the
k
feature vectors in the training set that are nearest to with respect to the Euclidean distance.
Estimate the conditional probability for the
l
-th class as the fraction of vectors in whose labels are equal to
l
:

Predict the class that has the highest probability for the feature vector :

Brute-force inference method determines the set of the nearest feature vectors by iterating over all the pairs in the implementation defined order, , . The final prediction is computed according to the equations (1) and (2).

K-d tree inference method traverses the

k

-

d

tree to find feature vectors associated with a leaf node that are closest to , . The set of the currently-known nearest

k

-th neighbors is progressively updated during tree traversal. The search algorithm limits exploration of the nodes for which the distance between the and respective part of the feature space is not less than the distance between and the most distant feature vector from . Once tree traversal is finished, . The final prediction is computed according to the equations (1) and (2).

Programming Interface

template<typename

Float

= detail::descriptor_base<>::float_t, typename

Method

= detail::descriptor_base<>::method_t, typename

Task

= detail::descriptor_base<>::task_t>

class

descriptor

Template Parameters

Float
– The floating-point type that the algorithm uses for intermediate computations. Can be
float
or
double
.
Method
– Tag-type that specifies an implementation of algorithm. Can be
method::bruteforce
or
method::kd_tree
.
Task
– Tag-type that specifies type of the problem to solve. Can be
task::classification
.

Constructors

descriptor

(std::int64_t

class_count

, std::int64_t

neighbor_count

)

Creates a new instance of the class with the given

class_count

and

neighbor_count

property values.

Public Methods

auto &

set_class_count

(std::int64_t

value

)

auto &

set_neighbor_count

(std::int64_t

value

)

struct

brute_force

Tag-type that denotes brute-force computational method.

struct

kd_tree

Tag-type that denotes k-d tree computational method.

using

by_default

= brute_force

Alias tag-type for brute-force computational method.

struct

classification

Tag-type that parameterizes entities used for solving classification problem.

using

by_default

= classification

Alias tag-type for classification task.

template<typename

Task

= task::by_default>

class

model

Template Parameters

Task

– Tag-type that specifies type of the problem to solve. Can be

task::classification

.

Constructors

model

()

Creates a new instance of the class with the default property values.

template<typename

Task

= task::by_default>

class

train_input

Template Parameters

Task

– Tag-type that specifies type of the problem to solve. Can be

task::classification

.

Constructors

train_input

(

const

table &

data

,

const

table &

labels

)

Creates a new instance of the class with the given

data

and

labels

property values.

Properties

const

table &

data

= table{}

The training set .

Getter & Setter

const table & get_data() const
auto & set_data(const table &data)

const

table &

labels

= table{}

Vector of labels for the training set .

Getter & Setter

const table & get_labels() const
auto & set_labels(const table &labels)

template<typename

Task

= task::by_default>

class

train_result

Template Parameters

Task

– Tag-type that specifies type of the problem to solve. Can be

task::classification

.

Constructors

train_result

()

Creates a new instance of the class with the default property values.

Properties

const

model<Task> &

model

= model<Task>{}

The trained -NN model.

Getter & Setter

const model< Task > & get_model() const
auto & set_model(const model< Task > &value)

template<typename

Task

= task::by_default>

class

infer_input

Template Parameters

Task

– Tag-type that specifies type of the problem to solve. Can be

task::classification

.

Constructors

infer_input

(

const

table &

data

,

const

model<Task> &

model

)

Creates a new instance of the class with the given

model

and

data

property values.

Properties

const

table &

data

= table{}

The dataset for inference .

Getter & Setter

const table & get_data() const
auto & set_data(const table &data)

const

model<Task> &

model

= model<Task>{}

The trained -NN model.

Getter & Setter

const model< Task > & get_model() const
auto & set_model(const model< Task > &m)

template<typename

Task

= task::by_default>

class

infer_result

Template Parameters

Task

– Tag-type that specifies type of the problem to solve. Can be

task::classification

.

Constructors

infer_result

()

Creates a new instance of the class with the default property values.

Properties

const

table &

labels

= table{}

The predicted labels.

Getter & Setter

const table & get_labels() const
auto & set_labels(const table &value)