8
$\begingroup$

I know that R's rpart function keeps the data it would need to implement multivariate split, but I don't know if it's actually performing multivariate splits. I've tried researching it online looking at the rpart docs, but I don't see any information that it can do it or is doing it. Anyone know for sure?

$\endgroup$
  • $\begingroup$ What do you precisely mean by multivariate split? Multivariate test which attribute should be used for split or split based on some function of few attributes? $\endgroup$ – mbq Nov 9 '10 at 19:22
  • $\begingroup$ This is a split that uses more than one variable. Geometrically this means a splits along a hyperplane, rather than a plane perpendicular to one of the axis. $\endgroup$ – chubbsondubs Nov 10 '10 at 19:13
13
$\begingroup$

Rpart only provides univariate splits. I believe, based upon your question, that you are not entirely familiar with the difference between a univariate partitioning method and a multivariate partitioning method. I have done my best to explain this below, as well as provide some references for further research and to suggest some R packages to implement these methods.

Rpart is a tree based classifier that uses recursive partitioning. With partitioning methods you must define the points within your data at which a split is to be made. The rpart algorithm in R does this by finding the variable and the point which best splits (and thus reduces) the RSS. Because the splits only happen along one variable at a time, these are univariate splits. A Multivariate Split is typically defined as a simultaneous partitioning along multiple axis (hence multivariate), i.e. the first rpart node might split along Age>35, the second node might split along Income >25,000, and the third node might split along Cities west of the Mississippi. The second and third nodes are split on smaller subsets of the overall data, so in the second node the income criterion best splits the RSS only for those people who have an age of over 35, it does not apply to observations not found in this node, the same applies for the Cities criterion. One could continue doing this until there is a node for each observation in your dataset (rpart uses a minimum bucket size function in addition to a minimum node size criterion and a cp parameter which is the minimum the r-squared value must increase in order to continue fitting).

A multivariate method, such as Patient Rule Induction Method (the prim package in R) would simultaneously split by selecting, for example, All Observations where Income was Greater than 22,000, Age>32, and Cities West of Atlanta. The reason why the fit might be different is because the calculation for the fit is multivariate instead of univariate, the fit of these three criterion is calculated based upon the simultaneous fit of the three variables on all observations meeting these criterion rather than iteratively partitioning based upon univariate splits (as with rpart).

There are varying beliefs in regards to the effectiveness of univariate versus multivariate partitioning methods. Generally what I have seen in practice, is that most people prefer univariate partitioning (such as rpart) for explanatory purposes (it is only used in prediction when dealing with a problem where the structure is very well defined and the variation among the variables is fairly constant, this is why these are often used in medicine). Univariate tree models are typically combined with ensemble learners when used for prediction (i.e. a Random Forest). People who do use multivariate partitioning or clustering (which is very closely related to multivariate partitioning) often do so for complex problems that univariate methods fit very poorly, and do so mainly for prediction, or to group observations into categories.

I highly recommend Julian Faraway's book Extending the Linear Model with R. Chapter 13 is dedicated entirely to the use of Trees (all univariate). If you're interested further in multivariate methods, Elements of Statistical Learning by Hastie et. al, provides an excellent overview of many multivariate methods, including PRIM (although Friedman at Stanford has his original article on the method posted on his website), as well as clustering methods.

In regards to R Packages to utilize these methods, I believe you're already using the rpart package, and I've mentioned the prim package above. There are various built in clustering routines, and I am quite fond of the party package mentioned by another person in this thread, because of its implementation of conditional inference in the decision tree building process. The optpart package lets you perform multivariate partitioning, and the mvpart package (also mentioned by someone else) lets you perform multivariate rpart trees, however I personally prefer using partDSA, which lets you combine nodes further down in your tree to help prevent partitioning of similar observations, if I feel rpart and party are not adequate for my modeling purposes.

Note: In my example of an rpart tree in paragraph 2, I describe how partitioning works with node numbers, if one were to draw out this tree, the partitioning would proceed to the left if the rule for the split was true, however in R I believe the split actually proceeds to the right if the rule is true.

$\endgroup$
  • $\begingroup$ Adam great answer. That's exactly what I was asking. However, you added a tid bit of information that I have had a hard time finding more information on. The Mallow's CP stop criterion. I've looked through the R source code, but it's too hard to figure how they are choosing to stop. I roughly have an idea, but I need a paper or some discussion on how it works so I can finish implementing it. Do you have any information about it? $\endgroup$ – chubbsondubs Dec 29 '10 at 21:44
  • $\begingroup$ So, I checked the rpart reference manual, and apparently I was incorrect. While one of the criterion for stopping in rpart is called "cp" this is short for "complexity parameter" and is merely the minimum amount r^2 must increase by in order to pursue a particular split. I have corrected my post above to reflect this. The lack of statistical tests in splitting rules is one of the reasons why I use the party package over the rpart package. With the party package the default method implements a Bonferroni corrected p-value as a stopping criterion (default p=0.05). For details see the vignette. $\endgroup$ – Adam Dec 30 '10 at 6:14
  • $\begingroup$ I feel the fact that rpart does not use a stopping criterion is an asset, rather than a liability. A split may appear to be worthless, and yet open the way for subsequent splits further down the tree, which may be quite significant. A "grow, then prune" policy as implemented in rpart will avoid early stopping and seems to me a sensible approach. $\endgroup$ – F. Tusell Dec 30 '10 at 9:00
  • $\begingroup$ @Tusell that's the whole idea behind CART's research is that choosing a stop criterion is suboptimal. Grow a full tree then use pruning to find an optimal tree. However, as @Adam has pointed out rpart doesn't exactly work like that. Part of it I think is an optimization for large datasets. If it can chop off a subtree early without exploring it can save way more CPU time than going through a full expansion and pruning session. As you point out though that means some trees aren't fully explored and you have to tweak the cp param to make it work. $\endgroup$ – chubbsondubs Dec 31 '10 at 14:57
  • $\begingroup$ @Adam is R^2 calculated from the testing dataset or is it using the pruning set to calculate MSE? $\endgroup$ – chubbsondubs Dec 31 '10 at 15:04
1
$\begingroup$

As fas as I know, it doesn't; but have not used it for a while. If I understand you well, you might want to look at package mvpart instead.

$\endgroup$
1
$\begingroup$

Your terminology is confusing. Due you mean splits using more than one variable, or a tree that allows for a multivariate (as opposed to a univariate) response? I presume the latter.

F. Tusell has pointed you to the mvpart package, which adds a multivariate criterion for node impurity that is evaluated for all possible splits at each stage of tree building.

An alternative is the party package, whose function ctree() can handle multivariate responses.

$\endgroup$
  • $\begingroup$ Actually I'm referring to splits using more than one variable. If you read the Leo Breiman's CART book it refers to this as multi-variate splits as opposed to uni-variate where only one variable is consider. Thanks for you answer. $\endgroup$ – chubbsondubs Nov 10 '10 at 19:10
  • 1
    $\begingroup$ All variables are considered in rpart, the binary split is formed by searching over all variables and all possible split locations within each variable. rpart also stores information about surrogate splits which can be used when there is missing data in your variables. Does this help? $\endgroup$ – Gavin Simpson Nov 10 '10 at 20:04
  • $\begingroup$ If you mean splits that are some combination of two or more variables, no, rpart doesn't handle that case. $\endgroup$ – Gavin Simpson Nov 10 '10 at 20:25
1
$\begingroup$

Multivariate splits as defined in the CART book aren't implemented in rpart. The CART software package from Salford Systems has this feature, but AFAIK it uses a proprietary algorithm licensed from Breiman, Friedman et al.

$\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.