Lesson 5.2.1: Logistic Regression and K-Nearest Neighbors

Definition and Historical Context

When we first encounter the toolkit of statistical learning, two methods stand out for their simplicity and enduring popularity: logistic regression and k‑nearest neighbours (k‑NN). Although they arise from different intellectual traditions, both share a common goal – to solve classification problems – and they exhibit starkly contrasting philosophies of inference. This section traces their origins, explains their core concepts, and situates them within the broader history of machine learning.

Logistic Regression: From Probability to Classification

Logistic regression was formalised in the early 20th century as an extension of linear regression that could handle binary outcomes. The method was first described by the statistician David Cox in the 1950s, but its roots lie earlier in the work of Pierre-Charles de Laplace and G. U. Yule, who recognised the need for a model that outputs probabilities constrained between 0 and 1. The key innovation is the use of the logistic function, also called the sigmoid:

def sigmoid(z):
    return 1 / (1 + math.exp(-z))

Here, z is a linear combination of predictors, typically written as z = β₀ + β₁x₁ + … + βₖxₖ. By applying the sigmoid to this linear predictor, the model ensures that the estimated probability p = sigmoid(z) lies in the unit interval. The coefficients β are estimated by maximum likelihood, a principle that dates back to R. A. Fisher’s 1922 work on the likelihood function.

Logistic regression is a parametric model: it assumes a specific functional form (the logistic link) and estimates a finite set of parameters. This makes it highly interpretable. For instance, in a medical screening context, the coefficient for a risk factor can be expressed as an odds ratio, giving clinicians a clear sense of how much the risk of disease changes with each unit increase in the predictor.

Historically, logistic regression was the workhorse of social science and biostatistics well into the 1990s. Its simplicity and strong theoretical underpinnings made it a favourite for hypothesis testing, especially when the number of predictors was modest relative to the sample size. The method also laid groundwork for later advances in probit models, generalized linear models, and machine learning classifiers such as support vector machines.

K‑Nearest Neighbours: A Non‑Parametric, Instance‑Based Approach

In contrast, k‑NN was formally introduced by Thomas Cover and Peter Hart in 1967. It represents one of the earliest instance‑based learning algorithms. Rather than fitting a global model, k‑NN stores the entire training set and classifies a new observation by examining the labels of its k closest neighbours in feature space.

The algorithm is incredibly simple to describe:

def knn_predict(X_train, y_train, x_new, k=5):
    distances = [euclidean(x_new, x_i) for x_i in X_train]
    nearest = sorted(zip(distances, y_train))[:k]
    return majority_vote([label for _, label in nearest])

Key components are the choice of distance metric (Euclidean, Manhattan, cosine, etc.) and the parameter k. Because the method relies solely on the data, it is called non‑parametric. There is no assumption about the underlying distribution of the predictors or the shape of the decision boundary.

Historically, k‑NN has been a staple in pattern recognition tasks such as handwriting recognition, where the method was applied to the MNIST dataset in the 1990s. Its appeal lies in its conceptual simplicity and the fact that it can adapt to complex, high‑dimensional data without explicit feature engineering. However, the method suffers from the “curse of dimensionality”: as the number of features grows, all points tend to become equidistant, reducing the discriminative power of nearest‑neighbour searches.

Comparing the Philosophies

• Model vs Data‑Driven – Logistic regression posits a specific functional form (log‑odds linear in predictors), whereas k‑NN makes no such assumption and learns directly from the data.
• Interpretability – Logistic regression coefficients can be interpreted in terms of odds ratios; k‑NN offers no direct parameter estimates, making it less transparent for explaining decisions.
• Computational Cost – Training logistic regression involves solving an optimisation problem that is typically fast for moderate‑sized data. k‑NN’s training is trivial (just storing the data), but prediction can be expensive for large datasets unless efficient data structures (KD‑trees, ball trees) are employed.
• Scalability – Logistic regression scales well to large feature spaces, especially with regularisation (L1, L2). k‑NN struggles with very high dimensional data unless dimensionality reduction is applied.
• Robustness to Outliers – Logistic regression can be sensitive to extreme values unless robust loss functions are used. k‑NN is inherently robust insofar as the majority vote can mitigate the influence of a few outliers.

Concrete Example: Email Spam Detection

