Multivariate decision trees for machine learning

4.2.Class Separation by Selection Method

1. 
   Select an initial partition, C_L and C_R where each part only consists of examples of two arbitrarily chosen classes C_i and C_j respectively.
   
2. 
   Train the network at node t with the given partition. Do not consider the elements of other classes yet.
   
3. 
   For other classes in the class list, search for the class C_k that is best placed into one of the partitions. Best placing is the placing when C_k is assigned into the child where the impurity is minimum.
   
4. 
   Put C_k into its best partition and continue adding classes one by one using steps 2 to 4 until no more classes are left.
   

Algorithm traces steps 2 to 4 c-2 times. So the complexity of this algorithm is O(c) where c is the number of the class available at node t.

4.3.Class Separation by Exchange Method

1. 
   Select an initial partition of all in classes into two subsets, C_L and C_R.
   
2. 
   Train the network to separate C_L and C_R. Compute the entropy E₀ with the selected entropy formulae.
   
3. 
   For each of the classes k  {C₁, …, C_c} form the partitions C_L(k) and C_R(k) by changing the assignment of the class C_k in the partitions C_L and C_R. Train the neural network with the partitions C_L(k) and C_R(k). Compute the entropy E_k and the decrease in the entropy E_k=E_k-E₀.
   
4. 
   Let E_* be the maximum of the impurity decreases for all classes. If this impurity decrease is less than 0 then exit else set C_L = C_L(k) and C_R = C_R(k), and do the steps 2 to 4 again.
   

1. 
   The two classes C_i and C_j with the maximum distance are found and placed into C_L and C_R.
   
2. 
   For each of the classes k  {C₁, …, C_c} find the one with the minimum distance to C_L or C_R and then put it into that group. Repeat this second step until no more classes are left.
   

5.THE STATISTICAL MODEL FOR TREE CONSTRUCTION

The statistical approach is named as Fisher’s Linear Discriminant Analysis (LDA) (Duda and Hart, 1973). This approach aims to find a linear combination of the variables that separates the two classes as much as possible, which is what we want to do. The criterion proposed by Fisher is the ratio of between-class to within-class variances, which we want to maximize. Formally we must find a direction w to maximize

where m_L and m_R are the two left and right groups means

and S_w is within-class covariance matrix, which is bias corrected as

where _L and _R are the covariance matrices of class groups C_L and C_R respectively.

There are n_L samples in the left class group and n_R samples in the right class group. The solution for w that maximizes J_F can be obtained by differentiating J_F with respect to w and equating it to zero. So we define w, namely the set of coefficients of the linear combination as:

But the coefficients of the features is only for the direction, we must also specify a threshold w₀, which is defined as:

Note however that though the direction given in Equation 5.3 has been derived without any assumptions of normality, normal assumptions are used in Equation 5.4 to set the threshold for discrimination.

So in our case, we first divide classes into two groups as C_L and C_R by an appropriate class selection procedure (as defined in Sections 4.2 or 4.3). But this time the inner optimization procedure will be carried out by LDA as we will find the linear split with the Equations 5.3 and 5.4. There will be no training but only simple calculations with matrices. So we expect less training time in LDA, than a neural network.

In implementing the idea, we see that if there is a linear dependency between two or more features then some of the rows or columns of the covariance matrix S_w are the same or a multiple of the other and it becomes singular. But in this case the determinant will be zero and we can not find S_w^-1.

A possible answer to the problem is PCA, which is principal component analysis (Rencher, 1995). In this analysis we first find the eigenvectors and eigenvalues of the matrix S_w. As the multiplication of the eigenvalues of a matrix is equal to the determinant, we sort the eigenvalues of the matrix and get rid of the eigenvectors with small eigenvalues. Let us say that the eigenvalues of the matrix S_w are λ₁, λ ₂ ... λ _f, which are sorted in decreasing order. We will find the new number of features k such that;

(5.7)

where  is the proportion of variance explained. k is the number of eigenvectors that are linearly independent. After finding k, we will find the corresponding k eigenvectors and store them. For each instance with f features, we will multiply it with the k eigenvectors to have a new instance with the number of features k. So our instance space is mapped from f dimensions into k dimensions. After this we will do LDA now with the mapped instances and find a new S_w and means and calculate the split. Now S_w can have an inverse so there is no problem.

In order to test the tree we will convert first the test instances into a space of k dimensions and then we will multiply the new test instance with the linear split found with LDA. If the result is greater then -w₀ this instance is assigned to the left subtree of the node else to the right subtree of the node.