Classification Algorithms

Classification Overview

Classification assigns an input to one of K discrete categories. When K=2 it is binary classification; when K>2 it is multiclass (or multilabel if multiple classes can be true simultaneously).

The model learns a decision boundary in feature space. Points on one side map to one class, points on the other side to another. The shape and nature of that boundary is what distinguishes algorithms.

Logistic Regression

Despite the name, logistic regression is a classification model. It models the probability of the positive class via the sigmoid function:

P(y=1 | x) = σ(θᵀx) = 1 / (1 + e^(−θᵀx))

Decision boundary: P(y=1|x) = 0.5 ↔ θᵀx = 0 → a linear hyperplane.

Loss (binary cross-entropy):

L(θ) = −(1/n) Σᵢ [yᵢ log ŷᵢ + (1−yᵢ) log(1−ŷᵢ)]

No closed form — optimized with gradient descent or L-BFGS.

Multiclass extension: softmax regression (multinomial logistic regression):

P(y=k | x) = exp(θₖᵀx) / Σⱼ exp(θⱼᵀx)

from sklearn.linear_model import LogisticRegression

model = LogisticRegression(
    C=1.0,              # inverse regularization strength (1/λ)
    penalty="l2",       # l1, l2, elasticnet, none
    solver="lbfgs",     # for multiclass
    multi_class="auto",
    max_iter=1000
)
model.fit(X_train, y_train)
probs = model.predict_proba(X_test)   # shape (n_samples, n_classes)
preds = model.predict(X_test)

Strengths: fast, interpretable coefficients, calibrated probabilities, good baseline. Weaknesses: assumes linear boundary, sensitive to unscaled features.

Decision Trees

A decision tree recursively partitions the feature space with axis-aligned splits. Each internal node tests one feature against a threshold; each leaf predicts a class.

Splitting Criteria

Gini impurity (default in sklearn):

Gini(S) = 1 − Σₖ pₖ²

Information gain (entropy-based):

Entropy(S) = −Σₖ pₖ log₂ pₖ

The split is chosen to maximize information gain = parent impurity − weighted child impurity.

Tree Parameters

from sklearn.tree import DecisionTreeClassifier, plot_tree
import matplotlib.pyplot as plt

tree = DecisionTreeClassifier(max_depth=5, min_samples_leaf=10)
tree.fit(X_train, y_train)

# Visualize
plt.figure(figsize=(20, 10))
plot_tree(tree, feature_names=feature_names,
          class_names=class_names, filled=True)
plt.show()

Strengths: interpretable, no scaling needed, handles mixed types. Weaknesses: high variance (small data change = very different tree), rectangular-only boundaries.

Random Forests

An ensemble of decision trees trained on bootstrap samples of the training data (bagging), with each tree considering only a random subset of features at each split. Final prediction: majority vote (classification) or mean (regression).

Why it works: individual trees overfit differently; averaging uncorrelated errors reduces variance.

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=200,
    max_features="sqrt",
    min_samples_leaf=2,
    n_jobs=-1,
    random_state=42
)
rf.fit(X_train, y_train)

# Feature importance
importances = rf.feature_importances_
sorted_idx = importances.argsort()[::-1]

Strengths: robust, handles missing features, built-in feature importance, parallelizable. Weaknesses: slower than single tree, less interpretable, can overfit on noisy data.

Support Vector Machines (SVM)

SVM finds the maximum-margin hyperplane separating classes. The boundary is defined entirely by support vectors — the training points closest to the boundary.

Hard margin (linearly separable):

Maximize margin = 2/‖w‖ subject to yᵢ(wᵀxᵢ + b) ≥ 1 ∀i

Soft margin (allows misclassifications via slack ξᵢ):

Minimize (1/2)‖w‖² + C Σᵢ ξᵢ

C is the regularization parameter: small C = wider margin, more misclassifications allowed; large C = small margin, fewer misclassifications.

Kernel Trick

Map data to a high-dimensional feature space ϕ(x) without computing ϕ explicitly, using a kernel function K(xᵢ, xⱼ) = ϕ(xᵢ)ᵀϕ(xⱼ):

from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler

# SVM requires scaling!
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

svm = SVC(kernel="rbf", C=10, gamma="scale",
          probability=True)  # enable for predict_proba
