Classical Machine Learning Algorithms Questions

Direct answer

K-means fails on varying-density, non-globular clusters because its objective, minimizing distance to a single centroid per cluster, implicitly assumes clusters are convex, similarly sized, and similarly dense. When that assumption breaks, I would reach for a density-based method like DBSCAN or HDBSCAN first, since they define clusters by connectivity rather than distance to a center, and consider spectral clustering or a full-covariance Gaussian mixture when the failure mode is about cluster shape/orientation rather than density.

Structured elaboration

$\min_{C} \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$

is k-means' actual objective, and it explains the failure mode directly: it only ever measures distance to a centroid, so a cluster that isn't roughly ball-shaped around some center will be split or merged incorrectly. Reach for DBSCAN or HDBSCAN first, since they attack the density-mismatch problem directly; treat spectral clustering and a full-covariance GMM as options for a different, less common failure mode, when clusters are the wrong shape or orientation rather than the wrong density.

Worked example

Six points in one dimension: 0, 1, 2 (a tight, dense group) and 10, 40, 70 (a sparse, spread-out group), to show exactly how k-means' centroid-distance rule mishandles varying density.

Run k-means (k=2) starting from centroids near the two groups' means, $c_1 = 1$ and $c_2 = 40$, and assign each point to its nearest centroid:

• 0: distance 1 to $c_1$, distance 40 to $c_2$, assigned to A
• 1, 2: also assigned to A (0 or 1, and 38 or 39 away from $c_2$)
• 10: distance 9 to $c_1$, distance 30 to $c_2$, assigned to A even though it belongs with the sparse group by density
• 40, 70: assigned to B

After recomputing centroids ($c_1 = 3.25$ over {0,1,2,10}, $c_2 = 55$ over {40,70}), the assignment is stable at that same grouping. Point 10 stays permanently absorbed into the tight cluster, because k-means only measures raw distance to a center, it has no notion that 10, 40, and 70 form a low-density-but-coherent group.

Now check what DBSCAN sees from the gaps between consecutive points: internal gaps within {0,1,2} are at most 1, the gap from 2 to 10 is 8, and the gaps 10-to-40 and 40-to-70 are both 30. With eps = 2.5 and minPts = 2, {0,1,2} forms one dense, connected cluster (each point has a neighbor within eps), while 10, 40, and 70 each have no neighbor within eps of any other point, so DBSCAN correctly flags them as noise/outliers rather than force-merging 10 into the tight cluster the way k-means did.

Trade-offs & pitfalls

• DBSCAN's single global eps is its main weakness, exactly the density-variation problem the question describes. If your data has multiple regions of genuinely different density, a single eps that works for one region will either merge everything in a denser region or mark an entire sparser region as noise.
• HDBSCAN addresses this by building a hierarchy across many eps values and extracting the most stable clusters, at the cost of being more expensive to run and somewhat less intuitive to explain.
• Spectral clustering's exact eigendecomposition doesn't scale past a few thousand points without approximation (sparse similarity graphs, Nystrom-approximated eigenvectors).
• Pitfall: reaching for a fancier algorithm before checking whether simple preprocessing (log-transforming a skewed feature, or standardizing before computing distances) already fixes the apparent density mismatch. Not every density problem is really a clustering-algorithm problem.

Direct answer

