# A Novel Multiway Splits Decision Tree for Multiple Types of Data

Authors: Zhenyu Liu; Tao Wen; Wei Sun; Qilong Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Classical decision trees such as C4.5 and CART partition the feature space using axis-parallel splits. Oblique decision trees use the oblique splits based on linear combinations of features to potentially simplify the boundary structure. Although oblique decision trees have higher generalization accuracy, most oblique split methods are not directly conducive to the categorical data and are computationally expensive. In this paper, we propose a multiway splits decision tree (MSDT) algorithm, which adopts feature weighting and clustering. This method can combine multiple numerical features, multiple categorical features, or multiple mixed features. Experimental results show that MSDT has excellent performance for multiple types of data.


---

## Body

## 1. Introduction

Despite the great success of deep neural network (DNN) model in image processing, speech recognition, and other fields in recent years, decision trees have competitive performance compared to DNN scheme, such as the advantage of interpretability, less parameters, and good robustness to noise, and can be applied to large-scale data sets with less computational cost. Therefore, the decision tree is still one of the hotspots in the field of machine learning today [1–3]. The research mainly focused on the construction method of decision trees, split criterion [4], decision trees ensemble [5, 6], mixing with other learners [7–9], decision trees for semisupervised learning [10], and so on.Despite practical success, the optimal construction of decision trees has been theoretically proven to be NP-complete [11]. In order to avoid the local optimal solution, some researchers adopted evolutionary algorithms to build decision trees [12–14]. However, due to the time complexity, the most popular algorithms, such as ID3 [15], C4.5 [16], and CART [17], and their various modifications [18] are greedy by nature and construct the decision tree in a top-down, recursive manner. Besides, they only act on one dimension at a time and thus result in an axis-parallel split. In the induction of decision tree, if the candidate features are numerical, a suitable cut point needs to be searched. Instances in the training set are divided into the left node or the right node according to the following formula:(1)xl≤θl,where xl denotes the value of the instance on the feature Al and θl is the cut point.Axis-parallel trees have the advantages of fast induction and strong comprehensibility. However, in the case of highly correlated features, a very bad situation may arise. Figure1 gives an illustration. The parallel splits will be carried out many times with a stair case-like structure, which leads to the complexity of the decision tree structure.Figure 1
Axis-parallel splits and oblique split.To solve the problem of parallel decision trees, some researchers introduced oblique decision trees. In such oblique decision trees, the nonleaf node tests the linear combination of features, i.e.,(2)∑i=1palxl≤θ,where al represents the coefficient for the lth feature, θ is the threshold, and p is the number of features. In Figure 1, the instances of the two classes can be completely separated by one oblique split. Therefore, it is generally believed that the oblique splits can often produce smaller decision trees and better generalization performance for the same data.It is much more difficult to search the optimal oblique hyperplanes than the optimal axis-parallel hyperplanes. To solve this problem, numerous techniques have been applied, for example, hill-climbing [17], simulated annealing [19], and genetic algorithm [20]. Among them, a large amount of research work has been done on reducing the risk of falling into local optimal solution, such as Simulated Annealing Decision Tree (SADT) [19], which used the simulated annealing algorithm; OC1 [21] method combined the ideas of CART-LC [17] and SADT.In searching oblique hyperplanes, thousands of candidates have been tried in both simulated annealing algorithm and genetic algorithm, resulting in low time efficiency. So many researchers used linear discriminant analysis, linear regression, perceptron, SVM, and other methods to find suitable oblique hyperplanes. Fisher’s decision tree (FDT) [22] takes advantage of dimensionality reduction of Fisher’s linear discriminant and uses the decomposition strategy of decision trees to come up with an oblique decision tree. FDT is only applicable to binary classification problems. Based on ADTree [23], Hong et al. [24] proposed the multivariate ADTree. Paper [24] presented and discussed the different variations of ADTree (Fisher’s ADTree, Sparse ADTree, and Regularized Logistic ADTree). Wickramarachchi et al. [25] explored a decision tree algorithm (HHCART). HHCART uses a series of Householder matrices to reflect the training data during tree construction. Shah and Sastry [26] defined separability of instances as the split criterion that optimized their evaluation function at each node and then presented the Alopex Perceptron Decision Tree algorithm for learning a decision tree. Menze et al. [27] presented an oblique tree forest method, which used LDA and ridge regression to conduct oblique splits.In the above oblique methods, the trees with fewer nodes and better accuracy can be obtained. However, there are also some deficiencies, mainly including three aspects.


### 1.1. Inability to Directly Employ the Methods for Categorical Data

The oblique splits use the linear combination of features. Therefore, the categorical features need to be converted into one or more numerical features [28]. This transformation may bring new biases to the classification problems, thus reducing the generalization ability of the models.


### 1.2. High Time Cost

The oblique splits always require complex matrix calculation when using linear discriminant analysis, ridge regression, or other methods. Although these methods are more efficient than simulated annealing and genetic algorithm, they still pay more cost than the axis-parallel methods, such as C4.5.


### 1.3. Some Methods Cannot Be Suitable for Multiclassification Problems

Generally, the oblique split methods conduct the binary splits. Although the binary tree can also be directly used for multiclassification problems, some binary splits rely on class label, such as FDA, original SVM, etc., which makes some algorithms like FDT in [22] limited to binary classification problems. In addition, some models need to convert multiclassification problems into binary ones [7].In order to overcome the above shortcomings, this paper proposes a multiway splits decision tree for multiple types of data (numerical, categorical, and mixed data). The specific characteristics of this method are as follows:(i)
Categorical features are handled directly.(ii)
The time complexity is similar to that of the axis-parallel split algorithms.(iii)
It is not necessary to convert multiclassification problems into binary ones by using the multiway splits directly.The remainder of the paper is organized as follows. In Section2, we review RELIEF-F and k-means algorithms briefly. Section 3 presents our algorithm and discusses its time complexity. Section 4 presents and analyzes the compared experimental results with other decision trees. The last section gives the conclusion of this paper.


## 1.1. Inability to Directly Employ the Methods for Categorical Data

The oblique splits use the linear combination of features. Therefore, the categorical features need to be converted into one or more numerical features [28]. This transformation may bring new biases to the classification problems, thus reducing the generalization ability of the models.


## 1.2. High Time Cost

The oblique splits always require complex matrix calculation when using linear discriminant analysis, ridge regression, or other methods. Although these methods are more efficient than simulated annealing and genetic algorithm, they still pay more cost than the axis-parallel methods, such as C4.5.


## 1.3. Some Methods Cannot Be Suitable for Multiclassification Problems

Generally, the oblique split methods conduct the binary splits. Although the binary tree can also be directly used for multiclassification problems, some binary splits rely on class label, such as FDA, original SVM, etc., which makes some algorithms like FDT in [22] limited to binary classification problems. In addition, some models need to convert multiclassification problems into binary ones [7].In order to overcome the above shortcomings, this paper proposes a multiway splits decision tree for multiple types of data (numerical, categorical, and mixed data). The specific characteristics of this method are as follows:(i)
Categorical features are handled directly.(ii)
The time complexity is similar to that of the axis-parallel split algorithms.(iii)
It is not necessary to convert multiclassification problems into binary ones by using the multiway splits directly.The remainder of the paper is organized as follows. In Section2, we review RELIEF-F and k-means algorithms briefly. Section 3 presents our algorithm and discusses its time complexity. Section 4 presents and analyzes the compared experimental results with other decision trees. The last section gives the conclusion of this paper.


## 2. Preliminaries

The proposed decision tree method needs to weight the features by RELIEF-F algorithm and split the nodes by the weightedk-means algorithm. Therefore, this section reviews the two algorithms and their variations.


### 2.1. RELIEF-F Algorithms

The RELIEF algorithm [29] is popular to feature selection. It estimates the weights of features according to the correlation between individual feature and class label. RELIEF randomly samples an instance R from the training set and then searches its two nearest neighbors H and M: H is from the same class (called near Hit) and M is from different class (called near Miss). If the distance between R and H on feature A is less than the distance between R and M, RELIEF will increase A’s weight. On the contrary, RELIEF will decrease the weight.In fact, RELIEF’s estimateWA of feature A is an approximation of the following difference of probabilities:(3)WA=Pdifferent value ofA|nearest instance from different class−Pdifferent value ofA|nearest instance from same class,where P⋅|⋅ represents the conditional probability.RELIEF algorithm only deals with binary classification problems. Kononeill addressed an algorithm called RELIEF-F for multiclassification problems [30]. The algorithm picks m instances. For each instance R, its knn nearest neighbors are searched in each class.The weightWA is calculated as follows:(4)WA=WA−∑j=1knndiffA,R,Hjmknn+∑T∉classRpT/1−pclassR∑j=1knndiffA,R,MjTmknn,where pT represents the proportion of class T instances to the total instances and MjT represents the jth nearest neighbor to R in class T. diffA,R1,R2 calculates the difference between two instances R1 and R2 on the feature A as follows:(5)diffA,R1,R2=R1A−R2AmaxA−minA,ifAis numerical,0,ifAis categorical AndR1A=R2A,1,ifAis categorical AndR1A≠R2A.


### 2.2.k-Means, k-Modes, and k-Prototypes

Thek-means is widely used in real world applications due to its simplicity and efficiency.LetD be a set of n instances. D is characterized by a set of p features and needs to be clustered into k clusters C1,C2,…,Ck. First, randomly pick some instances as the centers of the initial k clusters μ1,μ2,…,μk, and then calculate the cluster label for each instance xi as follows:(6)labeli=argmin1≤j≤kxi−μj.After all the instances are partitioned, each cluster center will be updated by the following formula:(7)μj=1nj∑i=1njxi,xi∈Cj.Repeat formulas (6) and (7) until the variable E in formula (8) converges to the local optimal solution or the preset number of iterations is reached:(8)E=∑j=1k∑i=1njxi−μj2,xi∈Cj.However, the classicalk-means is only worked on the numerical data. The k-modes and k-prototypes are variants of k-means for categorical and mixed data, respectively [31]. When k-modes processes the categorical variables, the center of each cluster is represented by modes. When calculating the distance between instance and cluster center, the distance on each feature is calculated by formula (5) and then accumulated.It is straightforward to integrate thek-means and k-modes into the k-prototypes. disxi,μj is the distance between instance xi and cluster center μj as follows:(9)disxi,μj=1−γ⋅dis_nxi,μj+γ⋅dis_cxi,μj,where dis_nxi,μj represents the distance on the numerical variables and dis_cxi,μj represents the distance on the categorical variables, respectively. γ is used to adjust the proportion of dis_nxi,μj and dis_cxi,μj, γ∈0,1.


