skip to main content
article
Free access

Hit Miss Networks with Applications to Instance Selection

Published: 01 June 2008 Publication History

Abstract

In supervised learning, a training set consisting of labeled instances is used by a learning algorithm for generating a model (classifier) that is subsequently employed for deciding the class label of new instances (for generalization). Characteristics of the training set, such as presence of noisy instances and size, influence the learning algorithm and affect generalization performance. This paper introduces a new network-based representation of a training set, called hit miss network (HMN), which provides a compact description of the nearest neighbor relation over pairs of instances from each pair of classes. We show that structural properties of HMN's correspond to properties of training points related to the one nearest neighbor (1-NN) decision rule, such as being border or central point. This motivates us to use HMN's for improving the performance of a 1-NN, classifier by removing instances from the training set (instance selection). We introduce three new HMN-based algorithms for instance selection. HMN-C, which removes instances without affecting accuracy of 1-NN on the original training set, HMN-E, based on a more aggressive storage reduction, and HMN-EI, which applies iteratively HMN-E. Their performance is assessed on 22 data sets with different characteristics, such as input dimension, cardinality, class balance, number of classes, noise content, and presence of redundant variables. Results of experiments on these data sets show that accuracy of 1-NN classifier increases significantly when HMN-EI is applied. Comparison with state-of-the-art editing algorithms for instance selection on these data sets indicates best generalization performance of HMN-EI and no significant difference in storage requirements. In general, these results indicate that HMN's provide a powerful graph-based representation of a training set, which can be successfully applied for performing noise and redundance reduction in instance-based learning.

References