Under a fixed compute budget, tune the hyperparameters with the biggest expected impact first (n_estimators, max_features, max_depth or min_samples_leaf), search with a random or Bayesian strategy rather than exhaustive grid search since it covers the space more efficiently per trial, and evaluate with OOB error during the search (it's essentially free) before confirming the shortlisted top configurations with k-fold cross-validation.

Structured elaboration

Which hyperparameters to prioritize. Not all random forest hyperparameters matter equally:

• max_features (features considered per split) has the largest effect on the bias-variance trade-off discussed elsewhere in this topic; it directly controls how correlated the trees are with each other, which is the main lever on ensemble variance.
• n_estimators (number of trees) mostly trades compute for variance reduction with diminishing returns past a point; cheap to sweep since more trees just means more (parallelizable) work, not a different model shape.
• max_depth / min_samples_leaf control each tree's own bias-variance trade-off; too deep and individual trees overfit, too shallow and the ensemble underfits regardless of how many trees you add.
• class_weight matters specifically when the target is imbalanced; otherwise low priority.

Given limited trials, spend the early budget on max_features and max_depth/min_samples_leaf, since these change what each tree can represent; treat n_estimators as something you can increase for the finalists almost for free once the other hyperparameters are set, since it's the cheapest one to scale up after the fact.

Search strategy. Grid search wastes budget on combinations that share a bad value along one axis; random search covers each hyperparameter's marginal range more efficiently for the same trial count, and is the reasonable default under a hard compute ceiling, and the right first choice for most searches. If the budget allows more than a couple dozen trials, an optional upgrade beyond that baseline is Bayesian optimization: instead of picking each trial randomly, it fits a cheap probabilistic model of which hyperparameter values tend to score well, based on the trials run so far (for example a Gaussian process or a tree-structured Parzen estimator), and uses that model to choose where to try next, so it typically needs fewer total trials than random search to reach a comparable score. This is depth beyond what most interviews require as a first answer, worth naming as an available option rather than leading with it. A practical middle ground: an initial batch of random trials to map the space broadly, then switch to Bayesian optimization for the remaining budget.

OOB vs. cross-validation for evaluation. OOB error comes for free from the bootstrap mechanism (no extra retraining), which makes it the natural choice for the exploratory phase of the search, when you want to screen many configurations cheaply. For the final handful of candidate configurations, confirm with stratified k-fold CV (or a genuine held-out test set); OOB and CV are both estimates of generalization error but computed via different resampling mechanics, and CV's fold-based averaging is the more standard, better-understood number to report as the final generalization estimate.

Worked example

Suppose the budget allows 40 total training runs (a stand-in for "compute budget," expressed in trial count rather than wall-clock time so it stays portable across hardware). Work the budget backward from the confirmation step: the final check runs 5-fold stratified CV on the top 3 finalist configurations, and a 5-fold CV run on one configuration costs about as much as 5 single-fold trials, so confirming 3 finalists costs $3 \times 5 = 15$ trial-equivalents. That leaves $40 - 15 = 25$ trials for the search phase itself: 18 trials of random search over max_features (uniform over {sqrt, log2, 0.3, 0.5, 0.8}), max_depth (uniform over {5, 10, 20, None}), and min_samples_leaf (log-uniform over [1, 50]), each evaluated by OOB error; then 7 trials of Bayesian optimization refining around the best region those random trials found. n_estimators is fixed at a moderate value (say 200) during the search phase to keep trials cheap, then increased (say to 500-800) for the final chosen configuration, since increasing tree count essentially never hurts and mostly costs compute, not risk. Total accounted-for cost: $18 + 7 + 15 = 40$, exactly the stated budget.

Trade-offs & pitfalls

• OOB error can diverge from true generalization error on small or imbalanced datasets (see the OOB tradeoffs discussed for out-of-bag error more generally); if the dataset is small, spend more of the budget on CV directly rather than relying heavily on OOB during search.
• Random and Bayesian search both still require you to define sensible ranges up front; a poorly chosen range (e.g., max_depth capped too low) will make the whole search converge to a mediocre optimum regardless of search strategy.
• Treating n_estimators as "always increase for the finalist" assumes you have leftover compute budget at the end reserved for that; if the budget is truly exhausted after the search phase, this step gets skipped and you ship with the tree count used during search.
• A common mistake is to search all hyperparameters jointly with equal trial allocation regardless of expected impact; under a genuinely tight budget, deliberately weighting the search toward max_features and max_depth/min_samples_leaf first gets more signal per trial than treating every hyperparameter as equally worth exploring.

Direct answer

The L1 penalty $\lambda|\beta|$ has a sharp corner (a "kink") at $\beta = 0$: its left-hand derivative there is $-1$ and its right-hand derivative is $+1$, so no single tangent line, and hence no ordinary gradient, exists at that point. Solvers like coordinate descent sidestep this by optimizing one coefficient at a time, where the one-dimensional L1 subproblem has a closed-form solution called soft-thresholding, so the algorithm never actually needs a gradient at the kink.

Structured elaboration

Why the kink breaks vanilla gradient descent. For a smooth penalty like L2 ($\lambda\beta^2$), the derivative $2\lambda\beta$ is continuous everywhere, including at $\beta=0$, so gradient descent works unmodified. For L1:

These disagree, so $|\beta|$ is not differentiable at exactly $\beta=0$, which is precisely the point L1 is designed to push many coefficients toward.

Coordinate descent's workaround. Instead of computing a joint gradient over all coefficients, coordinate descent fixes every coefficient except one, $\beta_j$, and solves that one-dimensional subproblem exactly. Because the subproblem is one-dimensional, it has a closed-form minimizer even though the objective isn't smooth, no gradient step is needed at all for that coordinate; the algorithm just evaluates the closed form and moves on to the next coordinate.

Deriving the univariate soft-thresholding update. Fix all coefficients except $\beta_j$ (drop the subscript $j$ for readability). Let $r$ be the partial residual (the target minus the prediction from all other fixed coefficients), $x$ the feature column for this coordinate, $s = \|x\|^2$, and $z = x^\top r$. The one-dimensional subproblem (dropping the constant term $\|r\|^2$ that doesn't depend on $\beta$) is:

Consider the two smooth cases separately, since $|\beta|=\beta$ for $\beta>0$ and $|\beta|=-\beta$ for $\beta<0$:

• For $\beta>0$: setting the derivative to zero, $s\beta - z + \lambda = 0 \Rightarrow \beta = (z-\lambda)/s$, valid only if this is actually positive, i.e. $z>\lambda$.
• For $\beta<0$: $s\beta - z - \lambda = 0 \Rightarrow \beta = (z+\lambda)/s$, valid only if $z<-\lambda$.
• If $-\lambda \le z \le \lambda$, neither case is feasible. At a kink like $\beta=0$ there's no single tangent slope, but there's a whole range of slopes between the left-hand and right-hand derivatives (here $[-1,1]$, called the subdifferential) that all count as valid generalized gradients (subgradients) at that point. The optimality condition for a non-smooth function is that zero must be reachable by some value in that range; since $z/\lambda$ falls inside $[-1,1]$ here, that condition holds and confirms $\beta=0$ is the minimizer.

Combining all three cases into one closed form (the soft-thresholding operator):

If the feature column is standardized so that $s=1$, this simplifies to $\beta^\star = S(z,\lambda)$: shrink $z$ toward zero by $\lambda$, and clip to exactly zero if $|z|\le\lambda$.

Worked example

Take $s = 1$ (standardized feature) and $\lambda = 0.3$. For three candidate partial-correlation values $z$:

• $z = 0.5$: $|z| - \lambda = 0.2 > 0$, so $\beta^\star = \operatorname{sign}(0.5)\times 0.2 = 0.2$.
• $z = -0.5$: $|z|-\lambda = 0.2>0$, so $\beta^\star = \operatorname{sign}(-0.5)\times 0.2 = -0.2$.
• $z = 0.2$: $|z|-\lambda = -0.1 < 0$, so the max clips to $0$, giving $\beta^\star = 0$.

That third case is the entire point of the exercise: any coordinate whose signal $z$ is smaller in magnitude than the penalty $\lambda$ gets set to exactly zero, not just shrunk close to zero, which is the mechanism by which L1 produces genuinely sparse solutions rather than merely small coefficients (which is what L2 does instead).

Trade-offs and pitfalls

• Coordinate descent's closed-form update is fast per step but the algorithm cycles through coordinates, so convergence depends on the number of features and how correlated they are; highly correlated features can slow convergence.
• Proximal-gradient methods, ISTA (Iterative Shrinkage-Thresholding Algorithm) and its accelerated version FISTA, are the alternative to coordinate descent: they apply the same soft-thresholding operator to a full gradient step on the smooth part of the objective, useful when a closed-form per-coordinate update isn't available (e.g. more complex smooth losses), at the cost of needing a step size tied to the Lipschitz constant of the gradient (a bound on how fast the gradient itself can change; it sets the largest step size the update can safely take before it overshoots and diverges).
• A common wrong turn is trying to "fix" the non-differentiability by smoothing the L1 penalty (e.g. approximating $|\beta|$ with $\sqrt{\beta^2+\epsilon}$) so that plain gradient descent works; this sacrifices the exact-zero property that makes L1 useful for sparsity and feature selection in the first place, defeating the purpose of choosing L1 over L2.
• The derivation above assumes the feature column's scale $s=\|x\|^2$ is factored in correctly; skipping standardization and using a shared $\lambda$ across differently-scaled features silently penalizes large-scale features more, a common and easy-to-miss bug in from-scratch coordinate descent implementations.

Direct answer

A near-perfect training fit with a much worse validation score on a tree is the textbook overfitting signature, and the first place to look is whatever is currently letting the tree grow arbitrarily specific: max_depth, min_samples_leaf, min_samples_split, and cost-complexity pruning (ccp_alpha). Each one attacks the same problem from a different angle, and the fix is usually two or three of them together, not a single knob.

Structured elaboration

Why fraud data specifically makes this worse. Fraud datasets are typically severely class-imbalanced and full of near-duplicate legitimate transactions with a handful of true positives scattered among them. An unconstrained tree will happily carve out single-leaf rules that isolate individual fraud examples by coincidental feature combinations, rules that generalize to nothing. This is exactly the setting where min_samples_leaf matters more than usual: a leaf of size 1 on a rare-event dataset is almost never a real pattern.

My usual order: constrain leaf size and depth first (they're cheap to reason about and directly address "the tree is memorizing individual rows"), then add ccp_alpha if the tree still looks overly complex after that, since pruning is more expensive to tune (it requires its own validation curve) and works best as a refinement on top of already-sane depth/leaf settings rather than as the sole fix.

Worked example

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import roc_auc_score
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=4000, n_features=15, n_informative=6,
                            weights=[0.97, 0.03], flip_y=0.02, random_state=12)
Xtr, Xval, ytr, yval = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)

results = []
for depth, min_leaf in [(None, 1), (6, 1), (6, 20), (4, 50)]:
    t = DecisionTreeClassifier(max_depth=depth, min_samples_leaf=min_leaf, random_state=0)
    t.fit(Xtr, ytr)
    train_auc = roc_auc_score(ytr, t.predict_proba(Xtr)[:, 1])
    val_auc = roc_auc_score(yval, t.predict_proba(Xval)[:, 1])
    results.append((depth, min_leaf, train_auc, val_auc))

Running this on a synthetic imbalanced dataset (4,000 samples, roughly 3% positive rate, similar shape to a fraud problem) with a 70/30 train/validation split gives (verified):

The unconstrained tree hits a perfect train AUC of 1.000 (it has memorized the training set) but only 0.681 on validation, a large gap that is the overfitting signature described in the question. Constraining max_depth=6 and min_samples_leaf=20 together brings training AUC down to 0.881, but validation AUC actually goes up to 0.803: the model got measurably better at generalizing by giving up some of its training-set fit. That's the concrete evidence that these settings aren't just cosmetically closing the train/validation gap, they're producing a genuinely better model. Pushing further to max_depth=4, min_samples_leaf=50 overshot into mild underfitting here (validation AUC dropped back to 0.747), which is the reason this is a search, not a single guess.

Trade-offs & pitfalls

• Don't stop at "the gap closed"; confirm validation performance actually improved, not just that train and validation scores got closer together (a tree that's bad on both would also have a small gap).
• min_samples_leaf and max_depth interact: setting a large minimum leaf size implicitly limits how deep the tree can meaningfully grow anyway, so tune them jointly rather than treating each grid dimension as fully independent.
• Cost-complexity pruning needs its own validation curve (grow the full tree, then sweep ccp_alpha and measure held-out performance at each pruning level); skipping this and picking an arbitrary ccp_alpha value is a common shortcut that under- or over-prunes.
• On severely imbalanced data like fraud, growth-control hyperparameters interact with your resampling/class-weighting strategy: an aggressively subsampled majority class changes what "min_samples_leaf=20" effectively means relative to the minority class, so re-tune growth controls whenever the resampling strategy changes.