## 2.1. RELIEF-F Algorithms

The RELIEF algorithm [29] is popular to feature selection. It estimates the weights of features according to the correlation between individual feature and class label. RELIEF randomly samples an instance R from the training set and then searches its two nearest neighbors H and M: H is from the same class (called near Hit) and M is from different class (called near Miss). If the distance between R and H on feature A is less than the distance between R and M, RELIEF will increase A’s weight. On the contrary, RELIEF will decrease the weight.In fact, RELIEF’s estimateWA of feature A is an approximation of the following difference of probabilities:(3)WA=Pdifferent value ofA|nearest instance from different class−Pdifferent value ofA|nearest instance from same class,where P⋅|⋅ represents the conditional probability.RELIEF algorithm only deals with binary classification problems. Kononeill addressed an algorithm called RELIEF-F for multiclassification problems [30]. The algorithm picks m instances. For each instance R, its knn nearest neighbors are searched in each class.The weightWA is calculated as follows:(4)WA=WA−∑j=1knndiffA,R,Hjmknn+∑T∉classRpT/1−pclassR∑j=1knndiffA,R,MjTmknn,where pT represents the proportion of class T instances to the total instances and MjT represents the jth nearest neighbor to R in class T. diffA,R1,R2 calculates the difference between two instances R1 and R2 on the feature A as follows:(5)diffA,R1,R2=R1A−R2AmaxA−minA,ifAis numerical,0,ifAis categorical AndR1A=R2A,1,ifAis categorical AndR1A≠R2A.


## 2.2.k-Means, k-Modes, and k-Prototypes

Thek-means is widely used in real world applications due to its simplicity and efficiency.LetD be a set of n instances. D is characterized by a set of p features and needs to be clustered into k clusters C1,C2,…,Ck. First, randomly pick some instances as the centers of the initial k clusters μ1,μ2,…,μk, and then calculate the cluster label for each instance xi as follows:(6)labeli=argmin1≤j≤kxi−μj.After all the instances are partitioned, each cluster center will be updated by the following formula:(7)μj=1nj∑i=1njxi,xi∈Cj.Repeat formulas (6) and (7) until the variable E in formula (8) converges to the local optimal solution or the preset number of iterations is reached:(8)E=∑j=1k∑i=1njxi−μj2,xi∈Cj.However, the classicalk-means is only worked on the numerical data. The k-modes and k-prototypes are variants of k-means for categorical and mixed data, respectively [31]. When k-modes processes the categorical variables, the center of each cluster is represented by modes. When calculating the distance between instance and cluster center, the distance on each feature is calculated by formula (5) and then accumulated.It is straightforward to integrate thek-means and k-modes into the k-prototypes. disxi,μj is the distance between instance xi and cluster center μj as follows:(9)disxi,μj=1−γ⋅dis_nxi,μj+γ⋅dis_cxi,μj,where dis_nxi,μj represents the distance on the numerical variables and dis_cxi,μj represents the distance on the categorical variables, respectively. γ is used to adjust the proportion of dis_nxi,μj and dis_cxi,μj, γ∈0,1.


## 3. Our Proposed Algorithm

Our proposed MSDT has three differences with most oblique methods: (i) MSDT does not use greedy methods to pursue maximum impurity reduction, (ii) MSDT uses a combination of multiple variables to do multiway splits for nonleaf nodes, and (iii) MSDT treats categorical features in a similar way to numerical features.


### 3.1. Multiway Splits

Most oblique methods conduct binary splits, while the proposed algorithm performs multiway splits; that is, in one split, multiple hyperplanes are generated simultaneously, and the feature space is divided into several disjoint regions. Ho [32] categorized the linear split methods into three types, axis-parallel linear splits, oblique linear splits, and piecewise linear splits, while our method falls into the third. Piecewise linear split methods find k anchors in feature space, and each instance is clustered according to the nearest neighbor anchor. Figure 2 shows the 5-way splits of the two-dimensional feature space.Figure 2
Piecewise linear splits.


### 3.2. Location of Anchor

Finding suitable split hyperplanes is the key problem in most decision tree induction algorithms. Under piecewise linear splits, the problem of finding appropriate hyperplanes is equivalent to that of finding appropriate anchors. Usually, anchor selection can use the class centroids, or cluster centers generated by some clustering algorithms. In MSDT, we first use RELIEF-F to weight features and then usek-means with weighted distance to cluster instances.


#### 3.2.1. Why Do We Usek-Means?

If the instances are linearly separable, it is obviously more efficient to use simply the class centroids than cluster centers as anchors. However, when the instances of some classes are distributed in different regions of the feature space, the class centroids may no longer be suitable for being anchors. For example, in Figure3, the circular instances are distributed in two different areas. If the solid line that is perpendicular to the line between the two class centroids is used to separate the instances, the effect is obviously not satisfactory. The instances in Figure 3 are obviously distributed into two clusters. If the instances are divided by the dotted line that is a perpendicular bisector of the two cluster centers, at least the circular instances on the right side of the figure can be distinguished.Figure 3
Split results of class centroids as anchors and cluster centers as anchors.The split method proposed is based on clustering assumption. The clustering assumption states that the samples belonging to the same cluster belong to the same class.k-means methods partition instances according to some (dis)similarity measures; hence, the leaf nodes of MSDT can be regarded as some prototypes, and the class of a test instance depends on which prototype the instance is more similar to.The univariate decision trees can produce a comprehensible classification mode, due to the knowledge representation method—a decision tree is a graphical representation and can be easily converted into a set of rules written in a natural language. Some researchers believe that multivariate decision trees are not able to convert into the comprehensible rules. The other researchers think that multivariate tree with fewer nodes is easy to understand. MSDT is easy to understand due to two reasons. One is that MSDT has fewer nodes compared to univariate decision trees. The other one is that the similarity with the prototype is easy to understand by the users and it can replace the rules generated by the univariate decision tree.


#### 3.2.2. Why Do We Weight Features?

The originalk-means is an unsupervised clustering algorithm, which is suitable for unlabeled data. And the optimization goal is to minimize (8). The goal of split is to reduce the class impurity of current node as much as possible. Note that the two goals are not the same. Therefore, we estimate the correlations between features and label to weight features. When calculating the distance from an instance to a cluster center, we give a larger weight to the feature strongly related to the label that enlarges the contribution of the feature to the distance. Otherwise, we give a smaller weight that reduces the contribution of the uncorrelated feature to the distance. In this way, the optimization goal of k-means algorithm is close to that of node split.Figure4 shows an example to illustrate the effectiveness of feature weighting. The solid line comes from unweighted features, and the dotted line comes from weighted features when the weight of A1 is 0.05 and the weight of A2 is 0.95. It is obvious that some instances have been corrected.Figure 4
Split results of unweighted and weighted features.To further illustrate the role of feature weighting, we use datasetiris to carry out a simple experiment: 150 samples of dataset iris come from three classes, and each class has 50 samples. We directly use k-means algorithm to cluster and obtain 10 misclassified samples. The specific results are shown in Table 1.Table 1
Split results of unweighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20444Child node 30646Then, we use the RELIEF-F algorithm to calculate the weights of four features, which are 0.09, 0.14, 0.34, and 0.39, respectively. In the process ofk-means clustering, the distances between instances and cluster centers are calculated by (10), where p indicates the number of features and wl indicates the weight of the lth feature. We obtain 6 misclassified samples, and the specific results are shown in Table 2.(10)xi−μj=∑l=1pwl⋅xi,l−μj,l2.Table 2
Split results of weighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20484Child node 30246Our proposed split method is shown in Algorithm1, which will be used to split nodes for numerical data.Algorithm 1: Multi_split.
Input: Current node training set DOutput: Divide D as C1,C2,…,Ck, cluster centers μ1,μ2,…,μk, the weights w(1)
Initialize the number of clustersk with the number of classes in D.(2)
InputD, call RELIEF-F to generate w.(3)
Assignwmax with maximum in w, excludes features whose weight is less than β⋅wmax, β∈0,1, 0.2 by default.(4)
Initializeμ1,μ2,…,μk by using the class centroids in D.(5)
For 1 to lmaxDo(6)
Combining formulas (6) and (10), divide instances into C1,C2,…,Ck(7)
Recalculateμ1,μ2,…,μk according to formula (7).(8)
Ifμ1,μ2,…,μk do not change significantly Then break For(9)
End For(10)
ReturnC1,C2,…,Ck, μ1,μ2,…,μk and wIn the fifth step of Algorithm1, lmax represents the maximum number of iterations. In the experiments, we set it to 6 by default. The reason for setting such a small value is mainly to consider the time efficiency of the algorithm. In addition, the purpose of clustering is to split nodes. Even if the clustering algorithm does not converge, the partition results can still be accepted.


### 3.3. Categorical Feature

