Fast Pattern Selection Algorithm for Support Vector Classifiers: Time Complexity Analysis
Lecture notes in computer sciencePublished 1 January 2003
Hyunjung Shin, Sungzoon Cho
Citations13
SJR quartileQ2
SJR score0.35
SNIP0.55
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 fast preprocessing algorithm which selects only the patterns near the decision boundary is proposed which is much smaller than that of the naive M 2 algorithm.
Abstract
Training SVM requires large memory and long cpu time when the pattern set is large. To alleviate the computational burden in SVM training, we propose a fast preprocessing algorithm which selects only the patterns near the decision boundary. The time complexity of the proposed algorithm is much smaller than that of the naive M 2 algorithm
Keywords
Computer Science
IEEE Intelligent Systems and their ApplicationsSupport vector machines
6,931 Citations1998Marti A. Hearst, Susan Dumais +3 more
This issue's collection of essays should help familiarize readers with this interesting new racehorse in the Machine Learning stable, and give a practical guide and a new technique for implementing the algorithm efficiently.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
Journal of the ACMAn optimal algorithm for approximate nearest neighbor searching fixed dimensions
2,321 Citations1998Sunil Arya, David M. Mount +3 more
It is shown that it is possible to preprocess a set of data points in real D-dimensional space in O(kd) time and in additional space, so that given a query point q, the closest point of S to S to q can be reported quickly.
IEEE Transactions on Information TheoryThe optimal distance measure for nearest neighbor classification
239 Citations1981Robert D. Short, Keinosuke Fukunaga
A local distance measure is shown to optimize the performance of the nearest neighbor two-class classifier for a finite number of samples using the difference between the finite sample error and the asymptotic error as the criterion of improvement.
SVM-KM: speeding SVMs learning with a priori cluster selection and k-means
130 Citations2002Marcelo Barros de Almeida, Antônio P. Braga +1 more
The number of vectors in a SVM training is smaller and the training time can be decreased without compromising the generalization capability of the SVM.
Pattern RecognitionFast implementations of nearest neighbor classifiers
71 Citations1997Patrick Grother, Gerald T. Candela +1 more
Four techniques for expediting the nearest neighbor methods are described: replacing the linear search with a new kd tree method, exhibiting approximately O (N 1 2 ) behavior; employing an L ∞ instead of L 2 distance metric; using variance-ordered features; and rejecting prototypes by evaluating distances in low dimensionality subspaces.
IEEE Transactions on Neural NetworksSample selection via clustering to construct support vector-like classifiers
69 Citations1999Abdelouahid Lyhyaoui, M.A. Martı́nez +4 more
Simulation results for well-known classification problems show very good performance of the corresponding designs, improving that of support vector machines and reducing substantially their number of units, which shows that interest in selecting samples (or centroids) in an efficient manner is justified.
MPG.PuRe (Max Planck Society)Fast Pattern Selection for Support Vector Classifiers
58 Citations2003Shin, H., Cho, S.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)The training of neural classifiers with condensed datasets
45 Citations2002Shiu Hong Choi, Peter Rockett
A k-nearest-neighbor-based data condensing algorithm is applied to the training set of multilayer perceptron neural networks to significantly speed the network training time while achieving an undegraded misclassification rate compared to a network trained on the unedited training set.
Lecture notes in computer scienceIntelligent Data Engineering and Automated Learning — IDEAL 2002
43 Citations2002M.Khairudin Kasiran, Farid Meziane +3 more
This paper presents an information model for a merchant trust based on the previously cited factors, and provides a framework for the implementation of the model using intelligent agents.
Lecture notes in computer sciencePattern Selection for Support Vector Classifiers
15 Citations2002Hyunjung Shin, Sungzoon Cho
A k-nearest neighbors (k-NN) based pattern selection method that tries to select the patterns that are near the decision boundary and that are correctly labeled to reduce training time of redundant SVs.
MPG.PuRe (Max Planck Society)Pattern Selection Using the Bias and Variance of Ensemble
9 Citations2001Hyunjung Shin
A pattern 'utility index' that measures the utility of an individual pattern based on the bias and variance of a pattern trained by a network ensemble is proposed.
Termination conditions for a fast k-nearest neighbor method
5 Citations2003Naoki Masuyama, Mineichi Kudo +2 more
A method for reducing the computation cost of searching k-NNs on the basis of the branch-and-bound algorithm while not considering the computation time required for pre-processing is proposed.