k-Nearest Neighbors (k-NN)#
This chapter contains functions for computing the k-nearest neighbors of a test data set and a training data set. Nearest neighbors functionality provided in this chapter can be used for classification.
The k-nearest neighbors algorithm is a supervised learning method used for classification and regression. For each point \(x_i\) of a test data set \(X_{test}\), this algorithm computes the \(k\) points of a given training set \(X_{train}\) which are the most similar to \(x_i\).
In addition, when a vector \(y_{train}\) with the associated labels for each data point in \(X_{train}\) is provided, this algorithm computes the predicted labels of the test data \(X_{test}\). A query point \(x_i\) of \(X_{test}\) is labeled using the majority vote of the neighbors. In case of a tie, the first class label is returned by convention.
Outputs from k-nearest neighbors#
The following results can be computed with this algorithm:
indices of nearest neighbors - the indices of the nearest neighbors for each data point, provided in order of distance (closest first).
distances to the nearest neighbors - the corresponding distances to each data point.
number of classes - the number of available class labels. Used to allocate memory for the probability prediction.
class labels - the available class labels, sorted in ascending order.
probability estimates - the probability that data points are labeled according to the available classes.
predicted labels - the predicted label for each of the queries in \(X_{test}\).
Typical workflow for k-NN#
The standard way of computing the k-nearest neighbors using AOCL-DA is as follows.
Initialize a
aoclda.nearest_neighbors.knn_classifier()object with options set in the class constructor.Fit the k-NN for your training data set using
aoclda.nearest_neighbors.knn_classifier.fit().Compute the indices of the nearest neighbors and optionally the corresponding distances using
aoclda.nearest_neighbors.knn_classifier.kneighbors().If only the labels of the test data are required, use
aoclda.nearest_neighbors.knn_classifier.predict(). Note that a previous call toaoclda.nearest_neighbors.knn_classifier.kneighbors()is not required.If the probability estimates for each label are required, use
aoclda.nearest_neighbors.knn_classifier.predict_proba(). Note that a previous call toaoclda.nearest_neighbors.knn_classifier.kneighbors()is not required.
Initialize a
da_handlewithda_handle_typeda_handle_knn.Pass data to the handle using da_knn_set_training_data_?.
Set the number of neighbors required and the metric or weights used in k-NN using da_options_set_? (see below).
Compute the indices to the nearest neighbors and optionally the corresponding distances using da_knn_kneighbors_?.
If only the labels of the test data are required, use da_knn_predict_?.
If the probability estimates for each label are required, use da_knn_predict_proba_?. To allocate the appropriate memory space for the predicted probabilities, use da_knn_classes_?.
Options#
The available Python options are detailed in the aoclda.nearest_neighbors.knn_classifier() class constructor.
The following options can be set using da_options_set_?:
Option name |
Type |
Default |
Description |
Constraints |
|---|---|---|---|---|
weights |
string |
\(s=\) uniform |
Weight function used to compute the k-nearest neighbors. |
\(s=\) distance, or uniform. |
metric |
string |
\(s=\) euclidean |
Metric used to compute the pairwise distance matrix. |
\(s=\) euclidean, or sqeuclidean. |
algorithm |
string |
\(s=\) brute |
Algorithm used to compute the k-nearest neighbors. |
\(s=\) brute. |
number of neighbors |
integer |
\(i=5\) |
Number of neighbors considered for k-nearest neighbors. |
\(1 \le i\) |
Examples#
The code below is supplied with your installation (see Python examples).
1# Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
2#
3# Redistribution and use in source and binary forms, with or without modification,
4# are permitted provided that the following conditions are met:
5# 1. Redistributions of source code must retain the above copyright notice,
6# this list of conditions and the following disclaimer.
7# 2. Redistributions in binary form must reproduce the above copyright notice,
8# this list of conditions and the following disclaimer in the documentation
9# and/or other materials provided with the distribution.
10# 3. Neither the name of the copyright holder nor the names of its contributors
11# may be used to endorse or promote products derived from this software without
12# specific prior written permission.
13#
14# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17# IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23# POSSIBILITY OF SUCH DAMAGE.
24#
25
26"""
27k-nearest neighbors classification example Python script
28"""
29
30import sys
31import numpy as np
32from aoclda.nearest_neighbors import knn_classifier
33
34def knn_classifier_example():
35 """
36 k-Nearest Neighbors classification
37 """
38
39 # Define data arrays
40 x_train = np.array([[-1, -1, 2],
41 [-2, -1, 3],
42 [-3, -2, -1],
43 [1, 3, 1],
44 [2, 5, 1],
45 [3, -1, 2]])
46
47 y_train = np.array([1, 2, 0, 1, 2, 2])
48
49 x_test = np.array([[-2 , 2, 3],
50 [-1, -2, -1],
51 [2, 1, -3]])
52
53 print("\nk-nearest neighbors for a small data matrix\n")
54 knn = knn_classifier()
55 knn.fit(x_train, y_train)
56 print(x_train)
57 k_dist, k_ind = knn.kneighbors(x_test, n_neighbors=3, return_distance=True)
58 proba = knn.predict_proba(x_test)
59 y_test = knn.predict(x_test)
60
61 # Print results
62 print("\nIndices of the nearest neighbors:\n")
63 print(k_ind)
64 print("\nCorresponding distances of the nearest neighbors:\n")
65 print(k_dist)
66 print("\nProbability estimates for the test data matrix:\n")
67 print(proba)
68 print("\nPredicted labels for the test data matrix:\n")
69 print(y_test)
70
71 # Check against expected results
72 expected_ind = np.array([[1, 0, 3],
73 [2, 0, 1],
74 [3, 5, 4]])
75 expected_dist = np.array([[3. , 3.31662479, 3.74165739 ],
76 [2. , 3.16227766, 4.24264069 ],
77 [4.58257569, 5.47722558, 5.65685425]])
78 expected_proba = np.array([[0.2, 0.4, 0.4],
79 [0.2, 0.4, 0.4],
80 [0.2, 0.4, 0.4]])
81 expected_labels = np.array([[1, 1, 1]])
82
83 norm_dist = np.linalg.norm(k_dist - expected_dist)
84 norm_proba = np.linalg.norm(proba - expected_proba)
85 incorrect_indices = np.any(k_ind - expected_ind)
86 incorrect_labels = np.any(y_test - expected_labels)
87
88 tol = 1.0e-8
89
90 if norm_dist > tol or norm_proba > tol or incorrect_indices or incorrect_labels:
91 print("\nSolution is not within expected tolerance\n")
92 print("norm_dist = ", norm_dist)
93 print("norm_proba = ", norm_proba)
94 print("incorrect_indices = ", incorrect_indices)
95 print("incorrect_labels = ", incorrect_labels)
96 sys.exit(1)
97
98 print("\nk-nearest neighbors successfully computed\n")
99
100if __name__ == "__main__":
101 try:
102 knn_classifier_example()
103 except RuntimeError:
104 sys.exit(1)
The code below can be found in knn.cpp in the examples folder of your installation.
1/*
2 * Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification,
5 * are permitted provided that the following conditions are met:
6 * 1. Redistributions of source code must retain the above copyright notice,
7 * this list of conditions and the following disclaimer.
8 * 2. Redistributions in binary form must reproduce the above copyright notice,
9 * this list of conditions and the following disclaimer in the documentation
10 * and/or other materials provided with the distribution.
11 * 3. Neither the name of the copyright holder nor the names of its contributors
12 * may be used to endorse or promote products derived from this software without
13 * specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
19 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
21 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 *
26 */
27
28#include "aoclda.h"
29#include <iostream>
30#include <vector>
31
32/*
33 * Basic k-nearest neighbors (kNN) example
34 *
35 * This example computes k-nearest neighbors classification for a small data matrix.
36 */
37
38int main() {
39 std::cout << "--------------------------------------------" << std::endl;
40 std::cout << "k-Nearest Neighbors model (double precision)" << std::endl;
41 std::cout << "--------------------------------------------" << std::endl;
42 std::cout << std::fixed;
43 std::cout.precision(5);
44
45 da_status status;
46 bool pass = true;
47
48 // Input data
49 da_int n_features = 3;
50 da_int n_samples = 6;
51 da_int n_queries = 3;
52 da_int n_neigh = 3;
53 std::vector<double> X_train{-1., -2., -3., 1., 2., 3., -1., -1., -2.,
54 3., 5., -1., 2., 3., -1., 1., 1., 2.};
55 std::vector<da_int> y_train{1, 2, 0, 1, 2, 2};
56
57 // Set up and train the kNN
58 da_handle knn_handle = nullptr;
59 pass = da_handle_init_d(&knn_handle, da_handle_knn) == da_status_success;
60 pass &= da_knn_set_training_data_d(knn_handle, n_samples, n_features, X_train.data(),
61 n_samples, y_train.data()) == da_status_success;
62 // Set options
63 pass &= da_options_set_int(knn_handle, "number of neighbors", n_neigh) ==
64 da_status_success;
65 pass &= da_options_set_string(knn_handle, "metric", "euclidean") == da_status_success;
66 pass &= da_options_set_string(knn_handle, "weights", "uniform") == da_status_success;
67 if (!pass) {
68 std::cout << "Something went wrong setting up the knn data and "
69 "optional parameters.\n";
70 return 1;
71 }
72
73 std::vector<double> X_test{-2., -1., 2., 2., -2., 1., 3., -1., -3.};
74
75 // Compute the k-nearest neighbors and return the distances
76 std::vector<double> k_dist(n_neigh * n_queries);
77 std::vector<da_int> k_ind(n_neigh * n_queries);
78 status = da_knn_kneighbors_d(knn_handle, n_queries, n_features, X_test.data(),
79 n_queries, k_ind.data(), k_dist.data(), n_neigh, 1);
80
81 if (status != da_status_success) {
82 std::cout << "Failure while computing the neighbors\n";
83 return 1;
84 }
85 std::cout << "The indices of neighbors\n";
86 for (da_int i = 0; i < n_queries; i++) {
87 for (da_int j = 0; j < n_neigh; j++) {
88 std::cout << k_ind[i + j * n_queries] << " ";
89 }
90 std::cout << std::endl;
91 }
92 std::cout << std::endl;
93
94 std::cout << "\n\nThe corresponding distances\n";
95 for (da_int i = 0; i < n_queries; i++) {
96 for (da_int j = 0; j < n_neigh; j++) {
97 std::cout << k_dist[i + j * n_queries] << " ";
98 }
99 std::cout << std::endl;
100 }
101 std::cout << std::endl;
102
103 da_int n_classes = 0; // Set n_classes to zero to do query for the required memory
104 status = da_knn_classes_d(knn_handle, &n_classes, nullptr);
105 std::cout << "\n\nThe number of available classes\n";
106 std::cout << n_classes << std::endl;
107
108 // Allocate required memory for classes
109 std::vector<da_int> classes(n_classes);
110 status = da_knn_classes_d(knn_handle, &n_classes, classes.data());
111 std::cout << "\n\nThe corresponding classes, sorted in ascending order\n";
112 for (auto &ic : classes)
113 std::cout << ic << std::endl;
114
115 // Allocate required memory for classes
116 std::vector<double> proba(n_queries * n_classes);
117 status = da_knn_predict_proba_d(knn_handle, n_queries, n_features, X_test.data(),
118 n_queries, proba.data());
119 if (status != da_status_success) {
120 std::cout << "Failure while computing the probabilities\n";
121 return 1;
122 }
123
124 std::cout << "\n\nThe probabilities\n";
125 for (da_int i = 0; i < n_queries; i++) {
126 for (da_int j = 0; j < n_classes; j++) {
127 std::cout << proba[i + j * n_queries] << " ";
128 }
129 std::cout << std::endl;
130 }
131 std::cout << std::endl;
132
133 // Allocate memory for predicted labels for test data
134 std::vector<da_int> y_test(n_queries);
135 status = da_knn_predict_d(knn_handle, n_queries, n_features, X_test.data(), n_queries,
136 y_test.data());
137 if (status != da_status_success) {
138 std::cout << "Failure while computing the predicted labels\n";
139 return 1;
140 }
141 std::cout << "\n\nThe label estimates\n";
142 for (auto &iy : y_test)
143 std::cout << iy << std::endl;
144
145 da_handle_destroy(&knn_handle);
146
147 return 0;
148}