Concept · beginner
k-nearest neighbors
Classify a point by the majority vote of its closest neighbors.
k-nearest neighbors (kNN) classifies a new point by finding the labelled points closest to it and taking a majority vote. The assumption is that things that measure alike are probably the same kind. There is no training step: kNN keeps every training point and does its work when you ask about a new one. The data is the model.
The dataset
data.csv holds 200 synthetic wheat seeds, 100 each of two varieties, kama
and rosa, with kernel length_mm and width_mm. We drew it once with
make_data.py (fixed seed 20261031) from normal distributions: kama seeds
centered at 5.5 mm by 3.2 mm, rosa at 6.2 mm by 3.6 mm. The varieties overlap
a little, so some seeds are genuinely hard to call. The rows are shuffled,
and the split column marks 150 as train and 50 as test.
The generator rejects any draw where a test seed’s 5th and 6th nearest training seeds are less than 10⁻⁶ mm apart in distance; it took 32 draws to pass. Otherwise, which seed got 5th place would depend on each language’s tie-breaking or floating-point rounding, and the answers could differ.
The method
For each test seed, with :
- Compute the Euclidean distance to every training seed: .
- Take the 5 nearest training seeds.
- Predict the variety most of them have. With two varieties and an odd , the vote cannot tie.
Deep inside a cluster, every neighbor agrees: 40 of the 50 test seeds got a 5–0 vote. Near the border, neighbors mix. Take the test seed at 5.96 mm by 3.21 mm, a kama:
| Neighbor (length × width) | Variety | Distance (mm) |
|---|---|---|
| 5.99 × 3.18 | rosa | 0.042 |
| 5.94 × 3.27 | kama | 0.063 |
| 5.88 × 3.14 | kama | 0.106 |
| 5.90 × 3.12 | kama | 0.108 |
| 5.93 × 3.35 | rosa | 0.143 |
Kama wins 3 to 2, correctly, even though the single nearest seed is a rosa. With this seed would be misclassified. A larger outvotes one unlucky neighbor; too large a pulls in seeds from far away.
Reading the results
47 of the 50 test seeds are classified correctly, an accuracy of 0.94. The three misses were all 3–2 votes in the overlap. A rosa at 5.84 × 3.32 is closer to the kama center than to its own, a kama at 6.06 × 3.21 is closer to the rosa center, and a kama at 5.87 × 3.36 is nearly equidistant (0.403 mm versus 0.408 mm). Any method that sees only length and width would struggle with them.
Distance adds up differences across features, so a feature measured in bigger numbers counts for more. Here both are millimetres with similar spreads: standard deviations of 0.46 mm for length and 0.27 mm for width. Record width in micrometres and length stops counting: accuracy drops to 45 of 50, the same as using width alone. The fix is feature scaling, such as rescaling each feature to a standard deviation of 1.
What to watch for across languages
None of these implementations calls a ready-made kNN classifier. They use
general tools: arithmetic, square roots, Python’s math.dist, Fortran’s
norm2, sorting, and counting helpers such as Counter, tally,
table(), Elixir’s Enum.frequencies, and SQL’s count. Go, Rust, C++, Java, JavaScript, Julia, Swift, Haskell, Common Lisp, OCaml, Prolog, Tcl, Lua, and Perl have
no counter type, so they count votes in a map or a short list, PHP does the same although array_count_values could tally them, Octave sums
the yes-or-no list that strcmp returns, C compares
labels with strcmp and counts them in a loop, BASIC, Pascal, and Ada do the same with a plain =, Fortran counts matching
labels with count, and APL compares every neighbor with every label at
once. awk and COBOL skip the square root and compare squared distances.
Watch how each finds the 5 nearest. Twenty-five of the twenty-nine sort all 150
distances for every test seed; awk, BASIC, COBOL, and Fortran pick the nearest
unused seed five times over. Fortran’s minloc returns the first of equal
distances, and BASIC’s strict < keeps the first it saw, which keeps the same order a stable sort would.
Watch tie-breaking too. On an exactly equal distance, all twenty-nine keep the
earlier training row. Python’s sorted, R’s order(), Rust’s sort_by, Java’s List.sort, Swift’s sorted(by:), Prolog’s keysort, Tcl’s lsort, PHP’s usort,
Perl’s, JavaScript’s, Julia’s, and Octave’s sort, Haskell’s sortOn, Elixir’s Enum.sort_by, and APL’s ⍋ are
stable. Go uses slices.SortStableFunc, because its plain SortFunc isn’t guaranteed to be, and C++, Common Lisp, and OCaml call std::stable_sort, stable-sort, and List.stable_sort for the same reason. Ruby’s sort_by, C’s qsort, Pascal’s TArrayHelper.Sort, Lua’s table.sort, and Ada’s Generic_Array_Sort
aren’t stable, so Ruby adds the file position to its sort key, and C’s, Pascal’s, Lua’s, and Ada’s
comparison functions break ties by row number. Perl’s and PHP’s comparisons do too, although their sorts are stable. But
floating point decides what counts as equal. The test seed at 6.06 × 3.21
has two training seeds exactly 0.13 mm away. COBOL’s decimal arithmetic sees
a tie; Python sees 0.1299999999999999 and 0.13000000000000037, so the two
come out in opposite orders. Both are among the five either way, which is
why the generator only guards the 5th/6th boundary.
Data preview
| length_mm | width_mm | variety | split |
|---|---|---|---|
| 5.50 | 3.11 | kama | train |
| 5.22 | 3.25 | kama | train |
| 5.94 | 3.82 | rosa | train |
| 6.04 | 3.40 | rosa | train |
| 5.53 | 3.16 | kama | train |
| 6.13 | 3.55 | rosa | train |
| 5.41 | 3.22 | kama | train |
| 5.54 | 3.37 | kama | train |
First 8 of 200 rows · Download data.csv
Expected results
Every implementation must print these, to within a relative tolerance of 10⁻⁴.
train_count | 150 |
test_count | 50 |
correct | 47 |
accuracy | 0.940000 |
Implementations
"""k-nearest neighbors classification, using only the standard library.
Each test seed is labelled with the majority variety among its K nearest
training seeds, by Euclidean distance.
"""
import csv
import math
import sys
from collections import Counter
K = 5
FEATURES = ("length_mm", "width_mm")
LABEL = "variety"
def read(path):
train, test = [], []
with open(path, newline="") as f:
for row in csv.DictReader(f):
point = (tuple(float(row[name]) for name in FEATURES), row[LABEL])
(train if row["split"] == "train" else test).append(point)
return train, test
def classify(point, train):
# Sort training seeds by distance (a stable sort, so equal distances keep
# file order) and let the K nearest vote.
nearest = sorted(train, key=lambda seed: math.dist(point, seed[0]))[:K]
votes = Counter(label for _, label in nearest)
return votes.most_common(1)[0][0]
def main():
train, test = read(sys.argv[1])
correct = sum(classify(point, train) == label for point, label in test)
print(f"train_count {len(train)}")
print(f"test_count {len(test)}")
print(f"correct {correct}")
print(f"accuracy {correct / len(test):.6f}")
if __name__ == "__main__":
main()Python is the baseline, and kNN fits in a few lines. csv.DictReader reads
the columns by header name, and the whole neighbor search is one expression:
sorted(train, key=lambda seed: math.dist(point, seed[0]))[:K]. Because
sorted is stable, seeds at an equal distance keep file order with no extra
work. collections.Counter counts the vote, and most_common(1) names the
winner.
It barely pushes back. Sorting all 150 seeds to keep 5 is more work than
needed; heapq.nsmallest would select just the five. The standard library
has no kNN classifier, so there was no built-in to skip. In real code you’d
reach for scikit-learn’s KNeighborsClassifier, a separate package that
isn’t installed in this image.
-- k-nearest neighbors classification, using only Ada's standard library.
--
-- Each test seed is labelled with the majority variety among its K nearest
-- training seeds, by Euclidean distance. There is no classifier to avoid;
-- sorting uses Generic_Array_Sort, and the votes are counted in a loop.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Long_Float_Text_IO; use Ada.Long_Float_Text_IO;
with Ada.Command_Line;
with Ada.Strings.Fixed; use Ada.Strings.Fixed;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Numerics.Long_Elementary_Functions;
use Ada.Numerics.Long_Elementary_Functions;
with Ada.Containers.Vectors;
with Ada.Containers.Generic_Array_Sort;
procedure Main is
K : constant := 5;
-- A record groups one seed's measurements with its variety. A plain
-- String has a fixed length, so the variety is an Unbounded_String.
type Seed is record
Length_Mm, Width_Mm : Long_Float;
Variety : Unbounded_String;
end record;
package Seed_Vectors is new Ada.Containers.Vectors (Positive, Seed);
use Seed_Vectors;
-- A training seed's distance from the test seed, and its row in Train.
type Neighbor is record
Distance : Long_Float;
Row : Positive;
end record;
type Neighbor_Array is array (Positive range <>) of Neighbor;
-- GNAT's Generic_Array_Sort is a heapsort, which doesn't keep equal
-- elements in order, so equal distances fall back to file order.
function Nearer (A, B : Neighbor) return Boolean is
(A.Distance < B.Distance
or else (A.Distance = B.Distance and then A.Row < B.Row));
procedure Sort is new Ada.Containers.Generic_Array_Sort
(Positive, Neighbor, Neighbor_Array, Nearer);
-- The text of field number Col (counting from 1) in a CSV line.
function Field (Line : String; Col : Positive) return String is
Start : Positive := Line'First;
begin
for I in 1 .. Col - 1 loop
Start := Index (Line (Start .. Line'Last), ",") + 1;
end loop;
declare
Stop : constant Natural := Index (Line (Start .. Line'Last), ",");
begin
return (if Stop = 0 then Line (Start .. Line'Last)
else Line (Start .. Stop - 1));
end;
end Field;
-- The number of the header field called Name.
function Column (Header, Name : String) return Positive is
begin
for C in 1 .. Ada.Strings.Fixed.Count (Header, ",") + 1 loop
if Field (Header, C) = Name then
return C;
end if;
end loop;
raise Constraint_Error with "column not found: " & Name;
end Column;
function Classify (Point : Seed; Train : Vector) return Unbounded_String is
Neighbors : Neighbor_Array (1 .. Natural (Train.Length));
Best : Unbounded_String;
Best_Votes : Natural := 0;
begin
for I in Neighbors'Range loop
Neighbors (I) :=
(Distance => Sqrt ((Point.Length_Mm - Train (I).Length_Mm) ** 2 +
(Point.Width_Mm - Train (I).Width_Mm) ** 2),
Row => I);
end loop;
Sort (Neighbors);
-- Count each of the K nearest labels' votes among the K; the first
-- label to reach the highest count wins.
for I in 1 .. K loop
declare
Label : constant Unbounded_String :=
Train (Neighbors (I).Row).Variety;
Votes : Natural := 0;
begin
for J in 1 .. K loop
if Train (Neighbors (J).Row).Variety = Label then
Votes := Votes + 1;
end if;
end loop;
if Votes > Best_Votes then
Best := Label;
Best_Votes := Votes;
end if;
end;
end loop;
return Best;
end Classify;
File : File_Type;
Train, Test : Vector;
Correct : Natural := 0;
begin
Open (File, In_File, Ada.Command_Line.Argument (1));
declare
Header : constant String := Get_Line (File);
Length_C : constant Positive := Column (Header, "length_mm");
Width_C : constant Positive := Column (Header, "width_mm");
Variety_C : constant Positive := Column (Header, "variety");
Split_C : constant Positive := Column (Header, "split");
begin
while not End_Of_File (File) loop
declare
Line : constant String := Get_Line (File);
S : constant Seed :=
(Length_Mm => Long_Float'Value (Field (Line, Length_C)),
Width_Mm => Long_Float'Value (Field (Line, Width_C)),
Variety => To_Unbounded_String (Field (Line, Variety_C)));
begin
if Field (Line, Split_C) = "train" then
Train.Append (S);
else
Test.Append (S);
end if;
end;
end loop;
end;
Close (File);
for S of Test loop
if Classify (S, Train) = S.Variety then
Correct := Correct + 1;
end if;
end loop;
Put_Line ("train_count" & Train.Length'Image);
Put_Line ("test_count" & Test.Length'Image);
Put_Line ("correct" & Correct'Image);
Put ("accuracy ");
Put (Long_Float (Correct) / Long_Float (Test.Length),
Fore => 1, Aft => 6, Exp => 0);
New_Line;
end Main;Ada has no kNN classifier and no counter type, so we count votes the way
C and Pascal do: for each of the five nearest labels, a loop counts how
many of the five share it, and the first label to reach the top count
wins. Each variety is an Unbounded_String, since a plain String has a
fixed length, and = compares the text.
For each test seed we fill an array of distance-and-row records and sort
all 150 with Generic_Array_Sort. GNAT implements it as a heapsort, which
doesn’t keep equal elements in order, so our Nearer comparison breaks
distance ties by row number.
⍝ k-nearest neighbors classification, from scratch in GNU APL.
⍝ Each test seed gets the majority variety among its K nearest training
⍝ seeds. APL reads right to left, with no operator precedence: 2×3+4 is
⍝ 2×(3+4). ⍝ starts a comment; ← assigns; ⍵ is a function's right argument.
∇NAME SAY N
⍝ Print "name value" for a whole number. ⍕ formats a number as text.
⎕←NAME,' ',⍕N
∇
∇NAME SAY6 X;T
⍝ Print "name value" with six decimal places.
T←0 6⍕|X ⍝ |X is the size of X; 0 6⍕ gives 6 decimals
T←(∨\T≠' ')/T ⍝ drop the leading blank ⍕ adds
T←((T[1]='.')/'0'),T ⍝ ⍕ writes .94 for 0.94, so put the 0 back
⎕←NAME,' ',((X<0)/'-'),T ⍝ sign as -, since APL's own minus is ¯
∇
K←5
⍝ Read the file. ⎕ARG is the command line; ↑¯1↑ takes its last item, the
⍝ data path. ⎕FIO[26] reads the whole file as one string.
TEXT←⎕FIO[26]↑¯1↑⎕ARG
LINES←(TEXT≠⎕UCS 10)⊂TEXT ⍝ ⊂ splits at the 0s of the mask: one item per line
⍝ Split each (¨) line at commas; ⊃ stacks them into a table.
ROWS←⊃{(⍵≠',')⊂⍵}¨LINES
⍝ A column by header name (⍳), minus the header (1↓).
COLUMN←{1↓ROWS[;ROWS[1;]⍳⊂⍵]}
⍝ 2-row table of numbers (⍎ turns text to number).
XY←⍎¨⊃COLUMN¨'length_mm' 'width_mm'
LABEL←COLUMN 'variety'
⍝ 1 for each training row (≡ matches whole strings).
TRAIN←(COLUMN 'split')≡¨⊂'train'
⍝ / keeps the training columns; ⍉ flips to one row per seed.
TP←⍉TRAIN/XY ⋄ TL←TRAIN/LABEL
QP←⍉(~TRAIN)/XY ⋄ QL←(~TRAIN)/LABEL ⍝ ~ is not: the test rows
∇WINNER←CLASSIFY P;D;NEAR;KINDS;VOTES
⍝ Distance to every training seed: (⍴TP)⍴P repeats P per row.
D←(+/(TP-(⍴TP)⍴P)*2)*0.5
⍝ ⍋ sorts stably, so equal distances keep file order.
NEAR←TL[K↑⍋D]
KINDS←∪NEAR ⍝ ∪ is unique, in order of first appearance
⍝ ∘.≡ compares every kind with every neighbor; +/ counts.
VOTES←+/KINDS∘.≡NEAR
⍝ The first kind with the most votes (⌈/ is the max).
WINNER←⊃KINDS[VOTES⍳⌈/VOTES]
∇
⍝ ⊂[2] makes one item per row, so ¨ classifies each test seed.
PRED←CLASSIFY¨⊂[2]QP
CORRECT←+/PRED≡¨QL
'train_count' SAY ≢TL
'test_count' SAY ≢QL
'correct' SAY CORRECT
'accuracy' SAY6 CORRECT÷≢QL
)OFFThe distance to all 150 training seeds is one line: (⍴TP)⍴P repeats the
test point once per row, so subtracting, squaring, and summing each row
(+/) gives every distance at once. K↑⍋D takes the first five indices of
the sorted order. ⍋ is stable, which we checked on 10,000 values with
many ties, so equal distances keep file order.
The vote is array style too. ∪ lists the varieties in order of first
appearance, ∘.≡ compares each one with every neighbor, and +/ counts
the matches. ⍳ finds the first position of the top count. There is no
nearest-neighbor built-in to avoid.
# k-nearest neighbors classification, in POSIX awk.
#
# Each test seed is labelled with the majority variety among its K nearest
# training seeds, by Euclidean distance. Rows are stored as they are read;
# the classifying happens in END.
BEGIN { FS = ","; K = 5 }
# The header line: find each column by name.
NR == 1 {
for (i = 1; i <= NF; i++) {
if ($i == "length_mm") c_len = i
if ($i == "width_mm") c_wid = i
if ($i == "variety") c_lab = i
if ($i == "split") c_split = i
}
if (!c_len || !c_wid || !c_lab || !c_split) {
print "missing a column (length_mm, width_mm, variety, split)" > "/dev/stderr"
failed = 1
exit 1
}
next
}
# Every other line goes into the training or the test arrays.
$c_split == "train" {
n_train++
tx[n_train] = $c_len + 0; ty[n_train] = $c_wid + 0; tlab[n_train] = $c_lab
next
}
$c_split == "test" {
n_test++
qx[n_test] = $c_len + 0; qy[n_test] = $c_wid + 0; qlab[n_test] = $c_lab
}
# Label the point (px, py) by a vote of its K nearest training seeds.
# Locals are declared as extra parameters, the awk idiom for local variables.
function classify(px, py, i, j, best, dist, used, votes, label, winner) {
# Squared distance is enough for ranking, and skips the square root.
for (i = 1; i <= n_train; i++)
dist[i] = (tx[i] - px) ^ 2 + (ty[i] - py) ^ 2
# Repeated selection: pick the nearest unused seed K times. The strict
# "<" keeps the earlier training row on equal distances.
winner = ""
for (j = 1; j <= K; j++) {
best = 0
for (i = 1; i <= n_train; i++)
if (!(i in used) && (best == 0 || dist[i] < dist[best]))
best = i
used[best] = 1
label = tlab[best]
votes[label]++
# Highest vote wins; a tie stays with the label seen first (nearest).
if (winner == "" || votes[label] > votes[winner])
winner = label
}
return winner
}
END {
if (failed) exit 1
for (t = 1; t <= n_test; t++)
if (classify(qx[t], qy[t]) == qlab[t]) correct++
printf "train_count %d\n", n_train
printf "test_count %d\n", n_test
printf "correct %d\n", correct
printf "accuracy %.6f\n", correct / n_test
}awk handles the reading well. A pattern like $c_split == "train" sends
each line to the right arrays, and associative arrays make each vote a
single votes[label]++. The program compares squared distances, which rank
neighbors the same way and skip the square root.
The search is where awk pushes back. POSIX awk has no sort function (mawk
answers asort with “function asort never defined”), so classify picks
the nearest unused seed five times over, marking picks in used. That’s
five scans of all 150 training seeds per test seed. There are no records
either, so each seed lives in parallel arrays, tx, ty, and tlab, and
locals are declared as extra function parameters. In exchange it
runs unchanged on mawk and on the awk that ships with macOS.
10 REM k-nearest neighbors classification, in classic BASIC.
20 REM
30 REM Each test seed gets the majority variety among its K nearest
40 REM training seeds, by Euclidean distance. There is no sort, so we pick
50 REM the nearest unused training seed K times over.
60 REM
70 REM run.sh passes the data path in the DATA environment variable,
80 REM because bwbasic can't read command-line arguments.
100 K = 5
110 DIM TL(500), TW(500), TV$(500) : REM training seeds: length, width, variety
120 DIM QL(500), QW(500), QV$(500) : REM test seeds
130 DIM D(500), U(500), NB(10), FL$(20)
140 GOSUB 1000 : REM read the seeds into the two sets
150 C = 0
160 FOR T = 1 TO NQ
170 GOSUB 2000 : REM find the K nearest training seeds, NB(1..K)
180 GOSUB 3000 : REM vote, leaving the winning variety in P$
190 IF P$ = QV$(T) THEN C = C + 1
200 NEXT T
210 PRINT "train_count"; NT
220 PRINT "test_count"; NQ
230 PRINT "correct"; C
240 PRINT "accuracy ";
250 PRINT USING "#.######"; C / NQ
260 SYSTEM : REM without SYSTEM, bwbasic waits at its prompt
1000 REM Read each row into the training set or the test set by its split.
1010 F$ = ENVIRON$("DATA")
1020 OPEN "I", #1, F$
1030 LINE INPUT #1, L$
1040 GOSUB 4000 : REM find which field of the header holds each column
1050 FOR J = 1 TO NF
1060 IF FL$(J) = "length_mm" THEN CL = J
1070 IF FL$(J) = "width_mm" THEN CW = J
1080 IF FL$(J) = "variety" THEN CV = J
1090 IF FL$(J) = "split" THEN CS = J
1100 NEXT J
1110 NT = 0 : NQ = 0
1120 IF EOF(1) THEN 1190
1130 LINE INPUT #1, L$
1140 GOSUB 4000
1150 IF FL$(CS) = "train" THEN GOSUB 1300 ELSE GOSUB 1400
1160 GOTO 1120
1190 CLOSE #1
1200 RETURN
1300 REM Add the row just split to the training set.
1310 NT = NT + 1 : TL(NT) = VAL(FL$(CL)) : TW(NT) = VAL(FL$(CW)) : TV$(NT) = FL$(CV)
1320 RETURN
1400 REM Add the row just split to the test set.
1410 NQ = NQ + 1 : QL(NQ) = VAL(FL$(CL)) : QW(NQ) = VAL(FL$(CW)) : QV$(NQ) = FL$(CV)
1420 RETURN
2000 REM Distances from test seed T, then pick the nearest unused seed K times.
2010 FOR J = 1 TO NT
2020 D(J) = SQR((QL(T) - TL(J)) ^ 2 + (QW(T) - TW(J)) ^ 2) : U(J) = 0
2030 NEXT J
2040 FOR M = 1 TO K
2050 B = 0 : BD = 1E+30 : REM BD starts larger than any distance
2060 FOR J = 1 TO NT
2070 REM A strict < keeps the earlier row when two distances are equal.
2080 IF U(J) = 0 AND D(J) < BD THEN B = J : BD = D(J)
2090 NEXT J
2100 NB(M) = B : U(B) = 1
2110 NEXT M
2120 RETURN
3000 REM Count each neighbor's votes; the first to reach the most votes wins.
3010 BV = 0
3020 FOR M = 1 TO K
3030 V = 0
3040 FOR J = 1 TO K
3050 IF TV$(NB(J)) = TV$(NB(M)) THEN V = V + 1
3060 NEXT J
3070 IF V > BV THEN BV = V : P$ = TV$(NB(M))
3080 NEXT M
3090 RETURN
4000 REM Split L$ at its commas into FL$(1) to FL$(NF).
4010 NF = 0 : P = 1
4020 Q = INSTR(P, L$, ",")
4030 NF = NF + 1
4040 IF Q = 0 THEN FL$(NF) = MID$(L$, P) : RETURN
4050 FL$(NF) = MID$(L$, P, Q - P) : P = Q + 1
4060 GOTO 4020BASIC has no sort, record type, or dictionary, so we keep each seed’s
length, width, and variety in three parallel arrays, one set for training
and one for testing. A row goes to the training or test set through
IF ... THEN GOSUB 1300 ELSE GOSUB 1400.
For each test seed we store all 150 distances, then pick the nearest unused
training seed five times over, marking each pick in U. The search starts
from BD = 1E+30 and uses a strict <, so on an exact tie the earlier
row wins. The vote counts how many of the five share each neighbor’s
variety, comparing strings with a plain =, and the first to reach the
most votes wins.
/* k-nearest neighbors classification, using only the C standard library.
*
* Each test seed is labelled with the majority variety among its K nearest
* training seeds, by Euclidean distance. */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define K 5
#define MAX_LINE 1024
#define MAX_FIELDS 16
#define MAX_LABEL 16
/* A struct groups one seed's measurements with its variety. */
struct seed {
double length, width;
char variety[MAX_LABEL];
};
/* A growable array of seeds: realloc doubles its room whenever it fills. */
struct seeds {
struct seed *items;
size_t count, capacity;
};
static void push(struct seeds *list, struct seed s) {
if (list->count == list->capacity) {
list->capacity = list->capacity ? list->capacity * 2 : 64;
list->items = realloc(list->items, list->capacity * sizeof *list->items);
}
list->items[list->count++] = s;
}
/* Cut a line at its commas, in place, and return the number of fields.
* strtok replaces each comma with '\0', so fields[i] points into line. */
static int split(char *line, char *fields[]) {
int n = 0;
for (char *f = strtok(line, ",\r\n"); f && n < MAX_FIELDS; f = strtok(NULL, ",\r\n"))
fields[n++] = f;
return n;
}
/* Return the 0-based position of name among the header fields, or exit. */
static int column(char *header[], int n, const char *name) {
for (int i = 0; i < n; i++)
if (strcmp(header[i], name) == 0) return i;
fprintf(stderr, "no column %s\n", name);
exit(1);
}
static void read_seeds(const char *path, struct seeds *train, struct seeds *test) {
FILE *file = fopen(path, "r");
if (!file) { perror(path); exit(1); }
char line[MAX_LINE], *fields[MAX_FIELDS];
if (!fgets(line, sizeof line, file)) { fprintf(stderr, "empty file\n"); exit(1); }
int n = split(line, fields);
int length = column(fields, n, "length_mm"), width = column(fields, n, "width_mm");
int variety = column(fields, n, "variety"), which = column(fields, n, "split");
while (fgets(line, sizeof line, file)) {
if (split(line, fields) != n) continue;
struct seed s = { strtod(fields[length], NULL), strtod(fields[width], NULL), "" };
/* snprintf copies the label and always ends it with '\0'. */
snprintf(s.variety, sizeof s.variety, "%s", fields[variety]);
push(strcmp(fields[which], "train") == 0 ? train : test, s);
}
fclose(file);
}
/* A training seed's distance from the test seed, and its row in the file. */
struct neighbor {
double distance;
size_t index;
};
/* qsort isn't stable, so equal distances fall back to file order. */
static int compare_neighbors(const void *a, const void *b) {
const struct neighbor *x = a, *y = b;
if (x->distance != y->distance) return (x->distance > y->distance) - (x->distance < y->distance);
return (x->index > y->index) - (x->index < y->index);
}
static const char *classify(const struct seed *point, const struct seeds *train,
struct neighbor *scratch) {
for (size_t i = 0; i < train->count; i++) {
double dl = point->length - train->items[i].length;
double dw = point->width - train->items[i].width;
scratch[i] = (struct neighbor){ sqrt(dl * dl + dw * dw), i };
}
qsort(scratch, train->count, sizeof *scratch, compare_neighbors);
/* Count each of the K nearest labels' votes among the K; the first
* label to reach the highest count wins. */
const char *best = NULL;
int best_votes = 0;
for (int i = 0; i < K; i++) {
const char *label = train->items[scratch[i].index].variety;
int votes = 0;
for (int j = 0; j < K; j++)
if (strcmp(train->items[scratch[j].index].variety, label) == 0) votes++;
if (votes > best_votes) { best = label; best_votes = votes; }
}
return best;
}
int main(int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: %s data.csv\n", argv[0]); return 1; }
struct seeds train = {0}, test = {0};
read_seeds(argv[1], &train, &test);
if (train.count < K || test.count == 0) { fprintf(stderr, "too few seeds\n"); return 1; }
struct neighbor *scratch = malloc(train.count * sizeof *scratch);
int correct = 0;
for (size_t i = 0; i < test.count; i++)
if (strcmp(classify(&test.items[i], &train, scratch), test.items[i].variety) == 0)
correct++;
printf("train_count %zu\n", train.count);
printf("test_count %zu\n", test.count);
printf("correct %d\n", correct);
printf("accuracy %.6f\n", (double)correct / test.count);
free(scratch);
free(train.items);
free(test.items);
return 0;
}C has no kNN classifier, hash table, or counter type, so we build the
pieces. A struct seed holds a seed’s length, width, and variety, with the
variety copied into a fixed 16-character array, and the training and test
sets are arrays that grow with realloc.
For each test seed we fill a scratch array with every training seed’s
distance and row number, then sort it with qsort. The C standard leaves
the order of equal elements unspecified, so the comparison function breaks
distance ties by row number, keeping file order. The vote compares labels
with strcmp, since == on two strings only compares their addresses.
// k-nearest neighbors classification, using only the C++ standard library.
//
// Each test seed is labelled with the majority variety among its K nearest
// training seeds, by Euclidean distance.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <fstream>
#include <map>
#include <print>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
constexpr std::size_t K = 5;
// A struct groups one seed's measurements with its variety.
struct Seed {
double length;
double width;
std::string variety;
};
// Split one line at every comma.
std::vector<std::string> split(const std::string& line) {
std::vector<std::string> fields;
std::stringstream stream(line);
std::string field;
while (std::getline(stream, field, ',')) {
fields.push_back(field);
}
return fields;
}
// Read every seed into the training or the test set, by its split column.
void read_seeds(const std::string& path, std::vector<Seed>& train, std::vector<Seed>& test) {
std::ifstream file(path);
std::string line;
std::getline(file, line);
std::vector<std::string> header = split(line);
// A lambda that finds a column's position, or throws.
auto column = [&header](const std::string& name) {
auto found = std::find(header.begin(), header.end(), name);
if (found == header.end()) {
throw std::runtime_error("no column " + name);
}
return static_cast<std::size_t>(found - header.begin());
};
std::size_t length = column("length_mm"), width = column("width_mm");
std::size_t variety = column("variety"), which = column("split");
while (std::getline(file, line)) {
if (line.empty()) {
continue;
}
std::vector<std::string> fields = split(line);
Seed seed{std::stod(fields.at(length)), std::stod(fields.at(width)), fields.at(variety)};
(fields.at(which) == "train" ? train : test).push_back(seed);
}
}
std::string classify(const Seed& point, const std::vector<Seed>& train) {
// Pointers to the training seeds, so sorting doesn't copy the labels.
std::vector<const Seed*> nearest;
for (const Seed& seed : train) {
nearest.push_back(&seed);
}
auto distance = [&point](const Seed* seed) {
return std::hypot(point.length - seed->length, point.width - seed->width);
};
// std::sort isn't stable; stable_sort keeps equal distances in file order.
std::ranges::stable_sort(nearest, [&](const Seed* a, const Seed* b) {
return distance(a) < distance(b);
});
// Count the K nearest labels' votes. A std::map starts each new key at 0.
std::map<std::string, int> votes;
for (std::size_t i = 0; i < K; i++) {
votes[nearest[i]->variety]++;
}
// The map keeps its keys in alphabetical order, so walk the nearest
// seeds instead: the first label to reach the highest count wins.
std::string best;
int best_votes = 0;
for (std::size_t i = 0; i < K; i++) {
const std::string& label = nearest[i]->variety;
if (votes[label] > best_votes) {
best = label;
best_votes = votes[label];
}
}
return best;
}
int main(int argc, char* argv[]) {
if (argc != 2) {
std::println(stderr, "usage: program data.csv");
return 1;
}
std::vector<Seed> train, test;
read_seeds(argv[1], train, test);
if (train.size() < K || test.empty()) {
throw std::runtime_error("too few seeds");
}
// count_if counts the test seeds whose predicted variety is right.
auto correct = std::ranges::count_if(test, [&train](const Seed& seed) {
return classify(seed, train) == seed.variety;
});
std::println("train_count {}", train.size());
std::println("test_count {}", test.size());
std::println("correct {}", correct);
std::println("accuracy {:.6f}", static_cast<double>(correct) / test.size());
}C++ has no kNN classifier, so we build one from a struct Seed, two
std::vectors, and a std::map. Unlike C, the variety is a std::string,
so == compares the labels themselves, with no strcmp.
For each test seed we sort pointers to all 150 training seeds by
std::hypot distance. std::sort isn’t stable, so we use
std::stable_sort, which keeps equal distances in file order. On this data
plain std::sort reorders the five nearest for 4 of the 50 test seeds but
still gets 47 right. The std::map counts votes, but it keeps its keys
alphabetical, so we walk the nearest five again and the first label to reach
the top count wins.
*> k-nearest neighbors classification, in COBOL.
*>
*> Each test seed is labelled with the majority variety among its
*> K = 5 nearest training seeds. Squared Euclidean distance ranks
*> the neighbors in the same order as distance, without a SQRT.
IDENTIFICATION DIVISION.
PROGRAM-ID. K-NEAREST-NEIGHBORS.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT DATA-FILE ASSIGN TO DYNAMIC WS-FILE-NAME
ORGANIZATION IS LINE SEQUENTIAL.
DATA DIVISION.
FILE SECTION.
FD DATA-FILE.
01 DATA-LINE PIC X(200).
WORKING-STORAGE SECTION.
01 WS-FILE-NAME PIC X(256).
01 WS-K PIC 9 VALUE 5.
01 WS-EOF PIC X VALUE "N".
88 END-OF-FILE VALUE "Y".
*> One CSV line split into fields, and where the columns are.
01 WS-FIELDS.
05 WS-FIELD PIC X(40) OCCURS 20 TIMES.
01 WS-FIELD-COUNT PIC 99.
01 WS-POINTER PIC 999.
01 WS-LINE-LENGTH PIC 999.
01 WS-COLUMNS.
05 WS-LENGTH-COLUMN PIC 99 VALUE 0.
05 WS-WIDTH-COLUMN PIC 99 VALUE 0.
05 WS-LABEL-COLUMN PIC 99 VALUE 0.
05 WS-SPLIT-COLUMN PIC 99 VALUE 0.
*> Training and test seeds: two features and a label each.
01 WS-TRAIN-COUNT PIC 9(4) VALUE 0.
01 WS-TRAIN.
05 WS-TRAIN-SEED OCCURS 5000 TIMES.
10 WS-TRAIN-X1 PIC S9(9)V9(6).
10 WS-TRAIN-X2 PIC S9(9)V9(6).
10 WS-TRAIN-LABEL PIC X(40).
*> Squared distance to the current test seed, and whether
*> this seed has already been picked as a neighbor.
10 WS-DIST PIC S9(12)V9(12).
10 WS-USED PIC X.
01 WS-TEST-COUNT PIC 9(4) VALUE 0.
01 WS-TEST.
05 WS-TEST-SEED OCCURS 5000 TIMES.
10 WS-TEST-X1 PIC S9(9)V9(6).
10 WS-TEST-X2 PIC S9(9)V9(6).
10 WS-TEST-LABEL PIC X(40).
*> The votes of the K nearest, one entry per distinct label.
01 WS-VOTE-COUNT PIC 9.
01 WS-VOTES.
05 WS-VOTE OCCURS 5 TIMES.
10 WS-VOTE-LABEL PIC X(40).
10 WS-VOTE-TALLY PIC 9.
01 I PIC 9(4).
01 T PIC 9(4).
01 N PIC 9.
01 V PIC 9.
01 WS-BEST PIC 9(4).
01 WS-PREDICTED PIC X(40).
01 WS-CORRECT PIC 9(4) VALUE 0.
01 WS-ACCURACY PIC S9(3)V9(12).
01 WS-ACCURACY-OUT PIC -(3)9.9(6).
01 WS-COUNT-OUT PIC Z(8)9.
PROCEDURE DIVISION.
MAIN.
ACCEPT WS-FILE-NAME FROM ARGUMENT-VALUE
OPEN INPUT DATA-FILE
READ DATA-FILE
AT END SET END-OF-FILE TO TRUE
END-READ
PERFORM SPLIT-LINE
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-FIELD-COUNT
EVALUATE WS-FIELD(I)
WHEN "length_mm" MOVE I TO WS-LENGTH-COLUMN
WHEN "width_mm" MOVE I TO WS-WIDTH-COLUMN
WHEN "variety" MOVE I TO WS-LABEL-COLUMN
WHEN "split" MOVE I TO WS-SPLIT-COLUMN
END-EVALUATE
END-PERFORM
IF WS-LENGTH-COLUMN = 0 OR WS-WIDTH-COLUMN = 0
OR WS-LABEL-COLUMN = 0 OR WS-SPLIT-COLUMN = 0
DISPLAY "missing column" UPON SYSERR
MOVE 1 TO RETURN-CODE
STOP RUN
END-IF
PERFORM UNTIL END-OF-FILE
READ DATA-FILE
AT END SET END-OF-FILE TO TRUE
NOT AT END PERFORM ADD-SEED
END-READ
END-PERFORM
CLOSE DATA-FILE
PERFORM VARYING T FROM 1 BY 1 UNTIL T > WS-TEST-COUNT
PERFORM CLASSIFY
IF WS-PREDICTED = WS-TEST-LABEL(T)
ADD 1 TO WS-CORRECT
END-IF
END-PERFORM
MOVE WS-TRAIN-COUNT TO WS-COUNT-OUT
DISPLAY "train_count " FUNCTION TRIM(WS-COUNT-OUT)
MOVE WS-TEST-COUNT TO WS-COUNT-OUT
DISPLAY "test_count " FUNCTION TRIM(WS-COUNT-OUT)
MOVE WS-CORRECT TO WS-COUNT-OUT
DISPLAY "correct " FUNCTION TRIM(WS-COUNT-OUT)
COMPUTE WS-ACCURACY ROUNDED = WS-CORRECT / WS-TEST-COUNT
COMPUTE WS-ACCURACY-OUT ROUNDED = WS-ACCURACY
DISPLAY "accuracy " FUNCTION TRIM(WS-ACCURACY-OUT)
STOP RUN.
*> Split DATA-LINE on commas into WS-FIELD(1), WS-FIELD(2), ...
SPLIT-LINE.
MOVE SPACES TO WS-FIELDS
MOVE 0 TO WS-FIELD-COUNT
MOVE 1 TO WS-POINTER
MOVE FUNCTION LENGTH(FUNCTION TRIM(DATA-LINE TRAILING))
TO WS-LINE-LENGTH
PERFORM UNTIL WS-POINTER > WS-LINE-LENGTH
ADD 1 TO WS-FIELD-COUNT
UNSTRING DATA-LINE DELIMITED BY ","
INTO WS-FIELD(WS-FIELD-COUNT)
WITH POINTER WS-POINTER
END-UNSTRING
END-PERFORM.
*> Store one data line as a training or a test seed.
ADD-SEED.
PERFORM SPLIT-LINE
IF WS-FIELD(WS-SPLIT-COLUMN) = "train"
ADD 1 TO WS-TRAIN-COUNT
COMPUTE WS-TRAIN-X1(WS-TRAIN-COUNT) =
FUNCTION NUMVAL(WS-FIELD(WS-LENGTH-COLUMN))
COMPUTE WS-TRAIN-X2(WS-TRAIN-COUNT) =
FUNCTION NUMVAL(WS-FIELD(WS-WIDTH-COLUMN))
MOVE WS-FIELD(WS-LABEL-COLUMN)
TO WS-TRAIN-LABEL(WS-TRAIN-COUNT)
ELSE
ADD 1 TO WS-TEST-COUNT
COMPUTE WS-TEST-X1(WS-TEST-COUNT) =
FUNCTION NUMVAL(WS-FIELD(WS-LENGTH-COLUMN))
COMPUTE WS-TEST-X2(WS-TEST-COUNT) =
FUNCTION NUMVAL(WS-FIELD(WS-WIDTH-COLUMN))
MOVE WS-FIELD(WS-LABEL-COLUMN)
TO WS-TEST-LABEL(WS-TEST-COUNT)
END-IF.
*> Label test seed T by majority vote of its K nearest seeds.
CLASSIFY.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-TRAIN-COUNT
COMPUTE WS-DIST(I) =
(WS-TEST-X1(T) - WS-TRAIN-X1(I)) ** 2
+ (WS-TEST-X2(T) - WS-TRAIN-X2(I)) ** 2
MOVE "N" TO WS-USED(I)
END-PERFORM
*> Pick the nearest unused seed K times. A strict "<" keeps the
*> earlier training seed when two distances are equal.
MOVE 0 TO WS-VOTE-COUNT
PERFORM VARYING N FROM 1 BY 1 UNTIL N > WS-K
MOVE 0 TO WS-BEST
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-TRAIN-COUNT
IF WS-USED(I) = "N"
IF WS-BEST = 0
MOVE I TO WS-BEST
ELSE
IF WS-DIST(I) < WS-DIST(WS-BEST)
MOVE I TO WS-BEST
END-IF
END-IF
END-IF
END-PERFORM
MOVE "Y" TO WS-USED(WS-BEST)
PERFORM ADD-VOTE
END-PERFORM
*> Labels are in the order first seen among the nearest, so a
*> strict ">" gives a tied vote to the label met first.
MOVE 1 TO V
PERFORM VARYING N FROM 2 BY 1 UNTIL N > WS-VOTE-COUNT
IF WS-VOTE-TALLY(N) > WS-VOTE-TALLY(V)
MOVE N TO V
END-IF
END-PERFORM
MOVE WS-VOTE-LABEL(V) TO WS-PREDICTED.
*> Count one vote for the label of training seed WS-BEST.
ADD-VOTE.
MOVE 0 TO V
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-VOTE-COUNT
IF WS-VOTE-LABEL(I) = WS-TRAIN-LABEL(WS-BEST)
MOVE I TO V
END-IF
END-PERFORM
IF V = 0
ADD 1 TO WS-VOTE-COUNT
MOVE WS-VOTE-COUNT TO V
MOVE WS-TRAIN-LABEL(WS-BEST) TO WS-VOTE-LABEL(V)
MOVE 0 TO WS-VOTE-TALLY(V)
END-IF
ADD 1 TO WS-VOTE-TALLY(V).COBOL gets the distances exactly right. Each feature is a fixed-point
decimal, PIC S9(9)V9(6), and squared distances go into PIC S9(12)V9(12), so with two-decimal data nothing rounds. An exact tie really
compares equal. The two training seeds 0.13 mm from the test seed at 6.06 ×
3.21 both have a squared distance of exactly 0.0169, where floating point
produces two slightly different numbers.
Everything else is by hand. With no sort-by-key or counter, CLASSIFY runs
five selection scans over WS-DIST with a strict <, marking picks in
WS-USED, and ADD-VOTE keeps a small table of labels and tallies. Tables
are fixed in size (OCCURS 5000 TIMES), and at 214 lines the program is
nearly five times as long as the 45-line Python. There is no kNN built-in to
skip.
;;;; k-nearest neighbors classification, using only standard Common Lisp.
;;;;
;;;; Each test seed is labelled with the majority variety among its K
;;;; nearest training seeds, by Euclidean distance. Common Lisp has no kNN,
;;;; no distance function, and no CSV reader, so we write those; sqrt,
;;;; stable-sort, and count are built in.
(defparameter *k* 5)
;; By default the reader turns 5.50 into a single float, which keeps only
;; about 7 digits. Read doubles.
;; eval-when makes the setting apply while the compiler reads this file, too,
;; not only once the program runs.
(eval-when (:compile-toplevel :load-toplevel :execute)
(setf *read-default-float-format* 'double-float))
;; defstruct defines a record type with a constructor, make-seed, and one
;; reader per slot: seed-length, seed-width, seed-variety, seed-split.
(defstruct seed length width variety split)
(defun split-on-comma (line)
"The fields of LINE, split at every comma."
(loop for start = 0 then (1+ end)
for end = (position #\, line :start start)
collect (subseq line start end)
while end))
(defun parse-number (text)
"The number written in TEXT, read by the Lisp reader. Binding *read-eval*
to nil stops the reader from running code written as #.(...)."
(let ((*read-eval* nil))
(coerce (read-from-string text) 'double-float)))
(defun read-seeds (path)
"The rows of the CSV file at PATH, as a list of seeds in file order."
(with-open-file (in path)
(let ((header (split-on-comma (read-line in))))
;; Each field's position in the header, looked up by name.
(flet ((column (name)
(or (position name header :test #'string=)
(error "no column ~a" name))))
(let ((length-at (column "length_mm"))
(width-at (column "width_mm"))
(variety-at (column "variety"))
(split-at (column "split")))
(loop for line = (read-line in nil)
while line
unless (string= line "")
collect (let ((fields (split-on-comma line)))
(make-seed
:length (parse-number (nth length-at fields))
:width (parse-number (nth width-at fields))
:variety (nth variety-at fields)
:split (nth split-at fields)))))))))
(defun distance (a b)
"The Euclidean distance between seeds A and B."
(sqrt (+ (expt (- (seed-length a) (seed-length b)) 2)
(expt (- (seed-width a) (seed-width b)) 2))))
(defun classify (point train)
"The majority variety among the K training seeds nearest POINT."
;; stable-sort keeps equal distances in file order; plain sort may not.
;; It may take its argument apart, so we sort a fresh copy of TRAIN.
(let* ((nearest (subseq (stable-sort (copy-list train) #'<
:key (lambda (s) (distance point s)))
0 *k*))
(votes (mapcar #'seed-variety nearest))
(best nil)
(best-count 0))
;; Count each variety's votes, in the order the neighbors came. Only a
;; strictly larger count replaces the leader, so the first wins a tie.
(dolist (variety (remove-duplicates votes :test #'string= :from-end t)
best)
(let ((n (count variety votes :test #'string=)))
(when (> n best-count)
(setf best variety
best-count n))))))
;; With --script, the data path is the second item of *posix-argv*.
(let* ((seeds (read-seeds (second sb-ext:*posix-argv*)))
(train (remove-if-not (lambda (s) (string= (seed-split s) "train")) seeds))
(test (remove-if-not (lambda (s) (string= (seed-split s) "test")) seeds))
(correct (count-if (lambda (s)
(string= (classify s train) (seed-variety s)))
test)))
;; ~d prints an integer, ~,6f a number with six decimals, ~% a newline.
(format t "train_count ~d~%" (length train))
(format t "test_count ~d~%" (length test))
(format t "correct ~d~%" correct)
;; (/ 47 50) would be the exact fraction 47/50; dividing by a double
;; gives a double.
(format t "accuracy ~,6f~%" (/ correct (float (length test) 1d0))))Each row becomes a seed struct, and defstruct writes the readers, such
as seed-length, for us. To find the 5 nearest, we stable-sort a copy of
all 150 training seeds, keyed on distance, and keep the first 5 with
subseq. Only stable-sort is guaranteed to keep equal distances in file
order; in our test, SBCL’s plain sort reordered ties in a vector.
For the vote, remove-duplicates with :from-end t lists each variety in
the order the neighbors came, count tallies it, and only a strictly larger
count takes the lead. No kNN or distance function is called.
# k-nearest neighbors classification, using only Elixir's standard library.
#
# Each test seed is labelled with the majority variety among its k nearest
# training seeds, by Euclidean distance.
defmodule Knn do
@k 5
# Every row as a map, keyed by the header's column names.
def read_rows(path) do
[header | rows] =
path
|> File.read!()
|> String.split("\n", trim: true)
|> Enum.map(&String.split(&1, ","))
Enum.map(rows, fn fields -> header |> Enum.zip(fields) |> Map.new() end)
end
# A seed is {{length, width}, variety}.
def seed(row) do
{length, ""} = Float.parse(row["length_mm"])
{width, ""} = Float.parse(row["width_mm"])
{{length, width}, row["variety"]}
end
def distance({l1, w1}, {l2, w2}), do: :math.sqrt((l1 - l2) ** 2 + (w1 - w2) ** 2)
# Sort the training seeds by distance and keep the first k. Enum.sort_by
# is a stable merge sort, so seeds at exactly equal distances stay in
# file order.
def nearest(train, point) do
train
|> Enum.sort_by(fn {features, _} -> distance(point, features) end)
|> Enum.take(@k)
end
# Enum.frequencies counts the votes into a map, but a map doesn't keep
# first-seen order, so we walk the varieties in the order they appear.
# max_by returns the first of equal maxima, so on a tied vote the variety
# seen first among the neighbors wins.
def majority(labels) do
votes = Enum.frequencies(labels)
labels |> Enum.uniq() |> Enum.max_by(&votes[&1])
end
def classify(train, point) do
train |> nearest(point) |> Enum.map(&elem(&1, 1)) |> majority()
end
end
[path] = System.argv()
# split_with returns {rows that pass the test, the rest}.
{train, test} =
path
|> Knn.read_rows()
|> Enum.split_with(&(&1["split"] == "train"))
train = Enum.map(train, &Knn.seed/1)
test = Enum.map(test, &Knn.seed/1)
correct = Enum.count(test, fn {point, variety} -> Knn.classify(train, point) == variety end)
IO.puts("train_count #{length(train)}")
IO.puts("test_count #{length(test)}")
IO.puts("correct #{correct}")
IO.puts("accuracy #{:erlang.float_to_binary(correct / length(test), decimals: 6)}")We read every row into a map keyed by the header’s column names, split the
rows into training and test seeds with Enum.split_with, and, for each test
seed, sort all 150 training seeds by Euclidean distance and let the 5
nearest vote.
Enum.sort_by is a stable merge sort, so seeds at exactly equal distances
keep file order. Enum.frequencies counts the votes, but its map doesn’t
keep first-seen order, so we walk the varieties as they appear and let
Enum.max_by, which returns the first of equal maxima, pick the winner.
Nothing here is a kNN classifier, and Hex packages such as Nx aren’t
installed.
! k-nearest neighbors classification, using only standard Fortran.
!
! Each test seed is labelled with the majority variety among its K nearest
! training seeds, by Euclidean distance.
program k_nearest_neighbors
implicit none
integer, parameter :: dp = kind(1.0d0) ! double precision
integer, parameter :: k = 5
! A derived type groups a seed's measurements with its variety.
type :: seed
real(dp) :: point(2)
character(len=16) :: variety
end type seed
type(seed), allocatable :: train(:), test(:)
integer :: i, correct
call read_seeds(train, test)
correct = 0
do i = 1, size(test)
if (classify(test(i)%point) == test(i)%variety) correct = correct + 1
end do
print "(a, 1x, i0)", "train_count", size(train)
print "(a, 1x, i0)", "test_count", size(test)
print "(a, 1x, i0)", "correct", correct
call say("accuracy", real(correct, dp) / size(test))
contains
function classify(point) result(variety)
real(dp), intent(in) :: point(2)
character(len=16) :: variety
character(len=16) :: nearest(k)
real(dp) :: distance(size(train))
logical :: taken(size(train))
integer :: votes(k), i, j
! norm2 is the Euclidean length of a vector, so this is the distance.
do i = 1, size(train)
distance(i) = norm2(point - train(i)%point)
end do
! Take the closest untaken seed k times. minloc returns the first of
! equal minimums, so equal distances keep file order, like a stable sort.
taken = .false.
do i = 1, k
j = minloc(distance, dim=1, mask=.not. taken)
taken(j) = .true.
nearest(i) = train(j)%variety
end do
! Each neighbor's vote total; maxloc also returns the first maximum, so
! a tied vote goes to the variety seen first among the nearest.
do i = 1, k
votes(i) = count(nearest == nearest(i))
end do
variety = nearest(maxloc(votes, dim=1))
end function classify
subroutine read_seeds(train, test)
type(seed), allocatable, intent(out) :: train(:), test(:)
character(len=256) :: path, line, text
integer :: unit, status, length_col, width_col, variety_col, split_col
type(seed) :: s
call get_command_argument(1, path)
open(newunit=unit, file=path, status="old", action="read")
read(unit, "(a)") line
length_col = field_index(line, "length_mm")
width_col = field_index(line, "width_mm")
variety_col = field_index(line, "variety")
split_col = field_index(line, "split")
allocate(train(0), test(0))
do
read(unit, "(a)", iostat=status) line
if (status /= 0) exit
! An internal read parses a number. It must read from a variable,
! not straight from the result of field(), so we copy into text.
text = field(line, length_col)
read(text, *) s%point(1)
text = field(line, width_col)
read(text, *) s%point(2)
s%variety = field(line, variety_col)
if (field(line, split_col) == "train") then
train = [train, s] ! grows the array by one
else
test = [test, s]
end if
end do
close(unit)
end subroutine read_seeds
! The position of a name in a comma-separated header line.
integer function field_index(header, name)
character(len=*), intent(in) :: header, name
integer :: i, fields
fields = 1
do i = 1, len_trim(header)
if (header(i:i) == ",") fields = fields + 1
end do
do field_index = 1, fields
if (field(header, field_index) == name) return
end do
error stop "column not found: " // name
end function field_index
! The k-th comma-separated field of a line.
function field(line, k) result(text)
character(len=*), intent(in) :: line
integer, intent(in) :: k
character(len=:), allocatable :: text
integer :: start, i, comma
start = 1
do i = 1, k - 1
start = start + index(line(start:), ",")
end do
comma = index(line(start:), ",")
if (comma == 0) then
text = trim(line(start:))
else
text = line(start:start + comma - 2)
end if
end function field
! Print "name value" with six decimals. The f0.6 format drops the zero
! before the point (0.5 prints as .500000), so we put it back.
subroutine say(name, x)
character(len=*), intent(in) :: name
real(dp), intent(in) :: x
character(len=40) :: text
write(text, "(f0.6)") x
if (text(1:1) == ".") text = "0" // text
if (text(1:2) == "-.") text = "-0" // text(2:)
print "(a, 1x, a)", name, trim(text)
end subroutine say
end program k_nearest_neighborsEach seed is a derived type holding its two measurements and its variety, and
norm2(point - train(i)%point) is the distance: norm2 gives the Euclidean
length of a vector, a general tool like Python’s math.dist.
Fortran has no sort intrinsic, so we pick the nearest five one at a time with
minloc(distance, dim=1, mask=.not. taken). minloc returns the first of
equal minimums, so equal distances keep file order, as a stable sort would.
maxloc does the same for votes, so a tie goes to the variety seen first. One
gfortran surprise: an internal read can’t parse straight from a function’s
result, so each field is copied into a variable first.
// k-nearest neighbors classification, using only the standard library.
//
// Each test seed is labelled with the majority variety among its K nearest
// training seeds, by Euclidean distance.
package main
import (
"cmp"
"encoding/csv"
"fmt"
"math"
"os"
"slices"
"strconv"
)
const k = 5
var features = []string{"length_mm", "width_mm"}
const label = "variety"
type seed struct {
features []float64
label string
}
func read(path string) (train, test []seed, err error) {
f, err := os.Open(path)
if err != nil {
return nil, nil, err
}
defer f.Close()
records, err := csv.NewReader(f).ReadAll()
if err != nil {
return nil, nil, err
}
// Map each header name to its column number.
column := map[string]int{}
for i, name := range records[0] {
column[name] = i
}
for _, record := range records[1:] {
s := seed{label: record[column[label]]}
for _, name := range features {
v, err := strconv.ParseFloat(record[column[name]], 64)
if err != nil {
return nil, nil, err
}
s.features = append(s.features, v)
}
if record[column["split"]] == "train" {
train = append(train, s)
} else {
test = append(test, s)
}
}
return train, test, nil
}
func distance(a, b []float64) float64 {
sum := 0.0
for i := range a {
sum += (a[i] - b[i]) * (a[i] - b[i])
}
return math.Sqrt(sum)
}
func classify(point []float64, train []seed) string {
type neighbor struct {
distance float64
label string
}
neighbors := make([]neighbor, len(train))
for i, s := range train {
neighbors[i] = neighbor{distance(point, s.features), s.label}
}
// A stable sort, so equal distances keep file order.
slices.SortStableFunc(neighbors, func(a, b neighbor) int {
return cmp.Compare(a.distance, b.distance)
})
// Count the votes of the K nearest. The comparison is strict, so a tied
// vote goes to the label that reached the top count first.
votes := map[string]int{}
winner := ""
for _, n := range neighbors[:k] {
votes[n.label]++
if votes[n.label] > votes[winner] {
winner = n.label
}
}
return winner
}
func main() {
train, test, err := read(os.Args[1])
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
correct := 0
for _, s := range test {
if classify(s.features, train) == s.label {
correct++
}
}
fmt.Printf("train_count %d\n", len(train))
fmt.Printf("test_count %d\n", len(test))
fmt.Printf("correct %d\n", correct)
fmt.Printf("accuracy %.6f\n", float64(correct)/float64(len(test)))
}Go’s standard library has no counter type, but a map does the job: a missing
key reads as zero, so votes[n.label]++ counts a vote with no setup. We
keep track of the leader as we count, using a strict >, so a tied vote
would go to the label that reached the top count first.
For tie-breaking on distance, the choice of sort matters. slices.SortFunc
is documented as not guaranteed stable, so we use slices.SortStableFunc,
which keeps equal distances in file order, with cmp.Compare as the
comparison. Each neighbor is a small struct holding a distance and a label,
declared inside the function that uses it.
-- k-nearest neighbors classification, using only Haskell's base library.
--
-- Each test seed is labelled with the majority variety among its k nearest
-- training seeds, by Euclidean distance. There's no CSV reader in base, so
-- we split lines ourselves and find each column by its header name.
import Data.List (elemIndex, nub, sortOn)
import System.Environment (getArgs)
import Text.Printf (printf)
k :: Int
k = 5
-- A seed is its (length, width) in millimetres and its variety.
type Seed = ((Double, Double), String)
-- Split a line at every comma. break returns the text before the first comma
-- and the rest, which still starts with the comma.
splitOnComma :: String -> [String]
splitOnComma line = case break (== ',') line of
(field, ',' : rest) -> field : splitOnComma rest
(field, _) -> [field]
-- The position of a column in the header, or a stop with a message.
columnIndex :: [String] -> String -> Int
columnIndex header name = case elemIndex name header of
Just index -> index
Nothing -> error ("no column " ++ name)
-- Every row as a seed, paired with its split ("train" or "test").
readSeeds :: String -> [(String, Seed)]
readSeeds text = case lines text of
[] -> error "empty file"
headerLine : rows ->
[ (field "split", ((read (field "length_mm"), read (field "width_mm")), field "variety"))
| row <- rows
, not (null row)
, let fields = splitOnComma row
field name = fields !! columnIndex header name
]
where
header = splitOnComma headerLine
distance :: (Double, Double) -> (Double, Double) -> Double
distance (l1, w1) (l2, w2) = sqrt ((l1 - l2) ^ (2 :: Int) + (w1 - w2) ^ (2 :: Int))
-- Sort the training seeds by distance and keep the first k. sortOn is stable,
-- so seeds at exactly equal distances stay in file order.
nearest :: [Seed] -> (Double, Double) -> [Seed]
nearest train point = take k (sortOn (\(features, _) -> distance point features) train)
-- The variety with the most votes. nub lists each variety once, in the order
-- it first appears. foldl1 walks the counts left to right, and > is strict,
-- so on equal counts the earlier variety would win.
majority :: [String] -> String
majority labels = fst (foldl1 pick counts)
where
counts = [(label, length (filter (== label) labels)) | label <- nub labels]
pick best candidate = if snd candidate > snd best then candidate else best
classify :: [Seed] -> (Double, Double) -> String
classify train point = majority [label | (_, label) <- nearest train point]
main :: IO ()
main = do
[path] <- getArgs
text <- readFile path
let seeds = readSeeds text
train = [seed | ("train", seed) <- seeds]
test = [seed | ("test", seed) <- seeds]
correct = length [() | (point, label) <- test, classify train point == label]
accuracy = fromIntegral correct / fromIntegral (length test) :: Double
printf "train_count %d\n" (length train)
printf "test_count %d\n" (length test)
printf "correct %d\n" correct
printf "accuracy %.6f\n" accuracyEach seed is a tuple, ((length, width), variety), and the comprehension
[seed | ("train", seed) <- seeds] keeps only the rows whose split matches,
quietly skipping the rest. To find the 5 nearest, we sort all 150 training
seeds with sortOn, keyed on distance, and take 5. sortOn is stable, so
seeds at exactly equal distances keep their file order, and it computes each
key once.
For the vote, nub lists each variety once and filter counts it. We pick
the winner with foldl1 rather than maximumBy, which returns the last of
equal counts, not the first. No kNN function is called.
// k-nearest neighbors classification, using only the Java standard library.
//
// Each test seed is labelled with the majority variety among its K nearest
// training seeds, by Euclidean distance.
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.stream.Collectors;
class Main {
static final int K = 5;
// A record is a small class that holds values: Java writes its
// constructor, its accessors (seed.length()), equals, and toString.
record Seed(double length, double width, String variety) {}
record Neighbor(double distance, String variety) {}
// The named column of a CSV file's lines, as text. Numbers are parsed by
// the caller, since the variety and split columns are words.
static String[] readColumn(List<String> lines, String name) {
int index = Arrays.asList(lines.get(0).split(",")).indexOf(name);
if (index < 0) {
throw new IllegalArgumentException("no column " + name);
}
String[] values = new String[lines.size() - 1];
for (int row = 1; row < lines.size(); row++) {
values[row - 1] = lines.get(row).split(",")[index];
}
return values;
}
static String classify(Seed point, List<Seed> train) {
List<Neighbor> neighbors = new ArrayList<>();
for (Seed seed : train) {
// Math.hypot(dx, dy) is the straight-line distance, sqrt(dx*dx + dy*dy).
double d = Math.hypot(point.length() - seed.length(), point.width() - seed.width());
neighbors.add(new Neighbor(d, seed.variety()));
}
// List.sort is stable, so equal distances keep file order.
neighbors.sort(Comparator.comparingDouble(Neighbor::distance));
// Count the votes of the K nearest: groupingBy makes a map from each
// variety to how many neighbors have it.
Map<String, Long> votes = neighbors.subList(0, K).stream()
.collect(Collectors.groupingBy(Neighbor::variety, Collectors.counting()));
// With two varieties and an odd K, the vote can't tie.
String winner = null;
for (var vote : votes.entrySet()) {
if (winner == null || vote.getValue() > votes.get(winner)) {
winner = vote.getKey();
}
}
return winner;
}
// Reading a file can fail with an IOException, and Java makes us say so
// with "throws".
public static void main(String[] args) throws IOException {
List<String> lines = Files.readAllLines(Path.of(args[0]));
String[] lengths = readColumn(lines, "length_mm");
String[] widths = readColumn(lines, "width_mm");
String[] varieties = readColumn(lines, "variety");
String[] splits = readColumn(lines, "split");
List<Seed> train = new ArrayList<>(), test = new ArrayList<>();
for (int i = 0; i < lengths.length; i++) {
var seed = new Seed(Double.parseDouble(lengths[i]),
Double.parseDouble(widths[i]), varieties[i]);
// Strings are compared with equals; == would compare objects.
(splits[i].equals("train") ? train : test).add(seed);
}
int correct = 0;
for (Seed seed : test) {
if (classify(seed, train).equals(seed.variety())) {
correct++;
}
}
Locale root = Locale.ROOT;
System.out.printf(root, "train_count %d%n", train.size());
System.out.printf(root, "test_count %d%n", test.size());
System.out.printf(root, "correct %d%n", correct);
System.out.printf(root, "accuracy %.6f%n", (double) correct / test.size());
}
}Each seed is a record, a one-line class for which Java writes the
constructor, the accessors, equals, and toString. We measure distance
with Math.hypot, collect a Neighbor record for every training seed, and
sort them with List.sort, which Java documents as stable, so equal
distances keep file order. For the 0.13 mm pair, Math.hypot gives the same
0.1299999999999999 and 0.13000000000000037 that Python does.
Java has no counter type, so Collectors.groupingBy with
Collectors.counting() turns the five nearest into a map from variety to
votes. Labels are compared with equals, since == on strings compares
objects: the "train" that split returns isn’t == to the literal.
// k-nearest neighbors classification, using only Node's built-in modules.
// Each test seed is labelled with the majority variety among its K nearest
// training seeds, by Euclidean distance.
import { readFileSync } from "node:fs";
const K = 5;
const FEATURES = ["length_mm", "width_mm"];
const LABEL = "variety";
// Node has no CSV parser. No field here is quoted, so we split on commas and
// turn each line into an object keyed by the header names.
function readRows(path) {
const [header, ...lines] = readFileSync(path, "utf8").trim().split("\n");
const names = header.split(",");
return lines.map((line) => {
const fields = line.split(",");
return Object.fromEntries(names.map((name, i) => [name, fields[i]]));
});
}
function distance(a, b) {
return Math.sqrt(a.reduce((acc, x, i) => acc + (x - b[i]) ** 2, 0));
}
function classify(point, train) {
// Array.prototype.sort is stable (guaranteed since ES2019), so seeds at an
// equal distance keep file order. toSorted() returns a sorted copy.
const nearest = train
.map((seed) => ({ label: seed.label, dist: distance(point, seed.features) }))
.toSorted((a, b) => a.dist - b.dist)
.slice(0, K);
// A Map keeps insertion order, and we keep the first label to reach the
// top count, so a tied vote goes to the label seen first among the nearest.
const votes = new Map();
for (const { label } of nearest) votes.set(label, (votes.get(label) ?? 0) + 1);
let best = null;
for (const [label, count] of votes) {
if (best === null || count > votes.get(best)) best = label;
}
return best;
}
const seeds = readRows(process.argv[2]).map((row) => ({
features: FEATURES.map((name) => Number(row[name])),
label: row[LABEL],
split: row.split,
}));
const train = seeds.filter((seed) => seed.split === "train");
const test = seeds.filter((seed) => seed.split === "test");
const correct = test.filter((seed) => classify(seed.features, train) === seed.label).length;
console.log(`train_count ${train.length}`);
console.log(`test_count ${test.length}`);
console.log(`correct ${correct}`);
console.log(`accuracy ${(correct / test.length).toFixed(6)}`);The neighbor search is a chain of array methods: map pairs each training
seed with its distance, toSorted orders the pairs without changing
train, and slice(0, K) keeps the nearest five. JavaScript’s sort is
stable, so seeds at an equal distance keep file order without the index
tie-breaker Ruby needs. The comparator matters: with none, sort compares
values as strings.
There is no Counter, so the vote is counted in a Map, which keeps keys
in insertion order. Taking the first label to reach the top count sends a
tied vote to the label seen first among the nearest, as in Python and Ruby.
The standard library has no kNN classifier to skip.
# k-nearest neighbors classification, using only Base Julia.
#
# Each test seed is labelled with the majority variety among its K nearest
# training seeds, by Euclidean distance.
using Printf
const K = 5
struct Seed
point::Vector{Float64}
variety::String
end
function read_seeds(path)
train, test = Seed[], Seed[]
for line in Iterators.drop(eachline(path), 1) # skip the header
length_mm, width_mm, variety, split_name = split(line, ",")
seed = Seed(parse.(Float64, [length_mm, width_mm]), variety)
push!(split_name == "train" ? train : test, seed)
end
return train, test
end
distance(a, b) = sqrt(sum((a .- b) .^ 2))
function classify(point, train)
# Julia's default sort is stable, so equal distances keep file order.
nearest = sort(train, by = seed -> distance(point, seed.point))[1:K]
votes = Dict{String,Int}()
for seed in nearest
votes[seed.variety] = get(votes, seed.variety, 0) + 1
end
# Pick the most votes; among ties, the variety seen first among the nearest.
best = maximum(values(votes))
return first(seed.variety for seed in nearest if votes[seed.variety] == best)
end
function main(path)
train, test = read_seeds(path)
correct = count(seed -> classify(seed.point, train) == seed.variety, test)
println("train_count $(length(train))")
println("test_count $(length(test))")
println("correct $correct")
@printf("accuracy %.6f\n", correct / length(test))
end
main(ARGS[1])Each seed is a small struct holding its point and its variety, and the
nearest five come from sort(train, by = ...). Julia’s default sort is
documented as stable, so seeds at equal distances keep their file order, as
in Python. The distance is written out as
sqrt(sum((a .- b) .^ 2)); Base has no distance function to avoid.
Julia has no Counter, so the votes go into a Dict with
get(votes, variety, 0) + 1. A Dict doesn’t keep insertion order, so a
tied vote is settled by walking the nearest seeds in order and taking the
first variety with the most votes.
-- k-nearest neighbors classification, using only Lua's standard library.
--
-- Each test seed is labelled with the majority variety among its K nearest
-- training seeds, by Euclidean distance. Lua has no kNN or distance
-- function, so both are written out.
local K = 5
-- Each seed becomes a table with named fields, like a small record:
-- {len = 5.5, wid = 3.11, label = "kama"}.
local function read_seeds(path)
local f = assert(io.open(path, "r"))
local col, i = {}, 0
for field in f:read("l"):gmatch("[^,]+") do
i = i + 1
col[field] = i -- column name -> position
end
local train, test = {}, {}
for line in f:lines() do
local fields = {}
for field in line:gmatch("[^,]+") do
fields[#fields + 1] = field
end
local seed = {
len = tonumber(fields[col.length_mm]),
wid = tonumber(fields[col.width_mm]),
label = fields[col.variety],
}
local list = fields[col.split] == "train" and train or test
list[#list + 1] = seed
end
f:close()
return train, test
end
local function classify(point, train)
-- Pair each training seed's distance with its row number.
local scored = {}
for row, seed in ipairs(train) do
local d = math.sqrt((point.len - seed.len) ^ 2 + (point.wid - seed.wid) ^ 2)
scored[row] = {d = d, row = row, label = seed.label}
end
-- table.sort isn't stable, so equal distances could come out in any
-- order. Breaking ties by row number keeps the earlier training seed.
table.sort(scored, function(a, b)
if a.d ~= b.d then return a.d < b.d end
return a.row < b.row
end)
-- Count votes in a table keyed by label; a missing key reads as nil, so
-- "or 0" starts each count. With two varieties and odd K, no vote ties.
local votes, best = {}, nil
for i = 1, K do
local label = scored[i].label
votes[label] = (votes[label] or 0) + 1
if best == nil or votes[label] > votes[best] then best = label end
end
return best
end
local train, test = read_seeds(arg[1])
local correct = 0
for _, seed in ipairs(test) do
if classify(seed, train) == seed.label then
correct = correct + 1
end
end
print("train_count " .. #train)
print("test_count " .. #test)
print("correct " .. correct)
print(string.format("accuracy %.6f", correct / #test))Lua keeps each seed as a table with named fields, {len, wid, label}, so
seed.len reads like a record. For every test seed we score each training
seed’s distance, then table.sort orders them with our own comparison.
That sort isn’t stable, so equal distances could come out in any order;
the comparison breaks ties by row number to keep the earlier seed.
Lua has no counter type, kNN, or distance function. Votes go in a table
keyed by label: a missing key reads as nil, so (votes[label] or 0) + 1
starts each count at 1. The distance is written out with math.sqrt and ^.
(* k-nearest neighbors classification, using only OCaml's standard library.
Each test seed is labelled with the majority variety among its k nearest
training seeds, by Euclidean distance. *)
let k = 5
(* A record type: each seed's measurements in millimetres and its variety. *)
type seed = { len : float; wid : float; variety : string }
(* Every row as (split, seed), with each column found by its header name. *)
let read_seeds path =
In_channel.with_open_text path (fun ic ->
let lines = In_channel.input_lines ic in
let header = String.split_on_char ',' (List.hd lines) in
let index name =
match List.find_index (String.equal name) header with
| Some i -> i
| None -> failwith ("column not found: " ^ name)
in
List.map
(fun line ->
let fields = String.split_on_char ',' line in
let field name = List.nth fields (index name) in
( field "split",
{ len = float_of_string (field "length_mm");
wid = float_of_string (field "width_mm");
variety = field "variety" } ))
(List.tl lines))
let distance a b = sqrt (((a.len -. b.len) ** 2.) +. ((a.wid -. b.wid) ** 2.))
(* Sort the training seeds by distance and keep the first k. stable_sort
keeps seeds at exactly equal distances in file order; the docs don't
promise that for List.sort. *)
let nearest train point =
let by_distance =
List.stable_sort
(fun a b -> Float.compare (distance point a) (distance point b))
train
in
List.filteri (fun i _ -> i < k) by_distance
(* Count votes in an association list of (variety, count) pairs. A new
variety goes on the end, so the list keeps first-seen order. *)
let rec add_vote label = function
| [] -> [ (label, 1) ]
| (l, n) :: rest when l = label -> (l, n + 1) :: rest
| pair :: rest -> pair :: add_vote label rest
(* The variety with the most votes. > is strict, so on equal counts the
variety seen first among the neighbors wins. *)
let majority labels =
let counts = List.fold_left (fun acc l -> add_vote l acc) [] labels in
let pick (bl, bn) (l, n) = if n > bn then (l, n) else (bl, bn) in
fst (List.fold_left pick (List.hd counts) (List.tl counts))
let classify train point =
majority (List.map (fun s -> s.variety) (nearest train point))
let () =
let seeds = read_seeds Sys.argv.(1) in
(* partition splits one list into the rows that pass a test and the rest *)
let train, test = List.partition (fun (split, _) -> split = "train") seeds in
let train = List.map snd train and test = List.map snd test in
let correct =
List.length (List.filter (fun s -> classify train s = s.variety) test)
in
Printf.printf "train_count %d\n" (List.length train);
Printf.printf "test_count %d\n" (List.length test);
Printf.printf "correct %d\n" correct;
Printf.printf "accuracy %.6f\n"
(float_of_int correct /. float_of_int (List.length test))OCaml keeps each seed as a record, { len; wid; variety }, so s.len
reads like a field. For every test seed, List.stable_sort orders the
training seeds by distance, and we keep the first five. Stable matters:
Array.sort is a heap sort, and a run shows it reorders equal keys, while
stable_sort is guaranteed to keep equal distances in file order.
OCaml has no counter type, kNN, or distance function. Votes go in an
association list of (variety, count) pairs, and a recursive function
adds one vote at a time. The distance is written out with sqrt and
**.
% k-nearest neighbors classification, using only core GNU Octave.
%
% Each test seed is labelled with the majority variety among its K nearest
% training seeds, by Euclidean distance. Core Octave has no kNN function, and
% the Octave Forge statistics package isn't installed.
% The named column of a CSV file, as a column cell array of strings. Wrap it
% in str2double to get numbers.
function values = read_column(path, name)
lines = strsplit(strtrim(fileread(path)), "\n");
header = strsplit(strtrim(lines{1}), ",");
index = find(strcmp(header, name));
if isempty(index)
error("no column %s", name);
end
values = cell(numel(lines) - 1, 1);
for row = 2:numel(lines)
fields = strsplit(strtrim(lines{row}), ",");
values{row - 1} = fields{index};
end
end
K = 5;
args = argv();
len = str2double(read_column(args{1}, "length_mm"));
wid = str2double(read_column(args{1}, "width_mm"));
variety = read_column(args{1}, "variety");
split_name = read_column(args{1}, "split");
% strcmp compares a whole cell array with one string, giving a logical mask.
is_train = strcmp(split_name, "train");
train_len = len(is_train);
train_wid = wid(is_train);
train_variety = variety(is_train);
test_len = len(~is_train);
test_wid = wid(~is_train);
test_variety = variety(~is_train);
correct = 0;
for t = 1:numel(test_len)
% Distances from this test seed to all 150 training seeds at once.
d = sqrt((train_len - test_len(t)) .^ 2 + (train_wid - test_wid(t)) .^ 2);
% sort returns the sorted values and their original positions. It's
% stable, so equal distances keep file order.
[~, order] = sort(d);
nearest = train_variety(order(1:K));
% Count how many of the nearest share each one's variety. max returns the
% first position of the largest count, so a tie goes to the nearer seed.
votes = zeros(K, 1);
for i = 1:K
votes(i) = sum(strcmp(nearest, nearest{i}));
end
[~, best] = max(votes);
correct = correct + strcmp(nearest{best}, test_variety{t});
end
printf("train_count %d\n", numel(train_len));
printf("test_count %d\n", numel(test_len));
printf("correct %d\n", correct);
printf("accuracy %.6f\n", correct / numel(test_len));For each test seed, one line computes the distance to all 150 training seeds
at once, as a column, with .^ and sqrt. [~, order] = sort(d) then
returns the positions of the sorted distances, and the first five are the
neighbors. Octave’s help sort says equal elements keep their original
order, so a tie goes to the earlier training row.
There’s no counter type, so we count votes with strcmp, which compares a
whole cell array of labels with one string and returns a mask to sum.
max returns the first position of the largest count. Core Octave has
no knnsearch or fitcknn, and the statistics package isn’t installed.
{ k-nearest neighbors classification, using only Free Pascal's run-time
library.
Each test seed is labelled with the majority variety among its K nearest
training seeds, by Euclidean distance. There is no classifier to avoid;
sorting uses TArrayHelper from Generics.Collections, and the votes are
counted in a loop. }
program KNearestNeighbors;
{$mode objfpc}{$H+} // 32-bit Integer, and strings longer than 255 characters
uses
SysUtils, Generics.Collections, Generics.Defaults;
const
K = 5;
type
// A record groups one seed's measurements with its variety.
TSeed = record
LengthMm, WidthMm: Double;
Variety: String;
end;
TSeedArray = array of TSeed;
// A training seed's distance from the test seed, and its row in the file.
TNeighbor = record
Distance: Double;
Index: Integer;
end;
TNeighborArray = array of TNeighbor;
// The named column of a CSV file, as text. Numbers are parsed by the
// caller, since the variety and split columns are words.
function ReadColumn(const Path, Name: String): TStringArray;
var
F: TextFile;
Line: String;
Fields: TStringArray;
Col, I: Integer;
begin
Result := nil;
AssignFile(F, Path);
Reset(F);
ReadLn(F, Line);
Fields := Line.Split(',');
Col := -1;
for I := 0 to High(Fields) do
if Fields[I] = Name then
Col := I;
if Col < 0 then
raise Exception.Create('column not found: ' + Name);
while not Eof(F) do
begin
ReadLn(F, Line);
Fields := Line.Split(',');
SetLength(Result, Length(Result) + 1); // grow by one
Result[High(Result)] := Fields[Col];
end;
CloseFile(F);
end;
// TArrayHelper.Sort is a quicksort, which doesn't keep equal elements in
// order, so equal distances fall back to file order.
function CompareNeighbors(constref A, B: TNeighbor): Integer;
begin
if A.Distance < B.Distance then Result := -1
else if A.Distance > B.Distance then Result := 1
else Result := A.Index - B.Index;
end;
function Classify(const Point: TSeed; const Train: TSeedArray): String;
var
Neighbors: TNeighborArray;
I, J, Votes, BestVotes: Integer;
begin
Neighbors := nil;
SetLength(Neighbors, Length(Train));
for I := 0 to High(Train) do
begin
Neighbors[I].Distance := Sqrt(Sqr(Point.LengthMm - Train[I].LengthMm) +
Sqr(Point.WidthMm - Train[I].WidthMm));
Neighbors[I].Index := I;
end;
// @ passes the function itself, not a call to it.
specialize TArrayHelper<TNeighbor>.Sort(Neighbors,
specialize TComparer<TNeighbor>.Construct(@CompareNeighbors));
// Count each of the K nearest labels' votes among the K; the first label
// to reach the highest count wins.
Result := '';
BestVotes := 0;
for I := 0 to K - 1 do
begin
Votes := 0;
for J := 0 to K - 1 do
if Train[Neighbors[J].Index].Variety = Train[Neighbors[I].Index].Variety then
Inc(Votes);
if Votes > BestVotes then
begin
Result := Train[Neighbors[I].Index].Variety;
BestVotes := Votes;
end;
end;
end;
var
Lengths, Widths, Varieties, Splits: TStringArray;
Train, Test: TSeedArray;
Seed: TSeed;
I, Correct: Integer;
begin
Lengths := ReadColumn(ParamStr(1), 'length_mm');
Widths := ReadColumn(ParamStr(1), 'width_mm');
Varieties := ReadColumn(ParamStr(1), 'variety');
Splits := ReadColumn(ParamStr(1), 'split');
Train := nil;
Test := nil;
for I := 0 to High(Lengths) do
begin
Seed.LengthMm := StrToFloat(Lengths[I]);
Seed.WidthMm := StrToFloat(Widths[I]);
Seed.Variety := Varieties[I];
// Strings compare by their text with =, and records copy by value.
if Splits[I] = 'train' then
Insert(Seed, Train, Length(Train)) // append
else
Insert(Seed, Test, Length(Test));
end;
Correct := 0;
for I := 0 to High(Test) do
if Classify(Test[I], Train) = Test[I].Variety then
Inc(Correct);
WriteLn('train_count ', Length(Train));
WriteLn('test_count ', Length(Test));
WriteLn('correct ', Correct);
WriteLn('accuracy ', Correct / Length(Test):0:6);
end.Free Pascal has no kNN classifier, and the dictionary in
Generics.Collections won’t compile with warnings as errors, so we count
votes the way C does: for each of the five nearest labels, a loop counts
how many of the five share it, compared with =, which compares a
string’s text.
A TSeed record holds a seed’s length, width, and variety. For each test
seed we fill an array of distance-and-row records and sort it with
TArrayHelper.Sort, passing a comparison function with @. That sort is
a quicksort and doesn’t keep equal elements in file order, so the
comparison breaks distance ties by row number.
# k-nearest neighbors classification, using only Perl and its core modules.
#
# Each test seed is labelled with the majority variety among its K nearest
# training seeds, by Euclidean distance. Perl has no kNN or distance
# function, so both are written out.
use strict;
use warnings;
my $K = 5;
# Each seed becomes a hash reference, a small record:
# { len => 5.5, wid => 3.11, label => 'kama' }. $seed->{len} reads a field.
sub read_seeds {
my ($path) = @_;
open my $fh, '<', $path or die "can't open $path: $!";
chomp(my $header = <$fh>);
my @fields = split /,/, $header;
my %col = map { $fields[$_] => $_ } 0 .. $#fields; # name -> position
my (@train, @test);
while (my $line = <$fh>) {
chomp $line;
my @row = split /,/, $line;
my $seed = {
len => $row[ $col{length_mm} ],
wid => $row[ $col{width_mm} ],
label => $row[ $col{variety} ],
};
if ($row[ $col{split} ] eq 'train') { push @train, $seed }
else { push @test, $seed }
}
close $fh;
return (\@train, \@test);
}
sub classify {
my ($point, $train) = @_;
# Pair each training seed's distance with its row number. The + marks
# the braces as a new hash, not a block of code.
my @scored = map {
my $seed = $train->[$_];
+{ d => sqrt(($point->{len} - $seed->{len}) ** 2
+ ($point->{wid} - $seed->{wid}) ** 2),
row => $_,
label => $seed->{label} }
} 0 .. $#$train;
# <=> compares numbers and returns -1, 0, or 1. When distances are equal
# it returns 0, which is false, so || falls through to the row number:
# equal distances keep the earlier training seed. Perl's sort is stable
# anyway, but the tie rule is now written in the code.
my @nearest = (sort { $a->{d} <=> $b->{d} || $a->{row} <=> $b->{row} }
@scored)[0 .. $K - 1];
# Count votes in a hash keyed by label. ++ on a missing key starts it
# at 0, with no warning. With two varieties and odd K, no vote ties.
my (%votes, $best);
for my $seed (@nearest) {
my $label = $seed->{label};
$votes{$label}++;
$best = $label if !defined $best || $votes{$label} > $votes{$best};
}
return $best;
}
my ($train, $test) = read_seeds($ARGV[0]);
my $correct = grep { classify($_, $train) eq $_->{label} } @$test;
print 'train_count ', scalar @$train, "\n";
print 'test_count ', scalar @$test, "\n";
print "correct $correct\n";
printf "accuracy %.6f\n", $correct / @$test;Each seed is a hash reference, a small record read as $seed->{len}, and
map pairs every training seed with its distance and row number. The sort
block, $a->{d} <=> $b->{d} || ..., compares distances first. When they’re
equal, <=> returns 0, which is false, so || falls through to the row
number and the earlier training seed wins. Perl’s sort is stable anyway,
but spelling out the tie rule means the result doesn’t depend on that.
A hash counts the votes: $votes{$label}++ starts a missing key at 0 with
no warning. Perl has no kNN or distance function, so both are written out,
and split /,/ reads the file because no field is quoted.
<?php
// k-nearest neighbors classification, using only PHP and the extensions
// built into it.
//
// Each test seed is labelled with the majority variety among its K nearest
// training seeds, by Euclidean distance. PHP has no kNN or distance
// function, so both are written out.
declare(strict_types=1);
const K = 5;
// Each seed becomes an array with string keys, a small record:
// ['len' => 5.5, 'wid' => 3.11, 'label' => 'kama'].
function read_seeds(string $path): array
{
$lines = file($path, FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$col = array_flip(explode(',', array_shift($lines))); // name => position
$train = [];
$test = [];
foreach ($lines as $line) {
$row = explode(',', $line);
$seed = [
'len' => (float) $row[$col['length_mm']],
'wid' => (float) $row[$col['width_mm']],
'label' => $row[$col['variety']],
];
if ($row[$col['split']] === 'train') {
$train[] = $seed;
} else {
$test[] = $seed;
}
}
return [$train, $test];
}
function classify(array $point, array $train): string
{
// Pair each training seed's distance with its row number.
$scored = [];
foreach ($train as $row => $seed) {
$d = sqrt(($point['len'] - $seed['len']) ** 2
+ ($point['wid'] - $seed['wid']) ** 2);
$scored[] = ['d' => $d, 'row' => $row, 'label' => $seed['label']];
}
// <=> returns -1, 0, or 1. When distances are equal it returns 0, and
// ?: falls through to the row number, so equal distances keep the
// earlier training seed. PHP 8's sort is stable anyway, but the tie
// rule is now written in the code.
usort($scored, fn($a, $b) => ($a['d'] <=> $b['d']) ?: ($a['row'] <=> $b['row']));
$nearest = array_slice($scored, 0, K);
// Count votes in an array keyed by label. ++ on a missing key warns,
// so ?? 0 supplies the starting count. With two varieties and odd K,
// no vote ties.
$votes = [];
$best = null;
foreach ($nearest as $seed) {
$label = $seed['label'];
$votes[$label] = ($votes[$label] ?? 0) + 1;
if ($best === null || $votes[$label] > $votes[$best]) {
$best = $label;
}
}
return $best;
}
[$train, $test] = read_seeds($argv[1]);
$correct = 0;
foreach ($test as $seed) {
if (classify($seed, $train) === $seed['label']) {
$correct++;
}
}
echo 'train_count ', count($train), "\n";
echo 'test_count ', count($test), "\n";
echo "correct $correct\n";
printf("accuracy %.6f\n", $correct / count($test));Each seed is a PHP array with string keys, which serves as a small record,
and array_flip turns the header into a map from column name to position.
We sort the scored seeds with usort and a comparison built from <=>.
When two distances are equal it returns 0, and
?: falls through to the row number. PHP 8’s sort is already stable, but
spelling out the tie rule means the result doesn’t depend on that.
Votes go in an array keyed by label. PHP warns when ++ meets a missing
key, so ?? 0 supplies the first count. array_count_values could tally
the labels in one call, but the loop also keeps track of the leader as it
counts.
-- k-nearest neighbors classification (k = 5), in PostgreSQL.
--
-- Each test seed is labelled with the majority variety among its 5 nearest
-- training seeds, by Euclidean distance.
WITH seeds AS (
-- A table has no row order; run.sh numbers rows in file order as row_id.
-- It only matters for breaking distance ties, which the data avoids.
SELECT row_id AS id, length_mm, width_mm, variety, split
FROM data
),
train AS (SELECT * FROM seeds WHERE split = 'train'),
test AS (SELECT * FROM seeds WHERE split = 'test'),
ranked AS (
-- Every (test, train) pair, ranked by distance within each test seed.
SELECT test.id, test.variety AS actual, train.variety AS neighbor,
row_number() OVER (
PARTITION BY test.id
ORDER BY sqrt((test.length_mm - train.length_mm) ^ 2
+ (test.width_mm - train.width_mm) ^ 2),
train.id
) AS rank
FROM test CROSS JOIN train
),
votes AS (
-- How many of the 5 nearest neighbors have each variety.
SELECT id, actual, neighbor, count(*) AS n
FROM ranked
WHERE rank <= 5
GROUP BY id, actual, neighbor
),
predictions AS (
-- The variety with the most votes. With two varieties and k = 5 it cannot tie.
SELECT DISTINCT ON (id) id, actual, neighbor AS predicted
FROM votes
ORDER BY id, n DESC
),
totals AS (
SELECT (SELECT count(*) FROM train) AS train_count,
(SELECT count(*) FROM test) AS test_count,
count(*) FILTER (WHERE predicted = actual) AS correct
FROM predictions
)
SELECT name, value
FROM totals,
LATERAL (VALUES
(1, 'train_count', train_count::text),
(2, 'test_count', test_count::text),
(3, 'correct', correct::text),
(4, 'accuracy', round(correct::numeric / test_count, 6)::text)
) AS results (position, name, value)
ORDER BY position;SQL suits the shape of kNN. “Every test seed against every training seed”
is a CROSS JOIN, 7,500 pairs here. row_number() OVER (PARTITION BY test.id ORDER BY ...) ranks the training seeds for each test seed, the vote
is a GROUP BY with count(*), and DISTINCT ON (id) ... ORDER BY id, n DESC keeps the winning variety.
Row order is where it pushes back. A table has none, so ties are broken by
the row_id column the harness adds in file order, as train.id in the
ORDER BY. The distance is written out with sqrt and ^. PostgreSQL’s
geometric point type has a distance operator, point(0, 0) <-> point(3, 4) returns 5, which would count as a general tool too. There is no kNN
classifier built in to skip.
% k-nearest neighbors classification, using SWI-Prolog and the libraries
% that come with it.
%
% Each test seed is labelled with the majority variety among its K nearest
% training seeds, by Euclidean distance. A rule such as
% classify(Train, Seed, Variety) is true when Variety is the vote of Seed's
% neighbors, and running the program asks Prolog to find values that make
% main true.
:- initialization(main, main).
k(5).
% read_seeds(+Path, -Train, -Test): every row as seed(Length, Width,
% Variety), split by its "split" column. findall collects every term that
% satisfies the goals in the middle, one per line. nth0 finds a column's
% position by its header name, or picks the field at that position.
read_seeds(Path, Train, Test) :-
read_file_to_string(Path, Text, []),
split_string(Text, "\n", "", [HeaderLine|Lines]),
split_string(HeaderLine, ",", "", Header),
nth0(L, Header, "length_mm"),
nth0(W, Header, "width_mm"),
nth0(V, Header, "variety"),
nth0(S, Header, "split"),
findall(Split-seed(Length, Width, Variety),
( member(Line, Lines),
Line \== "",
split_string(Line, ",", "", Fields),
nth0(L, Fields, LengthText),
nth0(W, Fields, WidthText),
nth0(V, Fields, Variety),
nth0(S, Fields, Split),
number_string(Length, LengthText),
number_string(Width, WidthText) ),
Rows),
% Only rows whose key unifies with "train" (or "test") are collected.
findall(Seed, member("train"-Seed, Rows), Train),
findall(Seed, member("test"-Seed, Rows), Test).
% distance_pair(+Seed, +TrainSeed, -Pair): Pair is Distance-Variety, the
% Key-Value form that keysort orders by key. "is" does the arithmetic.
distance_pair(seed(L1, W1, _), seed(L2, W2, Variety), Distance-Variety) :-
Distance is sqrt((L1 - L2) ** 2 + (W1 - W2) ** 2).
% nearest(+Train, +Seed, -Varieties): the varieties of the K training seeds
% closest to Seed. keysort is stable and keeps repeated keys, so seeds at
% exactly equal distances stay in file order. (sort/2 would drop pairs
% that are entirely equal.) append(Nearest, _, Sorted) holds when Nearest
% is the start of Sorted, and fixing its length at K takes the first K.
nearest(Train, Seed, Varieties) :-
maplist(distance_pair(Seed), Train, Pairs),
keysort(Pairs, Sorted),
k(K),
length(Nearest, K),
append(Nearest, _, Sorted),
pairs_values(Nearest, Varieties).
% majority(+Labels, -Winner): the label with the most votes. sort/2 drops
% repeats, which here is what we want: one entry per variety. aggregate_all
% counts the solutions of member(Label, Labels), that is, how many times
% Label appears. max_member picks the largest Count-Label pair; with two
% varieties and an odd K, two counts can never be equal.
majority(Labels, Winner) :-
sort(Labels, Candidates),
findall(Count-Label,
( member(Label, Candidates),
aggregate_all(count, member(Label, Labels), Count) ),
Counts),
max_member(_-Winner, Counts).
% classify(+Train, +Seed, -Variety): the variety Seed's neighbors vote for.
classify(Train, Seed, Variety) :-
nearest(Train, Seed, Labels),
majority(Labels, Variety).
% correct(+Train, +Seed): true when the vote matches Seed's own variety.
% When it doesn't, == fails, so the goal fails, and aggregate_all below
% simply doesn't count that seed.
correct(Train, Seed) :-
Seed = seed(_, _, Variety),
classify(Train, Seed, Predicted),
Predicted == Variety.
main :-
current_prolog_flag(argv, [Path|_]),
read_seeds(Path, Train, Test),
length(Train, TrainCount),
length(Test, TestCount),
aggregate_all(count, ( member(Seed, Test), correct(Train, Seed) ), Correct),
Accuracy is Correct / TestCount,
format("train_count ~d~n", [TrainCount]),
format("test_count ~d~n", [TestCount]),
format("correct ~d~n", [Correct]),
format("accuracy ~6f~n", [Accuracy]).We turn every training seed into a Distance-Variety pair and keysort
them. keysort is stable and keeps repeated keys, so seeds at exactly equal
distances stay in file order; sort/2 would drop pairs that are entirely
equal. To take the nearest five, we ask for a list of length 5 that
append can find at the front of the sorted pairs.
There’s no kNN classifier or counter type. Here sort/2 dropping repeats
helps: it lists each variety once, aggregate_all(count, ...) counts its
votes, and max_member picks the winner. The correct count is
aggregate_all again, over the test seeds whose vote matches.
# k-nearest neighbors classification, using only base R.
#
# Each test seed is labelled with the majority variety among its k = 5 nearest
# training seeds, by Euclidean distance.
k <- 5
args <- commandArgs(trailingOnly = TRUE)
data <- read.csv(args[1])
train <- data[data$split == "train", ]
test <- data[data$split == "test", ]
classify <- function(length_mm, width_mm) {
# Distances from this point to every training seed at once. order() is
# stable, so equal distances keep file order.
distance <- sqrt((train$length_mm - length_mm)^2 + (train$width_mm - width_mm)^2)
nearest <- train$variety[order(distance)[1:k]]
# table() counts the votes; with two varieties and odd k there is no tie.
votes <- table(nearest)
names(votes)[which.max(votes)]
}
predicted <- mapply(classify, test$length_mm, test$width_mm)
correct <- sum(predicted == test$variety)
cat(sprintf("train_count %d\n", nrow(train)))
cat(sprintf("test_count %d\n", nrow(test)))
cat(sprintf("correct %d\n", correct))
cat(sprintf("accuracy %.6f\n", correct / nrow(test)))R measures distance without a loop.
sqrt((train$length_mm - length_mm)^2 + (train$width_mm - width_mm)^2)
compares one test seed with all 150 training seeds at once,
order(distance)[1:k] picks the five nearest, and table() counts the vote.
order() keeps tied values in their original order, so equal distances keep
file order.
Where R pushes back is shape. Picking rows needs the trailing comma in
data[data$split == "train", ], and mapply() runs classify over the two
test columns side by side. One quiet difference: table() sorts labels
alphabetically and which.max() takes the first maximum, so a tied vote
would go to kama, not to the nearer label. With odd k there is no tie.
The usual built-in, knn(), lives in the class package, which isn’t
installed in this image.
# k-nearest neighbors classification, using only the standard library.
# Each test seed gets the majority variety among its K nearest training seeds,
# by Euclidean distance.
K = 5
FEATURES = %w[length_mm width_mm].freeze
LABEL = "variety"
# The csv library is a bundled gem since Ruby 3.4, so split lines by hand
# (no quoted fields here) and turn each row into a hash keyed by header name.
def read_rows(path)
header, *lines = File.readlines(path, chomp: true)
names = header.split(",")
lines.map { |line| names.zip(line.split(",")).to_h }
end
def distance(a, b)
Math.sqrt(a.zip(b).sum { |x, y| (x - y)**2 })
end
def classify(point, train)
# sort_by is not stable in Ruby, so add the file position as a tie-breaker:
# equal distances keep file order.
nearest = train.each_with_index
.sort_by { |(features, _), i| [distance(point, features), i] }
.first(K)
# tally keeps first-seen order and max_by keeps the first maximum, so a tied
# vote goes to the label that appears first among the nearest.
nearest.map { |(_, label), _| label }.tally.max_by { |_, votes| votes }.first
end
rows = read_rows(ARGV[0])
points = rows.map { |row| [FEATURES.map { |f| Float(row[f]) }, row[LABEL], row["split"]] }
train, test = points.partition { |_, _, split| split == "train" }
correct = test.count { |features, label, _| classify(features, train) == label }
puts "train_count #{train.length}"
puts "test_count #{test.length}"
puts "correct #{correct}"
puts format("accuracy %.6f", correct.fdiv(test.length))Ruby reads cleanly here. partition splits training from test seeds in one
call, tally turns the five neighbor labels into vote counts, and max_by
picks the winner. Distance is a one-liner,
Math.sqrt(a.zip(b).sum { |x, y| (x - y)**2 }), and it works for any number
of features. For exactly two, Math.hypot(dx, dy) would also do.
The catch is sorting. Ruby’s sort_by is not stable: when we sorted 100
pairs on a key with only two values, equal keys came back out of their
original order. So classify sorts by [distance, i], where i is the
file position from each_with_index. Equal distances then keep file order,
as in the other languages. Each line is split on commas by hand, which works
because no field in this file is quoted.
//! k-nearest neighbors classification, using only the standard library.
//!
//! Each test seed is labelled with the majority variety among its K nearest
//! training seeds, by Euclidean distance.
use std::env;
use std::fs;
const K: usize = 5;
const FEATURES: [&str; 2] = ["length_mm", "width_mm"];
const LABEL: &str = "variety";
struct Seed {
features: [f64; 2],
label: String,
}
/// Splits the file into training and test seeds. There is no CSV parser in
/// the standard library; the file has no quoted fields, so commas suffice.
fn read(path: &str) -> (Vec<Seed>, Vec<Seed>) {
let text = fs::read_to_string(path).expect("cannot read data file");
let mut lines = text.lines();
let header: Vec<&str> = lines.next().expect("empty file").split(',').collect();
let column = |name| {
header
.iter()
.position(|&h| h == name)
.expect("column not found")
};
let (feature_ix, label_ix, split_ix) = (FEATURES.map(column), column(LABEL), column("split"));
let (mut train, mut test) = (Vec::new(), Vec::new());
for line in lines {
let fields: Vec<&str> = line.split(',').collect();
let seed = Seed {
features: feature_ix.map(|i| fields[i].parse().unwrap()),
label: fields[label_ix].to_string(),
};
if fields[split_ix] == "train" {
train.push(seed);
} else {
test.push(seed);
}
}
(train, test)
}
fn distance(a: &[f64; 2], b: &[f64; 2]) -> f64 {
a.iter()
.zip(b)
.map(|(p, q)| (p - q).powi(2))
.sum::<f64>()
.sqrt()
}
fn classify(point: &[f64; 2], train: &[Seed]) -> String {
// Sort references to the training seeds by distance. sort_by is stable,
// so equal distances keep file order. f64 isn't Ord, hence total_cmp.
let mut nearest: Vec<&Seed> = train.iter().collect();
nearest.sort_by(|a, b| distance(point, &a.features).total_cmp(&distance(point, &b.features)));
// Count the votes in first-seen order, so a tied vote would go to the
// label met first among the nearest.
let mut votes: Vec<(&str, usize)> = Vec::new();
for seed in &nearest[..K] {
match votes.iter_mut().find(|(label, _)| *label == seed.label) {
Some((_, count)) => *count += 1,
None => votes.push((&seed.label, 1)),
}
}
// max_by_key returns the *last* maximum, so scan for the first by hand.
let mut winner = votes[0];
for &vote in &votes[1..] {
if vote.1 > winner.1 {
winner = vote;
}
}
winner.0.to_string()
}
fn main() {
let path = env::args().nth(1).expect("usage: main <data.csv>");
let (train, test) = read(&path);
let correct = test
.iter()
.filter(|seed| classify(&seed.features, &train) == seed.label)
.count();
println!("train_count {}", train.len());
println!("test_count {}", test.len());
println!("correct {correct}");
println!("accuracy {:.6}", correct as f64 / test.len() as f64);
}Like Python, Rust sorts all 150 training seeds for every test seed. sort_by
is stable, so seeds at an equal distance keep file order, and total_cmp
compares the f64 distances, since floats aren’t Ord. We sort references
to the seeds, so nothing is copied.
The vote takes more care. Rust has no counter type, so we keep a short list
of (label, count) pairs in first-seen order. Then we pick the winner by hand,
because max_by_key returns the last of equal maximums, not the first.
select_nth_unstable_by would find the five nearest without sorting the
rest, but it isn’t stable, so ties would lose file order.
// k-nearest neighbors classification, using only Swift's standard library
// and Foundation, which ships with it.
//
// Each test seed is labelled with the majority variety among its k nearest
// training seeds, by Euclidean distance.
import Foundation
let k = 5
let features = ["length_mm", "width_mm"]
let labelColumn = "variety"
// A struct is a value type: copying a Seed copies its fields.
struct Seed {
let point: [Double]
let label: String
}
// The rows of a CSV file, each as a dictionary from column name to text.
// A function that can fail is marked throws, and every call to it is marked
// try. The file has no quoted fields, so splitting on commas is enough.
func readRows(_ path: String) throws -> [[String: String]] {
let text = try String(contentsOfFile: path, encoding: .utf8)
// split skips empty pieces, so a blank last line doesn't become a row.
var lines = text.split(separator: "\n")
let header = lines.removeFirst().split(separator: ",").map(String.init)
return lines.map { line in
let fields = line.split(separator: ",", omittingEmptySubsequences: false).map(String.init)
// zip pairs each column name with its field, and the pairs become a
// dictionary.
return Dictionary(uniqueKeysWithValues: zip(header, fields))
}
}
// Looking up a dictionary key gives an optional, which ! unwraps. Double(_:)
// also gives nil for text that isn't a number, and ! stops the program there.
let rows = try readRows(CommandLine.arguments[1])
func seed(_ row: [String: String]) -> Seed {
Seed(point: features.map { Double(row[$0]!)! }, label: row[labelColumn]!)
}
let train = rows.filter { $0["split"] == "train" }.map(seed)
let test = rows.filter { $0["split"] == "test" }.map(seed)
func distance(_ a: [Double], _ b: [Double]) -> Double {
zip(a, b).map { p, q in (p - q) * (p - q) }.reduce(0, +).squareRoot()
}
func classify(_ point: [Double], _ train: [Seed]) -> String {
// Sort every training seed by distance and keep the first k. Swift's
// sorted(by:) is stable, so equal distances keep file order.
let nearest = train
.sorted { distance(point, $0.point) < distance(point, $1.point) }
.prefix(k)
// Count the votes. counts[label, default: 0] reads 0 for a label we
// haven't seen yet, so += 1 works the first time too.
var counts: [String: Int] = [:]
for seed in nearest {
counts[seed.label, default: 0] += 1
}
// A Dictionary has no fixed order, so pick the winner by walking the
// neighbors nearest first: a tied vote would go to the label met first.
var winner = nearest.first!.label
for seed in nearest where counts[seed.label]! > counts[winner]! {
winner = seed.label
}
return winner
}
let correct = test.filter { classify($0.point, train) == $0.label }.count
print("train_count", train.count)
print("test_count", test.count)
print("correct", correct)
print("accuracy", String(format: "%.6f", Double(correct) / Double(test.count)))Each seed is a struct holding its two measurements and its variety. For
every test seed we sort all 150 training seeds with sorted(by:), which
the standard library’s own documentation in the image calls “guaranteed to
be stable”, so equal distances keep file order. For the 0.13 mm pair,
Swift gets the same 0.1299999999999999 and 0.13000000000000037 as Python.
Swift has no counter type, so a Dictionary counts the votes:
counts[label, default: 0] += 1 starts a new label at zero. A
dictionary’s order changes from run to run, so we pick the winner by
walking the five neighbors nearest first, and a tie would go to the label
met first.
# k-nearest neighbors classification, using only Tcl's built-in commands.
#
# Each test seed is labelled with the majority variety among its K nearest
# training seeds, by Euclidean distance. Tcl has no kNN or distance command,
# so both are written out. expr does the arithmetic; its {braces} keep Tcl
# from substituting twice.
set K 5
# Each seed becomes a three-item list: {length width variety}.
proc read_seeds {path} {
set f [open $path r]
set header [split [gets $f] ,]
set cols {}
foreach name {length_mm width_mm variety split} {
set col [lsearch -exact $header $name]
if {$col < 0} { error "column not found: $name" }
lappend cols $col
}
set train {}
set test {}
while {[gets $f line] >= 0} {
# lassign unpacks a list into separate variables.
lassign [lmap col $cols {lindex [split $line ,] $col}] len wid label split
if {$split eq "train"} {
lappend train [list $len $wid $label]
} else {
lappend test [list $len $wid $label]
}
}
close $f
return [list $train $test]
}
proc classify {len wid train k} {
# Pair each training seed's distance with its label, then sort on the
# distance (-index 0) as a number (-real). lsort is stable, so equal
# distances keep file order.
set scored {}
foreach seed $train {
lassign $seed slen swid label
set d [expr {sqrt(($len - $slen) ** 2 + ($wid - $swid) ** 2)}]
lappend scored [list $d $label]
}
set nearest [lrange [lsort -real -index 0 $scored] 0 [expr {$k - 1}]]
# Count votes in a dict: dict incr starts a missing label at 0. A dict
# keeps first-seen order, and > keeps the first maximum, so a tied vote
# would go to the label seen first among the nearest.
set votes [dict create]
foreach pair $nearest {
dict incr votes [lindex $pair 1]
}
set best ""
set best_count 0
dict for {label count} $votes {
if {$count > $best_count} {
set best $label
set best_count $count
}
}
return $best
}
lassign [read_seeds [lindex $argv 0]] train test
set correct 0
foreach seed $test {
lassign $seed len wid label
if {[classify $len $wid $train $K] eq $label} {
incr correct
}
}
puts "train_count [llength $train]"
puts "test_count [llength $test]"
puts "correct $correct"
puts "accuracy [format %.6f [expr {double($correct) / [llength $test]}]]"Tcl keeps each seed as a small list, {length width variety}, and
lassign unpacks it into variables. For every test seed we pair each
training seed’s distance with its label, then lsort -real -index 0 sorts
those pairs by distance as numbers. Without -real, lsort would compare
text and put 10 before 9. Because lsort is stable, equal distances keep
file order, and lrange keeps the first five.
A dict counts the vote: dict incr starts a missing label at 0. Tcl has
no kNN or distance command, so the distance is written out with sqrt,
though expr also offers hypot.