As mentioned in the previous subsection, the split method can be directly applied to numerical features. For categorical features, RELIEF-F algorithm can still be used to weight features. However, in the process of clustering, the representation of cluster center and the distance from instance to cluster center need to be redefined.Thek-modes extends the k-means by replacing the means of numerical variables with the modes of the categorical variables. Yet it is less precise to calculate the distance. What is more, choosing different modes may cause opposite conclusion while there are several modes for a feature.Here is an example. Suppose there are two clustersC1 and C2 described by two categorical features A1 and A2, and each cluster contains 10 instances as is shown in Table 3. The modes of C1 and C2 for A1 are a11, which makes A1 useless for distinguishing the distances between instances and the clusters. There are two modes for A2 in C1 and C2, respectively. Suppose that there is an instance q=a11,a21; if μ1=a11,a21 is selected as the center of C1 and μ2=a11,a23 for C2, distance between q and μ1 is 0 and distance between q and μ2 is 1; hence, q is nearer to C1. If μ1=a11,a22 is selected as the center of C1 and μ2=a11,a21 for C2, distance between q and μ1 is 1 and distance between q and μ2 is 0; hence, q is nearer to C2.Table 3
The distribution of values.
A1feature1A2feature2C1cluster1a11:9,a12:1a21:4,a22:4,a23:2C2cluster2a11:4,a12:3.a13:3a21:4,a23:4,a24:2To avoid the less precision and the ambiguity of distance measure on the modes, we use the probability estimation of each categorical feature value to represent the cluster center and define a function to calculate the distance from instance to cluster center.LetD be a set of categorical data described by p categorical features. Number of instances in D is n and instances are partitioned into k clusters. There are di,j with different values ω1,ω2,…,ωdi,j for the lth feature Al of the jth cluster Cj, l∈1,2,…,p,j∈1,2,…,k.Definition 1.
Cj,xl represents the set of instances with value of xl on the feature Al in Cj, where xl∈ω1,ω2,…,ωdl,jx1∈ω1,ω2,…,ωdl,j. The condition probability is estimated as follows:(11)Pxl|j=Cj,xlCj,Sj,l is the summary of all values of Al in Cj, defined as follows:(12)Sj,l=Pω1|j,Pω2|j,…,Pωd|j.Definition 2.
The center ofCj is represented by the following vector:(13)μj=Sj,1,Sj,2,…,Sj,p.Definition 3.
diffAl,ω,Sj,l represents the distance between value ω and Sj,l for Al:(14)diffAl,ω,Sj,l=1−Pω|j,ifω∈ω1,ω2,…,ωd,1,others.Definition 4.
dis_cxi,μj represents the weighted distance between instance xi and center μj:(15)dis_cxi,μj=∑l=1pwl⋅diffAl,xi,l,Sj,l.
According to formula (15), in the above example, the weights of two features are 1. The distances between instance q=a11,a21 and two cluster centers (μ1 and μ2) in Table 3 are 0.7 = 0.1 + 0.6 and 1.2 = 0.6 + 0.6, respectively. It means that q is closer to C1, which is in accordance with the human’s intuition.
To cluster categorical data, we use formula (13) to replace formula (7) in step 4 and step 7 of Algorithm 1 and formula (15) to formula (10) in step 6.


### 3.4. Mixed Features Data

For mixed data, the vector of cluster center consists of two parts: one is the means of numerical features and the other is the vector as shown in (13). In this case, we use (9) to calculate the distance from instance to cluster center, where dis_n and dis_c are obtained by (10) and (15), respectively. As the ratio of numerical and categorical features differs by the datasets, we choose γ in (9) that makes the most reduction of GINI index, where γ∈0.1,0.2,…,0.9.


### 3.5. MSDT and Time Complexity Analysis

The multi_split function is prompted for node splits. Algorithm2 describes the construction process of MSDT.Algorithm 2: MSDT.
Input: training set D and the threshold value minparentOutput: the decision tree(1)
Createnode according to the instances in D.(2)
Proceduregrow(node)(3)
IfD is less than the minparent or the instances are not partitionable (All the instances are of the same class or have the same feature values) Then(4)
marknode as a leaf, and label it with the class of the majority of instances in D.(5)
Returnnode(6)
End If(7)
Callmulti_split to get the cluster C1,C2,…,Ck, μ1,μ2,…,μk, and w.(8)
Save the values ofμ1,μ2,…,μk, and w into the current node for the prediction.(9)
Fori = 1 to kDo(10)
Createnode_i according to instances in Ci, call grow(node_i).(11)
End For(12)
End Procedure(13)
Prune thenode-rooted tree by pessimistic pruning algorithm.(14)
Return the node-rooted decision tree.In step 2 of Algorithm1, RELIEF-F is used to get the weights. Time complexity of RELIEF-F is Om⋅p⋅n⋅log2km, where p is the feature number, n is the instance number, m is the sampling number, and knn is the nearest neighbor number. In this paper, m is set log2n,knn is set 1, and log2knn is negligible, so the time complexity of RELIEF-F in this paper is Op⋅n⋅log2n.Steps 4 to 9 of Algorithm1 are the clustering process, and the time complexity is OI⋅p⋅n⋅k, where k is cluster number and I is iteration number. When we use Algorithm 1 to split nodes, the max iterations Imax is 6; it means that time complexity may reach O6⋅p⋅n⋅k in the worst case.Considering the above two parts, the time complexity of Algorithm1 is O6k+log2n⋅p⋅n. Compared with the time complexity of the classical axis-parallel splits, there is an extra k. When k is large, this algorithm is lower efficiency than the axis-parallel algorithms. Compared with binary splits, if the node numbers of the decision trees are the same, the operations in k-way splits are obviously less than in binary splits.OC1 [21] is a classic oblique decision tree, whose time complexity is Op⋅n2⋅log2n in the worst case. In [25], the time complexities of HHCART(A) and HHCART(D) are Op+n⋅log2n⋅p2⋅k and Op+log2n⋅p⋅n⋅k, respectively. In [22], the speed of FDT for splitting node is close to or even better than that of axis-parallel split method. The time complexity of this method is Op2⋅n. Unfortunately, it can only be applied in binary classification problems.In summary, whenk is small, the efficiency of the proposed split method is close to classical axis-parallel split methods, and it is better than most oblique split methods.


## 3.1. Multiway Splits

Most oblique methods conduct binary splits, while the proposed algorithm performs multiway splits; that is, in one split, multiple hyperplanes are generated simultaneously, and the feature space is divided into several disjoint regions. Ho [32] categorized the linear split methods into three types, axis-parallel linear splits, oblique linear splits, and piecewise linear splits, while our method falls into the third. Piecewise linear split methods find k anchors in feature space, and each instance is clustered according to the nearest neighbor anchor. Figure 2 shows the 5-way splits of the two-dimensional feature space.Figure 2
Piecewise linear splits.


## 3.2. Location of Anchor

Finding suitable split hyperplanes is the key problem in most decision tree induction algorithms. Under piecewise linear splits, the problem of finding appropriate hyperplanes is equivalent to that of finding appropriate anchors. Usually, anchor selection can use the class centroids, or cluster centers generated by some clustering algorithms. In MSDT, we first use RELIEF-F to weight features and then usek-means with weighted distance to cluster instances.


### 3.2.1. Why Do We Usek-Means?

If the instances are linearly separable, it is obviously more efficient to use simply the class centroids than cluster centers as anchors. However, when the instances of some classes are distributed in different regions of the feature space, the class centroids may no longer be suitable for being anchors. For example, in Figure3, the circular instances are distributed in two different areas. If the solid line that is perpendicular to the line between the two class centroids is used to separate the instances, the effect is obviously not satisfactory. The instances in Figure 3 are obviously distributed into two clusters. If the instances are divided by the dotted line that is a perpendicular bisector of the two cluster centers, at least the circular instances on the right side of the figure can be distinguished.Figure 3
Split results of class centroids as anchors and cluster centers as anchors.The split method proposed is based on clustering assumption. The clustering assumption states that the samples belonging to the same cluster belong to the same class.k-means methods partition instances according to some (dis)similarity measures; hence, the leaf nodes of MSDT can be regarded as some prototypes, and the class of a test instance depends on which prototype the instance is more similar to.The univariate decision trees can produce a comprehensible classification mode, due to the knowledge representation method—a decision tree is a graphical representation and can be easily converted into a set of rules written in a natural language. Some researchers believe that multivariate decision trees are not able to convert into the comprehensible rules. The other researchers think that multivariate tree with fewer nodes is easy to understand. MSDT is easy to understand due to two reasons. One is that MSDT has fewer nodes compared to univariate decision trees. The other one is that the similarity with the prototype is easy to understand by the users and it can replace the rules generated by the univariate decision tree.


### 3.2.2. Why Do We Weight Features?

The originalk-means is an unsupervised clustering algorithm, which is suitable for unlabeled data. And the optimization goal is to minimize (8). The goal of split is to reduce the class impurity of current node as much as possible. Note that the two goals are not the same. Therefore, we estimate the correlations between features and label to weight features. When calculating the distance from an instance to a cluster center, we give a larger weight to the feature strongly related to the label that enlarges the contribution of the feature to the distance. Otherwise, we give a smaller weight that reduces the contribution of the uncorrelated feature to the distance. In this way, the optimization goal of k-means algorithm is close to that of node split.Figure4 shows an example to illustrate the effectiveness of feature weighting. The solid line comes from unweighted features, and the dotted line comes from weighted features when the weight of A1 is 0.05 and the weight of A2 is 0.95. It is obvious that some instances have been corrected.Figure 4
Split results of unweighted and weighted features.To further illustrate the role of feature weighting, we use datasetiris to carry out a simple experiment: 150 samples of dataset iris come from three classes, and each class has 50 samples. We directly use k-means algorithm to cluster and obtain 10 misclassified samples. The specific results are shown in Table 1.Table 1
Split results of unweighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20444Child node 30646Then, we use the RELIEF-F algorithm to calculate the weights of four features, which are 0.09, 0.14, 0.34, and 0.39, respectively. In the process ofk-means clustering, the distances between instances and cluster centers are calculated by (10), where p indicates the number of features and wl indicates the weight of the lth feature. We obtain 6 misclassified samples, and the specific results are shown in Table 2.(10)xi−μj=∑l=1pwl⋅xi,l−μj,l2.Table 2
Split results of weighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20484Child node 30246Our proposed split method is shown in Algorithm1, which will be used to split nodes for numerical data.Algorithm 1: Multi_split.
Input: Current node training set DOutput: Divide D as C1,C2,…,Ck, cluster centers μ1,μ2,…,μk, the weights w(1)
Initialize the number of clustersk with the number of classes in D.(2)
InputD, call RELIEF-F to generate w.(3)
Assignwmax with maximum in w, excludes features whose weight is less than β⋅wmax, β∈0,1, 0.2 by default.(4)
Initializeμ1,μ2,…,μk by using the class centroids in D.(5)
For 1 to lmaxDo(6)
Combining formulas (6) and (10), divide instances into C1,C2,…,Ck(7)
Recalculateμ1,μ2,…,μk according to formula (7).(8)
Ifμ1,μ2,…,μk do not change significantly Then break For(9)
End For(10)
ReturnC1,C2,…,Ck, μ1,μ2,…,μk and wIn the fifth step of Algorithm1, lmax represents the maximum number of iterations. In the experiments, we set it to 6 by default. The reason for setting such a small value is mainly to consider the time efficiency of the algorithm. In addition, the purpose of clustering is to split nodes. Even if the clustering algorithm does not converge, the partition results can still be accepted.


## 3.2.1. Why Do We Usek-Means?

If the instances are linearly separable, it is obviously more efficient to use simply the class centroids than cluster centers as anchors. However, when the instances of some classes are distributed in different regions of the feature space, the class centroids may no longer be suitable for being anchors. For example, in Figure3, the circular instances are distributed in two different areas. If the solid line that is perpendicular to the line between the two class centroids is used to separate the instances, the effect is obviously not satisfactory. The instances in Figure 3 are obviously distributed into two clusters. If the instances are divided by the dotted line that is a perpendicular bisector of the two cluster centers, at least the circular instances on the right side of the figure can be distinguished.Figure 3
Split results of class centroids as anchors and cluster centers as anchors.The split method proposed is based on clustering assumption. The clustering assumption states that the samples belonging to the same cluster belong to the same class.k-means methods partition instances according to some (dis)similarity measures; hence, the leaf nodes of MSDT can be regarded as some prototypes, and the class of a test instance depends on which prototype the instance is more similar to.The univariate decision trees can produce a comprehensible classification mode, due to the knowledge representation method—a decision tree is a graphical representation and can be easily converted into a set of rules written in a natural language. Some researchers believe that multivariate decision trees are not able to convert into the comprehensible rules. The other researchers think that multivariate tree with fewer nodes is easy to understand. MSDT is easy to understand due to two reasons. One is that MSDT has fewer nodes compared to univariate decision trees. The other one is that the similarity with the prototype is easy to understand by the users and it can replace the rules generated by the univariate decision tree.


## 3.2.2. Why Do We Weight Features?

The originalk-means is an unsupervised clustering algorithm, which is suitable for unlabeled data. And the optimization goal is to minimize (8). The goal of split is to reduce the class impurity of current node as much as possible. Note that the two goals are not the same. Therefore, we estimate the correlations between features and label to weight features. When calculating the distance from an instance to a cluster center, we give a larger weight to the feature strongly related to the label that enlarges the contribution of the feature to the distance. Otherwise, we give a smaller weight that reduces the contribution of the uncorrelated feature to the distance. In this way, the optimization goal of k-means algorithm is close to that of node split.Figure4 shows an example to illustrate the effectiveness of feature weighting. The solid line comes from unweighted features, and the dotted line comes from weighted features when the weight of A1 is 0.05 and the weight of A2 is 0.95. It is obvious that some instances have been corrected.Figure 4
Split results of unweighted and weighted features.To further illustrate the role of feature weighting, we use datasetiris to carry out a simple experiment: 150 samples of dataset iris come from three classes, and each class has 50 samples. We directly use k-means algorithm to cluster and obtain 10 misclassified samples. The specific results are shown in Table 1.Table 1
Split results of unweighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20444Child node 30646Then, we use the RELIEF-F algorithm to calculate the weights of four features, which are 0.09, 0.14, 0.34, and 0.39, respectively. In the process ofk-means clustering, the distances between instances and cluster centers are calculated by (10), where p indicates the number of features and wl indicates the weight of the lth feature. We obtain 6 misclassified samples, and the specific results are shown in Table 2.(10)xi−μj=∑l=1pwl⋅xi,l−μj,l2.Table 2
Split results of weighted features for theiris dataset.
SetosaVersicolorVirginicaChild node 15000Child node 20484Child node 30246Our proposed split method is shown in Algorithm1, which will be used to split nodes for numerical data.Algorithm 1: Multi_split.
Input: Current node training set DOutput: Divide D as C1,C2,…,Ck, cluster centers μ1,μ2,…,μk, the weights w(1)
Initialize the number of clustersk with the number of classes in D.(2)
InputD, call RELIEF-F to generate w.(3)
Assignwmax with maximum in w, excludes features whose weight is less than β⋅wmax, β∈0,1, 0.2 by default.(4)
Initializeμ1,μ2,…,μk by using the class centroids in D.(5)
For 1 to lmaxDo(6)
Combining formulas (6) and (10), divide instances into C1,C2,…,Ck(7)
Recalculateμ1,μ2,…,μk according to formula (7).(8)
Ifμ1,μ2,…,μk do not change significantly Then break For(9)
End For(10)
ReturnC1,C2,…,Ck, μ1,μ2,…,μk and wIn the fifth step of Algorithm1, lmax represents the maximum number of iterations. In the experiments, we set it to 6 by default. The reason for setting such a small value is mainly to consider the time efficiency of the algorithm. In addition, the purpose of clustering is to split nodes. Even if the clustering algorithm does not converge, the partition results can still be accepted.


## 3.3. Categorical Feature

As mentioned in the previous subsection, the split method can be directly applied to numerical features. For categorical features, RELIEF-F algorithm can still be used to weight features. However, in the process of clustering, the representation of cluster center and the distance from instance to cluster center need to be redefined.Thek-modes extends the k-means by replacing the means of numerical variables with the modes of the categorical variables. Yet it is less precise to calculate the distance. What is more, choosing different modes may cause opposite conclusion while there are several modes for a feature.Here is an example. Suppose there are two clustersC1 and C2 described by two categorical features A1 and A2, and each cluster contains 10 instances as is shown in Table 3. The modes of C1 and C2 for A1 are a11, which makes A1 useless for distinguishing the distances between instances and the clusters. There are two modes for A2 in C1 and C2, respectively. Suppose that there is an instance q=a11,a21; if μ1=a11,a21 is selected as the center of C1 and μ2=a11,a23 for C2, distance between q and μ1 is 0 and distance between q and μ2 is 1; hence, q is nearer to C1. If μ1=a11,a22 is selected as the center of C1 and μ2=a11,a21 for C2, distance between q and μ1 is 1 and distance between q and μ2 is 0; hence, q is nearer to C2.Table 3
The distribution of values.
A1feature1A2feature2C1cluster1a11:9,a12:1a21:4,a22:4,a23:2C2cluster2a11:4,a12:3.a13:3a21:4,a23:4,a24:2To avoid the less precision and the ambiguity of distance measure on the modes, we use the probability estimation of each categorical feature value to represent the cluster center and define a function to calculate the distance from instance to cluster center.LetD be a set of categorical data described by p categorical features. Number of instances in D is n and instances are partitioned into k clusters. There are di,j with different values ω1,ω2,…,ωdi,j for the lth feature Al of the jth cluster Cj, l∈1,2,…,p,j∈1,2,…,k.Definition 1.
Cj,xl represents the set of instances with value of xl on the feature Al in Cj, where xl∈ω1,ω2,…,ωdl,jx1∈ω1,ω2,…,ωdl,j. The condition probability is estimated as follows:(11)Pxl|j=Cj,xlCj,Sj,l is the summary of all values of Al in Cj, defined as follows:(12)Sj,l=Pω1|j,Pω2|j,…,Pωd|j.Definition 2.
The center ofCj is represented by the following vector:(13)μj=Sj,1,Sj,2,…,Sj,p.Definition 3.
diffAl,ω,Sj,l represents the distance between value ω and Sj,l for Al:(14)diffAl,ω,Sj,l=1−Pω|j,ifω∈ω1,ω2,…,ωd,1,others.Definition 4.
dis_cxi,μj represents the weighted distance between instance xi and center μj:(15)dis_cxi,μj=∑l=1pwl⋅diffAl,xi,l,Sj,l.
According to formula (15), in the above example, the weights of two features are 1. The distances between instance q=a11,a21 and two cluster centers (μ1 and μ2) in Table 3 are 0.7 = 0.1 + 0.6 and 1.2 = 0.6 + 0.6, respectively. It means that q is closer to C1, which is in accordance with the human’s intuition.
To cluster categorical data, we use formula (13) to replace formula (7) in step 4 and step 7 of Algorithm 1 and formula (15) to formula (10) in step 6.


## 3.4. Mixed Features Data

For mixed data, the vector of cluster center consists of two parts: one is the means of numerical features and the other is the vector as shown in (13). In this case, we use (9) to calculate the distance from instance to cluster center, where dis_n and dis_c are obtained by (10) and (15), respectively. As the ratio of numerical and categorical features differs by the datasets, we choose γ in (9) that makes the most reduction of GINI index, where γ∈0.1,0.2,…,0.9.


## 3.5. MSDT and Time Complexity Analysis

The multi_split function is prompted for node splits. Algorithm2 describes the construction process of MSDT.Algorithm 2: MSDT.
Input: training set D and the threshold value minparentOutput: the decision tree(1)
Createnode according to the instances in D.(2)
Proceduregrow(node)(3)
IfD is less than the minparent or the instances are not partitionable (All the instances are of the same class or have the same feature values) Then(4)
marknode as a leaf, and label it with the class of the majority of instances in D.(5)
Returnnode(6)
End If(7)
Callmulti_split to get the cluster C1,C2,…,Ck, μ1,μ2,…,μk, and w.(8)
Save the values ofμ1,μ2,…,μk, and w into the current node for the prediction.(9)
Fori = 1 to kDo(10)
Createnode_i according to instances in Ci, call grow(node_i).(11)
End For(12)
End Procedure(13)
Prune thenode-rooted tree by pessimistic pruning algorithm.(14)
Return the node-rooted decision tree.In step 2 of Algorithm1, RELIEF-F is used to get the weights. Time complexity of RELIEF-F is Om⋅p⋅n⋅log2km, where p is the feature number, n is the instance number, m is the sampling number, and knn is the nearest neighbor number. In this paper, m is set log2n,knn is set 1, and log2knn is negligible, so the time complexity of RELIEF-F in this paper is Op⋅n⋅log2n.Steps 4 to 9 of Algorithm1 are the clustering process, and the time complexity is OI⋅p⋅n⋅k, where k is cluster number and I is iteration number. When we use Algorithm 1 to split nodes, the max iterations Imax is 6; it means that time complexity may reach O6⋅p⋅n⋅k in the worst case.Considering the above two parts, the time complexity of Algorithm1 is O6k+log2n⋅p⋅n. Compared with the time complexity of the classical axis-parallel splits, there is an extra k. When k is large, this algorithm is lower efficiency than the axis-parallel algorithms. Compared with binary splits, if the node numbers of the decision trees are the same, the operations in k-way splits are obviously less than in binary splits.OC1 [21] is a classic oblique decision tree, whose time complexity is Op⋅n2⋅log2n in the worst case. In [25], the time complexities of HHCART(A) and HHCART(D) are Op+n⋅log2n⋅p2⋅k and Op+log2n⋅p⋅n⋅k, respectively. In [22], the speed of FDT for splitting node is close to or even better than that of axis-parallel split method. The time complexity of this method is Op2⋅n. Unfortunately, it can only be applied in binary classification problems.In summary, whenk is small, the efficiency of the proposed split method is close to classical axis-parallel split methods, and it is better than most oblique split methods.


