Classical ML: Trees, Ensembles, k-NN, SVM & Clustering

The workhorses of tabular data. Learn decision trees (Gini impurity, entropy, information gain, depth and pruning), ensembles (random forests, bagging, gradient boosting — XGBoost/LightGBM), k-nearest neighbours and distance metrics, support vector machines and kernels, Naive Bayes, unsupervised learning (k-means, hierarchical clustering, DBSCAN, PCA), the bias–variance trade-off, feature engineering and pipelines — with NumPy code for k-means and a Gini decision stump.

Before deep learning, and still today for most business (tabular) data, the best models are trees and their ensembles. Gradient-boosted trees win many Kaggle competitions and run fraud detection, credit risk and pricing systems.

Unsupervised methods like k-means and PCA find structure in unlabelled data — customer segments, anomalies, compressed representations.

An analogy

A decision tree is like the game 'twenty questions': each question splits the possibilities until the answer is clear. A random forest asks hundreds of slightly different players and takes a vote — collectively wiser than any single player.

Decision trees

Trees split data on feature thresholds to make groups purer (Gini or entropy for classification, variance for regression). They handle mixed feature types, need no scaling, capture interactions and are easy to explain — but deep trees overfit. Control with max depth, minimum samples per leaf and pruning.

Ensembles

Combining many models:

• Bagging / random forests — train trees on bootstrap samples with random feature subsets, average votes (reduces variance)
• Gradient boosting — add shallow trees sequentially, each fixing previous errors (reduces bias); XGBoost, LightGBM, CatBoost
• Stacking — a meta-model combines different models
• Feature importance and SHAP values explain ensembles
• Typically the strongest choice for tabular data

Distance, margin and probability models

k-NN predicts from the k closest training points (needs scaling; slow at prediction time; suffers in high dimensions). SVMs find the maximum-margin boundary; kernels (RBF, polynomial) create non-linear boundaries. Naive Bayes applies Bayes' theorem assuming feature independence — fast, strong baseline for text.

Unsupervised learning and bias–variance

k-means (choose k with elbow/silhouette; sensitive to initialisation — use k-means++), hierarchical clustering (dendrograms), DBSCAN (density-based, finds arbitrary shapes and outliers), Gaussian mixtures, PCA (variance-maximising projection via eigenvectors) and t-SNE/UMAP for visualisation. The bias–variance trade-off: simple models underfit (high bias), complex ones overfit (high variance); choose complexity with cross-validation. Pipelines bundle preprocessing and models to prevent leakage.

Formulas

• Gini impurity: G = 1 − Σ pₖ²
• Split quality: weighted G = (n_L/n)G_L + (n_R/n)G_R (minimise)
• k-means objective: min Σᵢ ‖xᵢ − μ_c(i)‖²
• Euclidean distance: d(x, z) = √Σ(xⱼ − zⱼ)²
• Boosting: F_m(x) = F_{m−1}(x) + η·h_m(x) (fit h_m to residuals)
• Bias–variance: E[error] = bias² + variance + irreducible noise

Worked example: Gini impurity

Given: Node with 6 positives, 4 negatives

Find: G.

• 1 − (0.6² + 0.4²)

Answer: 0.48

Worked example: Entropy

Given: 50/50 node

Find: H.

• −2 × 0.5 log₂ 0.5

Answer: 1 bit (maximum)

Worked example: k-NN vote

Given: k = 5 neighbours: 3 A, 2 B

Find: Prediction.

• Majority vote

Answer: A (probability 0.6)

k-means clustering and a Gini split

import numpy as np
# k-means clustering and a Gini-impurity decision stump
rng = np.random.default_rng(1)
pts = np.vstack([rng.normal(c, 0.6, (50, 2)) for c in ((0, 0), (5, 5), (0, 6))])
centroids = pts[[0, 50, 100]].copy()
for it in range(10):
    labels = np.argmin(((pts[:, None, :] - centroids[None]) ** 2).sum(-1), axis=1)
    centroids = np.array([pts[labels == k].mean(0) for k in range(3)])
print("k-means centroids:", np.round(centroids, 2).tolist())
print("cluster sizes:", np.bincount(labels).tolist())
# Decision stump: best split on one feature by Gini impurity
x = np.array([2, 3, 4, 5, 6, 7, 8, 9]); y = np.array([0, 0, 0, 1, 0, 1, 1, 1])
def gini(v):
    if len(v) == 0: return 0.0
    p = np.bincount(v, minlength=2) / len(v)
    return 1 - np.sum(p ** 2)
best = min(((t, (gini(y[x <= t]) * (x <= t).sum() + gini(y[x > t]) * (x > t).sum()) / len(y)) for t in x[:-1]), key=lambda z: z[1])
print(f"root Gini {gini(y):.3f}; best split x <= {best[0]} with weighted Gini {best[1]:.3f}")
# k-means centroids: [[-0.01, -0.08], [4.92, 4.99], [-0.18, 5.99]]
# cluster sizes: [50, 50, 50]
# root Gini 0.500; best split x <= 4 with weighted Gini 0.200

k-means alternates assigning points to the nearest centroid and moving centroids to the mean — it recovers the three true centres (0,0), (5,5), (0,6). The decision stump tries every threshold and picks the one that most reduces impurity: splitting at x ≤ 4 leaves one pure side and one mostly-pure side (weighted Gini 0.2). A tree repeats this recursively.

Common mistakes

• Wrong: Using deep single trees. — Right: Limit depth or use ensembles.
• Wrong: Running k-NN/k-means on unscaled features. — Right: Standardise features first.
• Wrong: Assuming k-means finds any cluster shape. — Right: It prefers spherical, similar-size clusters; try DBSCAN/GMM.

Applications

• Fraud detection: Gradient-boosted trees on transaction features.
• Customer segmentation: k-means on behaviour data.
• Credit risk: Tree ensembles with SHAP explanations.
• Anomaly detection: Isolation forests, DBSCAN.

Key takeaways

• Trees split to reduce impurity.
• Ensembles: forests (variance), boosting (bias).
• k-NN, SVM, Naive Bayes, k-means, PCA.
• Tune complexity with cross-validation.

Going further

• SHAP values: Game-theoretic feature attribution.
• Kernel trick: Implicit high-dimensional features.
• Isolation forest: Tree-based anomaly detection.