Consider the classic problem of classifying emails as spam or ham. The dataset consists of a bag‑of‑words representation: each email is encoded as a high‑dimensional sparse vector indicating the presence or frequency of particular words.

Logistic Regression Approach
We fit a logistic regression model where each word is a predictor. The coefficients reveal which words increase or decrease the probability of spam. For instance, a large positive coefficient for the word “offer” suggests that its presence strongly indicates spam. Once trained, the model can be applied to new emails, producing a probability that the email is spam. This probability can be thresholded (e.g., at 0.5) to make a binary decision.

k‑NN Approach
Here, each email is a point in a very high‑dimensional space. To classify a new email, we compute its distance to all training emails, identify the five nearest ones, and take the majority label. If most of those neighbours are spam, we classify the new email as spam. The algorithm makes no assumptions about which words are important; it simply relies on proximity in the word‑frequency space.

In practice, logistic regression often outperforms k‑NN on such sparse textual data because it can exploit the linear separability of the log‑odds. However, if the decision boundary is highly non‑linear or if the dataset contains complex local patterns, a carefully tuned k‑NN (perhaps with a kernelised distance) might achieve superior performance.

Evolution and Modern Context

Both logistic regression and k‑NN have evolved considerably since their inception. In the 1990s, the rise of regularised logistic regression (the Lasso and Ridge) addressed overfitting in high‑dimensional settings, making the method competitive with tree‑based models. Meanwhile, k‑NN benefited from advances in approximate nearest‑neighbour search algorithms (such as locality‑sensitive hashing) that dramatically reduce prediction time on large datasets.

Today, logistic regression remains a baseline in many machine learning pipelines, especially in domains where interpretability is paramount (e.g., credit scoring, medical diagnosis). k‑NN, while less popular in high‑dimensional contexts, still finds niche applications in recommender systems and in scenarios where the data are naturally clustered.

Both methods also serve as pedagogical tools. Logistic regression introduces students to likelihood estimation, odds ratios, and the idea of a link function, while k‑NN illustrates the concept of instance‑based learning and the importance of distance metrics.

Key Takeaways from the Historical Lens

• Logistic regression is a parametric, probabilistic model that offers interpretability and efficiency in moderate‑dimensional spaces.
• k‑NN is a non‑parametric, instance‑based algorithm that excels in low‑dimensional, well‑structured data but struggles as dimensionality rises.
• Both methods have matured through regularisation, efficient data structures, and integration into larger machine‑learning frameworks.
• The choice between them depends on the problem context, data characteristics, and the need for interpretability versus flexibility.

Understanding the historical trajectory of these methods not only enriches our appreciation of their strengths and limitations but also equips us with a richer vocabulary for selecting appropriate techniques in contemporary data‑science projects.

Mechanisms and Mathematics

In this section we unpack the core mathematical ideas that make logistic regression and k‑Nearest Neighbours (k‑NN) distinct yet complementary tools for classification. We will see how each algorithm formulates a decision rule, the role of parameters, and how the choice of distance or link function shapes the model’s behaviour. Concrete numerical examples will illustrate the mechanics and help you visualise the underlying geometry.

Logistic Regression: From Linear Scores to Probabilities

Logistic regression is a parametric method that models the probability of a binary outcome as a smooth function of the predictors. The starting point is a linear combination of the input features:

z = β0 + β1 x1 + β2 x2 + … + βp xp

Here z is called the logit score, and the vector β = (β0, β1, …, βp) contains the model coefficients to be estimated from data. To convert this unbounded linear score into a probability that lies strictly between 0 and 1, logistic regression applies the logistic (sigmoid) function:

p = 1 / (1 + exp(-z))

or, equivalently, p = σ(z). The inverse of this mapping, logit(p) = log(p/(1-p)) = z, is what gives the model its name.

Parameter Estimation Coefficients are typically estimated by maximum likelihood. For a training set of n observations with binary responses y_i ∈ {0,1}, the likelihood of the data is

L(β) = ∏_{i=1}^n p_i^{y_i} (1-p_i)^{1-y_i}

Taking the natural logarithm gives the log‑likelihood, which is then maximised using iterative numerical methods such as Newton–Raphson or gradient ascent. The resulting estimates minimise the cross‑entropy loss, a convex function that guarantees a unique global optimum when the design matrix has full rank.