[1]
D.W. Aha, D. Kibler, and M.K. Albert. Instance-based learning algorithms. Machine Learning, 6: 37-66, 1991.
[2]
F. Angiulli. Fast nearest neighbor condensation for large data sets classification. IEEE Transactions on Knowledge and Data Engineering, 19(11):1450-1464, 2007. ISSN 1041-4347.
[3]
V. Barnett. The ordering of multivariate data. J. Roy. Statist. Soc., Ser. A 139(3):318-355, 1976.
[4]
B. Bhattacharya and D. Kaller. Reference set thinning for the k-nearest neighbor decision rule. Proceedings of the 14th International Conference on Pattern Recognition, (1):238-243, 1998.
[5]
B. Bhattacharya, K. Mukherjee, and G. Toussaint. Geometric decision rules for instance-based learning problems. In Proceedings of the 1st International Conference on Pattern Recognition and Machine Intelligence (PReMI'05), number LNCS 3776, pages 60-69. Springer, 2005.
[6]
B.K. Bhattacharya. Application of computational geometry to pattern recognition problems. PhD Thesis. Simon Fraser University, School of Computing Science, Technical Report, TR 82-3, 1982.
[7]
H. Brighton and C. Mellish. On the consistency of information filters for lazy learning algorithms. In PKDD '99: Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, pages 283-288. Springer-Verlag, 1999.
[8]
H. Brighton and C. Mellish. Advances in instance selection for instance-based learning algorithms. Data Mining and Knowledge Discovery, (6):153-172, 2002.
[9]
R.M. Cameron-Jones. Instance selection by encoding length heuristic with random mutation hill climbing. In Proceedings of the Eighth Australian Joint Conference on Artificial Intelligence, pages 99-16, 1995.
[10]
O. Chapelle and A. Zien. Semi-supervised classification by low density separation. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, pages 57-64, 2005.
[11]
T. Cover and P. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13:21-27, 1967.
[12]
B. V. Dasarathy. Minimal consistent set (mcs) identification for optimal nearest neighbor decision systems design. IEEE Transactions on Systems, Man, and Cybernetics, 24(3):511-517, 1994.
[13]
J. Demsar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1-30, 2006.
[14]
J. DeVinney and C.E. Priebe. The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association. Statistics and Probability Letters, 73 (1):37-50, 2005.
[15]
J. DeVinney and C.E. Priebe. A new family of proximity graphs: Class cover catch digraphs. Discrete Applied Mathematics, 154(14):1975-1982, 2006.
[16]
E.J. Wegman D.J. Marchette and C.E. Priebe. Fast algorithms for classification using class cover catch digraphs. Handbook of Statistics, 24:331-358, 2005.
[17]
S.N. Dorogovtsev and J.F.F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, 2003.
[18]
P.J. Grother, G.T. Candela, and J.L. Blue. Fast implementation of nearest neighbor classifiers. Pattern Recognition, 30:459-465, 1997.
[19]
P. E. Hart. The condensed nearest neighbor rule. IEEE Transactions on Information Theory, 14: 515-516, 1968.
[20]
N. Jankowski and M. Grochowski. Comparison of instances selection algorithms i. algorithms survey. In Artificial Intelligence and Soft Computing, pages 598-603. Springer, 2004a.
[21]
N. Jankowski and M. Grochowski. Comparison of instances selection algorithms ii. results and comments. In Artificial Intelligence and Soft Computing, pages 580-585. Springer, 2004b.
[22]
J.W. Jaromczyk and G.T. Toussaint. Relative neighborhood graphs and their relatives. P-IEEE, 80: 1502-1517, 1992.
[23]
C.D.J. Marchette, C.E. Priebe, D.A. Socolinsky, and J.G. DeVinney. Classification using class cover catch digraphs. Journal of classification, 20(1):3-23, 2003.
[24]
K. Mukherjee. Application of the gabriel graph to instance-based learning. In M.sc. project, School of Computing Science, Simon Fraser University, 2004.
[25]
E. Pekalska, R.P. W. Duin, and P. Paclík. Prototype selection for dissimilarity-based classifiers. Pattern Recognition, 39(2):189-208, 2006.
[26]
G. Rätsch, T. Onoda, and K.-R. Müller. Soft margins for AdaBoost. Machine Learning, 42(3): 287-320, 2001.
[27]
G.L. Ritter, H.B. Woodruff, S.R. Lowry, and T.L. Isenhour. An algorithm for a selective nearest neighbor decision rule. IEEE Transactions on Information Theory, 21(6):665-669, 1975.
[28]
J.S. Sánchez, F. Pla, and F.J. Ferri. Prototype selection for the nearest neighbour rule through proximity graphs. Pattern Recognition Letters, 18:507-513, 1997.
[29]
J. Sankaranarayanan, H. Samet, and A. Varshney. A fast all nearest neighbor algorithm for applications involving large point-clouds. Comput. Graph., 31(2):157-174, 2007.
[30]
H. Shin and S. Cho. Neighborhood property based pattern selection for support vector machines. Neural Computation, (19):816-855, 2007.
[31]
I. Tomek. An experiment with the edited nearest-neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, 6(6):448-452, 1976.
[32]
G.T. Toussaint. Proximity graphs for nearest neighbor decision rules: recent progress. In Interface- 2002, 34th Symposium on Computing and Statistics, pages 83-106, 2002.
[33]
G.T. Toussaint, B.K. Bhattacharya, and R.S. Poulsen. The application of voronoi diagrams to non-parametric decision rules. In Proceedings of the 16th Symposium on Computer Science and Statistics, pages 97-108, 1984.
[34]
A. Vezhnevets and O. Barinova. Avoiding boosting overfitting by removing "confusing" samples. In Proceedings of the 18th European Conference on Machine Learning (ECML), volume 4701, pages 430-441. LNCS, 2007.
[35]
D. L. Wilson. Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man and Cybernetics, (2):408-420, 1972.
[36]
D.R. Wilson and T.R. Martinez. Instance pruning techniques. In Proc. 14th International Conference on Machine Learning, pages 403-411. Morgan Kaufmann, 1997.
[37]
D.R. Wilson and T.R. Martinez. Reduction techniques for instance-based learning algorithms. Machine Learning, 38(3):257-286, 2000.
[38]
D.A. Zighed, S. Lallich, and F. Muhlenbach. Separability index in supervised learning. In PKDD '02: Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, pages 475-487. Springer-Verlag, 2002.

Cited By

View all
  • (2024)A heuristic hybrid instance reduction approach based on adaptive relative distance and k-means clusteringThe Journal of Supercomputing10.1007/s11227-023-05885-x80:9(13096-13123)Online publication date: 1-Jun-2024
  • (2023)A prototype selection technique based on relative density and density peaks clustering for k nearest neighbor classificationIntelligent Data Analysis10.3233/IDA-22673027:3(675-690)Online publication date: 1-Jan-2023
  • (2019)Ensembles of instance selection methodsInternational Journal of Applied Mathematics and Computer Science10.2478/amcs-2019-001229:1(151-168)Online publication date: 1-Mar-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research
The Journal of Machine Learning Research  Volume 9, Issue
6/1/2008
1964 pages
ISSN:1532-4435
EISSN:1533-7928
Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 June 2008
Published in JMLR Volume 9

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)39
  • Downloads (Last 6 weeks)12
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A heuristic hybrid instance reduction approach based on adaptive relative distance and k-means clusteringThe Journal of Supercomputing10.1007/s11227-023-05885-x80:9(13096-13123)Online publication date: 1-Jun-2024
  • (2023)A prototype selection technique based on relative density and density peaks clustering for k nearest neighbor classificationIntelligent Data Analysis10.3233/IDA-22673027:3(675-690)Online publication date: 1-Jan-2023
  • (2019)Ensembles of instance selection methodsInternational Journal of Applied Mathematics and Computer Science10.2478/amcs-2019-001229:1(151-168)Online publication date: 1-Mar-2019
  • (2019)Minimizing the Misclassification Rate of the Nearest Neighbor Rule Using a Two-stage MethodProceedings of the 2019 11th International Conference on Machine Learning and Computing10.1145/3318299.3318339(124-132)Online publication date: 22-Feb-2019
  • (2018)Comparison of Prototype Selection Algorithms Used in Construction of Neural Networks Learned by SVDInternational Journal of Applied Mathematics and Computer Science10.2478/amcs-2018-005528:4(719-733)Online publication date: 1-Dec-2018
  • (2017)An Evolutionary Multiobjective Model and Instance Selection for Support Vector Machines With Pareto-Based EnsemblesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.268886321:6(863-877)Online publication date: 1-Dec-2017
  • (2017)An efficient instance selection algorithm for k nearest neighbor regressionNeurocomputing10.1016/j.neucom.2017.04.018251:C(26-34)Online publication date: 16-Aug-2017
  • (2016)Natural Neighbor Reduction Algorithm for Instance-based LearningInternational Journal of Cognitive Informatics and Natural Intelligence10.4018/IJCINI.201610010310:4(59-73)Online publication date: 1-Oct-2016
  • (2016)Prototype Selection for k-Nearest Neighbors Classification Using Geometric MedianProceedings of the Fifth International Conference on Network, Communication and Computing10.1145/3033288.3033301(140-144)Online publication date: 17-Dec-2016
  • (2016)Instance selection for regressionNeurocomputing10.1016/j.neucom.2016.04.003201:C(66-81)Online publication date: 12-Aug-2016
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media