Introduction

One of the important problems of classification and clustering of information is the problem of minimizing the dimension of the space of features, the choice of criteria for optimal solutions in the processes of practical use. Such problems are effectively solved by the method of multidimensional scaling of empirical data on the proximity of objects, with the help of which the dimension of the measured objects essential characteristics space is determined and the configuration of points -objects in this space -is constructed. This space is a multidimensional scale, similar to the commonly used scales in various applications in the sense that the values of the specially generated essential characteristics of the measured objects correspond to certain positions on the axes of the new space [1]- [5].

The purpose of this work is the development of mathematical methods for the synthesis of systems for solving problems of classification and clustering based on information about the characteristic features of objects [6]- [10]. These problems are proposed to be solved by constructing hyperplanes in a space derived from the original space of features using theory of perturbation of pseudo-inverse and projection matrices and solving systems of linear algebraic equations. The paper proposes a method for synthesizing a piecewise hyperplane cluster to isolate the most effective characteristic features and an algorithm for constructing piecewise hyperplane clusters that allow you to find an effective solution to the problems. The performance and efficiency of the proposed approach is shown on the example of the scaling of characteristic features for recognizing the letters of the fingerprint alphabet of the sign language [8], [9], [11].

Related works

The problem of synthesis of a piecewise hyperplane cluster for a training sample of vectors

