The article describes the solving of data mining task using neural-like structures of Successive Geometric Transformations Model (NLS SGTM). The main problems of this task are imbalanced dataset and different weigh of errors. Therefore, to take into account these features, the method of penalties and rewards was used, as well as a piecewise linear approach to classification. The supplement of the methods used by the final optimization procedure is proposed. The procedure of final optimization using simulated annealing.
In the previous articles [1-2] the methods based on the combination of a Successive Geometric Transformations Model with the method of penalties and rewards was described. In addition, was developed the piecewise-linear approach to constructing separating surfaces in classification tasks.
The purpose of these methods is to solve the data mining tasks of the classification. The main features of these tasks are large-size datasets, imbalanced dataset and different weight of errors. The main goal of this research is increasing the accuracy of classification and minimize the number of penalty points.
In order to increase the accuracy of classification, we propose to supplement the developed methods with final optimization procedures, in particular by the method of random correction of decomposition elements and the method of simulated annealing.
Today the data mining tasks are widespread because most companies today have a huge amount of accumulated data with information about sales, customers, orders, and more. This information is a source of hidden knowledge. In turn, the possession of this knowledge allows this company to take a leading position in the market, to win the competitive struggle. Among such tasks, one of the most popular is the task of classification. These tasks are formulated daily; in such spheres of life how as commerce, telecommunication, and chemical industry, target marketing, insurance, medicine, bioinformatics, and others. Researchers use different methods to solve classification problems [1, 2, 3, 4].
The main features of classification tasks in data mining are imbalanced data, different weight of error, huge amounts of data. These features require using some special additional methods to well-known methods of classification to provide high accuracy of classification.
Hereby as basic methods of classification, we used the neural-like structure of successive geometric transformations model (NLS SGTM) [5, 6]. As an additional method was used piecewise-linear approach [1] and cost-sensitive learning method [7, 8]. This allowed us to improve the classification accuracy and take into account the specifics of a specific task. This article proposes to apply global optimization methods to the neuro-like structure already trained as a result of previous experiments. This will allow us to find such parameters of the neural-like structure, in which the sum of points reaches the global max.
3.1.
The analysis of the principal components is the standard method used to reduce the dimensionality of data in statistical pattern recognition system and signal processing systems. However, it is also advisable to use the analysis of the principal components to solve the problems of data mining because of their high dimensionality [9, 10].
The main task of statistical recognition is the allocation of attributes - the process in which the data space is transformed into space of attributes, which theoretically has the same dimension as the input space. Conversions, however, are usually performed so that a reduced number of the most effective features can represent the data space. Consequently, only a substantial part of the information contained in the data remains, the dimension of the data is reduced. If this approach is applied to data mining task, we will reduce the size of the input data by extracting non-informative features without losing significant data. Consider a more detailed analysis of the principal components (in the theory of information is known as Karhunen-Loeve Transform) [11, 12].
Assume that there exists a vector X of dimension m, which we want to convey with the help of l numbers, where l <m. If we simply cut the vector x, this will cause the mean square error to be equal to the sum of the dispersions of the elements carved out of the vector x. It is necessary to find some linear transformation T, for which the value of the mean square error for the reduction of the vector X will be optimal. In this case, the transformation T must have the property of a small dispersion for its individual components. The analysis of the principal components maximizes the rate of dispersion reduction and, accordingly, the probability of the correct choice [13, 14].
Let X be an m-dimensional random vector from the initial set of data. The mean value of this vector equal zero. where E is the operator of statistical expectation. If X have a nonzero average, then you can calculate this value before the analysis begins. Let q be a unit vector with dimension m, the vector X is projected on vector q. This projection is defined as the product of the vectors X and q:
E(X)=0,
A=XTq=qTX with restriction
||q||=(qTq)0.5 = 1. (3)
Projection A is a random variable that has an average value and variance that is related to random vector statistics X. Dispersion A equals
σ2=E[A2]=E[(qTX) (XTq)]= qTE[(XXT]q = qTRq (4)
The matrix R of dimension mm is the matrix of the correlation of the random vector X defined as the expectation of the product of the random vector X on itself:
R=E[XXT] (5) The matrix R is symmetric, then:
RT=R. (6) It follows from (6) that if a and b are arbitrary vectors with dimension m1 then: aTRb=bTRa (7)
From equation (4) it follows that the projection A is a function of an odd vector q. So, we have: (q) =σ2= qTRq, (1) (2) (8) (q) – dispersion probe.
Directly the principal components are defined as follows. Let the data vector x be a realization of the random vector X. Since there are m possible values of the single vector q, then we must consider m possible projections of the data vector x. By formula (2)
aj = qjTx=xTqj, j = 1,2,…,m (9) where aj - the projections of the vector x on the main guides, represented by single vectors qj. These projections are called principal components, their number corresponds to the dimension of the data vector x. In this case formula (9) can be considered as the analysis procedure.
input data
Allocation of the principal components (PC) is also proceeding on the outputs of the hidden layer of the neural-like structure of GTM. After selecting the PC, we create and teach an additional neural-like structure (Fig. 2), where the inputs are the vectors of the PC, and the outputs are the significance of the corresponding outputs of the initial training data [15, 16, 17]. The feature of this neural network is the representation of the output of the synapse as y im1 zi well as weak correlation zi. In the mode of application on the inputs of the trained neural network, input vectors are: 0 0 ...0 y0
Get the elements of decomposition z0 y0 , zi PCii , i 1,2,..., m. Initially we have y im0 zi or y im0 zi ki , (10) where zi the elements of decomposition, ki =1, i = 1,2,…, m .
For classification tasks, appropriate indicators are optimized (percentage of properly classified specimens, number of penalty points, average arithmetic or mean square error) by random correction of elements of decomposition of coefficients ki . Random correction of coefficients ki can be performed simultaneously for all components or for each component independently. It should be noted that componentbased random correction is appropriate for prediction since it has been experimentally confirmed that the components are practically independent [18, 19].
Consider a more detailed algorithm for random correction. 3.2.
Let us consider the case of optimizing the accuracy of the classification problem solving for a case where the recognized data belong to one of the two classes.
Re-coding the input file: outputs of the elements belonging to class 1, assign 1, the outputs of the elements belonging to class 2, assign -1.
The problem of recognition is solved as a prediction problem by the formula (3), but after obtaining a value, we analyze it by the formula (11):
class1, y 0, y (11)
class2, y 0.
For the task of recognizing the criteria by which optimization can be carried out, there may be the number of penalty points, the percentage of incorrectly classified representatives of class 1, the percentage of incorrectly classified representatives of class 2.
Then the percentage of incorrectly classified representatives of classes is calculated as follows:
ErrC1 =100% NWC1/NC1, ErrC2 =100% NWC2/NC2 (12) where NC1 is the number of representatives in class 1 in the training sample, NC2 – number of representatives of class 2 in the training sample, NWC1 – number of incorrectly classified representatives of class 1, NWC2 – number of incorrectly classified representatives of class 2.
In order to calculate the number of penalty points, it is necessary to determine the fines that count for erroneous recognition. So if P1 is a fine charged if the element of class 1 is recognized as an element of class 2 and P2 is a fine charged if a class 2 element is recognized as an element of class 1.
Then the value of the penalty function - the total number of received penalty points (PP) is:
PP=ErrC1P1+ErrC2P2. (13)
Optimization method for classification tasks based on correction of decomposition elements by random correction: 1. Initial values ki=1.
2. We calculate the value of the error, which is optimization (PP, ErrC1 or ErrC2).
3. Using a random number generator with a uniform distribution, we choose the value ΔD from the range (–D, D).
4. Calculate new values ki = ki + ΔD. 5. Calculate the value of outputs with new ki .
6. Convert the resulting value to the designation of the class to which this element belongs.
7. Calculate the new value of the error, which is optimization (PP, ErrC1 or ErrC2).
8. Compare the value of the calculated error with the pre-calculated value. If the new value is less than the previous one, we will remember it as well as the current coefficients ki . Go to step 3. Otherwise, go to step 3 without remembering.
9. Continue optimization until the predefined desired optimization value is reached, or until the time t has expired.
After performing the optimization method by randomly correcting the decomposition elements, the resulting coefficients are used for further classification.
accuracy of classification in the tasks of the data mining 4.1.
Annealing method is an algorithmic analogue of the controlled cooling process. It was proposed in 1953 by N. Metropolis and refined by numerous followers. Today it is considered one of the few methods by which one can practically find the global minimum of functions of several variables. Consider a more detailed method of simulated annealing [20, 21].
Algorithm of simulated annealing method: 1. Start the process from the starting point at a given initial temperature T=Tmax. 2. As long as T>0, repeat L times the following actions: • choose a new solution w' from the vicinity w; • calculate the change of target function; Δ = E(w')- E(w); • if Δ≤0, take w = w'; otherwise, if Δ>0, take w = w' with probability exp(-Δ/T) by generating a random number R from the interval (0,1), then comparing it with the value exp(-Δ/T); if exp(-Δ/T) > R, take a new solution w = w'; in other case - ignore it. 3. Reduce the temperature ( T rT ) using the reduction coefficient r, selected from the interval (0,1) and return to step 2. 4. After lowering the temperature to zero, apply one of the deterministic methods (Levenberg-Marquardt algorithm, error-return algorithm, fastest-speed algorithm, etc.) to achieve the minimum of the target function.
The concept of "temperature" in this algorithm is quite formal, since the presented optimization model is only a mathematical analogy of the annealing process.
The efficiency of the annealing algorithm has an extremely high impact with the choice of parameters such as the initial temperature Tmax, the coefficient of reduction of temperature r and the number of cycles L, performed at each temperature level.
The main problem is to determine the threshold level optimal for each annealing simulation process. For some practical tasks, this level may have different meanings, but the overall range remains unchanged. As a rule, the initial temperature is selected so as to ensure the implementation of about 50% of the subsequent random changes in the solution. Therefore, knowledge of the pre-distribution of such changes makes it possible to estimate the initial temperature approximately.
Numerous computer experiments [22] prove that in the case where the time limit is small, the best results give a single implementation. If simulation can be long lasting, then statistically better results can be achieved thanks to the multiple implementation of the annealing simulation if the value of the coefficient r is close to 1.
If we compare genetic algorithms with an annealing algorithm, then, in spite of the significant external difference between the algorithms, they are essentially similar in nature. An annealing algorithm according to [23] can be considered a genetic algorithm with a population consisting of one instance. Consequently, an algorithm for simulating annealing of a metal can be regarded as an algorithm that has only a mutation operation, but not cross-linking.
In addition, if we compare these two algorithms from the applied point of view, then it should be noted that, according to Kohonen's study [7], in the case when the initial solution is sufficiently close to optimal, the annealing algorithm of the metal has significant advantages over the genetic algorithms from a computational point of view.
Since in our study the initial data are pre-processed by methods of fines and incentives with sampling alignment and piecewise linear classification on the basis of the model of geometric transformations, then the initial solution of the problem is sufficiently close to the optimal. Accordingly, in this case, it is more appropriate to choose for optimization of the solution.
Let's consider a more detailed algorithm of simulated annealing of metal in combination with methods of fines and incentives and piecewise linear classification on the basis of a model of geometric transformations.
Fig. 3 depicts the structural scheme of the developed neural network based on the model of geometric transformations, where x1, x2 ,..., xn primary features of classification objects – input data, PC1, PC2, ..., PCn the principal components derived from input data, w1, w2 ,..., wn weight coefficients, y an output that indicate on belonging to certain classes. Functioning of such a neural network can be described by the formula 14.
y in1 PCwi (14)
The method of simulating annealing of a metal is proposed to be used to optimize weight coefficients so that the resulting amount of penalty points is minimal, that is, the optimization parameter is the amount of penalty points [15, 17].
As can be seen from the flowchart describing the solution of the data mining problem by combining the method of fines and incentives, simulated annealing and piecewise linear approach, a modified annealing method for which the target function is the number of penalty points, will be applied separately for each cluster [22, 24].
Accordingly, if we have a two-step division into clusters for a sample of n classes, then we will have division into clusters, which is depicted in Fig. 4, and for each of the clusters a modified annealing algorithm will be implemented.
This article describes the solving of classification task, which was formulated in [1]. The training sample describes the transactions carried out by credit card holders within two days and consists of 284,807 lines and 31 columns Also, the dataset contains one target feature 'Class', which shows the client's affiliation to one of two classes - frauds or ordinary clients. The main feature of the dataset is that the data set is highly unbalanced - only 492 transactions out of 284807 (0.172% of all transactions) have the value of the target field 1, that is, customers are fraudulent. The dataset has been collected and analyzed during a research collaboration of Worldline and the Machine Learning Group (http://mlg.ulb.ac.be) of ULB (Université Libre de Bruxelles) on big data mining and fraud detection [7].
According to the subject area, a matrix was formed. By analyzing this matrix, it can be seen that a properly classified vector that belongs to the "fraud" class has a much greater weight than a properly classified "ordinary client" vector. At the same time, the case where an ordinary customer is classified as fraud has the highest number of penalty points (Table 1).
Then we used the modified method of imitation of annealing of the metal with parameters: initial temperature T=Tmax=20895, L=100, R is a random number from the interval (0,1), r=0,9.
After lowering the temperature to zero, apply one of the deterministic methods (Levenberg-Marquardt algorithm, error-return algorithm, fastest-speed algorithm, etc.) to achieve the minimum of the target function. The results of classification are described (Fig 5, Fig.6). The application of global optimization methods to classification in the data mining tasks allowed to increase the accuracy of classification, especially in combination with other methods of classification, such as neural-like structure of successive geometric transformations model. Also, the method of simulated annealing successfully combined with such methods as piecewise-linear approach and cost-sensitive learning method. The application of the method of simulated annealing made it possible to reach the point of the global maximum and minimize the amount of penalty points for this task.