In supervised classification, a training set is given to a classifier to learn a decision rule for classifying unseen cases. When large training sets are processed, the training stage becomes slow especially for instance-based learning. However, not all information in a training set is useful for classification because it could contain either redundant or noisy prototypes. Therefore a process for discarding useless prototypes is required; this process is known as prototype selection. In this work, we present some methods for selecting prototypes based on prototype relevance, which are accurate and fast for large datasets; in addition, our methods can be applied over datasets described by nominal features. We report experimental results showing the effectiveness of our methods as well as a comparison against other successful prototype selection methods.
KunchevaL.I. and BezdekJ.C., Nearest prototype classification: Clustering. Genetic algorithms. Or random search?IEEE Transactions on Systems. Man and Cybernetics28-1(Part C) (1998), 160–164.
2.
Olvera-LópezJ.A., Carrasco-OchoaJ.A., Martínez-TrinidadJ.F.Prototype Selection Via Prototype RelevanceRuiz-ShulcloerJ. and KropatschW.G.CIARP LNCS153–160.
3.
CoverT. and HartP., Nearest neighbor pattern classification, IEEE Transactions on Information Theory13 (1967), 21–27.
VapnikV., The Nature of Statistical Learning Theory, Springer-VerlagNew York1995.
6.
QuinlanJ.R., C4.5: Programs for Machine LearningMorgan Kaufmann1993.
7.
HartP.E., The condensed nearest neighbor rule, IEEE Transactions on Information Theory14 (1968), 515–516.
8.
Chien-HsingC., Bo-HanK. and FuC., The Generalized Condensed Nearest Neighbor Rule as A Data Reduction Method, in: 18th International Conference on Pattern Recognition (2006),2, 556–559.
9.
WilsonD.L., Asymptotic properties of nearest neighbor rules using edited data, IEEE Transactions on Systems, Man and Cybernetics2 (1972), 408–421.
10.
DevijverP.A. and KittlerJ., On the edited nearest neighbor rule, In Proceedings of the 5th International Conference on Pattern Recognition (1980), 72–80.
11.
WilsonD.R. and MartínezT.R., Reduction techniques for instance-based learning algorithms, Machine Learning38 (2000), 257–286.
12.
BrightonH. and MellishC., Advances in instance selection for instance-based learning algorithms, Data Mining and Knowledge Discovery6(2) (2002), 153–172.
13.
YuanguiL., ZhonhuiH., YunzeC., WeidongZ., Support Vector Based Prototype Selection Method for Nearest Neighbor Rules, WangL., ICNIC 2005, LNCS 3610 (2005), 528–535.
14.
GarainU., Prototype reduction using an artificial immune model, Pattern Analysis and Applications11 (2008), 353–363.
15.
GarcíaS., CanoJ.R. and HereraF., A memetic algorithm for evolutionary prototype selection: A scaling up approach, Pattern Recognition41(8) (2008), 2693–2709.
16.
García-PedrajasN. and Romero del CastilloJ.A., and Ortíz-BoyerD., A cooperative coevolutionary algorithm for instance selection for instance-based learning, Machine Learning78(3) (2010), 381–420.
17.
VallejoC.G., TroyanoJ.A. and OrtegaJ., InstanceRank: Bringing order datasets, Pattern Recognition Letters31 (2010), 133–142.
18.
BezdekJ.C. and KunchevaL.I., Nearest prototype classifier designs: An experimental study, International Journal of Intelligent Systems16(12) (2001), 1445–1473.
19.
LiuH. and MotodaH., On issues of instance selection, Data Mining and Knowledge Discovery6 (2002), 115–130.
20.
SpillmannB., NeuhausM., BunkeH., PękalskaE., DuinR.P.W., Transforming Strings to Vector Spaces Using Prototype Selection, YeungD.-Y., SSPR&SPR 2006 LNCS 4109 (2006), 287–296.
21.
CaisesY., GonzálezA., LeyvaE., PérezR.SCIS: Combining Instance Selection Methods to Increase Their Effectiveness over a Wide Range of Domains, CorchadoE. and YinH., IDEAL 2009 LNCS 5788 (2009), 17–24.
22.
LuminiA. and NanniL., A clustering method for automatic biometric template selection, Pattern Recognition39(3) (2006), 495–497.
23.
Olvera-LópezJ.A., Carrasco-OchoaJ.A. and Martínez-TrinidadJ.F., A new Fast prototype selection method based on clustering, Pattern Analysis and Applications13(2) (2010), 131–141.
24.
LeyvaE., GonzálezA. and PérezR., Three new instance selection methods based on local sets: A comparative study with several approaches from a bi-objective perspective, Pattern Recognition48(4) (2015), 1523–1537.
25.
HamidzadehJ., MonsefiR. and YazdiH.S., IRAHC: Instance reduction algorithm using hyperrectangle clustering, Pattern Recognition48(5) (2015), 1878–1889.
26.
OugiaroglouS. and EvangelidisG., Fast and accurate k-nearest neighbor classification using prototype selection by clustering, In: 16th IEEE Panhellenic Conference on Informatics (2012), pp 168–173.
27.
Hernandez-LealP., Carrasco-OchoaJ.A., Martínez-TrinidadJ.F. and Olvera-LopezJ.A., InstanceRank based on borders for instance selection, Pattern Recognition46(1) (2013), 365–375.
28.
De Haro-GarcíaA. and García-PedrajasN., A divide-and-conquer approach for scaling up instance selection algorithm, Data Mining and Knowledge Discovery18(3) (2009), 392–418.
29.
De Haro-GarcíaA., García-PedrajasN. and del CastilloJ.A., Large scale instance selection by means of federal instance selection, Data & Knowledge Engineering75 (2012), 58–77.
30.
SwongerC.W., Sample set condensation for a condensed nearest neighbour decision rule for pattern recognition, WatanabeS., In Frontiers of Pattern Recognition (1972), 511–519.
31.
BacheK. and LichmanM., UCI Machine Learning Repository, Irvine CAUniversity of California, School of Information and Computer Science (2013) http://archive.ics.uci.edu/ml.
32.
WilsonD.R. and MartínezT.R., Improved heterogeneous distance functions, Journal of Artificial Intelligence Research6(1) (1997), 1–34.
33.
HallM., FrankE., HolmesG., PfahringerB., ReutemannP. and WittenI.H., The WEKA data mining software: An update, ACM SIGKDD Explorations News Letter11(1) (2009), 10–18.
34.
DemšarJ., Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research7 (2006), 1–30.
35.
ZhaiJ., LiT. and WnagX., A cross-selection instance algorithm, Journal of Intelligent & Fuzzy Systems30 (2016), 717–728.
36.
LiuC., WangW., LvF. and KonanM., An efficient instance selection algorithm to reconstruct training sets for support vector machine, Knowledge-Based Systems116 (2017), 58–73.