{ } n j E j x x m , 1 , ) ( : 0 = ∈ = Ω

, where

) ( , ), 1 ( n x x 

-vectors from the Euclidean space of features m E is to build a cluster so that the training sample points in this space are located quite close, in the sense of a given distance criterion, to some set of hyperplanes that are formed according to this sample.

Note that in the formulation of this problem for clustering of information, the components of the set of hyperplanes are not known in advance. Therefore, for the correct construction of piecewise hyperplane clustering procedures, it is assumed that vectors

) ( , ), 1 ( n x x  from the space of features m E can belong to one of several hyperplanes )), ( ), ( ( k b k A L where m s E k A × ∈ ) ( , s E k b ∈ ) ( , ,... 2 , 1 = k some given dimension s , ) ( m s < . Here ) (k A and ) (k b

are matrix and vector parameters, respectively, for a fixed hyperplane

)) ( ), ( ( k b k A L , ,... 2 , 1 = k .

The proposed method of a piecewise-hyperplane cluster synthesis is based on using the representation of hyperplanes by means of a set of solutions (pseudo solutions) of systems of algebraic equations.

) ( ) ( k b x k A = ,(1)= )) ( ), ( ( k b k A L } , )) ( ( ) ( ) ( : { m m E z z k A Z k b k A x E x ∈ + = ∈ = + .(2)

Here + A -pseudo inverse matrix, Z -projection matrix. Let us give some mathematical results on the inversion (pseudo inversion) of matrices and the construction of projection matrices, which are important for solving the problem of synthesizing a piecewise-hyperplane cluster.

Let the matrix be given

n j m i a A ij , 1 , 1 ), ( = = =

and we write down, which are important in further studies, the representations of this matrix in columns or rows, respectively:

, , 1 , ) ( )), ( ... ) 1 ( ( n j E j a n a a A m = ∈ =   ( ) m i E a a a A n T i T T m T , 1 , , ) ( ) ( ) 1 ( = ∈ =  ,

where T -transpose symbol.

We consider the singular decomposition of an arbitrary matrix A of dimension

n m × of rank ) , min( n m r ≤ in the form T i i r i i v u A ∑ = =1 λ

, where:

0 ... 2 2 1 > ≥ ≥ r λ λ

-non-zero eigenvalues of matrices

A A AA T T , ; r i E v n i , 1 , = ∈

-orthonormal set of eigenvectors of the matrix A A T , which correspond to non-zero eigenvalues

r i i , 1 , 2 = λ , , 2 i i i T v Av A λ = ij j T i v v r i δ = = , , 1 r i E u m i , 1 , = ∈

orthonormal set of eigenvectors of the matrix T AA , which also correspond to non-zero eigenvalues

r i i , 1 , 2 = λ , , 2 i i i T u u AA λ = , , , 1 ij j T u u r i i δ = = ij δ -Kronecker's symbol.

Let us give the definition of a pseudo inverse matrix in the Penrose optimization form [12]. For a matrix

n m E A × ∈ , a pseudo inverse matrix n m E A × + ∈

is defined by the relation:

) ( 2 . min arg b x m A x b A E b Ω ∈ + = ∈ ∀ Here 2 min ) ( b Ax Arg b n E x A − = Ω ∈ .

Also, using the singular representation of the matrix

n m E A × ∈

, the pseudo inverse matrix

m n E A × + ∈

can be represented as [13]:

1 1 − = + ∑ = j r j T j j u A λ ν .

Will consider important for practical application, matrices that are defined and calculated using matrices A и + A :

1) a projection matrix

∑ ≡ = = + r i T i i A A A P 1 ) ( ν ν

that is an orthogonal projector onto the subspace 3) matrix

∑ ≡ = = − Τ Τ + + r j j j j A A A R 1 2 ) ( ) ( λ ν ν .

Note the important properties of projection matrices P and Z :

, ) ( ) ( n I A Z A P = + , ) ( A A A P + = ∑ = = r i T i i v v A P 1 ) ( , ∑ = + = r r i T i i v v A Z 1 ) ( .

Note that the calculation of the pseudo inverse matrix for an arbitrary matrix can be reduced to the calculation of the corresponding to it some inverse matrix using the following relations:

+ + + = = ) ( ) ( T T T T AA A A A A A , T A A R A ) ( = + .

Using the above mathematical ratios for the inversion and pseudo inversion of matrices, we write the necessary formulas for the synthesis of a piecewise hyperplane cluster.

The distance ( )

) , ( ), ( b A L j x ρ from the point ) ( j x to the hyperplane ) , ( b A L will be found from the relation ( )2 2

)

) ( ( ) , ( ), ( j Ax b A b A L j x − = + ρ , x x x T = 2 .

To calculate the sum of the squares of the distances of the set of points

n j j x , 1 , ) ( = to the hyperplane ) , ( b A L

, we use the following formula:

{ } ( )= = ) , ( , , 1 ), ( : 2 b A L n j j x x ρ ( ) ( ) = − ∑ − = = ) ( ) ( ) ( 1 j Ax b A R j Ax b T T n j ( )( ) T n j T j Ax b j Ax b A R tr ) ( ) ( ) ( 1 − ∑ − = = .

Here () tr -matrix trace. Then, for given values

n j j x A , 1 ), ( , =

, the optimal value of the vector of the right-hand side of the system of equations determining the hyperplane is determined from the conditions { } ( )

. ) ( 1 , ) , ( , ,1

), ( : min arg

ˆ1 2 ∑ = = = = = = ∈ n j R b opt j x n x b A L n j j x x x A b S ρ

From here, the distance { } ( )

) , ( , , 1 ), ( : b A L n j j x x = ρ

of the set of points

n j j x , 1 , ) ( =

to the hyperplane, with an optimal vector opt b , is calculated by the following formula:

{ } ( ) , ) ( )) ( , ( , 1 2 1 T opt X X A trA A b A L ,n j x(j), x: + = = ρ where ), ) ( .. ) ) 1 ( ( ~n x x X   = , ) ( ) ( ~x j x j x − = n j , 1 = . The optimal matrix m s E A × ∈ defined as a solution of the problem { },., 1 ), ( : ( min arg 2, n j j x x A m s s T E A E AA opt = = × ∈ = ρ ( ) . ))) ( , (1T T m T s m opt u u A b A L  + − = Wherein ∑ = + − = + r s m j j T opt opt X X A trA 1 2 ~λ , m m T m I u u u u = ) , ,( ) , , ( 1 1  .

Using the above results on pseudo inversion of matrices and calculation of distances, a piecewise hyperplane clustering method is proposed. The idea of the method is to perform a sequence of steps, at each of which the parameters of the hyperplanes ,... , the performance efficiency criterion of hyperplane clustering is checked. If the efficiency criterion is satisfied, this means that the result of the construction of the piecewise hyperplane cluster is achieved by building the cluster with one hyperplane and those characteristic features are the optimal set. If the conditions of the efficiency criterion in the framework of this (first) hyperplane are not met, then the transition to the construction of the second hyperplane of the cluster is carried out. For this purpose, the vectors that determine the non-fulfillment of the efficiency criterion are excluded from the training sample, that is, a subset is formed

{ } 1 1 1 1 , 1 , ) ( : n j E j x x m = ∈ = Ω

. Then the actions on the optimal approximation of the subset 1 Ω by the hyperplane the fulfillment of the clustering efficiency criterion is checked. When the criterion is met, the result of the piecewise hyperplane cluster construction is reached, then the resulting vectors of characteristic features are added to the optimal set of features. When not performing -it is necessary to exclude from the training sample those vectors that cause to the non-fulfillment of the efficiency criterion and repeat the procedure. Note that this finite recurrent process will always ensure the construction of an optimal piecewise hyperplane cluster.

Algorithm of synthesis of the piecewise hyperplane cluster

Using the proposed method of synthesizing piecewise hyperplane clusters, the algorithm of such a synthesis can be represented as the following sequence of actions:

1. Formation of a single-link cluster (the number of a link in a cluster is an index in brackets):

1) All vectors of the training sample

{ } n j E j x x m , 1 , ) ( : ) 0 ( = ∈ = Ω

from the space of features are to be optimally approximated by a hyperplane

)) 1 ( ), 1 ( ( opt opt b A L

, which is defined as the set of solutions (pseudo-solutions) of systems of algebraic equations ( 1), (2), where

) (k A and ) (k b

are respectively the matrix and vector parameters of a certain hyperplane (basic formulas for constructing a hyperplane cluster are implemented).

2) To form a set

{ } 1 1 1 , 1 , ) ( : ) 1 ( n j E j x x m = ∈ = Ω of points ) 0 ( Ω for which the condition is satisfied, namely: , )) ( ) 1 ( ) 1 ( ( )) 1 ( ( )) ( ) 1 ( ) 1 ( ( min 1 1 1 1 1 1 1 h j x A b A R j x A b opt opt T opt T opt opt > − × × −

where min h -valid distance of vectors from components of the cluster of hyperplanes. The linear dependence or independence of vectors that can be removed from the set makes it possible to simplify the form of the formulas for the distances of these vectors from the corresponding hyperplanes.

3) The stop of the algorithm at the stage of the first cluster link can be completed after the distance of each of the vectors of the training sample

{ } n j E j x x m , 1 , ) ( : ) 0 ( = ∈ = Ω to the hyperplane )) 1 ( ), 1 ( ( opt opt b A L

does not exceed the allowable distance.

4) If the set{ } 1 1 1 , 1 , ) ( : ) 1 ( n j E j x x m = ∈ = Ω

includes at least two vectors, then go on to form the second link of the cluster.

2. Formation of the second cluster link. Consists of the following: 1) From the set obtained in the process of building the first link

