SPARK-1536: multiclass classification support for decision tree

The ability to perform multiclass classification is a big advantage for using decision trees and was a highly requested feature for mllib. This pull request adds multiclass classification support to the MLlib decision tree. It also adds sample weights support using WeightedLabeledPoint class for handling unbalanced datasets during classification. It will also support algorithms such as AdaBoost which requires instances to be weighted.

It handles the special case where the categorical variables cannot be ordered for multiclass classification and thus the optimizations used for speeding up binary classification cannot be directly used for multiclass classification with categorical variables. More specifically, for m categories in a categorical feature, it analyses all the ```2^(m-1) - 1``` categorical splits provided that #splits are less than the maxBins provided in the input. This condition will not be met for features with large number of categories -- using decision trees is not recommended for such datasets in general since the categorical features are favored over continuous features. Moreover, the user can use a combination of tricks (increasing bin size of the tree algorithms, use binary encoding for categorical features or use one-vs-all classification strategy) to avoid these constraints.

The new code is accompanied by unit tests and has also been tested on the iris and covtype datasets.

cc: @mengxr, @etrain, @hirakendu, @atalwalkar, @srowen
Yeah, makes sense. If it doesn't complicate things too much we might
consider adding an interface that doesn't have this specified and figures
it out in one shot.

Worth noting is that in R, an object of type "factor" (the default for
categorical/label data) has this information built in. It can be a big pain
at load time while the system tries to figure out the cardinality of the
factor, but it leads to a nice compact representation of the data and
eliminates situations like this one.

I agree on doing the API separation with the ensembles PR.


On Thu, Jun 19, 2014 at 10:46 AM, manishamde <notifications@github.com>
wrote:

> In
> examples/src/main/scala/org/apache/spark/examples/mllib/DecisionTreeRunner.scala:
>
> > @@ -49,6 +49,7 @@ object DecisionTreeRunner {
> >    case class Params(
> >        input: String = null,
> >        algo: Algo = Classification,
> > +      numClassesForClassification: Int = 2,
>
> Inference from a large dataset could take a lot of time. In general, most
> practitioners know in advance. If not, we can add a pre-processing step.
>
> Currently we have only numClassesForClassification as a classification
> specific parameter. In general, I agree with you. At the same time, didn't
> want to create more configuration classes for the user. Shall we leave it
> as is for now and handle it with the ensembles PR where we have more
> parameters (boosting iterations, num trees, feature subsetting, etc.) ?
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/apache/spark/pull/886/files#r13982468>.
>