Decision Boundary Because the logit is linear in the predictors, the decision boundary (where p = 0.5) is a hyperplane defined by z = 0, i.e. β0 + β1 x1 + … + βp xp = 0. Points on one side of this hyperplane are classified as class 1, points on the other as class 0. The slope of the boundary depends directly on the coefficients.

Example Suppose we have a single predictor x (e.g. age) and a fitted model with β0 = -3, β1 = 0.08. The probability of class 1 for an individual aged 50 is

z = -3 + 0.08*50 = 1
p = 1 / (1 + exp(-1)) ≈ 0.73

Thus, the model would predict class 1 for this individual. The decision boundary occurs at z = 0, i.e. at age x = 37.5.

k‑Nearest Neighbours: A Distance‑Based Voting Scheme

k‑NN is a non‑parametric, instance‑based learner. Instead of fitting a global function, it stores the entire training set and makes predictions for a new point by examining its nearest neighbours in feature space.

Distance Metric The most common choice is Euclidean distance:

d(x, x') = sqrt( Σ_{j=1}^p (x_j - x'_j)^2 )

Other metrics (Manhattan, Mahalanobis, cosine) can be used depending on the data geometry.

Neighbour Selection Given a query point x, we compute its distance to every training point, then select the k points with the smallest distances. These are the nearest neighbours.

Voting Rule For binary classification, the simplest rule is majority voting: assign the class that appears most frequently among the k neighbours. A weighted variant assigns each neighbour a weight inversely proportional to its distance, giving closer points more influence.

Choice of k A small k leads to a flexible decision boundary that can adapt to local structure but risks overfitting (high variance). A large k smooths the boundary, reducing variance but potentially increasing bias. The optimal k is usually found via cross‑validation.

Decision Boundary Unlike logistic regression, k‑NN’s boundary is highly irregular, conforming to the local distribution of the training points. In low dimensions, one can visualise it as a contour of equal class probability that snakes around clusters of points.

Example Imagine a two‑dimensional dataset with two classes arranged in interleaving spirals. With k = 1, the decision boundary is a jagged line that follows every training point, leading to extreme over‑fitting. Increasing to k = 15 smooths the boundary, capturing the overall spiral shape while still respecting local variations.

Comparing the Two Approaches

• Parametric vs Non‑parametric Logistic regression assumes a global linear structure in the logit space. k‑NN makes no such assumption, allowing arbitrary decision surfaces.
• Interpretability Logistic regression coefficients provide direct insight into the effect of each predictor on the log‑odds. k‑NN offers no such summary; interpretation relies on inspecting local neighbourhoods.
• Computational Complexity Training logistic regression is relatively cheap (solving a convex optimisation). k‑NN is trivial to train (just store the data) but prediction time grows linearly with the size of the training set.
• Handling of Non‑linearities Logistic regression can be extended with basis expansions (polynomials, splines) to capture non‑linear effects. k‑NN inherently captures non‑linearity through the distance metric.
• Robustness to Outliers A single extreme point can severely distort logistic regression coefficients. k‑NN is robust in the sense that an outlier will only affect predictions for points very close to it, but its influence can be mitigated by choosing a suitable distance metric or incorporating distance weighting.

Concrete Numerical Comparison

Let us compare the two algorithms on a toy binary classification task. Suppose we have the following six training points in a two‑dimensional space:

We fit a logistic regression model (using a library that automatically centres and scales). The estimated coefficients (illustrative) are β0 = -4.2, β1 = 0.9, β2 = 0.7. For a new point (x1,x2) = (4,5), the logit is

z = -4.2 + 0.94 + 0.75 = 3.3
p = 1/(1+exp(-3.3)) ≈ 0.965

The model predicts class 1 with high confidence.

Now consider k‑NN with k=3. The three nearest neighbours to (4,5) are points 3, 4 and 2 (distances 2.24, 2.83, 3.61 respectively). Two of them belong to class 1, so the majority vote assigns class 1. If we instead use k=5, the nearest five points are 3, 4, 2, 1, 6; the vote splits 3:2 in favour of class 1, still yielding class 1. However, with k=6 (i.e. all points), the vote is 3:3, leading to a tie that a typical implementation resolves by returning the class of the nearest neighbour (class 1).

In this small example, both methods agree on the prediction for the query point, but their internal reasoning differs: logistic regression uses a weighted sum of all features; k‑NN relies on local majority.

