Decision Trees and k-Nearest Neighbours

Questions versus neighbours

A decision tree asks a sequence of yes/no questions about features (is petal width at most 0.8 cm?) and predicts the majority class at the leaf it reaches. Trees are easy to read and need no scaling, but deep trees memorise the training data. k-nearest neighbours (k-NN) stores the training data and predicts the majority class among the k closest examples; small k follows noise, large k smooths too much. Both show the key trade-off of ML: flexible models fit training data better but may generalise worse.

A readable depth-2 tree on iris, run

I ran this with Python 3, numpy 2.5.3 and scikit-learn 1.9.1, using fixed random seeds. A two-level tree on the bundled iris flowers uses only petal width: at most 0.80 cm is setosa, otherwise at most 1.75 cm is versicolor, else virginica, with 0.96 training accuracy.

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_text
iris = load_iris()
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(iris.data, iris.target)
print(export_text(tree, feature_names=list(iris.feature_names)))
print("training accuracy:", round(tree.score(iris.data, iris.target), 3))

Output:

|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

training accuracy: 0.96

How k changes k-NN, run

I ran this with Python 3, numpy 2.5.3 and scikit-learn 1.9.1, using fixed random seeds. On noisy two-moons data, k = 1 scores 1.000 on training but 0.873 on test; k = 5 to 15 reaches 0.880 on test; k = 201 smooths too much and drops to 0.840.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
X, y = make_moons(n_samples=600, noise=0.3, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)
print(" k | train acc | test acc")
for k in [1, 5, 15, 51, 201]:
    m = KNeighborsClassifier(n_neighbors=k).fit(X_tr, y_tr)
    print(f"{k:>3}| {m.score(X_tr, y_tr):>9.3f} | {m.score(X_te, y_te):.3f}")

Output:

 k | train acc | test acc
  1|     1.000 | 0.873
  5|     0.938 | 0.880
 15|     0.927 | 0.880
 51|     0.911 | 0.867
201|     0.884 | 0.840

Quick check: What happens with k = 1 in k-NN?

• It needs no data
• The model ignores all training data
• It always predicts one class
• Training accuracy is perfect but the model follows noise