Feature Sorting Algorithm Based on XGBoost and MIC Combination Model

XGBoost, the full name of eXtreme Gradient Boosting, is an optimized distributed gradient boosting library, which is efficient, flexible and portable. XGBoost is a tool for large-scale parallel Boosting tree. XGBoost is an optimization of boosting algorithm, which integrates weak classifier into a strong classifier. XGBoost algorithm generates a new tree through continuous iteration to fit the residual of the previous tree. With the increase of iteration times, the accuracy continues to improve. It is the fastest and the best open source Boosting tree toolkit at present, which is more than 10 times faster than common toolkits. In terms of data science, XGBoost is a necessary weapon for major data science competitions, and a large number of contestants like to choose XGBoost for data mining competitions. In terms of industrial large-scale data, the distributed version of XGBoost is widely portable. And it is supported in various distributed environments such as Kubernetes, Hadoop, SGE, MPI, Dask, etc, which makes it a good solution to the problem of industrial large-scale data.

The definition function of XGBoost is shown in formula (1). (1) y^i=ϕ(xi)=∑k=1Kfk(Xi) {\hat y_i} = \phi \left( {{x_i}} \right) = \sum\limits_{k = 1}^K {{f_k}\left( {{X_i}} \right)}

The goal of formula (1) is to learn such K tree models f(x). In order to learn the model f(x), the objective function shown in formula (2) is defined. (2) L(ϕ)=∑il(y^i,yi)+∑kΩ(fk)where Ω(f)=γT+12λ‖ω‖2 \matrix{ {L\left( \phi \right) = \sum\limits_i {l\left( {{{\hat y}_i},{y_i}} \right) + \sum\limits_k {\Omega \left( {{f_k}} \right)} } } \cr {where\;\;\;\;\Omega \left( {\rm{f}} \right) = \gamma {\rm{T}} + {1 \over 2}\lambda {{\left\| \omega \right\|}^2}} \cr }

Among them, k is the total number of trees, f_k is the model of the kth tree, ŷ_i represents the predicted value of the model and y_i represents the category label of the ith sample, T represents the number of leaf nodes of each tree, and ω represents the set of scores of leaf nodes of each tree.

The tree model of XGBoost and the method of calculating feature importance are introduced below.

2)

Feature importance model

Importance is a measure to evaluate the importance of each feature in the feature sets to which it belongs. XGBoost uses three attributes to measure the importance of features, including Freq, Gain and Cover. Here, Freq is the percentage of times that a specific feature occurs in the model tree, Gain is the relative contribution value obtained by calculating the contribution of features in the model to each tree, and Cover is the coverage index of all functions related to a certain function.

The calculation formulas of the above three importance metrics are shown below (5). (5) Freq=|X|Gain=∑GainxFScoreCover=∑CoverxFScore \matrix{ {Freq = \left| X \right|} \hfill \cr {Gain = {{\sum {Gai{n_x}} } \over {FScore}}} \hfill \cr {Cover = {{\sum {Cove{r_x}} } \over {FScore}}} \hfill \cr }

X is a set of feature classification into leaf nodes, Gain is the gain value of each leaf node in X when it is segmented, and Cover is the number of samples falling on each node in X.

In order to get the best model, we construct L = f(θ), and get θ by “gradient descent”. With the support of the ascension tree, what we are looking for θ is a parameter for all trees(tree structure, scores of leaf nodes). In order to optimize the parameters and reduce the amount of calculation, we regard a tree as θ, and build a relationship between the loss function and a certain tree, and then take the derivative of loss for θ, and the process of finding the tree is the solution process of XGBoost.

In this paper, XGBoost model needs to determine three parameters: general parameters, auxiliary parameters and task parameters. General parameters are used to control the function macroscopically; The auxiliary function controls the iterative model, select tree model or linear model; Task parameters control the performance of learning tasks and learning objectives.