Direct answer

For a modest tabular dataset, I would default to linear regression when I expect roughly linear relationships, need interpretable coefficients, or need fast, predictable inference latency in production. I would reach for KNN when I expect meaningfully non-linear local structure, have relatively low dimensionality, and can tolerate or optimize away its per-query cost.

Structured elaboration

Dataset size and dimensionality. KNN's distance metric becomes less meaningful as dimensionality grows (the curse of dimensionality: in high dimensions, distances between points concentrate, so "nearest" stops being informative). Linear regression's cost and sample requirements scale gently with dimensionality by comparison.

Feature scaling. KNN requires careful standardization since it is entirely distance-based, an unscaled feature with a large numeric range will dominate the distance calculation regardless of its actual predictive relevance. Linear regression doesn't strictly require scaling for correctness, though it helps numerically and makes coefficients comparable.

Interpretability. Linear regression gives directly interpretable coefficients (sign, relative magnitude, confidence intervals). KNN is non-parametric: you can inspect which neighbors drove a prediction, but there's no global "effect of this feature" statement to make.

Inference latency.

Worked example

Take a dataset with n = 1,000 training rows and d = 10 features, a small but realistic tabular size.

Linear regression, per prediction: one dot product of length 10 plus an intercept add.

$O(d) = 10 \text{ multiplies} + 1 \text{ add} = 11 \text{ flops}$

