More Web Proxy on the site http://driver.im/

article

A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm

Authors:

Thanapant Raicharoen,

Chidchanok LursinsapAuthors Info & Claims

Pattern Recognition Letters, Volume 26, Issue 10

Pages 1554 - 1567

Published: 01 July 2005 Publication History

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.

References

[1]

Voting over multiple condensed nearest neighbors. Artificial Intell. Rev. v11. 115-132.

[2]

Finding prototypes for nearest neighbor classifiers. IEEE Trans. Computer. v23 i11. 1179-1184.

[3]

The condensed nearest neighbor rule using the concept of mutual nearest neighborhood. IEEE Trans. Inform. Theory. v25 i4. 488-490.

[4]

Support Vector Networks. Mach. Learn. v20 i3. 273-297.

[5]

Nearest neighbor pattern classification. IEEE Trans. Inform. Theory. v13. 21-27.

[6]

Nearest neighbor editing and condensing tools-synergy exploitation. Pattern Anal. Appl. v3. 19-30.

[7]

An incremental prototype set building technique. Pattern Recognit. v35. 505-513.

[8]

Pattern Recognition: A Statistical Approach. Prentice-Hall, Englewood Cliffs, NJ.

[9]

A Probabilistic Theory of Pattern Recognition. Springer-Verlag, Inc, New York.

[10]

Pattern Classification. John Wiley and Sons, Inc.

[11]

Considerations about sample-size sensitivity of a family of edited nearest neighbor rules. IEEE Trans. Systems Man Cybernet. B. v29 i5. 667-672.

[12]

The reduced nearest neighbor rule. IEEE Trans. Inform. Theory. v18. 431-433.

[13]

Hart, P.E., 1966. An asymptotic analysis of the nearest-neighbor decision rule. Stanford Electron. Lab., Stanford, Calif., Tech. Rep., SEL-66-016, 1828-2.

[14]

The condensed nearest neighbor rule. IEEE Trans. Inform. Theory. v14 i3. 515-516.

[15]

Hastie, T., Tibshirani, R., Friedman, J., 2001. The Elements of Statistical Learning. Springer Series in Statistics, Springer-Verlag.

[16]

Probability and Statistics for Engineers and Scientists. Duxbury.

[17]

Nearest prototype classification: Clustering, genetic algorithm, or random search?. IEEE Trans. Systems Man Cybernet. C. v28 i1. 160-164.

[18]

Statistics for Business and Economics. Prentice Hall.

[19]

Michie, D., Spiegelhalter, D.J., Taylor, C.C., 1994. Machine learning, neural and statistical classification. Available from <ftp://ftp.ncc.up.pt/pub/statlog>.

[20]

Machine Learning. McGraw Hill.

[21]