When to Prefer One Over the Other

1. Data Size If the dataset is large and the relationship is roughly linear, logistic regression scales better. For small to medium datasets where the shape of the decision boundary is complex, k‑NN can capture intricate patterns without explicit model specification.
2. Feature Dimensionality High‑dimensional spaces dilute the concept of proximity; distances become less informative (the curse of dimensionality). Logistic regression, possibly with regularisation, can handle many predictors more gracefully. Dimensionality reduction (PCA, t‑SNE) can be applied to k‑NN if needed.
3. Interpretability Needs When explaining model decisions to stakeholders, logistic regression’s coefficients and odds ratios are valuable. If interpretability is not a priority and accuracy is paramount, k‑NN’s black‑box nature may be acceptable.
4. Computational Resources Training logistic regression is quick, but predicting with k‑NN can be slow for large databases unless efficient data structures (KD‑trees, ball trees) are employed.
5. Robustness to Noise Logistic regression can be regularised (L1, L2) to mitigate over‑fitting. k‑NN can incorporate distance weighting and outlier rejection to improve robustness.

Mathematical Extensions and Hybridisation

Both algorithms can be enriched in various ways:

• Logistic Regression
  • Regularisation (ridge, lasso) introduces a penalty term λ Σ β_j^2 or λ Σ |β_j| to the loss, controlling over‑fitting.
  • Interaction terms and polynomial features allow modelling of non‑linear relationships.
  • Multinomial logistic regression extends to multi‑class problems by fitting a softmax link.
• k‑NN
  • Feature weighting assigns different importance to dimensions, e.g. via Fisher discriminant scores.
  • Approximate nearest neighbour search (Locality Sensitive Hashing) speeds up predictions on massive datasets.
  • Hybrid schemes combine k‑NN with a parametric model: for example, use logistic regression to obtain a baseline probability and then adjust it with a k‑NN estimate.

Understanding these mathematical underpinnings equips you to select, tune, and customise the right algorithm for a given classification problem. In the next lesson we will explore regularisation techniques that can be applied to logistic regression to further improve generalisation.

Implications and Practical Considerations

When selecting a predictive model for a binary classification problem, it is essential to consider how the model will respond to the idiosyncrasies of the data at hand. Logistic regression and k‑nearest neighbours (k‑NN) occupy opposite ends of the model spectrum: the former is a parametric, globally‑fitted algorithm that assumes a specific functional form, while the latter is a non‑parametric, instance‑based learner that relies entirely on local relationships. This section explores the practical trade‑offs between the two, focusing on bias–variance dynamics, data characteristics, and computational overhead.

Bias–Variance Trade‑Off

In statistical learning, the bias–variance trade‑off describes the balance between a model’s ability to capture the underlying pattern (low bias) and its sensitivity to fluctuations in the training data (high variance). Logistic regression, by imposing a linear decision boundary in the transformed feature space, typically exhibits high bias but low variance. In contrast, k‑NN, with its reliance on local neighbourhoods, tends to have low bias but can suffer from high variance when the data are noisy or sparse.

For example, consider a dataset where the relationship between predictors and the log‑odds of the target is truly linear. A logistic model will fit well, achieving low error because its assumptions align with reality. If the data contain a non‑linear, complex interaction (e.g., a decision surface shaped like a spiralling curve), the logistic model will struggle, resulting in high bias. A small value of k in k‑NN will adapt to such intricacies, reducing bias, but will also magnify the impact of random noise, thereby increasing variance.

In practice, one often mitigates variance in k‑NN by increasing k or by weighting neighbours by distance, but this can re‑introduce bias. Conversely, regularisation techniques such as L2 (ridge) or L1 (lasso) penalisation can reduce variance in logistic regression, at the cost of potentially inflating bias.

Data Dimensionality

High‑dimensional data present a particular challenge for k‑NN due to the “curse of dimensionality.” As the number of features grows, the distance between points becomes less informative; all distances converge, making it difficult to distinguish neighbours. Consequently, k‑NN’s performance degrades sharply in high dimensions unless dimensionality reduction techniques (e.g., PCA, t‑SNE) or feature selection are applied beforehand.

