Nearest centroid classifier

Nearest centroid classifierMain

Community hub

8 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Nearest centroid classifier

View on Wikipedia

from Wikipedia

In machine learning, a nearest centroid classifier or nearest prototype classifier is a classification model that assigns to observations the label of the class of training samples whose mean (centroid) is closest to the observation. When applied to text classification using word vectors containing tf*idf weights to represent documents, the nearest centroid classifier is known as the Rocchio classifier because of its similarity to the Rocchio algorithm for relevance feedback.^[1]

An extended version of the nearest centroid classifier has found applications in the medical domain, specifically classification of tumors.^[2]

Algorithm

[edit]

Training

[edit]

Given labeled training samples $\textstyle \{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}$ with class labels $y_{i}\in \mathbf {Y}$ , compute the per-class centroids $\textstyle {\vec {\mu }}_{\ell }={\frac {1}{|C_{\ell }|}}{\underset {i\in C_{\ell }}{\sum }}{\vec {x}}_{i}$ where $C_{\ell }$ is the set of indices of samples belonging to class $\ell \in \mathbf {Y}$ .

Prediction

[edit]

The class assigned to an observation ${\vec {x}}$ is ${\hat {y}}={\arg \min }_{\ell \in \mathbf {Y} }\|{\vec {\mu }}_{\ell }-{\vec {x}}\|$ .

References

[edit]

^ Manning, Christopher; Raghavan, Prabhakar; Schütze, Hinrich (2008). "Vector space classification". Introduction to Information Retrieval. Cambridge University Press.
^ Tibshirani, Robert; Hastie, Trevor; Narasimhan, Balasubramanian; Chu, Gilbert (2002). "Diagnosis of multiple cancer types by shrunken centroids of gene expression". Proceedings of the National Academy of Sciences. 99 (10): 6567–6572. Bibcode:2002PNAS...99.6567T. doi:10.1073/pnas.082099299. PMC 124443. PMID 12011421.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

Nearest centroid classifier

View on Grokipedia

from Grokipedia

The nearest centroid classifier is a simple supervised machine learning algorithm for multi-class classification that represents each class by the centroid, or arithmetic mean, of its training samples and assigns an unlabeled test sample to the class whose centroid is closest to it, typically using the Euclidean distance metric.^[1]^[2] This classifier operates in two main phases: during training, it computes the centroid

\bar{x}_k = \frac{1}{n_k} \sum_{i=1}^{n_k} x_i

for each class

k

, where

n_k

is the number of samples in class

k

and

x_i

are the feature vectors; for prediction, it classifies a new sample

x

by finding the class

k

that minimizes the distance

\|x - \bar{x}_k\|_2

.^[3] The decision boundary between classes is linear, derived from the difference in squared distances, and the method assumes features are on comparable scales, often requiring standardization for optimal performance.^[2] It is computationally efficient, with training and prediction both achieving linear time complexity

O(pn)

where

p

is the number of features and

n

the number of samples, making it suitable for large datasets.^[3] Historically, the approach traces its roots to the Rocchio algorithm introduced in 1971 for relevance feedback in information retrieval, which updates query vectors as weighted averages of relevant and non-relevant documents—essentially a centroid-based method adapted for binary relevance classification.^[4] In modern machine learning, it is recognized as a baseline prototype classifier, particularly effective in scenarios with well-separated, spherical class distributions, and serves as a foundation for extensions like the nearest shrunken centroids method for high-dimensional data such as gene expression analysis.^[1] Key advantages include its interpretability, as centroids provide a clear summary of class prototypes, and its robustness in low-dimensional spaces with balanced classes; however, it can underperform with outliers, imbalanced data, or non-spherical clusters, where alternatives like linear discriminant analysis or support vector machines may excel.^[2] Applications span text categorization using TF-IDF representations—where it is equivalently termed the Rocchio classifier—image recognition, and bioinformatics, often as a fast initial model before more complex techniques.^[1] Variants, such as those incorporating shrinkage toward the global centroid or alternative metrics like Manhattan distance, address limitations in high dimensions or noisy features.^[1]

