
---
title: "Tree based models - 3: cross-validation"
author: ''
output:
  html_document:
    toc: yes
  pdf_document: null
  pdf_presentation: null
  slidy_presentation:
    css: slidy.css
    widescreen: yes
  word_document: null
---

# Terminology

 + Training set
 
 + Testing set
 
 + Validation set

 + Cross-validation: used to estimate the error rate of classification
 
 + Validation: used to build the 'right level of complexity' model
 
 Are these fundamentally different?
 
 You will see sites that say that CV has nothing to do with model building:
 
 https://stackoverflow.com/questions/2314850/help-understanding-cross-validation-and-decision-trees
 
 But you will also see lectures (Stanford) that say the opposite:
 
 e.g. Find the optimal subtree by cross validation
 
 https://web.stanford.edu/class/stats202/content/lec19.pdf
 
 This is also the approach we used in class.
 
 
  + cost complexity pruning (CSP) and cross-validation
  
 
(Figure: Dec. 28, 1987 - Landing of the Soyuz-TM3 craft carrying the Soyuz-TM2 crew Y. Romanenko, Aleksandrov & Levchenko)


<img src="https://pbs.twimg.com/media/CXTQofWUwAA9CqI?format=jpg&name=small">


 + VARIANTS OF CV
 
 TT, L10, LpO, VS, stratified-CV, kF-CV, nested cross-VALIDCEPTION

https://www.cs.utoronto.ca/~fidler/teaching/2015/slides/CSC411/tutorial3_CrossVal-DTs.pdf


 + Relatives of CARTs: recursive partitions

RECURSIVE PARTITIONING (library RPART in R)

https://www.statmethods.net/advstats/cart.html

BSP:

<img src="https://upload.wikimedia.org/wikipedia/commons/8/81/Binary_space_partition.png">

BSP for collision detection and polygon visibility in videogames:

<img src="http://www.unrealtexture.com/Unreal/Downloads/3DEditing/UnrealEd/Tutorials/unrealwiki-offline/images/bsp-diagram.gif">

BSP for creating games:

https://gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps--gamedev-12268


inter and intra-object representation:

<img src="https://lh3.googleusercontent.com/-2wyoGweafYI/VTvMHHAoHBI/AAAAAAAACXA/62fBQLJgTss/image_thumb.png?imgmax=800">


# DATA SET 1: Heart failure


## Cross-validation

Recall the CV procedure:


```{r}
heart=read.csv("http://faculty.marshall.usc.edu/gareth-james/ISL/Heart.csv")
head(heart)
summary(heart)
nmiss=apply(is.na(heart),1,sum) #number of missing values, by row

heartm=heart[nmiss!=0,]  #cases with missing values
heart=heart[nmiss==0,]   #remove cases with missing values
head(heartm)
library(tree)
heart.tree=tree(AHD~., data=heart)
plot(heart.tree)
text(heart.tree)
print(heart.tree)

heartcv=cv.tree(heart.tree, FUN=prune.misclass)
print(heartcv)
plot(heartcv$size,heartcv$dev,type='b')
bestsize=heartcv$size[heartcv$dev==min(heartcv$dev)]
```


## Under the hood of CV

<pre>
297

> rand <- sample(K, length(m[[1L]]), replace = TRUE)
> rand
  [1] 10  9  2  2  3  8  7  4  6  5  3 10  4  9  9  4  3  3  6  9  5  9  1  9
 [25]  8  3  1  8  2  1 10  9  7  2  4  6  4  7  5  8  9  8  3  8  3  2  8  1
 [49]  2  4  2  6  3  6  7  3  2  8 10  9  3  6  1  6 10  3 10  1  5  7  9  6
 [73]  7 10  4  6  2  3  1  2  9  2  7  2  2  5  7  8  6  9 10  2  8  1  2  2
 [97]  5  4 10  7 10  1  2  6  2  2  2  1  8  1  3  9  8  9  4  5  3  1 10  1
[121]  5  3  2  9 10  1  2  2  1  1  7  3  4  3  9  4  7  5  2  4  7  3  9  8
[145] 10  8  1  6 10  9  8 10  4  6  8  8  3  8  6  5  5 10 10  5  1  6  2  6
[169] 10  9  3 10  3 10  9  6  2  6 10  4 10  1  7 10 10  4  6  9  4  4  2  3
[193]  1  8  2  5  6  5  8  8  3  8  4  4  6  4  3  9  4  7 10  4  5 10  7  6
[217]  7  6  9  3  3  8  7  5 10  1  2  8  5 10  7  3  1  2  9  8  6  3  5  9
[241]  9  3  1  8  5  9  8  4  7  4  2  4  7  5  5  9  2  9  9  2  4  9 10  7
[265]  3  9  7  5  6 10  7  9 10  2  8  1  1  2  3  4  8  7 10  6  9  9  2 10
[289]  1  8  6  4 10  7  9  7 10



