# CART (Classification and regression tree)

CART is the base method for XGBoost. It can be used to build (1) regression tree and (2) classification tree

### Deal with Categorical and Numerical feature

* Categorical&#x20;
  * If the category number is more than 2,&#x20;
    * Enumerate all of splitting combinations
    * Pick splitting point with lowest Gini index
  * If category number is 2.
    * Split directly
* Numerical
  * Sort values based on the numerical feature
  * Find the splitting point between numerical values&#x20;
    * Calculate the Gini index of all possible splitting point
    * Find the splitting point corresponding to the minimum value

### CART regression tree

Target is $$\min\_{j,s}{\min\_{c\_1}\sum\_{x\_i \in R\_1}(y\_i-c\_1)^2 + \min\_{c\_2}\sum\_{x\_i \in R\_2}(y\_i-c\_2)^2 }$$&#x20;

&#x20;            Where, $$c\_1 = avg(y\_i|x \in R\_1)$$ and $$c\_2 = avg(y\_i|x \in R\_2)$$&#x20;

CART regression tree is

$$
f(x) = \sum\_{m=1}^{M} c\_mI(x \in R\_m)
$$

&#x20;                Where, $$c\_m^\* = avg(y\_i | x\_i \in R\_m)$$&#x20;

Steps to generate a CART regression Tree:

* Iterate all features
  * *For each feature*, browsing all possible splitting point
  * *For each splitting point*, Measure the sum of square root error&#x20;
  * \--> Each feature: Find the best splitting point
  * \--> Combine all features: find the best splitting point
* Split the samples based on the best splitting point of a feature:

  * Output the child nodes:

  &#x20;      $$R\_1 = {x|x\_i^{(j)} \leq s^{(j)}}$$ and  $$R\_2 = {x|x\_i^{(j)} > s^{(j)}}$$&#x20;

&#x20;               $$c\_1 = \frac{1}{|R\_1|}\sum\_{x\_i \in R\_1}y\_i$$  and $$c\_2 = \frac{1}{|R\_2|}\sum\_{x\_i \in R\_2}y\_i$$&#x20;

* Finally, split the input space into M areas $$R\_1, R\_2, ..., R\_M$$, and output the CART model as $$f(x) = \sum\_{m=1}^{M} c\_mI(x \in R\_m)$$

### CART classification tree

Target is Gini index:&#x20;

$$
Gini(D) = 1 - \sum\_k(\frac{|C\_k|}{|D|})^2 , \\
where,;
Gini(D\_i) = 1 - \sum\_k(\frac{|C\_{ik}|}{|D\_i|})^2
$$

* &#x20;$$D\_i$$  is feature $$A = a\_i$$的samples
* &#x20;$$C\_{ik}$$ is samples in $$D\_i$$with label k

Gini index the smaller, the better

Steps to generate a CART classification Tree:

* Iterate all features
  * *For each feature*, browsing all possible splitting point
  * *For each splitting point*, Measure the$$Gini(D\_i)$$&#x20;
  * \--> Each feature: Find the best splitting point&#x20;
* Select the feature with minimum $$Gini(D\_i)$$, as the best splitting point
* Recursive the subsamples of each child tree
