Classification Algorithms

Introduction and Context

Classification is the supervised-learning task of assigning an observation to one of two or more predefined classes. A credit applicant may be classified as likely or unlikely to default, a transaction as fraudulent or legitimate, or a customer as likely or unlikely to churn. Unlike regression, whose output is usually numerical, classification produces a categorical decision, often supported by a probability or score.

Classification is central to business analytics because many managerial actions are discrete: approve or reject, intervene or do not intervene, retain or discontinue, inspect or release. However, the technically most accurate classifier is not automatically the most valuable. Model selection must consider probability quality, decision boundaries, class imbalance, unequal error costs, interpretability, computational requirements, and regulatory obligations.

This chapter compares logistic regression, naïve Bayes, discriminant analysis, k-nearest neighbours (k-NN), and support vector machines (SVMs). The comparison emphasizes four questions:

1. How does each algorithm represent evidence for a class?
2. What shape of decision boundary can it learn?
3. Does it provide a meaningful probabilistic output?
4. How should its predictions be converted into business decisions when class costs differ?

Learning Objectives

After studying this chapter, the reader should be able to:

• explain the distinction between class labels, scores, and posterior probabilities;
• derive and interpret the logistic regression model;
• explain the conditional-independence assumption of naïve Bayes;
• compare linear and quadratic discriminant analysis;
• describe the geometric and operational logic of k-NN;
• explain maximum-margin classification and kernel methods in SVMs;
• select suitable metrics and thresholds for unequal class costs;
• compare the five algorithms in business settings;
• identify limitations, ethical risks, and governance requirements in classification projects.

Classification Foundations

Let x denote a vector of predictor variables and let Y denote a class label. In binary classification, Y ∈ {0,1}. A classifier estimates either a class directly or a conditional probability such as P(Y=1|x). A decision rule then maps this estimate to an action.

The distinction between prediction and decision is fundamental. If a bank estimates a 0.30 probability of default, that estimate does not by itself determine whether the application should be rejected. The appropriate action depends on the financial loss from approving a risky applicant, rejecting a safe applicant, and other operational consequences.

For a binary classifier, the confusion matrix is:

Important measures include:

Accuracy is informative when class proportions and error costs are reasonably balanced. Precision answers: among predicted positives, how many are truly positive? Recall answers: among actual positives, how many were detected? Specificity measures the correct identification of negatives. All denominators must be nonzero, and the metrics are proportions rather than percentages unless multiplied by 100.

A receiver operating characteristic (ROC) curve plots recall against false-positive rate as the decision threshold varies. The false-positive rate is FP/(FP+TN). The area under the ROC curve (AUC) measures ranking discrimination across thresholds, but it does not by itself establish probability calibration or business value. For rare events, precision–recall curves can be more informative because they focus on the positive class.

Logistic Regression

Model and interpretation

Logistic regression models the log-odds of the positive class as a linear function of predictors:

Here, β₀ is the intercept, β_j is the coefficient of predictor x_j, and p is the number of predictors. Solving for the probability gives the logistic function:

The output is constrained to the interval [0,1]. A one-unit increase in x_j, holding other variables constant, changes the log-odds by β_j and multiplies the odds by exp(β_j). This interpretation assumes that the predictor is measured in the stated units and that the linearity assumption applies to the log-odds, not necessarily to the probability itself.

For a default model, if β_income = -0.04 per thousand currency units, an increase of one thousand units multiplies the odds of default by exp(-0.04) ≈ 0.961. This is an association conditional on the included variables, not automatically a causal effect.

Estimation and assumptions

Parameters are commonly estimated by maximum likelihood. For observations (x_i,y_i), where y_i ∈ {0,1}, the likelihood is:

where p_i = P(Y=1|x_i). The log-likelihood is maximized numerically. In practice, regularization may be added. L₂ regularization discourages large coefficients, while L₁ regularization can produce sparse models by shrinking some coefficients to zero. The penalty strength must be selected using validation data or cross-validation.