Among the above three parameters, the auxiliary parameters have the greatest impact on the algorithm performance, and the maximum height of the tree will affect the final result. Therefore, first tune the maximum height of the tree. In the tuning process, first give other parameters an initial value, and set the important parameter lines to common typical values or default values. Compare the changes of test data by changing the height of the tree, So as to get better parameter selection. After determining the maximum height of the tree, the best combination of other parameters is obtained by traversal method.

Figure 1 shows the process of building decision tree and optimizing parameters. Figure 2 shows the XGBoost algorithm flow.

Figure 1

Figure 2

MIC (Maximum Mutual Information Coefficient) can be used to measure the degree of correlation between two variables X and Y, which is often used for feature selection of machine learning. Compared with Mutual Information(MI), MIC has a higher accuracy and is an excellent data correlation calculation method.

According to the nature of MIC, MIC is universal, fair and symmetrical. The so-called universality means that when the sample size contains most of the information of the total sample, it can capture all kinds of associations, but not limited to specific function types (such as linear function, exponential function or periodic function), or it can cover all functional relationships in a balanced way. The complex relationship between general variables can be modeled not only by a single function, but also by superposition functions. The so-called fairness means that when the sample size is large enough, similar coefficients can be given for the correlation of different types of single noise with similar degree. Symmetry means that the amount of information obtained from different footholds is the same.

The basic principle of MIC will make use of the concept of mutual information. Mutual information is a measure of the degree of interdependence between random variables, which can be regarded as the information of another variable contained in one random variable. Mutual information can be defined by formula (6). P(x, y) is the joint probability between variables x and y. (6) I(x,y)=∫p(x,y)log2p(x,y)p(x)p(y)dxdyI[x;y]≈I[X;Y]=∑XYlog2p(X,Y)p(X)p(Y) \matrix{ {I\left( {x,y} \right) = \int {p\left( {x,y} \right){{\log }_2}{{p\left( {x,y} \right)} \over {p\left( x \right)p\left( y \right)}}dxdy} } \hfill \cr {I\left[ {x;y} \right] \approx I\left[ {X;Y} \right] = \sum\nolimits_{XY} {{{\log }_2}{{p\left( {X,Y} \right)} \over {p\left( X \right)p\left( Y \right)}}} } \hfill \cr }

The following formula (7) of MIC model is given as follows. (7) MIC(x;y)=maxa*b<BI(x;y)log2min(a,b)MIC[x;y]=max|X||Y|<BI[X;Y]log2(min(|X|,|Y|)) \matrix{ {MIC\left( {x;y} \right) = \mathop {\max }\limits_{a*b < B} {{I\left( {x;y} \right)} \over {{{\log }_2}\min \left( {a,b} \right)}}} \hfill \cr {MIC\left[ {x;y} \right] = \mathop {\max }\limits_{\left| X \right|\left| Y \right| < B} {{I\left[ {X;Y} \right]} \over {{{\log }_2}\left( {\min \left( {\left| X \right|,\left| Y \right|} \right)} \right)}}} \hfill \cr }

MIC model calculates the relationship between two attributes in turn, discretizes them in two-dimensional space, and uses scatter plot to represent them. The model divides the current two-dimensional space into a certain number of intervals in the X and Y directions, and then checks the situation that the current scatters fallen into each grid, thus solving the problem that the joint probability in mutual information is hard to find.

The calculation of MIC value is generally divided into the following three steps: first normalize the data volume through different meshing methods, then calculate the maximum mutual information value, then normalize the maximum mutual information value, and finally select the maximum mutual information value under different scales as the mic value.

In XGBoost algorithm, the steps of constructing decision tree are as follows:

Traverse all feature nodes from the root node. For a certain feature, according to the sample value, sort and then determine the segmentation point with the best gain.

