Algebraic Recognition Approach in IoT Ecosystem

Abstract

The solution to the problem of identifying objects in the IoT ecosystem of the Aral region is analyzed. The problem of constructing a correct algorithm with linear closure operators of a model for calculating estimates for identifying objects in the IoT ecosystem of the Aral region is considered. An algorithm operator is developed, which is considered correct for the problem Z, is the sum of q operators of the assessment calculation model, and is described by a set of numerical parameters $3·n·m·q$, where n is the number of specified features, m is the number of reference objects, and q is the set of recognized objects. Within the framework of the algebraic approach, several variants of linear combinations of recognition operators are constructed, the use of which gives the correct answer on the control material, and this is proven in the form of theorems. The constructed correct recognition algorithms, which are the easiest to use, where there is no optimization procedure, make it possible to quickly solve the issue of identifying incoming information flows in the IoT ecosystem of the Aral region.

1. Introduction

In recent years, solutions to applied problems of classification recognition and prediction have achieved great developments. In many real cases, the solution scheme remains the same; the set of possible solutions is divided into subsets in such a way that solutions that are close in some metric fall into one subset [1,2]. In the future, solutions that fall into the same subset do not differ, and all objects corresponding to these solutions are included in one class [3]. The information gained from past experience is presented in the following form: various objects are described in some way and their descriptions are divided into a finite number of non-overlapping classes [4]. When a new object appears, a decision is made to assign it to one class or another [5]. It is proposed to choose a generalized algorithm such that it achieves extreme forecasting quality [6]. Let us consider algorithmic models for solving classification problems. Among these models, we can identify the most frequently encountered ones when solving applied problems.

The work [7] discusses practical precedent-based recognition algorithms based on logical or algebraic correction of various heuristic recognition algorithms. The recognition problem is solved in two stages. First, algorithms of a certain group are applied independently to recognize an arbitrary object, then an appropriate corrector is applied to calculate the final collective solution. The general concepts of the algebraic approach, descriptions of practical algorithms for logical and algebraic correction, and the results of their practical comparison are given.

In [8], the problem of classification (recognition) based on precedents was studied. The issues of increasing the recognition ability and learning speed of logical correctors—recognition procedures based on constructing correct sets of elementary classifiers—have been studied. The concept of a correct set of elementary classifiers of a general form is introduced, and on this basis, a qualitatively new model of a logical corrector is constructed and studied. This model uses a wider class of correcting functions than previously constructed models of logical correctors.

In ref. [9], the supervised classification problem with a large number of classes was studied and the ECOS circuit (error output codes) was optimized. First, an initial binary matrix was randomly formed, the number of rows was equal to the number of classes, and each of the columns corresponded to the union of several classes into two macroclasses. In the ECOS approach, the binary classification problem was solved for the recognized object and each association. The object belonged to the class whose code string was closest. A generalization of the ESOS approach was given, offering a solution to the discrete optimization problem when searching for optimal associations, the use of the probabilities of correct classification in dichotomous problems, and the degree of information content of dichotomies. If the algorithms for solving dichotomous problems are correct, then the algorithm for recognizing the original problem is also correct.

In ref. [10], the complexity of the logical analysis of integer data was studied. For special problems of searching for frequent and infrequent elements in data, on the solution of which the training of logical classification procedures is based, the asymptotics of the typical number of solutions were given. The technical basis for obtaining these estimates was the methods for obtaining similar estimates for the intractable discrete problem of constructing (enumerating) dead-end coverings of an integer matrix, formulated in the work as the problem of finding “minimal” infrequent elements. The new results mainly concern the study of metric (quantitative) properties of frequently occurring elements.

The purpose of the research in this article is to develop effective object recognition methods to solve the identification problem in the IoT ecosystem of the Aral region. The objective of the research is to develop correct recognition algorithms based on an algebraic approach in solving the problem of identifying [11,12,13,14,15] the flow of information in the IoT ecosystem of the Aral region, which is described in detail in work [15] of the authors of this paper.

The IoT ecosystem of the Aral region covers a network of sensors for determining groundwater levels and salinity of water and soil and transmitting information via communication channels to the system server for identification and further processing. This article solves the applied problem of identification in the ecosystem of the Aral region, where formulas for recognizing correct algorithms are specifically given. Moreover, the correctness is proven in the theorems of this work in terms of the algebraic approach.

The public benefit of the results of this study is that the results are used in the ecosystem of the Aral region in monitoring the use of water resources and calculating salinity levels for agricultural use in an interactive mode.

The problems of recognizing disjoint classes are considered in refs. [8,16,17,18]. The methodology used to develop and test the algebraic recognition approach was proposed and described in the works of academician Yu.I. Zhuravlev and his students. In this work, based on the idea of the algebraic approach of academician Yu.I. Zhuravlev, a much simpler and significantly more efficient computational algorithm of the nearest neighbor and an average distance algorithm are proposed for solving these problems using algebraic methods. Methods have been developed that make it possible to more economically encode the recognition operator, which reduces the required memory and more efficiently uses the constructed correct algorithms for solving applied problems. The algebraic approach shows that each algorithm A can be represented as $A=B\times C$, two operators, recognition operator B, and the decision rule C. Within the framework of the algebraic approach, several variants of linear combinations of recognition operators A are constructed, the use of which gives the correct answer on the control material, and this is proven in the form of theorems.

Thus, taking into account the analysis of the works of scientists in the field of recognition researched on the topic of the article, this work investigates the problem of constructing a correct algorithm with linear closure operators for a model for calculating estimates. An algorithm operator was developed, which is considered correct for problem Z, represents the sum of q operators from the model for calculating estimates, and is described by a set of $3·n·m·q$ (where n is the number of predetermined features, m is the number of reference objects, q is the set of recognized objects) numerical parameters. An operator belonging to the linear closure of a model of the type of calculation of estimates was constructed [19,20,21,22]. The completeness of the linear closure of this model was proven for all problems in which for each class there is at least one stationary pair $\left(u,v\right)$, and this correct algorithm is written explicitly.

2. Models Based on the Calculation of Estimates

In the work [23], the so-called parametric recognition algorithms were considered, such collections of algorithms in which each algorithm is encoded in a one-to-one way by a set of numerical parameters. In these models, the proximity between parts of previously classified objects and the object to be classified was analyzed [24]. Based on a set of estimates, a general estimate for the object was developed and, according to the introduced decision rule, the belonging of the recognized object to one or another class was determined [25,26].

In the article, as the initial model (A), a model was considered that is related to the model for calculating estimates, supplemented by some simple type recognition algorithms: the nearest neighbor algorithm, the average distance algorithm, etc.

A feature of the algorithms of this class is that for calculating estimates that determine the belonging of a recognized object, there are simple analytical formulas that replace complex enumeration procedures that arise when calculating proximity estimates using a system of support sets [27].

In these models, the division of the algorithm into recognition operators and decision rules was carried out in a natural way [28,29,30,31,32].

We will consider only algorithms represented in the form $A=B·C$, where B is an arbitrary recognition operator. It turns out that an essential part of the algorithm is the operator—B; decision rule—C can be made standard for all algorithms and programs. Any recognizing vote operator maps task Z to a numeric matrix of votes or scores $B\left(Z\right)={∥G_{ij}∥}_{q·l},$$G_{ij}=G_j\left(S^i\right)$; moreover, the value $G_{ij}$ has a clear, meaningful interpretation. This value can be considered as the degree of belonging of the examined object $S^i$ to the class expressed by a number $K_j$. After introducing appropriate normalizations, the value $G_{ij}$ can also be considered as the value of the membership function of elements $S^i$ of the set $K_j$.

Before introducing the submodel used in what follows, let us write how the algebra of recognizing operators is constructed [33,34]. Let $Z=\left(J,{\tilde{S}}^2\right)$ be a fixed recognition problem with classes $K_1,\dots ,K_l$, also let $B_1$ and $B_2$ recognize operators, c is a real number

$$B_i\left(Z\right)={∥G_{uv}^i∥}_{q·l},i=1,2.$$

(1)

Then, the sum and product of the operators $B_1$ and $B_2$ as well as the multiplication of the operator by a real number is defined as follows

$$\left(B_1+B_2\right)\left(Z\right)={∥G_{uv}^1+G_{uv}^2∥}_{q\times l}$$

(2)

$$\left(B_1\times B_2\right)\left(Z\right)={∥G_{uv}^1\times G_{uv}^2∥}_{q\times l}$$

(3)

$$\left(cB\right)\left(Z\right)={∥c·G∥}_{q\times l},i=1,2.$$

(4)

Obviously, all these operations are commutative and associative; moreover, the operation of addition is distributive with respect to the operation of multiplication by a number. Due to these properties, if $\left(B\right)$ is the original set of operators, $a\left(B\right)$ is the closure of the family $\left(B\right)$ with respect to the introduced operations (algebraic closure) from $a\left(B\right)$ can be represented as operator polynomials $\sum b_{i1},\dots ,b_{ik},B_{i1}·B_{i2}·\dots ·B_{ik}.$

Here, $b_{ik}$—constants and original operators $B_{ik}$—play the role of variables for ordinary polynomials.

Note that if we have one algorithm for applying the original operators $B_{ik}$ to any problem Z, then it is easy to construct an algorithm for applying the operator polynomial to Z.

For any operator polynomial, the algorithm to be applied to the problem is constructed in a similar way: the original operators are applied to the problem, and then the resulting matrices are multiplied by the corresponding scalars and finally added, as in the example just considered. The evaluation matrix obtained by applying the algorithm $a\left(B\right)$ from the closure algebra does not allow such a simple interpretation as the matrix of the number of votes in voting algorithms [16,17,18]. The new recognizing operators are a formal extension of the original space of meaningful operators. Such formal extensions are often used in mathematics; thus, the field of complex numbers is a formal extension of the field of real numbers, for example, the process of formal Galois extensions is known. In the Galois extension, an algebraic equation of any degree is solved elementarily. However, for a long time, no physical interpretation of the Galois expansion was found [35]. Only in recent years has it been established that the elements of the Galois extension are naturally interpreted in connection with problems of error correction in information transmission.

There is currently no meaningful interpretation for the algebraic extension of the space of operators. However, with the help of these extensions, difficult extremal problems are relatively easily solved, including the problem of synthesizing an error-free algorithm for a given recognition problem [36].

The degree of an operator polynomial is introduced similarly to the degree of an ordinary polynomial in many variables from the terms:

$$b_{i1},\dots ,b_{in}{B}_{i1}·B_{i2}·\dots ·B_{ik}$$

(5)

the term with the largest K equal, for example, is chosen, and the degree of the polynomial is assumed to be equal to K. Based on the definition of the degree of polynomials, it is easy to distinguish in the extension $a\left(B\right)$ a system of nested extensions

$$a^0\left\{B\right\}=\left\{B\right\},a^1\left\{B\right\}=\left\{\sum b_i\left\{B_i\right\}\right\},\dots ,a^k\left\{B\right\}=\left\{\begin{array}{cc}& \mathrm{the}\mathrm{totality}\mathrm{of}\mathrm{all}\\ & \mathrm{polynomials}\mathrm{of}\mathrm{degree}\\ & \mathrm{not}\mathrm{higher}\mathrm{than}\mathrm{K}\end{array}\right\}$$

obviously, $a^0\left\{B\right\}\le a^1\left\{B\right\}\le \dots \le a^k\left\{B\right\}\dots a\left\{B\right\}$ the set $a^k\left\{B\right\}$ is called the k-th power extension of the original space of operators $\left\{B\right\}$. The set is of particular importance $a^1\left\{B\right\}$, it consists of all possible linear forms from the original operators $\left\{B\right\}$. The elements are represented as:

