C: k-nearest-neighbors classification

The concept

k-nearest neighbours classifies a new point by looking at the k closest training points and choosing the most common label among them. There is no training step: the training data itself is the model. The distance is usually Euclidean, computed with sqrt, which needs the math library (link with -lm).

The program stores each training point with its label and its distance to the query, sorts by distance with qsort, and counts the labels among the first k. A small k follows noise, while a large k blurs the boundary. When features have very different scales, they should be normalized first.

Code example

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  double x, y;
  char label;
  double dist;
} Point;

static int by_distance(const void *p, const void *q) {
  double a = ((const Point *)p)->dist;
  double b = ((const Point *)q)->dist;
  return (a > b) - (a < b);
}

static char classify(const Point *train, int n, double qx, double qy, int k) {
  Point copy[8];
  for (int i = 0; i < n; i++) {
    copy[i] = train[i];
    copy[i].dist = hypot(copy[i].x - qx, copy[i].y - qy);
  }
  qsort(copy, (size_t)n, sizeof copy[0], by_distance);

  int votes_a = 0, votes_b = 0;
  for (int i = 0; i < k; i++) {
    if (copy[i].label == 'A') {
      votes_a++;
    } else {
      votes_b++;
    }
  }
  return votes_a > votes_b ? 'A' : 'B';
}

int main(void) {
  Point train[] = {
    {1, 1, 'A', 0}, {1, 2, 'A', 0}, {2, 1, 'A', 0},
    {6, 6, 'B', 0}, {7, 6, 'B', 0}, {6, 7, 'B', 0},
  };
  printf("(5,5) -> %c\n", classify(train, 6, 5, 5, 3));
  printf("(2,2) -> %c\n", classify(train, 6, 2, 2, 3));
  printf("(3,3) with k=5 -> %c\n", classify(train, 6, 3, 3, 5));
  return 0;
}

(5,5) -> B
(2,2) -> A
(3,3) with k=5 -> A

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

(5,5) -> B

(5,5) -> B
(2,2) -> A
(3,3) with k=5 -> A

Behind the scenes

Cost and common mistakes

O(n log n) per query for n training points with this sort. A selection of the k nearest takes O(n).

• The copy array has room for 8 points. A larger training set needs a larger array or dynamic allocation.
• Ties between classes occur with an even k. Pick an odd k for two classes or define a tie-break.
• The classifier compares the query with every training point, so it gets slow as the data grows.

Try it yourself

How would you handle three classes?

Further reading

• C reference (cppreference) (external)
• C11 committee draft (N1570) (external)
• Mathematics for Machine Learning (external)