[R] multi-class classification using rpart

[Liaw, Andy]

> From: Uwe Ligges 
> 
> WeiWei Shi wrote:
> 
> > Hi, Andy:
> > Thanks. It works after I removed the variable. I think I 
> got a similar
> > problem when I used randomForest. And I am not sure if they were due
> > to the same reason.
> > 
> > Practically and Unfortunately, that variable is very 
> important to the
> > accuracy. I am wondering if there is another way besides collapsing
> > it. BTW, I remember you mentioned some alternative implementation to
> > randomForest (the author provided) to avoid the upper limit 
> (32, if I
> > am correct) for the level of factor which can be used in the R
> > version's randomForest.
> > 
> > Thanks for further assistance!
> 
> 
> So you *really* want it to be factor?! Thought it was a 
> mistake not to 
> have it numerical....
> Amazing! Maybe computers are sometimes even too fast these days.
> 
> Uwe

[Uwe: Not sure if you meant to keep this off-list.  If so, my most sincere
apologies.]

Er... not really.  Currently (classification) randomForest encode splits on
categorical variables by binary expansion of levels that go to the left.
Such split is stored in (4-byte) integers, thus the 32-level restriction.
In newer version of Breiman & Cutler's Fortran code, that restriction is
removed by storing the entire indicator matrix (# of nodes by max. number of
levels, then by number of trees in the forest).  For the stand-alone
Fortran, each tree is written to file as soon as it's grown, so it doesn't
need to store the entire forest in memory.  The R version has no such luxury
(if you can call it that).

The way the new RF Fortran code deals with categorical variables with more
than 10 categories is by randomly sampling some number (say 512) of random
splits and pick the best among them.  That's probably a good strategy for
random forests, but may not be what one would do to grow a single tree.

When growing a single tree with data containing categorical variables with
large number of categories, one should also be mindful of the problem that,
because of the greedy nature of the algorithm, it will tend to split on
variables with larger numbers of possible splits, even if those variables
are less `informative'.

Andy
 
> > Ed
> > 
> > On Tue, 25 Jan 2005 14:58:04 -0500, Liaw, Andy 
> <andy_liaw at merck.com> wrote:
> > 
> >>>From: WeiWei Shi
> >>>
> >>>Hi,
> >>>I am trying to make a multi-class classification tree by 
> using rpart.
> >>>I used MASS package'd data: fgl to test and it works well.
> >>>
> >>>However, when I used my small-sampled data as below, the 
> program seems
> >>>to take forever. I am not sure if it is due to slowness or there is
> >>>something wrong with my codes or data manipulation.
> >>>
> >>>Please be advised !
> >>>
> >>>The data is described as the output from str() function. 
> The call to
> >>>rpart is like:
> >>>
> >>>library(rpart)
> >>>test_tree<-rpart(x$V142 ~ ., data=x,
> >>>parms=list(split='gini'), cp =0.01)
> >>>
> >>>the response variable is $V142, with 3 levels.
> >>>
> >>>Thanks for your suggestions!
> >>>
> >>>Ed.
> >>
> >>[snip]
> >>
> >>
> >>> $ V141: Factor w/ 88 levels "1001","1002",..: 59 59 59 59 59
> >>>59 55 78 7 73 ...
> >>
> >>I'd bet this is the problem.  There are 2^(88-1) - 1 
> possible ways to split
> >>a factor with 88 levels.  It will work on those splits til 
> the cows come
> >>home...
> >>
> >>I'd suggest getting rid of that variable, or collapse the levels to
> >>something more reasonable.  The CART book describes some 
> heuristic shortcuts
> >>for testing only n-1 splits for factors with n levels, but 
> I believe that
> >>only works for 2-class problems, if I'm not mistaken.
> >>
> >>Andy
> >>
> >>------------------------------------------------------------
> ------------------
> >>Notice:  This e-mail message, together with any 
> attachment...{{dropped}}
> > 
> > 
> > ______________________________________________
> > R-help at stat.math.ethz.ch mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide! 
> http://www.R-project.org/posting-guide.html
> 
>