{ } 1 1 1 , 1 , ) ( : ) 1 ( n j E j x x m = ∈ = Ω , a hyperplane )) 2 ( ), 2 ( ( opt opt b A L

defined as the set of solutions (pseudo -solutions) of a system of algebraic equations

, ) 2 ( ) 2 ( k k b x A = ,... 2 , 1 = k (3) is constructed. 2) To calculate optimal ) 2 ( , ) 2 ( kopt kopt b A for )) 2 ( ), 2 ( ( k k b A L , ,... 2 , 1 = k 3) To form a set ), 2 ( 0 k Ω ,... 2 , 1 = k

by the distance of the vector The superscript j denotes the number of iterations at the second link stage.

( )= )) 2 ( ), 2 ( ( , ) ( : 2 kopt kopt b A L j x x ρ ( ) × − = )) 2 ( ( ) ( ) 2 ( ) 2 ( kopt T T kopt kopt A R j x A b ( ) ) ( )2

The algorithm is stopped at the stage of the second cluster link after the distances of each of the vectors of the corresponding partitioning element to the corresponding hyperplane are not improved.

The efficiency criterion of the carried out hyperplane clustering is checked (for example, the requirement of the level of compactness of the cluster links). When the criterion is fulfilled, the cluster is completed, and if it is unfulfilled, the transition to the formation of the third cluster link is carried out. Then the process repeats and, since it is finite, we will always find a solution to the clustering problem.

Experimental studies

To test the effectiveness of the proposed method of scaling information, we used characteristic features for recognizing the dactyl letters of the Ukrainian sign language alphabet [6], [7]. As characteristic features, 52 features were taken, which were divided into 6 groups, depending on the method of their getting. The construction of piecewise hyperplane clusters was carried out with groups of features that characterize the geometric -topological parameters of the human hand when showing the letters of the dactyl alphabet and for which an acceptable recognition quality was obtained [6]. Using the example of the classification of nine dactylemes (А, Б, В, Г, Ж, І, Є, И, Й) according to three and five characteristic features, the separation of these dactylemes on the scaling plane was obtained. Wherein three characteristic features were taken: compactness, directionality, elongation, and in experiments with five features: the ratio of width to height, four angles values between vectors drawn from the center of the hand to the most distant points of the hand.

Experimental results using these three characteristic features are given in Fig. 1, where image of the dactylemes location on the scaling plane is normalized on the interval 0,1. Without reducing the generality of research, dactylem A was placed at the origin.

The results of clustering with using of five characteristic features are shown in Fig. 2., where the dactylem A was also placed at the origin. The results of the experiments showed that using of five characteristic features makes it possible to get a clearer separability (the distance of the dactylemes from the scaling plane ranged from 0.1580 to 0.3828), while using three features the distances from the scaling plane were significantly less (ranging from 0.0306 to 0.1274) that is, three to five times less. The exception was dactylem Б, in the first case (0.0177) and in the second case (0.0073), the separability from the scaling plane was not insignificant in both cases.

Conclusions

The paper proposes method and algorithm for multidimensional scaling of recognition objects characteristic features using the means of matrix pseudo inversion, building piecewise hyperplane clusters that provide a solution of the problem [14]- [18]. Proposed method makes it possible to analyze information about the set of characteristic features and to identify those that are essential for solving the recognition problem that is important due to their significant number and for difficult separable classes [19]- [25]. The effectiveness of the proposed approach is shown by the example of obtaining clusters for dactylemes sign language in order to obtain the optimal number of characteristic features for effective recognition.

Subsequent research will focus on the study of different types of characteristics features and their impact on the quality of recognition.