Visible to Intel only — GUID: GUID-8006D5FC-23C2-4281-984A-B9EA43395249
basic_statistics_dense_batch.cpp
column_accessor_homogen.cpp
cor_dense_batch.cpp
cov_dense_batch.cpp
dbscan_brute_force_batch.cpp
df_cls_hist_batch.cpp
df_cls_traverse_model.cpp
df_reg_hist_batch.cpp
df_reg_traverse_model.cpp
kmeans_init_dense.cpp
kmeans_lloyd_dense_batch.cpp
knn_cls_brute_force_dense_batch.cpp
knn_reg_brute_force_dense_batch.cpp
knn_search_brute_force_dense_batch.cpp
linear_kernel_dense_batch.cpp
linear_regression_dense_batch.cpp
pca_cor_dense_batch.cpp
pca_precomputed_cor_dense_batch.cpp
pca_precomputed_cov_dense_batch.cpp
rbf_kernel_dense_batch.cpp
svm_two_class_thunder_dense_batch.cpp
basic_statistics_dense_batch.cpp
column_accessor_homogen.cpp
connected_components_batch.cpp
cor_dense_batch.cpp
cov_dense_batch.cpp
dbscan_brute_force_batch.cpp
df_cls_dense_batch.cpp
df_reg_dense_batch.cpp
directed_graph.cpp
graph_service_functions.cpp
jaccard_batch.cpp
jaccard_batch_app.cpp
kmeans_init_dense.cpp
kmeans_lloyd_dense_batch.cpp
knn_cls_brute_force_dense_batch.cpp
knn_cls_kd_tree_dense_batch.cpp
knn_search_brute_force_dense_batch.cpp
linear_kernel_dense_batch.cpp
linear_regression_dense_batch.cpp
louvain_batch.cpp
pca_dense_batch.cpp
pca_precomputed_dense_batch.cpp
polynomial_kernel_dense_batch.cpp
rbf_kernel_dense_batch.cpp
shortest_paths_batch.cpp
sigmoid_kernel_dense_batch.cpp
subgraph_isomorphism_batch.cpp
svm_multi_class_thunder_dense_batch.cpp
svm_nu_cls_thunder_dense_batch.cpp
svm_nu_reg_thunder_dense_batch.cpp
svm_reg_thunder_dense_batch.cpp
svm_two_class_smo_dense_batch.cpp
svm_two_class_thunder_dense_batch.cpp
triangle_counting_batch.cpp
K-Means Clustering
Density-Based Spatial Clustering of Applications with Noise
Correlation and Variance-Covariance Matrices
Principal Component Analysis
Principal Components Analysis Transform
Singular Value Decomposition
Association Rules
Kernel Functions
Expectation-Maximization
Cholesky Decomposition
QR Decomposition
Outlier Detection
Distance Matrix
Distributions
Engines
Moments of Low Order
Quantile
Quality Metrics
Sorting
Normalization
Optimization Solvers
Decision Forest
Decision Trees
Gradient Boosted Trees
Stump
Linear and Ridge Regressions
LASSO and Elastic Net Regressions
k-Nearest Neighbors (kNN) Classifier
Details
Batch Processing
Examples
Implicit Alternating Least Squares
Logistic Regression
Naïve Bayes Classifier
Support Vector Machine Classifier
Multi-class Classifier
Boosting
Visible to Intel only — GUID: GUID-8006D5FC-23C2-4281-984A-B9EA43395249
k-Nearest Neighbors (kNN) Classifier
NOTE:
k-Nearest Neighbors Classifier is also available with oneAPI interfaces:
k-Nearest Neighbors (kNN) classification is a non-parametric classification algorithm. The model of the kNN classifier is based on feature vectors and class labels from the training data set. This classifier induces the class of the query vector from the labels of the feature vectors in the training data set to which the query vector is similar. A similarity between feature vectors is determined by the type of distance (for example, Euclidian) in a multidimensional feature space.
Details
Given n feature vectors 
of size p and a vector of class labels 
, where 
and C is the number of classes, describes the class to which the feature vector 
belongs, the problem is to build a kNN classifier.
Given a positive integer parameter k and a test observation 
, the kNN classifier does the following:
Identifies the set
of the k feature vectors in the training data that are closest to according to the distance metricEstimates the conditional probability for the class j as the fraction of vectors in
whose labels y are equal to jAssigns the class with the largest probability to the test observation
On CPU, kNN classification might use K-D tree, a space-partitioning data structure, or Brute Force search to find nearest neighbors, while on GPU only Brute Force search is available.
K-D tree
On CPU, the library provides kNN classification based on multidimensional binary search tree (K-D tree, where D means the dimension and K means the number of dimensions in the feature space). For more details, see [James2013], [Patwary2016].
oneDAL version of the kNN algorithm with K-D trees uses the PANDA algorithm [Patwary2016].
Each non-leaf node of a tree contains the identifier of a feature along which to split the feature space and an appropriate feature value (a cut-point) that defines the splitting hyperplane to partition the feature space into two parts. Each leaf node of the tree has an associated subset (a bucket) of elements of the training data set. Feature vectors from any bucket belong to the region of the space defined by tree nodes on the path from the root node to the respective leaf.
Brute Force
Brute Force kNN algorithm calculates the squared distances from each query feature vector to each reference feature vector in the training data set. Then, for each query feature vector it selects k objects from the training set that are closest to that query feature vector. For details, see [Li2015], [Verma2014].
Training Stage
Training using K-D Tree
For each non-leaf node, the process of building a K-D tree involves the choice of the feature (that is, dimension in the feature space) and the value for this feature (a cut-point) to split the feature space. This procedure starts with the entire feature space for the root node of the tree, and for every next level of the tree deals with ever smaller part of the feature space.
The PANDA algorithm constructs the K-D tree by choosing the dimension with the maximum variance for splitting [Patwary2016].
Therefore, for each new non-leaf node of the tree, the algorithm computes the variance of values that belong to the respective region of the space for each of the features and chooses the feature with the largest variance. Due to high computational cost of this operation, PANDA uses a subset of feature values to compute the variance.
PANDA uses a sampling heuristic to estimate the data distribution for the chosen feature and chooses the median estimate as the cut-point.
PANDA generates new K-D tree levels until the number of feature vectors in a leaf node gets less or equal to a predefined threshold. Once the threshold is reached, PANDA stops growing the tree and associates the feature vectors with the bucket of the respective leaf node.
Training using Brute Force
During training with the Brute Force approach, the algorithm stores all feature vectors from the training data set to calculate their distances to the query feature vectors.
Prediction Stage
Given kNN classifier and query vectors 
, the problem is to calculate the labels for those vectors.
Prediction using K-D Tree
To solve the problem for each given query vector , the algorithm traverses the K-D tree to find feature vectors associated with a leaf node that are closest to . During the search, the algorithm limits exploration of the nodes for which the distance between the query vector and respective part of the feature space is not less than the distance from the 
neighbor. This distance is progressively updated during the tree traverse.
Prediction using Brute Force
To solve the problem, the algorithm computes distances between vectors from training and testing sets: 
. For example, if Euclidean distance is used, 
would be the following:
K training vectors with minimal distance to the testing vector are the nearest neighbors the algorithms searches for.
Batch Processing
kNN classification follows the general workflow described in Classification Usage Model.
Training
For a description of the input and output, refer to Usage Model: Training and Prediction.
At the training stage, both Brute Force and K-D tree based kNN classifier have the following parameters:
Parameter |
Default Value |
Description |
|---|---|---|
algorithmFPType |
float |
The floating-point type that the algorithm uses for intermediate computations. Can be float or double. |
method |
defaultDense |
The computation method used by kNN classification. The only training method supported so far is the default dense method. |
nClasses |
2 |
The number of classes. |
dataUseInModel |
doNotUse |
A parameter to enable/disable use of the input data set in the kNN model. Possible values:
K-D tree based kNN reorders feature vectors and corresponding labels in the input data set or its copy to improve performance at the prediction stage. If the value is doUse, do not deallocate the memory for input data and labels. |
engine |
SharePtr< engines:: mt19937:: Batch>() |
Pointer to the random number generator engine that is used internally to perform sampling needed to choose dimensions and cut-points for the K-D tree. |
Prediction
For a description of the input and output, refer to Usage Model: Training and Prediction.
At the prediction stage, both Brute Force and K-D tree based kNN classifier have the following parameters:
Parameter |
Default Value |
Description |
|---|---|---|
algorithmFPType |
float |
The floating-point type that the algorithm uses for intermediate computations. Can be float or double. |
method |
defaultDense |
The computation method used kNN classification. The only prediction method supported so far is the default dense method. |
nClasses |
2 |
The number of classes. |
k |
1 |
The number of neighbors. |
resultsToCompute |
0 |
The 64-bit integer flag that specifies which extra characteristics of the kNN algorithm to compute. Provide one of the following values to request a single characteristic or use bitwise OR to request a combination of the characteristics:
|
voteWeights |
voteUniform |
The voting method for prediction:
|
Output
In addition to classifier output, kNN calculates the results described below. Pass the Result ID as a parameter to the methods that access the result of your algorithm.
Result ID |
Result |
|---|---|
indices |
A numeric table
NOTE:
By default, this result is an object of the HomogenNumericTable class, but you can define the result as an object of any class derived from NumericTable.
|
distances |
A numeric table
NOTE:
By default, this result is an object of the HomogenNumericTable class, but you can define the result as an object of any class derived from NumericTable.
|
containing indices of rows from training dataset that are nearest neighbors computed when the computeIndicesOfNeigtbors option is on.Examples
oneAPI DPC++
Batch Processing:
dpc_knn_cls_brute_force_dense_batch.cpp
oneAPI C++
Batch Processing:
cpp_knn_cls_kd_tree_dense_batch.cpp
C++ (CPU)
Batch Processing:
Java*
NOTE:
There is no support for Java on GPU.
Batch Processing:
Python* with DPC++ support
Batch Processing:
Python*
Batch Processing: