A classification and regression algorithm based on quantitative association rule tree

4.1 Reconstructing the classification and regression quantitative association rule

For the quantitative association rule A ⇒ B, the input and output variables of frequent itemsets L _k are described as the rule antecedent (record as A) and consequent (record as B) respectively. The existing quantitative association rules are rewritten with a similar expression by combining with TS fuzzy inference rules to predict the output values to evaluate the category or regression function (see Equation (2)).

Rule l : If x 1 min ( i 1 ) < x 1 < x 1 max ( i 1 ) , x 2 min ( i 2 ) < x 2 < x 2 max ( i 2 ) , … , Then y min ( m ) < y ( l ) < y max ( m ) , y ( l ) = a 0 ( m ) + ∑ p = 1 n a p ( m ) x p(2) where Rule _l denotes the l-th rule, the antecedent is derived from the quantitative association rule, x 1 min ( i 1 ) and x 1 max ( i 1 ) denote the minimum and maximum of i₁-th cluster of x₁ respectively. The consequent y min ( m ) < y ( l ) < y max ( m ) is the interval of the output category m that derived from quantitative association rule, and also the consequent can be expressed as a regression function whose coefficients a i ( m ) are obtained by the weighted least squares estimation algorithm.

All the existing association rules are grouped according to the output category variable. In the same output category, the antecedent variables corresponding to the rule that has the highest importance calculated according to (1) is determined as the antecedent variables of fuzzy rules. Besides, all data within the output category are selected to fit the consequent function of the rules. So, the rules can be used to not only classify new data to get the output category, but also estimate the future tendency with regression function to realize TS fuzzyinference.

For example, for the input x, the degree of activation of the l-th rule is calculate by τ l = ∏ p = 1 n μ p ( l )(3)

Where μ p ( l ) represents the membership of x _p in the l-th rule, as (4): μ p ( l ) = e - ( x p - x ¯ p ( l ) ) 2 2 ( σ p ( l ) ) 2(4)

Where x ¯ p ( l ) and σ p ( l ) represent the mean and the standard deviation of x _p belong to the l-th rule respectively, which are generated from the clustering results of various variables. The output y of the model is a weighted sum of rule contributions (see Equation (5)):

y = ∑ l = 1 R τ l y ( l ) / - ∑ l = 1 R τ l , l = 1 , ⋯ , R(5)

When mass rules are generated, classifying and predicting the new sample enjoys matching so many rules one by one as to decrease the efficiency and accuracy. In order to solve this problem, a classification and regression quantitative association rule tree is presented.

Unlike FP-tree, the classification and regression quantitative association rule tree is built on the basis of the association rule bases, which only scan the rule base twice but not the whole database. The process is divided into the following two steps.

1) The first scan of the association rule base is to generate the header table.

This process is the same as Apriori, which derives the set of frequent items (1-itemsets) and their support counts (frequencies). The set of frequent items is sorted in the order of descending support count. Moreover, the input variable sets and output variable sets of frequent 1-itemsets are ranked as their support counts respectively to form two part of head table, where one is denoted as filist-1 and the other is denoted as filist-2. If the support counts of two itemsets are same, the itemsets are ranked as their importance by (6). Importance ( I i ) = ∑ j = 1 k O p ( I i , O j ) / - p ( I i ) p ( O j )(6)

Where O _j represents the itemset corresponding to the output variable and k _O represents the category number for the output variable, p (I _i , O _j ), p (I _i ) and p (O _j ) represent the support counts of itemsets (I _i , O _j ), item I _i and item O _j in the association rule base respectively.

For instance, the scan of the Iris dataset, the header table generated by scanning association rule base is shown in Table 1, which recorded the item variables and other features such as category, support count, importance, maximum and minimum values and spread(square root of data variance). According to the head table, each item variable in association rule base is checked whether matching the corresponding variable category when the new sample is to be classified. The items in each association rule can be denoted as the serial number of header table. For example, in Table 1, the item 1 ≤ x₄ ≤ 1.5 corresponding the first row whose variable serial number is 4 and category number is 3 can be denoted as “1”. In this way, all items in association rules can be represented as the serial number.

For example, an association rule is described as: If 2 ≤ x 2 ≤ 2.7 , and 3 ≤ x 3 ≤ 4.3 , and 1 ≤ x 4 ≤ 1.5 , Then class is 2 , class = 0.0151 – 0.0900 × x 2 + 0.1694 × x 3 + 0.4979 × x 4(7)

Which can be transformed into such expression: 4 and 3 and 1 = = > 14(8)

2) The second scan of the association rule base is to construct the CRQAR-tree.

First, create the root of the tree, labeled with “null.” Scan association rule base a second time. The items in first association rule are processed in L order (i.e., sorted according to descending support count), and a branch is created for the first association rule. Scan association rule base a third time. If the next association rule contains the same items with the first branch, a common prefix would be shared with the existing path. Otherwise, a new branch is linked to the root and a new node is created and linked as a child of root node. In general, when considering the branch to be added for a association rule, the nodes for the items following the prefix are created and linked accordingly. When the last item of the association rule is scanned (assuming the i-th item of the rule), a new leaf node is added which recorded the output category, linear expressions and confidence of the consequent of the association rule in the corresponding layer (the i-th layer). Such a process can be recursively applied to generate the CRQAR-tree.

Algorithm 1: constructing the CRQAR-tree.

Input:D, an association rule base; minsup, the minimum support count threshold.

Output: The complete set of category and regression association rules.

Step 1. Scan the association rule base D once, collect F, the set of frequent items (1-itemsets), and the support counts, the input variable sets and output variable sets of frequent 1-itemsets are ranked as their support counts respectively to form two part of head table, where one is denoted as filist-1 and the other is denoted as filist-2.

Step 2. Based on the corresponding relationship between each item in the original association rules and each record in the head table, the original association rules can be transformed into new rules (see Equation (8)). Create the root of the CRQAR-tree, labeled with “R”. Let the sorted frequent item list in Rules be [p|P], where p is the first item and P is the remaining list. Calling the insert-tree ([p|P], R) is performed as follows. If R has a child Node, then Node . name = p; else create a new node that Node . name = p, its parent link be linked to R, and its node-link to the nodes with the same item-name via the node-link structure. If P is nonempty, then call insert-tree ([p|P], R) recursively. When the last item of the association rule is scanned (assuming the i-th item of the rule), a new leaf node is added which recorded the output category, linear expressions and confidence of the consequent of the association rule in the corresponding layer(the i-th layer). Such a process can be recursively applied to generate the CRQAR-tree as shown in Fig. 1.

When predicting a new case, the best rule in the CRQAR-tree is selected to satisfy the case. There are three possible occasions for matching a case with a set of rules in the CRQAR-tree: 1) the case matches only one rule; 2) the case does not match any rules; 3) the case matches more than one rule. If the matched rules do not agree on the class labels, the rule with the highest confidence is selected to determine the class label C.

The matching process is described as follows:

The first step is to discretize new data. The discrete items are denoted as the serial number in the head table.

Algorithm 2: Classification and Regression Prediction based on the CARA-tree.

Input: the new sample.

Output: the category and the real value.

Step 1. For a testing sample x, which is discretized according to the head table and matched by using the CRQAR-tree following the appropriate branch from the root node to the first level child node Node_1j  (j = 1, …, n _i ).

Step 2. Starting from the i-th level child nodes and moving to its subsequent node that matches with x until a leaf node. If the sample matches more than one branch, the output category is determined by whose leaf node has the highest confidence. Otherwise, go to step 3.

Step 3. If there is no branch to match the sample x through the CRQAR-tree, the TS fuzzy inference rules deduced from all the samples are adopted to predict the category and the real value according to Equation (5).

4.4 Time complexity analysis

For a training dataset comprising S transactions (I itemsets in each transaction) and getting K rules, |L _k | and |C _k | is the number of frequent and candidate k-itemsets respectively. In the worst case, each item variable will be discretized into S intervals, each transaction contains I × S interval itemsets by the categorical variable map.

According to the learing process of Apriori algorithm, to get the frequent 1-itemsets, the time complexity is O (I × S²), to produce the candidate k-itemsets, the time complexity is O (|L _k | × |L _k |), and to get the frequent k-itemsets from candidate k-itemsets, the time complexity is O (|C _k | × (S + 1)), therefore, the total time complexity of Apriori learning process is summarized by (9): O ( I × S 2 + ∑ k ≥ 2 ( | L k | × | L k | + | C k | × ( S + 1 ) ) )(9)

While the time complexity with our proposed method is summarized by (10): O ( I × S + ∑ k ≥ 2 ( | L k | × | L k | + 2 | C k | ) )(10)

By adopting the categorical variable matrix to calculate the support, it avoid from generating a large number of candidate itemsets, so the time complexity is O (I × S). To get frequent k-itemsets, the time complexity is O (2|C _k |), which is fairly low complexity than Apriori algorithm.

To classifying a new case, the time complexity is O (K × (I – 1) × S) with the quantitative association rule mining algorithm(see Section 3), while the time complexity is O ((I – 1) × S) with the CAQRA-tree, which improve the efficiency of the classification and increase the rule matching speed.

5.1 Datasets

Here, For Iris dataset, the header table generated by scanning association rule base is shown in Table 1. According to Table 1, each item in the corresponding association rules can be denoted as the serial number of header table, based on which the CRQAR-tree is constructed for Iris dataset as shown in Fig. 1. When the CRQAR-tree is applied to predict the new case, the efficiency can be greatly improved.

As shown in Fig. 2, we make a comparison between our proposed CRQAR-tree algorithm and quantitative association rule mining algorithm(see Section 3) on eight datasets in terms of executing time. The executing time of our proposed approach through Iris, Wine, Hepatitis, Pima, Breast Cancer, Australia, Sona and Heart datasets are 0.022 s, 0.043 s, 0.053 s, 0.065 s, 0.081 s, 0.090 s 0.098 s and 0.115 s respectively, while that of the quantitative association rule mining algorithm through above datasets are 0.030 s, 0.100 s, 0.150 s, 0.170 s, 0.209 s, 0.276 s, 0.294 s and 0.312 s respectively. It is obvious that the proposed approach achieves higher speed to match therules.

For the purpose of comparative analysis, other nine methods are applied on eight datasets. The accuracy of different algorithms in each dataset is summarized in Table 2. Here, the classification rate is adopted as follows: Classification _ rate = m / - n(11)

Where n represents the number of data samples, m represents the number of data samples which match the association rules respectively.

It is obvious that the CRQAR-tree shows a better performance than other models especially in the Breast Cancer, Pima and Australia datasets, although it is a slightly worse compared with RBF in the first two datasets, and it still perform better than other eight models. For Sona dataset, the CRQAQ-tree also perform better than other eight models except KNN with a small gap. For Hepatitis and Heart datasets, although the performance of the CRQAR-tree is not the best, it also perform better than other most of models. The last column is the average accuracy of the methods for all the datasets, which also yields that our proposed method can achieve a better classification performance and good scalability.

In order to better illustrate the results shown in Table 3, ties using the paired t-test [20] with a confidence level of 0.95 is detected, and the results is shown in Table 4, which composed of five parts(ties, wins, loses, wins-loses and ranking) of all methods. The first three columns are the number of ties, wins and loses, and the fourth column is the difference between the number of wins and loses, which is used to generate the ranking in the last column. It is obvious that the CRQAR-tree is superior to other methods significantly.

In order to further verify the validity and the performance of regression forecasting, a comparison of RMSE(Root Mean Square Error) with different methods on benchmark datasets are compared as shown in Table 4. Here, The RMSE is adopted for generalization performance evaluation: RMSE = ∑ i = 1 n ( y ˆ i - y i ) 2 / - n(12)

Where n represents the number of data samples, y ˆ i and y _i represent predictive output and actual output respectively.

It is apparently that the CRQAR-tree exhibits an even better performance than other four methods, where the RMSE values of our proposed method are smaller than other methods especially in the first three datasets. The average value of REMS is also be calculated for every method on different datasets. For CRQAR-tree, the average value of REMS is 7.41, which is also smaller than those of the other methods, so the CRQAR-tree shows better results for regression forecasting.

In recent years, medium plates are widely used in industries, such as construction, ship building, national defense and so on. Therefore, more and more attention is paid to the quality of medium plates [21]. In the manufacturing process of hot medium plates, the mechanical properties of the medium plate plays a very important role. But the boundary conditions in hot rolling process is so sophisticated that it would be difficult to build model to describe the relation between the mechanical properties and the process parameters. In this paper, a CRQAR-tree model is proposed to predict the mechanical properties.

After data preprocessing, 15 input variables are included: original chemical contents such as C, Mn, P, S, Si, some alloying elements of Cr, Ni, Cu, Mo, and three gas composition of H, N, O, and the process parameters such as the during time and discharging temperature of the slab, the middle billet height, the beginning and finish temperature, the roughing rolling temperature, the rolling finish temperature, the thickness of rolled coil, the coiling average temperature and pressure rate. The output variable of model is yield strength.

In order to mine the medium plate dataset, the discretization method based on DFAC is applied and the improved Apriori algorithm is used to generate the quantitative association rules based on the discrete data(see Section 3). The rules are reconstructed by combining with the TS fuzzy inference algorithm to enhance the classification and regression accuracy (see Section 4).

Here only two quantitative association rules for the medium plate are shown as follows:

Rule 1 : If 0 .8135 < w ( Cr) ≤ 0 .8645 , and 0 .3333 < w ( H ) ≤ 0 .6333 , and 0.5000 < w ( M o ) ≤ 1.0000 , and 0 .1530 < w ( S i ) ≤ 0 .2296 , and 0 .4479 < w ( S ) ≤ 0 .5833 Then 0 .4687 ≤ y s _ r e l 1 ≤ 0 .5777 , y s _ r e l 1 = - 0.3265 − 4.4205 × w ( C r ) − 3.3825 × w ( H ) + 3.4450 × w ( M o ) + 0.2379 × w ( S i ) − 0.6286 × w ( S )(13) Rule 2 : If 0 .0945 < C i _ T ≤ 0 .1435 , and 0 .4638 < F t _ A v e r ≤ 0 .6811 , and 0 .1430 < T _ A v e r ≤ 0 .1576 , and 0 .4409 < w ( M n ) ≤ 0 .6929 and 0 .2667 < w ( O ) ≤ 0 .3778 , and 0.0000 < w ( S i ) ≤ 0 .0580 , and 0 .3229 < w ( S ) ≤ 0 .4271 , Then 0 .5913 ≤ y s _ r e l 2 ≤ 0 .7275 , y s _ r e l 2 = 0.0111 + 16.1103 C i _ T − 0.0397 F t _ A v e r − 16.1699 T _ A v e r + 0.1243 × w ( M n ) − 0.9588 × w ( O ) + 0.4298 × w ( S i ) − 0.0316 × w ( S )(14)

Where Ci _ T represents the thickness of rolled coil, Ft _ Aver represents the roll-finish average temperature, T _ Aver represents the average temperature, w(Mn) represents the mass fraction of Manganese element, w(O) represents the mass fraction of Oxygen element, w(Si) represents the mass fraction of Silicon element, w(S) represents the mass fraction of Sulfur element, w(Cr) represents the mass fraction of Chromium element, w(H) represents the mass fraction of Hydrogen element, w(Mo) represents the mass fraction of Molybdenum element, ys_rel represents the yield strength of l-th rules. 0.0945 < Ci_T ≤ 0.1435 represents the 1-itemsets of the input variable Ci_T and 0.5913 ≤ ys_rel² ≤ 0.7275 represents the 1-itemsets of the output variable.

In order to improve the efficiency to predict a new case with these rules, the header table of medium plates is shown in Table 5. Based on it, the CRQAR-tree is constructed (see Section 4), in which each intermediate node corresponds to the item of the header table and each leaf node records three parts: the output category, confidence and the linear coefficients for the rule consequent part.

Figure 3 shows the structure of CRQAR-tree for the medium plate dataset. It can be seen that the CRQAR-tree for the medium plates dataset has eight layer, the serial number of each node in each layer corresponds to the serial number of header table for the specific item, the leaf nodes of each path record the output category, linear coefficients for the rule consequent and confidence. Moreover, if the case matches more than one branch, the output category is determined for the leaf node with the highest confidence. If there is no branch to match the case through the CRQAR-tree, the TS fuzzy inference rules derived from all the samples are used to induce the category and the real value according to (5).

In order to evaluate the performance of the CRQAR-tree, the proposed approach is compared with other five methods by using 1000 data for training and 500 data for testing. The results are shown in Table 6.

Notice that the prediction performance of the CRQAR-tree method is superior to that of the remaining methods. The parameters of the remaining methods were selected according to the recommendation of the corresponding authors within each proposal. For the training data, the RMSE based on the proposed approach is 0.1858, while that of the other five methods are 0.2064, 0.2205, 0.9760, 1.1040 and 1.0423 respectively. Similarly, the testing results are also derived that our proposed method has achieved higher performance.

The fitting curve of the mechanical properties with the CRQAR-tree algorithm for training and testing data are given in Figs. 4 and 5. From Fig. 4, one can observe that CRQAR-tree algorithm is responsive to change in the underlying characteristics of the hot rolling system in a timely fashion, where the straight line represents the actual output value and the dotted line represents the predictive output value. Although the fitting errors of testing data in Fig. 5 is slightly higher than that in Fig. 4, the CRQAR-tree algorithm still tracks the system well. It can be concluded that the quality model of medium plates based on CRQAR-tree algorithm is effective and practical.