init <- do.call(FUN=prune.misclass, c(list(object)))


> init <- do.call(prune.misclass, c(list(object)))
> init$k
[1] -Inf  0.0  1.0  2.0  3.0  5.5  7.0 67.0

k	
cost-complexity parameter defining either a specific subtree of tree (k a scalar) or the (optional) sequence of subtrees minimizing the cost-complexity measure (k a vector).
 If missing, k is determined algorithmically.
 
 > init <- do.call(prune.misclass, c(list(object)))
> init$k
[1] -Inf  0.0  1.0  2.0  3.0  5.5  7.0 67.0


$size
[1] 19 14 11  8  6  4  2  1

$dev
[1]  66  66  56  60  59  71  79 138

$k
[1] -Inf  0.0  1.0  2.0  3.0  5.5  7.0 67.0

$method
[1] "misclass"

attr(,"class")

</pre>



HERE WE ARE with the Tree Homotopy Process of CSP


```{r}
#$size
#[1] 19 14 11  8  6  4  2  1

#$dev
#[1]  66  66  56  60  59  71  79 138

#$k
#[1] -Inf  0.0  1.0  2.0  3.0  5.5  7.0 67.0

```

MY MAIN POINT HERE (correction of a wrong statement I made during my previous lecture on classification trees)

Do you see where the grid of alpha values is?

The grid of SIZES is used instead for plotting !

Are there any jumps in sizes? (tree homotopy process - THP- of Breiman 1984)





# DATASET 2:  Forensic Glass Fragments

<a href="">(src:R ?prune.misclass)</a>

<img src="https://study.com/cimages/videopreview/videopreview-full/je7t8q05wr.jpg">

<pre>

José R. Almirall, Tatiana Trejos
Advances in technology provide forensic scientists with better tools to detect, to identify, and to individualize small amounts of trace 
evidence that have been left at a crime scene. 
The analysis of glass fragments can be useful in solving cases such as hit and run, burglaries, kidnappings, and bombings. 
The value of glass as "evidentiary material" lies in its inherent characteristics such as: 
(a) it is a fragile material that is often broken and hence commonly found in various types of crime scenes, 
(b) it can be easily transferred from the broken source to the scene, suspect, and/or victim, 
(c) it is relatively persistent, 
(d) it is chemically stable, and 
(e) it has measurable physical and chemical properties that can provide significant evidence of an association between the recovered glass fragments and the source of the broken glass.
 Forensic scientists have dedicated considerable effort to study and improve the detection and discrimination capabilities of analytical techniques 
 in order to enhance the quality of information obtained from glass fragments. 
 This article serves as a review of the developments in the application of both traditional 
 and novel methods of glass analysis. 
 The greatest progress has been made with respect to the incorporation of automated refractive 
 index measurements and elemental analysis to the analytical scheme. 
 Glass examiners have applied state-of-the-art technology including elemental analysis by sensitive methods such as ICPMS 
 and LA-ICP-MS. 
 A review of the literature regarding transfer, persistence, and interpretation of glass is also presented. LESS

</pre>



```{r}
library(tree)
data(fgl, package="MASS")
fgl.tr <- tree(type ~ ., fgl)
#plot(print(fgl.tr))
```


```{r}
fgl.cv <- cv.tree(fgl.tr,, prune.tree)
for(i in 2:5)  fgl.cv$dev <- fgl.cv$dev +
   cv.tree(fgl.tr,, prune.tree)$dev
fgl.cv$dev <- fgl.cv$dev/5
plot(fgl.cv)

```


```{r}
fgl.cv <- cv.tree(fgl.tr,, prune.tree)
plot(fgl.cv)
fgl.cv <- cv.tree(fgl.tr,, prune.tree)
plot(fgl.cv)
fgl.cv <- cv.tree(fgl.tr,, prune.tree)
plot(fgl.cv)

```



```{r}
fgl.cv <- cv.tree(fgl.tr,, prune.tree)
fgl.cv

```