Logistic regression assumes independent observations, a correctly specified outcome definition, an appropriate relationship between predictors and log-odds, and no severe uncontrolled multicollinearity. It does not require predictors to be normally distributed. Continuous nonlinear effects can be represented with transformations, splines, or carefully chosen interaction terms.

Decision boundary and probability quality

With a threshold of 0.5, the positive class is selected when β₀ + βᵀx ≥ 0. Thus, the boundary is a hyperplane. Logistic regression is therefore a linear classifier in the original feature space, although transformed features can create nonlinear boundaries in the original variables.

Logistic regression often provides useful probabilities, especially when the model is well specified and calibrated. Calibration should nevertheless be assessed using reliability plots, calibration error, or a calibration model. A high AUC does not guarantee calibrated probabilities.

Naïve Bayes

Bayes’ rule and the independence assumption

Naïve Bayes applies Bayes’ rule:

where k identifies a class, P(Y=k) is the prior probability, P(x|Y=k) is the class-conditional likelihood, and P(x) is the evidence. Since the evidence is common across classes, classification can compare P(Y=k)P(x|Y=k) across classes.

The naïve assumption is conditional independence of predictors given the class:

This assumption is often false, especially when variables are correlated. Yet the classifier can still perform well because accurate ranking does not require a perfectly realistic joint distribution in every application.

Variants and smoothing

Gaussian naïve Bayes models a continuous predictor as normally distributed within each class. Multinomial naïve Bayes is widely used for word counts, while Bernoulli naïve Bayes uses binary occurrence indicators. For count data, zero frequencies can make a class likelihood zero. Laplace smoothing replaces a raw count with a positive adjusted count, preventing a single unseen feature from eliminating a class entirely. The smoothing parameter must be selected thoughtfully; excessive smoothing can erase meaningful differences.

Probabilities should generally be computed on the log scale:

This avoids numerical underflow when many small probabilities are multiplied. Naïve Bayes is fast, requires relatively little training data, and is especially effective for high-dimensional sparse text. Its posterior probabilities, however, can be poorly calibrated because the independence assumption often causes evidence to be counted repeatedly.

Decision boundaries

With Gaussian class-conditional distributions, the boundary may be quadratic if each class has its own covariance matrix. Under a shared covariance structure, it becomes linear, linking naïve Bayes conceptually to linear discriminant analysis. Thus, the apparent simplicity of naïve Bayes does not imply that all of its boundaries are linear.

Discriminant Analysis

Discriminant analysis models the distribution of predictors within each class and uses Bayes’ rule for classification. The most common forms are linear discriminant analysis (LDA) and quadratic discriminant analysis (QDA).

LDA

LDA assumes that each class has a multivariate normal distribution with its own mean vector but a common covariance matrix:

Here, μ_k is the mean vector for class k, and Σ is the shared covariance matrix. The discriminant score, omitting terms common to all classes, is:

where π_k is the prior probability of class k. The class with the largest score is selected. Because the quadratic terms in x cancel under a common covariance matrix, LDA has a linear decision boundary.

LDA can be effective when class distributions are approximately elliptical and covariance structures are similar. It can be more statistically efficient than flexible methods when sample sizes are modest and assumptions are credible. However, covariance estimation becomes unstable when the number of predictors is large relative to the sample size. Regularized or shrinkage discriminant analysis can help.

QDA

QDA permits a separate covariance matrix for every class:

Its discriminant score includes a quadratic term:

QDA can represent curved boundaries and is more flexible than LDA, but it estimates more parameters and therefore has greater variance. It is vulnerable to singular or poorly estimated covariance matrices, particularly with small samples, redundant features, or high dimensionality.

Both LDA and QDA can produce posterior probabilities if the distributional assumptions and priors are appropriately estimated. Probability quality should be validated rather than presumed.