## 4. Experiments

In this section, we use experimental results to demonstrate the effectiveness and performance of our proposed algorithm. In the first part, the experiments are used to illustrate the effectiveness of clustering, feature weighting, and the novel distance calculation method for categorical feature. The second parts compare MSDT with classical decision trees and another two oblique trees. Finally, we use a larger dataset covertype to compare with two axis-parallel trees.


### 4.1. Datasets

As shown in Table4, the 20 UCI datasets [33] are used to evaluate the proposed algorithm, where the number of instances, the number of classes, and feature types (numerical data 1–10, categorical data 11–15, and mixed data 16–20) are varied and are sufficiently representative to demonstrate the performance of MSDT. In column Features with pn&pc,pnandpc is number of numerical features and categorical features, respectively. Abalone is treated as a 3-category classification problem (grouping classes 1–8, 9 and 10, and 11 on).Table 4
Datasets.
No.NameAbb.InstancesFeaturesClasses1Blood Transfusion Service CenterBlood748422Glass identificationGlass214963Image segmentationImage21301974IrisIris150435Letter recognitionLetter2000016266Multiple features-morMF-mor20006107Waveform database generator (version 1)Wav150002138Waveform database generator (version 2)Wav250004039WineWine17813310YeastYeast148481011Balance scaleBalance6254312Car evaluationCar17286413Chess (King-Rook vs. King-Pawn)Chess319636214Hayes-RothHayes1604315MONK’s problemsMONK4326216AbaloneAbalone41777&1317Contraceptive method choiceCMC14732&7318FlagsFlags19410&19819Teaching assistant evaluationTAE1511&4320ZooZoo10115&17


### 4.2. Comparison of Different Piecewise Linear Split Methods

The piecewise linear split methods can be summarized as two steps. First, find appropriate anchors. Then, divide instances according to the nearest anchor. On the basis of this approach, our proposed algorithm is improved in three aspects: feature weighting, clustering, and special categorical feature processing. This section combines these three changes into multiple functions and compares the performances in multiple types of data. These functions are shown in Table5.Table 5
Split function description.
Function nameFunction descriptionFeature weightingClusteringCluster center and distance of categorical featureFun 0✗✗k-modesFun 1✓✗k-modesFun 2✗✓k-modesFun 3✓✓k-modesFun 4✗✗Definitions1–4Fun 5✓✗Definitions1–4Fun 6✗✓Definitions1–4Fun 7✓✓Definitions1–4The pessimistic pruning algorithm is adopted after the decision trees are generated. In addition, the average results of all experiments are obtained by 10 repetitions of 10-fold cross-validation.


#### 4.2.1. Numerical Data

In terms of numerical data, the proposed algorithm uses weightedk-means to optimize cluster center position. In order to demonstrate the role of clustering and feature weighting, we implement four different node split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. Instances are divided according to the nearest anchor. Euclidean distance is used for distance calculation. Fun1 also uses the center of each class as the anchor. However, in the process of selecting the nearest anchor for each instance, RELIEF-F is firstly used to calculate the weight of each feature. Then remove features whose weights are less than 1/5 of the maximum. Finally, the distance is calculated according to formula (10). Fun2 uses the center of each class as the initial cluster center of k-means and the outputs of k-means as the partition results. Fun3 combines Fun1 with Fun2 and is our proposed algorithm for numerical data.Table6 gives the classification accuracy of the 4 functions in 10 datasets, and the best entry in each row is bolded. As can be seen, Fun3 gets the best accuracy on 9 of 10 datasets and the average improvement is 4.16% higher than Fun0. In particular, the accuracy increases by more than 8% on Glass and Letter. The average accuracy of 10 datasets shows that Fun1 is about 1.07% higher than Fun0, and Fun3 is 1.39% higher than Fun2. The results show that feature weighting improves the classification performance. Fun2 is about 2.77% higher than Fun0, and Fun3 is 3.09% higher than Fun1. The reason for improvement is using clustering.Table 6
Comparison of the accuracy for different splitting functions on numerical data (%).
Fun 0Fun 1Fun 2Fun 3Blood76.4476.7877.0277.53Glass61.6863.4666.9270.47Image91.6892.5694.7996.01Iris91.4096.0093.0796Letter72.9678.1889.6191.77MF-mor69.7770.0070.4871.13Wav182.3081.7680.9282.30Wav280.5880.3579.3480.65Wine95.7393.6095.5695.11Yeast52.6353.1955.1455.84Average77.5278.5980.2981.68


#### 4.2.2. Categorical and Mixed Data

On the categorical and mixed data, we implement eight different split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. For categorical features, modes are used to replace the means of numerical features as the component of anchors. When calculating the distance between instance and anchor, the distance on each feature is calculated by formula (5) and then summed. The difference between Fun1 and Fun0 is that the weight of each feature is calculated by RELIEF-F. Then remove features whose weights are less than 1/5 of the maximum. The distance between the instance and the anchor is obtained by formula (15) and formula (9). Fun2 adds clustering process on Fun0. k-modes and k-prototypes are used for categorical data and mixed data, respectively. Fun3 combines Fun1 and Fun2. Fun4-7 corresponds to Fun0-3 respectively. On the categorical features, the calculation of cluster centers and distances adopts the method described in Section 3.3 (formulas (13) and (15), respectively). Fun7 is our proposed algorithm for categorical and mixed data.Table7 gives the classification accuracy of the 8 functions in 5 categorical datasets (Balance, Car, Chess, Hayes, and MONK) and 5 mixed datasets (Abalone, CMC, Flags, TAE, and Zoo), and the best entry in each row is bolded. Except for CMC and Zoo, Fun7 obtains the best accuracy, and the average is 11.77% higher than Fun0. As can be seen, Fun1 is better than Fun0, Fun3 is better than Fun2, Fun5 is better than Fun4, and Fun7 is better than Fun6. The average improvement is 5.37%. This is the contribution of feature weighting. It is shown that Fun2 is better than Fun0, Fun3 is better than Fun1, Fun6 is better than Fun4, and Fun7 is better than Fun5. The average improvement is 4.45%. The reason is the use of clustering. Meanwhile, we can see that Fun4-7 is averagely 1.48% better than Fun0-3. This improvement is the statistical distribution of feature values instead of modes.Table 7
Comparison of the accuracy for different splitting functions on categorical and mixed data.
Fun 0Fun 1Fun 2Fun 3Fun 4Fun 5Fun6Fun 7Balance72.5170.7573.4273.4768.9471.0469.2376.45Car74.8886.1176.8989.4881.9283.7692.7396.45Chess80.0595.6690.4295.9671.5193.6892.6299.17Hayes71.0076.8872.0077.8859.2571.5666.6979.75MONK73.9885.2383.9488.0388.8097.4188.1799.63Abalone59.1259.4461.3361.4650.5655.6661.6662.84CMC45.1944.3149.0445.6643.1345.1044.6047.95Flags47.0157.0650.3160.0547.7359.1248.7662.42TAE47.7549.0759.4753.9756.5658.4161.8563.77Zoo95.6496.7395.7496.5395.5496.0495.7496.34Average66.7172.1271.2674.2566.3973.1872.2178.48


### 4.3. Comparison with Other Decision Trees

