A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm
Pattern Recognition LettersPublished 18 February 2005
Thanapant Raicharoen, Chidchanok Lursinsap
Citations60
SJR quartileQ1
SJR score1.00
SNIP1.43
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new method based on divide-and-conquer approach to the selection and replacement of a set of prototypes from the training set for the nearest neighbor rule, which aims at reducing the computational time and the memory space as well as the sensitivity of the order and the noise of the training data.
Abstract
This paper presents a new method based on divide-and-conquer approach to the selection and replacement of a set of prototypes from the training set for the nearest neighbor rule. This method aims at reducing the computational time and the memory space as well as the sensitivity of the order and the noise of the training data. A reduced prototype set contains Pairwise Opposite Class-Nearest Neighbor (POC-NN) prototypes which are close to the decision boundary and used instead of the training patterns. POC-NN prototypes are obtained by recursively iterative separation and analysis of the training data into two regions until each region is correctly grouped and classified. The separability is determined by the POC-NN prototypes essential to define the locations of all separating hyperplanes. Our method is fast and order independent. The number of prototypes and the overfitting of the model can be reduced by the user. The experimental results signify the effectiveness of this technique and its performance in both accuracy and prototype rate as well as in training time to those obtained by classical nearest neighbor techniques.
Keywords
Computer Science
Machine LearningSupport-vector networks
40,463 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Springer series in statisticsThe Elements of Statistical Learning
24,344 Citations2001Trevor Hastie, J. Friedman +1 more
IEEE Transactions on Information TheoryNearest neighbor pattern classification
16,134 Citations1967Thomas M. Cover, Peter E. Hart
The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
Advances in industrial controlPattern Classification
7,884 Citations2000Evan L. Russell, Leo H. Chiang +1 more
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
TechnometricsMachine Learning, Neural and Statistical Classification
2,188 Citations1995Bill Fulkerson, D. Michie +2 more
IEEE Transactions on Systems Man and CyberneticsAsymptotic Properties of Nearest Neighbor Rules Using Edited Data
2,050 Citations1972Dennis L. Wilson
The convergence properties of a nearest neighbor rule that uses an editing procedure to reduce the number of preclassified samples and to improve the performance of the rule are developed.
Statistics for Engineers and Scientists
590 Citations2004William Navidi
This chapter discusses sampling and Descriptive Statistics, statistical quality control, and hypothesis testing in the context of discrete-time linear regression.
IEEE Transactions on Information TheoryThe reduced nearest neighbor rule (Corresp.)
560 Citations1972Geoffrey W. Gates
A further modification to Cover and Hart's nearest neighbor decision rule, the reduced nearest neighbor rule, is introduced and experimental results demonstrate its accuracy and efficiency.
The Reduced Nearest Neighbor Rule
419 Citations1998Geoffrey W. Gates
ACM SIGART BulletinBook review: Machine Learning, Neural and Statistical Classification Edited by D. Michie, D.J. Spiegelhalter and C.C. Taylor (Ellis Horwood Limited, 1994)
371 Citations1996Huan Liu
This well-edited book provides an up-to-date review of different approaches to classification, compares their performance on a wide range of challenging datasets, and draws conclusions on their applicability to realistic industrial problems.
IEEE Transactions on ComputersFinding Prototypes For Nearest Neighbor Classifiers
327 Citations1974Chin-Liang Chang
An algorithm is given to find prototypes for a nearest neighbor classifier, which is to start with every sample in a training set as a prototype, and then successively merge any two nearest prototypes of the same class so long as the recognition rate is not downgraded.
IEEE Transactions on Information TheoryAn algorithm for a selective nearest neighbor decision rule (Corresp.)
326 Citations1975G. L. Ritter, H. B. Woodruff +2 more
A procedure is introduced to approximate nearest neighbor (INN) decision boundaries that produces a selective subset of the original data so that the subset is consistent, the distance between any sample and its nearest selective neighbor is less than the distance from the sample to any sample of the other class.
IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews)Nearest prototype classification: clustering, genetic algorithms, or random search?
213 Citations1998Ludmila I. Kuncheva, James C. Bezdek
This research compares the resubstitution performance of the NPC on the IRIS data set and recommends GA selection for the NPC, which compares favorably to the best result found with R-prototypes.
Pattern Recognition LettersAnalysis of new techniques to obtain quality training sets
176 Citations2002J. Salvador Sánchez
New algorithms to identify and eliminate mislabelled, noisy and atypical training samples for supervised learning and more specifically, for nearest neighbour classification are presented.
IEEE Transactions on Information TheoryThe condensed nearest neighbor rule using the concept of mutual nearest neighborhood (Corresp.)
146 Citations1979Kiran Gowda, G. Krishna
A two-stage iterative algorithm for selecting a subset of a training set of samples for use in a condensed nearest neighbor (CNN) decision rule is introduced.
Artificial Intelligence ReviewVoting over Multiple Condensed Nearest Neighbors
96 Citations1997Ethem Alpaydın
The condensed nearest neighbor classifier incrementally stores a subset of the sample, thus decreasing storage and computation requirements and it is proposed to train multiple such subsets and take a vote over them, thus combining predictions from a set of concept descriptions.
Pattern RecognitionAn incremental prototype set building technique
91 Citations2002V. Susheela Devi, M. Narasimha Murty
A reduced set is obtained which is used instead of the training set when nearest neighbour classification is used and this method has been used to obtain the prototypes for a variety of benchmark data sets.
Pattern Analysis and ApplicationsNearest Neighbour Editing and Condensing Tools–Synergy Exploitation
78 Citations2000B.V. Dasarathy, J. Salvador Sánchez +1 more
This study addresses the issue of minimising the computational resource requirements of NN techniques, memory as well as time, through the use of prototype reduction techniques such as Minimal Consistent Set (MCS) selection while preserving the performance quality through suitable editing techniques, such as Proximity Graphs (PG).
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Considerations about sample-size sensitivity of a family of edited nearest-neighbor rules
67 Citations1999Francesc J. Ferri, J. Albert +1 more
This paper investigates the possibility of modifying optimal editing to cope with a broader range of practical situations and shows the relative limits in the applicability of different editing algorithms.
DirectSVM: a fast and simple support vector machine perceptron
27 Citations2002Danny Roobaert
A simple implementation of the support vector machine (SVM) for pattern recognition, that is not based on solving a complex quadratic optimization problem, is proposed, based on a few simple heuristics.
The Journal of VLSI Signal Processing Systems for Signal Image and Video TechnologyDirectSVM: A Simple Support Vector Machine Perceptron
18 Citations2002Danny Roobaert
A very simple learning algorithm, DirectSVM, for constructing support vector machine classifiers, based on the proposition that the two closest training points of opposite class in a training set are support vectors, on condition that the training points in the set are linearly independent.
Pattern Recognition LettersA counterexample to Tomek's consistency theorem for a condensed nearest neighbor decision rule
9 Citations1994Godfried T. Toussaint
The condensed nearest neighbor rule was proposed by Hart (1968) as a method to reduce the storage requirements of the original data set D for the efficient implementation of the nearest neighbor decision rule in pattern classification problems and Tomek's algorithm is analyzed.