Overview

Definition and intuition

The nearest centroid classifier is a simple prototype-based method for multi-class classification, where each class is represented by a single prototype known as the centroid, and an input data point is assigned to the class whose centroid is closest according to a distance metric. This approach treats the centroid as the "center of mass" for the class's training samples, providing an intuitive summary that captures the average location of the class in feature space. It operates as a linear-time algorithm, requiring only a single pass over the training data to compute centroids, which makes it computationally efficient and suitable as a baseline for more complex classifiers.^[1] The core intuition behind the nearest centroid classifier is that data points from the same class tend to cluster around a central representative point, exerting a "pull" on new samples toward their respective class centers during prediction. For a test sample, the classifier measures the distance—typically Euclidean—to each class centroid and assigns the sample to the nearest one, effectively partitioning the feature space into regions dominated by each class prototype. This mimics natural grouping behaviors observed in clustering tasks, where points are attracted to their nearest center, and it assumes well-separated classes with roughly spherical distributions for optimal performance. A high-level pseudocode overview of the workflow is as follows: Training Phase:

For each class $k$ in the set of classes:
- Compute the centroid $\mathbf{c}_k$ as the arithmetic mean of all training samples assigned to class $k$ .

Prediction Phase:

For a test sample $\mathbf{x}$ :
- Compute the distance $d_k$ from $\mathbf{x}$ to each centroid $\mathbf{c}_k$ .
- Assign $\mathbf{x}$ to the class $k^*$ where $d_{k^*} = \min_k d_k$ .

To illustrate, consider a 2D toy dataset with two classes: Class A consists of points (1,2), (2,1), (2,3), and (3,2), yielding a centroid at approximately (2,2); Class B consists of points (5,4), (6,5), (4,5), and (5,6), with a centroid at (5,5). A test point at (3,3) would be closer to Class A's centroid (Euclidean distance ≈1.41) than to Class B's (≈2.83), so it is classified as A. The decision boundary between the classes forms the perpendicular bisector of the line segment joining the centroids (at (3.5,3.5)), dividing the plane into regions where points are nearer to one centroid or the other.

Historical development

The concept of using arithmetic means as representative points for groups of observations emerged in 19th-century statistics, providing an early foundation for centroid-based classification approaches. Karl Pearson's 1901 paper on lines and planes of closest fit to systems of points in space introduced methods for representing multivariate data around central tendencies, such as means, which later influenced class prototyping in pattern recognition. The nearest centroid classifier was formalized in the mid-20th century amid the growth of statistical pattern recognition, particularly for applications like radar signal processing. In the 1960s, researchers developed fixed-centroid methods where class prototypes were predefined means, as explored in works on signal classification; for instance, Keinosuke Fukunaga's contributions to nonparametric and parametric techniques in pattern recognition during this period highlighted the use of centroids for efficient decision boundaries in high-noise environments. George S. Sebestyen's 1962 book further advanced the minimum distance framework, treating class means as prototypes for assigning patterns via Euclidean proximity, establishing it as a core technique in early computational pattern recognition systems.^[5] By the 1970s, the method gained prominence in machine learning literature as a simple, interpretable baseline, notably through its adaptation in the Rocchio algorithm for relevance feedback in information retrieval.^[6] Richard O. Duda and Peter E. Hart's influential 1973 textbook Pattern Classification and Scene Analysis presented the nearest centroid (or nearest mean) classifier as an accessible parametric approach, contrasting it with more complex discriminants while emphasizing its utility in low-dimensional settings with Gaussian assumptions. In the 2000s, the nearest centroid classifier experienced a resurgence for high-dimensional data challenges, such as text categorization and genomics, where its linear-time complexity proved advantageous over memory-intensive alternatives. Han and Karypis's 2000 analysis demonstrated its effectiveness in centroid-based document classification, achieving competitive accuracy on benchmark corpora by modeling classes via term-frequency vectors.^[7] Similarly, Tibshirani et al.'s 2002 nearest shrunken centroid method adapted it for sparse, high-dimensional gene expression data, shrinking centroids toward the global mean to mitigate overfitting and improve prediction in microarray studies, influencing its adoption in bioinformatics.^[8] This era also saw approximations linking it to probabilistic models like Naive Bayes for scalable text classification.