MY MAIN POINT HERE (correction of a wrong statement I made during my previous lecture on classification trees)

Do you see where the grid of alpha values is?

The grid of SIZES is used instead for plotting !

Are there any jumps in sizes? (tree homotopy process - THP- of Breiman 1984)



# DATASET 3: Carseats sales


<a href="https://daviddalpiaz.github.io/r4sl/trees.html">(src:daviddalpiaz.github.io/r4sl/trees.html)</a> 

## Full tree


```{r}
library(tree)
library(ISLR)

data(Carseats)
#?Carseats
str(Carseats)

Carseats$Sales = as.factor(ifelse(Carseats$Sales <= 8, "Low", "High"))
str(Carseats)

# Fit an unpruned classification tree using all of the predictors.

seat_tree = tree(Sales ~ ., data = Carseats)
# seat_tree = tree(Sales ~ ., data = Carseats, 
#                  control = tree.control(nobs = nrow(Carseats), minsize = 10))
summary(seat_tree)
plot(seat_tree)
text(seat_tree, pretty = 0)
title(main = "Sales of carseats: full classification tree: no pruning!")
```



```{r}

#  details of the splits.
seat_tree

```


## Test-Train

PLAN: evaluate the overfit of a given test-train partition

simple: 1. predict answers of test and train and 2. compare each to truth (confusion table) and 3. compare tables


```{r}
# try a test-train split
dim(Carseats)
## [1] 400  11
set.seed(2)
seat_idx = sample(1:nrow(Carseats), 200)
seat_trn = Carseats[seat_idx,]
seat_tst = Carseats[-seat_idx,]
seat_tree = tree(Sales ~ ., data = seat_trn)
summary(seat_tree)

# display the predictors used in the tree. Not all columns are used !
summary(seat_tree)$used

# this is clearer
names(Carseats)[which(!(names(Carseats) %in% summary(seat_tree)$used))]

# is the tree built on this training set the SAME as the tree built on all data?
# visual inspection tells you this is not the case

plot(seat_tree)
text(seat_tree, pretty = 0)
title(main = "Unpruned Classification Tree")

```

Confusion tables


```{r}
seat_trn_pred = predict(seat_tree, seat_trn, type = "class")
seat_tst_pred = predict(seat_tree, seat_tst, type = "class")
#predict(seat_tree, seat_trn, type = "vector")  this would not return the classes predicted but the probabilities of both claaes
#predict(seat_tree, seat_tst, type = "vector")

# confusion table of predictions of data in train
table(predicted = seat_trn_pred, actual = seat_trn$Sales)
# same for data in test
table(predicted = seat_tst_pred, actual = seat_tst$Sales)

```



What was training, what was testing predictions?

```{r}
##          actual
## predicted High Low
##      High   57  29
##      Low    27  87


##          actual
## predicted High Low
##      High   66  10
##      Low    14 110

```

Now calculate accuracies


```{r}
# define a function
accuracy = function(actual, predicted) {
  mean(actual == predicted)
}

# run it on train
accuracy(predicted = seat_trn_pred, actual = seat_trn$Sales)

# run it on test
accuracy(predicted = seat_tst_pred, actual = seat_tst$Sales)

```

Conclusion : overfit

Cure? Pruning to avoid overfit

How?  By penalizing large trees (too many leaves) (cost-complexity pruning CCP)

More precisely how? Use cross-validation to find the cost of each leaf


## CCP


(Figure: Dec. 28, 1987 - Landing of the Soyuz-TM3 craft carrying the Soyuz-TM2 crew Y. Romanenko, Aleksandrov & Levchenko)


<img src="https://pbs.twimg.com/media/CXTQofWUwAA9CqI?format=jpg&name=small">



## Cross-validation tuning of leaf-cost 


Apply the cross-validation receipe to find the optimal penalty hyperparameter


```{r}
set.seed(3)
seat_tree_cv = cv.tree(seat_tree, FUN = prune.misclass)
# index of tree with minimum error
min_idx = which.min(seat_tree_cv$dev)
min_idx
# number of terminal nodes in that tree
seat_tree_cv$size[min_idx]
# misclassification rate of each tree
seat_tree_cv$dev / length(seat_idx)
par(mfrow = c(1, 2))
# default plot
plot(seat_tree_cv)
# better plot
plot(seat_tree_cv$size, seat_tree_cv$dev / nrow(seat_trn), type = "b",
     xlab = "Tree Size", ylab = "CV Misclassification Rate")

```