In order to verify the performance of our proposed algorithm, we selected four decision trees: J48 (WEKA’s implementation of C4.5), CARTSL (scikit-learn’s implementation of optimal CART), OC1, and HHCART(A). Since CARTSL and OC1 do not support categorical features, we convert categorical features to numerical features using the One Hot method. The 10 repetitions of 10-fold cross-validation were used in our experiments to report the average accuracy and tree size of 5 classifiers on the test set. Friedman test and Nemenyi test will be used to analyze the algorithm difference.The accuracy over the numerical datasets by each method is shown in Table8. As can be seen, MSDT gets the best accuracy on 5 of 10 datasets and the average accuracy is 81.68%. It is 1.91%, 4.42%, 1.15%, and 1.81% higher than other four trees, respectively. In order to further demonstrate the differences of the classifiers, the Friedman test is used. We use the averages of the ranks of 5 classifiers on 10 datasets to calculate FF=7.129032. Here, with 5 algorithms and 10 datasets, FF follows the F−distribution with 4 and 36 degrees of freedom, and the critical value is F4,36=2.634. So, we reject the null hypothesis; namely, there are significant differences among the five classifiers. Nemenyi method is used for post hoc test. Critical interval (CD) is obtained by the following formula:.(16)CD=qαkk+16N,where k is the number of algorithms and N is the number of datasets. When k=5, N=10 and significance α=0.05, qα=2.728, the calculated critical interval CD = 1.92899. In the case of these conclusions, the MSDT and OC1 have obvious performance advantages compared with CARTSL.Table 8
The accuracy of five classifiers on numerical data.
DatasetAccuracy % (rank)J48CARTSLOC1HHCART(A)MSDTBlood78.09 ± 0.50(1)70.51± 0.70(5)77.34± 0.56(3)76.50± 0.45(4)77.53± 0.68(2)Glass66.73± 2.84(3)66.59± 2.06(4)68.43± 2.80(2)64.02± 3.14(1)Image96.55± 0.26(3)96.32± 0.39(4)96.78± 0.33(2)97.22 ± 0.25(1)96.01± 0.40(5)Iris95.13± 0.73(3)95.07± 0.61(4)94.67± 0.62(5)95.33± 0.63(2)96.00 ± 0.00(1)Letter88.09± 0.23(5)88.19± 0.17(4)89.72± 0.20(2)88.23± 0.22(3)91.77 ± 0.16(1)MF-mor72.01 ± 0.62(1)65.11± 0.43(5)70.15± 0.48(3)69.83± 0.63(4)71.13± 0.43(2)Wav176.50± 0.32(4)75.38± 0.52(5)80.07± 0.33(2)79.83± 0.33(3)82.30 ± 0.32(1)Wav275.29± 0.61(4)74.27± 0.43(5)79.68± 0.56(2)79.01± 0.45(3)80.65 ± 0.42(1)Wine93.54± 0.88(3)90.00± 1.46(5)92.54± 0.98(4)94.47± 0.86(2)95.11 ± 1.23(1)Yeast55.77± 0.93(3)51.14± 1.01(5)55.90 ± 1.06(1)54.28± 1.11(4)55.84± 0.93(2)Average79.77(3)77.26(4.6)80.53(2.6)79.87(3.1)81.68(1.7)The accuracy over the categorical and mixed datasets by each method is shown in Table9. MSDT gets the best accuracy on 4 of 10 datasets and the average accuracy is 78.48%. It is 3.62%, 1.1%, 1.56%, and 1.88% higher than four other trees, respectively. We use the averages of the ranks of 5 classifiers on 10 datasets to calculate FF = 1.48951. Here, the critical value is F(4, 36) = 2.634. So, we cannot reject the null hypothesis; namely, there is no significant difference among the five classifiers. In the case of these conclusions, on categorical and mixed data, the advantages of three multivariate decision trees over two univariate decision trees are not so obvious. Especially in OC1, one categorical feature is transformed into multiple numerical features by One Hot method, which greatly increases the dimension of feature space. In the new feature space, the data becomes very sparse, and OC1 cannot find a suitable split hyperplanes.Table 9
The accuracy of five classifiers on categorical and mixed data.
DatasetAccuracy % (rank)J48CARTSLOC1HHCART(A)MSDTBalance64.00± 1.18(5)76.91± 0.82(3)80.36± 1.49(2)82.82 ± 1.12(1)76.45± 2.05(4)Car92.52± 0.63(5)97.31 ± 0.22(1)96.27± 0.76(4)96.91± 0.53(2)96.45± 0.23(3)Chess99.41± 0.10(2)99.54 ± 0.06(1)98.58± 0.15(5)99.23± 0.17(3)99.17± 0.21(4)Hayes75.13± 1.55(5)83.00 ± 1.52(1)79.26± 1.56(3)76.37± 1.16(4)79.75± 2.14(2)MONK96.11± 1.54(3)91.94± 1.51(5)93.37± 1.53(4)98.57± 1.58(2)99.63 ± 0.85(1)Abalone61.30± 0.45(2)57.52± 0.54(5)60.05± 0.34(3)59.29± 0.43(4)62.84 ± 0.28(1)CMC51.61 ± 0.66(1)47.40± 0.47(4)46.92± 1.46(5)47.83± 0.73(3)47.95± 1.38(2)Flags64.34 ± 3.34(1)61.96± 1.03(3)60.35± 3.62(5)61.73± 1.49(4)62.42± 2.04(2)TAE51.43± 4.67(5)62.91± 1.87(3)63.10± 3.97(2)53.26± 4.57(4)63.77 ± 3.79(1)Zoo92.77± 0.01(3)95.35± 0.00(2)90.98± 0.33(4)89.99± 0.02(5)96.34 ± 0.45(1)Average74.86(3.2)77.38(2.8)76.92(3.7)76.60(3.2)78.48(2.1)The tree size over 20 datasets by each method is shown in Table10. In terms of the complexity of model structure, the average number of nodes in three multivariate decision tree is lower than the other two univariate decision trees. We use the averages of the ranks of 5 classifiers on 20 datasets to calculate FF = 3.35294. Here, with 5 algorithms and 20 datasets, FF follows the F-distribution with 4 and 76 degrees of freedom, and the critical value is F(4, 76) = 2.492. So, we reject the null hypothesis. Nemenyi method is used for post hoc test. Critical interval is obtained; CD = 1.364. In the case of these conclusions, the MSDT has obvious performance advantages compared with J48.Table 10
The tree size of five classifiers.
DatasetTree size (rank)J48CARTSLOC1HHCART(A)MSDTBlood12.60± 0.87(2)179.64± 1.00(5)7.88 ± 0.75(1)16.56± 0.88(3)32.72± 2.50(4)Glass46.68± 1.66(5)44.93± 0.56(3)32.65± 0.78(2)27.73 ± 0.67(1)46.55± 2.15(4)Image80.28± 1.28(4)69.22± 0.79(2)57.62 ± 0.93(1)70.43± 1.46(3)161.59± 4.57(5)Iris8.40± 0.24(4)8.56± 0.14(5)5.10± 0.08(2)5.60± 0.12(3)4.00 ± 0.00(1)Letter2326.72± 9.04(5)2098.23± 9.34(3)2285.22± 9.81(4)1795.23 ± 8.91(1)1893.41± 11.64(2)MF-mor162.40± 5.54(2)462.94± 1.89(5)153.32 ± 3.55(1)212.97± 4.74(4)174.07± 1.29(3)Wav1546.74± 7.62(5)484.45± 2.61(4)470.26± 6.17(3)465.34± 6.62(2)178.12 ± 5.12(1)Wav2585.42± 9.45(5)453.02± 1.73(2)481.54± 8.05(4)480.38± 9.17(3)126.18 ± 10.69(1)Wine9.54± 0.31(4)10.47± 0.62(5)9.25± 0.30(3)7.83± 0.27(2)4.00 ± 0.72(1)Yeast328.70± 4.12(4)463.38± 2.33(5)260.47± 9.81(2)303.25± 6.40(3)101.52 ± 9.00(1)Balance42.05± 1.31(2)140.83± 1.47(4)159.93± 2.36(5)57.82± 1.42(3)31.13 ± 5.48(1)Car170.45± 1.27(4)97.18± 1.11(2)91.46 ± 1.19(1)186.54± 2.28(5)141.60± 1.32(3)Chess54.66± 1.07(4)52.15± 0.64(2)53.70± 0.96(3)49.62 ± 1.38(1)106.96± 2.90(5)Hayes27.13± 0.55(4)22.09± 0.33(3)20.73± 0.47(2)29.75± 0.51(5)18.63 ± 0.94(1)MONK39.14± 1.83(3)59.09± 6.33(5)56.28± 5.92(4)20.93± 3.41(2)18.54 ± 1.08(1)Abalone589.00± 18.45(3)965.09± 2.66(5)679.45± 13.25(4)401.11± 9.52(2)270.67 ± 19.72(1)CMC247.16± 6.21(3)611.94± 3.87(5)538.95± 8.36(4)108.92 ± 4.78(1)139.64± 6.33(2)Flags62.63± 2.07(5)45.01± 0.52(3)39.87± 1.28(2)54.28± 2.11(4)26.86 ± 1.74(1)TAE93.01± 3.75(4)56.40± 0.53(2)50.57 ± 0.66(1)68.82± 0.72(3)114.40± 1.76(5)Zoo11.00± 0.00(3)9.65 ± 0.00(1)12.07± 0.23(5)10.53± 0.07(2)11.08± 0.57(4)Average272.19(3.75)316.71(3.55)273.32(2.7)218.68 (2.65)180.08 (2.35)


### 4.4. Comparison on Big Data

The data setcovertype comes from UCI [35], which is a 7-classification problem, which includes 581012 instances and 54 features. 10 of 54 features are numerical, and the remainders are Boolean. MSDT and J48 regard Boolean as categorical features, and CARTSL is regarded as numerical features. The 10 repetitions of 10-fold cross-validation are used. Table 11 provides the accuracy of the three classifiers, the size of the tree, and the time to build the tree.Table 11
The performance of three classifiers on covertype
J48CARTSLMSDTAccuracy (%)94.58±0.0994.30±0.1194.64±0.12Tree size28348.11±274.8351728.89±347.5925736.90±235.86Time (s)71.61±1.5245.58±0.56150.12±2.66The three classifiers achieve similar accuracies oncovertype. In terms of tree size, MSDT has the least number of nodes. The running time provided in Table 11 is the time to build a tree and does not include the time consumed by loading data and testing. J48 runs slower than CARTSL, which does not mean that there is a significant difference in time complexity between the two algorithms. The difference may be caused by the different development language. There are two reasons why MSDT gets the most expensive time consumption. One is that the time complexity of our proposed method is higher than that of the axis-parallel methods when dividing a node. The other one is that the axis-parallel methods mainly perform relational operations, for instance, “<.” Our method needs to calculate a large number of distances, which requires arithmetic operations of real number. Although multiway splits can reduce the number of times to split nodes, the time consumed by our method is about 2 to 3 times that of the axis-parallel methods from the experimental results.


## 4.1. Datasets

As shown in Table4, the 20 UCI datasets [33] are used to evaluate the proposed algorithm, where the number of instances, the number of classes, and feature types (numerical data 1–10, categorical data 11–15, and mixed data 16–20) are varied and are sufficiently representative to demonstrate the performance of MSDT. In column Features with pn&pc,pnandpc is number of numerical features and categorical features, respectively. Abalone is treated as a 3-category classification problem (grouping classes 1–8, 9 and 10, and 11 on).Table 4
Datasets.
No.NameAbb.InstancesFeaturesClasses1Blood Transfusion Service CenterBlood748422Glass identificationGlass214963Image segmentationImage21301974IrisIris150435Letter recognitionLetter2000016266Multiple features-morMF-mor20006107Waveform database generator (version 1)Wav150002138Waveform database generator (version 2)Wav250004039WineWine17813310YeastYeast148481011Balance scaleBalance6254312Car evaluationCar17286413Chess (King-Rook vs. King-Pawn)Chess319636214Hayes-RothHayes1604315MONK’s problemsMONK4326216AbaloneAbalone41777&1317Contraceptive method choiceCMC14732&7318FlagsFlags19410&19819Teaching assistant evaluationTAE1511&4320ZooZoo10115&17


## 4.2. Comparison of Different Piecewise Linear Split Methods

The piecewise linear split methods can be summarized as two steps. First, find appropriate anchors. Then, divide instances according to the nearest anchor. On the basis of this approach, our proposed algorithm is improved in three aspects: feature weighting, clustering, and special categorical feature processing. This section combines these three changes into multiple functions and compares the performances in multiple types of data. These functions are shown in Table5.Table 5
Split function description.
Function nameFunction descriptionFeature weightingClusteringCluster center and distance of categorical featureFun 0✗✗k-modesFun 1✓✗k-modesFun 2✗✓k-modesFun 3✓✓k-modesFun 4✗✗Definitions1–4Fun 5✓✗Definitions1–4Fun 6✗✓Definitions1–4Fun 7✓✓Definitions1–4The pessimistic pruning algorithm is adopted after the decision trees are generated. In addition, the average results of all experiments are obtained by 10 repetitions of 10-fold cross-validation.


### 4.2.1. Numerical Data