According to the above algorithm ideas, the results of the two algorithms are weighted and combined by the error reciprocal method which are shown in formula (8). (8) ft=α1f1t+α2f2t,t=1,2,3,…,nα1=ε2ε1+ε3, α2=ε1ε1+ε2 \matrix{ {{f_t} = {\alpha _1}{f_{1t}} + {\alpha _2}{f_{2t}},t = 1,2,3, \ldots ,n} \hfill \cr {{\alpha _1} = {{{\varepsilon _2}} \over {{\varepsilon _1} + {\varepsilon _3}}},\;\;\;{\alpha _2} = {{{\varepsilon _1}} \over {{\varepsilon _1} + {\varepsilon _2}}}} \hfill \cr }

Respectively, ɛ₁ and ɛ₂ is the error between the calculated result and the true value by XGBoost and MIC algorithms. It can be seen from formula (8) that this method all error, thus reducing the error of the whole combination model and obtaining the predicted value closer to the real situation, thus improving the overall prediction accuracy. The error reciprocal method can not only give greater weight to the method with higher prediction accuracy, but also ensure that the error reciprocal method can give greater weight to the method with smaller absolute error value (i.e. the method with high prediction accuracy) at any time. If the number of positive and negative errors of each single prediction error is equal, the error reciprocal method can effectively reduce the combined prediction error and achieve better combination effect.

In this data set, there are a certain number of unique attributes and empty attributes, so before using this data set, data processing should be carried out first.

For the unique attributes in the data set which can’t describe the distribution law of the sample itself, we can delete these attributes directly.

In order to avoid dealing with high-dimensional data and reduce the difficulty of learning tasks, feature coding is needed. The feature coding method adopted in this paper is One-Hot Encoding. Only One-Hot Encoding uses N-bit status registers to code N possible values, and each state is represented by an independent register, and only one of them is valid at any time.

For data with different magnitudes in the data set, the magnitude difference may greatly affect the calculation results. In order to reduce its effect on the results, the data must be standardized. In this paper, the data are normalized. Its conversion function is shown in formula (9). (9) x=x−minmax−min x = {{x - \min } \over {\max - \min }}

Finally, we divide the data set into two parts: the training set (80%) and the verification set (20%). The verification set is used to record the accuracy of the algorithm to find out the best model parameters.

As shown in Figure 3, the XGBoost and MIC models are realized respectively. The two models are optimized by grid search method to get the optimal parameters, and then the combination model is calculated by the reciprocal error method. The score and ranking of feature importance calculated by this model are shown in Figure 4.

Figure 4

In this paper, R² (the decisive coefficient of the relationship between a random variable and multiple random variables) is selected to reflect the regression model, and is used as the main evaluation index of the prediction performance of each model. Root mean square error (RMSE) is selected as the auxiliary evaluation index. The calculation of R² and RMSE is shown in formula (10) and (11) respectively. (10) R2=1−RSSTSS=1−∑i(yi−fi)2∑i(yi−y¯)2 {\rm R^2} = 1 - {{RSS} \over {TSS}} = 1 - {{\sum\limits_i {{{\left( {{y_i} - {f_i}} \right)}^2}} } \over {{{\sum\limits_i {\left( {{y_i} - \bar y} \right)} }^2}}} (11) RMSE=1m∑i=1m(yi−y^i)2 {\rm{RMSE}} = \sqrt {{1 \over {\rm{m}}}\sum\limits_{i = 1}^m {{{\left( {{y_i} - {{\hat y}_i}} \right)}^2}} }

y_i is the predicted value of XGBoost-MIC combination model for the I-th data set, ŷ_i is the actual measured value in the I-th data set, and m is the number of samples.

The XGBoost-MIC combination model was tested with the testing-set data divided in the preprocessing, and the R² and RMSE values were compared with those of the single model. The results are shown in Table 1.

As can be seen from Table 1, the value of XGBoost-MIC combination model is higher(the closer the R² value is to the 1, the closer the predicted value is to the real value), The prediction accuracy of the combination model is nearly 0.02 higher than that of the single model. By analyzing RMSE values, it can be concluded that the combination model has lower error than the single model. In general, the combination model has higher accuracy and less error, which has obvious advantages over the single model.