k-Nearest Neighbours

Principle

k-NN is a nonparametric, instance-based method. To classify a new point, it identifies the k training observations closest to it and assigns the majority class. A distance-weighted version gives nearer observations greater influence.

For numerical features, the Euclidean distance between points x and z is:

This distance is meaningful only when feature scales are comparable and the variables’ measurement properties justify the metric. Standardization is therefore usually essential. Categorical variables require suitable encodings or alternative distances.

Selecting k and estimating probabilities

Small k produces flexible, jagged boundaries and low bias but high variance. Large k produces smoother boundaries and may overlook local structure. The value of k should be selected using validation or cross-validation, with the evaluation metric aligned to the business objective.

A simple probability estimate is the proportion of positive neighbours:

This estimate is discrete and can be unstable for small k. Distance weighting can improve local discrimination but does not automatically guarantee calibration.

Strengths and limitations

k-NN can discover highly nonlinear boundaries without specifying a functional form. It is easy to explain locally: a prediction is supported by similar historical cases. Its disadvantages include slow prediction when the training set is large, sensitivity to irrelevant variables and scaling, difficulty in high dimensions, and vulnerability to changing data density. The curse of dimensionality means that distances become less discriminative as dimensions increase; feature selection or dimensionality reduction may be necessary.

Support Vector Machines

Maximum-margin classification

For linearly separable data, an SVM seeks a hyperplane wᵀx+b=0 that separates classes while maximizing the margin. The margin is inversely related to ||w||, so the hard-margin optimization is:

Here, y_i ∈ {−1,+1}, w is the normal vector to the hyperplane, and b is the intercept. The constraints assume perfect separability.

Real data usually overlap. A soft-margin SVM introduces slack variables ξ_i ≥ 0:

The parameter C>0 controls the trade-off between a wide margin and training violations. A large C penalizes violations strongly and can produce a narrower, more data-fitting boundary; a small C allows more violations and emphasizes regularization.

Kernels and probability outputs

The kernel trick allows an SVM to construct nonlinear boundaries through an implicit feature mapping. A common radial basis function (RBF) kernel is:

where γ>0 controls the locality of influence. Large γ produces highly local effects and potentially complex boundaries; small γ produces smoother effects. Both C and γ should be tuned using a properly separated validation process.

The raw SVM decision function is a margin score, not a probability. Probabilities can be obtained by calibration, such as Platt scaling or isotonic regression, using data separate from the fitting data where possible. Calibration is important when predictions drive risk-based decisions rather than merely ranking cases.

SVMs can perform strongly in medium-sized, high-dimensional settings, especially with informative margins. They may be computationally expensive for very large datasets, sensitive to feature scaling, and less transparent than logistic regression. The support vectors are influential observations, but the resulting model is not always easy to communicate to stakeholders.

Decision Boundaries and Comparative View

A decision boundary is the set of predictor values at which the selected class changes. Logistic regression and LDA generally produce linear boundaries. QDA and Gaussian naïve Bayes can produce quadratic boundaries. k-NN creates locally adaptive boundaries. Linear SVM produces a hyperplane, while kernel SVM can create complex nonlinear boundaries.

No algorithm is universally superior. A useful comparison uses nested cross-validation or a separate validation set, preserves temporal order where appropriate, prevents leakage, and evaluates both discrimination and calibration.

Class Costs, Thresholds, and Business Decisions

Suppose a model estimates p=P(Y=1|x). Let C_FP be the cost of a false positive and C_FN the cost of a false negative. If the cost of taking action on a predicted positive is treated as zero or already incorporated, the expected cost of predicting positive is (1−p)C_FP, while predicting negative costs pC_FN. Predict positive when:

which is equivalent to:

This threshold applies when probabilities are calibrated, the costs are correctly specified, and class priors and operating conditions match the deployment environment. If there are explicit benefits or intervention costs, they must be included in the expected-utility calculation. In multiclass problems, the decision should minimize expected cost across all possible actions, not merely select the class with the largest probability.