In terms of numerical data, the proposed algorithm uses weightedk-means to optimize cluster center position. In order to demonstrate the role of clustering and feature weighting, we implement four different node split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. Instances are divided according to the nearest anchor. Euclidean distance is used for distance calculation. Fun1 also uses the center of each class as the anchor. However, in the process of selecting the nearest anchor for each instance, RELIEF-F is firstly used to calculate the weight of each feature. Then remove features whose weights are less than 1/5 of the maximum. Finally, the distance is calculated according to formula (10). Fun2 uses the center of each class as the initial cluster center of k-means and the outputs of k-means as the partition results. Fun3 combines Fun1 with Fun2 and is our proposed algorithm for numerical data.Table6 gives the classification accuracy of the 4 functions in 10 datasets, and the best entry in each row is bolded. As can be seen, Fun3 gets the best accuracy on 9 of 10 datasets and the average improvement is 4.16% higher than Fun0. In particular, the accuracy increases by more than 8% on Glass and Letter. The average accuracy of 10 datasets shows that Fun1 is about 1.07% higher than Fun0, and Fun3 is 1.39% higher than Fun2. The results show that feature weighting improves the classification performance. Fun2 is about 2.77% higher than Fun0, and Fun3 is 3.09% higher than Fun1. The reason for improvement is using clustering.Table 6
Comparison of the accuracy for different splitting functions on numerical data (%).
Fun 0Fun 1Fun 2Fun 3Blood76.4476.7877.0277.53Glass61.6863.4666.9270.47Image91.6892.5694.7996.01Iris91.4096.0093.0796Letter72.9678.1889.6191.77MF-mor69.7770.0070.4871.13Wav182.3081.7680.9282.30Wav280.5880.3579.3480.65Wine95.7393.6095.5695.11Yeast52.6353.1955.1455.84Average77.5278.5980.2981.68


### 4.2.2. Categorical and Mixed Data

On the categorical and mixed data, we implement eight different split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. For categorical features, modes are used to replace the means of numerical features as the component of anchors. When calculating the distance between instance and anchor, the distance on each feature is calculated by formula (5) and then summed. The difference between Fun1 and Fun0 is that the weight of each feature is calculated by RELIEF-F. Then remove features whose weights are less than 1/5 of the maximum. The distance between the instance and the anchor is obtained by formula (15) and formula (9). Fun2 adds clustering process on Fun0. k-modes and k-prototypes are used for categorical data and mixed data, respectively. Fun3 combines Fun1 and Fun2. Fun4-7 corresponds to Fun0-3 respectively. On the categorical features, the calculation of cluster centers and distances adopts the method described in Section 3.3 (formulas (13) and (15), respectively). Fun7 is our proposed algorithm for categorical and mixed data.Table7 gives the classification accuracy of the 8 functions in 5 categorical datasets (Balance, Car, Chess, Hayes, and MONK) and 5 mixed datasets (Abalone, CMC, Flags, TAE, and Zoo), and the best entry in each row is bolded. Except for CMC and Zoo, Fun7 obtains the best accuracy, and the average is 11.77% higher than Fun0. As can be seen, Fun1 is better than Fun0, Fun3 is better than Fun2, Fun5 is better than Fun4, and Fun7 is better than Fun6. The average improvement is 5.37%. This is the contribution of feature weighting. It is shown that Fun2 is better than Fun0, Fun3 is better than Fun1, Fun6 is better than Fun4, and Fun7 is better than Fun5. The average improvement is 4.45%. The reason is the use of clustering. Meanwhile, we can see that Fun4-7 is averagely 1.48% better than Fun0-3. This improvement is the statistical distribution of feature values instead of modes.Table 7
Comparison of the accuracy for different splitting functions on categorical and mixed data.
Fun 0Fun 1Fun 2Fun 3Fun 4Fun 5Fun6Fun 7Balance72.5170.7573.4273.4768.9471.0469.2376.45Car74.8886.1176.8989.4881.9283.7692.7396.45Chess80.0595.6690.4295.9671.5193.6892.6299.17Hayes71.0076.8872.0077.8859.2571.5666.6979.75MONK73.9885.2383.9488.0388.8097.4188.1799.63Abalone59.1259.4461.3361.4650.5655.6661.6662.84CMC45.1944.3149.0445.6643.1345.1044.6047.95Flags47.0157.0650.3160.0547.7359.1248.7662.42TAE47.7549.0759.4753.9756.5658.4161.8563.77Zoo95.6496.7395.7496.5395.5496.0495.7496.34Average66.7172.1271.2674.2566.3973.1872.2178.48


## 4.2.1. Numerical Data

In terms of numerical data, the proposed algorithm uses weightedk-means to optimize cluster center position. In order to demonstrate the role of clustering and feature weighting, we implement four different node split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. Instances are divided according to the nearest anchor. Euclidean distance is used for distance calculation. Fun1 also uses the center of each class as the anchor. However, in the process of selecting the nearest anchor for each instance, RELIEF-F is firstly used to calculate the weight of each feature. Then remove features whose weights are less than 1/5 of the maximum. Finally, the distance is calculated according to formula (10). Fun2 uses the center of each class as the initial cluster center of k-means and the outputs of k-means as the partition results. Fun3 combines Fun1 with Fun2 and is our proposed algorithm for numerical data.Table6 gives the classification accuracy of the 4 functions in 10 datasets, and the best entry in each row is bolded. As can be seen, Fun3 gets the best accuracy on 9 of 10 datasets and the average improvement is 4.16% higher than Fun0. In particular, the accuracy increases by more than 8% on Glass and Letter. The average accuracy of 10 datasets shows that Fun1 is about 1.07% higher than Fun0, and Fun3 is 1.39% higher than Fun2. The results show that feature weighting improves the classification performance. Fun2 is about 2.77% higher than Fun0, and Fun3 is 3.09% higher than Fun1. The reason for improvement is using clustering.Table 6
Comparison of the accuracy for different splitting functions on numerical data (%).
Fun 0Fun 1Fun 2Fun 3Blood76.4476.7877.0277.53Glass61.6863.4666.9270.47Image91.6892.5694.7996.01Iris91.4096.0093.0796Letter72.9678.1889.6191.77MF-mor69.7770.0070.4871.13Wav182.3081.7680.9282.30Wav280.5880.3579.3480.65Wine95.7393.6095.5695.11Yeast52.6353.1955.1455.84Average77.5278.5980.2981.68


## 4.2.2. Categorical and Mixed Data

On the categorical and mixed data, we implement eight different split functions to generate decision trees. Fun0 directly uses the center of each class as the anchor. For categorical features, modes are used to replace the means of numerical features as the component of anchors. When calculating the distance between instance and anchor, the distance on each feature is calculated by formula (5) and then summed. The difference between Fun1 and Fun0 is that the weight of each feature is calculated by RELIEF-F. Then remove features whose weights are less than 1/5 of the maximum. The distance between the instance and the anchor is obtained by formula (15) and formula (9). Fun2 adds clustering process on Fun0. k-modes and k-prototypes are used for categorical data and mixed data, respectively. Fun3 combines Fun1 and Fun2. Fun4-7 corresponds to Fun0-3 respectively. On the categorical features, the calculation of cluster centers and distances adopts the method described in Section 3.3 (formulas (13) and (15), respectively). Fun7 is our proposed algorithm for categorical and mixed data.Table7 gives the classification accuracy of the 8 functions in 5 categorical datasets (Balance, Car, Chess, Hayes, and MONK) and 5 mixed datasets (Abalone, CMC, Flags, TAE, and Zoo), and the best entry in each row is bolded. Except for CMC and Zoo, Fun7 obtains the best accuracy, and the average is 11.77% higher than Fun0. As can be seen, Fun1 is better than Fun0, Fun3 is better than Fun2, Fun5 is better than Fun4, and Fun7 is better than Fun6. The average improvement is 5.37%. This is the contribution of feature weighting. It is shown that Fun2 is better than Fun0, Fun3 is better than Fun1, Fun6 is better than Fun4, and Fun7 is better than Fun5. The average improvement is 4.45%. The reason is the use of clustering. Meanwhile, we can see that Fun4-7 is averagely 1.48% better than Fun0-3. This improvement is the statistical distribution of feature values instead of modes.Table 7
Comparison of the accuracy for different splitting functions on categorical and mixed data.
Fun 0Fun 1Fun 2Fun 3Fun 4Fun 5Fun6Fun 7Balance72.5170.7573.4273.4768.9471.0469.2376.45Car74.8886.1176.8989.4881.9283.7692.7396.45Chess80.0595.6690.4295.9671.5193.6892.6299.17Hayes71.0076.8872.0077.8859.2571.5666.6979.75MONK73.9885.2383.9488.0388.8097.4188.1799.63Abalone59.1259.4461.3361.4650.5655.6661.6662.84CMC45.1944.3149.0445.6643.1345.1044.6047.95Flags47.0157.0650.3160.0547.7359.1248.7662.42TAE47.7549.0759.4753.9756.5658.4161.8563.77Zoo95.6496.7395.7496.5395.5496.0495.7496.34Average66.7172.1271.2674.2566.3973.1872.2178.48


## 4.3. Comparison with Other Decision Trees