Logistic regression, however, can handle high dimensionality more gracefully, especially when paired with regularisation. By shrinking coefficients towards zero, regularised logistic regression reduces model complexity and combats overfitting. Nonetheless, if the number of predictors far exceeds the number of observations, even logistic regression may encounter singularity issues, necessitating techniques such as penalised likelihood or Bayesian priors.

Sample Size and Class Imbalance

With limited data, k‑NN’s reliance on local structures can lead to unstable predictions, as the set of nearest neighbours may change dramatically with the addition or removal of a single observation. Logistic regression, being a global model, benefits from pooling information across the entire dataset, often yielding more reliable estimates when samples are scarce.

When class imbalance is present, k‑NN can be heavily biased towards the majority class because the majority class will dominate the neighbourhood. Adjustments such as class‑weighted distance metrics or synthetic minority oversampling (SMOTE) can alleviate this, but the fundamental issue remains. Logistic regression handles imbalance more naturally through its probabilistic framework; by incorporating class weights or adjusting the decision threshold, one can tune sensitivity and specificity without altering the underlying model.

Computational Demands

Training logistic regression is computationally inexpensive: it involves solving a convex optimisation problem that scales linearly with the number of samples and features for algorithms such as stochastic gradient descent. Once trained, predictions are instantaneous, requiring only a matrix‑vector multiplication per instance.

k‑NN, in contrast, has negligible training cost but incurs significant prediction time, as each query requires computing distances to all training points (or to a subset if a KD‑tree or ball tree is used). For a dataset with n training instances, the time complexity of a single prediction is O(n·d), where d is the number of features. In large‑scale applications, this can become prohibitive, necessitating approximate nearest neighbour algorithms or pre‑computation of distance structures.

Memory consumption is also a concern for k‑NN, as the entire training set must be retained in memory for distance calculations. Logistic regression, conversely, only requires storage of the fitted coefficient vector, which is negligible even for high‑dimensional data.

Interpretability

Interpretability is a key consideration in many domains, such as healthcare or finance. Logistic regression offers clear, probabilistic outputs and coefficients that can be directly interpreted as log‑odds multipliers. This transparency facilitates regulatory compliance and stakeholder confidence.

k‑NN lacks a global model; predictions are purely instance‑based, making it challenging to summarise the influence of individual features. While instance explanations (e.g., local surrogate models) can provide some insight, they are inherently less straightforward than logistic regression coefficients.

Robustness to Outliers

k‑NN is highly sensitive to outliers because an anomalous point can become a neighbour for many queries, skewing predictions. Techniques such as distance weighting or robust distance metrics (e.g., Mahalanobis distance) can mitigate this vulnerability.

Logistic regression assumes that the relationship between predictors and the log‑odds is linear and that residuals follow a binomial distribution. Outliers in the predictors can have a disproportionate influence on the coefficient estimates, especially when no regularisation is applied. Robust variants of logistic regression, such as penalised likelihood with Huber loss, can provide resilience against such anomalies.

Practical Example: Customer Churn Prediction

"In our churn dataset, we have 10,000 customers with 20 features, including both continuous variables (e.g., monthly spend) and categorical variables (e.g., contract type). The churn rate is 12%." — Data Science Lead, TelecomCo

With this dataset, a regularised logistic regression model would be a sensible first choice. It can accommodate the mixture of feature types via one‑hot encoding, and the L2 penalty would prevent overfitting given the modest feature count. Training would take under a second on a standard laptop, and the model’s coefficients would offer actionable insights: for instance, a negative coefficient for “month‑to‑month contract” would suggest that such customers are more likely to churn.

If the organisation wishes to capture subtle, non‑linear patterns—perhaps a complex interaction between service usage and payment behaviour—a k‑NN approach might be considered. However, before deployment, one should assess the dimensionality: a 20‑dimensional space is manageable, but the training set of 10,000 instances would mean each prediction requires up to 200,000 distance calculations. Employing a KD‑tree would reduce this to approximately O(log n) per query, yet the memory footprint remains significant.

In practice, a hybrid strategy can be effective: use logistic regression as a baseline model and reserve k‑NN for a local refinement stage, perhaps only on customers flagged as high‑risk by the logistic model. This leverages the strengths of both algorithms while mitigating their weaknesses.

Model Selection Checklist