Class weighting changes the fitting objective so that errors in an important class receive greater influence. It is not identical to changing the final decision threshold. Resampling changes the training distribution and can affect probability interpretation; predicted probabilities may need prior-probability correction or recalibration.

Worked Example: A Cost-Sensitive Churn Decision

Assume a calibrated model estimates that a customer has a 0.18 probability of churn. A retention offer costs £12 if sent to a customer who would not churn, while failing to intervene with a customer who would churn has an estimated cost of £60. The cost-sensitive threshold is:

Because 0.18 exceeds 0.167, the customer should receive the offer under this simplified cost model. The expected cost of offering is:

The expected cost of not offering is:

The offer is preferred by £0.96 per customer. This conclusion would change if the offer produced retention benefits, if costs varied by customer, or if the probability were poorly calibrated. The example illustrates why a fixed threshold of 0.5 can be economically irrational.

Illustrative Business Case: Fraud Screening for an Online Retailer

Background and problem

An online retailer processes millions of card-not-present transactions. Fraud is rare, but each confirmed fraudulent transaction causes chargeback losses, investigation costs, and possible customer dissatisfaction. Automatically blocking legitimate customers also imposes revenue and reputational costs.

Analysis

The analytics team defines the positive class as “transaction subsequently confirmed as fraudulent.” Candidate variables include transaction amount, time, device history, account age, geographic consistency, and velocity measures. Leakage controls are essential: a variable that becomes available only after an investigation cannot be used at authorization time.

The team compares logistic regression, naïve Bayes, LDA, k-NN, and an RBF SVM. Logistic regression is selected as a transparent baseline. Naïve Bayes is tested because some event and text-like indicators are sparse. LDA is considered as a compact distributional model, while QDA is rejected after unstable covariance estimates. k-NN performs poorly because the feature space is high dimensional and fraud patterns are sparse. The SVM obtains strong ranking performance but requires calibration and is computationally more demanding.

Approach and solution

The data are split chronologically to reflect deployment. Preprocessing, scaling, feature selection, and hyperparameter tuning are fitted only on the training period. The models are assessed using precision–recall curves, recall at a fixed review capacity, expected cost, calibration, and stability across time. Because false negatives are expensive but manual review capacity is limited, the operating threshold is chosen using an expected-cost and capacity analysis rather than accuracy.

The retailer uses a two-stage process: high-confidence legitimate transactions are approved automatically; high-risk transactions are declined or held; an intermediate band is sent for review. A calibrated logistic model is used for the principal score because its probabilities and feature effects can be communicated to compliance and operations teams. An SVM score is retained as a challenger model and monitored for incremental value.

Outcome

The key outcome is not merely a higher AUC. The system reduces expected fraud loss while keeping review volume within staffing limits and monitoring legitimate-customer friction. Thresholds are recalculated when fraud prevalence, payment methods, or review costs change. Model outputs are logged so that decisions can be audited.

Learning points

• Rare-event classification requires metrics beyond accuracy.
• Temporal validation is more realistic than random splitting when behaviour changes.
• Probability calibration and threshold selection are separate from model training.
• A slightly less accurate but transparent model may be preferable when decisions are consequential.
• Fraud models require continuous drift, fairness, and feedback-loop monitoring.

Implementation and Governance Best Practices

A robust classification workflow begins with a precise target definition and a decision owner. Analysts should document the prediction time, outcome window, eligible population, data provenance, missing-value treatment, transformations, and cost assumptions. All preprocessing must be learned within training folds to prevent leakage.

For imbalanced data, report the class prevalence, confusion matrix, precision, recall, specificity, PR-AUC, calibration, and business cost. Select metrics before examining results where feasible. Confidence intervals or repeated resampling can reveal whether apparent model differences are meaningful.

