2
$\begingroup$

I am trying to learn about Conditional Inference Trees, and have been doing some very simple comparisons of the ctree() and rpart() functions in R. I have looked at the documentation for ctree(), but sadly, I am too dense to figure out what it is doing in even the most elementary of cases.

Consider the following:

###################################################################

t20.a=c(rep(0,10),rep(1,10)) # 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
p20=c(1:20) # 1 2 3 4 5 6 7 8 9 1011121314151617181920
ctree(t20.a~p20) 

     Conditional inference tree with 2 terminal nodes

Response: t20.a
Input: p20
Number of observations: 20

1) p20 <= 10; criterion = 1, statistic = 14.286
2)* weights = 10
1) p20 > 10
3)* weights = 10
>

###################################################################

How is the "statistic = 14.286" value determined? Is there a statistic computed at every possible cut point, and 14.286 is the best value?

For contrast, if I were using Gini Impurity to try to determine where to split the tree, the values for the potential splits are:
left = (0) right = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.47368421
left = (0,0) right = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.44444444
left = (0,0,0) right = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.41176471
left = (0,0,0,0) right = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.37500000
left = (0,0,0,0,0) right = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.33333333
left = (0,0,0,0,0,0) right = (0,0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.28571429
left = (0,0,0,0,0,0,0) right = (0,0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.23076923
left = (0,0,0,0,0,0,0,0) right = (0,0,1,1,1,1,1,1,1,1,1,1) gini = 0.16666667
left = (0,0,0,0,0,0,0,0,0) right = (0,1,1,1,1,1,1,1,1,1,1) gini = 0.09090909
left = (0,0,0,0,0,0,0,0,0,0) right = (1,1,1,1,1,1,1,1,1,1) gini = 0.00000000
left = (0,0,0,0,0,0,0,0,0,0,1) right = (1,1,1,1,1,1,1,1,1) gini = 0.09090909
left = (0,0,0,0,0,0,0,0,0,0,1,1) right = (1,1,1,1,1,1,1,1) gini = 0.16666667
left = (0,0,0,0,0,0,0,0,0,0,1,1,1) right = (1,1,1,1,1,1,1) gini = 0.23076923
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1) right = (1,1,1,1,1,1) gini = 0.28571429
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1) right = (1,1,1,1,1) gini = 0.33333333
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1) right = (1,1,1,1) gini = 0.37500000
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1) right = (1,1,1) gini = 0.41176471
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1) right = (1,1) gini = 0.44444444
left = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1) right = (1) gini = 0.47368421

It's obvious by eye where the split should be, and the Gini impurity values confirm this. Recall that Gini impurity for a binary vector is just 1 - (f0*f0) - (f1*f1), where f0 is the fraction of zeroes and f1 is the fraction of ones. For each cut point, take the weighted sum of the left and right individual values.

So, what would be the set of split statistic values for the Conditional Inference Tree, and how are they computed?

One reason I am trying to understand at this level of detail (besides the general benefits of education) is that I have observed some possibly paradoxical behavior in the ctree() function, and I wonder whether this is either a mistake in the implementation of ctree(), or a flaw in the Conditional Inference Tree method, or perfectly correct as is.

Here is an example:

pat363=c(0,0,0,1,1,1,1,1,1,0,0,0)
pat363.xm=rep(pat363,each=10000)
seq363.xm=c(1:length(pat363.xm))
ctree(pat363.xm~seq363.xm) 

     Conditional inference tree with 1 terminal nodes

Response: pat363.xm
Input: seq363.xm
Number of observations: 120000

1)* weights = 120000

rpart(pat363.xm~seq363.xm)
n= 120000

node), split, n, deviance, yval
* denotes terminal node

1) root 120000 30000 0.5000000
2) seq363.xm< 30000.5 30000 0 0.0000000 *
3) seq363.xm>=30000.5 90000 20000 0.6666667
6) seq363.xm>=90000.5 30000 0 0.0000000 *
7) seq363.xm< 90000.5 60000 0 1.0000000 *

You can see three groups by eyeball, and rpart() finds them handily, but ctree() finds no splits. And this appears to be the case for any symmetric binary vector, i.e., if bivec is a vector of zeroes and ones, then symbivec=c(bivec,rev(bivec)) is a symmetric vector of zeroes and ones, and ctree(symbivec~c(1:length(symbivec))) will not find a single split, no matter how many groups you can identify by eye or with rpart(). (At least, that's been true in all the examples I've tried.)

Do you agree with the ctree() conclusion in this case?

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

By default ctree() uses a certain generalized type of association test to determine the split variable to be used. You can easily replicate this with the coin package that implements the same class of association tests for direct use:

library("coin")
independence_test(t20.a ~ p20, teststat = "quad")
##         Asymptotic General Independence Test
## 
## data:  t20.a by p20
## chi-squared = 14.286, df = 1, p-value = 0.0001571

Once the variable is selected, the optimal split point is selected by maximizing the corresponding two-sample association test. More details and further references are given in this discussion: What is the test statistics used for a conditional inference regression tree?

Optionally, it is possible to also use the maximally-selected statistic for the split variable already. By default this is not used because it is somewhat less powerful for monotonic associations and computationally more intensive. However, as your pat363 example illustrates: It can miss certain completely balanced patters (like the XOR or chessboard example). However, any splitting strategy you use will perform better on some patterns and worse on others...

Improve this answer
$\endgroup$
5
  • $\begingroup$ Professor Zeileis, thank for responding! Yes, it seems the issue has to do with symmetry. If I have a symmetric pattern, then the chi-squared value from the independence_test() function will be zero. And I guess that causes ctree() to stop looking for splits, even if there are significant ones available? I wonder whether the test could be altered so that it doesn't assume symmetry is the same as lack of association. In order to do this, I'd still need to understand how the independence_test() generates its value, and then how ctree() decides where to split if the value is significant. $\endgroup$
    – Talbot Katz
    Commented Jul 6, 2015 at 18:12
  • $\begingroup$ The problems of exhaustive searches over all possible splits are: (a) potentially time-consuming, (b) potential bias towards variables with many splits (if not appropriately adjusted). rpart ignores problem (b). ctree tries to address it by using a statistic that is not maximally selected (by default). In the old party implementation you can change this, though, by setting: xtrafo = function(data) ptrafo(data, numeric_trafo = maxstat_trafo) (after loading the coin package). Then you get the maximally selected test for the variable selection. $\endgroup$
    – Achim Zeileis
    Commented Jul 6, 2015 at 19:04
  • $\begingroup$ The mob algorithm (with convenience interfaces lmtree and glmtree in the new partykit implementation) takes yet another route: It employs a maximally selected LM (Lagrange multplier aka score) test statistic. This is computationally cheap and asymptotically equivalent to the LR (likelihood ratio) tests. Other routes are conveivable as well, e.g., GUIDE uses chi-square type tests with a fixed number of bins. Of course, for any of these tests you can construct artificial counter-examples that the tests will have little or no power against... $\endgroup$
    – Achim Zeileis
    Commented Jul 6, 2015 at 19:09
  • $\begingroup$ @AchimZeileis can you give more details on "the optimal split point is selected by maximizing the corresponding two-sample association test."? $\endgroup$
    – blueskyddd
    Commented Jun 27, 2020 at 22:09
  • $\begingroup$ The original question shows all possible binary splits in the regressor variable but instead of computing the Gini index ctree() computes a two-sample association test. Here, in the classification case, this would be a $\chi^2$ test for a $2 \times 2$ contingency table. In the regression case it would essentially be a two-sample t-test etc. $\endgroup$
    – Achim Zeileis
    Commented Jun 28, 2020 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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