Classification Methods

Introduction

Classification is a supervised data-mining task in which a model learns from examples whose class labels are known and then assigns labels to previously unseen observations. Typical problems include identifying fraudulent transactions, diagnosing diseases, filtering spam, predicting customer churn, and recognizing objects in images. Unlike regression, which predicts a numerical quantity, classification predicts a categorical outcome such as fraudulent/non-fraudulent or low/medium/high risk.

A classification dataset consists of observations described by input attributes and an outcome variable called the class, target, or label. A model attempts to learn a function

where X is the feature space and Y is the set of possible classes. For an observation x, the model produces either a predicted class ŷ or a probability distribution over classes.

Classification is central to data mining because many organizational decisions are categorical. However, a useful classifier must do more than achieve high accuracy on historical data. It should generalize to new cases, use information appropriately, remain computationally feasible, and provide explanations suitable for the application domain.

Learning Objectives

After studying this chapter, you should be able to:

• explain the classification problem and distinguish training, validation, and test data;
• construct and interpret decision trees and rule-based classifiers;
• describe the assumptions and operation of naïve Bayes, logistic regression, k-nearest neighbors, support vector machines, and neural networks;
• select suitable evaluation measures for binary and multiclass classification;
• compare classifiers according to assumptions, interpretability, scalability, and predictive performance;
• identify overfitting, data leakage, class imbalance, and ethical risks;
• design a defensible classification workflow for a practical application.

1. Foundations of Classification

1.1 Supervised learning formulation

Let a dataset contain n labeled observations:

Here, x_i is the feature vector for observation i and y_i is its class label. In binary classification, y_i commonly belongs to {0, 1}; in multiclass classification, it belongs to one of K classes. The training objective is to estimate a model from D that performs well on observations not used to fit it.

A dataset is commonly divided into:

• Training set: used to estimate model parameters.
• Validation set: used to select algorithms, hyperparameters, or decision thresholds.
• Test set: reserved for final, unbiased performance estimation.

When data are limited, k-fold cross-validation divides the training data into k folds. Each fold is used once for validation while the remaining folds are used for fitting. The reported score is usually the mean across folds. The test set must not be repeatedly consulted during model development.

1.2 Decision boundaries and probabilities

A classifier separates the feature space into regions associated with different classes. The boundary between two regions is a decision boundary. A linear classifier produces a boundary of the form:

where w is a vector of feature weights and b is an intercept. Nonlinear classifiers can create curved, fragmented, or highly complex boundaries.

A probabilistic classifier estimates P(Y = c | X = x), the probability that an observation with features x belongs to class c. The usual prediction rule is maximum a posteriori classification:

This rule is appropriate when all classification errors have equal cost. In applications such as medical screening or fraud detection, the threshold may instead be adjusted to reflect unequal costs.

1.3 Confusion matrix and evaluation

For binary classification, predictions can be summarized using:

Important measures are:

Accuracy is the proportion of all predictions that are correct. Precision measures how many predicted positives are truly positive; recall, also called sensitivity, measures how many actual positives are detected. Specificity measures how many actual negatives are correctly rejected. F1 is the harmonic mean of precision and recall and is useful when the positive class is important and class frequencies are unequal.

For probability predictions, the receiver operating characteristic (ROC) curve plots recall against false-positive rate as the classification threshold changes. The area under this curve, ROC–AUC, measures ranking ability across thresholds. Precision–recall curves are often more informative when the positive class is rare. A model with good discrimination may still be poorly calibrated. Calibration asks whether cases assigned probability 0.8 are positive approximately 80% of the time.

2. Decision Trees

A decision tree classifies an observation by following a sequence of tests from a root node to a leaf. Internal nodes contain feature-based decisions, branches represent outcomes, and leaves contain predicted classes or class probabilities.

2.1 Impurity and splitting

A common impurity measure is Gini impurity:

where S is a node, K is the number of classes, and p_c is the proportion of observations in S belonging to class c. Gini impurity is zero when a node contains one class only and is larger when classes are mixed.

Entropy is another measure:

The convention 0 log₂ 0 = 0 is used. Information gain for a split is:

where I is impurity, S_j are child nodes, m is the number of children, and |S| denotes the number of observations in a node. The selected split generally maximizes gain or, equivalently, minimizes weighted child impurity.

2.2 Construction and pruning

A greedy tree algorithm repeatedly selects the best available split. Stopping conditions may include maximum depth, minimum observations per node, or insufficient impurity reduction. A fully grown tree often fits noise in the training data. Pruning reduces complexity by removing branches that do not improve validation performance.