Fairness analysis should examine error rates, calibration, selection rates, and other relevant measures across legally or ethically protected groups. These criteria can conflict mathematically; therefore, the organization must articulate which harms it prioritizes and why. Sensitive variables may be excluded from prediction but still needed for fairness auditing, subject to law and governance policy.

Classification systems can create automation bias, deny access to services, or reinforce historical discrimination. Human review should be meaningful rather than nominal. Individuals may require notice, explanation, contestability, and correction mechanisms, particularly in credit, employment, insurance, healthcare, and public-sector applications. Data minimization, access controls, retention limits, and secure logging are part of model quality, not administrative extras.

Challenges and Contemporary Developments

Concept drift occurs when the relationship between predictors and outcomes changes. Prior-probability drift occurs when class prevalence changes, while concept drift changes P(Y|x). Monitoring should distinguish these cases because recalibration may address prior drift, whereas concept drift may require retraining or redesign.

Modern systems often combine interpretable baselines with ensemble or deep-learning challengers. Explainability tools can describe local or global patterns, but explanations are approximations and should not be treated as causal accounts. Conformal prediction and selective classification can provide uncertainty sets or allow a system to abstain when confidence is inadequate. Privacy-preserving learning, federated approaches, and fairness-aware optimization are active areas of research, but they introduce additional assumptions and operational complexity.

Chapter Summary

Classification algorithms estimate class membership and support decisions under uncertainty. Logistic regression models linear log-odds and is often a strong, interpretable baseline. Naïve Bayes uses Bayes’ rule with conditional independence and is fast, particularly for sparse data, but its probabilities may be poorly calibrated. LDA assumes class-specific means and a common covariance matrix, producing linear boundaries; QDA allows separate covariance matrices and curved boundaries at the cost of greater estimation variance. k-NN makes local, nonparametric decisions and is sensitive to scaling, feature selection, and dimensionality. SVMs maximize a separating margin, can use kernels for nonlinear boundaries, and produce scores that require calibration when probabilities are needed.

Model evaluation must distinguish discrimination, calibration, and decision utility. Accuracy alone is often inadequate, especially for rare classes. Thresholds should reflect calibrated probabilities, false-positive and false-negative costs, intervention capacity, and regulatory requirements. Responsible deployment requires leakage prevention, temporal validation where appropriate, fairness assessment, monitoring for drift, documentation, security, and human accountability.

Key Terms

Classification: Assigning observations to predefined categories.

Class probability: Estimated conditional probability of an observation belonging to a class.

Decision boundary: Set of predictor values at which the predicted class changes.

Log-odds: The logarithm of the odds of an event.

Logistic regression: A model that represents binary log-odds as a function of predictors.

Naïve Bayes: A Bayesian classifier using conditional independence of predictors given the class.

Prior probability: Probability assigned to a class before observing predictors.

Likelihood: Probability of observed predictors conditional on a class.

LDA: Discriminant analysis with a common covariance matrix across classes.

QDA: Discriminant analysis with a separate covariance matrix for each class.

k-NN: An instance-based method using the classes of nearby observations.

Support vector machine: A margin-based classifier that can use kernel functions.

Kernel: A function representing similarity in an implicit feature space.

Calibration: Agreement between predicted probabilities and observed frequencies.

Precision: Proportion of predicted positives that are actual positives.

Recall: Proportion of actual positives that are detected.

Class imbalance: Unequal prevalence of classes in the data.

Cost-sensitive classification: Classification in which errors or actions have unequal costs.

Data leakage: Use of information unavailable at prediction time or improperly shared across validation sets.

Concept drift: Change over time in the relationship between predictors and outcomes.

Review Questions

Short Answer Questions

1. Distinguish a class probability from a classification decision.
2. What does a logistic regression coefficient represent in odds terms?
3. State the conditional-independence assumption of naïve Bayes.
4. Why should features usually be scaled before applying k-NN or an SVM?
5. Why is an SVM decision score not automatically a probability?