$$\sum b_i{B}_i,B_i\in \left\{B\right\}$$

(6)

When forming the elements included in the $a^1\left\{B\right\}$ operation, the product of operators is not used [37,38]. Therefore, this extension is an extension of the original space using the “+” operation, “multiplication by a number”; therefore, the set is $a^1\left\{B\right\}$, also commonly denoted as $L\left\{B\right\}$ and is called a linear extension of the set $\left\{B\right\}$. And so, let a set of $\left\{A\right\}$ algorithms be given $\left\{A\right\}$, and each A is represented as $A=B\times C$ and $\left\{B\right\}$ the initial model of operators. We take a fixed decision threshold rule $C\left(d_1,d_2\right)$. We introduce a family of algorithms $L\left\{B\right\}·C\left(d_1,d_2\right),\dots ,a^k\left\{B\right\}·C\left(d_1,d_2\right),\dots ,a\left\{B\right\}·C\left(d_1,d_2\right)$ called, respectively, a linear extension $L\left\{A\right\}$, an algebraic extension of the k-th degree $a^k\left\{A\right\}$, and an algebraic extension $a\left\{A\right\}$ of a family of algorithms $\left\{A\right\}$.

We see that the constructed sets of algorithms consist, in the execution of the corresponding operators, and a fixed threshold decision rule c is applied to the result of the operator’s action $c\left(d_1,d_2\right)$.

Let some set of recognition problems be given $\left\{Z\right\}$ and the initial set of recognizing operators be chosen in some way $\left\{B\right\}$. Let also within the framework $\left\{B\right\}$, not for every problem $\left\{B\right\}$, there exist an operator $B_Z$ and an algorithm $B_Z\times C_Z$, which gives an error-free solution to the problem Z. Then, the scheme for constructing a correct recognition algorithm consists of the following steps:

Stage 1. Some extension is chosen $a^k\left\{A\right\}$ in which the existence of an error-free solution is guaranteed for each problem Z from $\left\{Z\right\}$. In this case, it is natural to find, if possible, the smallest degree of expansion of K [39]. The implementation of the first stage in the literature is usually called the study of the completeness of the expansion. The theorems proved in this case are usually analogous to the existence theorem.

Stage 2. In the chosen extension, $a^k\left\{A\right\}$ for an admissible problem Z, either an error-free (correct algorithm) is constructed, or, if the former is associated with large computational difficulties, an algorithm for solving with respect to, which is sufficiently acceptable in accuracy Z. The exact calculation of the minimum degree of K is a laborious task, which at present can be solved only for relatively narrow classes of problems $\left\{Z\right\}$, and the original family of algorithms $\left\{A\right\}$. Therefore, in the studies carried out for the minimum degree of expansion, an upper estimate is constructed that guarantees the completeness of the expansion. So, for the voting model, such an estimate is

$$K=\left[\frac{lnq+lnl+ln(d_1+d_2)+ln{d}_2-ln{d}_1}{ln\left(1-\frac{1}{q}\right)}\right]$$

(7)

built in [16].

Here, q is the number of recognizable objects, l is the number of classes, $d_1,d_2$ and are the parameters of the threshold decision rule.

For most real problems, this estimate is overestimated, and therefore, the algorithm built in the second stage has computational redundancy. Of particular importance is the fact that the above estimate is constructed for problems with intersecting classes, while the majority of real problems are problems with non-intersecting classes. Later, we will see that for a wide class of problems it is sufficient to consider the degree of 1, that is, to use only a linear closure.

Algorithms of the class for calculating estimates allow solving recognition problems of all types: assigning an object to one of the given classes, automatic classification, choosing a feature system to describe recognition objects, and evaluating their effectiveness.

3. Algebraic Methods for Solving Recognition Problems with Non-Crossing Classes

In [12], algebraic methods for solving recognition problems with a finite number of intersecting classes were developed. For each recognition problem Z in terms of algebra over families of heuristic algorithms, a correct algorithm was constructed, e.g., an algorithm that correctly classifies a given finite sample of objects for each of the classes. Due to the fact that the problem with intersecting classes was considered, the algorithm constructed in the above works is rather cumbersome [40,41,42,43,44,45]. The description of the algorithm itself requires the use of large memory (the amount of memory grows proportionally) $q^2·l^2$, where q—the number of recognition objects in a given task, l—the number of classes. It turns out that if we consider only problems with non-intersecting classes, then similar algebraic methods can be used to obtain a much simpler description and a much more effective computational algorithm.

Basic concepts and designations. Let a set of admissible objects be given $\left\{S\right\}$ and it is known that $\left\{S\right\}$ can be represented as the sum of a finite number of disjoint subsets $K_j,j=\overline{1,l}$ called classes

$$\left\{S\right\}=K_1\bigcup \dots \bigcup K_l,K_u\bigcap K_v=⌀,u=\overline{1,l},v=1,2,\dots ,u-1,u+1,\dots ,l.$$

Objects S are descriptions of some real objects using successive values of a finite number of predefined features $1,2,3,\dots ,n$. Each attribute i can be associated with its set of values $M_i$, which we will assume to be a metric space with distance ${\rho }_i\left(xy\right)$. This paper considers the following sets $M_1,\dots ,M_n$ and metrics ${\rho }_1,\dots ,{\rho }_n$.

1. $M_i$—there is a finite or infinite interval, a half-interval, or a finite segment of the numerical axis. Then, ${\rho }_i\left(xy\right)=\left|x-y\right|$. In this case, the sign i is called numerical.

2. $M_i=\left\{0,1\right\}$ then ${\rho }_i\left(xy\right)=\left|x-y\right|$ the sign i is called binary.

3. $M_i=0,1,\dots ,k_i-1$—a finite set of integers; then defined by the following

Table 1. Set of integers.

	X	0	1	2	…	…	…	${\mathit{K}}_{\mathit{i}-1}$
Y
0		0	${\rho }_{01}$	${\rho }_{02}$	…	…	…	${\rho }_{0(k_i-1)}$
1		${\rho }_{10}$	0	${\rho }_{12}$	…	…	…	${\rho }_{1(k_i-1)}$
2		${\rho }_{20}$	${\rho }_{21}$	0	…	…	…	${\rho }_{2\left(k_i-1\right)}$
…		…	…	…	…	…	…	…
…		…	…	…	…	…	…	…
…		…	…	…	…	…	…	…
$k_i-1$		${\rho }_{k_i-1,0}$	${\rho }_{k_i-1,1}$	…	…	…	…	0

:

There are zeros on the diagonal in the table, in addition (the table is symmetrical with respect to the main diagonal).

Not every table of the specified type defines a metric. A necessary and sufficient condition for the latter is the fulfillment of inequalities for any $u,v,t$ such that $0\le u,v,t\le k-1$ occurs $\rho \left(u,v\right)=t$.

These inequalities ensure that the triangle axiom holds true. Signs are called graded or scalable.

4. $M_i=\left\{a_{i1},\dots ,a_{ik}\left(i\right)\right\}$ finite non-numeric set.

Then $\rho \left(x,y\right)=\left\{\begin{array}{cc}& 1,\mathrm{if}x\ne y\hfill \\ & 0,\mathrm{if}x=y\hfill \end{array}\right..$

The attribute in this case is called named.

In the future, we will consider only numerical, binary, graded, and named features.

A set $\left\{S\right\}$ is a collection of sets; $\left(a_1\left(S\right),\dots ,a_n\left(S\right)\right)$, such cases will be noted separately.

Consider the predicates $P_i\left(S\right)=S\in K_j,j=\overline{1,l}$. It is easy to notice that for each S, one of these predicates is equal to 1 and the rest are equal to 0.

The task of recognizing Z is to use some information $J_0$ about the sets $\left\{S\right\},K_1,\dots ,K_l$ compute the value of the predicates $P_j\left(S\right)$, for each finite number of objects $S^1,\dots ,S^q\in \left\{S\right\}$. In view of the previous remark, this is the same as specifying for each $S^i\in {\tilde{S}}^q=\left\{S^1,\dots ,S^q\right\}$ the number of the predicates t such that $P_t\left\{S^i\right\}=1$. The latter distinguishes the recognition problem with non-overlapping classes from the general recognition problem.

For a complete formalization of the description of task Z, it is necessary to determine the initial information $J_0$.

In this paper, we restrict ourselves to only one type: $J_0$—consists of an enumeration of reference objects, for each of which the number of the class containing this object is indicated.

For non-overlapping classes, information $J_0$ can also be in the form of a learning table $T_{nml}$, where n—determines the number of features, m—the number of objects, l—the number of classes:

$$J_o=T_{nml}=\left(\begin{array}{cc}\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ \dots & \dots & \dots & \dots \\ a_{m_{1}1}& a_{m_{1}2}& \dots & a_{m_{1}n}\end{array}& K_1\\ \begin{array}{cccc}\dots & \dots & \dots & \dots \end{array}& \dots \\ \begin{array}{cccc}{a}_{m_{j-1}1}& a_{m_{j-1}2}& \dots & a_{m_{j-1}n}\\ \dots & \dots & \dots & \dots \\ a_{m_{j}1}& a_{m_{j}2}& \dots & a_{m_{j}n}\end{array}& K_j\\ \begin{array}{cccc}\dots & \dots & \dots & \dots \end{array}& \dots \\ \begin{array}{cccc}{a}_{m_{l-1},1}& a_{m_{l-1},2}& \dots & a_{m_{l-1},n}\\ \dots & \dots & \dots & \dots \\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}& K_l\end{array}\right)$$

(8)

We will use such standard information presented in the form of a table. We will always count:

$$S_1,\dots ,S_{m_1}—\mathrm{belongs}\mathrm{to}{K}_i$$

(9)

$$S_{m_{j-1}},\dots ,S_{m_j}—\mathrm{belongs}\mathrm{to}{K}_j$$

(10)

$$S_{m_{l-1}+1},\dots ,S_m—\mathrm{belongs}\mathrm{to}{K}_l$$

(11)

We introduce important notation for what follows:

$$\left\{S_{m_{j-1}},\dots ,S_{m_j}\right\}={\tilde{K}}_j,\left\{S_1,\dots ,S_m\right\}/{\tilde{K}}_j=C{\tilde{K}}_j,j=1,2,\dots ,l,m_0=0.$$

The set ${\tilde{K}}_j$ consists of all reference objects belonging to the class $K_j$.

In recognition problems with intersecting classes, algorithms A were considered such that $A\left(Z\right)=A\left\{J_0,{\tilde{S}}^q\right\}=∥x_{ij}∥$ where $x_{ij}=P_i\left(S^i\right)$.

These algorithms calculate information vectors for each object

$$\tilde{\alpha }\left(S^i\right)=\left({\alpha }_{i1},{\alpha }_{i2},\dots ,{\alpha }_{il}\right)=\left(P_1\left(S^i\right),P_2\left(S^i\right),\dots ,P_l\left(S^i\right)\right)$$

and are called correct for problem Z.

For problems with intersecting classes, arbitrary binary vectors can be used as information vectors.

For problems with non-intersecting classes, only those containing exactly one-unit coordinate are informational, the rest of the coordinates are equal to zero. The last remark will be essential in what follows.

Let A be an arbitrary algorithm that translates the recognition problem Z, with l—classes, $Z=\left\{J_0,{\tilde{S}}^q\right\}$ into the matrix of answers ${∥{\beta }_{ij}∥}_{q\times l},A\left(J_0,{\tilde{S}}^q\right)={∥{\beta }_{ij}∥}_{q\times l},{\beta }_{ij}\in \left\{0,1,\Delta \right\}$.