For a numerical feature, a threshold such as income ≤ 50,000 can be tested. For a categorical feature, a split may separate one category from the others or divide categories into groups. Modern implementations can handle missing values through surrogate splits, learned default directions, or preprocessing.

Advantages: trees are intuitive, can represent nonlinear interactions, require little scaling, and handle mixed feature types. Limitations: individual trees are unstable, greedy splitting is not globally optimal, and deep trees overfit. Random forests and gradient-boosted trees address some limitations through ensembles, although they reduce direct interpretability.

3. Rule Learners

A rule classifier expresses knowledge as conditional statements:

IF conditions THEN class.

For example:

IF account age < 30 days AND transaction amount > 2,000, THEN flag as suspicious.

A rule has coverage, the proportion of cases satisfying its conditions, and accuracy or confidence, the proportion of covered cases correctly classified. A learner may generate rules directly or convert a decision tree into rules by representing each root-to-leaf path as a rule.

Sequential covering is a common strategy. The algorithm selects a high-quality rule, removes or downweights the cases it explains, and continues until a stopping criterion is reached. A default rule assigns a class when no specific rule applies.

Rule systems are valuable where auditability and domain communication matter. They can incorporate domain knowledge and offer local explanations. However, overlapping rules may conflict, rule order becomes important, and large rule sets can be difficult to maintain. Rule quality must be evaluated on validation data rather than only on the cases used to create the rules.

4. Naïve Bayes

Bayes’ theorem gives the posterior probability of class c after observing features x:

P(c | x) is the posterior probability, P(x | c) is the likelihood, P(c) is the prior probability, and P(x) is the evidence. Since P(x) is common to all classes for a given observation, classification can use:

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

where d is the number of features. This assumption is often unrealistic—for example, words in a document are not truly independent—but the classifier can still perform well, especially in text classification.

For continuous features, a Gaussian model may be used:

where μ_{jc} and σ²_{jc} are the class-specific mean and variance of feature j. For word counts, multinomial naïve Bayes is common. Zero counts can produce zero likelihoods, so Laplace smoothing adds a small positive count. In a vocabulary of V terms, a smoothed conditional probability can be written as:

where N_{jc} is the count of word j in class c, N_c is the total word count for class c, V is vocabulary size, and α > 0 is the smoothing parameter.

Naïve Bayes is fast, works well with high-dimensional sparse data, and needs relatively little training data. Its probability estimates may be poorly calibrated, and correlated features can distort likelihood calculations.

5. Logistic Regression

Logistic regression models the probability of a binary class using the logistic function:

β₀ is the intercept and β is the coefficient vector. Equivalently, the log-odds are linear in the features:

where p = P(Y = 1 | x). A threshold, commonly 0.5 but not necessarily optimal, converts probability into a class prediction.

Coefficients describe changes in log-odds while holding other variables constant. The odds ratio associated with a one-unit increase in feature x_j is exp(β_j). This interpretation assumes the feature scale and model specification are meaningful. For nonlinear effects, transformations, polynomial terms, splines, or interactions may be introduced.

Parameters are commonly estimated by maximum likelihood. Regularization controls overfitting. With L2 regularization, a typical objective is:

where p_i is the predicted probability for observation i and λ ≥ 0 controls penalty strength. The intercept is usually excluded from the penalty. L1 regularization replaces the squared penalty with ∑|β_j| and can produce sparse coefficients.

Logistic regression is interpretable, efficient, and often well calibrated when correctly specified. It assumes a linear relationship between predictors and log-odds and can underfit complex boundaries unless suitable features are engineered.

6. k-Nearest Neighbors

The k-nearest neighbors (k-NN) method stores the training observations rather than fitting an explicit parametric model. For a new point, it identifies the k closest training points and assigns the majority class. A probability estimate may be calculated as the proportion of neighbors in each class.

A common distance is Euclidean distance:

This formula assumes numerical features and meaningful comparable scales. Standardization is therefore important. A standardized value is:

where μ_j and σ_j are the training-set mean and standard deviation for feature j. These quantities must be calculated using training data only.

Small k gives flexible boundaries but is sensitive to noise; large k produces smoother boundaries but may overlook local structure. An odd k is sometimes selected in binary classification to reduce ties, but cross-validation is the appropriate method for choosing k. k-NN can be effective for modest, well-scaled datasets, but prediction is expensive for large datasets and performance degrades in high dimensions—the curse of dimensionality. Feature selection, dimensionality reduction, or specialized indexes can help.

