Characterizes Lebesgue points using nearest neighbor methods.
problem Consistency of classification algorithms based on nearest neighbors.
method Characterization of Lebesgue points via 1-Nearest Neighbor regression.
result Proves convergence of 1-Nearest Neighbor classification algorithms in metric spaces.
Nearest neighbor methods are a popular class of nonparametric estimators with several desirable properties, such as adaptivity to different distance scales in different regions of space. Prior work on convergence rates for nearest neighbor classification has not fully reflected these subtle properties. We analyze the b…
A new method uses nearest neighbors for importance weighting.
problem Data covariate shift problems in machine learning.
method Nearest neighbor classification scheme for determining importance weights.
result Demonstrated effectiveness through comparative experiments on various classification tasks.
Improved multiclass classification with class-weighted nearest neighbors.
problem Multiclass classification with large or imbalanced classes.
method Class-weighted k-nearest neighbors algorithm, derived bounds on accuracy and risk.
result Optimized classification metrics like F1 score or Matthew's Correlation Coefficient.
BigNN classifier improves nearest neighbor classification for large datasets.
problem Classification of large datasets that cannot fit into a single machine's memory.
method Divide and conquer scheme with majority voting for final decision; pre-training acceleration technique.
result Rates of convergence for bigNN classifier under minimal assumptions, proving it as optimal.
A new multilabel classification framework improves ANN search performance.
problem Efficiently finding approximate nearest neighbors in large datasets.
method Formulated ANN search as a multilabel classification problem, using partitioning classifiers.
result Natural classifier leads to strictly improved performance in ANN search.
The paper explains how nearest neighbor methods succeed in prediction.
problem Explaining the success of nearest neighbor methods in prediction.
method The paper covers both theoretical and practical aspects of nearest neighbor methods, including statistical guarantees and practical algorithms.
result The paper provides nonasymptotic statistical guarantees and practical algorithms for nearest neighbor methods.
Under-bagging k-NN improves performance on imbalanced classification.
problem Imbalanced classification problems where one class is significantly underrepresented.
method Proposes an under-bagging k-NN ensemble learning algorithm, analyzing convergence rates and efficiency. result Achieves optimal convergence rates under mild assumptions and reduces sub-sample size and k for highly imbalanced data. The nearest neighbor method together with the dynamic time warping (DTW) distance is one of the most popular approaches in time series classification. This method suffers from high storage and computation requirements for large training sets. As a solution to both drawbacks, this article extends learning vector quantiz…
We propose a simple kernel based nearest neighbor approach for handwritten digit classification. The "distance" here is actually a kernel defining the similarity between two images. We carefully study the effects of different number of neighbors and weight schemes and report the results. With only a few nearest neighbo…
New method accelerates large margin metric learning for nearest neighbor classification.
problem Efficiently learning metrics for nearest neighbor classification.
method Triplet mining and stratified sampling for large margin metric learning.
result Improved efficiency and scalability of optimization.
Study of classification in asymmetric quasi-metric spaces.
problem Classification in asymmetric quasi-metric spaces.
method Sample compression and nearest neighbor algorithm.
result Algorithm has favorable statistical properties.
Paper proposes a k-NN classifier for detecting spike-and-wave seizures in EEG.
problem Early detection of epileptic seizures in EEG signals.
method Uses t-location-scale distribution and k-nearest neighbors classifier.
result Demonstrates improved classification accuracy, sensitivity, and specificity on real data.
The stability of statistical analysis is an important indicator for reproducibility, which is one main principle of scientific method. It entails that similar statistical conclusions can be reached based on independent samples from the same underlying population. In this paper, we introduce a general measure of classif…
K-Nearest neighbor classifier (k-NNC) is simple to use and has little design time like finding k values in k-nearest neighbor classifier, hence these are suitable to work with dynamically varying data-sets. There exists some fundamental improvements over the basic k-NNC, like weighted k-nearest neighbors classifier (wh…
Improved image classification using centroids and stochastic sampling.
problem Limited accuracy of nearest-neighbor classification.
method Coarse-graining (replacing images by centroids) and stochastic sampling of centroids.
result Stochastic sampling of centroids improves classification accuracy.
This paper compares machine learning algorithms for ecological data.
problem Classifying ecological datasets into subsets with common patterns.
method Applied eight machine learning classification algorithms to ecological data.
result Linear Discriminant Analysis and k-nearest neighbors are the best methods.
Machine learning classifies IoT noise in smart cities.
problem Noise classification in smart cities.
method Mel-frequency cepstral coefficients for audio features, supervised classification (SVM, k-NN), parameter optimization.
result Noise classification accuracy of 85% - 100%.
Enhanced nearest neighbor improves accuracy in crowdsourced data.
problem Noise in crowdsourced labels degrades classification accuracy.
method Developed two algorithms to estimate worker quality and an enhanced nearest neighbor classifier.
result Proposed methods achieve the same regret as oracle version based on expert data.
For classifying time series, a nearest-neighbor approach is widely used in practice with performance often competitive with or better than more elaborate methods such as neural networks, decision trees, and support vector machines. We develop theoretical justification for the effectiveness of nearest-neighbor-like clas…
A new warping-invariant distance improves nearest-neighbor classification efficiency.
problem dtw distance inconsistency and inefficiency in nearest-neighbor classification.
method Showed dtw is not warping-invariant, converted to twi distance.
result twi distance equivalent error rates to dtw, more efficient.
Proposes multi-neighborhood LBPs for land use classification.
problem Challenges in classifying land use images due to intra class variability and inter class similarities.
method Uses multi-neighborhood LBPs combined with nearest neighbor classifier.
result Achieved an accuracy of 77.76% on UC Merced 21 class land use image dataset.
Interpolated nearest neighbor algorithms minimize bias in machine learning models.
problem Understanding and reducing overfitting in machine learning models.
method Proves the interpolated nearest neighbor algorithm achieves minimax optimal rates in regression and classification.
result Interpolated nearest neighbor algorithms are statistically optimal and perform better than traditional methods in some cases.
Improves time series classification with forest proximities.
problem Time series classification accuracy and efficiency.
method PF-GAP, an extension of RF-GAP proximities to proximity forests, combined with Multi-Dimensional Scaling and Local Outlier Factors.
result Forest proximities show stronger connection between misclassified points and outliers.
This research examines how the error rate of nearest neighbor classifiers varies with dataset size.
problem The scaling of classification error rates with dataset size is not uniform.
method Theoretical analysis of nearest neighbor classifiers, focusing on early and late phases of dataset size.
result The error rate of nearest neighbor classifiers can have fine-grained rates depending on the dataset size and data distribution.
SqueezeFit reduces high-dimensional data to lower dimensions while preserving label distances.
problem Label-aware dimensionality reduction in high-dimensional spaces.
method Semidefinite programming relaxation of nearest neighbor classification.
result Provable recovery of a planted projection operator from labeled data.
Given an n-sample of random vectors (Xi,Yi)1≤i≤n whose joint law is unknown, the long-standing problem of supervised classification aims to \textit{optimally} predict the label Y of a given a new observation X. In this context, the nearest neighbor rule is a popular flexible and intuitive method …
The condensed nearest neighbor (CNN) algorithm is a heuristic for reducing the number of prototypical points stored by a nearest neighbor classifier, while keeping the classification rule given by the reduced prototypical set consistent with the full set. I present an upper bound on the number of prototypical points ac…
Method detects adversarial samples using influence functions and nearest neighbors.
problem Detecting adversarial attacks on deep neural networks.
method Influence functions and k-NN model on activation layers.
result Successfully distinguishes adversarial examples with state-of-the-art results.
Enhanced KNN-TSVM reduces noise and overfitting with stable learning rules.
problem High computational cost and overfitting in KNN-based TSVM classifiers.
method Weighted KNN with stabilizer term and LDMDBA for efficient computation.
result Effective in both classification accuracy and computational time, with up to 14x speedup.
k-Nearest Neighbors is one of the most fundamental but effective classification models. In this paper, we propose two families of models built on a sequence to sequence model and a memory network model to mimic the k-Nearest Neighbors model, which generate a sequence of labels, a sequence of out-of-sample feature vecto…
Reduces bounded loss learning to binary classification.
problem Universal consistency of non-i.i.d. processes with bounded loss.
method Constructive reduction to binary classification.
result Any bounded loss output setting can be reduced to binary classification.
This paper proposes a new hashing-based KNN technique for faster nearest neighbor selection.
problem Slowness of KNN in big datasets due to searching entire dataset.
method Divide data space into subcells, use hashing to map data points, and select nearest neighbors layer by layer.
result The proposed technique offers competitive performance with KNN and KDtree while significantly improving time efficiency.
Random forest improves nearest neighbor estimation of information-theoretic quantities.
problem Estimating information-theoretic quantities in high-dimensional and scale-different settings.
method Decision forest-based adaptive nearest neighbor estimators.
result Forest-based estimators effectively estimate posterior probabilities and mutual information.
Multi-Output Dependence (MOD) learning is a generalization of standard classification problems that allows for multiple outputs that are dependent on each other. A primary issue that arises in the context of MOD learning is that for any given input pattern there can be multiple correct output patterns. This changes the…
New method improves nearest neighbor search using neural networks and graph partitioning.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Developed a new framework for space partitioning using neural networks and graph partitioning.
result Neural LSH partitions outperform existing methods on standard benchmarks.
K-nearest neighbors (KNN) method is used in many supervised learning classification problems. Potential Energy (PE) method is also developed for classification problems based on its physical metaphor. The energy potential used in the experiments are Yukawa potential and Gaussian Potential. In this paper, I use both app…
Paper proposes tensor sparse PCA for improved face recognition accuracy.
problem Face recognition accuracy improvement using novel methods.
method Combines tensor sparse PCA with nearest-neighbor and kernel ridge regression methods.
result Tensor sparse PCA method yields better accuracy than PCA method alone.
A new method for learning distance metrics for K-NN classification.
problem Improving the performance of K-NN classifier by learning an appropriate distance metric.
method Designing a continuous decision function for K-NN and minimizing its continuous empirical risk function.
result The proposed ANN algorithm outperforms existing methods like LMNN, NCA, and pairwise constraints.
Unsupervised classifier performs as well as supervised ones on ImageNet dataset.
problem Achieving performance of supervised learning classifiers without labeled data.
method Incremental shift and rotation operations on selected hyperplanes.
result 6.2% Top 3 probability of error on ImageNet dataset.
Visualizes classification results with class maps.
problem Label bias in classification predictions.
method Class maps reflecting probability, distance, and mislabeling likelihood.
result Insight into classification results and data structure.
In the panoply of pattern classification techniques, few enjoy the intuitive appeal and simplicity of the nearest neighbor rule: given a set of samples in some metric domain space whose value under some function is known, we estimate the function anywhere in the domain by giving the value of the nearest sample per the …
A novel distributed adaptive NN classifier for large data sets.
problem Handling large and distributed data for efficient classification.
method Distributed adaptive nearest neighbor classifier with stochastic tuning parameter selection and early stopping rule.
result Achieves nearly optimal convergence rate under large sub-sample sizes.
Dynamic text classification with changing labels using learned metrics.
problem Traditional text classifiers struggle with dynamic label sets.
method Replacing fixed output layer with a learned metric space for nearest-neighbor classification.
result Learning a non-Euclidean metric improves performance in low data regimes.
Study uses machine learning to recommend best solvers for slab transport problems.
problem Auto-selecting the best solvers for transport problems in uniform slabs.
method Three solvers (Richardson, diffusion synthetic acceleration, nonlinear diffusion acceleration) and five machine learning algorithms (linear discriminant analysis, K-nearest neighbors, support vector machine, random forest, neural networks) were tested.
result Random forest and K-nearest neighbors showed potential as best solvers for classification problems.
New bounds for balanced classification improve understanding of imbalanced datasets.
problem Negligible size of the minority class in imbalanced datasets.
method Developed non-asymptotic and consistent bounds for balanced empirical risk minimization and balanced nearest neighbors estimates.
result Improved understanding of class-weighting benefits in real-world imbalanced classification settings.
Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the qu…
A new classifier encodes local neighborhoods for each class using Fly Bloom Filters.
problem Efficiently classify data with single-pass learning.
method Proposes a new classifier that encodes local neighborhoods for each class with per-class Fly Bloom Filters.
result The proposed classifier's performance is competitive with nearest-neighbor classifiers and other single-pass classifiers.