In order to verify the performance of our proposed algorithm, we selected four decision trees: J48 (WEKA’s implementation of C4.5), CARTSL (scikit-learn’s implementation of optimal CART), OC1, and HHCART(A). Since CARTSL and OC1 do not support categorical features, we convert categorical features to numerical features using the One Hot method. The 10 repetitions of 10-fold cross-validation were used in our experiments to report the average accuracy and tree size of 5 classifiers on the test set. Friedman test and Nemenyi test will be used to analyze the algorithm difference.The accuracy over the numerical datasets by each method is shown in Table8. As can be seen, MSDT gets the best accuracy on 5 of 10 datasets and the average accuracy is 81.68%. It is 1.91%, 4.42%, 1.15%, and 1.81% higher than other four trees, respectively. In order to further demonstrate the differences of the classifiers, the Friedman test is used. We use the averages of the ranks of 5 classifiers on 10 datasets to calculate FF=7.129032. Here, with 5 algorithms and 10 datasets, FF follows the F−distribution with 4 and 36 degrees of freedom, and the critical value is F4,36=2.634. So, we reject the null hypothesis; namely, there are significant differences among the five classifiers. Nemenyi method is used for post hoc test. Critical interval (CD) is obtained by the following formula:.(16)CD=qαkk+16N,where k is the number of algorithms and N is the number of datasets. When k=5, N=10 and significance α=0.05, qα=2.728, the calculated critical interval CD = 1.92899. In the case of these conclusions, the MSDT and OC1 have obvious performance advantages compared with CARTSL.Table 8
The accuracy of five classifiers on numerical data.
DatasetAccuracy % (rank)J48CARTSLOC1HHCART(A)MSDTBlood78.09 ± 0.50(1)70.51± 0.70(5)77.34± 0.56(3)76.50± 0.45(4)77.53± 0.68(2)Glass66.73± 2.84(3)66.59± 2.06(4)68.43± 2.80(2)64.02± 3.14(1)Image96.55± 0.26(3)96.32± 0.39(4)96.78± 0.33(2)97.22 ± 0.25(1)96.01± 0.40(5)Iris95.13± 0.73(3)95.07± 0.61(4)94.67± 0.62(5)95.33± 0.63(2)96.00 ± 0.00(1)Letter88.09± 0.23(5)88.19± 0.17(4)89.72± 0.20(2)88.23± 0.22(3)91.77 ± 0.16(1)MF-mor72.01 ± 0.62(1)65.11± 0.43(5)70.15± 0.48(3)69.83± 0.63(4)71.13± 0.43(2)Wav176.50± 0.32(4)75.38± 0.52(5)80.07± 0.33(2)79.83± 0.33(3)82.30 ± 0.32(1)Wav275.29± 0.61(4)74.27± 0.43(5)79.68± 0.56(2)79.01± 0.45(3)80.65 ± 0.42(1)Wine93.54± 0.88(3)90.00± 1.46(5)92.54± 0.98(4)94.47± 0.86(2)95.11 ± 1.23(1)Yeast55.77± 0.93(3)51.14± 1.01(5)55.90 ± 1.06(1)54.28± 1.11(4)55.84± 0.93(2)Average79.77(3)77.26(4.6)80.53(2.6)79.87(3.1)81.68(1.7)The accuracy over the categorical and mixed datasets by each method is shown in Table9. MSDT gets the best accuracy on 4 of 10 datasets and the average accuracy is 78.48%. It is 3.62%, 1.1%, 1.56%, and 1.88% higher than four other trees, respectively. We use the averages of the ranks of 5 classifiers on 10 datasets to calculate FF = 1.48951. Here, the critical value is F(4, 36) = 2.634. So, we cannot reject the null hypothesis; namely, there is no significant difference among the five classifiers. In the case of these conclusions, on categorical and mixed data, the advantages of three multivariate decision trees over two univariate decision trees are not so obvious. Especially in OC1, one categorical feature is transformed into multiple numerical features by One Hot method, which greatly increases the dimension of feature space. In the new feature space, the data becomes very sparse, and OC1 cannot find a suitable split hyperplanes.Table 9
The accuracy of five classifiers on categorical and mixed data.
DatasetAccuracy % (rank)J48CARTSLOC1HHCART(A)MSDTBalance64.00± 1.18(5)76.91± 0.82(3)80.36± 1.49(2)82.82 ± 1.12(1)76.45± 2.05(4)Car92.52± 0.63(5)97.31 ± 0.22(1)96.27± 0.76(4)96.91± 0.53(2)96.45± 0.23(3)Chess99.41± 0.10(2)99.54 ± 0.06(1)98.58± 0.15(5)99.23± 0.17(3)99.17± 0.21(4)Hayes75.13± 1.55(5)83.00 ± 1.52(1)79.26± 1.56(3)76.37± 1.16(4)79.75± 2.14(2)MONK96.11± 1.54(3)91.94± 1.51(5)93.37± 1.53(4)98.57± 1.58(2)99.63 ± 0.85(1)Abalone61.30± 0.45(2)57.52± 0.54(5)60.05± 0.34(3)59.29± 0.43(4)62.84 ± 0.28(1)CMC51.61 ± 0.66(1)47.40± 0.47(4)46.92± 1.46(5)47.83± 0.73(3)47.95± 1.38(2)Flags64.34 ± 3.34(1)61.96± 1.03(3)60.35± 3.62(5)61.73± 1.49(4)62.42± 2.04(2)TAE51.43± 4.67(5)62.91± 1.87(3)63.10± 3.97(2)53.26± 4.57(4)63.77 ± 3.79(1)Zoo92.77± 0.01(3)95.35± 0.00(2)90.98± 0.33(4)89.99± 0.02(5)96.34 ± 0.45(1)Average74.86(3.2)77.38(2.8)76.92(3.7)76.60(3.2)78.48(2.1)The tree size over 20 datasets by each method is shown in Table10. In terms of the complexity of model structure, the average number of nodes in three multivariate decision tree is lower than the other two univariate decision trees. We use the averages of the ranks of 5 classifiers on 20 datasets to calculate FF = 3.35294. Here, with 5 algorithms and 20 datasets, FF follows the F-distribution with 4 and 76 degrees of freedom, and the critical value is F(4, 76) = 2.492. So, we reject the null hypothesis. Nemenyi method is used for post hoc test. Critical interval is obtained; CD = 1.364. In the case of these conclusions, the MSDT has obvious performance advantages compared with J48.Table 10
The tree size of five classifiers.
DatasetTree size (rank)J48CARTSLOC1HHCART(A)MSDTBlood12.60± 0.87(2)179.64± 1.00(5)7.88 ± 0.75(1)16.56± 0.88(3)32.72± 2.50(4)Glass46.68± 1.66(5)44.93± 0.56(3)32.65± 0.78(2)27.73 ± 0.67(1)46.55± 2.15(4)Image80.28± 1.28(4)69.22± 0.79(2)57.62 ± 0.93(1)70.43± 1.46(3)161.59± 4.57(5)Iris8.40± 0.24(4)8.56± 0.14(5)5.10± 0.08(2)5.60± 0.12(3)4.00 ± 0.00(1)Letter2326.72± 9.04(5)2098.23± 9.34(3)2285.22± 9.81(4)1795.23 ± 8.91(1)1893.41± 11.64(2)MF-mor162.40± 5.54(2)462.94± 1.89(5)153.32 ± 3.55(1)212.97± 4.74(4)174.07± 1.29(3)Wav1546.74± 7.62(5)484.45± 2.61(4)470.26± 6.17(3)465.34± 6.62(2)178.12 ± 5.12(1)Wav2585.42± 9.45(5)453.02± 1.73(2)481.54± 8.05(4)480.38± 9.17(3)126.18 ± 10.69(1)Wine9.54± 0.31(4)10.47± 0.62(5)9.25± 0.30(3)7.83± 0.27(2)4.00 ± 0.72(1)Yeast328.70± 4.12(4)463.38± 2.33(5)260.47± 9.81(2)303.25± 6.40(3)101.52 ± 9.00(1)Balance42.05± 1.31(2)140.83± 1.47(4)159.93± 2.36(5)57.82± 1.42(3)31.13 ± 5.48(1)Car170.45± 1.27(4)97.18± 1.11(2)91.46 ± 1.19(1)186.54± 2.28(5)141.60± 1.32(3)Chess54.66± 1.07(4)52.15± 0.64(2)53.70± 0.96(3)49.62 ± 1.38(1)106.96± 2.90(5)Hayes27.13± 0.55(4)22.09± 0.33(3)20.73± 0.47(2)29.75± 0.51(5)18.63 ± 0.94(1)MONK39.14± 1.83(3)59.09± 6.33(5)56.28± 5.92(4)20.93± 3.41(2)18.54 ± 1.08(1)Abalone589.00± 18.45(3)965.09± 2.66(5)679.45± 13.25(4)401.11± 9.52(2)270.67 ± 19.72(1)CMC247.16± 6.21(3)611.94± 3.87(5)538.95± 8.36(4)108.92 ± 4.78(1)139.64± 6.33(2)Flags62.63± 2.07(5)45.01± 0.52(3)39.87± 1.28(2)54.28± 2.11(4)26.86 ± 1.74(1)TAE93.01± 3.75(4)56.40± 0.53(2)50.57 ± 0.66(1)68.82± 0.72(3)114.40± 1.76(5)Zoo11.00± 0.00(3)9.65 ± 0.00(1)12.07± 0.23(5)10.53± 0.07(2)11.08± 0.57(4)Average272.19(3.75)316.71(3.55)273.32(2.7)218.68 (2.65)180.08 (2.35)


## 4.4. Comparison on Big Data

The data setcovertype comes from UCI [35], which is a 7-classification problem, which includes 581012 instances and 54 features. 10 of 54 features are numerical, and the remainders are Boolean. MSDT and J48 regard Boolean as categorical features, and CARTSL is regarded as numerical features. The 10 repetitions of 10-fold cross-validation are used. Table 11 provides the accuracy of the three classifiers, the size of the tree, and the time to build the tree.Table 11
The performance of three classifiers on covertype
J48CARTSLMSDTAccuracy (%)94.58±0.0994.30±0.1194.64±0.12Tree size28348.11±274.8351728.89±347.5925736.90±235.86Time (s)71.61±1.5245.58±0.56150.12±2.66The three classifiers achieve similar accuracies oncovertype. In terms of tree size, MSDT has the least number of nodes. The running time provided in Table 11 is the time to build a tree and does not include the time consumed by loading data and testing. J48 runs slower than CARTSL, which does not mean that there is a significant difference in time complexity between the two algorithms. The difference may be caused by the different development language. There are two reasons why MSDT gets the most expensive time consumption. One is that the time complexity of our proposed method is higher than that of the axis-parallel methods when dividing a node. The other one is that the axis-parallel methods mainly perform relational operations, for instance, “<.” Our method needs to calculate a large number of distances, which requires arithmetic operations of real number. Although multiway splits can reduce the number of times to split nodes, the time consumed by our method is about 2 to 3 times that of the axis-parallel methods from the experimental results.


## 5. Conclusion

The decision trees generated by the oblique splits often have better generalization ability and fewer nodes. However, most oblique split methods are time-consuming and cannot be directly used for categorical data, and some of these methods can only be used for binary classification problems. Our proposed algorithm MSDT uses feature weighting and clustering to multiway splits of nonleaf nodes, which can be directly applied to multiclassification problems. Meanwhile, it has a time complexity similar to that of the axis-parallel algorithms. In addition, we give the representation of cluster center and the distance from instance to cluster center, which enables clustering to be used in categorical and mixed data. Experimental results show that MSDT has a good generalization accuracy on multiple types of data.



---

*Source: 7870534-2020-11-16.xml*