Are there any libraries available for CART-like methods using sparse predictors & responses?

Question

I'm working with some large data sets using the gbm package in R. Both my predictor matrix and my response vector are pretty sparse (i.e. most entries are zero). I was hoping to build decision trees using an algorithm that takes advantage of this sparseness, as was done here). In that paper, as in my situation, most items have only a few of the many possible features, so they were able to avoid a lot of wasted computation by assuming that their items lacked a given feature unless the data explicitly said otherwise. My hope is that I could get a similar speedup by using this sort of algorithm (and then wrapping a boosting algorithm around it to improve my predictive accuracy).

Since they didn't seem to publish their code, I was wondering if there were any open-source packages or libraries (in any language) that are optimized for this case. Ideally, I'd like something that could take a sparse matrix directly from R's Matrix package, but I'll take what I can get.

I've looked around and it seems like this sort of thing should be out there:

• Chemists seem to run into this issue a lot (the paper I linked above was about learning to find new drug compounds), but the implementations I could find were either proprietary or highly specialized for chemical analysis. It's possible one of them could be re-purposed, though.

• Document classification also seems to be an area where learning from sparse feature spaces is useful (most documents don't contain most words). For instance, there's an oblique reference to a sparse implementation of C4.5 (a CART-like algorithm) in this paper, but no code.

• According to the mailing list, WEKA can accept sparse data, but unlike the method in the paper I linked above, WEKA isn't optimized to actually take advantage of it in terms of avoiding wasted CPU cycles.

Thanks in advance!

Answer 1

Probably there is a little chance for any code which would take advantage of that -- you would rather need to write something on your own.
However, the other option is to transform your data to reduce the size of your data removing redundant information. It is hard to tell how without the information about your data, but maybe you can merge some features which you know does not overlap, PCA parts of it or change representation of some descriptors? Also, if you say your response is sparse as well, maybe it is reasonable to downsample objects with 0 in response?

Answer 2

Have you looked at the caret package in R? It provides an interface that makes it easier to use a variety of models, including some for recursive partitioning such as rpart, ctree and ctree2.