7. Support Vector Machines

A support vector machine (SVM) seeks a separating hyperplane with a large margin. For a linear classifier, the boundary is:

The signed distance of x from the boundary is proportional to (wᵀx + b)/||w||. The margin is maximized by minimizing ||w||² while correctly classifying training points with a required separation.

For nonseparable data, the soft-margin formulation introduces slack variables ξ_i:

subject to:

Here y_i ∈ {−1, +1}, C > 0 controls the trade-off between margin size and training violations, and ξ_i measures violation. Large C penalizes errors strongly and may produce a narrower margin; smaller C allows more violations and stronger regularization.

Nonlinear SVMs use a kernel function, such as the radial basis function (RBF):

where γ > 0 controls the local influence of a training point. The kernel trick computes inner products in an implicit feature space without explicitly constructing that space.

SVMs are powerful in high-dimensional spaces and can generalize well. They require careful scaling and tuning of C and kernel parameters. Training can be costly for very large datasets, and the resulting model is less transparent than a small tree or logistic model. Standard SVM outputs are margins rather than naturally calibrated probabilities; calibration can be applied separately.

8. Neural Networks

A neural network is composed of layers of computational units. A neuron calculates a weighted sum followed by an activation function:

where x is the input vector, w is a weight vector, b is a bias, and φ is an activation function such as ReLU, φ(a) = max(0, a), or the sigmoid function.

For binary classification, an output sigmoid can produce a probability. For K mutually exclusive classes, the softmax function is commonly used:

where a_c is the output logit for class c. The probabilities are nonnegative and sum to one.

Networks are trained by minimizing a loss, often cross-entropy. For a K-class problem with one-hot targets y_ic:

p_ic is the predicted probability for class c for observation i. Backpropagation computes gradients of the loss with respect to weights, and an optimizer updates the weights. Learning rate, batch size, number of layers, width, regularization, and number of training epochs are important hyperparameters.

Neural networks can learn highly nonlinear relationships and are particularly effective with images, audio, text, and other unstructured data. Their disadvantages include data and computational requirements, sensitivity to design choices, vulnerability to distribution shifts, and limited interpretability. Dropout, weight decay, early stopping, data augmentation, and validation monitoring can reduce overfitting.

9. Comparative Selection of Classifiers

No method is universally best. Selection should consider the data-generating process, sample size, feature types, latency requirements, interpretability, regulatory constraints, and error costs. A simple model that meets the performance requirement may be preferable to a complex model that is only marginally more accurate.

10. A Defensible Classification Workflow

1. Define the decision. Specify the target, prediction time, users, acceptable errors, and action taken after prediction.
2. Audit the data. Examine missingness, duplicates, outliers, class frequencies, label quality, and potential leakage.
3. Split appropriately. Use a time-based split for temporal prediction, a group-based split when individuals or entities recur, or stratification when class proportions must be preserved.
4. Build a baseline. Compare against majority class, prior operational rules, and a simple logistic or tree model.
5. Preprocess within the training pipeline. Imputation, scaling, feature selection, and dimensionality reduction must be fitted only on training folds.
6. Tune using validation or cross-validation. Select hyperparameters and thresholds without using the final test set.
7. Evaluate multiple measures. Report a confusion matrix and metrics appropriate to the costs and class distribution. Include confidence intervals or variation across folds where possible.
8. Inspect errors. Analyze false positives and false negatives by subgroup, time period, and data quality category.
9. Calibrate and select a threshold. A probability threshold should reflect operational costs, capacity, and risk tolerance.
10. Deploy and monitor. Track input drift, label drift, performance, calibration, latency, and fairness. Establish retraining and rollback procedures.

Worked example: threshold choice

Suppose a screening classifier produces TP = 90, FN = 10, FP = 30, and TN = 870. Then:

The model detects 90% of actual positive cases, but 25% of flagged cases are false alarms. If missing a positive case is much more costly than investigating a false alarm, this operating point may be appropriate. Otherwise, the threshold should be reconsidered rather than choosing solely by accuracy.

11. Illustrative Case: Credit-Card Fraud Screening

Background

A payment provider wants to identify potentially fraudulent transactions before authorization. Fraud is rare, legitimate customer behavior changes over time, and immediate decisions are required.

Problem

A historical dataset contains transaction amount, time, merchant category, device information, location indicators, and a fraud label determined after investigation. The provider must minimize financial losses while avoiding excessive declines of legitimate transactions.

Analysis