Algorithm

Training procedure

The training procedure of the nearest centroid classifier begins with a labeled dataset comprising

n

samples, each represented as a

d

-dimensional feature vector, spanning

K

distinct classes.^[1]^[9] The procedure consists of three primary steps. First, the dataset is partitioned by class labels to group all samples associated with each class.^[1] Second, for each class

k

, the centroid

\mu_k

is calculated as the arithmetic mean of the feature vectors of the samples in that class.^[9] Third, the collection of

K

centroids is stored to form the complete model, which encapsulates the class prototypes without further optimization.^[1] In handling edge cases, an empty class—lacking any training samples—prevents centroid computation, resulting in the exclusion of that class from the model. For imbalanced datasets, where class sample sizes differ markedly, centroids are computed directly from the available samples as unweighted means, preserving the standard approach without reweighting.^[9] The overall time complexity is

O(n \cdot d)

, arising from the linear traversal of the dataset to accumulate sums and counts per class dimension before averaging.

Prediction procedure

The prediction procedure of the nearest centroid classifier assigns an unlabeled test sample

\mathbf{x} \in \mathbb{R}^d

to the class

k^*

whose precomputed centroid

\boldsymbol{\mu}_{k^*}

minimizes the distance to

\mathbf{x}

, using the stored centroids

\{\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_K\}

for the

K

classes. The process begins by computing the distance from

\mathbf{x}

to each centroid

\boldsymbol{\mu}_k

, typically using the Euclidean distance

\|\mathbf{x} - \boldsymbol{\mu}_k\|_2 = \sqrt{\sum_{i=1}^d (x_i - \mu_{k,i})^2}

∥x−μk∥2=∑i=1d(xi−μk,i)2

. The class $k^* = \arg\min_{k=1,\dots,K} \|\mathbf{x} - \boldsymbol{\mu}_k\|_2$ is then identified, and $\mathbf{x}$ is assigned the corresponding class label. If multiple classes yield the same minimum distance, a tie-breaking rule may be applied, such as selecting the class with the smallest index. For batch prediction on a set of $N$ test samples, the distance computations are performed independently for each sample, enabling parallelization across samples while maintaining an $O(K \cdot d)$ cost per sample.

Mathematical formulation

Centroid computation

In the nearest centroid classifier, the centroid for each class serves as a prototype representative of the training samples belonging to that class. For a dataset partitioned into

K

classes, where class

k

contains

n_k

samples

\{ \mathbf{x}_{k1}, \dots, \mathbf{x}_{kn_k} \}

with each

\mathbf{x}_{ki} \in \mathbb{R}^d

, the centroid

\boldsymbol{\mu}_k

is computed as the arithmetic mean of these samples:

\boldsymbol{\mu}_k = \frac{1}{n_k} \sum_{i=1}^{n_k} \mathbf{x}_{ki}.

This formulation, standard in centroid-based methods, captures the central tendency of the class distribution in the feature space.^[10] The computation is performed component-wise across the

d

dimensions of the feature vectors. For the

j

-th dimension (

j = 1

d

), the centroid coordinate is

\mu_k^j = \frac{1}{n_k} \sum_{i=1}^{n_k} x_{ki}^j,

yielding a

d

-dimensional vector that averages the positions of all class

k

samples along each axis. This vector mean approach ensures the centroid is a point in the same space as the data, facilitating subsequent distance calculations.^[10] The choice of the arithmetic mean as the centroid arises from its optimality in minimizing the within-class variance. Specifically,

\boldsymbol{\mu}_k

