The problems of constructing an extreme recogniton operator in the framework of the model of recognition operators based on radial functions are considered in the context of features correlations. To solve the problem of nding the optimal value of parameters, a heuristic approach based on the successive application of local procedures for calculating parameter values at each stage is proposed. In order to assess the e ciency of the proposed method, an experimental study was carried out to solve a model problem generated from speci ed distribution parameters and the problem of recognizing a person by photo portraits. The analysis of the results of the conducted experimental research showed that the proposed method of determining parameters in the construction of recognition operators in conditions of features correlations allows to improve recognition accuracy in solving applied problems. In this case, the constructed extreme model of recognition operators signicantly reduces the number of computational operations when recognizing an unknown object.
Pattern recognition is one of the most intensively developing areas in the eld of computer science. This is due to the fact that the methods and algorithms for pattern recognition have become increasingly used in science, technology, Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org production and everyday life in recent years. Therefore, an increasing number of specialists pay attention to the problem of pattern recognition and the number of scienti c publications on this subject is constantly growing.
An analysis of existing literature sources on pattern recognition shows that the development of this direction is divided into two stages. The rst stage of development consisted of the projects of various technical devices or algorithms for solving speci c applications. The value of the developed methods is determined, rst of all, by the achieved experimental results. At the second stage, the transition from individual algorithms to the construction of models - families of algorithms for a single description of methods for solving classi cation problems was carried out. At this stage, the recognition problem was formulated as an optimization problem, which allowed using the known optimization methods and stimulated the appearance of new methods, in particular [1{3].
Several well-known models of recognition algorithms have been constructed and studied up to now [1, 4{8]: models based on the principle of separation; statistical models; models based on the potential principle; models based on mathematical logic; models based on the calculation of estimates. However, analysis of these models shows that currently the models of recognition algorithms, oriented to solving problems, where objects are described in the space of independent (or weakly dependent) features, are mainly being developed. In practice, often there are applied problems of recognizing of objects de ned in the large dimensional feature space. When solving such problems, the assumption of the independence of features is often not ful lled [9]. Consequently, there remains an insu ciently resolved issue related to the creation of recognizing algorithms that can be applied to solving applied problems of diagnosing, forecasting and classifying objects in conditions of large dimensions of the feature space and correlated features.
In [10], a model of recognition operators based on the evaluation of the features correlations in conditions of features correlations was described. The main idea of this model is to nd correlations between the features characterizing objects belonging to the same class. We note that in [10] the problem of constructing an extreme recognition operator is not considered.
For completeness of the presentation, we brie y consider the above-mentioned model, determined by specifying seven steps: 1) extracting the subset of strongly correlated features: 2) forming of the set of representative features:
GB = nT1; T2; : : : ; Tn0 o;
RX = nxi1 ; : : : ; xiq ; : : : ; xin0 o;
(
M = nFi1 ; : : : ; Fiq ; : : : ; Fin0 o;
(
6) determining the proximity function between the object S and the objects of the class Kj (j = 1; l).
We have de ned a model of recognition operators of the type of potential functions based on the evaluation of the features correlations. An arbitrary operator B from this model is completely determined by specifying the set of parameters ~ [11]: ~ =
n0; fw~g; fcg; f!~g; f ig; f ig; f ug :
It is known [4] that an arbitrary recognition algorithm A can be represented as a sequential execution of the operators B (recognition operator) and C (decision rule):
A = B
C:
It follows from (
The aim of this paper is to solve the problems related to calculating the
values of the parameters (
The formal description of the problem of determining the parameters ~ is as
follows.
(
A model of recognition operators based on the potential principle is given. Any operator B from this model is completely determined by specifying the set of parameters ~ =
n0; fw~g; fcg; f!~g; f ig; f ig; f ug . We denote the set of all recognition operators from the proposed model by B(~; S). Then the problem of constructing extreme recognizing operators based on the potential principle can be formulated as the problem of nding the extreme operator B(~ ; S) among the recognizing operators B(~; S). Here ~ is a vector of con gurable parameters; ~ is the vector of optimal parameters. The recognition quality criterion is given in the form 'A(~) = 1 m
X K k ~(Sj ) m j=1
A(~; Sj )kB ;
(
Then the problem of constructing extreme recognition operators consists in
nding the optimal value of the components of the vector-parameter ~ for a
given model of recognizing operators ensuring the ful llment of the following
condition:
~ = arg min 'A(~):
~
(
Thus, the problem of determining parameters in the construction of extreme
recognition operators is reduced to the optimization problem (
For solving the formulated problem, it is reduced to nding the optimal values
of the parameters at each stage. After each iteration, the value of the quality
functional (
The Procedure for Determining Subsets of Strongly Correlated Features Let Tq (q = 1; n0) be subset of strongly correlated features. The proximity measure L Tp; Tq between the subsets Tp and Tq can be given in various ways, for example:
L Tp; Tq = where dk(xi; xj ) a proximity measure between the features xi and xj over the k-th object.
Determining of GB = nT1; T2; : : : ; Tn0 o is carried out as follows.
Step 1. The rst step assumes that each subset contains only one element. In this case we have the following n subsets:
T1 = fx1g; T2 = fx2g; : : : ; Tn = fxng
(N1 = N2 = : : : = Nn = 1):
(
We de ne the initial link matrix kLi1j k as Li1j = bij [12]. Next, we consider the execution of an arbitrary u-th step (k > 1).
Step u. We suppose that u0 subsets T1; : : : ; Tn0 are de ned and the link matrix kLi(ju 1)ku0 u0 is constructed at the step (u 1), where u0 = n u + 1.
Then at the u-th step the following operations are performed: 1) combining of Tp Tq into one subset, if
L(Tp; Tq) = maxkLi(ju 1)ku0 u0 ; where i; j 2 [1; 2; : : : ; u0] and i 6= j;
(
The process of combining features continues until n0 subsets (n0 - some given number), i.e. n0 independent subsets of the features T1; T2; : : : ; Tn0 , where each feature is strongly correlated in its subset, are obtained. 3.2
The Procedure for Determining a Representative Feature in each Subset of Strongly Correlated Features At this stage, di erent methods can be used to select uncorrelated (representative) features from a subset of strongly correlated features. The main idea of choosing is to allocate the most "independent" (or weakly dependent) set of features.
Let Tq (q = 1; n0) be subsets of strongly correlated features. It is assumed that Nq is the number of elements (power) of these subsets:
Nq = card(Tq);
(q = 1; n0):
(
Then the procedure of this stage can be described as follows. In the beginning it is assumed that u = 0.
Step 1. Selection as a representative feature of the isolated elements of the subset Tq, which di er sharply from other features. At this step, the following actions are performed:
- the value of u increases by one and the condition u > n0 is checked. If this condition is met, then the algorithm stops;
- if Nq = 1, then the element belonging to the subset Tq refers to the number of representative features, and the transition to the previous action is performed.
Step 2. Selecting a representative feature when a subset of strongly correlated features contains more than two elements, i.e. under the condition Nq > 2, the following sequence of operations is performed for all elements of Tq, except for the element under consideration: - for each element Tq, the proximity of each element to other elements of a given subset of features is calculated i 1 i = X (xi; xj ) + j=1
m (xi; xj ) = X
Nq X j=i+1
(xi; xj ); - an element of the subset Tq, that is closest to other elements is determined j =
max i2[1;:::;Nq] i ; - the feature xj is selected as a representative feature.
Step 3. When Nq = 2, the following actions are performed: - for each element Tq, the proximity estimate for the representative elements of the other subsets that were selected at the previous selection stages is calculated:
N0 i = X (xi; xj ); i = 1; 2; : : : ; ; j=1 where {number of subsets that consist of two elements. N0 is the number of isolated elements and elements selected from subsets with a power of more than two;
- element of the subset Tq, which is signi cantly di erent from other selected
representative features, is determined:
Let xiq be a representative feature belonging to the set Tq. The correlation
models between the features xiq and xi (xiq 2 Tq, xi 2 Tqnxiq ) are de ned for
each class Kj in the form
xi = Fj c; xiq ;
xi 2
qnxiq ;
(
For the sake of simplicity, it is assumed that the set fF g consists of only the linear models. It is assumed that the feature xiq (xiq 2 Iq is an independent variable, and the feature xi xi 2 Tqnxiq model of correlation takes the form is a dependent variable. Then the
xi = c1xiq + c0;
(
To determine the numerical values of these parameters, we use the least square method [13]. 3.4
The Procedure for Identifying Preferred Correlation Models Let J0 { be training set, E1 { set of objects belonging to the class Kj : E1 = J0 \ Kj , and E2 { set of objects not belonging to the class Kj : E2 = J0nE1. We consider the procedure for identifying an important (presumed) model of correlation on the basis of estimating the dominance of the models under consideration [10]:
Ti =
Di i ; Here Di { a selective error calculated for objects not belonging to the subset K~j : i { the selective variance of the error calculated for objects belonging to the subset K~i:
Di = i = 1 1 card(E2) S2E2
X j i(S)j; card(E1) S2E1
X j i(S)j; i(S) = yi(S)
Fj c; xiq (S) ; 1) values of Ti i = 1; (Nq conducted as follows: where xiq (S) { representative feature q-th subset (xiq 2 Iq) of the object S; yi { an arbitrary feature of the same object, except for the representative one (yi 2 Tqnxiq ).
On the basis of formula (
Repeating this procedure for all n00 subsets, we get a set of preferred correlation models for the class Kj . It is assumed that Nq > 1. Otherwise, the number of preferred models decreases as much as the number of subsets has only one element.
n00 dq(Kj ; S) = X q=1 jai
Fj (c; aq)j; where ai, aq the value of the i-th and iq-th feature, corresponding to the object S. It is assumed that the feature xi (i 6= iq) belongs to a subset of strongly correlated features { Rq; aq { the value of the basic (representative) feature xiq (xiq 2 Rq).
We consider the problem of constructing a function characterizing the quantitative estimation of the di erence between the objects Su and Sv in the subspace of strongly correlated features.
Let an admissible object in the subspace of strongly correlated features Jq (Jq = ( iq ; 1; : : : ; q0 ), q0 = card(Jq) 1) be given:
The Procedure for Determining the Di erence Function
between the Object Su and the Objects of the Class Kj
With the help of this procedure, di erence function that characterizes the
quantitative measure of the remoteness of the object S from the source of the potential
is de ned. In this case, the source of the potential is given as the model of the
correlation (
The di erence function dq(Kj ; S) between objects of class Kj and object S in Rq can be de ned as follows:
l Rq1 = X j=1 1 mj
! X dq(Kj ; S) ; S2K~j
l Rq2 = X j=1
1 m mj
X The di erence between this object and the class Kj is de ned as follows:
S = (aiq ; a1; : : : ; aq0 ): d(Kj ; S) = n00 X gqdq(Kj ; S); q=1 where gq recognition operator parameter (q = 1; n00). The set of these parameters forms a vector g~ = (g1; : : : ; gq; : : : ; gn00 ).
The problem is to determine the values of the unknown parameters fgqg (q = 1; n00) of the di erence function (26) over a given set of objects S~m.
For this problem, we introduce a functional that characterizes the importance of dq(Kj ; S): n00
P gqRq1 R(g~) = q=1 n00 P gqRq2 q=1 (26) (27) (28) (29)
Taking into account the imposed restrictions on the components of the vector, we can formulate the problem of determining g as follows
To nd the values of the vector g we construct a Lagrange function of the form:
By summing (34) over each derivative of gi, we nd the value
Without loss of generality, we introduce restrictions on the coe cients (g1; : : : ; gq; : : : ; gn00 ) in the form (31) (32) (33) (34) (35) (36) By substituting in (34), we compute the value gi (i = 1; n00: n00
P = i=1
R1
i n00 P giRi2 i=1
R2 i !2 : gi = n00 P i=1
R1 i
R2
i R2 i
R2 i :
Thus, by repeating the calculation process for all features, the di erence function is determined.
The Procedure for Determining the Proximity Function between the Object Su and the Objects of the Class Kj Let the proximity function between the objects Su and S be given as potential functions of the second type [14]: f ( ; d(Kj ; S)) =
1 1 + d(Kj ; S)
The main tasks in constructing the proximity function between objects on the basis of a potential function is to determine the value of the smoothing parameter . However, the search for the optimal value of this parameter in the creation of a potential function has not been studied enough, and for each speci c case, elements of search and creativity are contained in nding [15, 16]. The authors of [15] assert that, depending on , the resolving power of the potential function is located. So, as increases, fast decay of the potential function occurs by moving away from objects of the given class, which leads to the creation of a "relief" peaked above the "top" of this image. A decrease in results not only to smoothing out the peaks, but also to the leveling the "heights" of images of di erent classes, which makes recognition di cult and leads to a large number of vague and erroneous solutions.
To calculate the smoothing parameter of a potential function, the approach, the idea of which is borrowed from [16], is used.
For the sake of simplicity, we introduce some restrictions (ie. we consider the problem for only two classes) and the notations: = arg max R( );
Su2S~m R( ) = faug; bmax = bum2[1a;xN0]fbug; (37) (38) (39) (40) (41) (42) S~m = K~1 [ K~2; K~1 \ K~2 = ?; K~1 6= ?; K~2 6= ?; d(K~j ; S) = au; if Pj (S) = 1; bu; if Pj (S) = 0; where au - measure of the di erence between the object S and the objects of the class K~j , when S belongs to the class K~j (au > 0); bu is the measure of the di erence between the object S and the objects of the class K~j , when S does not belong to the class K~j (bu > 0).
Then the problem of determining the smoothing parameter is formulated as follows:
M0 = 0:5(m1(m1 1) + m2(m2 1)); N0 = m1
m2; m1 = card(K~j ); m2 = m m1: (44) (45)
To solve problem (
Thus, with the application of the proposed procedures, the values of all parameters of the considered model of recognition operators are determined. To assess the operability of the heuristic approach examined, experimental studies were conducted. 4
An experimental study of the e ciency of the proposed approach in the construction of recognition operators was carried out on the example of solving a number of problems, in particular, the model problem, the problem of person identi cation by the geometrical features of a photo portrait and the problem of diagnosing cotton diseases from leaf images.
As test models of recognition operators, the following were chosen: the classical model of recognition operators of the type of potential functions (B1), the model of recognition operators based on the calculation of estimates (B2), and the model of recognition operators based on the evaluation of the features correlations (B3) [10].
A comparative analysis of the above mentioned models of recognition operators in solving problems was carried out according to the following criteria: accuracy of recognition of test sample objects; time spent on training; time spent on recognizing objects from the test sample.
To calculate the above criteria in order to exclude the successful (or unsuccessful) partitioning of the initial sample B to Bo and Bk sets (B = B0 [ Bk, B0 is the training sample, Bk is the test sample), the cross-validation method was used [18]. The experiments were carried out on a Pentium IV Dual Core 2.2 GHz computer with 1 Gb of RAM. 4.1
Model Problem The initial data of the recognized objects for the model problem are generated in the space of the correlated features. The number of classes in this experiment is equal to two. The volume of the initial sample is 1000 implementations (500 implementations for objects of each class). The number of features in the model example is 200. The number of subsets of strongly correlated features is 5.
The Problem of Person Identi cation The initial data used for the problem of person identi cation by the geometric features of a photo portrait consist of 360 portraits. The number of classes in this experiment is equal to six. Each photo portrait is characterized by the corresponding parameters (see Fig. 1): the distance between the center of the retina of the left eye and the center of the tip of the nose; distance between the center of the retina of the left eye and the center of the oral opening; distance between the center of the retina of the right eye and the point of the tip of the nose; distance between the centers of the retina of the eyes, etc.
There are 60 di erent one-person portraits photographed at di erent times, but with the same shooting conditions in each class. To distinguish these parameters, we used the algorithm for searching for characteristic features of the face, described in [19{21]. 4.3
The Problem of Diagnosis of Cotton Diseases The initial data used in the problem of diagnosing cotton diseases from leaf images consist of 200 images. The number of classes in this experiment is equal to two: - images of cotton leaves, sick with wilt (K1); - images of cotton leaves without wilt (K2).
The number of images in each class is the same and is equal to 100. To extract the features characterizing the phytosanitary state of cotton by the original image of the leaves, we used the algorithm described in [22].
As mentioned earlier, all tasks were solved using the recognition operators B1, B2 and B3.
Fig. 2,a shows the training speed of the recognition model on the training sample of the problems under consideration, and Fig. 2,b shows the speed of recognition of objects. The results of solving the problems under consideration with the use of B1, B2 and B3 during the test are shown in Fig. 2,c.
A comparison of these results shows (see Fig.2) that the model of recognition operators B3 allowed to increase the accuracy of recognition of objects described in the space of correlated features (more than 6-10% higher than B1 and B2). This is because the models B1 and B2 do not take into account the features correlations. However, for model B3, there is some increase in training time, which requires further investigation.
The developed procedures are oriented to determine unknown parameters within the model of recognition operators, which di er from traditional recognition operators such as potential functions in that they are based on the evaluation of the features correlations. Therefore, it is advisable to use these procedures in those cases when there is some correlation between the features. Undoubtedly, this correlation should be di erent for objects of each class. This allows to describe the objects of each class with an individual model. If the relationship between the features is weak, then the classical model of recognition operators is used (for example, the model considered in [4, 1, 5]). Consequently, the models of recognition operators considered in [10] are not an alternative to models of recognition operators of the type of potential functions, but only complement them.
In the case when a su ciently strong correlation is found between the features of all the objects under consideration, then in the process of forming a set of representative features (described in the rst and second stages of specifying the model), the features repeating the same information are excluded, which ensures the selection of features that are su ciently representative of all those features that are not contained in the given set [10].
The results of the conducted experimental research show that the proposed optimization procedures for constructing extreme recognition operators allows to solve the problem of pattern recognition more accurately in conditions of features correlations. 7
Procedures for constructing an extreme recognition operator based on potential functions are proposed in the context of features correlations. These procedures allow to expand the scope of application of recognition operators based on potential functions.
The results of solving a number of problems have shown that the proposed procedures for determining parameters in the construction of an extreme recognition operator improve accuracy and signi cantly reduce the number of computational operations by recognizing an unknown object given in the space of correlated features.
Acknowledgement. The work was carried out with partial nancial support of the grant BV-M-F4-003 of the State Committee for the Coordination of the Development of Science and Technology of the Republic of Uzbekistan.