1. Data size: Large (>10,000) → logistic regression favoured; Small (<1,000) → k‑NN viable.
2. Dimensionality: High (>50) → logistic regression with regularisation; Low → both models acceptable.
3. Computational budget: Real‑time inference required → logistic regression; Batch processing → k‑NN possible.
4. Interpretability needed: Yes → logistic regression; No → k‑NN acceptable.
5. Non‑linearity suspected: Yes → consider k‑NN, tree‑based methods, or kernelised logistic regression; No → logistic regression sufficient.

Summary

Choosing between logistic regression and k‑NN hinges on a nuanced understanding of data characteristics and operational constraints. Logistic regression shines when interpretability, scalability, and robustness are paramount, especially in high‑dimensional or imbalanced settings. k‑NN excels in scenarios where the decision boundary is inherently local and the dataset is relatively small, offering flexibility at the cost of computational demand and sensitivity to noise. By systematically evaluating bias–variance behaviour, dimensionality, sample size, and resource availability, practitioners can align model choice with organisational objectives and technical realities.

Comparative Analysis

Interpretability

Interpretability is a key consideration when selecting a predictive model, especially in regulated sectors such as finance or healthcare. Logistic regression offers a high degree of transparency. Because the model estimates a linear combination of input features, each coefficient directly reflects the log‑odds change associated with a one‑unit increase in that feature, holding all others constant. For example, in a credit‑worthiness study, a coefficient of 0.45 for the variable annual_income indicates that a £10,000 rise increases the odds of default by approximately 57% (exp(0.45) ≈ 1.57). Stakeholders can readily communicate such insights to auditors or policy makers.

In contrast, k‑Nearest Neighbour (k‑NN) is an instance‑based learner. Its predictions are derived from a simple majority vote among the k closest points in the training set. While the algorithm itself is easy to understand, the decision surface is highly data‑dependent. Explaining why a particular observation was classified one way often requires inspecting the nearest neighbours, which may be located in disparate regions of the feature space. Consequently, k‑NN is generally considered less interpretable than logistic regression, especially when the dimensionality is high and the notion of “distance” becomes opaque.

Nevertheless, k‑NN can still provide local interpretability through techniques such as instance‑based explanations (e.g. LIME or SHAP). By approximating the decision boundary around a specific instance, these methods can highlight which features contributed most to the prediction. Such post‑hoc explanations help bridge the gap, but they add an extra layer of complexity that logistic regression does not require.

Scalability

Scalability concerns both computational efficiency and memory usage. Logistic regression is a parametric model: once the coefficients are estimated, making predictions on new data is essentially a linear algebra operation—multiplying a feature vector by a coefficient matrix and applying the logistic function. This operation has a time complexity of O(p), where p is the number of features, and it requires only the stored parameter vector, making it extremely lightweight in terms of memory.

k‑NN, however, is a non‑parametric method that stores the entire training set. Prediction time scales linearly with the number of training instances, O(n × p), because each new observation must be compared to all stored points to find the k nearest ones. For large datasets (e.g. millions of records), this can become prohibitively slow. Data structures such as KD‑trees or ball trees can mitigate the cost in lower dimensions, reducing the search to O(log n) on average, but performance degrades rapidly as dimensionality increases—a phenomenon known as the “curse of dimensionality.”

Moreover, logistic regression can be trained incrementally or in a stochastic manner, allowing it to handle streaming data or very large batches that do not fit into memory. k‑NN lacks such online learning capabilities; each new instance effectively expands the training set, further increasing prediction time.

Typical Application Domains

Both logistic regression and k‑NN are binary classification tools, but their suitability varies across domains due to differing assumptions and practical constraints.

• Finance and Credit Risk: Regulatory bodies demand model explainability. Logistic regression’s coefficient‑based insights satisfy this requirement, making it the de facto standard for credit scoring, fraud detection, and loan approval pipelines. k‑NN is rarely used in this context unless paired with interpretability techniques or limited to small, highly curated datasets.
• Medical Diagnosis: When the outcome is a disease presence/absence, clinicians often prefer models that offer clear risk estimates. Logistic regression provides odds ratios that can be directly integrated into clinical decision support systems. k‑NN can be useful for case‑based reasoning, where a patient's similarity to historic cases is clinically meaningful, but its opaque decision surface can be a barrier to adoption.
• Image and Text Classification: In high‑dimensional spaces, logistic regression is often combined with feature extraction (e.g. TF‑IDF for text, convolutional features for images) to produce a lower‑dimensional representation amenable to linear models. k‑NN can still be applied after dimensionality reduction (e.g. PCA), but the distance metric may become less informative as the number of features shrinks. Support Vector Machines or deep neural networks are typically preferred in these domains.
• Recommender Systems: k‑NN shines in collaborative filtering, where similarity between users or items is computed directly from sparse preference matrices. Logistic regression is less common here because the goal is to predict a continuous rating rather than a binary class.
• Embedded Systems and Edge Devices: Logistic regression’s lightweight nature makes it suitable for deployment on devices with limited memory and compute power (e.g. IoT sensors, mobile phones). k‑NN, due to its reliance on the full training set, is usually impractical in such constrained environments unless specialised indexing or hashing techniques are employed.