Apply the estimated hyperparameter to finalize our model (prune to target size)


```{r}
seat_tree_prune = prune.misclass(seat_tree, best = 9)
summary(seat_tree_prune)

```

Plot the optimized model


```{r}
plot(seat_tree_prune)
text(seat_tree_prune, pretty = 0)
title(main = "Pruned Classification Tree")

```

Apply the Test-train business to evaluate overfitting of the NEW supposedly improved model



```{r}
seat_prune_trn_pred = predict(seat_tree_prune, seat_trn, type = "class")
table(predicted = seat_prune_trn_pred, actual = seat_trn$Sales)
accuracy(predicted = seat_prune_trn_pred, actual = seat_trn$Sales)
seat_prune_tst_pred = predict(seat_tree_prune, seat_tst, type = "class")
table(predicted = seat_prune_tst_pred, actual = seat_tst$Sales)
accuracy(predicted = seat_prune_tst_pred, actual = seat_tst$Sales)

```

<ul>
<li>Training set: prediction errors comparable to before (high)
<li>Testing set: predictions were <b> a little</b> improved
</ul>

Tree models are easily prone to overfit.

<b>OVERALL CONCLUSION: CCP worked SOMEWHAT but we need other better methods!</b>

IDEAS: Will be introduced in next lectures : 

 + Bagging
 
 + Boosting
 
 + Random Forests



## Question for the curious

Why is it that cross-validation does not entrain us in an infinite loop hell?



# Using a test set to assess the misclassification rate

(src: Wikipedia)


