Github user atalwalkar commented on a diff in the pull request:
https://github.com/apache/spark/pull/2063#discussion_r16511872
--- Diff: docs/mllib-decision-tree.md ---
@@ -77,109 +85,316 @@ bins if the condition is not satisfied.
**Categorical features**
-For `$M$` categorical feature values, one could come up with `$2^(M-1)-1$`
split candidates. For
-binary classification, we can reduce the number of split candidates to
`$M-1$` by ordering the
+For a categorical feature with `$M$` possible values (categories), one
could come up with
+`$2^{M-1}-1$` split candidates. For binary classification and regression,
+we can reduce the number of split candidates to `$M-1$` by ordering the
categorical feature values by the proportion of labels falling in one of
the two classes (see
Section 9.2.4 in
[Elements of Statistical Machine
Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/) for
details). For example, for a binary classification problem with one
categorical feature with three
-categories A, B and C with corresponding proportion of label 1 as 0.2, 0.6
and 0.4, the categorical
-features are ordered as A followed by C followed B or A, C, B. The two
split candidates are A \| C, B
-and A , C \| B where \| denotes the split. A similar heuristic is used for
multiclass classification
-when `$2^(M-1)-1$` is greater than the number of bins -- the impurity for
each categorical feature value
-is used for ordering.
+categories A, B and C whose corresponding proportions of label 1 are 0.2,
0.6 and 0.4, the categorical
+features are ordered as A, C, B. The two split candidates are A \| C, B
+and A , C \| B where \| denotes the split.
+
+In multiclass classification, all `$2^{M-1}-1$` possible splits are used
whenever possible.
+When `$2^{M-1}-1$` is greater than the `maxBins` parameter, we use a
(heuristic) method
+similar to the method used for binary classification and regression.
+The `$M$` categorical feature values are ordered by impurity,
+and the resulting `$M-1$` split candidates are considered.
### Stopping rule
The recursive tree construction is stopped at a node when one of the two
conditions is met:
-1. The node depth is equal to the `maxDepth` training parameter
+1. The node depth is equal to the `maxDepth` training parameter.
2. No split candidate leads to an information gain at the node.
+## Implementation details
+
### Max memory requirements
-For faster processing, the decision tree algorithm performs simultaneous
histogram computations for all nodes at each level of the tree. This could lead
to high memory requirements at deeper levels of the tree leading to memory
overflow errors. To alleviate this problem, a 'maxMemoryInMB' training
parameter is provided which specifies the maximum amount of memory at the
workers (twice as much at the master) to be allocated to the histogram
computation. The default value is conservatively chosen to be 128 MB to allow
the decision algorithm to work in most scenarios. Once the memory requirements
for a level-wise computation crosses the `maxMemoryInMB` threshold, the node
training tasks at each subsequent level is split into smaller tasks.
+For faster processing, the decision tree algorithm performs simultaneous
histogram computations for
+all nodes at each level of the tree. This could lead to high memory
requirements at deeper levels
+of the tree, leading to memory overflow errors. To alleviate this problem,
a `maxMemoryInMB`
+training parameter specifies the maximum amount of memory at the workers
(twice as much at the
+master) to be allocated to the histogram computation. The default value is
conservatively chosen to
+be 128 MB to allow the decision algorithm to work in most scenarios. Once
the memory requirements
+for a level-wise computation cross the `maxMemoryInMB` threshold, the node
training tasks at each
+subsequent level are split into smaller tasks.
+
+Note that, if you have a large amount of memory, increasing
`maxMemoryInMB` can lead to faster
+training by requiring fewer passes over the data.
+
+### Binning feature values
+
+Increasing `maxBins` allows the algorithm to consider more split
candidates and make fine-grained
+split decisions. However, it also increases computation and communication.
+
+Note that the `maxBins` parameter must be at least the maximum number of
categories `$M$` for
+any categorical feature.
+
+### Scaling
-### Practical limitations
+Computation scales approximately linearly in the number of training
instances,
+in the number of features, and in the `maxBins` parameter.
+Communication scales approximately linearly in the number of features and
in `maxBins`.
-1. The implemented algorithm reads both sparse and dense data. However, it
is not optimized for sparse input.
-2. Python is not supported in this release.
+The implemented algorithm reads both sparse and dense data. However, it is
not optimized for sparse input.
## Examples
### Classification
-The example below demonstrates how to load a CSV file, parse it as an RDD
of `LabeledPoint` and then
+The example below demonstrates how to load a
+[LIBSVM data
file](http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/),
+parse it as an RDD of `LabeledPoint` and then
perform classification using a decision tree using Gini impurity as an
impurity measure and a
--- End diff --
"decision tree using Gini..." -> "decision tree with Gini..."
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