is the unique point that minimizes the sum of squared Euclidean distances to the class samples:

\sum_{i=1}^{n_k} \| \mathbf{x}_{ki} - \boldsymbol{\mu} \|^2.

To derive this, consider the objective function

f(\boldsymbol{\mu}) = \sum_{i=1}^{n_k} \| \mathbf{x}_{ki} - \boldsymbol{\mu} \|^2 = \sum_{i=1}^{n_k} \sum_{j=1}^d (x_{ki}^j - \mu^j)^2

. Taking the partial derivative with respect to

\mu^j

and setting it to zero gives

\frac{\partial f}{\partial \mu^j} = -2 \sum_{i=1}^{n_k} (x_{ki}^j - \mu^j) = 0

, which simplifies to

\mu^j = \frac{1}{n_k} \sum_{i=1}^{n_k} x_{ki}^j

. The second derivative

\frac{\partial^2 f}{\partial (\mu^j)^2} = 2n_k > 0

confirms this is a minimum, establishing the mean as the variance-minimizing point.^[11] Prior to centroid computation, optional feature scaling—such as standardization (subtracting the mean and dividing by the standard deviation) or min-max normalization—is often applied to the training data to mitigate the influence of varying feature scales on the Euclidean distances implicit in the mean calculation. While the nearest centroid classifier does not strictly require scaling, it can enhance performance by ensuring all dimensions contribute equally to the centroid position.^[12]

Classification rule

The classification rule of the nearest centroid classifier assigns an input vector

\mathbf{x}

to the class

k^*

whose centroid

\boldsymbol{\mu}_k

is closest in terms of a distance metric, typically the Euclidean norm:

k^* = \arg\min_k \|\mathbf{x} - \boldsymbol{\mu}_k\|_2

where

\boldsymbol{\mu}_k

is the centroid (mean vector) computed from the training samples of class

k

.^[10]^[1] This rule partitions the feature space into decision regions, each associated with one class. For the two-class case, the boundary between classes

k

and

l

is the set of points

\mathbf{x}

equidistant from

\boldsymbol{\mu}_k

and

\boldsymbol{\mu}_l

\{\mathbf{x} \mid \|\mathbf{x} - \boldsymbol{\mu}_k\|_2 = \|\mathbf{x} - \boldsymbol{\mu}_l\|_2\}

This equation simplifies to a hyperplane perpendicular to the vector

\boldsymbol{\mu}_k - \boldsymbol{\mu}_l

and passing through the midpoint between the centroids.^[10]^[13] In the multi-class setting, the decision regions generalize to Voronoi cells, where each cell consists of all points closer to a particular centroid than to any other, under the chosen distance metric.^[10] Optionally, a confidence measure for the assigned class can be derived from the distances, such as the inverse of the distance to the nearest centroid or the margin to the second-nearest centroid; implementations often compute class probabilities via a softmax over the negative squared distances to the centroids.^[1]

Properties and analysis

Computational complexity

The training phase of the nearest centroid classifier requires computing the mean vector for each of the K classes by summing the d-dimensional feature vectors of the n samples assigned to each class and dividing by the class size, resulting in O(n d) time complexity.^[3] Space complexity for training is O(K d), as only the K centroids need to be stored after computation.^[3] During prediction, classification of a new d-dimensional sample involves calculating its distance (typically Euclidean) to each of the K stored centroids, yielding O(K d) time per sample; no additional space beyond the centroids is required.^[14] This linear scaling with dimensionality ensures efficiency even in high-d settings. Overall, the classifier exhibits high scalability for large n and moderate K, with training linear in dataset size and prediction independent of n, contrasting with methods like k-NN whose naive prediction scales as O(n d) per query.^[15] Empirically, it incurs low overhead in high-dimensional applications, such as microarray datasets with 15,000+ features, where training and prediction remain computationally feasible without dimensionality reduction.^[14]

Geometric interpretation

