C: k-nearest-neighbors classification
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).
C
#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;
}