Nearest neighbor pattern classification

1967/01/01 by T. Cover, Thomas M. Cover, P. Hart +1 · 242 citations
Mathematics · Computer Science · #Statistical Methods and Inference #Advanced Statistical Methods and Models #Rough Sets and Fuzzy Logic

paper · doi:10.1109/tit.1967.1053964

Abstract

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> of such a rule must be at least as great as the Bayes probability of error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R^∗</tex> --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</tex> -category case that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R^∗ ≤ R ≤ R^∗(2 --MR^∗/(M-1))</tex> , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.

Cited by

• A Local Mean-Based k-Nearest Centroid Neighbor Classifier
• Asymptotic Properties of Nearest Neighbor Rules Using Edited Data
• The Distance-Weighted k-Nearest-Neighbor Rule
• Pattern Recognition with Partly Missing Data
• A Direct Method of Nonparametric Measurement Selection
• Learning similarity with cosine similarity ensemble
• Fuzzy nearest neighbor algorithms: Taxonomy, experimental analysis and prospects
• Using support vector regression and K-nearest neighbors for short-term traffic flow prediction based on maximal information coefficient
• LatentFlow: Visual Analytics for Latent Space Analysis in Molecular Graph Neural Networks
• Predicting water quality parameters in a subtropical estuary under different scenarios: Evidence from the Gold Coast, Australia
• Open-set mineral identification from CRISM hyperspectral data
• Grounding latent algorithm routing in transformer reasoning
• Time-Series Anomaly Detection for Mobile Robots in Automotive Active Safety Testing using an RNN-VAE
• Combining gravitational wave search pipelines to find subthreshold signals in GWTC-5.0
• Synthetic minority data is redundant or invalid: a data-dependent validity theory and a de-biased test
• SALT: Salience-Aware Lexical Trie for Long-Context Compression
• The Calibration Channel Determines the Bayes-Error Proxy: An Exact Law for Temperature-Induced Distortion
• Radio Map Updating from Streaming Spectrum Measurements via Memory-Based Online Gaussian Processes
• Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction
• SAR Vessel Detection and Gross Tonnage Estimation from Heterogeneous Datasets for Dark Vessel Identification
• Depth-Dependent Hidden-State Collapse in Dynamical System Autoencoders for LiDAR Point-Cloud Classification
• GeoDetect: Geometric Adversarial Detection for VLPs
• Hybrid neural interpolation of a sequence of wind flows
• A diverse community constitutes global coccolithophore calcium carbonate stocks
• Footprints of Data in a Classifier: Understanding the Privacy Risks and Solution Strategies
• DW-KNN: A Transparent Local Classifier Integrating Distance Consistency and Neighbor Reliability
• Hierarchical pattern recognition for tourism demand forecasting
• Machine learning-enhanced nuclear charge radius predictions: A comprehensive comparative analysis
• Explainable Artificial Intelligence (XAI) on TimeSeries Data: A Survey
• Enhancing the classification of isolated theropod teeth using machine learning: a comparative study
• Motion-Based Handwriting Recognition
• Enhancing Noise Resilience in Face Clustering via Sparse Differential Transformer
• SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems
• Sheet As Token: A Graph-Enhanced Representation for Multi-Sheet Spreadsheet Understanding
• Deep learning approaches show promise for predicting childhood malnutrition: A comparative study with traditional machine learning methods using survey data
• Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology
• FC-MIR: A Mobile Screen Awareness Framework for Intent-Aware Recommendation based on Frame-Compressed Multimodal Trajectory Reasoning
• IoMT-based Automated Leukemia Classification using CNN and Higher Order Singular Value
• Tracking Wildfire Assets with Commodity RFID and Gaussian Process Modeling
• Packed Malware Detection Using Grayscale Binary-to-Image Representations
• Residual GRU+MHSA: A Lightweight Hybrid Recurrent Attention Model for Cardiovascular Disease Detection
• Super Suffixes: Bypassing Text Generation Alignment and Guard Models Simultaneously
• Characterizing the Impact of Non-Stand Replacing Disturbances on LiDAR Based Forest Structure Using a Harmonized Landsat-Sentinel-2 Time-Series
• Continuous Edit Distance, Geodesics and Barycenters of Time-varying Persistence Diagrams
• Pathways of Distinction Analysis: a new technique for multi-SNP analysis\n of GWAS data
• Dual-Branch Center-Surrounding Contrast: Rethinking Contrastive Learning for 3D Point Clouds
• A Persistent Homology Pipeline for the Analysis of Neural Spike Train Data
• Driver Drowsiness Classification Based on Eye Blink and Head Movement\n Features Using the k-NN Algorithm
• LM-CartSeg: Automated Segmentation of Lateral and Medial Cartilage and Subchondral Bone for Radiomics Analysis
• Representation of Inorganic Synthesis Reactions and Prediction: Graphical Framework and Datasets
• Fiber Bundle Networks: A Geometric Machine Learning Paradigm
• Research on Milling Machine Predictive Maintenance Based on Machine Learning and SHAP Analysis in Intelligent Manufacturing Environment
• One Swallow Does Not Make a Summer: Understanding Semantic Structures in Embedding Spaces
• Heterogeneous Multi-Agent Reinforcement Learning with Attention for Cooperative and Scalable Feature Transformation
• A Survey on Malware Detection Using Data Mining Techniques
• Exploring Hidden Geographic Disparities in Android Apps
• Adversarial Poisoning Attacks and Defense for General Multi-Class Models\n Based On Synthetic Reduced Nearest Neighbors
• When barchan dunes move over craters
• Identifying environmental factors associated with tetrodotoxin contamination in bivalve mollusks using eXplainable AI
• Provably Outlier-resistant Semi-parametric Regression for Transferable Calibration of Low-cost Air-quality Sensors
• KOM: A Multi-Agent Artificial Intelligence System for Precision Management of Knee Osteoarthritis (KOA)
• MF-GCN: A Multi-Frequency Graph Convolutional Network for Tri-Modal Depression Detection Using Eye-Tracking, Facial, and Acoustic Features
• Implementation of machine-learning classification in remote sensing: an applied review
• Machine Learning vs. Randomness: Challenges in Predicting Binary Options Movements
• iLTM: Integrated Large Tabular Model
• Knowledge Graphs as Structured Memory for Embedding Spaces: From Training Clusters to Explainable Inference
• Design of novel PI3Kα and PI3Kγ inhibitors for cancer treatment using pharmacophore, protein–ligand contacts, and machine learning methods
• Similarity Search and Locality Sensitive Hashing using TCAMs
• Approximate Message Passing with Nearest Neighbor Sparsity Pattern Learning
• A Hybrid Swarm and Gravitation based feature selection algorithm for Handwritten Indic Script Classification problem
• DenoGrad: A Gradient-Based Framework for Data Refinement in Tabular and Time-Series Learning
• AdaptViG: Adaptive Vision GNN with Exponential Decay Gating
• Predicting student outcomes using digital logs of learning behaviors: Review, current standards, and suggestions for future work
• One Model for All: Universal Pre-training for EEG based Emotion Recognition across Heterogeneous Datasets and Paradigms
• Fuzzy Label: From Concept to Its Application in Label Learning
• Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier
• MG-HGNN: A Heterogeneous GNN Framework for Indoor Wi-Fi Fingerprint-Based Localization
• Robust Nearest Neighbour Retrieval Using Targeted Manifold Manipulation
• Prototype Selection Using Topological Data Analysis
• Going Beyond Expert Performance via Deep Implicit Imitation Reinforcement Learning
• Targeted Resilient Zoning for High Impact Events via Multi Circuit Polelines
• Robust Machine Learning for Encrypted Traffic Classification
• Exemplar-Based Open-Set Panoptic Segmentation Network
• Competing AI: How does competition feedback affect machine learning?
• Multivariate feature ranking of gene expression data
• Fingerprint localisation for fine‐scale wildlife tracking using automated radio telemetry
• Deep Long-Tailed Learning: A Survey
• KNN Classification with One-step Computation
• The GIST Korea Test System: A Public-Data Synthetic Model of the Korean Power Grid
• Effective data generation for imbalanced learning using conditional generative adversarial networks
• A Data Quality-Driven View of MLOps
• Structure of scientific knowledge flows to intergovernmental organizations
• Fast and Bayes-consistent nearest neighbors
• A Survey on Metric Learning for Feature Vectors and Structured Data
• Multi-Agent Transactive Memory
• Adversarial Self-Supervised Learning for Semi-Supervised 3D Action Recognition
• Designing a robust feature extraction method based on optimum allocation and principal component analysis for epileptic EEG signal classification
• Query complexity of adversarial attacks
• QSAR without borders
• Statistical Machine Learning and Dissolved Gas Analysis: A Review
• Evidential instance selection for K-nearest neighbor classification of big data
• Back into Plato's Cave: Examining Cross-modal Representational Convergence at Scale
• On the consistency of supervised learning with missing values
• Flexible Operator Embeddings via Deep Learning
• Deep Graph Similarity Learning: A Survey
• SPORE: Skeleton Propagation Over Recalibrating Expansions
• <scp>MediaMatch</scp> : Prediction of Bacterial Growth on Different Culture Media Using the <scp>XGBoost</scp> Algorithm
• Combining SHAP and Causal Analysis for Interpretable Fault Detection in Industrial Processes
• Exploration of Machine Learning Methods to Seismic Event Discrimination in the Pacific Northwest
• Enhancing Identification of Structure Function of Academic Articles Using Contextual Information
• Do Stop Me Now: Detecting Boilerplate Responses with a Single Iteration
• Memory-based Language Models: An Efficient, Explainable, and Eco-friendly Approach to Large Language Modeling
• RadioMapMotion: A Dataset and Baseline for Proactive Spatio-Temporal Radio Environment Prediction
• PSO-XAI: A PSO-Enhanced Explainable AI Framework for Reliable Breast Cancer Detection
• Towards Accurate and Efficient Waste Image Classification: A Hybrid Deep Learning and Machine Learning Approach
• Noisy data clusters are hollow
• Identify Significant Phenomenon-Specific Variables for Multivariate Time Series
• Enhancing Urban Data Exploration: Layer Toggling and Visibility-Preserving Lenses for Multi-Attribute Spatial Analysis
• DETree: DEtecting Human-AI Collaborative Texts via Tree-Structured Hierarchical Representation Learning
• VizCopilot: Fostering Appropriate Reliance on Enterprise Chatbots with Context Visualization
• Text-Enhanced Panoptic Symbol Spotting in CAD Drawings
• USA Tariffs Effect: Machine Learning Insights into the Stock Market
• Behind Python: The Languages That Power AI
• ATLO-ML: Adaptive Time-Length Optimizer for Machine Learning -- Insights from Air Quality Forecasting
• IMLP: An Energy-Efficient Continual Learning Method for Tabular Data Streams
• Crash Severity Prediction Using Deep Learning Approaches: A Hybrid CNN-RNN Framework
• Evaluating Embedding Frameworks for Scientific Domain
• Breaking the Euclidean Barrier: Hyperboloid-Based Biological Sequence Analysis
• Network-Level Vehicle Delay Estimation at Heterogeneous Signalized Intersections
• Automated Alignment of Math Items to Content Standards in Large-Scale Assessments Using Language Models
• Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph
• Physics-Informed Inductive Biases for Voltage Prediction in Distribution Grids
• How Well Do LLMs Imitate Human Writing Style?
• Advancing antimicrobial polymer development: a novel database and accelerated design <i>via</i> machine learning
• In-Context Compositional Q-Learning for Offline Reinforcement Learning
• Spatially informed graph transformers for spatially resolved transcriptomics
• Fast Search with Poor OCR
• Consistent Nonparametric Regression
• AI‐Assisted Morphometric Analysis and Molecular Phylogeny for a Dactylogyrid (Monopisthocotyla) Skin Parasite of an Ornamental Crenuchid Fish From Brazil
• Shapley Features for Robust Signal Prediction in Tactile Internet
• On Enhancing The Performance Of Nearest Neighbour Classifiers Using Hassanat Distance Metric
• Structure-Aware Face Clustering on a Large-Scale Graph with \bf10⁷ Nodes
• Memory Efficient Tabular Foundation Models
• GMM-PACO: Gaussian Mixture Models and Pareto-Based Ant Colony Optimization for Multi-objective Feature Selection
• Turing-Universal Learners with Optimal Scaling Laws
• Motion prediction and validation considering perceived risk-based three-dimensional collision avoidance
• From pixels to peaks: integrating LiDAR and RGB drone imagery to map mussel spat on intertidal rocky shores
• Inertial sensor-based gait classification for frailty status in older adults: A cross-sectional study
• Efficient Structure from Motion for Oblique UAV Images Based on Maximal Spanning Tree Expansions
• k-Nearest Neighbors by Means of Sequence to Sequence Deep Neural Networks and Memory Networks
• scGMB: A scRNA‐seq Cell Classification Method Combining GCN and Mamba
• Classification Using Proximity Catch Digraphs (Technical Report)
• The Tribes of Machine Learning and the Realm of Computer Architecture
• Consistency-Aware Parameter-Preserving Knowledge Editing Framework for Multi-Hop Question Answering
• Cluster Workload Allocation: A Predictive Approach Leveraging Machine Learning Efficiency
• Enhancing Performance and Calibration in Quantile Hyperparameter Optimization
• SemanticGarment: Semantic-Controlled Generation and Editing of 3D Gaussian Garments
• Make Your Bone Great Again : A study on Osteoporosis Classification
• Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
• Theoretical analysis of cross-validation for estimating the risk of the k-Nearest Neighbor classifier
• Performance evaluation of compact plastic scintillating fiber modules for muon tomography applications
• A Systematic Literature Review on Multi-label Data Stream Classification
• Object Recognition and Force Estimation with the GelSight Baby Fin Ray
• Distance Metric Learning for Kernel Machines
• Real-Time Detection and Tracking of Foreign Object Intrusions in Power Systems via Feature-Based Edge Intelligence
• Similarity-Distance-Magnitude Activations
• Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers
• Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization
• MachineLearningLM: Scaling Many-shot In-context Learning via Continued Pretraining
• Laguerre-Gauss Preprocessing: Line Profiles as Image Features for Aerial\n Images Classification
• Does data interpolation contradict statistical optimality?
• GUIDe: Generative and Uncertainty-Informed Inverse Design for On-Demand Nonlinear Functional Responses
• Light curve classification with DistClassiPy: A new distance-based classifier
• Clustering and Classification with Non-Existence Attributes: A Sentenced Discrepancy Measure Based Technique
• Enhancing Self-Supervised Speaker Verification Using Similarity-Connected Graphs and GCN
• Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study
• Guess-and-Learn (G&amp;L): Measuring the Cumulative Error Cost of Cold-Start Adaptation
• Encoding Tactile Stimuli for Organoid Intelligence in Braille Recognition
• A Twin Neural Model for Uplift
• SPELUNKER: Item Similarity Search Using Large Language Models and Custom K-Nearest Neighbors
• Word2Vec applied to Recommendation: Hyperparameters Matter
• Multivariate k-nearest neighbor density estimates
• Novel Approaches to Artificial Intelligence Development Based on the Nearest Neighbor Method
• Kinetic Song Comprehension: Deciphering Personal Listening Habits via Phone Vibrations
• Not All are Made Equal: Consistency of Weighted Averaging Estimators Under Active Learning
• SVM and ELM: Who Wins? Object Recognition with Deep Convolutional Features from ImageNet
• FLAIR: Feedback Learning for Adaptive Information Retrieval
• Machine learning algorithms for predicting malnutrition among under-five children in Bangladesh
• Cost-Aware Contrastive Routing for LLMs
• M3OOD: Automatic Selection of Multimodal OOD Detectors
• Anomaly Detection for IoT Global Connectivity
• Fast local linear regression with anchor regularization
• Dynamic Feature Scaling for K-Nearest Neighbor Algorithm
• Remote Sensing Image Intelligent Interpretation with the Language-Centered Perspective: Principles, Methods and Challenges
• A test statistic, h^*, for outlier analysis
• Land surface dynamics and meteorological forcings modulate land surface temperature characteristics
• Decoupling Understanding from Reasoning via Problem Space Mapping for Small-Scale Model Reasoning
• Argumentative Debates for Transparent Bias Detection [Technical Report]
• Energy-Efficient Real-Time 4-Stage Sleep Classification at 10-Second Resolution: A Comprehensive Study
• A Mathematical Programming approach to Binary Supervised Classification with Label Noise
• Deep Learning with Gaussian Differential Privacy
• Bayes Imbalance Impact Index: A Measure of Class Imbalanced Dataset for Classification Problem
• A Novel Sliced Fused Gromov-Wasserstein Distance
• Expressivity of expand-and-sparsify representations
• Toward Using Machine Learning as a Shape Quality Metric for Liver Point Cloud Generation
• Model Recycling Framework for Multi-Source Data-Free Supervised Transfer Learning
• Defending Against Beta Poisoning Attacks in Machine Learning Models
• What's Taboo for You? - An Empirical Evaluation of LLMs Behavior Toward Sensitive Content
• BS-1-to-N: Diffusion-Based Environment-Aware Cross-BS Channel Knowledge Map Generation for Cell-Free Networks
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory
• RadioMamba: Breaking the Accuracy-Efficiency Trade-off in Radio Map Construction via a Hybrid Mamba-UNet
• Maximum Margin Multiclass Nearest Neighbors
• Perturbative GAN: GAN with Perturbation Layers
• An Adjusted Nearest Neighbor Algorithm Maximizing the F-Measure from\n Imbalanced Data
• Learning the Experts for Online Sequence Prediction
• Machine learning-guided optimization of flame retardancy in rigid polyurethane foams
• Challenges and opportunities of deep learning-based process fault detection and diagnosis: a review
• Classification of schizophrenia patients based on resting-state functional network connectivity. [europepmc]
• The distance function effect on k-nearest neighbor classification for medical datasets. [europepmc]
• A real-time phenotyping framework using machine learning for plant stress severity rating in soybean. [europepmc]
• Individual Differences in Frequency and Topography of Slow and Fast Sleep Spindles. [europepmc]
• In Silico Prediction of Chemical Toxicity for Drug Design Using Machine Learning Methods and Structural Alerts. [europepmc]
• A Review of Emotion Recognition Using Physiological Signals. [europepmc]
• Machine Learning Based Toxicity Prediction: From Chemical Structural Description to Transcriptome Analysis. [europepmc]
• A Comprehensive Review of Magnetoencephalography (MEG) Studies for Brain Functionality in Healthy Aging and Alzheimer's Disease (AD). [europepmc]
• Predicting patient-reported outcomes following hip and knee replacement surgery using supervised machine learning. [europepmc]
• Comparing different supervised machine learning algorithms for disease prediction. [europepmc]
• Machine learning can predict survival of patients with heart failure from serum creatinine and ejection fraction alone. [europepmc]
• CoMPARA: Collaborative Modeling Project for Androgen Receptor Activity. [europepmc]
• An artificial intelligence decision support system for the management of type 1 diabetes. [europepmc]
• Machine learning-guided discovery and design of non-hemolytic peptides. [europepmc]
• Embeddings from deep learning transfer GO annotations beyond homology. [europepmc]
• CATMoS: Collaborative Acute Toxicity Modeling Suite. [europepmc]
• α-Synuclein in blood exosomes immunoprecipitated using neuronal and oligodendroglial markers distinguishes Parkinson's disease from multiple system atrophy. [europepmc]
• Identification of microbial markers across populations in early detection of colorectal cancer. [europepmc]
• A deep look into radiomics. [europepmc]
• Guidelines for bioinformatics of single-cell sequencing data analysis in Alzheimer's disease: review, recommendation, implementation and application. [europepmc]
• Single-nucleus RNA-sequencing of autosomal dominant Alzheimer disease and risk variant carriers. [europepmc]
• Deep Learning Approaches for Data Augmentation in Medical Imaging: A Review. [europepmc]
• A Review of Single-Cell RNA-Seq Annotation, Integration, and Cell-Cell Communication. [europepmc]
• Accurately identifying hemagglutinin using sequence information and machine learning methods. [europepmc]
• Self-Driving Laboratories for Chemistry and Materials Science. [europepmc]

Related

• Asymptotic Properties of Nearest Neighbor Rules Using Edited Data
• Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
• Local nearest neighbour classification with applications to semi-supervised learning
• Nearest Neighbor Classification based on Imbalanced Data: A Statistical Approach
• Speculate-Correct Error Bounds for k-Nearest Neighbor Classifiers