4
$\begingroup$

I have 4.4 million observations, 160 binary features, and a binary response. Using rpart on Windows (64-bit, with the 64-bit R v2.13.0 build), I run out of memory on a machine with 64GB RAM. My memory limit seems reasonable:

> memory.limit()
[1] 61440

But on running rpart, I still receive this error after watching memory usage spike:

> mytree = rpart(formula=fmla,data=mydata,method="class",xval=0)
Error in rpart(formula = fmla, data = mydata, method = "class",  : 
  cannot allocate memory block of size 5.0 Gb

This r-help post suggest that memory fragmentation may be an issue. Rebooting the machine and starting with a fresh workspace has no effect, nor does --max-mem-size=60G as recommended here.

I'm hoping to avoid sampling from my population. I've tried using logical and factor representations of my data. I've also tried tree and looked at gbm, randomforest and party packages, none of which appear to offer more efficient multi-class CART implementations. Can anyone suggest an alternate package or different run parameters?

Barring that, I'm looking for a package to streamline running it through rpart in pieces. I could run rpart on subsets of features and choose the best split from all my runs at each node, but reassembling the results into an rpart object for plotting and pruning sounds like a chore. Can anyone suggest a cleaner solution or a pre-written package for this?

Thanks.

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you tried changing the control parameters in the initial tree growing process? Something like control = rpart.control(maxdepth = 15) or perhaps increasing the cost-complexity parameter cp or increasing minsplit. $\endgroup$ – NRH Oct 28 '11 at 6:57
  • $\begingroup$ Does it have to be a tree? You mention gbm, which is a boosting package. and you can almost always improve on the performance of a single tree for classification by boosting or bagging, and random forests is an example of the latter. Not that this matters, if you can't build a single tree, but could you use other methods? Have you tried a logistic regression model? $\endgroup$ – NRH Oct 28 '11 at 7:08
  • $\begingroup$ I think there should be a tag about memory management $\endgroup$ – Michael Bishop Oct 28 '11 at 20:10
  • $\begingroup$ @MichaelBishop Why not simply resort on the large-data tag? $\endgroup$ – chl Oct 28 '11 at 21:43
  • $\begingroup$ @NRH: it does need to be a single tree, since it's an extension of an earlier (smaller) analysis and the client likes the visualization. $\endgroup$ – Shahin Oct 28 '11 at 22:24
3
$\begingroup$

It is hard to say something without detailed debug data, but some random thoughts:

  • First of all, don't even think of using formula interface for large data -- this is highly inefficient.
  • Second thing is that none of this options can really take advantage of the "binarity" of the data -- you can try reducing the set say 4-fold by merging consecutive packets of 4 original attributes into single factors from 1 to $2^4=16$.
  • It is possible you can resign from some attributes -- if some has less than 1% of some value it is most likely useless.
  • Finally you can try kNN (on binary data it often behaves similar to CART), simpler classifier (see @NRH comment) or some standalone CART code.
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Your first point is very interesting to me as I learn more about R. Why is this true (that formula semantics are highly inefficient)? $\endgroup$ – Josh Hemann Oct 28 '11 at 14:46
  • 1
    $\begingroup$ In short, it usually works by calling a series of not-too-fast functions that tries to find and execute complex expressions that may exist in a formula (like (a+b)^3+c*(e+f)+g:h+0) and makes a new data.frame ready to be used by the modelling function. In case you just want to pass predictors and decision this is a fully redundant and is a significant overhead with large sets due to numerous copying. $\endgroup$ – user88 Oct 28 '11 at 15:29
  • $\begingroup$ @mbq How might I obtain more useful debug data? I've tried traceback() but it looks like it can't show me exactly which allocation failed. From memory.c it looks like this has to be an R_alloc/S_alloc call. rpart.c uses several, and I'd like to determine which one fails. $\endgroup$ – Shahin Oct 28 '11 at 22:52

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.