Model Calibration and Probabilistic Output

Logistic regression naturally outputs probabilities that sum to one, as the logistic function maps the linear predictor to the (0,1) interval. These probabilities are often well‑calibrated if the underlying assumptions hold (e.g. linearity in the log‑odds). Calibration techniques such as Platt scaling or isotonic regression can further refine the probability estimates when necessary.

k‑NN produces probabilities by taking the proportion of labels in the neighbourhood: if 7 of the 10 nearest neighbours belong to class 1, the predicted probability is 0.7. While this is straightforward, it can be poorly calibrated in sparse regions of the feature space. For instance, in a high‑dimensional dataset where distances are uniformly large, the nearest neighbours may be arbitrarily far, leading to overconfident predictions. Post‑hoc calibration can be applied, but it is an additional step not required for logistic regression.

Robustness to Outliers

Because logistic regression estimates a global decision boundary, it can be influenced by outliers that lie far from the majority of the data. Regularisation (L1 or L2) mitigates this risk by penalising large coefficients, but extreme points can still skew the model.

k‑NN, being local, is inherently robust to global outliers: an isolated point will only affect predictions of instances that happen to be within its neighbourhood. However, if outliers cluster in a region, they can dominate the local majority vote, leading to misclassifications. Distance weighting (e.g. inverse distance weighting) can reduce outlier influence by giving nearer neighbours more sway.

Parameter Sensitivity

Logistic regression has a small set of hyperparameters: the regularisation strength (C for L2 or L1) and the choice of regulariser. Tuning these is straightforward with cross‑validation, and the impact on model performance is usually smooth.

k‑NN’s primary hyperparameter is k, the number of neighbours. Choosing an odd k helps avoid ties in binary classification, but small k values can lead to overfitting (high variance), while large k values can oversmooth (high bias). Additionally, distance metric choice (Euclidean, Manhattan, cosine) and feature scaling (standardisation or normalisation) are crucial. Mis‑scaling can cause features with larger numeric ranges to dominate the distance calculation, distorting the neighbourhood structure.

Conclusion

When deciding between logistic regression and k‑NN, educators and practitioners should weigh interpretability, scalability, and domain suitability. Logistic regression is favoured in regulated, data‑scarce, or resource‑constrained settings where clear explanations and fast inference are paramount. k‑NN excels in scenarios where local patterns matter, such as case‑based reasoning or similarity‑search tasks, and where the dataset is small enough for its computational demands to be acceptable. Understanding these trade‑offs ensures that the chosen model aligns with both organisational objectives and technical constraints.

Further Reading

• James, G., Witten, D., Hastie, T. & Tibshirani, R. (2013) — An Introduction to Statistical Learning. A clear, accessible primer on logistic regression and nearest‑neighbour algorithms, ideal for undergraduate students.
• Murphy, K.P. (2012) — Machine Learning: A Probabilistic Perspective. Offers a rigorous probabilistic treatment of logistic regression and discusses K‑NN within a Bayesian framework.
• Goodfellow, I., Bengio, Y. & Courville, A. (2016) — Deep Learning (Chapter 7). Although focused on deep learning, this chapter provides a concise comparison of classical models, including logistic regression and K‑NN, with modern techniques.
• Scikit‑learn developers (2024) — Scikit‑learn Documentation: LogisticRegression and KNeighborsClassifier. Official API reference and practical examples for implementing these algorithms in Python.
• International Organisation for Standardisation (ISO) (2020) — ISO/IEC 27001: Information Security Management Systems. Includes a section on risk assessment that often employs logistic regression and simple classification models for threat prediction.