Murphy, P.M., Aha, D.W., 1994. UCI Repository of machine learning databases {http://www.ics.uci.edu/mlearn/MLRepository.html}, Department of Information and Computer Science, University of California, Irvine, CA.

[22]

An algorithm for a selective nearest neighbor rule. IEEE Trans. Inform. Theory. v23. 1179-1184.

[23]

Roobaert, D., 2000. DirectSVM: A simple support vector machine perceptron. In: Proceedings of IEEE International Workshop on Neural Networks for Signal Processing, Sydney, Australia.

[24]

Analysis of new techniques to obtain quality training sets. Pattern Recognit. Lett. v24. 1015-1022.

[25]

Two modifications of CNN. IEEE Trans. Systems Man Cybernet. Cybernet. v2. 769-772.

[26]

A counterexample to Tomek's consistency theorem for a condensed nearest neighbor. Pattern Recognit. Lett. v15. 797-801.

[27]

Toussaint, G., 2002. Proximity Graphs for Nearest Neighbor Decision Rules: Recent Progress. In: Proceedings of 34 th Symposium on Computing and Statistics, Montreal, Canada.

[28]

USPS, 1994. Machine learning, neural and statistical classification. Available from <fpt://ftp.kyb.tuebingen.mpg.de/pub/bs/data/>.

[29]

Statistical Learning Theory. Wiley, New York.

[30]

Asymtotic properties of nearest neighbor rules using edited data. IEEE Trans. Systems Man Cybernet. Cybernet. v2. 408-420.

Cited By

Akinyelu AEzugwu AAdewumi A(2019)Ant colony optimization edge selection for support vector machine speed optimizationNeural Computing and Applications10.1007/s00521-019-04633-832:15(11385-11417)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1007/s00521-019-04633-8
Dif NElberrichi Z(2018)A Multi-Verse Optimizer Approach for Instance Selection and Optimizing 1-NN AlgorithmInternational Journal of Strategic Information Technology and Applications10.4018/IJSITA.20180401039:2(35-49)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJSITA.2018040103
Akinyelu AAdewumi A(2017)Improved Instance Selection Methods for Support Vector Machine Speed OptimizationSecurity and Communication Networks10.1155/2017/67909752017Online publication date: 9-Jan-2017
https://dl.acm.org/doi/10.1155/2017/6790975
Show More Cited By

A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
    2. Machine learning approaches

Recommendations

A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm for regression problem
ICONIP'06: Proceedings of the 13 international conference on Neural Information Processing - Volume Part I

This paper presents a method for regression problem based on divide-and-conquer approach to the selection of a set of prototypes from the training set for the nearest neighbor rule. This method aims at detecting and eliminating redundancies in a given ...
Salience-Based prototype selection for k-nearest neighbor classification in multiple-instance learning
IScIDE'12: Proceedings of the third Sino-foreign-interchange conference on Intelligent Science and Intelligent Data Engineering

The k-nearest neighbor algorithm (kNN) is one of the most well-known techniques in standard supervised learning. It could be adapted to the setting of multiple-instance learning (MIL) by using set-based distance metrics, such as Citation-kNN and ...
Semi-supervised learning based on nearest neighbor rule and cut edges

In this paper, we propose a novel semi-supervised learning approach based on nearest neighbor rule and cut edges. In the first step of our approach, a relative neighborhood graph based on all training samples is constructed for each unlabeled sample, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Pattern Recognition Letters

Pattern Recognition Letters Volume 26, Issue 10

July, 2005

204 pages

ISSN:0167-8655

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2005.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 July 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Akinyelu AEzugwu AAdewumi A(2019)Ant colony optimization edge selection for support vector machine speed optimizationNeural Computing and Applications10.1007/s00521-019-04633-832:15(11385-11417)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1007/s00521-019-04633-8
Dif NElberrichi Z(2018)A Multi-Verse Optimizer Approach for Instance Selection and Optimizing 1-NN AlgorithmInternational Journal of Strategic Information Technology and Applications10.4018/IJSITA.20180401039:2(35-49)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJSITA.2018040103
Akinyelu AAdewumi A(2017)Improved Instance Selection Methods for Support Vector Machine Speed OptimizationSecurity and Communication Networks10.1155/2017/67909752017Online publication date: 9-Jan-2017
https://dl.acm.org/doi/10.1155/2017/6790975
Khosravani HRuano AFerreira P(2016)A convex hull-based data selection method for data driven modelsApplied Soft Computing10.1016/j.asoc.2016.06.01447:C(515-533)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.asoc.2016.06.014
Hamidzadeh JMonsefi RSadoghi Yazdi H(2015)IRAHCPattern Recognition10.1016/j.patcog.2014.11.00548:5(1878-1889)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.patcog.2014.11.005
Olvera-López JCarrasco-Ochoa JMartínez-Trinidad JKittler J(2010)A review of instance selection methodsArtificial Intelligence Review10.1007/s10462-010-9165-y34:2(133-143)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1007/s10462-010-9165-y
Olvera-López JCarrasco-Ochoa JMartínez-Trinidad J(2010)A new fast prototype selection method based on clusteringPattern Analysis & Applications10.1007/s10044-008-0142-x13:2(131-141)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1007/s10044-008-0142-x
Raicharoen TLursinsap CLin F(2006)A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm for regression problemProceedings of the 13 international conference on Neural Information Processing - Volume Part I10.1007/11893028_85(765-772)Online publication date: 3-Oct-2006
https://dl.acm.org/doi/10.1007/11893028_85

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents