Slow convergence with rpart

Question

I'm building a decision tree in R using the rpart function, available in the library of the same name, but am experiencing some serious performance issues when partitioning data using more than one feature (there is roughly 5000 rows in my data set, and the features in question have around 30 unique values each). Running rpart with the one feature completes in a couple hours (running single thread on a CentOS server with about 250GB ram), but, after 6 days, a model with a second feature added has yet to complete!

I've created an approach to extracting the path through the tree new data takes (see my question/solution here), which is my main motivation here, but the method requires an object that can be type-cast as a party object. A colleague of mine told me that he's seen performance boosts using the ctree function, but the output of this is an inscrutable S4 object that I can't figure out how to convert. My questions are two:

1. Does anyone know a way to speed up rpart beyond what I've already done here:clf <- rpart(Y ~ X$var1 + X$var2, rpart.control(maxcompete=1, maxsurrogate=0))?
2. Does anyone know how to convert a ctree object to a party object? Alternatively, does anyone have concurring or contradicting observations on ctree performance?

Answer 1

I have faced similar challenges. You could try to use the RevolutionR rxDTree function which performs reasonably well on large data sets and can be converted to a rpart object.

I found to achieve a reasonable performance boost by specifying the minimum bin size with rpart.control(minbucket=2). You could also tune the complexity parameter. Note that both may lead to poor performance.

Answer 2

If you have unordered factors with 30 levels then when your decision tree is looking to make a split then it will look through all combinations to decide how to make a split. Let's calculate that:

(30 choose 1) + (30 choose 2) + ... + (30 choose 29) + (30 choose 30)

I.e. a huge number. This is computed at each split. I'm not an expert on this but it seems like unordered factor variables need to be avoided.