Brute-force KNN, per prediction: a squared-distance computation (d subtractions and multiplies) against every one of the 1,000 training points, ignoring the subsequent top-k selection.

$O(n \cdot d) = 1{,}000 \times 10 = 10{,}000 \text{ flops}$

$10{,}000 / 11 \approx 909$

At this scale, a single KNN prediction does roughly 909 times more arithmetic than a single linear regression prediction, and that ratio grows linearly with n as the dataset gets larger, while linear regression's cost stays fixed at $O(d)$ regardless of how much training data you have.

Trade-offs & pitfalls

• KNN's cost grows with data, linear regression's doesn't. This is the single biggest production consideration: a linear model's latency is flat as you collect more training data; KNN's latency (or memory, if you precompute a structure) keeps growing.
• Regularized linear regression (ridge/lasso) narrows some of the flexibility gap with KNN while keeping the interpretability and latency advantages, worth trying before jumping to a non-parametric method.
• KNN needs an explicit strategy for irrelevant features: unlike a regularized linear model, plain KNN has no built-in way to downweight a noisy or irrelevant dimension, it will happily let that dimension corrupt every distance calculation.
• Pitfall: picking KNN for its simplicity to implement while ignoring that its "training" is trivial but its serving cost is the opposite, an approximate nearest-neighbor index (KD-tree, ball-tree, or ANN library) is close to mandatory once n grows past a few thousand and latency matters.