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.

  1. Initialize a aoclda.nearest_neighbors.knn_classifier() object with options set in the class constructor.

  2. Fit the k-NN for your training data set using aoclda.nearest_neighbors.knn_classifier.fit().

  3. Compute the indices of the nearest neighbors and optionally the corresponding distances using aoclda.nearest_neighbors.knn_classifier.kneighbors().

  4. If only the labels of the test data are required, use aoclda.nearest_neighbors.knn_classifier.predict(). Note that a previous call to aoclda.nearest_neighbors.knn_classifier.kneighbors() is not required.

  5. If the probability estimates for each label are required, use aoclda.nearest_neighbors.knn_classifier.predict_proba(). Note that a previous call to aoclda.nearest_neighbors.knn_classifier.kneighbors() is not required.

  1. Initialize a da_handle with da_handle_type da_handle_knn.

  2. Pass data to the handle using da_knn_set_training_data_?.

  3. Set the number of neighbors required and the metric or weights used in k-NN using da_options_set_? (see below).

  4. Compute the indices to the nearest neighbors and optionally the corresponding distances using da_knn_kneighbors_?.

  5. If only the labels of the test data are required, use da_knn_predict_?.

  6. 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_?:

Table of options for k-Nearest Neighbors.#

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}