Classification Algorithms

ML interview notes — models & how to evaluate them

Logistic Regression

Predicts a probability by squashing a linear combination of features through the sigmoid function: σ(z) = 1 / (1 + e⁻ᶻ), mapping any real number to (0,1).

Sigmoid curve — the decision boundary is simply where predicted probability crosses the threshold (default 0.5).

The decision boundary itself is linear in the feature space (a straight line/plane) — logistic regression just wraps that linear boundary in a probability interpretation.

Fails when: classes aren't linearly separable — logistic regression draws one straight boundary, so an XOR-like or ring-shaped class pattern will confuse it unless you add interaction/polynomial terms.

Explain to a stakeholder: "The model outputs a probability of churn, e.g. 73%, not just yes/no — so we can prioritize outreach by risk level."

K-Nearest Neighbors (KNN)

Classifies a new point by majority vote among its k closest training points (by distance, usually Euclidean).

Small k (e.g. k=1)

Very flexible, jagged decision boundary — low bias, high variance. Sensitive to noise; a single mislabeled neighbor can flip a prediction.

Large k

Smoother boundary, averages over more neighbors — higher bias, lower variance. Too large and it starts ignoring local structure, underfitting toward the majority class.

Practical note: k is usually picked via cross-validation; odd k avoids ties in binary classification. Also requires feature scaling — distances are meaningless if features are on different scales.

Fails when: high-dimensional data ("curse of dimensionality" — distances become less meaningful as dimensions grow) or large datasets (prediction requires scanning many/all points, so it's slow at inference time).

Decision Trees

Splits data recursively on the feature/threshold that best separates classes, forming a tree of if/else rules.

Gini vs Entropy

Gini Impurity

Measures how often a randomly picked element would be misclassified if labeled randomly according to the node's class distribution. Faster to compute — the default in most libraries (e.g. sklearn's CART).

Entropy (Information Gain)

Measures disorder/uncertainty in a node; splits chosen to maximize information gain. Slightly more computationally expensive (uses logs); in practice gives very similar trees to Gini.

Overfitting: an unrestricted tree keeps splitting until nodes are pure — effectively memorizing training data (very deep tree, tiny leaf nodes). Fix with max_depth, min_samples_leaf/split, pruning, or by moving to an ensemble (Random Forest/Gradient Boosting).

Explain to a stakeholder: "The model follows readable rules, like 'if income is above $50k and age is under 30, predict approve' — we can literally show the decision path for any prediction."

Naive Bayes

Applies Bayes' theorem to compute P(class | features), assuming every feature is conditionally independent given the class — the "naive" assumption.

Why it still works despite a false assumption: classification only needs the correct class to get the highest score, not perfectly calibrated probabilities. Even when features are correlated, the ranking of classes often still comes out right, so accuracy holds up even though the assumption is technically wrong.

Great for: text classification (spam detection, sentiment) — high-dimensional, sparse features where independence is a "good enough" approximation.
Fast to train — just counts/frequencies, no iterative optimization.
Needs little data relative to more complex models.

Fails when: features are strongly correlated and that correlation carries real signal the model needs (not just for ranking) — or continuous features are far from the assumed distribution (e.g. Gaussian NB on multimodal data).

Support Vector Machines (SVM)

Finds the hyperplane that separates classes with the maximum margin — the widest possible gap between the boundary and the nearest points of each class (the "support vectors").

Kernel trick (intuition, not derivation)

When classes aren't linearly separable in the original space, the kernel trick implicitly maps points into a higher-dimensional space where a straight-line separator exists — without ever explicitly computing that transformation. Common kernels: linear, polynomial, RBF (Gaussian).

Everyday picture: two colors of dots mixed in a ring pattern on a flat table can't be split by a straight line — but lift the inner dots up (like squeezing the table into a cone) and a flat plane can now separate them cleanly. The kernel does that "lifting" mathematically.

Fails when: data is very large (training scales poorly, roughly O(n²)–O(n³)) or very noisy with overlapping classes — margin-based fitting struggles when there's no clean gap to maximize.

Evaluation, Deeply

Confusion matrix

Pred: Positive

Pred: Negative

Actual: Positive

Actual: Negative

Metric	Formula (intuition)	Answers
Precision	TP / (TP + FP)	Of everything I flagged positive, how much was actually positive?
Recall	TP / (TP + FN)	Of all actual positives, how many did I catch?
F1	Harmonic mean of precision & recall	A single number balancing both — punishes a big gap between them.

The trade-off: raising the classification threshold usually increases precision but drops recall (you're pickier, so you catch fewer positives but are more confident about the ones you do flag) — and vice versa. F1 is useful when you need one number, but the right threshold really depends on which error costs more.

Explain to a stakeholder: "Precision is 'when we say fraud, how often are we right' — recall is 'of all the actual fraud, how much did we catch.' Higher precision means fewer false alarms; higher recall means catching more real fraud but more false alarms too."

ROC-AUC vs PR curve

ROC-AUC

Plots True Positive Rate vs False Positive Rate across thresholds. Good default for roughly balanced classes.

PR Curve

Plots Precision vs Recall across thresholds. Preferred for imbalanced data — ROC-AUC can look deceptively high when negatives vastly outnumber positives, since FPR stays low even with many false positives in absolute terms.

Threshold tuning

The default 0.5 cutoff is arbitrary — pick a threshold based on the real cost of false positives vs false negatives. E.g. in cancer screening, missing a real case (FN) is far worse than a false alarm (FP), so lower the threshold to boost recall even at the cost of precision.

sklearn: Fit + Classification Report

from sklearn.linear_model import LogisticRegression
from sklearn.metrics import classification_report
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42)

model = LogisticRegression()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)

print(classification_report(y_test, y_pred))
# prints precision, recall, f1-score, support per class

★

Which Algorithm for Which Scenario

Scenario	Good fit	Why
Need interpretable, explainable output for stakeholders	Logistic Regression, Decision Tree	Coefficients / if-else rules are easy to explain in plain language.
Small dataset, few features	KNN, Naive Bayes, Logistic Regression	Don't need huge data to estimate few/simple parameters.
Text classification / spam / sentiment	Naive Bayes, Logistic Regression	Handle high-dimensional sparse features well and train fast.
Non-linear decision boundary, structured/tabular data	Decision Tree, SVM (RBF kernel), or ensembles	Can capture curves/interactions a linear model would miss.
High-dimensional data with clear margin between classes	SVM	Margin maximization tends to generalize well when a real gap exists.
Need probability estimates, not just labels	Logistic Regression, Naive Bayes	Naturally output calibrated-ish probabilities (logistic regression more so).
Very large dataset, need fast inference	Logistic Regression, Naive Bayes	KNN and SVM both get slow to predict on at scale.
Imbalanced classes, cost of false negatives is high	Any model + threshold tuning / class weights	The algorithm matters less here than tuning the threshold and using PR-AUC to evaluate.
Baseline / quick benchmark before trying complex models	Logistic Regression	Fast, well-understood, gives a sanity-check number to beat.