Concept · intermediate
Cross-validation
Choose a model's settings by testing it on every part of the training data in turn.
Every model on this site has settings you choose before it learns anything: in k-nearest neighbors, the depth of a decision tree, the learning rate in logistic regression. Cross-validation is how you choose them honestly. It holds back part of the training data, tests the model there, and repeats until every part has had its turn.
The dataset
data.csv is the k-nearest neighbors data, unchanged: 200 synthetic wheat
seeds, kama or rosa, with kernel length_mm and width_mm. The split
column marks 150 as train and 50 as test. The kNN page fixed and
got 47 of the 50 test seeds right. Here we ask which we should have used.
Why not just use the test seeds?
Try every on the test seeds and you’d pick , which gets 48 of 50 right. But the test seeds exist to estimate how the model does on seeds it has never seen. Once they’ve chosen , they’ve been seen, and 48 of 50 is flattering, not honest.
The method
- Split the 150 training seeds into 5 folds of 30. The rows are already shuffled, so fold 1 is rows 1 to 30, fold 2 rows 31 to 60, and so on.
- For each odd from 1 to 15 (odd, so a two-way vote can’t tie), hold out each fold in turn, classify its 30 seeds using the other 120, and count the correct ones. Every training seed is held out exactly once, so the cross-validated accuracy is
- Pick the with the highest CV accuracy. On a tie, the smaller wins.
- Test once. Classify the 50 test seeds using all 150 training seeds and the chosen , and report that score.
Reading the results
| Correct per fold | CV accuracy | |
|---|---|---|
| 1 | 27, 28, 27, 27, 25 | 0.893 |
| 3 | 28, 29, 28, 27, 26 | 0.920 |
| 5 | 28, 29, 29, 28, 27 | 0.940 |
| 7 | 28, 29, 29, 28, 28 | 0.947 |
| 9 | 28, 29, 27, 28, 28 | 0.933 |
| 11 | 28, 28, 28, 28, 27 | 0.927 |
| 13 | 28, 28, 27, 28, 27 | 0.920 |
| 15 | 28, 28, 28, 28, 27 | 0.927 |
Cross-validation picks , at 142 of 150, and it gets 47 of the 50 test seeds right: the same 0.94 as the kNN page’s , but now a number we can trust.
Read across a row and you’ll see why one held-out set isn’t enough. With , the folds score anywhere from 25 to 28 out of 30. And if you’d used a single fold to choose, you’d have picked with fold 1 or 2, with fold 3 or 4, and only with fold 5. Averaging over all five folds smooths out that luck.
The extremes lose for opposite reasons: with , one oddly placed seed misleads its neighbors, and with large , the vote reaches into the other variety’s territory.
What to watch for across languages
None of these implementations calls a ready-made cross-validation routine; scikit-learn, R’s caret, and Julia’s MLJ have them, but aren’t installed. Each language reuses its kNN classifier, so the interest is in how it carves out a fold.
Watch what the second number in a slice means. Python’s train[30:60]
stops before row 60, Tcl’s lrange and Julia’s 31:60 include both ends,
and PHP’s array_slice takes a length instead of an end. Mix them up and a
fold comes out one row short or one row long.
Watch for views, too. Go’s train[a:b], Java’s subList, and C++‘s
std::span look at the original rows without copying them. That’s cheap,
but in Go the obvious
append(train[:a], train[b:]...) writes the later folds over the fold
being tested, and cross-validation reports 100% accuracy for . Go
copies with slices.Concat instead.
Some languages never cut at all. R drops the fold with a negative index,
train[-rows, ]. Octave and APL keep rows with a true-or-false mask. awk,
BASIC, and COBOL skip the held-out rows inside the neighbor search, and
PostgreSQL gives every row a fold number and joins on fold <> held.fold.
And watch the tie rule for the best . Haskell’s maximumBy returns the
last of equal values, so most languages compare with a strict >, which
keeps the smaller . APL’s ⍳ and PostgreSQL’s
ORDER BY accuracy DESC, k get the same answer by taking the first.
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 |
cv_accuracy_k1 | 0.893333 |
cv_accuracy_k3 | 0.920000 |
cv_accuracy_k5 | 0.940000 |
cv_accuracy_k7 | 0.946667 |
cv_accuracy_k9 | 0.933333 |
cv_accuracy_k11 | 0.926667 |
cv_accuracy_k13 | 0.920000 |
cv_accuracy_k15 | 0.926667 |
best_k | 7 |
test_correct | 47 |
test_accuracy | 0.940000 |
Implementations
"""5-fold cross-validation for k-nearest neighbors, using only the standard
library.
Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
holding out one fold at a time, picks the k with the best average accuracy,
and then scores that k once on the untouched test seeds.
"""
import csv
import math
import sys
from collections import Counter
FOLDS = 5
KS = range(1, 16, 2) # odd k only, so two varieties can't tie
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, k):
# 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 count_correct(points, train, k):
return sum(classify(point, train, k) == label for point, label in points)
def cv_accuracy(train, k):
# Fold f is rows f*size up to (f+1)*size. The rows are already shuffled,
# so consecutive blocks make fair folds.
size = len(train) // FOLDS
correct = 0
for f in range(FOLDS):
held_out = train[f * size:(f + 1) * size]
rest = train[:f * size] + train[(f + 1) * size:]
correct += count_correct(held_out, rest, k)
return correct / len(train)
def main():
train, test = read(sys.argv[1])
print(f"train_count {len(train)}")
print(f"test_count {len(test)}")
best_k, best_accuracy = None, -1.0
for k in KS:
accuracy = cv_accuracy(train, k)
print(f"cv_accuracy_k{k} {accuracy:.6f}")
if accuracy > best_accuracy: # strictly better, so ties keep the smaller k
best_k, best_accuracy = k, accuracy
# Only now touch the test seeds, once, with the chosen k and all of train.
correct = count_correct(test, train, best_k)
print(f"best_k {best_k}")
print(f"test_correct {correct}")
print(f"test_accuracy {correct / len(test):.6f}")
if __name__ == "__main__":
main()The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation wraps it in two loops:
one over the odd values of k, and one over the 5 folds. Slicing builds each
split: held_out is one block of 30 rows, and rest joins the slices
before and after it.
Python’s standard library has no cross-validation; scikit-learn’s
cross_val_score and KFold do this, but scikit-learn isn’t installed.
math.dist gives the distance, sorted is stable so equal distances keep
file order, and Counter tallies the votes.
-- 5-fold cross-validation for k-nearest neighbors, using only Ada's
-- standard library.
--
-- Splits the training seeds into 5 folds, scores each odd K from 1 to 15
-- by holding out one fold at a time, picks the K with the best average
-- accuracy, and then scores that K once on the untouched test seeds.
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
Folds : 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 point, 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; K : Positive)
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;
function Count_Correct (Points, Train : Vector; K : Positive)
return Natural
is
Correct : Natural := 0;
begin
for P of Points loop
if Classify (P, Train, K) = P.Variety then
Correct := Correct + 1;
end if;
end loop;
return Correct;
end Count_Correct;
function CV_Accuracy (Train : Vector; K : Positive) return Long_Float is
Size : constant Positive := Natural (Train.Length) / Folds;
Correct : Natural := 0;
begin
-- Fold F is rows (F - 1) * Size + 1 through F * Size. The rows are
-- already shuffled, so consecutive blocks make fair folds.
for F in 1 .. Folds loop
declare
Held_Out, Rest : Vector;
begin
-- Vectors have no slices, so we copy each row into one side.
for I in 1 .. Train.Last_Index loop
if I in (F - 1) * Size + 1 .. F * Size then
Held_Out.Append (Train (I));
else
Rest.Append (Train (I));
end if;
end loop;
Correct := Correct + Count_Correct (Held_Out, Rest, K);
end;
end loop;
return Long_Float (Correct) / Long_Float (Train.Length);
end CV_Accuracy;
File : File_Type;
Train, Test : Vector;
Best_K : Positive := 1;
Best_Accuracy : Long_Float := -1.0;
Correct : Natural;
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);
Put_Line ("train_count" & Train.Length'Image);
Put_Line ("test_count" & Test.Length'Image);
-- Ada's for loop has no step, so an Ada 2022 filter (when ...) keeps
-- only the odd K, which two varieties can't tie.
for K in 1 .. 15 when K mod 2 = 1 loop
declare
Accuracy : constant Long_Float := CV_Accuracy (Train, K);
begin
-- 'Image puts a space before a positive number, so Trim drops it.
Put ("cv_accuracy_k" & Trim (K'Image, Ada.Strings.Left) & " ");
Put (Accuracy, Fore => 1, Aft => 6, Exp => 0);
New_Line;
-- Strictly better, so ties keep the smaller K.
if Accuracy > Best_Accuracy then
Best_K := K;
Best_Accuracy := Accuracy;
end if;
end;
end loop;
-- Only now touch the test seeds, once, with the chosen K and all of
-- Train.
Correct := Count_Correct (Test, Train, Best_K);
Put_Line ("best_k" & Best_K'Image);
Put_Line ("test_correct" & Correct'Image);
Put ("test_accuracy ");
Put (Long_Float (Correct) / Long_Float (Test.Length),
Fore => 1, Aft => 6, Exp => 0);
New_Line;
end Main;The kNN classifier is the one from the k-nearest neighbors page, with K
passed in instead of fixed at 5. Ada’s for loop has no step, so the loop
over K uses an Ada 2022 filter, when K mod 2 = 1, to keep the odd values.
Ada.Containers.Vectors has no slices, so for each fold we walk the
training rows and append each one to the held-out vector or the rest,
using a membership test, I in A .. B, for the block.
Ada has no cross-validation or kNN. Generic_Array_Sort is a heapsort, so
our Nearer comparison breaks distance ties by row number, and a loop
counts the votes.
⍝ 5-fold cross-validation for k-nearest neighbors, from scratch in GNU APL.
⍝ Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
⍝ holding out one fold at a time, picks the k with the best average
⍝ accuracy, and then scores that k once on the untouched test 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 ¯
∇
FOLDS←5
KS←¯1+2×⍳8 ⍝ 1 3 5 … 15: odd k only, so no tied votes
⍝ 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
⍝ RP, RL, and K belong to CORRECT below. APL names are dynamically
⍝ scoped, so a function sees the locals of the one that called it.
D←(+/(RP-(⍴RP)⍴P)*2)*0.5 ⍝ distance to every reference seed
NEAR←RL[K↑⍋D] ⍝ ⍋ sorts stably: ties keep file order
KINDS←∪NEAR ⍝ ∪ is unique, in order of first appearance
VOTES←+/KINDS∘.≡NEAR ⍝ ∘.≡ compares every kind with every neighbor
WINNER←⊃KINDS[VOTES⍳⌈/VOTES] ⍝ the first kind with the most votes
∇
∇C←K CORRECT SETS;QP;QL;RP;RL
⍝ SETS holds query points, query labels, reference points, and reference
⍝ labels; this assigns all four at once. C counts correct query labels.
(QP QL RP RL)←SETS
C←+/(CLASSIFY¨⊂[2]QP)≡¨QL ⍝ ⊂[2] makes one item per row for ¨
∇
∇ACC←CV K;N;SIZE;F;FOLD;HELD
⍝ The average accuracy of K over the folds.
N←≢TL ⋄ SIZE←N÷FOLDS ⋄ FOLD←⌈(⍳N)÷SIZE ⍝ each row's fold: 1 1 … 5 5
ACC←0 ⋄ F←1
NEXT:
HELD←FOLD=F ⍝ a mask: 1 for the rows of fold F
⍝ ⌿ keeps the rows of a table where the mask is 1.
ACC←ACC+K CORRECT (HELD⌿TP)(HELD/TL)((~HELD)⌿TP)((~HELD)/TL)
F←F+1 ⋄ →(F≤FOLDS)/NEXT ⍝ jump back while folds remain
ACC←ACC÷N
∇
'train_count' SAY ≢TL
'test_count' SAY ≢QL
ACCS←CV¨KS ⍝ score every k at once
⍝ ⊂ encloses the prefix so ,¨ joins it to each k's text.
((⊂'cv_accuracy_k'),¨⍕¨KS) SAY6¨ACCS
⍝ ⍳ finds the first top accuracy, so a tie goes to the smaller k.
BEST←KS[ACCS⍳⌈/ACCS]
⍝ Only now touch the test seeds, once, with the chosen k and all of train.
TESTC←BEST CORRECT QP QL TP TL
'best_k' SAY BEST
'test_correct' SAY TESTC
'test_accuracy' SAY6 TESTC÷≢QL
)OFFThe classifier is the one from the k-nearest neighbors page, and each fold
is a mask. ⌈(⍳N)÷SIZE gives every training row its fold number, 1 1 … 5 5,
so HELD←FOLD=F marks fold F, HELD⌿TP keeps its rows, and ~HELD keeps
the other four folds. CV¨KS scores all eight values of k with one each.
One surprise: CLASSIFY never receives the reference seeds. APL names are
dynamically scoped, so it reads RP, RL, and K from the locals of
CORRECT, which called it. ⍳ finds the first top accuracy, so a tie goes
to the smaller k. There is no cross-validation built-in to avoid.
# 5-fold cross-validation for k-nearest neighbors, in POSIX awk.
#
# Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
# holding out one fold at a time, picks the k with the best average
# accuracy, and then scores that k once on the untouched test seeds. Rows
# are stored as they are read; the work happens in END.
BEGIN { FS = ","; FOLDS = 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,
# skipping rows lo to hi (the held-out fold; lo > hi skips nothing).
# Locals are declared as extra parameters, the awk idiom for local variables.
function classify(px, py, k, lo, hi, 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 < lo || i > hi) && !(i in used) && (best == 0 || dist[i] < dist[best]))
best = i
used[best] = 1
label = tlab[best]
votes[label]++
# Highest vote wins; with two varieties and odd k, no vote ties.
if (winner == "" || votes[label] > votes[winner])
winner = label
}
return winner
}
# Fold f (from 0) is rows f*size+1 to (f+1)*size. The rows are already
# shuffled, so consecutive blocks make fair folds. Nothing is copied: the
# held-out rows are classified against all others, skipped by index.
function cv_accuracy(k, size, f, lo, hi, i, correct) {
size = int(n_train / FOLDS)
correct = 0
for (f = 0; f < FOLDS; f++) {
lo = f * size + 1
hi = (f + 1) * size
for (i = lo; i <= hi; i++)
if (classify(tx[i], ty[i], k, lo, hi) == tlab[i]) correct++
}
return correct / n_train
}
END {
if (failed) exit 1
printf "train_count %d\n", n_train
printf "test_count %d\n", n_test
best_k = 0; best_accuracy = -1
for (k = 1; k <= 15; k += 2) { # odd k only
accuracy = cv_accuracy(k)
printf "cv_accuracy_k%d %.6f\n", k, accuracy
# Strictly better, so ties keep the smaller k.
if (accuracy > best_accuracy) { best_k = k; best_accuracy = accuracy }
}
# Only now touch the test seeds, once, with the chosen k and all of train.
for (t = 1; t <= n_test; t++)
if (classify(qx[t], qy[t], best_k, 1, 0) == qlab[t]) correct++
printf "best_k %d\n", best_k
printf "test_correct %d\n", correct
printf "test_accuracy %.6f\n", correct / n_test
}The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in and two more parameters, lo and hi, naming rows to skip. That
is how we build folds: awk can’t slice or copy an array in one step, so
nothing is copied. Each held-out seed is classified against every training
row outside lo to hi, and the final test run passes 1, 0, a range that
skips nothing.
POSIX awk has no sort, so classify still picks the nearest unused seed k
times, with a strict < that keeps the earlier row on equal distances. At
k = 15 that’s 15 scans of 150 rows per seed, and it still finishes quickly.
10 REM 5-fold cross-validation for k-nearest neighbors, in classic BASIC.
20 REM
30 REM Scores each odd K from 1 to 15 by holding out one fold of 30
40 REM training seeds at a time, picks the K with the best accuracy, and
50 REM then scores that K once on the untouched test seeds.
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 NK = 15 : REM the largest K tried
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(20), CR(20), FL$(20)
140 GOSUB 1000 : REM read the seeds into the two sets
150 PRINT "train_count"; NT
160 PRINT "test_count"; NQ
170 S = INT(NT / 5) : REM fold size; fold F holds rows F*S+1 to (F+1)*S
180 REM Each held-out seed finds its 15 nearest once. The K nearest are
190 REM the first K of those, so every K reuses the same list.
200 FOR H = 1 TO NT
210 HF = INT((H - 1) / S) : PL = TL(H) : PW = TW(H)
220 GOSUB 2000 : REM NB(1..NK), nearest first, from the other folds
230 FOR K = 1 TO NK STEP 2
240 GOSUB 3000 : REM vote among NB(1..K), winner in P$
250 IF P$ = TV$(H) THEN CR(K) = CR(K) + 1
260 NEXT K
270 NEXT H
280 BK = 0 : BA = -1
290 FOR K = 1 TO NK STEP 2
300 A = CR(K) / NT
310 PRINT "cv_accuracy_k"; MID$(STR$(K), 2); " ";
320 PRINT USING "#.######"; A
330 REM A strict > keeps the smaller K on a tie.
340 IF A > BA THEN BK = K : BA = A
350 NEXT K
360 REM Only now touch the test seeds, once, against all training seeds.
370 C = 0 : HF = -1
380 FOR T = 1 TO NQ
390 PL = QL(T) : PW = QW(T)
400 GOSUB 2000
410 K = BK
420 GOSUB 3000
430 IF P$ = QV$(T) THEN C = C + 1
440 NEXT T
450 PRINT "best_k"; BK
460 PRINT "test_correct"; C
470 PRINT "test_accuracy ";
480 PRINT USING "#.######"; C / NQ
490 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 The NK training seeds nearest (PL, PW), skipping fold HF.
2010 REM Seeds in the held-out fold start out marked as used in U.
2020 FOR J = 1 TO NT
2030 D(J) = SQR((PL - TL(J)) ^ 2 + (PW - TW(J)) ^ 2) : U(J) = 0
2040 IF INT((J - 1) / S) = HF THEN U(J) = 1
2050 NEXT J
2060 FOR M = 1 TO NK
2070 B = 0 : BD = 1E+30 : REM BD starts larger than any distance
2080 FOR J = 1 TO NT
2090 REM A strict < keeps the earlier row when two distances are equal.
2100 IF U(J) = 0 AND D(J) < BD THEN B = J : BD = D(J)
2110 NEXT J
2120 NB(M) = B : U(B) = 1
2130 NEXT M
2140 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 4020This builds on the BASIC kNN program, with the same parallel arrays and
selection scans with a strict <. A seed’s fold is INT((J - 1) / S),
where S is 30, and seeds in the held-out fold start out marked as used in
U, so the scans skip them. Test seeds pass HF = -1, a fold no row has.
Each held-out seed finds its 15 nearest only once. The k nearest are the
first k of those, so one FOR K = 1 TO NK STEP 2 loop votes for every k
from the same list. BASIC has no
sort or cross-validation to avoid; everything is written out.
/* 5-fold cross-validation for k-nearest neighbors, using only the C
* standard library.
*
* Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
* holding out one fold at a time, picks the k with the best average
* accuracy, and then scores that k once on the untouched test seeds. */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FOLDS 5
#define MAX_K 15
#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 set. */
struct neighbor {
double distance;
size_t index;
};
/* qsort isn't stable, so equal distances fall back to row 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, int k,
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;
}
static int count_correct(const struct seed *points, size_t n, const struct seeds *train,
int k, struct neighbor *scratch) {
int correct = 0;
for (size_t i = 0; i < n; i++)
if (strcmp(classify(&points[i], train, k, scratch), points[i].variety) == 0)
correct++;
return correct;
}
/* Fold f is rows f*size up to (f+1)*size. The rows are already shuffled, so
* consecutive blocks make fair folds. The held-out fold is just a pointer
* into train; the other rows are copied, in order, into the rest buffer. */
static double cv_accuracy(const struct seeds *train, int k, struct seeds *rest,
struct neighbor *scratch) {
size_t size = train->count / FOLDS;
int correct = 0;
for (size_t f = 0; f < FOLDS; f++) {
size_t start = f * size, end = start + size;
rest->count = 0;
for (size_t i = 0; i < train->count; i++)
if (i < start || i >= end) push(rest, train->items[i]);
correct += count_correct(&train->items[start], size, rest, k, scratch);
}
return (double)correct / train->count;
}
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}, rest = {0};
read_seeds(argv[1], &train, &test);
if (train.count < FOLDS * MAX_K || test.count == 0) { fprintf(stderr, "too few seeds\n"); return 1; }
struct neighbor *scratch = malloc(train.count * sizeof *scratch);
printf("train_count %zu\n", train.count);
printf("test_count %zu\n", test.count);
int best_k = 0;
double best_accuracy = -1.0;
for (int k = 1; k <= MAX_K; k += 2) { /* odd k only */
double accuracy = cv_accuracy(&train, k, &rest, scratch);
printf("cv_accuracy_k%d %.6f\n", k, accuracy);
if (accuracy > best_accuracy) { /* strictly better, so ties keep the smaller k */
best_k = k;
best_accuracy = accuracy;
}
}
/* Only now touch the test seeds, once, with the chosen k and all of train. */
int correct = count_correct(test.items, test.count, &train, best_k, scratch);
printf("best_k %d\n", best_k);
printf("test_correct %d\n", correct);
printf("test_accuracy %.6f\n", (double)correct / test.count);
free(scratch);
free(train.items);
free(test.items);
free(rest.items);
return 0;
}The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed by #define. Cross-validation adds two loops:
one over the odd values of k, and one over the 5 folds.
C has no slices, so the two sides of each split are built differently. The
held-out fold is a pointer to its first row plus a count of 30, with nothing
copied. The other 120 rows are copied, in file order, into a reusable
rest buffer. Because qsort breaks distance ties by row number, keeping
rest in file order is what keeps the earlier training seed. There is no
cross-validation in the standard library, so every step is written out.
// 5-fold cross-validation for k-nearest neighbors, using only the C++
// standard library.
//
// Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
// holding out one fold at a time, picks the k with the best average accuracy,
// and then scores that k once on the untouched test seeds.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <fstream>
#include <map>
#include <print>
#include <span>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
constexpr std::size_t FOLDS = 5;
constexpr std::size_t MAX_K = 15;
// 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);
}
}
// The training seeds are passed as pointers, so a fold's split copies no labels.
std::string classify(const Seed& point, std::vector<const Seed*> nearest, std::size_t k) {
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;
}
// A std::span is a view of part of a vector: a pointer and a length, no copy.
long count_correct(std::span<const Seed> points, const std::vector<const Seed*>& train,
std::size_t k) {
return std::ranges::count_if(points, [&](const Seed& seed) {
return classify(seed, train, k) == seed.variety;
});
}
// Fold f is rows f*size up to (f+1)*size. The rows are already shuffled, so
// consecutive blocks make fair folds.
double cv_accuracy(const std::vector<Seed>& train, std::size_t k) {
std::size_t size = train.size() / FOLDS;
long correct = 0;
for (std::size_t f = 0; f < FOLDS; f++) {
std::size_t start = f * size, end = start + size;
std::span<const Seed> held_out(train.begin() + start, size);
// Every other row, in file order, as a pointer.
std::vector<const Seed*> rest;
for (std::size_t i = 0; i < train.size(); i++) {
if (i < start || i >= end) {
rest.push_back(&train[i]);
}
}
correct += count_correct(held_out, rest, k);
}
return static_cast<double>(correct) / train.size();
}
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() < FOLDS * MAX_K || test.empty()) {
throw std::runtime_error("too few seeds");
}
std::println("train_count {}", train.size());
std::println("test_count {}", test.size());
std::size_t best_k = 0;
double best_accuracy = -1.0;
for (std::size_t k = 1; k <= MAX_K; k += 2) { // odd k only
double accuracy = cv_accuracy(train, k);
std::println("cv_accuracy_k{} {:.6f}", k, accuracy);
if (accuracy > best_accuracy) { // strictly better, so ties keep the smaller k
best_k = k;
best_accuracy = accuracy;
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
std::vector<const Seed*> all;
for (const Seed& seed : train) {
all.push_back(&seed);
}
long correct = count_correct(test, all, best_k);
std::println("best_k {}", best_k);
std::println("test_correct {}", correct);
std::println("test_accuracy {:.6f}", static_cast<double>(correct) / test.size());
}The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation adds two loops: one over
the odd values of k, and one over the 5 folds.
The held-out fold is a std::span, a view of 30 rows inside the training
vector, so nothing is copied. The other 120 rows go into a vector of
pointers, in file order, which std::stable_sort then sorts by distance, so
equal distances keep the earlier seed. The standard library has no
cross-validation, and none of the C++ machine learning libraries, such as
mlpack, is installed, so every step is written out.
*> 5-fold cross-validation for k-nearest neighbors, in COBOL.
*>
*> Scores each odd K from 1 to 15 by holding out one fold of 30
*> training seeds at a time, picks the K with the best accuracy,
*> and then scores that K once on the untouched test seeds.
*> Squared Euclidean distance ranks the neighbors in the same order
*> as distance, without a SQRT.
IDENTIFICATION DIVISION.
PROGRAM-ID. CROSS-VALIDATION.
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-FOLDS PIC 9 VALUE 5.
01 WS-MAX-K PIC 99 VALUE 15.
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).
10 WS-FOLD PIC 9.
*> Squared distance to the current seed, and whether this
*> seed is already picked or sits in the held-out fold.
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 seed being classified, and the fold it may not look at
*> (9 for a test seed, which matches no fold).
01 WS-QUERY-X1 PIC S9(9)V9(6).
01 WS-QUERY-X2 PIC S9(9)V9(6).
01 WS-QUERY-LABEL PIC X(40).
01 WS-HELD-FOLD PIC 9.
01 WS-FOLD-SIZE PIC 9(4).
*> The 15 nearest, closest first. The K nearest are the first K,
*> so one list serves every K.
01 WS-NEAREST-TABLE.
05 WS-NEAREST PIC 9(4) OCCURS 15 TIMES.
*> Correct held-out votes for each K, summed over the folds.
01 WS-CV-TABLE.
05 WS-CV-CORRECT PIC 9(4) OCCURS 15 TIMES.
*> The votes of the K nearest, one entry per distinct label.
01 WS-VOTE-COUNT PIC 99.
01 WS-VOTES.
05 WS-VOTE OCCURS 15 TIMES.
10 WS-VOTE-LABEL PIC X(40).
10 WS-VOTE-TALLY PIC 99.
01 I PIC 9(4).
01 T PIC 9(4).
01 K PIC 99.
01 N PIC 99.
01 V PIC 99.
01 WS-BEST PIC 9(4).
01 WS-BEST-K PIC 99 VALUE 0.
01 WS-BEST-ACCURACY PIC S9(3)V9(12) VALUE -1.
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
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)
*> Fold F (from 0) is the F+1st block of 30 rows. The fields are
*> whole numbers, so the division drops any fraction.
DIVIDE WS-TRAIN-COUNT BY WS-FOLDS GIVING WS-FOLD-SIZE
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-TRAIN-COUNT
COMPUTE WS-FOLD(I) = (I - 1) / WS-FOLD-SIZE
END-PERFORM
*> Each held-out seed finds its 15 nearest once, then every odd
*> K votes from the front of that list.
MOVE ZEROS TO WS-CV-TABLE
PERFORM VARYING T FROM 1 BY 1 UNTIL T > WS-TRAIN-COUNT
MOVE WS-TRAIN-X1(T) TO WS-QUERY-X1
MOVE WS-TRAIN-X2(T) TO WS-QUERY-X2
MOVE WS-TRAIN-LABEL(T) TO WS-QUERY-LABEL
MOVE WS-FOLD(T) TO WS-HELD-FOLD
PERFORM FIND-NEAREST
PERFORM VARYING K FROM 1 BY 2 UNTIL K > WS-MAX-K
PERFORM VOTE
IF WS-PREDICTED = WS-QUERY-LABEL
ADD 1 TO WS-CV-CORRECT(K)
END-IF
END-PERFORM
END-PERFORM
*> A strict ">" keeps the smaller K on a tie.
PERFORM VARYING K FROM 1 BY 2 UNTIL K > WS-MAX-K
COMPUTE WS-ACCURACY ROUNDED =
WS-CV-CORRECT(K) / WS-TRAIN-COUNT
COMPUTE WS-ACCURACY-OUT ROUNDED = WS-ACCURACY
MOVE K TO WS-COUNT-OUT
DISPLAY "cv_accuracy_k" FUNCTION TRIM(WS-COUNT-OUT) " "
FUNCTION TRIM(WS-ACCURACY-OUT)
IF WS-ACCURACY > WS-BEST-ACCURACY
MOVE K TO WS-BEST-K
MOVE WS-ACCURACY TO WS-BEST-ACCURACY
END-IF
END-PERFORM
*> Only now touch the test seeds, once, with all training seeds.
MOVE 9 TO WS-HELD-FOLD
MOVE WS-BEST-K TO K
PERFORM VARYING T FROM 1 BY 1 UNTIL T > WS-TEST-COUNT
MOVE WS-TEST-X1(T) TO WS-QUERY-X1
MOVE WS-TEST-X2(T) TO WS-QUERY-X2
PERFORM FIND-NEAREST
PERFORM VOTE
IF WS-PREDICTED = WS-TEST-LABEL(T)
ADD 1 TO WS-CORRECT
END-IF
END-PERFORM
MOVE WS-BEST-K TO WS-COUNT-OUT
DISPLAY "best_k " FUNCTION TRIM(WS-COUNT-OUT)
MOVE WS-CORRECT TO WS-COUNT-OUT
DISPLAY "test_correct " FUNCTION TRIM(WS-COUNT-OUT)
COMPUTE WS-ACCURACY ROUNDED = WS-CORRECT / WS-TEST-COUNT
COMPUTE WS-ACCURACY-OUT ROUNDED = WS-ACCURACY
DISPLAY "test_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.
*> Fill WS-NEAREST with the 15 training seeds nearest the query,
*> leaving out the held-out fold by marking it used up front.
FIND-NEAREST.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-TRAIN-COUNT
COMPUTE WS-DIST(I) =
(WS-QUERY-X1 - WS-TRAIN-X1(I)) ** 2
+ (WS-QUERY-X2 - WS-TRAIN-X2(I)) ** 2
IF WS-FOLD(I) = WS-HELD-FOLD
MOVE "Y" TO WS-USED(I)
ELSE
MOVE "N" TO WS-USED(I)
END-IF
END-PERFORM
*> Pick the nearest unused seed 15 times. A strict "<" keeps the
*> earlier training seed when two distances are equal.
PERFORM VARYING N FROM 1 BY 1 UNTIL N > WS-MAX-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)
MOVE WS-BEST TO WS-NEAREST(N)
END-PERFORM.
*> Label the query by majority vote of WS-NEAREST(1) to (K).
*> Labels are in the order first seen, so a strict ">" gives a
*> tied vote to the label met first.
VOTE.
MOVE 0 TO WS-VOTE-COUNT
PERFORM VARYING N FROM 1 BY 1 UNTIL N > K
MOVE WS-NEAREST(N) TO WS-BEST
PERFORM ADD-VOTE
END-PERFORM
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).This builds on the COBOL kNN program, so distances are exact fixed-point decimals. That matters here: held-out seed 77 has two neighbors, training seeds 10 and 146, at a squared distance of exactly 0.0325, tied for seventh. COBOL keeps seed 10, by file order, where double-precision floating point puts 146 slightly nearer. The vote comes out the same either way.
Each seed’s WS-FOLD is its row number less 1, divided by 30 into a whole
number. FIND-NEAREST marks the held-out fold as used, then picks the 15
nearest once, and VOTE reads the first k for every odd k. A test seed
uses fold 9, which no row has. There’s no cross-validation built-in to
skip.
;;;; 5-fold cross-validation for k-nearest neighbors, using only standard
;;;; Common Lisp.
;;;;
;;;; Splits the training seeds into 5 folds, scores each odd K from 1 to 15
;;;; by holding out one fold at a time, picks the K with the best average
;;;; accuracy, and then scores that K once on the untouched test seeds.
(defparameter *folds* 5)
;; Odd k only, so two varieties can't tie.
(defparameter *ks* (loop for k from 1 to 15 by 2 collect k))
;; 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 k)
"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))))))
(defun count-correct (points train k)
"How many of POINTS get their own variety back from TRAIN."
(count-if (lambda (s) (string= (classify s train k) (seed-variety s)))
points))
(defun cv-accuracy (train k)
"The share of TRAIN classified correctly when each fold is held out."
;; Fold F is rows F*SIZE up to (F+1)*SIZE. The rows are already shuffled,
;; so consecutive blocks make fair folds. subseq copies a stretch of a
;; list; append joins the stretches before and after the fold.
(let ((size (floor (length train) *folds*)))
(/ (loop for f below *folds*
for start = (* f size)
for end = (+ start size)
sum (count-correct (subseq train start end)
(append (subseq train 0 start)
(subseq train end))
k))
(float (length train) 1d0))))
;; 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))
(best-k nil)
(best-accuracy -1))
;; ~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))
(dolist (k *ks*)
(let ((accuracy (cv-accuracy train k)))
(format t "cv_accuracy_k~d ~,6f~%" k accuracy)
;; Strictly better only, so ties keep the smaller k.
(when (> accuracy best-accuracy)
(setf best-k k
best-accuracy accuracy))))
;; Only now touch the test seeds, once, with the chosen k and all of train.
(let ((correct (count-correct test train best-k)))
(format t "best_k ~d~%" best-k)
(format t "test_correct ~d~%" correct)
;; (/ 47 50) would be the exact fraction 47/50; dividing by a double
;; gives a double.
(format t "test_accuracy ~,6f~%" (/ correct (float (length test) 1d0)))))The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. For each fold, subseq copies out the 30
held-out rows, and append joins the stretches before and after them into
that round’s training set. One loop walks the folds and sums the correct
counts.
(floor 150 5) gives the fold size, 30. Dividing by a double, not by the
integer 150, keeps the accuracy from becoming an exact fraction such as
71/75. Only a strictly larger accuracy replaces the leader, so ties keep
the smaller k. Common Lisp has no cross-validation or kNN function.
# 5-fold cross-validation for k-nearest neighbors, using only Elixir's
# standard library.
#
# Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
# holding out one fold at a time, picks the k with the best average
# accuracy, and then scores that k once on the untouched test seeds.
defmodule CrossValidation do
@folds 5
# Odd k only, so two varieties can't tie. 1..15//2 is a range with step 2.
@ks 1..15//2
def ks, do: @ks
# 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, k) 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, k) do
train |> nearest(point, k) |> Enum.map(&elem(&1, 1)) |> majority()
end
def count_correct(points, train, k) do
Enum.count(points, fn {point, variety} -> classify(train, point, k) == variety end)
end
# Fold f is rows f*size up to (f+1)*size. The rows are already shuffled,
# so consecutive blocks make fair folds. Enum.chunk_every cuts the list
# into blocks of size rows; the rest is every other block, joined.
def cv_accuracy(train, k) do
size = div(length(train), @folds)
blocks = Enum.chunk_every(train, size)
correct =
for f <- 0..(@folds - 1) do
held_out = Enum.at(blocks, f)
rest = blocks |> List.delete_at(f) |> Enum.concat()
count_correct(held_out, rest, k)
end
Enum.sum(correct) / length(train)
end
end
[path] = System.argv()
# split_with returns {rows that pass the test, the rest}.
{train, test} =
path
|> CrossValidation.read_rows()
|> Enum.split_with(&(&1["split"] == "train"))
train = Enum.map(train, &CrossValidation.seed/1)
test = Enum.map(test, &CrossValidation.seed/1)
format = &:erlang.float_to_binary(&1, decimals: 6)
IO.puts("train_count #{length(train)}")
IO.puts("test_count #{length(test)}")
# A strictly better accuracy replaces the leader, so ties keep the smaller k.
{best_k, _} =
Enum.reduce(CrossValidation.ks(), {nil, -1.0}, fn k, {best_k, best} ->
accuracy = CrossValidation.cv_accuracy(train, k)
IO.puts("cv_accuracy_k#{k} #{format.(accuracy)}")
if accuracy > best, do: {k, accuracy}, else: {best_k, best}
end)
# Only now touch the test seeds, once, with the chosen k and all of train.
correct = CrossValidation.count_correct(test, train, best_k)
IO.puts("best_k #{best_k}")
IO.puts("test_correct #{correct}")
IO.puts("test_accuracy #{format.(correct / length(test))}")The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. Enum.chunk_every cuts the 150 training
seeds into five blocks of 30. For each fold, Enum.at picks the held-out
block, and List.delete_at drops it so Enum.concat can join the other
four.
The values of k come from the range 1..15//2, where //2 is the step.
Enum.reduce prints each accuracy and replaces the leader only on a
strictly larger score, so ties keep the smaller k. Elixir has no
cross-validation, and Hex packages such as Nx aren’t installed.
! 5-fold cross-validation for k-nearest neighbors, using only standard
! Fortran.
!
! Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
! holding out one fold at a time, picks the k with the best average accuracy,
! and then scores that k once on the untouched test seeds.
program cross_validation
implicit none
integer, parameter :: dp = kind(1.0d0) ! double precision
integer, parameter :: folds = 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 :: k, best_k, correct
real(dp) :: accuracy, best_accuracy
character(len=20) :: name
call read_seeds(train, test)
print "(a, 1x, i0)", "train_count", size(train)
print "(a, 1x, i0)", "test_count", size(test)
best_accuracy = -1
do k = 1, 15, 2 ! odd k only, so two varieties can't tie
accuracy = cv_accuracy(k)
write(name, "(a, i0)") "cv_accuracy_k", k ! build the label as text
call say(trim(name), accuracy)
if (accuracy > best_accuracy) then ! strictly better: ties keep smaller k
best_k = k
best_accuracy = accuracy
end if
end do
! Only now touch the test seeds, once, with the chosen k and all of train.
correct = count_correct(test, train, best_k)
print "(a, 1x, i0)", "best_k", best_k
print "(a, 1x, i0)", "test_correct", correct
call say("test_accuracy", real(correct, dp) / size(test))
contains
real(dp) function cv_accuracy(k)
integer, intent(in) :: k
integer :: f, fold_size, first, last, correct
! Fold f is rows first to last, one block of fold_size. The rows are
! already shuffled, so consecutive blocks make fair folds.
fold_size = size(train) / folds
correct = 0
do f = 1, folds
first = (f - 1) * fold_size + 1
last = f * fold_size
! train(first:last) is an array section, the held-out fold. The array
! constructor [ ... ] joins the sections before and after it into the
! other four folds; an empty section such as train(1:0) adds nothing.
correct = correct + count_correct(train(first:last), &
[train(:first - 1), train(last + 1:)], k)
end do
cv_accuracy = real(correct, dp) / size(train)
end function cv_accuracy
! How many of points the k nearest of reference seeds label correctly.
integer function count_correct(points, reference, k)
type(seed), intent(in) :: points(:), reference(:)
integer, intent(in) :: k
integer :: i
count_correct = 0
do i = 1, size(points)
if (classify(points(i)%point, reference, k) == points(i)%variety) &
count_correct = count_correct + 1
end do
end function count_correct
function classify(point, reference, k) result(variety)
real(dp), intent(in) :: point(2)
type(seed), intent(in) :: reference(:)
integer, intent(in) :: k
character(len=16) :: variety
character(len=16) :: nearest(k)
real(dp) :: distance(size(reference))
logical :: taken(size(reference))
integer :: votes(k), i, j
! norm2 is the Euclidean length of a vector, so this is the distance.
do i = 1, size(reference)
distance(i) = norm2(point - reference(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) = reference(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 cross_validationThe classifier from the k-nearest neighbors page now takes the reference
seeds and k as arguments. Each fold comes from array sections:
train(first:last) is the held-out block of 30, and the array constructor
[ ... ] joins train(:first - 1) and train(last + 1:), the rows before
and after it, into a new array of 120. For the first fold, train(:0) is an empty
section, so nothing special is needed at the edges.
Fortran has no sort, so minloc with a mask still picks the nearest seeds
one at a time, and its first-of-equals rule keeps file order on ties.
Labels such as cv_accuracy_k7 are built with an internal write.
// 5-fold cross-validation for k-nearest neighbors, using only the standard
// library.
//
// Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
// holding out one fold at a time, picks the k with the best average accuracy,
// and then scores that k once on the untouched test seeds.
package main
import (
"cmp"
"encoding/csv"
"fmt"
"math"
"os"
"slices"
"strconv"
)
const folds = 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, k int) 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 countCorrect(points, train []seed, k int) int {
correct := 0
for _, s := range points {
if classify(s.features, train, k) == s.label {
correct++
}
}
return correct
}
// Fold f is rows f*size up to (f+1)*size. The rows are already shuffled, so
// consecutive blocks make fair folds.
func cvAccuracy(train []seed, k int) float64 {
size := len(train) / folds
correct := 0
for f := range folds {
heldOut := train[f*size : (f+1)*size]
// slices.Concat copies into a new slice. append(train[:f*size], ...)
// would write over train's own rows, since the two share memory.
rest := slices.Concat(train[:f*size], train[(f+1)*size:])
correct += countCorrect(heldOut, rest, k)
}
return float64(correct) / float64(len(train))
}
func main() {
train, test, err := read(os.Args[1])
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
fmt.Printf("train_count %d\n", len(train))
fmt.Printf("test_count %d\n", len(test))
bestK, bestAccuracy := 0, -1.0
for k := 1; k <= 15; k += 2 { // odd k only
accuracy := cvAccuracy(train, k)
fmt.Printf("cv_accuracy_k%d %.6f\n", k, accuracy)
if accuracy > bestAccuracy { // strictly better, so ties keep the smaller k
bestK, bestAccuracy = k, accuracy
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
correct := countCorrect(test, train, bestK)
fmt.Printf("best_k %d\n", bestK)
fmt.Printf("test_correct %d\n", correct)
fmt.Printf("test_accuracy %.6f\n", float64(correct)/float64(len(test)))
}The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation adds two loops: one over
the odd values of k, and one over the 5 folds.
Go slices make the held-out fold free: train[a:b] is a view of 30 rows,
not a copy. The other 120 rows need care. append(train[:a], ...) looks
right, but it writes into the array train shares, so it overwrites the
fold being tested. On this data that mistake reports 100% accuracy for k = 1.
slices.Concat copies into a new slice instead. The standard library has no
cross-validation, so every step is written out.
-- 5-fold cross-validation for k-nearest neighbors, using only Haskell's
-- base library.
--
-- Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
-- holding out one fold at a time, picks the k with the best average
-- accuracy, and then scores that k once on the untouched test seeds.
import Data.List (elemIndex, nub, sortOn)
import System.Environment (getArgs)
import Text.Printf (printf)
folds :: Int
folds = 5
-- Odd k only, so two varieties can't tie.
ks :: [Int]
ks = [1, 3 .. 15]
-- 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 :: Int -> [Seed] -> (Double, Double) -> [Seed]
nearest k 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 :: Int -> [Seed] -> (Double, Double) -> String
classify k train point = majority [label | (_, label) <- nearest k train point]
countCorrect :: Int -> [Seed] -> [Seed] -> Int
countCorrect k train points =
length [() | (point, label) <- points, classify k train point == label]
-- Fold f is rows f*size up to (f+1)*size. The rows are already shuffled, so
-- consecutive blocks make fair folds. splitAt cuts a list in two at a
-- position; cutting the second half again gives the fold and what follows.
cvAccuracy :: [Seed] -> Int -> Double
cvAccuracy train k = fromIntegral (sum (map foldCorrect [0 .. folds - 1])) / fromIntegral (length train)
where
size = length train `div` folds
foldCorrect f =
let (before, from) = splitAt (f * size) train
(heldOut, after) = splitAt size from
in countCorrect k (before ++ after) heldOut
-- The k with the highest accuracy. foldl1 walks left to right and > is
-- strict, so a tie keeps the smaller k.
bestK :: [(Int, Double)] -> Int
bestK scores = fst (foldl1 pick scores)
where
pick best candidate = if snd candidate > snd best then candidate else best
main :: IO ()
main = do
[path] <- getArgs
text <- readFile path
let seeds = readSeeds text
train = [seed | ("train", seed) <- seeds]
test = [seed | ("test", seed) <- seeds]
scores = [(k, cvAccuracy train k) | k <- ks]
chosen = bestK scores
-- Only now touch the test seeds, once, with the chosen k and all of train.
correct = countCorrect chosen train test
printf "train_count %d\n" (length train)
printf "test_count %d\n" (length test)
mapM_ (\(k, accuracy) -> printf "cv_accuracy_k%d %.6f\n" k accuracy) scores
printf "best_k %d\n" chosen
printf "test_correct %d\n" correct
printf "test_accuracy %.6f\n" (fromIntegral correct / fromIntegral (length test) :: Double)The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. Each fold comes from two calls to
splitAt: the first cuts off the rows before the fold, and the second cuts
the 30 held-out rows from the rows after them, so before ++ after is that
round’s training set.
Picking the best k reuses the vote’s trick. foldl1 with a strict >
keeps the earlier, smaller k on a tie, where maximumBy would return the
last. Haskell’s base library has no cross-validation or kNN function, so
both loops are written out.
// 5-fold cross-validation for k-nearest neighbors, using only the Java
// standard library.
//
// Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
// holding out one fold at a time, picks the k with the best average
// accuracy, and then scores that k once on the untouched test seeds.
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 FOLDS = 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, int k) {
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;
}
static int countCorrect(List<Seed> points, List<Seed> train, int k) {
int correct = 0;
for (Seed seed : points) {
// Strings are compared with equals; == would compare objects.
if (classify(seed, train, k).equals(seed.variety())) {
correct++;
}
}
return correct;
}
static double cvAccuracy(List<Seed> train, int k) {
// Fold f is rows f*size up to (f+1)*size. The rows are already
// shuffled, so consecutive blocks make fair folds.
int size = train.size() / FOLDS;
int correct = 0;
for (int f = 0; f < FOLDS; f++) {
int start = f * size, end = (f + 1) * size;
// subList is a view of train's rows, not a copy; rest is a new
// list that copies the rows before and after the held-out block.
List<Seed> heldOut = train.subList(start, end);
List<Seed> rest = new ArrayList<>(train.subList(0, start));
rest.addAll(train.subList(end, train.size()));
correct += countCorrect(heldOut, rest, k);
}
return (double) correct / train.size();
}
// 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]);
(splits[i].equals("train") ? train : test).add(seed);
}
Locale root = Locale.ROOT;
System.out.printf(root, "train_count %d%n", train.size());
System.out.printf(root, "test_count %d%n", test.size());
int bestK = 0;
double bestAccuracy = -1.0;
for (int k = 1; k <= 15; k += 2) { // odd k only, so two varieties can't tie
double accuracy = cvAccuracy(train, k);
System.out.printf(root, "cv_accuracy_k%d %.6f%n", k, accuracy);
if (accuracy > bestAccuracy) { // strictly better, so ties keep the smaller k
bestK = k;
bestAccuracy = accuracy;
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
int correct = countCorrect(test, train, bestK);
System.out.printf(root, "best_k %d%n", bestK);
System.out.printf(root, "test_correct %d%n", correct);
System.out.printf(root, "test_accuracy %.6f%n", (double) correct / test.size());
}
}The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation wraps it in two loops,
one over the odd values of k and one over the 5 folds. subList builds
each split: it returns a view of the training list, not a copy, so the
held-out block costs nothing, and the rest is a new ArrayList of the rows
before the block plus addAll of the rows after it.
Java’s standard library has no cross-validation; Weka’s crossValidateModel
does this, but Weka isn’t installed. List.sort is stable, so equal
distances keep file order, and groupingBy counts the votes.
// 5-fold cross-validation for k-nearest neighbors, using only Node's built-in
// modules. Scores each odd k from 1 to 15 by holding out one fold of the
// training seeds at a time, picks the best k, and then scores that k once on
// the untouched test seeds.
import { readFileSync } from "node:fs";
const FOLDS = 5;
const KS = [1, 3, 5, 7, 9, 11, 13, 15]; // odd k only, so two varieties can't tie
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, k) {
// 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;
}
function countCorrect(points, train, k) {
return points.filter((seed) => classify(seed.features, train, k) === seed.label).length;
}
function cvAccuracy(train, k) {
// Fold f is rows f * size up to (f + 1) * size. The rows are already
// shuffled, so consecutive blocks make fair folds. slice(start, end) copies
// rows start to end - 1; with one argument it runs to the end.
const size = Math.floor(train.length / FOLDS);
let correct = 0;
for (let f = 0; f < FOLDS; f++) {
const heldOut = train.slice(f * size, (f + 1) * size);
const rest = [...train.slice(0, f * size), ...train.slice((f + 1) * size)];
correct += countCorrect(heldOut, rest, k);
}
return correct / train.length;
}
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");
console.log(`train_count ${train.length}`);
console.log(`test_count ${test.length}`);
let bestK = null;
let bestAccuracy = -1;
for (const k of KS) {
const accuracy = cvAccuracy(train, k);
console.log(`cv_accuracy_k${k} ${accuracy.toFixed(6)}`);
// Strictly better, so ties keep the smaller k.
if (accuracy > bestAccuracy) [bestK, bestAccuracy] = [k, accuracy];
}
// Only now touch the test seeds, once, with the chosen k and all of train.
const correct = countCorrect(test, train, bestK);
console.log(`best_k ${bestK}`);
console.log(`test_correct ${correct}`);
console.log(`test_accuracy ${(correct / test.length).toFixed(6)}`);The classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. slice(start, end) copies one block of 30
rows for the held-out fold, and rest spreads the slices before and after
it into a new array with [...a, ...b]. Neither call changes train.
Node’s built-in modules have no cross-validation or kNN, and npm is removed
from this image, so no package could add one. toSorted is stable, so equal
distances keep file order with no index tie-breaker, and a Map counts the
votes.
# 5-fold cross-validation for k-nearest neighbors, using only Base Julia.
#
# Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
# holding out one fold at a time, picks the k with the best average
# accuracy, and then scores that k once on the untouched test seeds.
using Printf
const FOLDS = 5
const KS = 1:2:15 # odd k only, so two varieties can't tie
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, k)
# 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
best = maximum(values(votes))
return first(seed.variety for seed in nearest if votes[seed.variety] == best)
end
count_correct(points, train, k) =
count(seed -> classify(seed.point, train, k) == seed.variety, points)
function cv_accuracy(train, k)
# Fold f (from 0) is rows f*size+1 to (f+1)*size; ranges include both
# ends. The rows are already shuffled, so consecutive blocks make fair
# folds. vcat joins the rows before and after the held-out block.
size = length(train) ÷ FOLDS
correct = 0
for f in 0:FOLDS-1
fold = f*size+1:(f+1)*size
held_out = train[fold]
rest = vcat(train[1:first(fold)-1], train[last(fold)+1:end])
correct += count_correct(held_out, rest, k)
end
return correct / length(train)
end
function main(path)
train, test = read_seeds(path)
println("train_count $(length(train))")
println("test_count $(length(test))")
best_k, best_accuracy = 0, -1.0
for k in KS
accuracy = cv_accuracy(train, k)
@printf("cv_accuracy_k%d %.6f\n", k, accuracy)
if accuracy > best_accuracy # strictly better, so ties keep the smaller k
best_k, best_accuracy = k, accuracy
end
end
# Only now touch the test seeds, once, with the chosen k and all of train.
correct = count_correct(test, train, best_k)
println("best_k $best_k")
println("test_correct $correct")
@printf("test_accuracy %.6f\n", correct / length(test))
end
main(ARGS[1])The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
1:2:15, and one over the 5 folds. Each fold is a range such as 31:60,
which includes both ends, and train[fold] copies those seeds into a new
array. vcat joins the seeds before and after the held-out block.
Julia’s MLJ package has cross-validation built in, but it isn’t installed.
The sort is stable, so equal distances keep file order, and a Dict counts
the votes, with ties settled by walking the nearest seeds in order.
-- 5-fold cross-validation for k-nearest neighbors, using only Lua's standard
-- library.
--
-- Scores each odd k from 1 to 15 by holding out one fold of the training
-- seeds at a time, picks the best k, and then scores that k once on the
-- untouched test seeds.
local FOLDS = 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, k)
-- 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 function count_correct(points, train, k)
local correct = 0
for _, seed in ipairs(points) do
if classify(seed, train, k) == seed.label then correct = correct + 1 end
end
return correct
end
local function cv_accuracy(train, k)
-- Fold f (1 to FOLDS) is rows first to last. The rows are already
-- shuffled, so consecutive blocks make fair folds. Lua has no slicing,
-- so one pass over the row numbers sends each seed to one side, in order.
local size = #train // FOLDS
local correct = 0
for f = 1, FOLDS do
local first, last = (f - 1) * size + 1, f * size
local held_out, rest = {}, {}
for row, seed in ipairs(train) do
local list = (row >= first and row <= last) and held_out or rest
list[#list + 1] = seed
end
correct = correct + count_correct(held_out, rest, k)
end
return correct / #train
end
local train, test = read_seeds(arg[1])
print("train_count " .. #train)
print("test_count " .. #test)
local best_k, best_accuracy = nil, -1
for k = 1, 15, 2 do -- odd k only, so two varieties can't tie
local accuracy = cv_accuracy(train, k)
print(string.format("cv_accuracy_k%d %.6f", k, accuracy))
-- Strictly better, so ties keep the smaller k.
if accuracy > best_accuracy then best_k, best_accuracy = k, accuracy end
end
-- Only now touch the test seeds, once, with the chosen k and all of train.
local correct = count_correct(test, train, best_k)
print("best_k " .. best_k)
print("test_correct " .. correct)
print(string.format("test_accuracy %.6f", correct / #test))The classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. Lua has no slicing, so we build each split
by filtering on row number. One pass with ipairs sends rows first to
last to held_out and the rest to rest, which keeps file order on both
sides.
Fold bounds use //, which divides and rounds down, and they start at 1
because Lua arrays do. Lua has no cross-validation, kNN, or counter type,
and table.sort isn’t stable, so its comparison breaks distance ties by
row number.
(* 5-fold cross-validation for k-nearest neighbors, using only OCaml's
standard library.
Splits the training seeds into 5 folds, scores each odd k from 1 to 15
by holding out one fold at a time, picks the k with the best average
accuracy, and then scores that k once on the untouched test seeds. *)
let folds = 5
(* Odd k only, so two varieties can't tie. *)
let ks = List.init 8 (fun i -> (2 * i) + 1)
(* 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 k 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 k train point =
majority (List.map (fun s -> s.variety) (nearest k train point))
let count_correct k train points =
List.length (List.filter (fun s -> classify k train s = s.variety) points)
(* Fold f is rows f*size up to (f+1)*size. The rows are already shuffled,
so consecutive blocks make fair folds. List.mapi numbers the rows, and
List.partition splits them into the fold (i / size = f) and the rest. *)
let cv_accuracy train k =
let size = List.length train / folds in
let indexed = List.mapi (fun i s -> (i, s)) train in
let correct =
List.init folds (fun f ->
let held_out, rest =
List.partition (fun (i, _) -> i / size = f) indexed
in
count_correct k (List.map snd rest) (List.map snd held_out))
in
float_of_int (List.fold_left ( + ) 0 correct)
/. float_of_int (List.length train)
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
Printf.printf "train_count %d\n" (List.length train);
Printf.printf "test_count %d\n" (List.length test);
(* A strictly better accuracy replaces the leader, so ties keep the
smaller k. *)
let best_k, _ =
List.fold_left
(fun (bk, ba) k ->
let accuracy = cv_accuracy train k in
Printf.printf "cv_accuracy_k%d %.6f\n" k accuracy;
if accuracy > ba then (k, accuracy) else (bk, ba))
(0, -1.) ks
in
(* Only now touch the test seeds, once, with the chosen k and all of
train. *)
let correct = count_correct best_k train test in
Printf.printf "best_k %d\n" best_k;
Printf.printf "test_correct %d\n" correct;
Printf.printf "test_accuracy %.6f\n"
(float_of_int correct /. float_of_int (List.length test))The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. To build the folds, List.mapi numbers
the training rows, and List.partition splits them on i / size = f: the
30 rows of fold f are held out, and the other 120 train. Integer /
rounds down for positive numbers, so rows 0 to 29 are fold 0.
The best k comes from a List.fold_left that prints each accuracy as it
goes and replaces the leader only on a strictly larger score, so ties keep
the smaller k. OCaml’s standard library has no cross-validation or kNN.
% 5-fold cross-validation for k-nearest neighbors, using only core GNU Octave.
%
% Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
% holding out one fold at a time, picks the k with the best average accuracy,
% and then scores that k once on the untouched test seeds. Core Octave has no
% cross-validation or 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
% How many of the query seeds (q_len, q_wid, q_variety) the K nearest
% training seeds (t_len, t_wid, t_variety) label correctly.
function correct = count_correct(q_len, q_wid, q_variety, t_len, t_wid, t_variety, K)
correct = 0;
for t = 1:numel(q_len)
% Distances from this seed to every training seed at once.
d = sqrt((t_len - q_len(t)) .^ 2 + (t_wid - q_wid(t)) .^ 2);
% sort is stable, so equal distances keep file order.
[~, order] = sort(d);
nearest = t_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}, q_variety{t});
end
end
FOLDS = 5;
KS = 1:2:15; % odd k only, so two varieties can't tie
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);
n = numel(train_len);
fold_size = n / FOLDS;
printf("train_count %d\n", n);
printf("test_count %d\n", numel(test_len));
best_k = 0;
best_accuracy = -1;
for K = KS
correct = 0;
for f = 1:FOLDS
% A logical mask marks fold f, one block of fold_size rows. The rows are
% already shuffled, so consecutive blocks make fair folds.
held = false(n, 1);
held((f - 1) * fold_size + 1 : f * fold_size) = true;
correct = correct + count_correct( ...
train_len(held), train_wid(held), train_variety(held), ...
train_len(~held), train_wid(~held), train_variety(~held), K);
end
accuracy = correct / n;
printf("cv_accuracy_k%d %.6f\n", K, accuracy);
if accuracy > best_accuracy % strictly better, so ties keep the smaller k
best_k = K;
best_accuracy = accuracy;
end
end
% Only now touch the test seeds, once, with the chosen k and all of train.
correct = count_correct(test_len, test_wid, test_variety, ...
train_len, train_wid, train_variety, best_k);
printf("best_k %d\n", best_k);
printf("test_correct %d\n", correct);
printf("test_accuracy %.6f\n", correct / numel(test_len));The classifier from the k-nearest neighbors page becomes a function,
count_correct, that takes the query seeds, the training seeds, and K.
Each fold is a logical mask: held = false(n, 1) starts with all 150 rows
unmarked, and setting one block of 30 to true marks the fold. Indexing a
column with held picks the held-out rows, and ~held picks the other
120. Indexing returns a copy, so the training columns never change.
Core Octave has no cvpartition, crossval, or fitcknn. Those come with
the Octave Forge statistics package, which isn’t installed.
{ 5-fold cross-validation for k-nearest neighbors, using only Free Pascal's
run-time library.
Splits the training seeds into 5 folds, scores each odd K from 1 to 15 by
holding out one fold at a time, picks the K with the best average
accuracy, and then scores that K once on the untouched test seeds. }
program CrossValidation;
{$mode objfpc}{$H+} // 32-bit Integer, and strings longer than 255 characters
uses
SysUtils, Generics.Collections, Generics.Defaults;
const
Folds = 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 point, and its row in Train.
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; K: Integer): 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;
function CountCorrect(const Points, Train: TSeedArray; K: Integer): Integer;
var
I: Integer;
begin
Result := 0;
for I := 0 to High(Points) do
if Classify(Points[I], Train, K) = Points[I].Variety then
Inc(Result);
end;
function CVAccuracy(const Train: TSeedArray; K: Integer): Double;
var
Size, F, Start, Stop, Correct: Integer;
begin
// Fold F is rows F*Size up to (F+1)*Size. The rows are already shuffled,
// so consecutive blocks make fair folds.
Size := Length(Train) div Folds;
Correct := 0;
for F := 0 to Folds - 1 do
begin
Start := F * Size;
Stop := (F + 1) * Size;
// Copy(A, From, Count) copies Count elements of a dynamic array, and
// Concat joins the rows before and after the held-out block.
Correct := Correct + CountCorrect(Copy(Train, Start, Size),
Concat(Copy(Train, 0, Start), Copy(Train, Stop, Length(Train) - Stop)), K);
end;
Result := Correct / Length(Train);
end;
var
Lengths, Widths, Varieties, Splits: TStringArray;
Train, Test: TSeedArray;
Seed: TSeed;
I, K, BestK, Correct: Integer;
Accuracy, BestAccuracy: Double;
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;
WriteLn('train_count ', Length(Train));
WriteLn('test_count ', Length(Test));
BestK := 0;
BestAccuracy := -1.0;
// Pascal's for loop only steps by one, so I counts 0 to 7 and K is the
// odd number 2I + 1. Odd K only, so two varieties can't tie.
for I := 0 to 7 do
begin
K := 2 * I + 1;
Accuracy := CVAccuracy(Train, K);
WriteLn('cv_accuracy_k', K, ' ', Accuracy:0:6);
if Accuracy > BestAccuracy then // strictly better, so ties keep the smaller K
begin
BestK := K;
BestAccuracy := Accuracy;
end;
end;
// Only now touch the test seeds, once, with the chosen K and all of Train.
Correct := CountCorrect(Test, Train, BestK);
WriteLn('best_k ', BestK);
WriteLn('test_correct ', Correct);
WriteLn('test_accuracy ', Correct / Length(Test):0:6);
end.The kNN classifier is the one from the k-nearest neighbors page, with K
passed in instead of fixed at 5. Pascal’s for loop only steps by one, so
we count from 0 to 7 and take K as 2I + 1. For each fold,
Copy(Train, Start, Size) copies the held-out block of a dynamic array,
and Concat joins copies of the rows before and after it into the rest.
Free Pascal has no cross-validation or kNN. TArrayHelper.Sort isn’t
stable, so our comparison breaks distance ties by row number, and a
loop counts the votes, since TDictionary won’t compile with warnings as
errors.
# 5-fold cross-validation for k-nearest neighbors, using only Perl and its
# core modules.
#
# Scores each odd k from 1 to 15 by holding out one fold of the training
# seeds at a time, picks the best k, and then scores that k once on the
# untouched test seeds.
use strict;
use warnings;
my $FOLDS = 5;
my @KS = grep { $_ % 2 } 1 .. 15; # odd k only, so two varieties can't tie
# 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, $k) = @_;
# 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;
# When distances are equal, <=> returns 0, which is false, so || falls
# through to the row number: equal distances keep the earlier seed.
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;
}
sub count_correct {
my ($points, $train, $k) = @_;
return scalar grep { classify($_, $train, $k) eq $_->{label} } @$points;
}
sub cv_accuracy {
my ($train, $k) = @_;
# Fold $f is rows $lo to $hi. The rows are already shuffled, so
# consecutive blocks make fair folds. @$train[...] is an array slice:
# it takes the rows at a list of positions, and 0 .. -1 is empty.
my $size = int(@$train / $FOLDS);
my $correct = 0;
for my $f (0 .. $FOLDS - 1) {
my ($lo, $hi) = ($f * $size, ($f + 1) * $size - 1);
my @held_out = @$train[$lo .. $hi];
my @rest = @$train[0 .. $lo - 1, $hi + 1 .. $#$train];
$correct += count_correct(\@held_out, \@rest, $k);
}
return $correct / @$train;
}
my ($train, $test) = read_seeds($ARGV[0]);
print 'train_count ', scalar @$train, "\n";
print 'test_count ', scalar @$test, "\n";
my ($best_k, $best_accuracy) = (undef, -1);
for my $k (@KS) {
my $accuracy = cv_accuracy($train, $k);
printf "cv_accuracy_k%d %.6f\n", $k, $accuracy;
# Strictly better, so ties keep the smaller k.
($best_k, $best_accuracy) = ($k, $accuracy) if $accuracy > $best_accuracy;
}
# Only now touch the test seeds, once, with the chosen k and all of train.
my $correct = count_correct($test, $train, $best_k);
print "best_k $best_k\n";
print "test_correct $correct\n";
printf "test_accuracy %.6f\n", $correct / @$test;The classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. Array slices build each split.
@$train[$lo .. $hi] takes one block of 30 rows, and rest takes the rows
at two ranges in one slice. For the first fold, 0 .. -1 is an empty range,
so no special case is needed.
Perl has no cross-validation or kNN, and CPAN modules aren’t installed. The sort block compares distances, then row numbers, so equal distances keep the earlier seed, and a hash counts the votes.
<?php
// 5-fold cross-validation for k-nearest neighbors, using only PHP and the
// extensions built into it.
//
// Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
// holding out one fold at a time, picks the k with the best average
// accuracy, and then scores that k once on the untouched test seeds.
declare(strict_types=1);
const FOLDS = 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, int $k): 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. On equal distances ?: falls through to the
// row number, so the earlier training seed comes first.
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; ?? 0 supplies the first 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;
}
function count_correct(array $points, array $train, int $k): int
{
$correct = 0;
foreach ($points as $seed) {
if (classify($seed, $train, $k) === $seed['label']) {
$correct++;
}
}
return $correct;
}
function cv_accuracy(array $train, int $k): float
{
// Fold f is rows f*size up to (f+1)*size. The rows are already
// shuffled, so consecutive blocks make fair folds. array_slice takes
// (start, length) and numbers the copy from 0 again.
$size = intdiv(count($train), FOLDS);
$correct = 0;
for ($f = 0; $f < FOLDS; $f++) {
$held_out = array_slice($train, $f * $size, $size);
$rest = array_merge(array_slice($train, 0, $f * $size),
array_slice($train, ($f + 1) * $size));
$correct += count_correct($held_out, $rest, $k);
}
return $correct / count($train);
}
[$train, $test] = read_seeds($argv[1]);
echo 'train_count ', count($train), "\n";
echo 'test_count ', count($test), "\n";
$best_k = 0;
$best_accuracy = -1.0;
for ($k = 1; $k <= 15; $k += 2) { // odd k only
$accuracy = cv_accuracy($train, $k);
printf("cv_accuracy_k%d %.6f\n", $k, $accuracy);
if ($accuracy > $best_accuracy) { // strictly better: ties keep the smaller k
$best_k = $k;
$best_accuracy = $accuracy;
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
$correct = count_correct($test, $train, $best_k);
echo "best_k $best_k\n";
echo "test_correct $correct\n";
printf("test_accuracy %.6f\n", $correct / count($test));The kNN classifier is the same as on the k-nearest neighbors page, with $k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. array_slice builds each split. It
takes a start and a length, not an end, and numbers the copy from 0 again,
so array_merge can join the pieces before and after the held-out fold.
PHP has no cross-validation function, and PHP-ML and Rubix ML, the
Composer packages that offer one, aren’t installed. As on the kNN
page, an array keyed by label counts the vote, and usort breaks distance
ties by row number, so equal distances keep the earlier training seed.
-- 5-fold cross-validation for k-nearest neighbors, in PostgreSQL.
--
-- Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
-- holding out one fold at a time, picks the k with the best accuracy, and
-- then scores that k once on the untouched test seeds. There are no loops:
-- the folds and the values of k are columns, joined and grouped.
WITH train AS (
-- run.sh numbers rows in file order as row_id. Numbering the training
-- rows from 0 puts rows 0-29 in fold 0, rows 30-59 in fold 1, and so on.
SELECT row_id AS id, length_mm, width_mm, variety,
(row_number() OVER (ORDER BY row_id) - 1)
/ (count(*) OVER () / 5) AS fold -- integer division
FROM data
WHERE split = 'train'
),
test AS (SELECT row_id AS id, length_mm, width_mm, variety FROM data WHERE split = 'test'),
ks AS (SELECT k FROM generate_series(1, 15, 2) AS k), -- odd k, so votes can't tie
ranked AS (
-- Each held-out seed against the training seeds in the other folds,
-- ranked by distance. Equal distances keep the earlier row, train.id.
SELECT held.id, held.variety AS actual, train.variety AS neighbor,
row_number() OVER (
PARTITION BY held.id
ORDER BY sqrt((held.length_mm - train.length_mm) ^ 2
+ (held.width_mm - train.width_mm) ^ 2),
train.id
) AS rank
FROM train AS held
JOIN train ON train.fold <> held.fold
),
cv_votes AS (
-- The rank list is computed once, then reused for every k: the k nearest
-- are the rows ranked 1 to k.
SELECT k, id, actual, neighbor, count(*) AS n
FROM ks JOIN ranked ON rank <= k
GROUP BY k, id, actual, neighbor
),
cv_predictions AS (
SELECT DISTINCT ON (k, id) k, id, actual, neighbor AS predicted
FROM cv_votes
ORDER BY k, id, n DESC
),
cv AS (
SELECT k, round(count(*) FILTER (WHERE predicted = actual)::numeric
/ count(*), 6) AS accuracy
FROM cv_predictions
GROUP BY k
),
best AS (
-- Highest accuracy first; on a tie, the smaller k.
SELECT k FROM cv ORDER BY accuracy DESC, k LIMIT 1
),
test_ranked AS (
-- Only now touch the test seeds, once, against all of the training seeds.
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
),
test_predictions AS (
SELECT DISTINCT ON (id) id, actual, neighbor AS predicted
FROM (
SELECT id, actual, neighbor, count(*) AS n
FROM test_ranked JOIN best ON rank <= best.k
GROUP BY id, actual, neighbor
) AS votes
ORDER BY id, n DESC
),
totals AS (
SELECT (SELECT count(*) FROM train) AS train_count,
(SELECT count(*) FROM test) AS test_count,
(SELECT k FROM best) AS best_k,
count(*) FILTER (WHERE predicted = actual) AS correct
FROM test_predictions
)
SELECT name, value
FROM (
SELECT 1 AS position, 'train_count' AS name, train_count::text AS value FROM totals
UNION ALL SELECT 2, 'test_count', test_count::text FROM totals
UNION ALL SELECT 2 + k, 'cv_accuracy_k' || k, accuracy::text FROM cv
UNION ALL SELECT 20, 'best_k', best_k::text FROM totals
UNION ALL SELECT 21, 'test_correct', correct::text FROM totals
UNION ALL SELECT 22, 'test_accuracy',
round(correct::numeric / test_count, 6)::text FROM totals
) AS results
ORDER BY position;SQL has no loops, so the folds and the values of k become columns. Numbering
the training rows from 0 with row_number() and dividing by 30 gives each
row its fold, and a self-join on train.fold <> held.fold pairs every
seed with the 120 seeds outside its fold.
We rank those neighbors once. Joining the ranking to generate_series(1, 15, 2) on rank <= k gives the k nearest for every k at once, and
GROUP BY k counts the votes. ORDER BY accuracy DESC, k with LIMIT 1
picks the best k, smaller on a tie. As on the kNN page, train.id breaks
distance ties. PostgreSQL has no kNN or cross-validation built in.
% 5-fold cross-validation for k-nearest neighbors, using SWI-Prolog and the
% libraries that come with it.
%
% Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
% holding out one fold at a time, picks the k with the best accuracy, and
% then scores that k once on the untouched test seeds.
:- initialization(main, main).
folds(5).
% read_seeds(+Path, -Train, -Test): every row as seed(Length, Width,
% Variety), split by its "split" column, the same as on the kNN page.
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),
findall(Seed, member("train"-Seed, Rows), Train),
findall(Seed, member("test"-Seed, Rows), Test).
% distance_pair(+Seed, +TrainSeed, -Pair): Pair is Distance-Variety.
distance_pair(seed(L1, W1, _), seed(L2, W2, Variety), Distance-Variety) :-
Distance is sqrt((L1 - L2) ** 2 + (W1 - W2) ** 2).
% nearest(+K, +Train, +Seed, -Varieties): the varieties of the K nearest
% training seeds. keysort is stable, so equal distances keep file order,
% and a list of length K that append finds at the front is the first K.
nearest(K, Train, Seed, Varieties) :-
maplist(distance_pair(Seed), Train, Pairs),
keysort(Pairs, Sorted),
length(Nearest, K),
append(Nearest, _, Sorted),
pairs_values(Nearest, Varieties).
% majority(+Labels, -Winner): the label with the most votes.
majority(Labels, Winner) :-
sort(Labels, Candidates),
findall(Count-Label,
( member(Label, Candidates),
aggregate_all(count, member(Label, Labels), Count) ),
Counts),
max_member(_-Winner, Counts).
% count_correct(+K, +Train, +Seeds, -Correct): how many of Seeds the K
% nearest training seeds label correctly. When the vote and the seed's own
% variety differ, == fails, and aggregate_all doesn't count that seed.
count_correct(K, Train, Seeds, Correct) :-
aggregate_all(count,
( member(Seed, Seeds),
Seed = seed(_, _, Variety),
nearest(K, Train, Seed, Labels),
majority(Labels, Predicted),
Predicted == Variety ),
Correct).
% fold(+Train, +F, -HeldOut, -Rest): fold F (from 0) is the block of Size
% rows after the first F * Size. Each append splits a list in two, with
% the length of the first part fixed beforehand.
fold(Train, F, HeldOut, Rest) :-
folds(Folds),
length(Train, N),
Size is N // Folds,
Start is F * Size,
length(Before, Start),
append(Before, Tail, Train),
length(HeldOut, Size),
append(HeldOut, After, Tail),
append(Before, After, Rest).
% cv_accuracy(+Train, +K, -Accuracy): correct across all folds over N.
cv_accuracy(Train, K, Accuracy) :-
folds(Folds),
Last is Folds - 1,
findall(Correct,
( between(0, Last, F),
fold(Train, F, HeldOut, Rest),
count_correct(K, Rest, HeldOut, Correct) ),
PerFold),
sum_list(PerFold, Total),
length(Train, N),
Accuracy is Total / N.
% best(+Pairs, -BestK): Pairs are K-Accuracy in increasing K. A later K
% replaces the best only when strictly better, so ties keep the smaller K.
best([K-A|Rest], BestK) :- best(Rest, K, A, BestK).
best([], K, _, K).
best([K-A|Rest], _, BestA, BestK) :-
A > BestA, !,
best(Rest, K, A, BestK).
best([_|Rest], K0, A0, BestK) :-
best(Rest, K0, A0, BestK).
main :-
current_prolog_flag(argv, [Path|_]),
read_seeds(Path, Train, Test),
length(Train, TrainCount),
length(Test, TestCount),
format("train_count ~d~n", [TrainCount]),
format("test_count ~d~n", [TestCount]),
% Odd K only, so two varieties can't tie.
findall(K-Accuracy,
( between(1, 15, K), K mod 2 =:= 1,
cv_accuracy(Train, K, Accuracy) ),
Scores),
forall(member(K-Accuracy, Scores),
format("cv_accuracy_k~d ~6f~n", [K, Accuracy])),
best(Scores, BestK),
% Only now touch the test seeds, once, with all of the training seeds.
count_correct(BestK, Train, Test, Correct),
TestAccuracy is Correct / TestCount,
format("best_k ~d~n", [BestK]),
format("test_correct ~d~n", [Correct]),
format("test_accuracy ~6f~n", [TestAccuracy]).The kNN classifier is the one from the k-nearest neighbors page, with K
passed in: keysort orders the Distance-Variety pairs stably, so equal
distances keep file order. Each fold comes from append, which splits a
list in two once you fix the first part’s length. We split off the rows
before the fold, then the fold’s 30, and join what’s left into Rest.
There are no loops. between(1, 15, K) generates each k, and
K mod 2 =:= 1 keeps the odd ones. findall collects the per-fold
counts, and sum_list adds them. A recursive best keeps a new k only
when it’s strictly better. SWI-Prolog has no cross-validation library to
avoid.
# 5-fold cross-validation for k-nearest neighbors, using only base R.
#
# Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
# holding out one fold at a time, picks the k with the best average accuracy,
# and then scores that k once on the untouched test seeds.
folds <- 5
ks <- seq(1, 15, by = 2) # odd k only, so two varieties can't tie
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, seeds, k) {
# Distances from this point to every seed at once. order() is stable, so
# equal distances keep file order.
distance <- sqrt((seeds$length_mm - length_mm)^2 + (seeds$width_mm - width_mm)^2)
nearest <- seeds$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)]
}
count_correct <- function(points, seeds, k) {
# MoreArgs passes the same seeds and k to every call.
predicted <- mapply(classify, points$length_mm, points$width_mm,
MoreArgs = list(seeds = seeds, k = k))
sum(predicted == points$variety)
}
cv_accuracy <- function(k) {
# Fold f is rows (f - 1) * size + 1 to f * size. The rows are already
# shuffled, so consecutive blocks make fair folds.
size <- nrow(train) %/% folds
correct <- 0
for (f in 1:folds) {
rows <- ((f - 1) * size + 1):(f * size)
# A negative index drops those rows, leaving the other four folds.
correct <- correct + count_correct(train[rows, ], train[-rows, ], k)
}
correct / nrow(train)
}
cat(sprintf("train_count %d\n", nrow(train)))
cat(sprintf("test_count %d\n", nrow(test)))
best_k <- NA
best_accuracy <- -1
for (k in ks) {
accuracy <- cv_accuracy(k)
cat(sprintf("cv_accuracy_k%d %.6f\n", k, accuracy))
if (accuracy > best_accuracy) { # strictly better, so ties keep the smaller k
best_k <- k
best_accuracy <- accuracy
}
}
# Only now touch the test seeds, once, with the chosen k and all of train.
correct <- count_correct(test, train, best_k)
cat(sprintf("best_k %d\n", best_k))
cat(sprintf("test_correct %d\n", correct))
cat(sprintf("test_accuracy %.6f\n", correct / nrow(test)))The classifier is the same as on the k-nearest neighbors page, with the
training seeds and k passed in. Each fold is an index range, rows, and R
builds both halves of the split from it: train[rows, ] is the held-out
block of 30, and train[-rows, ] is everything else, because a negative
index drops rows instead of picking them. mapply() takes MoreArgs for
the seeds and k that every call shares.
Base R has no cross-validation function. The class package, home of
knn.cv(), and caret’s trainControl() aren’t installed in this image, so we
write out both loops, the one over k and the one over folds.
# 5-fold cross-validation for k-nearest neighbors, using only the standard
# library. Scores each odd k from 1 to 15 by holding out one fold of the
# training seeds at a time, picks the best k, and then scores that k once on
# the untouched test seeds.
FOLDS = 5
KS = (1..15).step(2).to_a # odd k only, so two varieties can't tie
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, k)
# 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)
nearest.map { |(_, label), _| label }.tally.max_by { |_, votes| votes }.first
end
def count_correct(points, train, k)
points.count { |features, label| classify(features, train, k) == label }
end
def cv_accuracy(train, k)
# Fold f is the block of size rows starting at f * size. The rows are
# already shuffled, so consecutive blocks make fair folds. arr[start, n]
# takes n rows from start, and arr[start..] runs to the end.
size = train.length / FOLDS
correct = (0...FOLDS).sum do |f|
held_out = train[f * size, size]
rest = train[0, f * size] + train[(f + 1) * size..]
count_correct(held_out, rest, k)
end
correct.fdiv(train.length)
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" }
puts "train_count #{train.length}"
puts "test_count #{test.length}"
best_k, best_accuracy = nil, -1.0
KS.each do |k|
accuracy = cv_accuracy(train, k)
puts format("cv_accuracy_k%d %.6f", k, accuracy)
# Strictly better, so ties keep the smaller k.
best_k, best_accuracy = k, accuracy if accuracy > best_accuracy
end
# Only now touch the test seeds, once, with the chosen k and all of train.
correct = count_correct(test, train, best_k)
puts "best_k #{best_k}"
puts "test_correct #{correct}"
puts format("test_accuracy %.6f", correct.fdiv(test.length))The classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. Slicing builds each split. train[start, n]
takes n rows from start, so the held-out fold is train[f * size, size],
and rest joins the rows before it to train[(f + 1) * size..], an endless
range that runs to the last row.
Ruby has no cross-validation in its standard library, and the Rumale gem,
which has it, isn’t installed. sort_by isn’t stable, so the sort key is
[distance, i], which keeps equal distances in file order.
//! 5-fold cross-validation for k-nearest neighbors, using only the standard
//! library.
//!
//! Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
//! holding out one fold at a time, picks the k with the best average accuracy,
//! and then scores that k once on the untouched test seeds.
use std::env;
use std::fs;
const FOLDS: 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()
}
/// `train` holds references to the training seeds, so a fold's split copies
/// no seeds.
fn classify(point: &[f64; 2], train: &[&Seed], k: usize) -> String {
// Sort the references by distance. sort_by is stable, so equal distances
// keep file order. f64 isn't Ord, hence total_cmp.
let mut nearest = train.to_vec();
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 count_correct(points: &[Seed], train: &[&Seed], k: usize) -> usize {
points
.iter()
.filter(|seed| classify(&seed.features, train, k) == seed.label)
.count()
}
/// Fold f is rows f*size up to (f+1)*size. The rows are already shuffled, so
/// consecutive blocks make fair folds.
fn cv_accuracy(train: &[Seed], k: usize) -> f64 {
let size = train.len() / FOLDS;
let mut correct = 0;
for f in 0..FOLDS {
let (start, end) = (f * size, (f + 1) * size);
let held_out = &train[start..end];
// chain joins the rows before and after the fold, in file order.
let rest: Vec<&Seed> = train[..start].iter().chain(&train[end..]).collect();
correct += count_correct(held_out, &rest, k);
}
correct as f64 / train.len() as f64
}
fn main() {
let path = env::args().nth(1).expect("usage: main <data.csv>");
let (train, test) = read(&path);
println!("train_count {}", train.len());
println!("test_count {}", test.len());
let (mut best_k, mut best_accuracy) = (0, -1.0);
// Odd k only. A strict > means a tie keeps the smaller k.
for k in (1..=15).step_by(2) {
let accuracy = cv_accuracy(&train, k);
println!("cv_accuracy_k{k} {accuracy:.6}");
if accuracy > best_accuracy {
(best_k, best_accuracy) = (k, accuracy);
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
let all: Vec<&Seed> = train.iter().collect();
let correct = count_correct(&test, &all, best_k);
println!("best_k {best_k}");
println!("test_correct {correct}");
println!("test_accuracy {:.6}", correct as f64 / test.len() as f64);
}The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation adds two loops: one over
the odd values of k, and one over the 5 folds.
The held-out fold is a slice, &train[start..end], which borrows 30 rows
without copying them. The other 120 rows come from chain, which joins the
rows before and after the fold into a vector of references, in file order.
A shared & borrow is read-only, so the fold can’t be changed by accident.
sort_by is stable, so equal distances keep the earlier seed. Crates such
as linfa and smartcore offer cross-validation, but none is installed.
// 5-fold cross-validation for k-nearest neighbors, using only Swift's
// standard library and Foundation, which ships with it.
//
// Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
// holding out one fold at a time, picks the k with the best average
// accuracy, and then scores that k once on the untouched test seeds.
import Foundation
let folds = 5
let ks = stride(from: 1, through: 15, by: 2) // odd k only, so two varieties can't tie
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)
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], _ k: Int) -> 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)
// counts[label, default: 0] reads 0 for a label we haven't seen yet.
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.
var winner = nearest.first!.label
for seed in nearest where counts[seed.label]! > counts[winner]! {
winner = seed.label
}
return winner
}
func countCorrect(_ points: [Seed], _ train: [Seed], _ k: Int) -> Int {
points.filter { classify($0.point, train, k) == $0.label }.count
}
func cvAccuracy(_ train: [Seed], _ k: Int) -> Double {
// Fold f is rows f*size up to (f+1)*size. The rows are already shuffled,
// so consecutive blocks make fair folds.
let size = train.count / folds
var correct = 0
for f in 0..<folds {
let start = f * size, end = (f + 1) * size
// A range subscript gives an ArraySlice that shares train's storage;
// Array(...) copies it into an array of its own.
let heldOut = Array(train[start..<end])
let rest = Array(train[..<start] + train[end...])
correct += countCorrect(heldOut, rest, k)
}
return Double(correct) / Double(train.count)
}
print("train_count", train.count)
print("test_count", test.count)
var bestK = 0
var bestAccuracy = -1.0
for k in ks {
let accuracy = cvAccuracy(train, k)
print("cv_accuracy_k\(k)", String(format: "%.6f", accuracy))
if accuracy > bestAccuracy { // strictly better, so ties keep the smaller k
bestK = k
bestAccuracy = accuracy
}
}
// Only now touch the test seeds, once, with the chosen k and all of train.
let correct = countCorrect(test, train, bestK)
print("best_k", bestK)
print("test_correct", correct)
print("test_accuracy", String(format: "%.6f", Double(correct) / Double(test.count)))The kNN classifier is the one from the k-nearest neighbors page, with k
passed in instead of fixed at 5. Cross-validation wraps it in two loops:
stride(from:through:by:) gives the odd values of k, and a plain range
gives the 5 folds. A range subscript such as train[start..<end] gives an
ArraySlice, a view that shares the array’s storage, so we wrap it in
Array(...) for the held-out block, and + joins the slices before and
after it into the rest.
Swift’s standard library has no cross-validation or kNN. sorted(by:) is
stable, so equal distances keep file order, and a Dictionary counts the
votes.
# 5-fold cross-validation for k-nearest neighbors, using only Tcl's
# built-in commands.
#
# Splits the training seeds into 5 folds, scores each odd k from 1 to 15 by
# holding out one fold at a time, picks the k with the best average
# accuracy, and then scores that k once on the untouched test seeds. expr
# does the arithmetic; its {braces} keep Tcl from substituting twice.
set FOLDS 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. With two
# varieties and odd k, no vote ties.
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
}
proc count_correct {points train k} {
set correct 0
foreach seed $points {
lassign $seed len wid label
if {[classify $len $wid $train $k] eq $label} {
incr correct
}
}
return $correct
}
proc cv_accuracy {train k} {
# Fold f is items f*size to (f+1)*size - 1. The rows are already
# shuffled, so consecutive blocks make fair folds. lrange takes first
# and last indices, both included; concat joins the two pieces around
# the held-out block.
global FOLDS
set size [expr {[llength $train] / $FOLDS}]
set correct 0
for {set f 0} {$f < $FOLDS} {incr f} {
set lo [expr {$f * $size}]
set hi [expr {$lo + $size - 1}]
set held_out [lrange $train $lo $hi]
set rest [concat [lrange $train 0 [expr {$lo - 1}]] \
[lrange $train [expr {$hi + 1}] end]]
incr correct [count_correct $held_out $rest $k]
}
return [expr {double($correct) / [llength $train]}]
}
lassign [read_seeds [lindex $argv 0]] train test
puts "train_count [llength $train]"
puts "test_count [llength $test]"
set best_k 0
set best_accuracy -1.0
for {set k 1} {$k <= 15} {incr k 2} {
set accuracy [cv_accuracy $train $k]
puts "cv_accuracy_k$k [format %.6f $accuracy]"
# Strictly better, so ties keep the smaller k.
if {$accuracy > $best_accuracy} {
set best_k $k
set best_accuracy $accuracy
}
}
# Only now touch the test seeds, once, with the chosen k and all of train.
set correct [count_correct $test $train $best_k]
puts "best_k $best_k"
puts "test_correct $correct"
puts "test_accuracy [format %.6f [expr {double($correct) / [llength $test]}]]"The kNN classifier is the same as on the k-nearest neighbors page, with k
passed in instead of fixed at 5. Two loops wrap it: one over the odd values
of k, and one over the 5 folds. lrange cuts each fold, and both of its
indices are included, so fold 1 is lrange $train 0 29. concat joins
the pieces before and after it. For the first fold, the “before” piece is
lrange $train 0 -1, which is simply empty.
Tcl has no cross-validation command, and Tcllib isn’t installed. The
distance is written out with sqrt, lsort -real -index 0 is stable, so
equal distances keep file order, and a dict counts the vote.