Trees and Random Forests
************************

.. module:: ailib.fitting

.. contents::

Decision tree
=============
The tree growing algorithm can be sketched as follows:
    
1. Grow the tree
   
    a) Given the data, determine the optimal dimension *j* and splitting point *s*.

        .. math::
            (j^*, s^*) = \min\limits_{j,s} \left( \min\limits_{c_1} \sum_{i:\, x_i[j] \le s } (y_i - c_1)^2  + \min\limits_{c_2} \sum_{i:\, x_i[j] > s } (y_i - c_2)^2 \right)

      where :math:`c_1` and :math:`c_2` are the labels of the (hypothetical) leaves.
   
    b) Grow two child trees on the respective data subsets.
    c) Stop, if the number of data points is below some threshold.

2. Prune the tree

    a) Collapse the internal node that produces the smallest per-node increase in the tree cost.
    b) Stop, if there's only one node left (the root).
    c) Out of the produced sequence of trees, select the one that minimizes the total tree cost.


Stumps are single-node trees with the node labels fixed to :math:`\pm m`. Also for stumps, the learning consists of finding the
optimal splitting dimension :math:`j` and threshold :math:`s`. Because stumps are classifiers, the :term:`0-1 loss function` is used
as error measurement. Thus, each stump has to solve the optimization problem:

.. math::
    (j^*, s^*) := \min_{j, s} \frac{ \sum\limits_{i=1}^N w_i I \{ y_i \neq c(x_i|j,s,m) \} }{ \sum\limits_{i=1}^n w_i }

Additionally to the training input, each training sample :math:`(x_i,y_i)` is assigned a weight :math:`w_i` that represents how
much a misclassification of the sample contributes to the classifier cost.

Random forest
=============



Interfaces
==========

.. autoclass:: Tree
   :members:
   :show-inheritance:

.. autoclass:: Stump
   :members:
   :show-inheritance:

Classification
--------------

.. autoclass:: ClassificationTree
   :members:
   :show-inheritance:

Regression
----------

.. autoclass:: RegressionTree
   :members:
   :show-inheritance:

Examples
========