apache/incubator-spark — pull request #161 by hirakendu (2013-11-11 20:56:41+00:00)
Title: Added an initial implementation of decision trees for mllib.

Added an initial implementation of decision trees for mllib. Includes both regression trees using square loss and classification trees using entropy loss. Follows a similar design as the linear regression and logistic regression implementations currently in mllib. Supports continuous and categorical features, and other functionality specific to tree models. Includes basic functional tests, a basic synthetic data generator and a processed version of the auto-mpg dataset from UCI machine learning repository as a small, real-world dataset.

While most of the design is similar to existing linear classification and regression algorithms in mllib, an additional interface for loss functions is defined, that is akin to the optimization interface for linear models. The decision tree algorithm implementation is generic and uses this loss interface, thus supporting any loss functions implemented using this interface.

Additional details about the usage, design, implementation, tests and benchmarks is provided at this working document at this external location (a repo in my github, for lack of a better place in Spark repo): [hirakendu/boosted_trees/doc/spark_mllib_boosted_trees_md](https://github.com/hirakendu/boosted_trees/blob/master/doc/spark_mllib_boosted_trees_md/spark_mllib_boosted_trees.md).

Comments are highly welcome, especially for the loss interface and its use for a generic implementation of decision tree algorithms.

Also see the [related pull request in MLI for decision trees](https://github.com/amplab/MLI/pull/3). Contributions from both pulls and beyond will be combined soon for the best implementation :).

The broader goal is to have boosting and ensemble models based on decision trees and other learners. See the github repo [hirakendu/boosted_trees/code/boosted_trees_spark](https://github.com/hirakendu/boosted_trees/tree/master/code/boosted_trees_spark_v2) for experimental but hopefully usable implementation with additional bells and whistles.