svm.fit(X_train_s, y_train)

Strengths: effective in high dimensions, kernels handle nonlinearity, memory-efficient (only store support vectors). Weaknesses: slow on large datasets (O(n²–n³)), requires scaling, C and γ tuning, poor probability calibration.

k-Nearest Neighbors (k-NN)

No training phase. At inference, classify a new point by majority vote of its k nearest training points (measured by distance).

Distance metrics: - Euclidean: d = √Σ(xᵢ−yᵢ)² (most common) - Manhattan: d = Σ|xᵢ−yᵢ| - Cosine: 1 − (x·y)/(‖x‖‖y‖) (for text)

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(
    n_neighbors=5,
    weights="uniform",    # or "distance" (closer points get more weight)
    metric="euclidean",
    algorithm="auto"      # kdtree/balltree for large d
)
knn.fit(X_train, y_train)

Choosing k: low k = high variance (overfits); high k = high bias (underfits). Cross-validate.

Strengths: simple, no assumptions, naturally handles multiclass, adapts to new data without retraining. Weaknesses: O(nd) inference time, O(nd) storage, suffers in high dimensions (curse of dimensionality), requires scaling.

Naive Bayes

Applies Bayes' theorem with the naive assumption that features are conditionally independent given the class:

P(y=k | x) ∝ P(y=k) · Πⱼ P(xⱼ | y=k)

Despite the unrealistic independence assumption, Naive Bayes works surprisingly well for text classification.

Variants

from sklearn.naive_bayes import GaussianNB, MultinomialNB
from sklearn.feature_extraction.text import TfidfVectorizer

# Multinomial NB for text
vectorizer = TfidfVectorizer()
X_vec = vectorizer.fit_transform(texts)
nb = MultinomialNB(alpha=1.0)  # alpha = Laplace smoothing
nb.fit(X_vec, y)

# Gaussian NB for continuous features
gnb = GaussianNB()
gnb.fit(X_train, y_train)

Strengths: extremely fast training and inference, works well on small data, handles high-dimensional data, easy to update with new data. Weaknesses: independence assumption often violated, poor probability estimates, can be outperformed by most algorithms on tabular data.

Gradient Boosting Classifiers

Build an additive ensemble of weak learners (usually shallow trees) where each tree corrects the errors of the previous ensemble:

F_m(x) = F_{m-1}(x) + α · hₘ(x)

where hₘ is fit to the negative gradient of the loss (pseudo-residuals).

import xgboost as xgb

xgb_clf = xgb.XGBClassifier(
    n_estimators=500,
    learning_rate=0.05,
    max_depth=6,
    min_child_weight=1,
    subsample=0.8,
    colsample_bytree=0.8,
    scale_pos_weight=1,   # for imbalanced (negative/positive ratio)
    use_label_encoder=False,
    eval_metric="logloss",
    random_state=42
)
xgb_clf.fit(X_train, y_train,
             eval_set=[(X_test, y_test)],
             early_stopping_rounds=20, verbose=False)

Algorithm Comparison

Multiclass Strategies

When an algorithm natively supports only binary classification:

• One-vs-Rest (OvR): train K binary classifiers, each separating class k from all others. Predict the class with highest confidence.
• One-vs-One (OvO): train K(K−1)/2 classifiers, one per pair. Majority vote.

from sklearn.multiclass import OneVsRestClassifier, OneVsOneClassifier
from sklearn.svm import SVC

ovr = OneVsRestClassifier(SVC(kernel="rbf"))
ovr.fit(X_train, y_train)

ovo = OneVsOneClassifier(SVC(kernel="rbf"))
ovo.fit(X_train, y_train)

Decision Thresholds

By default, classifiers predict the class with probability > 0.5. Adjusting the threshold trades precision for recall:

from sklearn.metrics import precision_recall_curve

probs = model.predict_proba(X_test)[:, 1]

# Custom threshold
threshold = 0.3   # lower threshold = higher recall, lower precision
y_pred_custom = (probs >= threshold).astype(int)

# Plot precision-recall curve
precision, recall, thresholds = precision_recall_curve(y_test, probs)

Use case: fraud detection → lower threshold (catch more fraud at cost of more false alarms). Medical diagnosis → often tune based on clinical context.