APPLICATION OF MACHINE LEARNING METHODS FOR FINDING THE MAXIMUM ELEMENT

Abstract

Sorting is the core operation of many computational tasks, including design, digital signal processing, networking, database management, and data processing, for which it is estimated that sorting accounts for more than 25% of total runtime. Although there are well-known fast classical sorting algorithms, there are still interesting sorting algorithms that simulate the work of the human brain, in particular on the basis of neural networks and in general, on the basis of machine learning methods. Systems based on neural networks are probabilistic, ie algorithms based on them will always have a certain percentage of errors and, therefore, they are not used in classical programming.

In this paper, classical algorithms are used to construct machine learning models with a teacher that find the maximum element of the array, namely: linear regression, naive Bayesian classifier, reference vectors method, decision tree. The task of finding the maximum element was reduced to the problem of classification in this way - to obtain a marked data set generated random arrays, each of which was labeled a class equal to the position number of the maximum element of the array. Thus, all arrays of dimension n are divided into n classes - the class with number i includes all arrays in which the maximum element is in the i-th place. Data sets of different dimensions were formed - 2, 3, 4, 10, 20 and different quantities - 100,500,1000,2000, 5000,10000, 100000 arrays. Models were trained on each of the 7 datasets and the accuracy of training was found. Based on computational experiments, it was found that the maximum quality of all models - more than 99.9% - was achieved on an array of two elements and deteriorated with increasing dimension of the array, up to 96%. This quality is not inferior to the quality achieved by neural networks. Also, it was found that the best quality of learning among all classical machine learning methods tested is achieved for linear regression and decision tree.

The paper proposes the implementation of classical machine learning technologies and analysis of the component of the sorting algorithm, namely, finding the maximum element of the array. The following methods were implemented: linear regression, decision trees, support-vector machines, the method of k-nearest neighbors. A comparative analysis of the accuracy of each algorithm.