The nearest centroid classifier partitions the feature space into Voronoi cells, where each cell corresponds to one class and consists of all points closer to that class's centroid than to any other centroid, according to the Euclidean distance metric. This geometric structure arises directly from the classification rule, which assigns a test point to the class with the nearest centroid. The boundaries between cells are the perpendicular bisectors of the line segments joining pairs of centroids, resulting in a tessellation of the space into convex polyhedral regions.^[16] This partitioning performs optimally under the assumption that the class-conditional probability densities are multivariate Gaussian with equal spherical covariance matrices across classes (i.e., covariance proportional to the identity matrix). In such cases, the decision boundaries are linear, as the log-posterior ratios simplify to linear functions of the feature vector, aligning the Euclidean nearest-centroid rule with the Bayes optimal classifier.^[17] However, the classifier is sensitive to outliers, which can displace centroids and distort the Voronoi cells, leading to suboptimal boundaries even in spherical settings. For non-spherical clusters, such as those with elongated or anisotropic Gaussian densities (unequal or non-identity covariances), the Euclidean metric fails to capture the true geometry, resulting in poorly aligned decision regions compared to methods like linear discriminant analysis that incorporate covariance structure.^[18] Visually, the centroids act as prototypes that define a set of piecewise linear decision surfaces, dividing the space into regions of constant classification. This contrasts with quadratic classifiers, which produce curved boundaries to accommodate differing class covariances, allowing for more flexible adaptation to non-spherical data distributions.

Variants and extensions

Alternative distance metrics

The nearest centroid classifier can be adapted by replacing the standard Euclidean distance with alternative metrics to better suit specific data characteristics, such as sparsity or feature correlations, while the core prediction procedure—assigning a test point to the class with the closest centroid—remains intact.^[1] One common alternative is the Manhattan distance, also known as the L1 norm, defined as

\| \mathbf{x} - \boldsymbol{\mu} \|_1 = \sum_{j=1}^d |x^j - \mu^j|

, where

\mathbf{x}

is the test point,

\boldsymbol{\mu}

is the class centroid, and

d

is the number of features. This metric sums the absolute differences along each feature dimension, making it particularly suitable for sparse high-dimensional data or grid-like structures, such as pixel-based images where features represent independent coordinates.^[19]^[20] In implementation, the Manhattan distance is substituted directly into the prediction step, but the training phase adjusts the centroid to the feature-wise median rather than the mean, as the median minimizes the sum of L1 distances and is more robust to outliers.^[1] Another prominent alternative is the Mahalanobis distance, given by

\| \mathbf{x} - \boldsymbol{\mu} \|_M = \sqrt{ (\mathbf{x} - \boldsymbol{\mu})^T \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu}) }

∥x−μ∥M=(x−μ)TΣ−1(x−μ)

, where $\boldsymbol{\Sigma}$ is the covariance matrix of the class. This distance incorporates the covariance structure to account for correlations and varying scales among features, providing a more geometrically informed measure that normalizes for data distribution and improves performance on datasets with dependent variables.^[21]^[22] During training, class centroids are still computed as means, but each class's covariance matrix must also be estimated; in prediction, the metric replaces the Euclidean distance, with matrix inversion (or pseudoinverse for singular cases) applied per class.^[21] While this enhances accuracy for correlated features, it introduces trade-offs in computational cost, as covariance estimation and inversion scale with $O(d^2)$ storage and up to $O(d^3)$ time per class, potentially limiting scalability in high dimensions without approximations.^[22]^[21]

Weighted centroid approaches

Weighted centroid approaches extend the standard nearest centroid classifier by incorporating weights into the computation of class prototypes, allowing the model to account for class imbalances, prior probabilities, or data uncertainties. These modifications adjust the centroid calculation to emphasize certain samples more than others, improving performance in scenarios where naive averaging may lead to biased representations. For instance, weights can be derived from inverse class frequencies to mitigate the dominance of majority classes in imbalanced datasets.^[23] In class-proportional weighting, the centroid for class

k

is computed as a weighted average of the training samples belonging to that class, given by

