The distance function optimization for the near neighbors-based classifiers

Jiřina, Marcel; Krayem, Said

dc.title	The distance function optimization for the near neighbors-based classifiers	en
dc.contributor.author	Jiřina, Marcel
dc.contributor.author	Krayem, Said
dc.relation.ispartof	ACM Transactions on Knowledge Discovery from Data
dc.identifier.issn	1556-4681 Scopus Sources, Sherpa/RoMEO, JCR
dc.identifier.issn	1556-472X Scopus Sources, Sherpa/RoMEO, JCR
dc.date.issued	2022
utb.relation.volume	16
utb.relation.issue	6
dc.type	article
dc.language.iso	en
dc.publisher	Association for Computing Machinery
dc.identifier.doi	10.1145/3434769
dc.relation.uri	https://dl.acm.org/doi/10.1145/3434769
dc.relation.uri	https://dl.acm.org/doi/pdf/10.1145/3434769
dc.subject	near neighbors	en
dc.subject	classification	en
dc.subject	distance function	en
dc.subject	metric	en
dc.description.abstract	Based on the analysis of conditions for a good distance function we found four rules that should be fulfilled. Then, we introduce two new distance functions, a metric and a pseudometric one. We have tested how they fit for distance-based classifiers, especially for the IINC classifier. We rank distance functions according to several criteria and tests. Rankings depend not only on criteria or nature of the statistical test, but also whether it takes into account different difficulties of tasks or whether it considers all tasks as equally difficult. We have found that the new distance functions introduced belong among the four or five best out of 23 distance functions. We have tested them on 24 different tasks, using the mean, the median, the Friedman aligned test, and the Quade test. Our results show that a suitable distance function can improve behavior of distance-based classification rules.	en
utb.faculty	Faculty of Applied Informatics
dc.identifier.uri	http://hdl.handle.net/10563/1011148
utb.identifier.obdid	43884064
utb.identifier.scopus	2-s2.0-85140904158
utb.identifier.wok	000859375300001
utb.source	J-wok
dc.date.accessioned	2022-10-18T12:15:01Z
dc.date.available	2022-10-18T12:15:01Z
dc.description.sponsorship	Czech Ministry of Education, Youth and Sports [LM2018113]
dc.description.sponsorship	Ministerstvo Školství, Mládeže a Tělovýchovy, MŠMT: LM2018113
utb.contributor.internalauthor	Krayem, Said
utb.fulltext.affiliation	MARCEL JIŘINA, Institute of Computer Science of the Czech Academy of Sciences, Czech Republic https://orcid.org/0000-0002-6686-1511 SAID KRAYEM, Faculty of Applied Informatics, Tomas Bata University, Czech Republic Authors’ addresses: M. Jiřina, Institute of Computer Science of the Czech Academy of Sciences, Pod Vodárenskou věží 2, Prague 18207, Czech Republic; email: marcel@cs.cas.cz; S. Krayem, Faculty of Applied Informatics, Tomas Bata University, Nad Stranemi, Zlin 4511, Czech Republic; email: drsaid@seznam.cz
utb.fulltext.dates	Online: 30 July 2022 Online AM: 24 February 2022 Accepted: 1 November 2020 Revised: 1 September 2020 Received: 1 April 2019
utb.fulltext.references	[1] M. Alkasassbeh, G. A. Altarawnwh, and A. B. Hassanat. 2015. On enhancing the performance of nearest neighbor classifiers using hassanat distance metric. Canadian Journal of Pure and Applied Science 9, 1 (2015), 6. [2] F. Angiulli and F. Fassetti. 2013. Nearest neighbor-based classification of uncertain data. ACM Transactions on Knowledge Discovery from Data 7, 1, Article 1 (2013), 35, DOI:10.1145/2435209.2435210 [3] M. Ashraf, K. Le, and X. Huang. 2011. Iterative weighted k-NN for constructing missing feature values in wisconsin breast cancer dataset. In Proceedings of the 3rd International Conference on Data Mining and Intelligent Information Technology Applications , Macao, 24–26 Oct. 2011, 23–27, ISBN: 978-1-4673-0231-9 (IEEE) [4] M. Benzi, J. K. Cullum, and M. Tuma. 2000. Robust approximate inverse preconditioning for the conjugate gradient ˙ method. SIAM Journal on Scientific Computing 22, 1318–1332. [5] T. M. Cover and P. E. Hart. 1967. Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13, 1 (1967), 21–27. [6] J. Derrac, S. Garcia, D. Molina, and F. Herrera. 2011. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 1, 1 (2011), 3–18. [7] E. Deza and M. M. Deza. 2006. Dictionary of Distances. Elsevier, Amsterdam, 391. [8] M. M. Deza and E. Deza. 2009. Encyklopedia of Distances. Springer, Heildelberg, 590. [9] C. Domeniconi, J. Peng, and D. Gunopulos. 2002. Locally adaptive metric nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 9 (2002), 1281–1285. [10] D. Dua and E. Karra Taniskidou. 2017. UCI machine learning repository. Irvine, CA: University of California, School of Information and Computer Science. Retrieved 13 March, 2008 from http://archive.ics.uci.edu/ml. [11] R. Duda, P. Hart, and D. G. Stork. 2000. Pattern Classification. John Wiley and Sons, 2000. [12] P. Grassberger and I. Procaccia. 1983. Measuring the strangeness of strange attractors. Physica 9D, 1–2 (1983), 189–208. [13] A. B. Hassanat. 2014. Dimensionality invariant similarity measure. Journal of American Science, 10, 8 (2014), 221–226. [14] A. B. Hassanat, M. A. Abbadi, G. A. Altarawneh, A. A. Alhasanat. 2014. Solving problem of K parameter in the KNN classifier using an ensemble learning approach. International Journal of Computer Science and Information Security 12, 8 (2014), 33–39. [15] M. Jiřina and M. Jiřina, Jr. 2013. Utilization of singularity exponent in nearest neighbor based classifier. Journal of Classification 30, 1 (2013), 3–29. ISSN 0176–4268. [16] M. Jiřina and M. Jiřina, Jr. 2014. Correlation dimension based classifier. IEEE Transactions on Cybernetics 44, 12 (2014), 2253–2263. ISSN 2168–2267. [17] M. Jiřina and M. Jiřina, Jr. 2015. Classification using zipfian kernel. Journal of Classification (Springer) 32, 2 (2015), 305–326. ISSN 0176–4268. [18] T. Joachims. 1999. Making large-scale SVM learning practical. In Proceedings of the Advances in Kernel Methods - Support Vector Learning, (Eds). B. Scholkopf, C. Burges and A. Smola, MIT-Press. [19] T. Joachims. 2008. Program codes for SVM-light and SVM-multiclass. Retrieved 30 Jan., 2014 from http://svmlight.joachims.org/. [20] A. Kontorovich and R. Weiss. 2015. A bayes consistent 1-NN classifier. InProceedings of the 18th International Conference on Artifficial Intelligence and Statistics 2015, San Diego, JMLR: W&CP 38, 480–488. [21] B. Li, Y. W. Chen, and Y. Q. Chen. 2008. The nearest neighbor algorithm of local probability centers. IEEE Transactions on Systems, Man, and Cybernetics/Part B: Cybernetics 38, 1 (2008), 141–154. [22] A. L uschow and C. Wartena. 2017. Classifying medical literature using k-nearest-neighbours algorithm. In Proceedings of the 17th European Networked Knowledge Organization Systems Workshop Co-located with the 21st International Conference on Theory and Practice of Digital Libraries 2017 , Mayr P., Tudhope D., Golub K., Wartena C., Luca E. W. D. (Eds.), CEUR-WS.org, CEUR Workshop Proceedings, Vol. 1937, pp. 26–38. Retrieved from http://ceur-ws.org/Vol1937/paper3.pdf. [23] B. B. Mandelbrot. 1982. The Fractal Geometry of Nature. W. H. Freeman and Co., ISBN 0-7167-1186-9. [24] A. Mishra. 2020. k-nearest neighbor (k-NN) for machine learning. Data Science Foundation, May 2020, 4 pp., Retrieved from https://datascience.foundation/datatalk/k-nearest-neighbor-k-nn-for-machine-learning. [25] M. Muja and D. G. Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 11 (2014), 2227–2240. [26] Y. -K. Noh, B. T. Zhang, and D. D. Lee. 2018. Generative local metric learning for nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, 1 (2018), 106–118. [27] R. Paredes. 2008. CPW: Class and prototype weights learning. Retrieved 11 Dec., 2007 from http://www.dsic.upv.es/~rparedes/research/CPW/index.html. [28] R. Paredes. 2010. Data sets corpora. Retrieved 11 Dec., 2007 from Available http://algoval.essex.ac.uk/data/vector/UCI/, in fact, the primary source is S. M. Lucas, Algoval: Algorithm Evaluation over the Web. [29] R. Paredes and E. Vidal. 2006. Learning weighted metrics to minimize nearest neighbor classification error. IEEE Transactions on Pattern Analysis and Machine Intelligence 20, 7 (2006), 1100–1110. [30] S. M. Piryonesi and T. E. El-Diraby. 2020. Role of data analytics in infrastructure asset management: Overcoming data size and quality problems. Journal of Transportation Engineering, Part B: Pavements. 146, 2 (2020), 1–15. DOI:10.1061/JPEODX.0000175 [31] S. Garcia, M. Wozniak, and B. Krawczyk. 2017. Nearest neighbor classification for high-speed big data streams using spark. IEEE Transactions on Systems, Man and Cybernetics Systems 47, 10 (2017), 2727–2739. [32] B. J. Samworth. 2012. Optimal weighted nearest neighbour classifiers. The Annals of Statistics 40, 5 (2012), 2733–2763. DOI:10.1214/12-AOS1049 [33] B. W. Silverman. 1986. Density Estimation for Statistics and Data Analysis. Chapman and Hall, London. [34] K. Q. Weinberger and L. K. Saul. 2009. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research 10, 2 (2009), 207–244. [35] F. Xiong, M. Kam, L. Hrebien, B. Wang, and Y. Qi. 2016. Kernelized information-theoretic metric learning for cancer diagnosis using high-dimensional moleculr profiling data. ACM Transactions on Knowledge Discovery from Data 10, 4, Article 38 (2016), 23. DOI:10.1145/2789212 [36] D. Yu, X. Yu, and A. Wu. 2011. Making the nearest neighbor meaningful for time series classification. In Proceedings of the 4th International Congress on Image and Signal Processing. 2481–2485. [37] B. Zhang and S. N. Srihari. 2004. Fast k-nearest neighbor classification using cluster-based trees. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 4 (2004), 525–528. [38] Y. Liang. 2018. Integrating forest inventory data and MODIS data to map species-level biomass in chinese boreal forests. Canadian Journal of Forest Research 48, 5 (2018), 461–479. DOI:https://doi.org/10.1139/cjfr-2017-0346
utb.fulltext.sponsorship	This work was supported by the Czech Ministry of Education, Youth and Sports in project No. LM2018113 Cooperation on experiments at the Fermi National Laboratory, USA.
utb.wos.affiliation	[Jirina, Marcel] Czech Acad Sci, Inst Comp Sci, Vodarenskou Vezi 2, Prague 18207, Czech Republic; [Krayem, Said] Tomas Bata Univ, Fac Appl Informat, Zlin 4511, Czech Republic
utb.scopus.affiliation	Institute of Computer Science of the Czech Academy of Sciences, Pod Vodárenskou věží 2, Prague, 18207, Czech Republic; Faculty of Applied Informatics, Tomas Bata University, Nad Stranemi, Zlin, 4511, Czech Republic
utb.fulltext.projects	MSMT LM2018113
utb.fulltext.faculty	Faculty of Applied Informatics
utb.fulltext.ou	-