Equality ${\beta }_{ij}=1,{\beta }_{ij}=0,{\beta }_{ij}=\Delta$ means, respectively, that the algorithm A calculated for the object $S^i:S^i\in K_j,S^i\notin K_j,$ turns out to be from the calculation of the object’s belonging $S^i$ to the class $K_j$. If ${\beta }_{ij}\in \left\{0,1\right\}$, then this also does not mean that, that ${\beta }_{ij}=P_j\left(S^i\right)$ is, the algorithm can also make errors in addition to failures.

Such algorithms are called incorrect for problem Z. Obviously, correct algorithms are a special case of incorrect ones.

For arbitrary incorrect algorithms (and hence for correct ones) hold.

Theorem 1.

Each algorithm A can be represented as $A=B\times C$ (multiplication means sequential execution), and if $A\left(Z\right)={∥{\beta }_{ij}∥}_{q\times l},{\beta }_{ij}\in \left\{0,1,\Delta \right\}$ that $B\left(Z\right)=∥a_{ij}∥$—numerical matrix, $C\left({∥a_{ij}∥}_{q·l}\right)={∥{\beta }_{ij}∥}_{q·l}$.

Theorem 1 [16] shows that each algorithm A can be divided into two successive stages. In the 1st stage, task Z is converted into a numerical matrix of standard sizes q—rows, l—columns, the number of rows is equal to the number of recognized objects, and the number of columns is equal to the number of classes.

In the 2nd stage, according to this numerical matrix, answers are finally formed to questions about the belonging of objects $S^i,\dots ,S^q$ to classes $K_1,\dots ,K_l$.

The value $a_{ij}$ is naturally interpreted as the values of the measures of belonging of objects $S^i$ to classes $K_j$. Stage B is called the recognition operator, stage C is the decision rule.

In what follows, only threshold decision rules are considered.

$$C^{*}\left({∥a_{ij}∥}_{q·l}\right)={∥C\left(a_{ij}\right)∥}_{q·l}$$

(12)

The rule is applied element by element. Let a be a number and $d_1,d_2$ also be numbers (thresholds) and $0<d_1<d_2$, then

