Python Decision Trees and K-Nearest Neighbors

A decision tree splits the data with conditions such as weight <= 5.5, choosing at each step the split that best separates the classes (by default using Gini impurity). Each branch is split again until a stopping rule applies, and each final leaf predicts the majority class of the training examples that reached it.

from sklearn.tree import DecisionTreeClassifier, export_text
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=["weight_kg"]))

To predict, a new item follows the conditions from the root down to a leaf. Trees handle features on any scale without preprocessing and capture interactions, such as "heavy and magnetic", automatically.

Left unrestricted, a tree keeps splitting until every leaf is pure, which often means memorising the training data, noise included. Limit growth with max_depth, min_samples_leaf or max_leaf_nodes. Shallow trees generalise better and are easier to read.

KNN stores the training data. To predict, it measures the distance from the new example to every stored one, takes the k nearest, and returns their majority class (or average value, for regression):

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=3).fit(X, y)
print(knn.kneighbors([[7]]))     # distances and indexes of the 3 nearest items

The default distance is Euclidean, so feature scales matter. With weight in kilograms (0 to 10) and volume in cubic centimetres (0 to 5,000), volume differences swamp weight differences and the model effectively ignores weight. Standardise features first, inside a pipeline: make_pipeline(StandardScaler(), KNeighborsClassifier()).

The choice of k sets the trade-off: k = 1 follows every quirk of the training data, while a large k smooths over real boundaries. weights="distance" lets closer neighbours count more. KNN also struggles with many features, because in high dimensions distances become less informative.

Settings chosen before training, such as max_depth for a tree or n_neighbors for KNN, are hyperparameters. Choose them by comparing candidates on validation data or with cross-validation, never on the final test set:

from sklearn.model_selection import GridSearchCV
search = GridSearchCV(KNeighborsClassifier(), {"n_neighbors": [1, 3, 5, 7]}, cv=5)
search.fit(X_train, y_train)
print(search.best_params_)

GridSearchCV runs cross-validation inside the training data for every candidate and refits the best one. The test set is used once, at the end, to report the chosen model's performance.

If you try ten depths and pick the one with the best test score, the test set has become part of model selection, and its score is optimistic: some of that "best" is luck. This is a subtle form of leakage that's easy to commit when experimenting in a notebook.

A shallow tree can be printed and checked by a person, which is valuable when decisions must be justified. KNN's explanations are example-based: "classified as metal because these three similar items were metal".

Readable doesn't mean fair or correct. A tree trained on biased historical decisions reproduces that bias in clear rules, and KNN reproduces whatever patterns its stored examples contain. Both models are only as good as the data they learn from. Ensembles of many trees, random forests and gradient boosting, usually predict better than one tree, at the cost of simple readability.

Task: compare a shallow tree and scaled KNN with the same held-out material records and training validation protocol.

from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.tree import DecisionTreeClassifier

X = [[0.2, 900], [0.3, 1500], [0.25, 3000], [2.0, 1000], [2.5, 1600], [2.2, 2900],
     [0.4, 1200], [1.8, 1300], [0.35, 2500], [2.4, 2200], [0.15, 700], [2.1, 800]]
y = ["paper"] * 3 + ["metal"] * 3 + ["paper", "metal", "paper", "metal", "paper", "metal"]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=1, stratify=y)

candidates = {
    "tree": GridSearchCV(DecisionTreeClassifier(random_state=0), {"max_depth": [1, 2, 3]}, cv=3),
    "knn": GridSearchCV(make_pipeline(StandardScaler(), KNeighborsClassifier()),
                        {"kneighborsclassifier__n_neighbors": [1, 3]}, cv=3),
}
for name, search in candidates.items():
    search.fit(X_tr, y_tr)
    print(name, search.best_params_, "test accuracy", search.score(X_te, y_te))

Both models are tuned only on the training split and scored once on the same test rows. For the worked check, mixed KNN features are scaled because distance depends on their magnitudes.

scikit-learn's guides to decision trees and nearest neighbors explain the algorithms and their parameters. Continue with training and testing datasets and cross-validation. Practise with the Python exercises and Python quiz.