A random split could place transactions from the same account in both training and test data, producing overly optimistic results. A time-based split is more realistic because the model will predict future transactions. Features available only after investigation must be excluded because they cause leakage. Class imbalance means accuracy is unsuitable as the main measure; recall, precision, precision–recall AUC, financial cost, and customer-impact measures are more useful.

Approach and solution

The team first establishes a rules-based baseline, such as blocking impossible geographic travel. Logistic regression provides an interpretable baseline, while a tree ensemble or neural network is tested for nonlinear interactions. Missing-value handling and scaling are fitted inside the training pipeline. Class weights or carefully designed resampling address imbalance, but all resampling occurs within training folds.

The decision threshold is selected using an explicit cost function. If C_FN is the cost of an undetected fraud and C_FP is the cost of a false alert, an illustrative expected cost is:

This expression is a simplified operational model; real systems may include investigation costs, transaction value, customer attrition, and regulatory consequences. The selected model is calibrated, monitored by transaction segment, and reviewed by fraud analysts. High-risk predictions may trigger manual review rather than automatic rejection.

Outcome and learning points

The case demonstrates that model choice is only one part of classification. Temporal validation, leakage prevention, cost-sensitive thresholds, human review, calibration, and monitoring are equally important. A highly accurate model can still be operationally harmful if it flags too many legitimate customers or fails when fraud patterns change.

12. Limitations, Ethics, and Governance

Classification models inherit limitations in the data and labels. Historical labels may reflect inconsistent human judgments, unequal investigation effort, or institutional bias. A model may therefore reproduce or amplify inequity even when sensitive attributes are excluded, because proxy variables can carry similar information.

Important safeguards include documenting data provenance, purpose, features, preprocessing, model version, evaluation population, and known limitations. Sensitive applications may require impact assessments, human oversight, appeal mechanisms, access controls, and retention limits. Fairness should be assessed across relevant groups using measures appropriate to the context, such as error-rate comparisons or calibration analyses. These measures can conflict mathematically when base rates differ, so fairness cannot be reduced to selecting one universal metric.

Privacy must be considered during collection, storage, feature construction, and sharing. Security threats include data poisoning, evasion, model extraction, and membership inference. Explanations should be faithful to the model and meaningful to affected people; a post hoc explanation is not automatically a causal explanation.

Contemporary practice increasingly uses automated machine-learning pipelines, explainability tools, conformal prediction, and drift detection. These tools improve workflow and uncertainty communication but do not eliminate the need for domain expertise, independent validation, and governance. Generative AI may assist with feature documentation or code generation, but generated artifacts require testing, data-protection review, and human approval.

Best Practices

• Start with a clear decision and error-cost definition.
• Prevent leakage by separating prediction-time information from later information.
• Keep preprocessing inside cross-validation pipelines.
• Use stratified, grouped, or temporal evaluation according to the application.
• Compare against simple baselines before adopting complex models.
• Tune both model hyperparameters and the decision threshold.
• Report precision, recall, specificity, calibration, and subgroup performance when relevant.
• Prefer interpretable models when their performance is adequate and accountability is important.
• Monitor deployed models for drift, changing class prevalence, and fairness.
• Record assumptions, versions, datasets, and decisions so results are reproducible.

Chapter Summary

Classification learns from labeled examples to assign categorical outcomes to new observations. Decision trees partition the feature space through impurity-reducing tests and provide intuitive nonlinear models, while rule learners express classifications as auditable conditional statements. Naïve Bayes uses Bayes’ theorem with a conditional-independence assumption and is especially efficient for sparse data. Logistic regression models class probability through linear log-odds and offers useful coefficient interpretation. k-NN predicts from nearby observations and depends strongly on scaling and the choice of k. SVMs seek maximum-margin boundaries and can represent nonlinear relationships through kernels. Neural networks learn layered nonlinear transformations and are powerful for complex, unstructured data, but require careful tuning and governance.

Evaluation must distinguish discrimination, calibration, and operational cost. Accuracy alone is unreliable with imbalanced classes. A sound workflow includes appropriate data splitting, leakage prevention, cross-validation, threshold selection, error analysis, and deployment monitoring. Ethical classification requires attention to bias, privacy, transparency, security, human oversight, and the consequences of automated decisions.

Key Terms

Classification: Supervised prediction of a categorical outcome.

Feature: An input variable used by a classification model.

Class label: The categorical outcome to be predicted.

Decision boundary: A surface separating regions assigned to different classes.