\mu_k = \frac{\sum_{i \in \mathcal{C}_k} w_i x_i}{\sum_{i \in \mathcal{C}_k} w_i},

where

\mathcal{C}_k

denotes the set of samples in class

k

x_i

are the feature vectors, and

w_i

are sample-specific weights often set based on prior probabilities or inverse class frequencies to balance the influence across classes. This approach corrects for class imbalance by upweighting minority class samples, reducing bias in the centroid toward overrepresented classes, as demonstrated in extensions of shrunken centroid methods for high-dimensional imbalanced data.^[23] Such weighting ensures that the classifier's decision boundaries are less skewed, enhancing accuracy on underrepresented classes without altering the core prediction mechanism. Robust variants replace the arithmetic mean with more resilient location estimators to lessen the impact of outliers or noisy data. For example, the componentwise median can serve as the centroid, where each feature dimension's prototype is the median value across class samples, providing breakdown-point robustness superior to the mean in heavy-tailed distributions. Similarly, trimmed means discard extreme values (e.g., the lowest and highest

\alpha\%

) before averaging, offering a compromise between the mean's efficiency and the median's outlier resistance; this is particularly useful in high-dimensional settings where contamination affects standard centroids. These robust estimators maintain the nearest centroid framework's simplicity while improving generalization on contaminated datasets.^[24] Under multivariate Gaussian assumptions with diagonal covariance matrices (feature independence) and equal variances across classes, the nearest centroid classifier with feature standardization approximates the maximum a posteriori (MAP) estimator from Gaussian Naive Bayes when class priors are equal. This equivalence holds in the transformed space where features have unit variance, aligning the Euclidean distance with the simplified Mahalanobis distance used in Naive Bayes.^[25] In text classification, inverse document frequency (IDF) weighting is commonly applied to centroid computation, where term weights in the vector space model are scaled by IDF to emphasize discriminative features, as in the Rocchio classifier; the centroid becomes

\mu_k = \frac{\sum_{i \in \mathcal{C}_k} \text{tf-idf}(x_i)}{\sum_{i \in \mathcal{C}_k} 1}

, reducing the influence of common terms and boosting rare, informative ones for better category separation. This adaptation has been analyzed probabilistically to justify IDF's role in enhancing relevance feedback and classification accuracy.^[26]

Nearest shrunken centroids

A prominent extension is the nearest shrunken centroids (NSC) method, particularly useful for high-dimensional data such as gene expression analysis. In NSC, class centroids are shrunk toward the overall centroid of all training samples by a shrinkage factor, which helps reduce the impact of noisy or irrelevant features. Features with shrunken values below a threshold are effectively removed, leading to sparse centroids and improved classification performance by mitigating the curse of dimensionality. The shrinkage intensity is often tuned via cross-validation, balancing bias and variance. This variant, introduced by Tibshirani et al. in 2002, has been widely applied in bioinformatics for tumor classification.^[27]

Applications and comparisons

Practical uses

The nearest centroid classifier, also known as the Rocchio classifier in text processing contexts, serves as a fast baseline for document classification tasks, such as spam detection, where documents are represented using bag-of-words models and centroids are computed as average term vectors per class.^[28] Its simplicity allows for efficient categorization of high-dimensional text data, with improvements like batch-updated centroids enhancing accuracy over naive baselines on corpora like TDT-5.^[28] In bioinformatics, the nearest centroid classifier has been applied to gene expression analysis for tumor classification from microarray data, particularly in the early 2000s. A seminal approach using shrunken centroids achieved zero test errors on lymphoma datasets with 81 selected genes out of 4,026, outperforming standard nearest centroid methods (which had 4/25 errors using 2,308 genes) on small round blue cell tumor data.^[29] This demonstrated competitive accuracy in high-dimensional genomic settings, selecting informative gene subsets for reliable subtype prediction.^[29]^[30] For image recognition, the nearest centroid classifier enables simple feature-based sorting, such as using color histogram centroids to categorize objects by dominant color distributions. In this setup, training images per category yield centroid histograms, and new images are assigned to the nearest centroid via distance metrics like Euclidean, reducing computational demands in content-based retrieval systems.^[31] More recently, as of 2024, variants like deep centroid classifiers have been applied to biomedical image analysis for precision medicine tasks such as cancer early diagnosis, cancer prognosis, and drug sensitivity prediction.^[32] In 2023, nearest centroid methods were used for feature-adaptive recommendations in mobile app ecosystems by analyzing user reviews to spot app problems.^[33] Additionally, quantum implementations of nearest centroid classification have been explored since 2021 for efficient computation on trapped ion quantum computers.^[34] Due to its low memory footprint—storing only class centroids rather than full training data—the nearest centroid classifier is favored in resource-constrained environments.^[12]