$$C^{*}\left(a\right)=\left\{\begin{array}{cc}\hfill & 1,\mathrm{if}a>d_2\hfill \\ \hfill & 0,\mathrm{if}a<d_1\hfill \\ \hfill & \Delta ,\mathrm{if}{d}_1<a<d_2\hfill \end{array}\right.$$

(13)

4. Basic Model of Recognizers (B)

Simple Heuristic Operators

Let, according to the accepted notation, the initial information $J_0$ presented in the form of a table $T_{nml}$ (see Section 3).

Also let the set of features $1,2,\dots ,n$ be divided into subsets

$${\widehat{M}}_1=\left\{1,2,\dots ,n_1\right\},{\widehat{M}}_2=\left\{n_1+1,\dots ,n_2\right\},{\widehat{M}}_3=\left\{n_2+1,\dots ,n_3\right\},{\widehat{M}}_4=\left\{n_3+1,\dots ,n\right\}$$

numerical, binary, graded, and named features.

For each of the signs, a metric ${\widehat{M}}_1$ is introduced ${\rho }_i\left(x,y\right)=\left|x-y\right|$.

For each of the features included in ${\widehat{M}}_2,{\widehat{M}}_4$, a metric is introduced

$${\rho }_i\left(x,y\right)=\left\{\begin{array}{cc}\hfill & 1,x\ne y\hfill \\ \hfill & 0,x=y\hfill \end{array}\right.$$

(14)

For each of the graded features included in $M_3$, either a metric is specified ${\rho }_i\left(x,y\right)=\left|x-y\right|,$ or a metric is defined using a table specifying $\left(x,y\right)$ values for each pair ${\rho }_i\left(x,y\right)$ (See the definition of the metric in Section 3).

Let $S=\left(a_1,\dots ,a_n\right),S^{\prime }=\left(b_1,\dots ,b_n\right)$ admissible objects.

Let us put

$${\rho }_1(S,S^{\prime })=\underset{i=\overline{1,n}}{min}{\rho }_i(a_i,b_i)$$

(15)

$${\rho }_2\left(S,S^{\prime }\right)=\frac{1}{n}\sqrt{\sum _{i=1}^n{\rho }_i^2\left(a_i,b_i\right)}$$

(16)

$${\rho }_3^{\alpha \beta }\left(S,S^{\prime }\right)=\alpha ·{\rho }_1\left(S,S^{\prime }\right)+\beta ·{\rho }_2\left(S,S^{\prime }\right)\alpha +\beta =1,0\le \alpha \le 1$$

(17)

We introduced two fixed metrics ${\rho }_1,{\rho }_2$ and a family of metrics ${\rho }_3^{\alpha \beta }$ depending on the parameter in the space of admissible objects $\alpha$. Any of the introduced metrics can be used in the operator described below.

The nearest neighbor operator ${\beta }_{min}^1$ is as follows:

(a)

in the selected metric $\rho$ of the three entered, the following are calculated $\rho \left(S,S^{\prime }\right)=\rho \left(t\right),t=m_{j-1}+1,\dots ,m_j$ distance from the recognized object S to the objects included in the set ${\tilde{K}}_j$.

(b)

The value is calculated ${min}_t\rho \left(t\right)=p_j\left(S\right),j=1,2,\dots ,l,t=m_{j-1}+1,\dots ,m_j$.

(c)

The values are formed in the following way:

$$G_j\left(S\right)=\frac{1}{p_i\left(S\right)+1},j=1,2,\dots ,l,B_{min}^1\left(S\right)=\left(G_1\left(S\right),\dots ,G_j\left(S\right),\dots ,G_l\left(S\right)\right)$$

(18)

The greater the value, the closer in the selected metric is the recognizable object to the object $G_j\left(S\right)$ closest to it from, ${\tilde{K}}_j$, to the object included in the learning table and belonging to the class $K_j$. Obviously, if the operator $B_{min}^1$ is consistently presented with a set of recognizable objects $S^1,\dots ,S^q$, then they will translate it into a matrix ${∥G_j\left(S^i\right)∥}_{q·l}$.

Thus

$$B_{min}^1\left(T_{nml},{\tilde{S}}^q\right)=B_{min}^1\left(Z\right)=∥\begin{array}{ccccc}{G}_1\left(S^{\prime }\right)& \dots & G_j\left(S^{\prime }\right)& \dots & G_l\left(S^{\prime }\right)\\ \dots & \dots & \dots & \dots & \dots \\ G_1\left(S^i\right)& \dots & G_j\left(S^i\right)& \dots & G_l\left(S^i\right)\\ \dots & \dots & \dots & \dots & \dots \\ G_1\left(S^q\right)& \dots & G_j\left(S^q\right)& \dots & G_l\left(S^q\right)\end{array}∥$$

(19)

The system of operators described by us $B_{min}^1$ is somewhat different from the operators that are commonly called nearest neighbor operators. However, we have retained the operator’s schematic diagram.

5. Average Distance Operator ${\mathit{B}}_{\mathit{sr}}^{\mathbf{1}}$

Clause

(a)

of the definition of this operator, exactly repeats the corresponding clause of the definition of the operator $B_{min}^1$.

(b)

The value is calculated $\frac{1}{m_j-m_{j-1}}{\displaystyle \sum _{t=m_{j-1}+1}^{m_j}}\rho \left(t\right)={\rho }_j\left(S\right)$

(c)

as in the definition, $B_{min}^1$ it is calculated $G_j\left(S^i\right)=\frac{1}{{\rho }_j\left(S\right)+1}j=1,2,\dots ,l$

As for the operator $B_{min}^1$, it is easy to see that

$$B_{sr}^1\left(Z\right)=B_{sr}^1\left(T_{nml},{\tilde{S}}^q\right)=∥\begin{array}{ccccc}{G}_1\left(S^{\prime }\right)& \dots & G_j\left(S^{\prime }\right)& \dots & G_l\left(S^{\prime }\right)\\ \dots & \dots & \dots & \dots & \dots \\ G_1\left(S^i\right)& \dots & G_j\left(S^i\right)& \dots & G_l\left(S^i\right)\\ \dots & \dots & \dots & \dots & \dots \\ G_1\left(S^q\right)& \dots & G_j\left(S^q\right)& \dots & G_l\left(S^q\right)\end{array}∥$$

(20)

Voting Type Operators

Let the objects in the training information $K_j$ belong to the class $S_{u1},\dots ,S_{ut}$, those $K_j=\left\{S_{u1},\dots ,S_{ut}\right\}$.

In our notation $S_{ui}=\left\{a_{u{i}_1},\dots ,a_{u{i}_n}\right\}$.

As before, ${\rho }_1,\dots ,{\rho }_n$ we denote the metrics in the sets $M_1,\dots ,M_n$ of feature values $1,2,\dots ,n$. Let us enter the parameters: ${\epsilon }_{rv}\ge 0,r=u_1,\dots ,u_t,v=1,2,\dots ,n$.

These parameters will further define the proximity function for the recognized object and the set ${\tilde{K}}_j$. Parameters are also entered $p_{rv}>0,r=u_1,\dots ,u_t,v=1,2,\dots ,n$.

The parameter $p_{rv}$ is the weight of the v-th feature in the reference object $S_r$. There are no other parameters. The operator is defined as follows. In the set of pairs, $\left(r,v\right):r=u_1,\dots$, $u_t,v=1,\dots ,n$ a subset is distinguished $\Omega$, which is called the support set of operators in what follows.

If the recognized object is equal to $S=\left(a_1,\dots ,a_n\right)$, then the proximity function $B\left(\Omega ,S,{\tilde{K}}_j\right)$ is introduced as follows: if the $\left(r,v\right)\in \Omega$ inequalities ${\rho }_v\left(a_{rv},a_{tv}\right)\le {\epsilon }_{rv}$ that $B\left(\Omega ,S,{\tilde{K}}_j\right)=1$.

Otherwise $B\left(\Omega ,S,{\tilde{K}}_j\right)=0$.

In other words, the proximity function is equal to 0 if $\Omega$ there is a pair $\left(r,v\right)$ in such that ${\rho }_v\left(a_{rv},a_{tv}\right)>{\epsilon }_{rv}$. The number of votes $G_j\left(S\right)$ for S is calculated in the following way: $G_j\left(S\right)=\left({\displaystyle \sum _{\left(r,v\right)\in \Omega }}{p}_{rv}·B\left(\Omega ,S,{\tilde{K}}_j\right)\right)$.

Obviously, if the proximity function B for a set $\Omega$ is 0, then the number of votes in this set for a recognized object is 0. If $B=1$, then the number of votes is equal to $G_j\left(S\right)={\displaystyle \sum _{\left(r,v\right)\in \Omega }}{p}_{rv}$.

In this case, the number of votes is equal to the sum of the weights of pairs $\left(r,v\right)$—a sign-reference for all pairs included in $\Omega$.

If a problem with non-intersecting classes is considered, then the sets ${\tilde{K}}_j,j=1,2,\dots ,n$ in the learning information do not intersect, and therefore, the parameters ${\epsilon }_{rv},p_{rv}$ are determined independently for each class K.

Thus, we have completely defined the operator that translates the training information and the object S into a numeric string $\left(G_1\left(S\right),\dots ,G_l\left(S\right)\right)$.

Similarly, the set of recognizable objects $S^1,\dots ,S^q$ is translated by the operator into a numerical matrix of voices ${∥G_j\left(S^i\right)∥}_{q·l}$.

For problems with intersecting classes, in place of the parameters ${\epsilon }_{rv},p_{rv}$, one should consider ${\epsilon }_{rv}^d,p_{rv}^d$ and enter them independently for each class. Thus, different parameters can be assigned to the same pair $\left(r,v\right),S_r\in J_0\left(n,m,l\right),1\le v\le n$ different parameters can be compared ${\epsilon }_{rv}^1,\dots ,{\epsilon }_{rv}^l,p_{rv}^1,\dots {,}_{rv}^l$. But $G_j\left(S\right)$ only $S_{rv}^d,p_{rv}^d$.

The constructed voting model is an essential generalization of the basic model. Indeed, in order to obtain a basic model from it, it is necessary to set the parameter ${\epsilon }_{rv}$ equal for different and identical v, and the parameters $p_{rv}=p_r{\gamma }_v$.

The fact that in this model one support set is considered, in contrast to the basic model, is not a limitation, since sums of operators can be considered. One can obtain an operator operating on an arbitrary system of support sets.

We will mainly explore this voting model. Let us show that already in a linear closure, under the fulfillment of natural assumptions, it is possible to construct an algorithm that is correct for any preassigned control sample.

The construction of the operator of this algorithm is very simple, and, accordingly, the algorithm, with a sufficiently large volume of training sample, gives the correct answer almost everywhere. In real calculations, it is not necessary to remember all the parameters, $p_{rv}·{\epsilon }_{rv}$ it is enough to limit ourselves to only a small part.

6. Completeness of Linear Closure of the Second Model Voting

We will consider problems with non-overlapping classes $K_1,\dots ,K_l$ and assume that the information $J_0$ is given in the form of a learning table $T_{nml}$. The task of recognition will be to classify the final sample $S^1,S^2,\dots ,S^q,S^i=\left(b_{i1},b_{in}\right)$.

As before, in what follows, we will assume that in the recognizable sample ${\tilde{K}}_j$ the objects belong to the class $S^{q_{j-1}+1},\dots ,S^{q_j},q=0,q_l=q$.

The purpose of this section is to single out a set of basic operators of the considered model for calculating estimates, construct their linear closure, and prove the fact that for each class object ${\tilde{K}}_j$ from the sample these operators ${\tilde{S}}^q$ form a sufficiently $G_j$ large estimate $G_u$ and for $u\ne j$.

All basic operators, as well as operators from the linear closure, will be constructed explicitly.

We will first need a standard condition relating the type of training information $T_{nml}$ and a recognizing sample, ${\tilde{S}}^q$ namely, we will assume that:

for any two different objects $S^u,S^v$ from the collection ${\tilde{S}}^q$ among the objects included in $T_{nml}$ and belonging to the class K, there is such an object $S_t$ and such a sign, r what ${\rho }_r\left(a_{tr},b_{ur}\right)\ne \rho \left(a_{tr},b_{ur}\right)$.

In this case, it is customary to say that objects from the system ${\tilde{S}}^q$ are pairwise non-isomorphic.

When proving the completeness of a linear closure, we will rely on the notion of a marked pair. Since in this paper only problems with non-overlapping classes are considered, the notion of a marked pair will be somewhat changed.

Definition 1.

Pair $\left(S^u,j\right),S^u\in {\tilde{S}}^q,{\tilde{S}}^u\in K_j,1\le j\le l$ is called marked in the operator B if $B_v\left(Z\right)={∥a_{tv}∥}_{q·l},1\le v\le w,a_{uj}\ge 1,\left|a_{rw}\right|<\delta \to 0$ for all S such that ${\tilde{S}}^u\in K_r,r=1,2,\dots ,l$.

From the definition of a marked pair, it can be seen that such a pair appears in the operator B if: $a_{uj}=G_j\left(S^u\right)$ the estimate for an object $S^u$ by class $K_j$ is large enough, all estimates $a_{tv}=G_v\left(S^t\right)$ for the case when the object $S^t$ does not belong to the class $K_v$ are sufficiently small in absolute value.

Let $B_1,\dots ,B_w$ be given in some model such that each pair $\left(S^u,j\right),S^u\in K_j$ is marked with at least one operator $B_1$.

Theorem 2.

There is a linear combination ${\displaystyle \sum _{i=1}^n}{a}_i{B}_i=\tilde{B}\in \tilde{L}\left\{B\right\}$ such that $\tilde{A}=\tilde{B}·C$, C the threshold decision rule algorithm is correct for problem Z.

Proof of Theorem 2.

Recall that the threshold decision rule C is defined by the relation $C\left({∥a_{tv}∥}_{q·l}\right)={∥C\left(a_{tv}\right)∥}_{q·l}$.

$$C\left(a\right)=\left\{\begin{array}{cc}\hfill & 1,\mathrm{if}a>C_2\hfill \\ \hfill & 0,\mathrm{if}a<C_1,0\le C_1\le C_2\hfill \\ \hfill & \Delta ,\mathrm{if}{C}_1\le a\le C_2\hfill \end{array}\right.$$

(21)

Since every pair $\left(S^u,j\right)$, such that ${\tilde{S}}^u\in K_j,S^u\in {\tilde{S}}^q$ is marked by some operator $B_v,1\le v\le w$, this operator is worth the evaluation $G_{uj}=G_j\left(S^u\right)\ge 1$.

All other systems either mark or do not mark this pair. Operators that do not mark a pair $\left(S^u,j\right)$ give an estimate that does not exceed an arbitrarily small value in absolute value $\delta$; therefore, one can choose $\delta$ such that

$$\delta <\frac{C_1}{W\left(C_1+C_2\right)}$$

(22)

W—number of operators in the system $C_1,C_2$—parameters of the decision rule C.

Let us put

$$\tilde{B}=\left(C_1+C_2\right)\left(B_1+\dots +B_w\right)$$

(23)

Consider what estimate the operator will build $\tilde{B}$ for an object $S^u$ from the class $K_j$. The couple $\left(S^u,j\right)$ is marked. This means that the operator $B_v$ constructs an estimate not less than 1. The remaining operators either also construct an estimate for this pair not less than 1, or an estimate less than $\delta$ and in turn, $\delta$ inequality Equation (22) holds. In the worst case, all other operators construct ${\tilde{S}}^q$ negative small estimates for to $K_j$. Then, if the estimate $S^u$ for $K_j$ in the operator $\tilde{B}$ is denoted by ${\tilde{G}}_{uj}$ then from Equation (23) it is easy to obtain the inequality:

$${\tilde{G}}_{uj}\ge \left(C_1+C_2\right)·\left(1-\frac{w-1}{w}·\frac{C_1}{C_1+C_2}\right)>\left(C_1+C_2\right)·\left(1-\frac{C_1}{C_1+C_2}\right)=C_2$$

(24)

Applying the decision rule, we get that $C\left({\tilde{G}}_{uj}\right)=1$, and algorithm A establishes this inclusion.

This is true for any pair $\left(S^u,j\right)$ such that $S^u\in {\tilde{S}}^q,{\tilde{S}}^u\in K_j,j=1,\dots ,l$ since all such pairs are marked by some operator from the system $B_1,\dots ,B_w$.

Now, let $S^u\in {\tilde{S}}^q$ be ${\tilde{G}}_{ur}$ the estimate built by the operator for the object $S^u$ according to the class $K_r$. Since $S^u$ does not belong, $K_r$ the pair $\left(S^u,r\right)$ is not marked in any of the operators $B_1,\dots ,B_w$. Consequently, each of these operators constructs an estimate for $S^u$ the class $K_r$ that does not exceed in absolute value $\delta$, from the definition of the operator $\tilde{B}$ and the estimate $\delta$ that $\left|{\tilde{G}}_{ur}\right|<\left(C_1+C_2\right)W·\left(\frac{C_1}{\left(C_1+C_2\right)W}\right)=C_1$.

It can be seen from the definition of decision rule C that the algorithm $\tilde{A}=\tilde{B}·C$ establishes the inclusion $S^u\in K$, this is true for any pair $\left(S^u,r\right)$ such that $S^u\in {\tilde{S}}^q,S^u\in K_r,j=1,2,\dots ,l$.

The theorem has been proven. □

The purpose of further constructions is to find a system of operators $B_1,\dots ,B_w$ that, for an arbitrary problem $Z=\left(T_{mnl},{\tilde{S}}^q\right)$, mark any pair $\left(S^u,j\right)$ such that $S^u\in {\tilde{S}}^q,S^u\in K_j,j=1,2,\dots ,l$ and do not mark any pair $\left(S^u,K_r\right),S^u\in {\tilde{S}}^q,{\tilde{S}}^u\in K_r,j=1,\dots ,l.$

If we manage to find such a system $B_1,\dots ,B_w$, then, according to A, the algorithm correctly solves problem Z. The correct algorithm for Z can be written as:

$$\left(\left(C_1+C_2\right)\sum _{i=1}^w{B}_i\right)·C=A$$

Consider a sample ${\tilde{S}}^q=\left\{S^i,\dots ,S^q\right\},S^i=\left(b_{i1},\dots ,b_{in}\right)$ and a system of operators $B\left(j\right)$ such that all parameters ${\epsilon }_{uv},P_{uv},u=1,\dots ,m_{j-1},m_{j+1},\dots ,m,v=1,2,\dots ,n$ are chosen the same: ${\epsilon }_{uv}=0,P_{uv}=\epsilon \ge 0$, where $\epsilon$ is a sufficiently small number.

In other words, this means that if all pairs ${\tilde{S}}^u\in K_j\left(u,v\right)$ are assumed to be small, ${\epsilon }_{uv},P_{uv},v=1,2,\dots ,m,u=m_{j-1}+1,\dots ,m_j$ no restrictions are imposed on the parameters yet.

Let B be an arbitrary operator from $B\left(j\right)$ and $S=\left(a_1,\dots ,a_n\right)$ an arbitrary admissible object.

Let also $B\left(S\right)=\left(G_1^j\left(S\right),\dots ,G_j^j\left(S\right),\dots ,G_l^j\left(S\right)\right).$

Lemma 1.

Let $0\le G_t^j\left(S\right)<m·n·\epsilon ,t=1,2,\dots ,j-1,j+1,\dots ,l.$

Proof of Lemma 1.

When forming a value, $G_t^j\left(S\right)$ only pairs $\left(u,v\right)$ are considered such that $u=m_{t-1}+1,\dots ,m_t,v=1,\dots ,n$ only objects belonging to the class are considered $K_j$. □

From these pairs, in turn, pairs are selected that are included in the reference set ${\Omega }_t$.

Let us denote the number of pairs from $K_t\bigcap {\Omega }_t$ through $n_t$. Obviously, there is an inequality: $n_t\le n\left(m_t-m_{t-1}\right)<n·m$

Since $P_{uv}=\epsilon$ when comparing the elements a, (the value of the feature in the recognizable object $S,G_t^j\left(S\right)$ either 0 can be added to the value, if $p_v\left(a_{tv},a_{uv}\right)>{\epsilon }_{uv}=0$, or the value $P_{uv}=\epsilon$ if $p_v\left(a_{tv},a_{uv}\right)\le {\epsilon }_{uv}=0$.

If from the last assertion, as well as from the inequality, one easily obtains:

Consequence: Let $B^j\in B\left(j\right),B\left(Z\right)=B\left(T_{mnl},S^q\right)={∥a_{rt}^j∥}_{q·l}$.

Then the elements—$a_{rt}^j$ at $t\ne j$ satisfy the inequalities:

$$0\le a_{rt}^j<n·m·\epsilon ,r=1,2,\dots ,q$$

The proof of the corollary is obtained if we consistently apply Lemma 1 to recognizable objects $S^1,\dots ,S^q$ from the sample ${\tilde{S}}^q$.

We see that the operator B from the family $\left(B\right)$ constructs numerical matrices in which the elements of all columns except the j-th can be made arbitrarily small with an appropriate choice of the value of $\epsilon$. If it is required that $a_{rt}^j<\delta$, it is enough to put $\epsilon =\frac{\delta }{n·m}$.

Consider now a pair $\left(u,v\right)$ such that $1\le v\le n$, in other words, an object $S_u\in {\tilde{K}}_j$. The pair $\left(u,v\right)$ corresponds to the element in the learning table $a_{uv}$. In the control sample, as was previously accepted, the objects belong to the class and the rest of the objects do not belong to the class. For brevity, we will assume that the objects that do not belong ${\tilde{K}}_j$ form the class $Q_j$, and the remaining objects form the class $C{Q}_j$. Consider the values $p_v\left(a_{uv},b_{tv}\right),t=\overline{1,q}$, that is, the distance of the value v-th of the feature on the object $S_u$, in the learning table $T_{mnl}$ to the value of that feature in $S^t$ from $S^q$.

Let us arrange the objects from ${\tilde{S}}^q$ in ascending order of value $p_v\left(a_{uv},b_{tv}\right),t=\overline{1,q}$, objects with equal values of elements, arrange among themselves in an arbitrary way.

We get:

$$S^{r_1},S^{r_2},\dots ,S^{r_i},\dots ,S^{r_q}$$

$$0\le p_v\left(a_{uv},b_{r_{1}v}\right)\le p_v\left(a_{uv},b_{r_{2}v}\right)\le \dots \le p_v\left(a_{uv},b_{r_{q}v}\right)$$

Let us assign to the objects of the sequence the sign “+” if they belong to the class and $Q_j$ the sign “−” if they belong to the class $C{Q}_j$. The result might be, for example, the following sequence:

$$S^{+r_1},S^{+r_2},S^{-r_3},S^{-r_4},S^{+r_5},\dots ,\mathrm{etc}.$$

Definition 2.

A pair $\left(u,v\right)$ is called stationary if in the constructed sequence the signs “+, −” take place equal to one change of sign, and if the change of sign occurs on the elements $S^{r_i},S^{r_{i+1}}$ then:

$$p_v\left(a_{uv},b_{r_{i}v}\right)<p_v\left(a_{uv},b_{r_{i+1}v}\right)$$

Otherwise, the pair $\left(u,v\right)$ is called non-stationary.

Let us first consider the case when for each number $j=1,2,\dots ,l$ there is at least one pair $\left(u,v\right)$ stationary. In this case, the basic operators from the family $B\left(j\right)$ are relatively easy to define, in different ways for the following two cases:

(A)

The sequence has the form $S^{+r_1},\dots ,S^{+r_i},S^{-r_{i+1}},\dots ,S^{-r_q}$, that is relatively $a_{uv}$ all objects of the class $Q_j$ are closer than all objects of class $CQ$, then the operator $B^j\in B\left(j\right)$ is redefined as follows:

• The support set ${\Omega }_j$ is composed of one stationary pair $\left(u,v\right),1\le v\le n,u\in \left\{m_{j-1},\dots ,m_j\right\}$.
• ${\epsilon }_{uv}=\frac{1}{2}{p}_v\left(a_{uv},b_{r_{i+1}},V\right)$ other ${\epsilon }_{rw}=0$.
• $P=N$ otherwise $P_{uw}={{\epsilon }^{\prime }}_j,{{\epsilon }^{\prime }}_j$—a fairly small value.

(B)

The sequence looks like $S^{-r_t},\dots ,S^{+r_i},S^{+r_{i+1}},\dots ,S^{+r_q}$. The operator is searched in the form $B^{j_1}-B^{j_2};B^{j_1},B^{j_2}\in B\left(j\right)$. As before, in both operators, the support set $\Omega$, is composed of one critical pair $\left(u,v\right).P_{uv}=N,$ other $P_{rw}={\epsilon }^{\prime }$. But:

In operator $B^{j_1}:{\epsilon }_{uv}=p_v\left(a_{uv},b_{r_{q}v}\right)+1$.

In operator $B:{\epsilon }_{uv}=\frac{1}{2}\left[p_u\left(a_{uv},b_{r_{i-1}v}\right)+p_v\left(a_{uv},b_{rq}\right)\right]$.

Thus, we completely defined the operators $B_1\in B\left(1\right),B_1\in B\left(l\right)$.

Let the result of applying the operator $B^j$ to the problem $Z=\left(T_{mnl},S^q\right)$ be denoted by ${∥b_{rt}∥}_{q·l}$.

Lemma 2.

If $S^r\in CQ\left(S^r\in {\tilde{S}}^q\right)\bigcap K_j$ then if $S^r\in CQ$ then $b_{rj}^j=0$.

Proof of Lemma 2.

1. Consider the first case of defining the operator $B^j$. Then, there is a stationary pair $\left(u,v\right)$ for which the descriptions of the above sequence are as follows:

$$S^{+r_1},\dots ,S^{+r_w},S^{-r_{w+1}},\dots ,S^{-r_q}$$

where

$$Q=\left\{S^{r_1},\dots ,S^{r_w}\right\},CQ=\left\{S^{r_{w+1}},\dots ,S^{r_q}\right\},p_v\left(a_{uv},b_{r_{w}v}\right)<p_v\left(a_{uv},b_{r_{w+1}v}\right)$$

(25)

When defining the operator B, the quantities ${\epsilon }_v$ are chosen in such a way that the following inequalities are satisfied:

$$p_v\left(a_{uv},b_{r_{w}v}\right)<{\epsilon }_v<p_v\left(a_{uv},b_{r_{w+1}v}\right)$$

(26)

From inequality [19], it is easy to see that for each object from Q the proximity function for this S over the reference set $S^i,\Omega =\left\{\left(u,v\right)\right\}$ is equal to 1. Therefore, $b_{ij}=N,i=r_i,\dots ,r_w$.

Similarly, the proximity function for objects from $CQ$ is $\Omega =\left\{\left(u,v\right)\right\}$ equal to 0. And therefore, $b_{ij}^j=0,i=r_w+1,\dots ,r_q$.

2. Consider the second case in the definition of the operator $B^j$. In this case, there is a stationary point $\left(u,v\right)$ and the sequence corresponding to it has the form:

$$S^{-r},\dots ,S^{-rw},S^{+rw+1},\dots ,S^{+rq};Q=\left\{S^{rw+1},S^{rq}\right\},CQ=\left\{S^{r1},\dots ,S^{rw}\right\}$$

(27)

In the operator, $B^j$ the value ${\epsilon }_v$ is chosen in such a way that the proximity function for the reference value ${\Omega }_j=\left\{\left(u,v\right)\right\}$ is equal to 1 for all objects from the selection ${\tilde{S}}^q$.

Therefore, if $B^{ij}\left(Z\right)={∥b_{rt}^{ij}∥}_{q·l}$, then $b_{rt}^{ij}=N,r=\overline{1,q}$.

In the operator $B^{jr}\left(Z\right)={∥b_{rt}^{ji}∥}_{q·l},$ the value ${\epsilon }_v$ is chosen in such a way that the proximity function in the reference set ${\Omega }_j=\left\{\left(u,v\right)\right\}$ is equal to 1 for objects from $CQ$, and is equal to 0 for objects from Q. That is why

$$\left\{\begin{array}{cc}\hfill & b_{rj}^{jr}=N,S^r\in CQ\hfill \\ \hfill & b_{rj}^{jr}=0,S^r\in Q\hfill \end{array}\right.$$

(28)

From equality [21,22], and also from the fact that $B^j=B^{j_1}-B^{j_2}$ equalities follow:

$$\left\{\begin{array}{cc}\hfill & b_{rj}^j=N,S^r\in CQ\hfill \\ \hfill & b_{rj}^j=0,S^r\in Q\hfill \end{array}\right.$$

(29)

The Lemma is proven. □

Consider now the operator: $B=B^1+\dots +B^l$ and put $B\left(Z\right)=B\left(T_{mnl},{\tilde{S}}^q\right)={∥b_{rt}∥}_{q·l}.$

In Lemma 2, when applying the operator, $B^j$, the elements of all columns with the exception of j are not exceeded.

Objects $S^r\in K_j$ obtain grade N.

Objects $S^r\in K_j\bigcap {\tilde{S}}^q$ obtain grade 0.

Because $b_{rt}=b_{rt}^1+\dots +b_{rt}^l$ by definition of the operator $B^j$, then if

$$S^r\in K_j\bigcap {\tilde{S}}^q\Rightarrow b_{rj}\ge N+m·n·\left(l-1\right)·\epsilon$$

(30)

$$S\in C{K}_j\bigcap {\tilde{S}}^q\Rightarrow \left|b_{rj}\right|\le m·n·l·\epsilon$$

(31)

Having appropriately chosen the values, $N,\epsilon$ and using Theorem 3, we prove the theorem.

Theorem 3.

If in the problem Z for each number $j=\overline{1,l}$ there is a stationary pair, then the algorithm $A=\left(\left(C_1+C_2\right){\displaystyle \sum _{i=1}^l}{B}^i\right)·\left(C\left(C_1,C_2\right)\right)$ is correct for problem Z.

Since the operator we have constructed $\left(C_1+C_2\right){\displaystyle \sum _{i=1}^l}{B}^i$ belongs to the linear closure of a model of the type of calculation of estimates, then we proved the completeness of the linear closure of this model for all problems in which for each class there is at least one stationary pair, $\left(u,v\right)$, and moreover, we wrote this correct algorithm A explicitly.

The verification of the fact that such a stationary pair really exists is not difficult.

For this, enough for each pair $\left(u,v\right)$, where $u=m_{j-1}+1,\dots ,m_j,v=1,2,\dots ,n$ calculate all $p_v\left(a_{uv},b_{iv}\right),i=1,2,\dots ,q$ and check whether all inequalities of the 1st or 2nd group are fulfilled simultaneously. If all inequalities of groups 1 and 2 are simultaneously satisfied, then the pair $\left(u,v\right)$ is stationary and can be constructed $B^j$ in the same way as was performed in the proof of the theorem.

The conditions for the existence of a stationary pair essentially mean the following:

There is an element $S^u,S^u\in K_j$ and features in the learning table $T_{mnl}$.

1. The distance according to the V attribute from $S_v$ to all elements of the control sample that belong is $K_j$ strictly less than all such distances for objects of the control sample that do not belong to K;

2. The distance according to the V attribute from the object in the control sample that does not belong is $K_j$ less than all such distances for the objects of the control sample that belong to $K_j$.

Consider the 2nd case, when the construction of a correct algorithm in a linear closure is quite simple. As before, we arrange the objects of the control set ${\tilde{S}}^q$ in sequence by increasing the distance from some value of the feature u, in the reference $S_w,S_w\in {\tilde{K}}_j,1\le u\le n$. We put the constructed sequence over the elements of the sequence with the sign “+”, if, $S^{ri}\in K_j$ and the sign “−”, if $S^{ri}\in C{K}_j$ denoted by $\pi \left(w,u\right)$. Let us find in this sequence the last element in order $S^{+rp}$, this element must also be such that the next element $S^{-rp}$ has the property:

$$p_v\left(a_{wu},b_{r_{t}u}\right)<p_v\left(a_{wu},b_{r_{p}u}\right)$$

The set of elements of the sequence $\pi \left(w,u\right)$ following the element $S^{+r_t}$ is denoted by $M^{-}\left(w,u\right)$.

We introduce the set $M_j^{-}={\displaystyle \bigcup _{S_w\in {\tilde{K}}_j}}{\displaystyle \bigcup _{u=1}^n}{M}^{-}\left(w,u\right).$

Similarly to the previous one, in each sequence, we select the first element in order $S^{+r_t}$, and moreover, such that $S^{-r_p}$ the inequality holds for the previous element:

$p_v\left(a_{wu},b_{r_{p}u}\right)<p_v\left(a_{wu},b_{r_{t}u}\right)$

Element $S^{+r_t}$ in the sequence $\pi \left(w,u\right)$ is denoted by $M^{+}\left(w,u\right)$. We introduce the set

$$M_j^{+}=\bigcup _{S_w\in {\tilde{K}}_j}\bigcup _{u=1}^n{M}^{+}\left(w,u\right)$$

(32)

Definition 3.

The problem $Z=\left(J,{\tilde{S}}^q\right)$ is called monotonic if for each $j=1,2,\dots ,l$ one of the two equalities is satisfied:

$${\tilde{S}}^q\bigcap C{\tilde{K}}_j=M_j^{-}$$

(33)

$${\tilde{S}}^q\bigcap {\tilde{K}}_j=M_j^{+}$$

(34)

The meaning of the monotonicity condition is as follows, an arbitrary reference object is chosen to belong to ${\tilde{K}}_j$ and an arbitrary feature with number u, in the control sample ${\tilde{S}}^q$ we select all objects that do not belong to the class ${\tilde{K}}_j$ and such that, relative to the selected feature, they are farther from $S_w$ than all objects ${\tilde{S}}^q$ belonging to the class ${\tilde{K}}_j$.

The set of all such objects not belonging to the class ${\tilde{K}}_j$ is denoted by $M^{-}\left(w,u\right)$. Condition [17] is that if all elements of the set $M_j^{-}\left(w,u\right)$ are summed up, then all elements from the control sample that do not belong to the class are obtained ${\tilde{K}}_j$.

Construction of operators $B_j,j=1,2,\dots ,$ for a monotonic problem Z.

1. The choice of the reference subset $\Omega$, since the problem Z is monotone, then one of the conditions [17] or [18] is satisfied, the choice of the reference set is the same in both cases, so we will assume that we have:

$${\tilde{S}}^q\bigcap C{K}_j=M_j^{-}\bigcup _{S_w\in {\tilde{K}}_j}\bigcup _{u=1}^n{M}^{-}\left(w,u\right)$$

(35)

The set $M^{-}\left(w,u\right)$ forms a cover of the set ${\tilde{S}}^q\bigcap CK$, but this cover may be redundant, in other words, some sets $M^{-}\left(w,u\right)$ may be removed so that the cover remains a cover. Removing such extra sets, we construct irreducible covers for ${\tilde{S}}^q\bigcap C{K}_j$.

Let the constructed irreducible cover have the form:

$${\tilde{S}}^q\bigcap C{K}_j=M^{-}\left(w_1,u_1\right)\bigcup \dots \bigcup M^{-}\left(w_2,u_2\right)$$

(36)

Then, ${\Omega }_j=\left\{\left(w_1,u_1\right),\dots ,\left(w_2,u_2\right)\right\}$.

Choice of options ${\tilde{\epsilon }}_j$.

All parameters of this group, with the exception of the parameters, ${\epsilon }_{w_i{u}_i},i=1,2,\dots ,$ are chosen so large that the following inequalities are satisfied: $p_v\left(a_{rv}{b}_{iv}\right)<{\epsilon }_{rv},i=1,2,\dots ,q$ or ${\epsilon }_{rv}={\displaystyle \underset{i=\overline{1,q}}{max}}{p}_v\left(a_{rv},b_{iv}\right)+1$.

The parameters ${\epsilon }_{w_i{u}_i}=\frac{1}{2}\left(p_{ui}\left(a_{w_i{u}_i}{b}_{t{u}_i}\right)+p\left(a_{w_i{u}_i}{b}_{t{u}_i}\right)\right)$ are chosen so that the following inequalities hold:

In the sequence $\pi \left(w_i,u_i\right)$, we find the last element $S^{+p}$ and the element following it $S^{-t}$, then $p_{u_i}\left(a_{w_i{u}_i}{b}_{p{u}_i}\right)<{\epsilon }_{w_i{u}_i}<p_{u_i}\left(a_{w_i{u}_i}{b}_{t{u}_i}\right)$ or ${\epsilon }_{w_i{u}_i}=\frac{1}{2}\left(p_{u_i}\left(a_{w_i{u}_i}{b}_{t{u}_i}\right)+p\left(a_{w_i{u}_i}{b}_{t{u}_i}\right)\right)$.

This choice of parameters ${\epsilon }_{w_i{u}_i}$ occurs in cases where the relation is satisfied: ${\tilde{\epsilon }}^q\bigcap C{K}_j=M_j^{-}$. If this relation is not satisfied, but the relation ${\tilde{\epsilon }}^q\bigcap K_j=M_j^{+}$.

Then, the operator $B_j$ is sought in the form of a difference $B_{j_1}-B_{j_2}$, and the values ${\epsilon }_{ij}$ are chosen differently for the operators that make up the difference.

Options $\tilde{p}\tilde{\gamma }$. The parameters $\gamma \left(S_i\right)={\gamma }_i$ are assumed to be equal to a sufficiently small value; $\delta$ more precisely, the value $\delta$ will be indicated later for all $S_i\in {\tilde{K}}_j$ and also for such $S_i$ numbers of which are not contained in the set $W_1,\dots ,W_2$. For the rest $S_i$, we assume: $\gamma \left(S_i\right)={\gamma }_i=N$.

Similarly, $P_u=\dots =P_{ur}=N$ rest $P_i$, $P_i=\delta$. The values N are chosen to be sufficiently large; the exact values for N are given later. The operator definition $B_j$ is complete for the case: ${\tilde{S}}^q\bigcap C{K}_j=M_j^{-}$.

Theorem 4.

The operator for calculating estimates defined above marks all objects from the class in the control sample $K_j$ and only them. In other words, if $B\left(Z\right)={∥G_{ij}∥}_{q·l}$ and objects $S^{u_1},\dots ,S^{u_n}\in K_j$ at the remaining objects do not belong to the control sample $K_j$, then $G_{u_{t}j}\ge N,t=\overline{1,K}$$\left|G_{vj}\right|<\delta ,V\notin \left\{u_1,\dots ,u_k\right\}$.

Proof of Theorem 4.

Threshold parameters ${\epsilon }_{uv}$ and reference sets were chosen in such a way that for each object $S^{up}=\left(b_{u{p}_1},\dots ,b_{u{p}_n}\right)$ from $K_j$ the relation was fulfilled $p_v\left(a_{uv}{b}_{u_{p}v}\right)$$\le {\epsilon }_{uv}$ in such a way, according to the constructed support set, the proximity function is equal to 1, and the total estimate is not less than ${\displaystyle \sum _{\left(u,v\right)}}{p}_{uv}·{\gamma }_{uv}\ge N·N=N^2>N$.

If the object of the control set does not belong, then $K_j$ it has a mark $\left(-\right)\left(u,v\right)$ in the sequences, and therefore there is such a pair $\pi$ (by the definition of a monotone problem) that in the sequence $\pi \left(u,v\right)$ this element is after all elements $K_j$, then ${\epsilon }_{uv}$ they are chosen so that the corresponding inequality $p_v\left(a_{uv}{b}_{iv}\right)\le {\epsilon }_{uv}$ violated. In this case, the proximity function for the object $S^i\in C{\tilde{K}}_j$ is equal to 0, and $G_{ij}=0<\delta$.

The evaluation operator constructed in this way puts large estimates for control elements from ${\tilde{K}}_j$, and small estimates for elements from $C{\tilde{K}}_j$. The last assertion easily implies the correctness of the algorithm composed of the previously defined operator and the threshold decision rule.

The Theorem has been proven. □

The proof for the 2nd case of the monotone problem is carried out according to the same principle (see the proof for the stationary problem) only the operator is sought as the difference between two operators.

The simple cases presented by us are an illustration for the proof of the main theorem on the well-posedness of the linear closure. The proof of this theorem is technically more complicated, it is divided into a series of steps; however, each individual step implements a construction of the same type that was used in the last theorems.

When proving the main theorem, in essence, it is the linear closure that is used.

The proof of the linear closure well-posedness theorem will be carried out in two stages. In the first stage, we will introduce one additional constraint on the control objects of the training sample.

Practical tasks really satisfy him. In the first stage, the well-posedness theorem will be proved under this constraint.

Definition 4.

Control objects $S^1,\dots ,S^q$ are called consistent with objects $S_1,\dots ,S_m$ if for each pair $S^u,S^v,S^u\in K_j,S^v\notin K_j$ there is at least one object $S_r\in K_j$ and attribute W such that $p_w\left(a_{rw},b_{uw}\right)<p_w\left(a_{rw},b_{vw}\right)$.

The lack of consistency in the control sample means that in the control there are objects $S^v\notin K_j$ that are closer in all respects to all objects in the class $K_j$. In this case, all learning information is collected in such a way as to assign a closer object $S^v$ to a class $K_j$ with greater preference than a more distant object $S^q$ and thereby make a mistake.

We will first consider classes in which there are no such pathological cases, that is, the situation when the control objects are consistent with the training ones.

Let, as before, the objects $S_1,\dots ,S_m;S_i=\left(a_{i1},\dots ,a_{in}\right)i=\overline{1,n}$.

They form learning information J, and the objects $S_{m_{j-1}}+1,\dots ,S_{m_j},m_0=0,m_l=m$ belong to the class $K_j$ and do not belong to other classes.

The objects $S^1,\dots ,S^q,S^i=\left(b_{i1},\dots ,b_{in}\right),j=\overline{1,l},i=\overline{1,q}$ form a control sample and the objects $S^{q_{j-1}+1},\dots ,S^{q_i}$ belong to a class $K_j$ and do not belong to other classes.

As before, we denote:

$$\left\{S_1,\dots ,S_m\right\}\bigcap K_j=K,\left\{S_1,\dots ,S_m\right\}\setminus {\tilde{K}}_j=C{\tilde{K}}_j$$

(37)

$$\left\{S^1,\dots ,S^q\right\}\bigcap K_j=K_j^1,\left\{S^1,\dots ,S^q\right\}\setminus {\tilde{K}}_j^1=C{K}_j^1$$

(38)

Operator formation $B_j,j=\overline{1,l}.$

1. For all pairs $\left(u,v\right)$ such that $S_k\in C{\tilde{K}}_j,V=\overline{1,K}$ we assume ${\epsilon }_{uv}=0,p_{uv}={\gamma }_{uv}=\delta$.

2. Consider an arbitrary control object $S^t\in K_j^1$.

By the definition of a training-consistent control sample, for each $S^r\in K_j^1$ there is such a pair $\left(S_k,W\right),S_k\in K_j,1\le W\le n$.

What $p_w\left(a_{kw},b_{tw}\right)<p_w\left(a_{kw},b_{rw}\right)$. For the pair $\left(k,w\right)$ we assume:

$$p_{kw}=N,{\gamma }_{kw}=N,{\epsilon }_{kw}=\frac{1}{2}\left(p_w\left(a_{kw},b_{tw}\right)+p_w\left(a_{kw},b_{rw}\right)\right)$$

(39)

Obviously $p_w\left(a_{kw},b_{tw}\right)<{\epsilon }_{kw}<p_w\left(a_{kw},b_{rw}\right)$.

Let us include in the support set all pairs $\left(k,w\right)$ for all $S^r\in K_j^1$.

We have defined an auxiliary operator: $B_j^t,1\le j\le l,S^t\in K_j^1$

$$B_j=\sum _{S^t\in K_j^1}{B}_j^t,j=1,2,\dots ,l$$

(40)

Formation of operator B. $B={\displaystyle \sum _{j=1}^l}{B}_j$

We need to study what numeric matrix the operator B translates into task Z, with a training sample $S_1,\dots ,S_m$ and a control sample $S^1,\dots ,S^q$. The evaluation of the elements of this matrix will be performed sequentially by the steps of constructing the operator B. The first step is to form the operator $B_j^t$.

Let $B_j^t\left(Z\right)={∥G_{\alpha \beta }\left(j,t\right)∥}_{q·l}$.

Lemma 3.

If $\beta \ne j$ that $G_{\alpha \beta }\left(j,t\right)·{\delta }^2·n·m$.

Proof of Lemma 3.

The formation of estimates with respect to the class $B_{\beta }$ is carried out for some of the pairs $\left(u,v\right)$ such that for each such pair the term included in the estimate does not exceed: $P_u{\gamma }_n=\delta ·\delta ={\delta }^2$.

The total number of pairs $\left(u,v\right),S_u\in C{K}_j$ is obviously $n·\left(m-\left(m_j-m_{j-1}\right)\right)<n·m_j$.

From this, it easily follows that $G_{\alpha \beta }\left(j,t\right)·{\delta }^2·n·m$.

The Lemma is proven. □

Lemma 4.

If $\beta \ne j,S^{\alpha }\in C{K}_j$, that $G_{\alpha \beta }\left(j,t\right)=0$.

Proof of Lemma 4.

In the base set of the operator $B_j^t$ for each element $S^{\alpha }\in C{K}_j$ there is a pair $\left(k,w\right),S_k\in K_j,1\le w\le n$ such that $p_w\left(a_{kw},b_{tw}\right)<p_w\left(a_{kw},b_{\alpha w}\right)$.

By choosing the parameters $E_{kw}$, as shown above, we obtain $p_w\left(a_{kw},b_{tw}\right)>{\epsilon }_{kw}$.

According to the definition of the proximity function for the unique support set of the operator $B_j^t$, for the object $S^{\alpha }$ it is equal to 0. Therefore, $G_{\alpha \beta }\left(j,t\right)\ge 0$, which proves the Lemma. □

Lemma 5.

$G_{\alpha \beta }\left(j,t\right)\ge N^2$.

Proof of Lemma 5.

For each pair $\left(k,w\right)$ included in the base set of the operator, $B_j^t$ the parameter ${\epsilon }_{kw}$, is chosen so that $p\left(a_{kw},b_{tw}\right)>{\epsilon }_{kw}$. Due to inequality, the proximity function in the base set of the operator $B_j^t$ is equal to 1; therefore, $G_{tj}\left(j,t\right)={\displaystyle \sum _{\left(k,w\right)}}{P}_{kw}{\gamma }_{kw}=\sum N·N>N^2.$

The Lemma is proven. □

Let $B_j\left(Z\right)={∥G_{\alpha \beta }\left(j\right)∥}_{q·l},j=\overline{1,l}.$

By definition of the operator $B_j$.

$$G_{\alpha \beta }\left(j\right)=G_{\alpha \beta }(j,q_{j-1}+1)+\dots +G_{\alpha \beta }(j,q_j)$$

(41)

Using the matrix ${∥G_{\alpha \beta }(j,t)∥}_{q·l}$ and Equation (41), we obtain the following inequalities:

$$\left\{\begin{array}{cc}\hfill & G_{j\alpha }\left(j\right)\ge N^2,\alpha =q_{i-1}+1,\dots ,q_i\hfill \\ \hfill & G_{j\alpha }\left(j\right)=0,\alpha =1,2,\dots ,q_{i-1},q_{i+1},\dots ,q\hfill \end{array}\right.$$

(42)

True $0\le G_{\alpha \beta }\left(j\right)\le q·n·{\delta }^2$ for others $\alpha \beta$.

$$\begin{array}{cc}\begin{array}{c}S\\ S^{\prime }\\ ⋮\\ S^{q_{j-1}}\\ S^{q_{j-1}+1}\\ ⋮\\ S^{t-1}\\ S^t\\ S^{t+1}\\ S^{q_j}\\ ⋮\\ S^q\end{array}& ∥\begin{array}{cccccccc}1& 2& \dots & j-1& j& j+1& \dots & l\\ 0& 0& 0& 0& 0\le G_{\alpha \beta }\left(j\right)\le q·n·{\delta }^2& 0& 0& 0\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& \ge N^2& 0& 0& 0\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& 0& 0& \ge N^2& 0& 0& 0\\ \dots & \dots & \dots & \dots & & \dots & \dots & \dots \\ 0& 0& 0& 0& \ge N^2& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& 0& 0& 0& 0& 0& 0\end{array}∥\end{array}$$

Because $B={\displaystyle \sum _{j=1}^l}{B}_j$.

And ${∥G_{\alpha \beta }∥}_{q·l}$ is the matrix into which the operator transforms the problem, then $G_{\alpha \beta }={\displaystyle \sum _{j=1}^l}{G}_{\alpha \beta }\left(j\right),\alpha =\overline{1,q},\beta =\overline{1,l}$.

Lemmas 3–5 clearly imply the following inequalities $G_{\alpha \beta }\ge 1·N^2,\beta =\overline{1,l}$ at $\beta =j,\alpha =q_{j-1}+1,\dots ,q;q_0=q,q_1=q$.

For everyone else $\alpha ,\beta$: $0\le G_{\alpha \beta }\le n·m·l·{\delta }^2$.

$C_1,C_2$ is a decision rule; then, we can choose the values in such a way $\delta ,N$ that the algorithm $A=B·C(C_1,C_2)$ will give correct answers for all elements $S^1,\dots ,S^q$ across all classes $K_1,\dots ,K_l$.

Recall that the decision rule $\left(C_1,C_2\right)$ is applied to numerical matrices element by element, that is, $C\left({∥G_{\alpha \beta }∥}_{q·l}\right)=∥C{\left(G_{\alpha \beta }\right)}_{q·l}∥$ and $C\left(G_{\alpha \beta }\right)=\left\{\begin{array}{cc}& 1,G_{\alpha \beta }>C_2\hfill \\ & 0,G_{\alpha \beta }<C_1,0<C_1<C_2\hfill \\ & \Delta ,C_1\le G_{\alpha \beta }\le C_2\hfill \end{array}\right..$

From the definition of the decision rule and inequalities, it is clear that the parameter N must be chosen so that the inequality $1·N^2>C_2$.

Therefore, one can put $N=\sqrt{\frac{C_2}{l}+1}$.

With this choice of the parameter N, each of the objects $S^{q_{j-1}+1},\dots ,S^{q_j}$ will be assigned by the algorithm A to the class $K_j$.

It follows from the definition of the threshold decision rule and inequalities that the parameter $\delta$ can be chosen so that the inequality $n·m·l·{\delta }^2<C_1$.

Therefore, it suffices to take as $\delta$ any positive quantity satisfying the inequalities $\delta <\sqrt{\frac{C_1}{n·m·q·l}}.$

In this case, each of the objects $S^1,\dots ,S^{q_{j-1}}{S}^{q_{j+1}},\dots ,S^q$ will not be assigned to the class $K_j,j=\overline{1,l},q_1=0,q_l=q.$

We have proven.

Theorem 5.

$A=B·C(C_1,C_2)$ with threshold decision rule C and operator B.

$$B={\displaystyle \sum _{j=1}^l}{B}_j,B_j=\sum _{S^t\in K_j}{B}_j^t$$

Operators $B_j^t$ are operators for calculating estimates, correct for the problem $Z=\left\{S_1,\dots ,S_m,{∥{\alpha }_{ij}∥}_{m·l},S^1,\dots ,S^q\right\}$.

Each of the operators $B_j$ is specified by a set of numerical parameters ${\epsilon }_{uv},p_{uv},$ where $u=\overline{1,m},v=\overline{1,n}$. m—the number of objects in the learning sample, n—the number of features participating in the description of objects, that is, a set of $3·n·m$ numerical parameters.

From all that has been said above, it follows that with the described choice of parameters N, the matrix ${∥{\beta }_{ij}∥}_{q·l}$, into which the problem Z is converted by the algorithm $A=B·C(C_1,C_2)$.

As follows:

$$\begin{array}{cc}\begin{array}{c}{S}^1\\ S^{q_1}\\ ⋮\\ S^{q_1+1}\\ S^{q_j}\\ ⋮\\ S^{q_j+1}\\ ⋮\\ S^{q_{l-1}}\\ ⋮\\ S^{q_{l-1}+1}\\ ⋮\\ S^q\end{array}& ∥\begin{array}{cccccc}1& 2& \dots & j& \dots & l\\ 1& 0& \dots & 0& \dots & 0\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 1& 0& \dots & 0& \dots & 0\\ 0& 1& \dots & 0& \dots & 0\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& \dots & 1& \dots & 0\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& \dots & 0& \dots & 0\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& \dots & 0& \dots & 1\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 0& 0& \dots & 0& \dots & 1\end{array}∥\end{array}$$

Here, the operator B in terms of elementary operators has the form $B={\displaystyle \sum _{j=1}^l}{\displaystyle \sum _{S^t\in K_j}}{B}_j^t$ that is, the operator B belongs to the linear closure of the previously introduced families of estimation algorithms.

Significant memory is required to write code B; however, when solving real applied problems, the operator code can be placed in the RAM of modern computers. So, if $n=100,m=50,q=100$, that is, the training material consists of 50 objects described by 100 features, and it is required to store $1.5\times {10}^{76}$ numbers in memory.

In the future, we will consider methods that make it possible to more economically encode the operator B, which will reduce the required memory and more efficiently use the constructed correct algorithms for solving applied problems.

Summarizing all the above, we can state that we have proved the theorem.

Theorem 6.

Algorithm

$$A=\left(\sum _{j=1}^l\sum _{S^t\in K_j}{B}_j\left(S^t\right)·C(C_1,C_2)\right)$$

with an operator from the linear closure of the score, the calculation model is correct for problem Z, and the operator is the sum of q operators from the score calculation model and is described by a set of $3·n·m·q$ numerical parameters.

The only condition for constructing a correct rule is the consistency of the training control sample.

7. Results

In [15], the use of Internet of Things technologies in ecology (using the example of the Aral Sea region) as a system is proposed (Figure 1). The system was developed as a website. The Django framework was used to develop the server side of the system and Vue.js was used to develop the client side as a single page application (SPA) using the Quasar GUI framework. To start the system, you need to open this website ecoaral.uz in one of the modern browsers. After this, the main window of the system will be reflected on the browser page.

In this article, to identify input information flows, we considered the so-called parametric recognition algorithms, i.e., such sets of algorithms in which each algorithm is one-to-one encoded by a set of numerical parameters. These models analyze the proximity between parts of previously classified objects and the object to be classified. Based on a set of assessments, a general assessment of the object is generated and, according to the introduced decision rule, the belonging of the recognized object to one or another class is determined.

In this article, as the initial model (A), we consider a model related to the model for calculating estimates, supplemented with some simple recognition algorithms such as the nearest neighbor algorithm, the average distance algorithm, etc.

The peculiarity of algorithms of this class is that in order to calculate estimates that determine the identity of a recognized object, there are simple analytical formulas that replace complex enumeration procedures that arise when calculating proximity estimates using a system of support sets.

In these models, the division of the algorithm into recognition operators and decision rules is carried out in a natural way.

We will only consider algorithms that can be represented in the form $A=B·C$, where B is an arbitrary recognition operator. It turns out that an essential part of the algorithm is the operator—B; the decisive rule is that C can be made standard for all algorithms and programs. Any voting recognition operator maps task Z into a numeric matrix of votes or ratings $B\left(Z\right)={∥{\Gamma }_{ij}∥}_{q·l}$${\Gamma }_{ij}={\Gamma }_j\left(S\right)$

Moreover, the value ${\Gamma }_{ij}$ has a clear, meaningful interpretation. This value can be considered as the degree of belonging of the examined object $S^i$ to class $K_j$, expressed as a number. Let

$$(\tilde{\alpha }-\tilde{\beta })=\sum _{i=1}^6\sum _{j=1}^{10}\left|{\alpha }_i-{\beta }_j\right|\to min$$

(43)

${\alpha }_i$—these are sensor data, ${\beta }_j$—salinity class parameters. Sensor data in

Table 2. Number of parameter votes.

Valid (HCO3)	Valid (Cl)	Valid (SO4)	Valid (Na)	Frequency	Percent	Valid Percent	Cumulative Percent
0.68	0.56	0.50	0.51	1	4.0	4.0	4.0
0.73	0.67	0.60	0.58	1	4.0	4.0	8.0
0.78	0.67	0.68	0.68	1	4.0	4.0	12.0
0.89	0.68	0.68	0.78	1	4.0	4.0	16.0
0.93	0.68	0.69	0.80	1	4.0	4.0	20.0
0.94	0.68	0.69	0.80	1	4.0	4.0	24.0
0.95	0.68	0.69	0.80	1	4.0	4.0	28.0
0.95	0.68	0.69	0.80	1	4.0	4.0	32.0
0.95	0.70	0.69	0.81	1	4.0	4.0	36.0
0.95	0.70	0.70	0.81	1	4.0	4.0	40.0
0.95	0.71	0.71	0.81	1	4.0	4.0	44.0
0.96	0.71	0.72	0.81	1	4.0	4.0	48.0
0.96	0.74	0.72	0.81	1	4.0	4.0	52.0
0.96	0.74	0.74	0.81	1	4.0	4.0	56.0
0.96	0.76	0.75	0.82	1	4.0	4.0	60.0
0.96	0.78	0.77	0.82	1	4.0	4.0	64.0
0.97	0.82	0.81	0.82	1	4.0	4.0	68.0
0.97	0.83	0.82	0.82	1	4.0	4.0	72.0
0.97	0.85	0.83	0.83	1	4.0	4.0	76.0
0.98	0.88	0.84	0.84	1	4.0	4.0	80.0
0.98	0.89	0.86	0.85	1	4.0	4.0	84.0
0.98	0.91	0.87	0.87	1	4.0	4.0	88.0
0.98	0.92	0.89	0.87	1	4.0	4.0	92.0
0.99	0.96	0.90	0.93	1	4.0	4.0	96.0
1.00	1.00	0.98	0.96	1	4.0	4.0	100.0
Total				25	100	100

: $HC{O}_3$ (bicarbonate), $Cl$ (chlorine), $S{O}_4$ (sulfuric acid), $Ca$ (calcium), $Mg$ (magnesium), $Na$ (sodium) in

Table 3. Descriptive Statistics.

	No.	Range	Minimum	Maximum	Mean	Std. Deviation	Variance
${\rho }_i\left(HC{O}_3\right)$	25	0.32	0.68	1.00	0.9323	0.08130	0.007
${\rho }_i\left(Cl\right)$	25	0.44	0.56	1. 00	0.7675	0.11096	0.012
${\rho }_i\left(S{O}_4\right)$	25	0.48	0.50	0.98	0.7528	0.10544	0.011
${\rho }_i\left(Na\right)$	25	0.45	0.51	0.96	0.8007	0.09227	0.009
Valid	25	1.66	2.24	3.90	3.2533	0.34047	0.116

and

Table 4. Statistics.

	${\mathit{\rho }}_{\mathit{i}}\left({\mathit{HCO}}_3\right)$	${\mathit{\rho }}_{\mathit{i}}\left(\mathit{Cl}\right)$	${\mathit{\rho }}_{\mathit{i}}\left(\mathit{S}{\mathit{O}}_4\right)$	${\mathit{\rho }}_{\mathit{i}}\left(\mathit{Na}\right)$	Number of Votes
Valid	25	25	25	25	25
Missing	0	0	0	0	0

: Salinity is divided into five classes (non-saline, slightly saline, moderately saline, highly saline, and very highly saline), and each class consists of 10 points.

If the sensor receives data $a_i$ and it checks the value $a_i-b_i\to min$ if the given condition completed, and indicates which salinity class it belongs to. If the $a_i-b_i\to min$ values correspond to more than one salinity class, then the information was intercepted somewhere (see Figure 2).

To solve the problem of comparative classification in an information system in electronic resources based on an algorithm for calculating estimates, a correct algorithm was used

$$A=\left(\sum _{i=1}^l\sum _{S^t\in K_j}B\left(S^t\right)·C\left(C_1,C_2\right)\right)$$

(44)

The work of the recognition algorithm in this case is based on the analysis of the data structure and its importance for classification purposes. With this approach, reliability is assessed by the quality of work of the recognition algorithm on control material. In other words, the algorithm carries out a classification and its results are compared with those that are known a priory. Obviously, with a sufficiently large volume of control, the results reflect the quality of the algorithm. It was this approach that was implied and incorporated into the software package, the application of which to the initial information made it possible to obtain the following: relative weights of feature groups ${\rho }_i\left(S,S^{\prime }\right)=minp(a_i-b_i)$, vote formula $G_j\left(S^i\right)=\frac{1}{{\rho }_j(S,S^{\prime })+1}$ and the sum of operators $B_1+B_2+B_3+B_4=G_1+G_2+G_3+G_4$.

Example for $Cl$:

${\rho }_1\left(S,S^{\prime }\right)=\left|0.001-0.5\right|=0.499$                   ${\rho }_2\left(S,S^{\prime }\right)=\left|0.004-0.5\right|=0.496$

${\rho }_3\left(S,S^{\prime }\right)=\left|0.015-0.5\right|=0.485$                  ${\rho }_4\left(S,S^{\prime }\right)=\left|0.02-0.5\right|=0.48$

${\rho }_5\left(S,S^{\prime }\right)=\left|0.025-0.5\right|=0.475$                  ${\rho }_6\left(S,S^{\prime }\right)=\left|0.035-0.5\right|=0.465$

${\rho }_7\left(S,S^{\prime }\right)=\left|0.045-0.5\right|=0.455$                  ${\rho }_8\left(S,S^{\prime }\right)=\left|0.055-0.5\right|=0.445$

${\rho }_9\left(S,S^{\prime }\right)=\left|0.07-0.5\right|=0.43$                     ${\rho }_{10}\left(S,S^{\prime }\right)=\left|0.09-0.5\right|=0.41$

${\rho }_{11}\left(S,S^{\prime }\right)=\left|0.12-0.5\right|=0.38$                    ${\rho }_{12}\left(S,S^{\prime }\right)=\left|0.16-0.5\right|=0.34$

${\rho }_{13}\left(S,S^{\prime }\right)=\left|0.2-0.5\right|=0.3$                       ${\rho }_{14}\left(S,S^{\prime }\right)=\left|0.24-0.5\right|=0.26$

${\rho }_{15}\left(S,S^{\prime }\right)=\left|0.29-0.5\right|=0.21$                   ${\rho }_{16}\left(S,S^{\prime }\right)=\left|0.32-0.5\right|=0.18$

${\rho }_{17}\left(S,S^{\prime }\right)=\left|0.36-0.5\right|=0.14$                   ${\rho }_{18}\left(S,S^{\prime }\right)=\left|0.46-0.5\right|=0.04$

${\rho }_{19}\left(S,S^{\prime }\right)=\left|0.57-0.5\right|=0.07$                   ${\rho }_{20}\left(S,S^{\prime }\right)=\left|0.59-0.5\right|=0.09$

${\rho }_{21}\left(S,S^{\prime }\right)=\left|0.61-0.5\right|=0.11$                   ${\rho }_{22}\left(S,S^{\prime }\right)=\left|0.63-0.5\right|=0.13$

${\rho }_{23}\left(S,S^{\prime }\right)=\left|0.64-0.5\right|=0.14$                   ${\rho }_{24}\left(S,S^{\prime }\right)=\left|0.68-0.5\right|=0.18$

${\rho }_{25}\left(S,S^{\prime }\right)=\left|1.3-0.5\right|=0.8$

$G_1\left(S,S^{\prime }\right)=\frac{1}{0.499+1}=0.6671$                    $G_2\left(S,S^{\prime }\right)=\frac{1}{0.496+1}=0.6684$

$G_3\left(S,S^{\prime }\right)=\frac{1}{0.485+1}=0.6734$                    $G_4\left(S,S^{\prime }\right)=\frac{1}{0.48+1}=0.67567$

$G_5\left(S,S^{\prime }\right)=\frac{1}{0.475+1}=0.67796$                  $G_6\left(S,S^{\prime }\right)=\frac{1}{0.465+1}=0.68259$

$G_7\left(S,S^{\prime }\right)=\frac{1}{0.455+1}=0.68728$                  $G_8\left(S,S^{\prime }\right)=\frac{1}{0.445+1}=0.69204$

$G_9\left(S,S^{\prime }\right)=\frac{1}{0.43+1}=0.6993$                     $G_{10}\left(S,S^{\prime }\right)=\frac{1}{0.41+1}=0.7092$

$G_{11}\left(S,S^{\prime }\right)=\frac{1}{0.38+1}=0.7246$                    $G_{12}\left(S,S^{\prime }\right)=\frac{1}{0.34+1}=0.7462$

$G_{13}\left(S,S^{\prime }\right)=\frac{1}{0.3+1}=0.79365$                    $G_{14}\left(S,S^{\prime }\right)=\frac{1}{0.26+1}=0.79365$

$G_{15}\left(S,S^{\prime }\right)=\frac{1}{0.21+1}=0.8264$                    $G_{16}\left(S,S^{\prime }\right)=\frac{1}{0.18+1}=0.8474$

$G_{17}\left(S,S^{\prime }\right)=\frac{1}{0.14+1}=0.87719$                  $G_{18}\left(S,S^{\prime }\right)=\frac{1}{0.04+1}=0.9615$

$G_{19}\left(S,S^{\prime }\right)=\frac{1}{0.07+1}=0.9345$                    $G_{20}\left(S,S^{\prime }\right)=\frac{1}{0.09+1}=0.9174$

$G_{21}\left(S,S^{\prime }\right)=\frac{1}{0.11+1}=0.9009$                    $G_{22}\left(S,S^{\prime }\right)=\frac{1}{0.13+1}=0.8849$

$G_{23}\left(S,S^{\prime }\right)=\frac{1}{0.14+1}=0.8772$                    $G_{24}\left(S,S^{\prime }\right)=\frac{1}{0.18+1}=0.84745$

$G_{25}\left(S,S^{\prime }\right)=\frac{1}{0.6+1}=0.625$

8. Conclusions

The solution to the problem of identifying objects in the IoT ecosystem of the Aral region was analyzed. The problem of constructing a correct algorithm with linear closure operators of a model for calculating estimates for identifying objects in the IoT ecosystem of the Aral region was considered.

Within the framework of the algebraic approach, several variants of linear combinations of recognition operators were constructed, the use of which gives the correct answer on the control material, and this was proven in the form of theorems.

An operator belonging to the linear closure of the model of the type of calculation of estimates was constructed, which was the sum of q operators of the model of calculation of estimates and was described by a set of numerical parameters $3·n·m·q$, where n was the number of specified characteristics, m was the number of reference objects, and q was the set of recognized objects. The completeness of the linear closure of this model was proven for all problems in which for each class there is at least one stationary pair $\left(u,v\right)$, and this correct algorithm A was written explicitly.

The results obtained in this article, namely the proven theorems, made it possible to construct correct algorithms on control material based on a combination of linear recognition operators.

The constructed correct recognition algorithms, which are the easiest to use, where there is no optimization procedure, made it possible to quickly solve the issues of identifying incoming information flows in the IoT ecosystem of the Aral region.