<h2><span class="mw-headline" id="Cost-Complexity_Pruning">Cost-Complexity Pruning</span></h2>
<p>Post-pruning algorithm for <a href="/index.php/Decision_Tree_(Data_Mining)" title="Decision Tree (Data Mining)">Decision Trees</a>
</p>
<ul><li> by Breiman, Olshen, Stone (1984) </li></ul>
<p><br />
</p>
<h3><span class="mw-headline" id="Cost-Complexity_Function">Cost-Complexity Function</span></h3>
<ul><li> need to optimize the cost-complexity function</li>
<li> $R_\alpha (T) = R(T) + \alpha \cdot | f(T) |$ where
<ul><li> $R(T)$ is the training/learning error</li>
<li> $f(T)$ a function that returns the set of leaves of tree $T$</li>
<li> $\alpha$ is a <a href="/index.php/Regularization" title="Regularization">Regularization</a> parameter</li></ul></li>
<li> $R(T) = \sum_{t \in f(T)} r(t) \cdot p(t) = \sum_{t \in f(T)} R(t)$
<ul><li> $\sum_{t \in f(T)} R(t)$ - sum of misclassification errors at each leaf</li>
<li> $r(t) = 1 - \max_k p(C_k - t)$  - <i>misclassification rate</i></li>
<li> $p(t) = \cfrac{n(t)}{n}$ with $n(t)$ being the # of records in node $t$ and $n$ - total # of records</li></ul></li></ul>
<p><br />
</p>
<h3><span class="mw-headline" id="Pruning_Subtrees">Pruning Subtrees</span></h3>
<p>Subtrees:
</p>
<ul><li> <img src="https://raw.githubusercontent.com/alexeygrigorev/wiki-figures/master/ufrt/kddm/decision-tree-subtrees.png" alt="decision-tree-subtrees.png" /></li></ul>
<p>Pruning a subtree $T_{t}$
</p>
<ul><li> $R_\alpha(T - T_t) - R_\alpha(T)$ - variation of the cost-complexity function
<ul><li> this is the cont-complexity when pruning subtree $T_t$</li></ul></li>
<li> $R_\alpha(T - T_t) - R_\alpha(T) = R(T - T_t) - R(T) + \alpha ( | f(T - T_t) | - |f(T)| ) = R(t) - R(T_t) + \alpha ( 1 - |f(T_t)| )$</li>
<li> let $\alpha' = \cfrac{R(t) - R(T_t)}{|f(T_t)| - 1}$</li>
<li> variation is 
<ul><li> null if $\alpha = \alpha'$</li>
<li> negative if $\alpha &lt; \alpha'$</li>
<li> positive if $\alpha &gt; \alpha'$</li></ul></li></ul>
<p><br />
</p><p><br />
</p>
<h3><span class="mw-headline" id="Algorithm">Algorithm</span></h3>
<p>Pruning Algorithm:
</p>
<ul><li> Initialization:
<ul><li> let $T^1$ be the tree obtained with $\alpha^1 = 0$</li>
<li> by minimizing $R(T)$</li></ul></li>
<li> Step 1
<ul><li> select node $t \in T^1 $ that minimizes 
<ul><li> $g_1(t) = \cfrac{R(t) - R(T^1_t)}{|f(T^1_t)| - 1}$</li></ul></li>
<li> let $t_1$ be this node</li>
<li> let $\alpha^2 = g_1(t_1)$ and $T^2 = T^1 - T^1_{t_1}$</li></ul></li>
<li> step $i$
<ul><li> select node $t \in T^i $ that minimizes 
<ul><li> $g_i(t) = \cfrac{R(t) - R(T^i_t)}{|f(T^i_t)| - 1}$</li></ul></li>
<li> let $t_i$ be this node</li>
<li> let $\alpha^{i + 1} = g_i(t_i)$ and $T^{i+1} = T^i - T^i_{t_i}$</li></ul></li></ul>
<p><br />
Output:
</p>
<ul><li> a sequence of trees $T^1 \supseteq T^2 \supseteq \ ... \ \supseteq T^k \supseteq \ ... \ \supseteq \{ \text{root} \}$</li>
<li> a sequence of parameters $\alpha^1 \leqslant \alpha^2 \leqslant \ ... \ \leqslant \alpha^k \leqslant \ ... $</li></ul>
<p><br />
</p>
<h3><span class="mw-headline" id="Choosing_.24.5Calpha.24">Choosing $\alpha$</span></h3>
<p>The algorithm outputs $\alpha^1 \leqslant \alpha^2 \leqslant \ ... \ \leqslant \alpha^k \leqslant \ ... $
</p>
<ul><li> need to choose some $\alpha \in [\alpha^k, \alpha^{k+1} lot )$</li>
<li> let $\alpha \in [\alpha^k, \alpha^{k+1} )$</li></ul>
<p>How to choose $\alpha$
</p>
<ul><li> use <a href="/index.php/Cross-Validation" title="Cross-Validation">Cross-Validation</a></li>
<li> it's the parameter that minimizes the validation error</li>
<li> thus helps avoid <a href="/index.php/Overfitting" title="Overfitting">Overfitting</a></li></ul>
<p><br />
</p>
<h2><span class="mw-headline" id="Example">Example</span></h2>
<h3><span class="mw-headline" id="Example_1">Example 1</span></h3>
<p>Suppose we have the following tree:
</p>
<ul><li> <img src="https://raw.githubusercontent.com/alexeygrigorev/wiki-figures/master/ufrt/kddm/decision-tree-pruning-ex1-1.png" alt="decision-tree-pruning-ex1-1.png" /></li>
<li> we want to prune it </li>
<li> we have 3 inner nodes where we can prune: $t_1 \equiv \text{root}, t_2, t_3$</li></ul>
<p>Some formulas:
</p>
<ul><li> $R(T_t)$ - training error of a subtree $T_t$ - a tree with root at node $t$
<ul><li> $R(T_t) = \sum_{l \in f(T_t)} R(l)$ - sum of all training errors over all leaves</li></ul></li>
<li> $R_(t)$ - training error of node $t$
<ul><li> $R_(t)  = r(t) \cdot p(t)$ </li>
<li> $r(t)$ - misclassification error at this none (without considering the leaves)</li>
<li> $p(t)$ - proportion of data items reached $t$ (i.e. # of items reached $t$ divided by # of training items)</li></ul></li>
<li> $g(t) = \cfrac{R(t) - R(T_{T_t})}{| f(T_t) | - 1}$
<ul><li> $| f(T_t) | - 1$ is the number of leaves to prune </li></ul></li></ul>
<p><br />
<b>Iteration 1:</b>
</p>
<ul><li> let $\alpha^{(1)} = 0$</li></ul>
<table class="wikitable">
<tr>
<th> $t$ </th>
<th> $R_(t)$ </th>
<th> $R(T_t)$ </th>
<th> $g(t)$
</th></tr>
<tr>
<td> $t_1$ </td>
<td> $\cfrac{8}{16} \cdot \cfrac{16}{16}$ </td>
<td> $T_{t_1}$ - the entire tree <br /> all leaves are pure <br /> $R(T_{t_1}) = 0$ </td>
<td> $\cfrac{8/16 - 0}{4 - 1} = \cfrac{1}{6}$
</td></tr>
<tr>
<td> $t_2$ </td>
<td> $\cfrac{4}{12} \cdot \cfrac{12}{16} = \cfrac{4}{16}$ <br /> (there are 12 records, 4 $\blacksquare$ + 8 $\bigcirc$ ) </td>
<td> $R(T_{t_2}) = 0$ </td>
<td> $\cfrac{4/16 - 0}{3 - 1} = \cfrac{1}{8}$
</td></tr>
<tr>
<td> $t_3$ </td>
<td> $\cfrac{2}{6} \cdot \cfrac{6}{16} = \cfrac{2}{16}$  </td>
<td> $R(T_{t_3}) = 0$ </td>
<td>  $\cfrac{2/16 - 0}{3 - 1} = \cfrac{1}{8}$
</td></tr></table>
<p>We want to find the minimal $g(t)$ 
</p>
<ul><li> it's $g(t_2)$ and $g(t_3)$</li>
<li> in case of a tie, we choose the one that prunes fewer nodes</li>
<li> i.e. $g(t_3)$</li>
<li> so prune at $t_3$</li>
<li> let $\alpha^{(2)} = 1/8$ (the min $g(t)$)</li></ul>
<p><img src="https://raw.githubusercontent.com/alexeygrigorev/wiki-figures/master/ufrt/kddm/decision-tree-pruning-ex1-2.png" alt="decision-tree-pruning-ex1-2.png" />
</p><p><br />
</p><p><b>Iteration 2:</b>
</p>
<ul><li> in the tree now we have only candidates: $t_1$ and $t_2$</li></ul>
<p><br />
</p>
<table class="wikitable">
<tr>
<th> $t$ </th>
<th> $R_(t)$ </th>
<th> $R(T_t)$ </th>
<th> $g(t)$
</th></tr>
<tr>
<td> $t_1$ </td>
<td> $\cfrac{8}{16} \cdot \cfrac{16}{16}$ </td>
<td> $\cfrac{2}{16}$ </td>
<td> $\cfrac{8/16 - 2/16}{3 - 1} = \cfrac{6}{32}$
</td></tr>
<tr>
<td> $t_2$ </td>
<td> $\cfrac{4}{12} \cdot \cfrac{12}{16}$ </td>
<td> $\cfrac{2}{16}$ </td>
<td> $\cfrac{4/16 - 2/16}{2 - 1} = \cfrac{1}{8}$
</td></tr></table>
<p><br />
Find minimal $g(t)$: 
</p>
<ul><li> it's $g(t_2) = 1/8$</li>
<li> let $\alpha^{(3)} = 1/8$</li>
<li> prune at $t_2$</li>
<li> <img src="https://raw.githubusercontent.com/alexeygrigorev/wiki-figures/master/ufrt/kddm/decision-tree-pruning-ex1-3.png" alt="decision-tree-pruning-ex1-3.png" /></li></ul>
<p><br />
</p><p><b>Iteration 3:</b>
</p>
<ul><li> only one candidate for pruning: $t_1$</li>
<li> $\alpha^{(4)} = g(t_1) = \cfrac{8/16 - 4/16}{2 - 1} = \cfrac{1}{4}$</li></ul>
<p><br />
</p><p><b>Selecting the best</b>:
</p>
<ul><li> we have these values: $\alpha^{(0)} = 0, \alpha^{(1)} = 1/8, \alpha^{(2)} = 1/8, \alpha^{(3)} = 1/4$</li>
<li> by the theorem we want to find tree such $T$ that minimizes the cost-complexity function 
<ul><li> if $0 \geqslant \alpha &lt; 1/8$, then $T_1$ is the best</li>
<li> if $\alpha = 1/8$, then $T_2$ is the best</li>
<li> if $1/8 &lt; \alpha &lt; 1/4$, then $T_3$ is the best</li>
<li> if $1/8 &lt; \alpha &lt; 1/4$, then $T_3$ is the best</li></ul></li>
<li> to choose $\alpha$ use <a href="/index.php/Cross-Validation" title="Cross-Validation">Cross-Validation</a></li></ul>
<p><br />
</p>
<h3><span class="mw-headline" id="Example_2">Example 2</span></h3>
<p>From IT4BI 2013 year exam:
</p>
<ul><li> see <a rel="nofollow" class="external text" href="https://docs.google.com/document/d/1d0Mh6XBX9NVyDExkVRNFIbrGGIwDugNDnP75xuDX9Aw/pub">here</a></li></ul>
<p><br />
</p>