Long Answer Questions

1. Compare logistic regression, LDA, and QDA in terms of assumptions, decision boundaries, estimation, and interpretability.
2. Explain how naïve Bayes can perform well even when its independence assumption is unrealistic.
3. Discuss the bias–variance implications of choosing a small versus large value of k in k-NN.
4. Explain soft-margin SVM optimization and the roles of C and the kernel parameter γ.
5. Design an evaluation framework for a rare-event classification problem in a regulated industry.

Analytical / Application Questions

1. A medical screening model has a false-positive cost of 5 units and a false-negative cost of 45 units. Derive the probability threshold under the simplified cost model and explain two reasons why the operational threshold may differ.
2. A retailer’s k-NN model performs well on a two-feature validation set but poorly after ten additional variables are added. Diagnose the likely causes and propose a revised workflow.
3. A calibrated fraud model has excellent AUC but produces too many false alarms for a fixed investigation team. Explain how threshold selection, calibration, capacity constraints, and cost analysis should be combined to redesign the system.

Multiple Choice Questions with Answers

Question 1

Which statement best describes the decision boundary of standard logistic regression using the original predictors?

A. It is generally a linear hyperplane.

B. It is always a circular boundary.

C. It is determined only by nearest observations.

D. It is undefined because logistic regression produces probabilities.

Correct Answer: A. It is generally a linear hyperplane.

Question 2

What is the central simplifying assumption of naïve Bayes?

A. All classes have identical prior probabilities.

B. Predictors are conditionally independent given the class.

C. All predictors must be normally distributed overall.

D. The decision boundary must be nonlinear.

Correct Answer: B. Predictors are conditionally independent given the class.

Question 3

LDA differs from QDA primarily because LDA assumes that classes have:

A. Different numbers of observations.

B. A common covariance matrix.

C. No prior probabilities.

D. Only categorical predictors.

Correct Answer: B. A common covariance matrix.

Question 4

Why is feature scaling especially important for k-NN?

A. Scaling changes the target labels.

B. Distance calculations can otherwise be dominated by large-unit variables.

C. Scaling guarantees perfect calibration.

D. Scaling removes the need to select k.

Correct Answer: B. Distance calculations can otherwise be dominated by large-unit variables.

Question 5

In a soft-margin SVM, increasing C generally:

A. Places greater penalty on margin violations.

B. Forces all probabilities to sum to zero.

C. Eliminates the kernel function.

D. Makes every boundary linear.

Correct Answer: A. Places greater penalty on margin violations.

Question 6

A calibrated binary model has false-positive cost 10 and false-negative cost 30, with no other costs. What probability threshold follows from p* = C_FP/(C_FP+C_FN)?

A. 0.10

B. 0.25

C. 0.50

D. 0.75

Correct Answer: B. 0.25

Question 7

Which metric answers the question, “Among observations predicted positive, what proportion is actually positive?”

A. Recall

B. Specificity

C. Precision

D. Accuracy

Correct Answer: C. Precision

Question 8

Why might an SVM require probability calibration before being used for expected-cost decisions?

A. Its raw output is normally a margin score rather than a probability.

B. It cannot classify binary outcomes.

C. It always assumes equal class costs.

D. Its support vectors are missing labels.

Correct Answer: A. Its raw output is normally a margin score rather than a probability.

Question 9

For a rare fraud class, which evaluation approach is generally more informative than accuracy alone?

A. Report only the majority-class proportion.

B. Use precision, recall, precision–recall analysis, calibration, and expected cost.

C. Ignore the confusion matrix.

D. Use training accuracy as the deployment estimate.

Correct Answer: B. Use precision, recall, precision–recall analysis, calibration, and expected cost.

Question 10

A model has TP = 80 and FN = 20. What is its recall?

A. 20%

B. 40%

C. 80%

D. 100%

Correct Answer: C. 80%