0
$\begingroup$

Is it possible that the order of features will change the accuracy of an SVM RBF kernel based classifier? I'm also interested in whether this would affect other ML classification algorithms, if applicable?

For example, if you have 5 features, and you order the columns differently:

1 2 3 4 5

5 4 3 2 1

1 5 2 4 3

Will all of these always produce the same result?

$\endgroup$
1
$\begingroup$

In general, it should not make a difference. For many methods (Naive Bayes, Decision Trees, Regression) this is not a factor. For SVM, it may depend on the type of SVM and the method used to solve it - if the algorithm used is approximate, or not run to convergence, or involves randomness that may lead to somewhat different results.

$\endgroup$
1
  • 1
    $\begingroup$ I would also add that if you choose an asymmetric kernel for SVM (I can't think of why you'd want to), such as a radial gaussian with non-trivial covariance matrix, then the kernel will be sensitive to coordinate order, especially if the features have largely different distributions (even when normalized). $\endgroup$ – Alex R. Nov 15 '17 at 19:01
1
$\begingroup$

It is incorrect that the order of the attributes cannot affect the results for a decision tree. It can. In the standard approach for generating decision trees, one splits a node using the "best" attribute, where best is decided by the change in some purity metric like information gain or Gini index. But what if there is a tie - two attributes produce identical changes in the purity metric? There is no clear specification as to how the attribute is chosen, so any implementation makes an arbitrary choice - like the first attribute encountered with the maximal change in purity. Different decisions to resolve these ties will lead to completely different trees.

I will provide a small example using R and the rpart library which implements CART. This is not a problem with CART. Other decision tree algorithms can be shown to have the same problem.

library(rpart)

## The data
V1 = rep(c("A", "B"), each=30)
V2 = c(rep("C", 12), rep("D", 30), rep("C", 18))
V3 = c(rep("F", 21), rep("E", 9), rep("F", 21), rep("E", 9))
class = c(rep("X", 21), rep("Y", 30), rep("X", 9))
Dat = data.frame(V1, V2, V3, class)

table(V1,class)
   class
V1   X  Y
  A 21  9
  B  9 21
table(V2,class)
   class
V2   X  Y
  C 21  9
  D  9 21

You can see that splitting on V1 or V2 will give identical distributions of the class variable, the same number of instances - not the same instances. That is, they will produce the same change in the purity metric.

rpart(class ~ ., Dat)
n= 60 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

1) root 60 30 X (0.5000000 0.5000000)  
  2) V1=A 30  9 X (0.7000000 0.3000000)  
    4) V3=F 21  0 X (1.0000000 0.0000000) *
    5) V3=E 9  0 Y (0.0000000 1.0000000) *
  3) V1=B 30  9 Y (0.3000000 0.7000000)  
    6) V3=E 9  0 X (1.0000000 0.0000000) *
    7) V3=F 21  0 Y (0.0000000 1.0000000) *

rpart(class ~ ., Dat[,c(2,1,3,4)])
n= 60 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

1) root 60 30 X (0.5000000 0.5000000)  
  2) V2=C 30  9 X (0.7000000 0.3000000) *
  3) V2=D 30  9 Y (0.3000000 0.7000000) *

You can also see that building a tree using the original order produces a different result from when V1 and V2 are switched. Not only is the tree different, the accuracy (on the training data) is quite different for the two trees: 100% and 70%.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.