Relation to other classifiers

The nearest centroid classifier shares a conceptual foundation with the k-nearest neighbors (k-NN) algorithm as a distance-based method, but it employs fixed class prototypes rather than instance-based retrieval. In k-NN, classification relies on storing the entire training dataset and dynamically identifying the k closest training samples to a query point at prediction time, which incurs a computational cost proportional to the training set size. By contrast, the nearest centroid classifier precomputes a single centroid per class during training, allowing predictions in constant time via simple distance computation to these prototypes, making it substantially faster for large-scale test sets or high-dimensional data where k-NN becomes inefficient. This efficiency comes at the expense of k-NN's flexibility in capturing local data variations, though empirical studies show nearest centroid achieving competitive or superior accuracy in scenarios with well-separated class clusters, such as certain genomic datasets.^[35]^[36] Compared to linear discriminant analysis (LDA), the nearest centroid classifier generates linear decision boundaries by assigning samples to the closest class mean, but it does so without the dimensionality reduction or covariance-adjusted projections that define LDA. LDA optimizes a linear transformation to maximize class separability by minimizing within-class variance relative to between-class variance, typically using the Mahalanobis distance to incorporate differing class covariances; in the special case of equal covariances, LDA reduces to a nearest centroid rule in the projected space. The nearest centroid approach, often using Euclidean distance, is non-parametric in its mean estimation and avoids LDA's need for covariance matrix inversion, which can be unstable in high dimensions (p >> n). Consequently, nearest centroid serves as a simpler baseline that performs comparably to LDA in low-noise settings but underperforms when class covariances vary significantly or when feature correlations require explicit modeling.^[37] In relation to support vector machines (SVM), the nearest centroid classifier prioritizes training simplicity and speed by merely averaging class samples, eschewing SVM's quadratic optimization for maximum-margin hyperplane separation. SVMs offer greater flexibility for non-linear data via kernel functions and robust margin-based generalization, often outperforming nearest centroid in noisy or overlapping distributions, as seen in protein mass spectrometry tasks where SVM achieved up to 92% accuracy versus nearest centroid's 85-100% range depending on feature selection. However, nearest centroid's linear nature and lack of kernel support limit its adaptability to complex boundaries, while its lower training complexity (O(np) versus SVM's O(n^2 p) or higher) makes it preferable for rapid prototyping or resource-constrained environments. Extensions like shrunken centroids can narrow this gap by incorporating sparsity, yielding error rates comparable to SVM (e.g., 5/21 misclassifications) with added interpretability through gene selection.^[36] The nearest centroid classifier is often favored as an initial baseline to benchmark more sophisticated models due to its minimal assumptions and ease of implementation, excelling particularly in balanced datasets exhibiting low noise and approximate Gaussian distributions per class, where its prototype-based decisions align closely with optimal Bayes classifiers under equal covariance.^[37]^[35]

History

Media collections

Nearest centroid classifier

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Nearest centroid classifier

Algorithm

Training

Prediction

See also

References

Nearest centroid classifier

Overview

Definition and intuition

Historical development

Algorithm

Training procedure

Prediction procedure

Add your contribution

Related Hubs

Contribute something