Instance Selection based on Nearest-Enemy Relations and Preservation of the Local Structure of a Training Sample
DOI:
https://doi.org/10.71310/pcam.5_76.2026.04Keywords:
instance selection, nearest enemy, ???? nearest neighbours, local structure of a sample, feature stability, meta-object, random subsamplesAbstract
The paper considers instance selection for a training sample and the analysis of how selection affects the local structure of the data. The ENRS (Enemy-Neighbor Relation Selection) algorithm is proposed, in which the decision to remove an object is based on its relations with the nearest objects of the opposite class and with same-class objects whose spheres of influence contain it. The local structure of a sample is described by a feature formed from the composition of the ???? nearest neighbours of an object and by the stability indicator of this feature; the set of indicator values for different ???? represents the sample as a meta-object in a unified space. A method for assessing the preservation of local structure is proposed, based on comparing a reduced sample with random subsamples of the same size and class composition. Computational experiments were carried out on the German Credit data set and five other UCI data sets, and ENRS was compared with the CNN, ENN and Tomek Links selection methods. It is found that on the German Credit and Pima data sets the samples produced by ENRS differ from random subsamples by a lower class homogeneity of object neighbourhoods, that the extent of this difference depends on the algorithm parameter, and that the classification accuracy on ENRS samples does not exceed that on random subsamples of the same size. The proposed approach separates changes of local structure caused by the selection of objects from those caused by the reduction of sample size and can be applied to the analysis of any selection method.
References
Hart P. E. The condensed nearest neighbor rule // IEEE Transactions on Information Theory. — 1968. — Vol. 14, №3. — P. 515–516. — doi: https://doi.org/10.1109/TIT.1968.1054155.
Wilson D. L. Asymptotic properties of nearest neighbor rules using edited data // IEEE Transactions on Systems, Man, and Cybernetics. — 1972. — Vol. 2, №3. — P. 408–421. — doi: https://doi.org/10.1109/TSMC.1972.4309137.
Tomek I. Two modifications of CNN // IEEE Transactions on Systems, Man, and Cybernetics. — 1976. — Vol. 6, №11. — P. 769–772. — doi: https://doi.org/10.1109/TSMC.1976.4309452.
Aha D. W., Kibler D., Albert M. K. Instance-based learning algorithms // Machine Learning. — 1991. — Vol. 6. — P. 37–66. — doi: https://doi.org/10.1023/A:1022689900470.
Wilson D. R., Martinez T. R. Reduction techniques for instance-based learning algorithms // Machine Learning. — 2000. — Vol. 38. — P. 257–286. — doi: https://doi.org/10.1023/A:1007626913721.
Garc´ıa S., Derrac J., Cano J. R., Herrera F. Prototype selection for nearest neighbor classification: taxonomy and empirical study // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2012. — Vol. 34, №3. — P. 417–435. — doi: https://doi.org/10.1109/TPAMI.2011.142.
Brighton H., Mellish C. Advances in instance selection for instance-based learning algorithms // Data Mining and Knowledge Discovery. — 2002. — Vol. 6, №2. — P. 153–172. — doi: https://doi.org/10.1023/A:1014043630878.
Olvera-L´opez J. A., Carrasco-Ochoa J. A., Mart´ınez-Trinidad J. F., Kittler J. A review of instance selection methods // Artificial Intelligence Review. — 2010. — Vol. 34, №2. — P. 133–143. — doi: https://doi.org/10.1007/s10462-010-9165-y.
Leyva E., Gonz´alez A., P´erez R. Three new instance selection methods based on local sets: a comparative study with several approaches from a bi-objective perspective // Pattern Recognition. — 2015. — Vol. 48, №4. — P. 1523–1537. — doi: https://doi.org/10.1016/j.patcog.2014.10.001.
Arnaiz-Gonz´alez ´ A., D´ıez-Pastor J. F., Rodr´ıguez J. J., Garc´ıa-Osorio C. Local sets for multi-label instance selection // Applied Soft Computing. — 2018. — Vol. 68. — P. 651–666. — doi: https://doi.org/10.1016/j.asoc.2018.04.016.
Arnaiz-Gonz´alez ´ A., D´ıez-Pastor J. F., Rodr´ıguez J. J., Garc´ıa-Osorio C. Instance selection of linear complexity for big data // Knowledge-Based Systems. — 2016. — Vol. 107. — P. 83–95. — doi: https://doi.org/10.1016/j.knosys.2016.05.056.
Liu C., Wang W., Wang M. [et al.] An efficient instance selection algorithm to reconstruct training set for support vector machine // Knowledge-Based Systems. — 2017. — Vol. 116. — P. 58–73. — doi: https://doi.org/10.1016/j.knosys.2016.10.031.
Jim´enez F., S´anchez G., Palma J., Sciavicco G. Three-objective constrained evolutionary instance selection for classification: wrapper and filter approaches // Engineering Applications of Artificial Intelligence. — 2022. — Vol. 107. — Art. 104531. — doi: https://doi.org/10.1016/j.engappai.2021.104531.
Ignat'yev N. A., Tursunmurotov D. KH. Tsenzurirovaniye obuchayushchikh vyborok s ispol'zovaniyem regulyarizatsii otnosheniy svyazannosti ob"yektov klassov // Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki. — 2024. — T. 24, № 2. — S. 322–329. — doi: https://doi.org/10.17586/2226-1494-2024-24-2-322-329.
Ignat'yev N. A., Akbarov B. KH. Otsenka blizosti struktur otnosheniy ob"yektov obuchayushchey vyborki na mnogoobraziyakh naborov latentnykh priznakov // Vestnik Tomskogo gosudarstvennogo universiteta. Upravleniye, vychislitel'naya tekhnika i informatika. — 2023. — № 65. — S. 69–78. — doi: https://doi.org/10.17223/19988605/65/7.
Ignat'yev N. A. Vybor tselevykh priznakov dlya klassifikatsii i klasternogo analiza struktur otnosheniy ob"yektov // International Journal of Open Information Technologies. — 2026. — Vol. 14, №3.
Jolliffe I. T., Cadima J. Principal component analysis: a review and recent developments // Philosophical Transactions of the Royal Society A. — 2016. — Vol. 374, №2065. — Art. 20150202. — doi: https://doi.org/10.1098/rsta.2015.0202.
Hofmann H. Statlog (German Credit Data) // UCI Machine Learning Repository. — 1994. — doi: https://doi.org/10.24432/C5NC77. — URL: https://archive.ics.uci.edu/dataset/144/statlog+german+credit+data (дата обращения: 08.05.2026).
Smith J. W., Everhart J. E., Dickson W. C. [et al.] Using the ADAP learning algorithm to forecast the onset of diabetes mellitus // Proceedings of the Annual Symposium on Computer Application in Medical Care. — 1988. — P. 261–265.
Sigillito V. G., Wing S. P., Hutton L. V., Baker K. B. Classification of radar returns from the ionosphere using neural networks // Johns Hopkins APL Technical Digest. — 1989. — Vol. 10. — P. 262–266.
Gorman R. P., Sejnowski T. J. Analysis of hidden units in a layered network trained to classify sonar targets // Neural Networks. — 1988. — Vol. 1, №1. — P. 75–89. — doi: https://doi.org/10.1016/0893-6080(88)90023-8.
Street W. N., Wolberg W. H., Mangasarian O. L. Nuclear feature extraction for breast tumor diagnosis // Proceedings of SPIE. Biomedical Image Processing and Biomedical Visualization. — 1993. — Vol. 1905. — P. 861–870. — doi: https://doi.org/10.1117/12.148698.
Lohweg V. Banknote Authentication // UCI Machine Learning Repository. — 2012. — doi: https://doi.org/10.24432/C55P57.
Wilson D. R., Martinez T. R. Improved heterogeneous distance functions // Journal of Artificial Intelligence Research. — 1997. — Vol. 6. — P. 1–34. — doi: https://doi.org/10.1613/jair.346.
Pedregosa F., Varoquaux G., Gramfort A. [et al.] Scikit-learn: machine learning in Python // Journal of Machine Learning Research. — 2011. — Vol. 12. — P. 2825–2830.
Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI). — 1995. — Vol. 2. — P. 1137–1143.
Cover T. M., Hart P. E. Nearest neighbor pattern classification // IEEE Transactions on Information Theory. — 1967. — Vol. 13, №1. — P. 21–27. — doi: https://doi.org/10.1109/TIT.1967.1053964.
Demˇsar J. Statistical comparisons of classifiers over multiple data sets // Journal of Machine Learning Research. — 2006. — Vol. 7. — P. 1–30.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Ш.Ш. Рамазонов
This work is licensed under a Creative Commons Attribution 4.0 International License.
