In this paper, the problem of the quality of the product of metallurgical production is investigated in the conditions when the reassignment can be organized in the process of realization of a specific technological route. The information on the completed technological routes forms a training sample for the pattern recognition problem with the teacher and the choice of the technological route for the continuation of the production process is carried out taking into account the expected quality indicators of the final product. To reduce the dimensionality of the problem, a given set of executed technological routes is divided into discrete classes, in each of which an algorithm for constructing a decision tree can be implemented. The paper gives a formal description of the developed algorithm for the node of the decision tree and an example of implementation.
In this paper, we present an algorithm for solving the problem of pattern recognition in a geometric formulation, the implementation of which determines the classification of the expected products. The algorithm is based on the principles of constructing logical decision trees and reducing the dimension of the problem by preliminary clustering the source data space. 1
Let A = {A1; : : : ; An} be the set of technological aggregates involved in production.
De nition 1.1 The directed graph −→G = (A; E) with the set of vertices A and the set of arcs E ⊆ A2 is called the infrastructural graph if (A1; A2) ∈ E if and only if the output EP of the aggregate A1 can serve as the input EP for the aggregate A2.
De ntion 1.2 The technological route P = (Ai1 ; Ai2 ; : : : ; Aik ) is any directed path in →−G .
The set of all technological routes P = {P1; : : : ; Pk} is the technological base of the production under consideration. We denote by EP = {ep1; : : : ; epn} the set of all possible product units of production under consideration.
Let each product unit epi be characterized by a set of parameters Pi = {pi1; pi2; : : : ; pini }; i ∈ [1; K]. De nition 1.3 Sequence
AIi = (Ai1; Pi1 (AIi) ; : : : ; Ais; Pis (AIi) ); where Pij (AIi) is the set of parameter values for epij in a particular implementation of the technological route AIi, is called the executed technological route (ETR).
As a result of the production activity of the production under consideration, the set of executed technological routes will be generated at the current time moment t:
PETR(t) = {AIi : i ∈ [1; q(t)]}: (1) De nition 1.4 The terminal vertex of a graph (subgraph) is a vertex from which no arc leaves in this graph (subgraph).
Let V ′ be the set of terminal vertices of the subgraph ⟨v ∪ −→G (v) ∪ −→G 2(v) ∪ · · · ∪ −→Gk(v)⟩→−G . Here −→G k(v) denotes the set of all vertices v′of −→G such that there exists a simple path from the vertex v to the vertex v′ of the length (k − 1). For each terminal vertex vi ∈ V ′ there is a certain output unit epi, which is the output EP for this vertex, and there may be several such epi depending on the type of ETR as a result of which this product unit was received.
De nition 1.5 An ETR is called a productive ETR if the output EP of the terminal vertex Ais of this ETR AIi | denote this vertex as term(AIi) | is one of the types of the nal product delivered to the market. De nition 1.6 The vertex v′ ∈ v ∪ −→G(v) ∪ : : : ∪ −→Gk(v))is called a fork-vertex if −→G (v′) > 1.
(
In the framework of this paper, the generalized problem of assigning a technological route is considered, in which it is supposed that it is possible to control the choice of the further passage to processing a product unit in the fork-vertices of the graph −→G. This means that the technological route in the process of its execution can be reassigned in order to increase production efficiency and reduce the level of rejection. 2
Consider the set (1) of all productive ETRs. For each productive ETR AIi you can define two parameters for EP of its terminal vertex epi = ep (term (AIi)): Price(epi) is the market price of the unit of measure epi, C(epi) is the production cost of the product unit epi.
Let there be a set of productive ETRs such that the initial sections to the fork-vertex are coincident in the part of the passage of aggregates. Then each productive ETR can be represented as a sequence:
AIi = (BIi; CIi) ; i ∈ [1; q (t)] ; where BIi is the ETR from the initial vertex v1 to the considered fork-vertex v′ and CIi — ETR from the vertex v′ to the terminal vertex term (AIi). Since each ETR AIi passages a certain technological route — we denote such route as P (AIi) — then the set of all ETRs can be divided into several classes
PETR (v; t) = PE(1T)R (v; t) ∪ PE(2T)R (v; t) ∪ : : : ∪ PE(lT)R (v; t) (2) such as AIi and AIj belong to the same class if and only if P (AIi) = P (AIj ).
We denote by Pi = P (PE(iT)R (v; t)) a technological route which is common for all ETRs from PE(iT)R (v; t). Then the problem is to determine which of the technological routes Pi should be chosen for further passage when reaching the fork-vertex v′.
For each class PE(iT)R (v; t) from (2) we compile a training sample
( Z (Pi) :
Ef (AIj ) =
Price(term (AIj ) )− C(term (AIj ) )
C(term (AIj ) )
) ; i ; BIj ; (3) where AIj ∈ PE(iT)R (v; t), and separate the set of values of efficiency Ef (AIj ) into several discrete intervals E1; E2; : : : ; Em.
Next, we represent the sample Z (Pi) in the form of the corresponding multidimensional vectors aj = (aj0; aj1; ajm1 ; : : : ; ajn); where aj0 ∈ {E1; : : : ; Em} is the value of the ETR’s efficiency, aj1 is the identifier of the technological route of this ETR. We assign the vector aj = (aj1; : : : ; ajn) to the class Ki, if aj0 ∈ Ei. Then each aj vector will be assigned to one of the classes K1; : : : ; Km and the well-known problem of pattern recognition in geometric formulation arises. 3
A = {(ai1 ; : : : ; ain ) : i ∈ [1; N ] } ;
A = A1 ∪ A2 ∪ : : : ∪ Am : It is required to construct a decision rule for assigning the vector ai to one of the classes. The solution will be sought in the class of logical decision trees given by a directed binary tree →−G = (V; E) with root vertex v0 ∈ V .
The binary tree −→G = (V; E) defines the process of sequentially separating of the sample A into two subsamples at the vertices of degree 2 so that each terminal vertex vi corresponds to a subset Avi ⊆ A, which can be assigned to one of the classes classvi ∈ [1; m]. In the case under consideration, linear functions will be used to separate the subsample at each vertex of the decision tree.
If v is a vertex of degree 2 in the graph −→G, then a vector nv and a scalar variable Ev are given for it, such that Av is separated into two subsamples of A′v and A′v′ according to the following rule:
A′v = {ai ∈ Av : ⟨nv ; ai⟩ 6 Ev} ; A′v′ = {ai ∈ Av : ⟨nv ; ai⟩ > Ev} ;
Av0 = A : and for the root-vertex v0 we have:
It is required to construct the decision tree −→G = (V; E) with minimal number of vertices, and at each terminal vertex v ∈ V we have: p (v) = {ai ∈ Av : ai ∈ classv} |Av| > pmin ; (4) that is, the fraction of vectors belonging to the some class classv is not less than a given value pmin. If pmin = 1 then each terminal vertex corresponds to the vectors of one particular class.
The rule (4) acts if |Av| > Kmin. If |Av| < Kmin then the process of further separating of the sample Av is not performed and the vertex v is declared terminal, and the (4) rule may not be executed. In other words, for |Av| < Kmin the sample Av is not representative enough for constructing a further decision rule and the probability p (v) of the vector from this sample belongs to the class classv can be less than pmin. 3.1
Algorithm for Constructing the Decision Function for the Node Suppose that we have a vertex v ∈ V for which Av is given. Suppose we have a partition
Av = (Av ∩ A1) ∪ : : : : : : ∪ (Av ∩ Am) ; (5) in which there are m′ non-empty sets. If m′ = 1 then the vertex v is terminal and p (v) = 1, if 2 6 m′ 6 m then sequentially calculate the values: pi (v) = {ai ∈ Av ∩ Ai} |Av| ; i ∈ [1; m] :
If there exists i0 ∈ [1; m] such that pi0 (v) > pmin then the vertex v is terminal and the class classv = i0, if |Av| < Kmin then the vertex v is terminal and classv = arg max { pi (v) : i ∈ [1; m′] } :
i 2 6 m′ 6 m ;
|Av| > Kmin ; pi (v) < pmin ∀ i ∈ [1; m′] ; I = {i : Av ∩ Ai ̸= ∅ ; i ∈ [1; m]} : Av1 = {aj ∈ Av : ⟨nv ; aj ⟩ 6 Ev} ;
Av2 = {aj ∈ Av : ⟨nv ; aj ⟩ > Ev} : p (Av1 ) = p (Av2 ) = ( |Av1 ∩ A1| ; : : : ; |Av1 ∩ An| ) ;
|Av1 | |Av1 | ( |Av2 ∩ A1| ; : : : ; |Av2 ∩ An| ) :
|Av2 | |Av2 |
Let some vector nv and a scalar value Ev be assigned. Then the vertex v is associated with two vertices v1 and v2 that are descendants of the vertex v in the constructed decision tree such that: In this case the vector nv and the quantity Ev require the sets Av1 ̸= ∅ and Av2 ̸= ∅.
Consider the following value discrim (Av ; nv ; Ev) = ∑ i ∈ I |Av1 ∩ Ai| |Av1 | − |Av2 ∩ Ai| : |Av2 | The value discrim (Av ; nv ; Ev) will be called the separating force of the function concerning the subsample Av. The meaning of this notion is that the stronger the vectors from the classes Ai of the training sample are separated in the half-space obtained by dividing the space by a hyperplane f (a) = a · nv − Ev f (a) = a · nv − Ev = 0 ; the more the function f (a) separates vectors from the training sample into classes. Thus, the formulation is natural, where it is required to find nv ∈ Rn+1 and Ev ∈ R for the sample (5) such that the value of quantity discrim (Av; nv; Ev) reaches its maximum. The naturalness of such formulation is also confirmed by the fact that for m = 2 the best solution is achieved for discrim (Av; nv; Ev) = 2 , which corresponds to a linear separation into classes Av ∩ A1 and Av ∩ A2 by the hyperplane f (a) = nv · a − E = 0. The problem in this formulation always has a solution, since Av1 ̸= ∅ and Av2 ̸= ∅ for each vertex v its descendants correspond to subsamples of lower power and when the condition (4) or the condition |Av| < Kmin are reached the vertex v becomes terminal.
For an arbitrary subset A′ ⊆ A we introduce the notation for the center of the subsample 1 |A′| i∈A′ C (A′) =
∑ {ai : ai ∈ A′} ; A (I) = {ai : ai ∈ A; i ∈ I} :
C (I2) − C (I1) ∥C (I2) − C (I1) ∥
; ∥C (I2) − C (I1) ∥ :
M and Let be given the partition I = I1 ∪ I2, where I1 ̸= ∅; I2 ̸= ∅. Consider the interval [C (I1) ; C (I2)] ⊂ Let n (I1; I2) be the normal vector Rn+1. then we divide the interval [C (I1) ; C (I2)] into M parts, where the length of each part is We consider the (M − 1) separating functions fj (a) = a · nv − Ej , which are passing sequential through all (M − 1) dividing points of the interval [C (I1) ; C (I2)]. We will search the best option for the separating force among these functions:
j0 = arg max {discrim (Av; nv; Ej ) : j ∈ [1; N − 1]} : It is easy to see that for j0 we have Av1 ̸= ∅; Av2 ̸= ∅.
We denote by
discrim (I1; I2) = discrim (Av; nv; Ej0 ) : In the case of C (A (I1)) = C (A (I2)) any two most distant points from the sample Av are choosed and for the interval which connects these points it is used the same procedure for constructing (M − 1) separating planes and choosing the best of them. In the general case it is assumed that all partitions of the form I = I1 ∪ I2 are searched, and the chosen partition is such that discrim (I1; I2) reaches its maximum. In practical implementation instead of a search a sequential algorithm can be used, in which I1 = I; I2 = ∅ is initially assigned. Further among all partitions of the form I = I1 \ {i} ∪ I2 ∪ {i}, where i ∈ I, the best is chosen by the criterion discrim (I1; I2) and so on. In the end, the best result is also chosen from the entire row obtained.
The algorithm of decision tree constructing for the node: 1. Let us consider the node v of decision tree with training sample Av. 2. The vertex v is declared terminal if there exists a class i ∈ [1; m] such that pi (Av) > pmin or |Av| 6 Kmin. 3. We consider all partitions I = I1 ∪ I2.
|I1| i∈I1 CI1 = ∑ Ci CI2 =
∑ Ci : 1 |I2| i∈I2 5. If the length of the interval [CI1 ; CI2 ] ̸= 0 then the normal vector nI1;I2 is constructed and the sample EI1;I2 such that discrim (Av; nI1;I2 ; EI1;I2 ) is maximal (search through all hyperplanes perpendicular to nI1;I2 and bypassing [CI1 ; CI2 ] for M steps from the point CI1 to the point CI2 ).
The process is finite since some separation takes place at the each step.
Example 3.1 Consider an example in which four classes of vectors are given, and each class contains 20 vectors.
Consider the partition I = I1 ∪ I2 and denote by
a (I1; I2) = ∑ {(as − at) : as ∈ Av ∩ Ii ∀ i ∈ I1; at ∈ Av ∩ Ij ∀ j ∈ I2} : The most practical efficiently seems the algorithm for separating the sample Av in the vertex v which choices the partition I = I1 ∪ I2, for which |a (I1; I2) | is maximal among all partitions I = I1 ∪ I2. Then the choice of the vector n (I1; I2) and the scalar value E (I1; I2) can be made according to the procedure described above for the obtained fixed partition I = I1 ∪ I2.
then for I = I1 ∪ I2 we have aij = ∑ {(as − at) : as ∈ Ai; at ∈ Aj } ; i; j ∈ [1; m] ; a (I1; I2) = ∑ {aij : i ∈ I1; j ∈ I2} : (6) Proceeding from the relation (6) it is possible to significantly reduce the amount of computation when choosing the optimal partition I = I1 ∪ I2 for the sample Av using the previously calculated values aij ∀ i; j ∈ I.
To solve the problem of the quality of the product of metallurgical production, an approach has been developed in which the research is reduced to solving the problem of pattern recognition in a geometric formulation. A heuristic algorithm for constructing a decision rule is developed which is aiming to find the best possible discrimination of training sample corresponding to each vertex of decision tree. Substantial reducing of the computational complexity of considerated algorithm is proposed. Thus, for the production under consideration, a large number of problems of pattern recognition are constructed for each of which a decision tree is constructed.
An important feature of the approach is that the set P(t) of ETRs is continuously expanding, thus providing all the new data to improve the decision rule. To achieve the effectiveness of the proposed approach in practice it is necessary to carry out additional training as soon as a new portion of the ETRs arrives. This will ensure the continuous improvement of the decision rules and consequently the improvement of production efficiency.