Confusion matrix: A table of correct and incorrect binary predictions.

Precision: The proportion of predicted positives that are truly positive.

Recall: The proportion of actual positives correctly detected.

Specificity: The proportion of actual negatives correctly identified.

Gini impurity: A measure of class mixture in a decision-tree node.

Information gain: Reduction in impurity produced by a split.

Pruning: Removing tree branches to reduce overfitting.

Rule learner: A classifier based on conditional IF–THEN rules.

Naïve Bayes: A Bayesian classifier using conditional feature independence.

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

Regularization: A penalty or constraint used to control model complexity.

k-nearest neighbors: A distance-based classifier using nearby labeled observations.

Support vector machine: A maximum-margin classifier that may use kernel functions.

Neural network: A layered model of weighted transformations and activation functions.

Calibration: Agreement between predicted probabilities and observed frequencies.

Data leakage: Use of information unavailable at prediction time or improperly separated during evaluation.

Review Questions

Short Answer Questions

1. What is the difference between a training set and a test set?
2. Define precision and recall.
3. State the conditional-independence assumption of naïve Bayes.
4. Why should numerical features often be scaled before applying k-NN?
5. What is the purpose of regularization in logistic regression or SVMs?

Long Answer Questions

1. Explain how a decision tree is constructed using impurity and why pruning is necessary.
2. Compare naïve Bayes and logistic regression in terms of assumptions, interpretation, computational cost, and typical applications.
3. Explain the soft-margin SVM formulation and the roles of C and slack variables.
4. Describe neural-network training using activation functions, cross-entropy, and backpropagation.
5. Develop a complete classification workflow for an imbalanced medical-screening dataset.

Analytical / Application Questions

1. A fraud classifier has high accuracy but very low recall. Explain why this may occur and recommend evaluation and threshold strategies.
2. A dataset contains customer records from repeated visits by the same people. Design a validation strategy that avoids optimistic performance estimates and justify it.
3. Choose two classifiers for a regulated credit decision system. Defend your choices with respect to interpretability, accuracy, calibration, fairness, and monitoring.

Multiple Choice Questions with Answers

Question 1

Which measure is the proportion of actual positive cases that a classifier correctly identifies?

A. Accuracy

B. Precision

C. Recall

D. Specificity

Correct Answer: C. Recall

Question 2

In a decision tree, Gini impurity is zero when a node:

A. Contains equal numbers of all classes

B. Contains observations from only one class

C. Has the maximum possible depth

D. Contains missing values

Correct Answer: B. Contains observations from only one class

Question 3

The central simplifying assumption of naïve Bayes is that features are:

A. Normally distributed in every dataset

B. Conditionally independent given the class

C. Always measured on the same scale

D. Linearly separable

Correct Answer: B. Conditionally independent given the class

Question 4

In binary logistic regression, coefficients are linear in the:

A. Raw probability

B. Class frequency only

C. Log-odds

D. Euclidean distance

Correct Answer: C. Log-odds

Question 5

Why is feature scaling particularly important for k-nearest neighbors?

A. It changes class labels

B. Distance calculations can be dominated by large-scale features

C. It removes the need to select k

D. It guarantees a linear boundary

Correct Answer: B. Distance calculations can be dominated by large-scale features

Question 6

In a soft-margin SVM, the parameter C primarily controls the trade-off between:

A. Number of classes and number of features

B. Margin size and training violations

C. Precision and probability calibration

D. Tree depth and pruning

Correct Answer: B. Margin size and training violations

Question 7

Which output function is commonly used for mutually exclusive K-class neural-network classification?

A. ReLU

B. Softmax

C. Absolute value

D. Linear scaling only

Correct Answer: B. Softmax

Question 8

A model has TP = 90, FN = 10, FP = 30, and TN = 870. What is its recall?

A. 0.75

B. 0.87

C. 0.90

D. 0.96

Correct Answer: C. 0.90

Question 9

Which practice prevents preprocessing information from leaking from validation folds into training?

A. Fit preprocessing separately within each training fold

B. Fit preprocessing on the complete dataset before splitting

C. Use the test set to select features

D. Remove the validation set

Correct Answer: A. Fit preprocessing separately within each training fold

Question 10

Why can accuracy be misleading for rare-event classification?

A. Accuracy cannot be calculated for binary outcomes

B. A majority-class classifier may achieve high accuracy while missing most rare positives

C. Accuracy always equals recall

D. Accuracy measures only calibration

Correct Answer: B. A majority-class classifier may achieve high accuracy while missing most rare positives