Visible to Intel only — GUID: GUID-708482E9-765F-4552-AE1F-C893B771566D
basic_statistics_dense_batch.cpp
basic_statistics_dense_online.cpp
column_accessor_homogen.cpp
cor_dense_batch.cpp
cor_dense_online.cpp
cov_dense_batch.cpp
cov_dense_biased_batch.cpp
cov_dense_biased_online.cpp
cov_dense_online.cpp
csr_accessor.cpp
csr_table.cpp
dbscan_brute_force_batch.cpp
df_cls_hist_batch.cpp
df_cls_hist_batch_random.cpp
df_cls_traverse_model.cpp
df_reg_hist_batch.cpp
df_reg_hist_batch_random.cpp
df_reg_traverse_model.cpp
heterogen_table.cpp
homogen_table.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
linear_regression_dense_online.cpp
logistic_regression_dense_batch.cpp
pca_cor_dense_batch.cpp
pca_cor_dense_online.cpp
pca_cov_dense_batch.cpp
pca_cov_dense_online.cpp
pca_precomputed_cor_dense_batch.cpp
pca_precomputed_cov_dense_batch.cpp
pca_svd_dense_batch.cpp
rbf_kernel_dense_batch.cpp
read_batch.cpp
svm_two_class_thunder_dense_batch.cpp
basic_statistics_dense_batch.cpp
basic_statistics_dense_online.cpp
column_accessor_homogen.cpp
connected_components_batch.cpp
cor_dense_batch.cpp
cor_dense_online.cpp
cov_dense_batch.cpp
cov_dense_biased_batch.cpp
cov_dense_biased_online.cpp
cov_dense_online.cpp
csr_accessor.cpp
csr_table.cpp
dbscan_brute_force_batch.cpp
df_cls_dense_batch.cpp
df_reg_dense_batch.cpp
directed_graph.cpp
graph_service_functions.cpp
heterogen_table.cpp
homogen_table.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
linear_regression_dense_online.cpp
logloss_dense_batch.cpp
louvain_batch.cpp
pca_cor_dense_batch.cpp
pca_cor_dense_online.cpp
pca_cov_dense_batch.cpp
pca_cov_dense_online.cpp
pca_precomputed_dense_batch.cpp
pca_svd_dense_batch.cpp
pca_svd_dense_online.cpp
polynomial_kernel_dense_batch.cpp
rbf_kernel_dense_batch.cpp
read_batch.cpp
shortest_paths_batch.cpp
sigmoid_kernel_dense_batch.cpp
subgraph_isomorphism_batch.cpp
svm_multi_class_thunder_csr_batch.cpp
svm_multi_class_thunder_dense_batch.cpp
svm_nu_cls_thunder_csr_batch.cpp
svm_nu_cls_thunder_dense_batch.cpp
svm_nu_reg_thunder_csr_batch.cpp
svm_nu_reg_thunder_dense_batch.cpp
svm_reg_thunder_csr_batch.cpp
svm_reg_thunder_dense_batch.cpp
svm_two_class_smo_csr_batch.cpp
svm_two_class_smo_dense_batch.cpp
svm_two_class_thunder_csr_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
Implicit Alternating Least Squares
Logistic Regression
Naïve Bayes Classifier
Support Vector Machine Classifier
Multi-class Classifier
Boosting
Visible to Intel only — GUID: GUID-708482E9-765F-4552-AE1F-C893B771566D
k-Nearest Neighbors Classification, Regression, and Search (k-NN)
k-NN classification, regression, and search algorithms are based on finding the k nearest observations to the training set. For classification, the problem is to infer the class of a new feature vector by computing the majority vote of its k nearest observations from the training set. For regression, the problem is to infer the target value of a new feature vector by computing the average target value of its k nearest observations from the training set. For search, the problem is to identify the k nearest observations from the training set to a new feature vector. The nearest observations are computed based on the chosen distance metric.
Operation |
Computational methods |
Programming Interface |
|||
Mathematical formulation
Training
Classification
Let 
be the training set of p-dimensional feature vectors, let 
be the set of class labels, where 
, 
, and C is the number of classes. 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.
Regression
Let be the training set of p-dimensional feature vectors, let be the corresponding continuous target outputs, 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.
Search
Let be the training set of p-dimensional feature vectors. Given X 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.
Training method: brute-force
The training operation produces the model that stores all the feature vectors from the initial training set X.
Training method: k-d tree
The training operation builds a k-d tree that partitions the training set X (for more details, see k-d Tree).
Inference
Classification
Let 
be the inference set of p-dimensional feature vectors. Given 
, the model produced at the training stage, and the number of nearest neighbors k, the problem is to predict the label 
from the Y set for each 
, 
, by performing the following steps:
Identify the set
of k feature vectors in the training set that are nearest to with respect to the Euclidean distance, which is chosen by default. The distance can be customized with the predefined set of pairwise distances: Minkowski distances with fractional degree (including Euclidean distance), Chebyshev distance, and Cosine 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
:
Regression
Let be the inference set of p-dimensional feature vectors. Given , the model produced at the training stage, and the number of nearest neighbors k, the problem is to predict the continuous target variable from the Y set for each , , by performing the following steps:
Identify the set
of k feature vectors in the training set that are nearest to with respect to the Euclidean distance, which is chosen by default. The distance can be customized with the predefined set of pairwise distances: Minkowski distances with fractional degree (including Euclidean distance), Chebyshev distance, and Cosine distance.Estimate the conditional expectation of the target variable based on the nearest neighbors
as the average of the target values for those neighbors:
Search
Let be the inference set of p-dimensional feature vectors. Given , the model produced at the training stage, and the number of nearest neighbors k:
Identify the set
of k feature vectors in the training set that are nearest to with respect to the Euclidean distance, which is chosen by default. The distance can be customized with the predefined set of pairwise distances: Minkowski distances with fractional degree (including Euclidean distance), Chebyshev distance, and Cosine distance.
Inference method: brute-force
Brute-force inference method determines the set of the nearest feature vectors by iterating over all the pairs 
in the implementation defined order, 
, 
.
Inference method: k-d tree
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 neighbors is progressively updated during the 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, 
.
Programming Interface
Refer to API Reference: k-Nearest Neighbors Classification, Regression, and Search.
The following table describes current device support:
Task |
CPU |
GPU |
|---|---|---|
Classification |
Yes |
Yes |
Regression |
No |
Yes |
Search |
Yes |
Yes |
Distributed mode
The algorithm supports distributed execution in SPMD mode (only on GPU).
Usage Example
Training
knn::model<> run_training(const table& data,
const table& labels) {
const std::int64_t class_count = 10;
const std::int64_t neighbor_count = 5;
const auto knn_desc = knn::descriptor<float>{class_count, neighbor_count};
const auto result = train(knn_desc, data, labels);
return result.get_model();
}Inference
table run_inference(const knn::model<>& model,
const table& new_data) {
const std::int64_t class_count = 10;
const std::int64_t neighbor_count = 5;
const auto knn_desc = knn::descriptor<float>{class_count, neighbor_count};
const auto result = infer(knn_desc, model, new_data);
print_table("labels", result.get_labels());
}Examples
oneAPI DPC++
Batch Processing:
oneAPI C++
Batch Processing:
Python* with DPC++ support
Distributed Processing: