\documentclass[ignorenonframetext,]{beamer}
\setbeamertemplate{caption}[numbered]
\setbeamertemplate{caption label separator}{: }
\setbeamercolor{caption name}{fg=normal text.fg}
\beamertemplatenavigationsymbolsempty
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\newif\ifbibliography
\hypersetup{
            pdftitle={TMA4268 Statistical Learning V2018},
            pdfauthor={Mette Langaas, Thea Roksvåg, Julia Debik, Department of Mathematical Sciences, NTNU},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\usepackage{framed}
\definecolor{shadecolor}{RGB}{248,248,248}
\newenvironment{Shaded}{\begin{snugshade}}{\end{snugshade}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.00,0.00,0.81}{#1}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.31,0.60,0.02}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.00,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.13,0.29,0.53}{\textbf{#1}}}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.81,0.36,0.00}{\textbf{#1}}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textit{#1}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.77,0.63,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.56,0.35,0.01}{\textbf{\textit{#1}}}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{0.94,0.16,0.16}{#1}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{0.64,0.00,0.00}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\usepackage{longtable,booktabs}
\usepackage{caption}
% These lines are needed to make table captions work with longtable:
\makeatletter
\def\fnum@table{\tablename~\thetable}
\makeatother
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight0.8\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}

% Prevent slide breaks in the middle of a paragraph:
\widowpenalties 1 10000
\raggedbottom

\AtBeginPart{
  \let\insertpartnumber\relax
  \let\partname\relax
  \frame{\partpage}
}
\AtBeginSection{
  \ifbibliography
  \else
    \let\insertsectionnumber\relax
    \let\sectionname\relax
    \frame{\sectionpage}
  \fi
}
\AtBeginSubsection{
  \let\insertsubsectionnumber\relax
  \let\subsectionname\relax
  \frame{\subsectionpage}
}

\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}

\title{TMA4268 Statistical Learning V2018}
\subtitle{Module 8: TREE-BASED METHODS}
\author{Mette Langaas, Thea Roksvåg, Julia Debik, Department of Mathematical
Sciences, NTNU}
\date{week 10, 2018 (version 04.03.2018)}

\begin{document}
\frame{\titlepage}

\begin{frame}

\begin{block}{Learning material for this module:}

\begin{itemize}
\tightlist
\item
  James et al (2013): An Introduction to Statistical Learning. Chapter
  8.\\
\item
  \href{https://www.math.ntnu.no/emner/TMA4268/2018v/notes/TMA4268ClassnotesM81.pdf}{Classnotes
  05.02.2018}
\item
  \href{https://www.math.ntnu.no/emner/TMA4268/2018v/notes/TMA4268ClassnotesM82.pdf}{Classnotes
  07.02.2018}
\end{itemize}

\end{block}

\end{frame}

\begin{frame}

\begin{block}{Move to:}

\begin{itemize}
\tightlist
\item
  \protect\hyperlink{intro}{Introduction}
\item
  \protect\hyperlink{regr}{Regression tree}
\item
  \protect\hyperlink{prune}{Pruning}
\item
  \protect\hyperlink{class}{Classification tree}
\item
  \protect\hyperlink{bagging}{Bagging}
\item
  \protect\hyperlink{rf}{Random forest}
\item
  \protect\hyperlink{boost}{Boosting}
\item
  \protect\hyperlink{summing}{Summing up}
\item
  \protect\hyperlink{recex}{Recommended exercises}
\item
  \protect\hyperlink{further}{Further reading}
\item
  \protect\hyperlink{Rpackages}{Packages to install before knitting this
  R Markdown file}
\end{itemize}

\end{block}

\end{frame}

\begin{frame}{ Introduction}

\begin{block}{What will you learn?}

\begin{itemize}
\item
  Regression trees

  \begin{itemize}
  \tightlist
  \item
    what is a tree
  \item
    how to grow a tree
  \item
    how to prune a tree
  \end{itemize}
\item
  Classification trees - any changes to the above
\item
  Bagging
\item
  Variable importance plots
\item
  Random forests
\item
  Boosting
\end{itemize}

\end{block}

\end{frame}

\begin{frame}{Artifical data: Detection of Minor Head Injury}

Assume that you work as a statistician at a hospital, and the head of
department asks you to develop a

\emph{simple method for detecting whether a patient is at risk for
having a minor head injury}.

The method should be easy to

\begin{itemize}
\tightlist
\item
  interpret for the medical personell that are not skilled in
  statistics, and
\item
  the method should be fast, such that the medical personell quickly can
  identify a patient that needs treatment.
\end{itemize}

\end{frame}

\begin{frame}[fragile]

You have the following dataset available: \footnotesize

\begin{verbatim}
##    amnesia.before basal.skull.fracture GCS.decrease GCS.13 GCS.15.2hours
## 3               0                    0            0      0             0
## 9               0                    0            0      0             0
## 11              0                    0            0      0             0
## 12              1                    0            0      0             0
## 14              0                    0            0      0             0
## 16              0                    0            0      0             0
##    high.risk loss.of.consciousness open.skull.fracture vomiting
## 3          0                     0                   0        0
## 9          1                     0                   0        0
## 11         0                     0                   0        0
## 12         0                     0                   0        0
## 14         0                     0                   0        0
## 16         0                     0                   0        0
##    clinically.important.brain.injury age
## 3                                  0  44
## 9                                  0  67
## 11                                 0  62
## 12                                 0   1
## 14                                 0  55
## 16                                 0  63
\end{verbatim}

\normalsize

\end{frame}

\begin{frame}

\begin{itemize}
\tightlist
\item
  The variable \emph{clinically.important.brain.injury} will be the
  response of our model: It has value 1 if a person has an acute brain
  injury, and 0 otherwise.
\item
  In this dataset, 250 (19\%) of the patients have a clinically
  important brain injury.
\item
  The remaining 10 variables in the dataset will be used as explanatory
  variables. These variables describe the state of the patient:

  \begin{itemize}
  \tightlist
  \item
    Is he/she vomiting?
  \item
    Is he/she in a age where there is a larger risk for getting a head
    injury?
  \item
    Has he/she had a loss of consciousness?
  \item
    and so on.
  \end{itemize}
\end{itemize}

\end{frame}

\begin{frame}

These are questions the medical staff ask themselves when diagnosing the
patient. Our job as a statistician is to systemize these questions in a
good way so we can use them to estimate the probability of a brain
injury.

This can be done by using tree-based methods.

The dataset includes data about 1321 patients and is a modified and
smaller version of the (simulated) dataset \emph{headInjury} from the
\emph{DAAG} library. We have made \emph{age} instead of \emph{age.65}
giving us the ``exact''" age of the patient.

\end{frame}

\begin{frame}

\begin{block}{Main idea}

The main idea behind tree-based methods is to

\begin{itemize}
\tightlist
\item
  derive a set of decision rules for segmenting the predictor space into
  a number of regions.
\item
  In order to make a prediction for a new observation, we classify the
  observation into one of these regions by applying the decision rules.
\item
  Then we typically use the mean or a majority vote of the training
  observations in this region as the prediction.
\end{itemize}

Below is a clasification tree made from a training set of 850 randomly
drawn observations.

\end{block}

\end{frame}

\begin{frame}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-2-1.pdf}

\end{frame}

\begin{frame}[fragile]

\footnotesize

\begin{verbatim}
## node), split, n, deviance, yval, (yprob)
##       * denotes terminal node
## 
##  1) root 850 816.00 0 ( 0.8141 0.1859 )  
##    2) GCS.15.2hours: 0 717 530.00 0 ( 0.8787 0.1213 )  
##      4) basal.skull.fracture: 0 664 407.00 0 ( 0.9081 0.0919 )  
##        8) high.risk: 0 503 222.00 0 ( 0.9423 0.0577 )  
##         16) age < 67.5 455 145.00 0 ( 0.9626 0.0374 ) *
##         17) age > 67.5 48  54.00 0 ( 0.7500 0.2500 )  
##           34) loss.of.consciousness: 0 42  37.80 0 ( 0.8333 0.1667 ) *
##           35) loss.of.consciousness: 1 6   5.41 1 ( 0.1667 0.8333 ) *
##        9) high.risk: 1 161 161.00 0 ( 0.8012 0.1988 ) *
##      5) basal.skull.fracture: 1 53  73.50 0 ( 0.5094 0.4906 )  
##       10) age < 67 46  62.40 0 ( 0.5870 0.4130 ) *
##       11) age > 67 7   0.00 1 ( 0.0000 1.0000 ) *
##    3) GCS.15.2hours: 1 133 184.00 1 ( 0.4662 0.5338 )  
##      6) age < 63.5 94 128.00 0 ( 0.5745 0.4255 )  
##       12) high.risk: 0 62  72.80 0 ( 0.7258 0.2742 )  
##         24) GCS.13: 0 55  55.00 0 ( 0.8000 0.2000 ) *
##         25) GCS.13: 1 7   5.74 1 ( 0.1429 0.8571 ) *
##       13) high.risk: 1 32  38.00 1 ( 0.2812 0.7188 )  
##         26) vomiting: 0 22  29.80 1 ( 0.4091 0.5909 ) *
##         27) vomiting: 1 10   0.00 1 ( 0.0000 1.0000 ) *
##      7) age > 63.5 39  39.60 1 ( 0.2051 0.7949 ) *
\end{verbatim}

\normalsize

\end{frame}

\begin{frame}

By using simple decision rules related to the most important explanatory
variables the medical staff can now assess the probability of a brain
injury.

For example if the Glasgow Coma Scale of the patient is 15
(\emph{GCS.15.2hours=1}) and the patient is older than 63 year then we
should predict a minor injury according to the fitted tree, and the
probability of that is estimated to be 0.7949 (node 7 in printout).

\begin{itemize}
\tightlist
\item
  The advantage of such decisions trees is that they are easier to
  interpret than many of the classification (and regression) methods
  that we have studied so far
\item
  and they provide an easy way to visualize the data for
  non-statisticians.
\end{itemize}

\end{frame}

\begin{frame}{Glossary}

\begin{itemize}
\tightlist
\item
  Classification and regression trees are usually drawn upside down,
  where the top node is called the \emph{root}.
\item
  The \emph{terminal nodes} or \emph{leaf nodes} are the nodes at the
  bottom, with no splitting criteria. These represent the final
  predicted class (for classification trees) or predicted response value
  (for regression trees) and are written symbolically as \(R_j\) for
  \(j = 1, 2, ..., J\).
\item
  \emph{Internal nodes} are all nodes between the root and the terminal
  nodes. These nodes correspond to the partitions of the predictor
  space.
\end{itemize}

\end{frame}

\begin{frame}{Constructing a decision tree}

You can construct decision trees for both classification and regression
problems. How do we construct a regression tree?

\begin{block}{Regression tree}

Assume that we have a dataset consisting of \(N\) quantitative responses
\((y_1,y_2,...,y_i,...,y_N)\) and that each response has \(p\)
corresponding predictors \(x_i=(x_{i1},x_{i2},...,x_{ip})\) for
\(i=1,..,N\).

When constructing the regression tree,the goal is to divide the set of
possible values of each of the predictors \(X_1,X_2,...,X_p\) into \(J\)
non-overlapping regions, \(R_1, R_2,...,R_J\). This is done by finding
boxes that minimize the RSS given by \[
RSS=\sum_{j=1}^J \sum_{i \in R_j}(y_i-\hat{y}_{R_j})^2,
\] where \(\hat{y}_{R_j}\) is the mean response for the training
observations in region \(j\). The mean \(\hat{y}_{R_j}\) is also the
predicted value for a new observations that falls into region \(j\).

Ideally, we should consider every partition of the predictor space
\(X_1, X_2,..., X_p\) when partitioning the predictor space, and compute
the \(RSS\) for each partition. However, this is computationally
unfeasible so we need to find an easier approach: An approach known as
recursive binary splitting is often used.

\end{block}

\end{frame}

\begin{frame}[fragile]{Unresolved}

\begin{itemize}
\tightlist
\item
  Kanskje man m?? bruke et annet datasett for ?? illustrere regresjon
  bedre? (Et datasett som ikke bare har 0 og 1 som response).
\end{itemize}

\begin{block}{Recursive binary splitting}

We start at the top of the tree and divide the predictor space into two
regions, \(R_1\) and \(R_2\) by making a decision rule for one of the
predictors \(X_1, X_2,...,X_p\). If we define the two regions by
\(R_1(j,s)=\{X|X_j<s\}\) and \(R_2(j,s)=\{X|X_j\geq s\}\), it means that
we need to find the \(j\) and \(s\) that minimize \[
RSS_{12}=\sum_{i: x_i \in R_1(j,s)}(y_i-\hat{y}_{R_1})^2+\sum_{i: x_i \in R_2(j,s)}(y_i -\hat{y}_{R_2})^2,
\] where \(\hat{y}_{R_1}\) and \(\hat{y}_{R_2}\) are the mean responses
for the training observations in \(R_1(j,s)\) and \(R_2(j,s)\)
respectively. This way we get the two first branches in our decision
tree.

We repeat the process to make branches further down in the tree. For
every iteration we let each single split depend on only one of the
predictors, giving us two new branches. This is done successively and in
each step we choose the split that gives the best split at that
particular step, i.e the split that gives the smallest RSS. We don't
consider splits in the future that might give a tree with a lower
overall RSS.

We continue splitting the predictor space until we reach some stopping
criterion. For example we stop when no region contains more than five
observations or when the reduction in the RSS is smaller than a
specified limit.

\end{block}

\begin{block}{\(\oplus\) Questions}

\begin{itemize}
\tightlist
\item
  Why is recursive binary splitting classified as a greedy algorithm?
\item
  Discuss the advantages by letting each single split depend on only one
  of the predictors.
\end{itemize}

\end{block}

\begin{block}{Regression tree example: Ozone concentration}

Consider the \texttt{ozone} data set from the \texttt{ElemStatLearn}
library. The data set consists of 111 observations on the following
variables:

\begin{itemize}
\tightlist
\item
  \texttt{ozone} : the concentration of ozone in ppb
\item
  \texttt{radiation}: the solar radiation (langleys)
\item
  \texttt{temperature} : the daily maximum temperature in degrees F
\item
  \texttt{wind} : wind speed in mph
\end{itemize}

Suppose we want to get an estimate of the ozone concentration based on
the measurement of wind speed and the daily maximum temperature.

\begin{longtable}[]{@{}rrrr@{}}
\toprule
ozone & radiation & temperature & wind\tabularnewline
\midrule
\endhead
41 & 190 & 67 & 7.4\tabularnewline
36 & 118 & 72 & 8.0\tabularnewline
12 & 149 & 74 & 12.6\tabularnewline
18 & 313 & 62 & 11.5\tabularnewline
23 & 299 & 65 & 8.6\tabularnewline
19 & 99 & 59 & 13.8\tabularnewline
\bottomrule
\end{longtable}

We can fit a regression tree to the data, with \texttt{ozone} as our
response variable and \texttt{temperature} and \texttt{wind} as
covariates. This gives us the following regression tree.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{ozone.tree =}\StringTok{ }\KeywordTok{tree}\NormalTok{(ozone}\OperatorTok{~}\NormalTok{temperature}\OperatorTok{+}\NormalTok{wind, }\DataTypeTok{data=}\NormalTok{ozone)}
\KeywordTok{plot}\NormalTok{(ozone.tree)}
\KeywordTok{text}\NormalTok{(ozone.tree)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-5-1.pdf}

Starting at the top of the tree, we can move downwards, by following the
criteria at each node. The numbers on the bottom are called the leaf
nodes, and in this example give the predicted ozone levels. We see that
\texttt{temperature} is the most important covariate for predicting the
ozone concentration. Given a temperature below \(82.5^\circ\) F, and a
low wind speed, the ozone level is high. For a low temperature and a
high wind speed, the ozone level is lower. The highest ozone level is
with a high temperature in combination with a wind speed below 10.6.

\end{block}

\end{frame}

\begin{frame}[fragile]

Now let's take a look at how the tree has been constructed. Below we see
the partition of the \texttt{ozone} data set from the
\texttt{ozone.tree}, where the ozone levels have been color-coded, where
a darker color corresponds to a higher ozone concentration. We recognize
the numbers from the leaf nodes on the figure. Each rectangle
corresponds to one leaf node. Each number corresponding to a leaf node
have been found by taking an average of all observations in the
corresponding region (rectangle). Each line corresponds to an internal
node, a binary partition of the predictor space.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{o.class =}\StringTok{ }\KeywordTok{cut}\NormalTok{(ozone}\OperatorTok{$}\NormalTok{ozone, }\DataTypeTok{breaks=} \DecValTok{7}\NormalTok{)}

\NormalTok{col.oz =}\StringTok{ }\KeywordTok{brewer.pal}\NormalTok{(}\DecValTok{9}\NormalTok{, }\StringTok{"BuGn"}\NormalTok{)}
\KeywordTok{palette}\NormalTok{(col.oz[}\DecValTok{3}\OperatorTok{:}\DecValTok{9}\NormalTok{]) }
\KeywordTok{par}\NormalTok{(}\DataTypeTok{mar=}\KeywordTok{c}\NormalTok{(}\FloatTok{5.1}\NormalTok{, }\FloatTok{4.1}\NormalTok{, }\FloatTok{2.1}\NormalTok{, }\FloatTok{8.1}\NormalTok{), }\DataTypeTok{xpd=}\OtherTok{TRUE}\NormalTok{)}
\KeywordTok{plot}\NormalTok{(wind}\OperatorTok{~}\NormalTok{temperature, }\DataTypeTok{col=}\NormalTok{o.class, }\DataTypeTok{data=}\NormalTok{ozone, }\DataTypeTok{pch=}\DecValTok{20}\NormalTok{)}
\KeywordTok{partition.tree}\NormalTok{(ozone.tree, }\DataTypeTok{add=}\OtherTok{TRUE}\NormalTok{)}
\KeywordTok{legend}\NormalTok{(}\StringTok{'topright'}\NormalTok{, }\DataTypeTok{inset=}\KeywordTok{c}\NormalTok{(}\OperatorTok{-}\FloatTok{0.3}\NormalTok{,}\FloatTok{0.2}\NormalTok{), }
       \DataTypeTok{title=}\StringTok{"Ozone conc."}\NormalTok{, }\DataTypeTok{legend =} \KeywordTok{levels}\NormalTok{(o.class), }
       \DataTypeTok{col=}\NormalTok{col.oz[}\DecValTok{3}\OperatorTok{:}\DecValTok{9}\NormalTok{], }\DataTypeTok{pch=}\DecValTok{20}\NormalTok{, }\DataTypeTok{box.col=}\OtherTok{NA}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-6-1.pdf}

We now grow a full tree: we include the covariate \texttt{radiation} in
our model. To test the predictive performance of our regression tree, we
can randomly divide our observations into a test and a training set. The
training set consists of approximately 2/3 of the observations, the test
set consists of the remaining observations. We fit a tree to the
training set, and use this tree to make predictions for the test set. We
evaluate the predictive performance by calculating the mean squared
error (MSE):

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{200}\NormalTok{)}
\NormalTok{ozone.trainID =}\StringTok{ }\KeywordTok{sample}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\DecValTok{111}\NormalTok{, }\DecValTok{75}\NormalTok{)}
\NormalTok{ozone.train =}\StringTok{ }\NormalTok{ozone[ozone.trainID, ]}
\NormalTok{ozone.test =}\StringTok{ }\NormalTok{ozone[}\OperatorTok{-}\NormalTok{ozone.trainID,]}

\NormalTok{ozone.full =}\StringTok{ }\KeywordTok{tree}\NormalTok{(ozone}\OperatorTok{~}\NormalTok{., }\DataTypeTok{data=}\NormalTok{ozone.train)}

\NormalTok{ozone.pred =}\StringTok{ }\KeywordTok{predict}\NormalTok{(ozone.full, }\DataTypeTok{newdata=}\NormalTok{ozone.test)}
\NormalTok{ozone.MSE =}\StringTok{ }\KeywordTok{mean}\NormalTok{((ozone.pred}\OperatorTok{-}\NormalTok{ozone.test}\OperatorTok{$}\NormalTok{ozone)}\OperatorTok{^}\DecValTok{2}\NormalTok{)}
\NormalTok{ozone.MSE}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## [1] 296.953
\end{verbatim}

\end{frame}

\begin{frame}{R: function \texttt{tree} in library \texttt{tree}}

tree \{tree\} R Documentation Fit a Classification or Regression Tree

Description: A tree is grown by binary recursive partitioning using the
response in the specified formula and choosing splits from the terms of
the right-hand-side.

Usage:

tree(formula, data, weights, subset, na.action = na.pass, control =
tree.control(nobs, \ldots{}), method = ``recursive.partition'', split =
c(``deviance'', ``gini''), model = FALSE, x = FALSE, y = TRUE, wts =
TRUE, \ldots{})

Details:

A tree is grown by binary recursive partitioning using the response in
the specified formula and choosing splits from the terms of the
right-hand-side. Numeric variables are divided into X \textless{} a and
X \textgreater{} a; the levels of an unordered factor are divided into
two non-empty groups. The split which maximizes the reduction in
impurity is chosen, the data set split and the process repeated.
Splitting continues until the terminal nodes are too small or too few to
be split.

Tree growth is limited to a depth of 31 by the use of integers to label
nodes.

Factor predictor variables can have up to 32 levels. This limit is
imposed for ease of labelling, but since their use in a classification
tree with three or more levels in a response involves a search over
2\^{}(k-1) - 1 groupings for k levels, the practical limit is much less.

tree.control(nobs, mincut = 5, minsize = 10, mindev = 0.01) Arguments

nobs\\
The number of observations in the training set. mincut\\
The minimum number of observations to include in either child node. This
is a weighted quantity; the observational weights are used to compute
the `number'. The default is 5. minsize The smallest allowed node size:
a weighted quantity. The default is 10. mindev\\
The within-node deviance must be at least this times that of the root
node for the node to be split.

\end{frame}

\begin{frame}[fragile]

SKAL DETTE MED FOR OZONE?

Further, we want to test the predictive performance of the model.
\(850\) observations were used to construct the tree, while \(471\)
observations were left out. We predict the response for these \(471\)
observations and evaluate the predictive performance by mean squared
error:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{tree.pred=}\KeywordTok{predict}\NormalTok{(tree.HI,headInjury2[test,]) }\CommentTok{#Predicted status of the pasients.}
\NormalTok{response.test=headInjury2}\OperatorTok{$}\NormalTok{clinically.important.brain.injury[test] }\CommentTok{#True status of the pasients.}
\NormalTok{MSE=}\KeywordTok{mean}\NormalTok{((tree.pred}\OperatorTok{-}\NormalTok{response.test)}\OperatorTok{^}\DecValTok{2}\NormalTok{)}
\KeywordTok{print}\NormalTok{(MSE)}
\end{Highlighting}
\end{Shaded}

Note that the predictions are numbers between 0 and 1 modeling
probabilities, while the true response can only be either 0 or 1.

\begin{block}{\(\oplus\) Questions\#\#\# BYTT TIL OZONE}

\begin{itemize}
\tightlist
\item
  Consider the \protect\hyperlink{mainidea}{regression tree} again. In
  our training set, \(100 \%\) of the patients with
  \emph{GCS.15.2hours}\(=0\), \emph{basal.skull.facture}\(=1\) and
  \emph{age\textgreater{}}\(67\) had a clinically important brain
  injury. Keep in mind that it is possible that this number is based on
  a small number of patients. In our training dataset it turns out that
  only \(6\) of the patients share these attributes, meaning that if a
  new patient falls into this category we do a prediction based on \(6\)
  former patients. What impact does this have on the predictions?
\end{itemize}

\end{block}

\begin{block}{Classification trees}

We go back to the \emph{headInjury2} dataset.

Building a decision tree in this setting is similar to building a
regression tree for a quantitative response, but there are two main
differences:

\textbf{1) The prediction:}

\begin{itemize}
\tightlist
\item
  In the regression case we use the mean value of the responses in
  \(R_j\) as a prediction for an observation that falls into region
  \(R_j\).
\item
  For the classification case however, we have two possibilities:

  \begin{itemize}
  \tightlist
  \item
    Majority vote: Predict that the observation belongs to the most
    commonly occurring class of the training observations in \(R_j\).\\
  \item
    Another possibility is to estimate the probability that an
    observation \(x_i\) belongs to a class \(k\), \(\hat{p}_{mk}(x_i)\),
    and then classify according to a threshold value. This estimated
    probability is the proportion of class \(k\) observations in region
    \(R_m\) with \(N_m\) observations:
    \[\hat{p}_{mk} = \frac{1}{N_m} \sum_{x_i \in R_m} I(y_i = k).\]
  \end{itemize}
\end{itemize}

\textbf{2) The splitting criterion:} We can not use RSS as a splitting
criterion for a qualitative variable. Instead we can use the Gini index
or the cross-entropy. These are defined as \[
G=\sum_{k=1}^K \hat{p}_{mk}(1-\hat{p}_{mk}),
\] and \[
D=-\sum_{k=1}^K \hat{p}_{mk}log\hat{p}_{mk}
\] respectively, where \(\hat{p}_{mk}\) is the proportion of training
observation in region \(m\) that are from class \(k\). When making a
split in our classification tree, we want to minimize the Gini index or
the cross-entropy.

\end{block}

\begin{block}{Example}

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{tree.HIClass=}\KeywordTok{tree}\NormalTok{(clinically.important.brain.injury}\OperatorTok{~}\NormalTok{.,headInjury2,}\DataTypeTok{subset=}\NormalTok{train)}
\KeywordTok{plot}\NormalTok{(tree.HIClass)}
\KeywordTok{text}\NormalTok{(tree.HIClass,}\DataTypeTok{pretty=}\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-9-1.pdf}

We also use the classification tree to predict the status of the
patients in the test set:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{tree.pred=}\KeywordTok{predict}\NormalTok{(tree.HIClass,headInjury2[test,],}\DataTypeTok{type=}\StringTok{"class"}\NormalTok{)}

\NormalTok{misclass=}\KeywordTok{table}\NormalTok{(tree.pred,headInjury2[test,]}\OperatorTok{$}\NormalTok{clinically.important.brain.injury)}

\KeywordTok{print}\NormalTok{(misclass)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
##          
## tree.pred   0   1
##         0 361  50
##         1  18  42
\end{verbatim}

The table shows how often the classification tree provides a correct
prediction of the status of the patient. For example the number in row
1, column 2 is the number of times the tree predicts ``no'' when the
real answer is ``yes''. The misclassification rate is given by

\begin{Shaded}
\begin{Highlighting}[]
\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(misclass))}\OperatorTok{/}\NormalTok{(}\KeywordTok{sum}\NormalTok{(misclass))}
\end{Highlighting}
\end{Shaded}

\end{block}

\end{frame}

\begin{frame}{Unresolved}

\begin{itemize}
\tightlist
\item
  Skal man heller gi ut sannsynligheter i stedet for ``yes'' og ``no''?
  Er dette mulig? Kommer kanskje ogs?? litt an p?? hva vi velger ??
  gj??re med regresjonstreet.
\end{itemize}

\begin{block}{\(\oplus\) Questions}

\begin{itemize}
\item
  Compare the \protect\hyperlink{mainidea}{regression tree} and the
  \protect\hyperlink{classtree2}{classification tree}. The
  classification tree is different from the corresponding regression
  tree even though they are built on the exact same data. How is this
  possible?
\item
  Discuss advantages and disadvantages by modeling this problem as a
  regression problem.
\item
  Discuss advantages and disadvantages by modeling this problem as a
  classification problem.
\item
  Are there cases where the \protect\hyperlink{mainidea}{regression
  tree} is more useful than the corresponding
  \protect\hyperlink{classtree2}{classification tree} and vice versa?
\item
  The \protect\hyperlink{classtree2}{classification tree} has two
  terminal nodes with factor ``yes'' originating from the same branch.
  Why do we get this ``unnecessary'' split?
\item
  Study the above confusion matrix (stored in \emph{misclass}). One type
  of mistake is more severe than the other. Discuss if it is possible to
  change the algorithm in order to decrease the number of severe
  mistakes.
\end{itemize}

\end{block}

\end{frame}

\begin{frame}[fragile]{Pruning}

In the \protect\hyperlink{regtree}{regression tree section} we saw that
the prediction in one of the regions was based on only \(6\) patients
from the training set. This may lead to poor predictions for test data.

\(Pruning\) is a technique for solving this problem. By \(pruning\) the
tree we reduce the size or depth of the decision tree. When we reduce
the number of terminal nodes and regions \(R_1,...,R_J\), each region
will probably contain more observations. This way we reduce the
probability of over fitting, and we may get better predictions for test
data.

If we have a large dataset with many explanatory variables and terminal
nodes, we can also prune the tree if we want to create a simpler tree
and increase the interpretability of the model.

In the \protect\hyperlink{classtree2}{classification tree} we saw that
we got several unnecessary splits. This is also something that can be
avoided by pruning.

\begin{block}{Cost complexity pruning}

We can prune the tree by using a algorithm called \emph{Cost complexity
pruning}. We first build a large tree \(T_0\) by recursive binary
splitting. Then we try to find a subtree \(T\subset T_0\) that minimizes

\[
C_{\alpha}(T)=\sum_{m=1}^{|T|}\sum_{x_i\in R_m}(y_i - \hat{y}_{R_m})^2+\alpha |T|,
\] where \(|T|\) is the number of terminal nodes in tree \(T\). The
parameter \(\alpha\) is then a parameter penalizing the number of
terminal nodes, ensuring that the tree does not get too many branches.
We proceed by repeating the the process for the best subtree \(T\), and
this way we get a sequence of smaller of smaller subtrees where each
tree is the best subtree of the previous tree.

See \href{https://folk.ntnu.no/bo/MA8701/2017v/CART1.pdf}{this note} for
an example of how we perform cost complexity pruning.

\begin{block}{Example}

We continue using the \protect\hyperlink{classtree2}{classification
tree}. First we want to find the optimal number of terminal nodes by
cross validation. This can be done by using the function
\emph{cv.tree()}:

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{1}\NormalTok{)}
\NormalTok{cv.head=}\KeywordTok{cv.tree}\NormalTok{(tree.HIClass,}\DataTypeTok{FUN=}\NormalTok{prune.misclass)}

\KeywordTok{par}\NormalTok{(}\DataTypeTok{pty=}\StringTok{"s"}\NormalTok{)}
\KeywordTok{plot}\NormalTok{(cv.head}\OperatorTok{$}\NormalTok{size,cv.head}\OperatorTok{$}\NormalTok{dev,}\DataTypeTok{type=}\StringTok{"b"}\NormalTok{,}\DataTypeTok{xlab=}\StringTok{"Terminal nodes"}\NormalTok{,}\DataTypeTok{ylab=}\StringTok{"Deviance"}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-12-1.pdf}

According to the plot, the deviance is lowest if we use 5 terminal
nodes. Next, we prune the classification tree according to this value:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{prune.HIClass=}\KeywordTok{prune.misclass}\NormalTok{(tree.HIClass,}\DataTypeTok{best=}\DecValTok{5}\NormalTok{) }\CommentTok{#Five node tree.}
\KeywordTok{plot}\NormalTok{(prune.HIClass)}
\KeywordTok{text}\NormalTok{(prune.HIClass,}\DataTypeTok{pretty=}\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-13-1.pdf}

We see that the new tree doesn't have any unnecessary splits, and we
have a simple and interpretable decision tree. How is the predictive
performance of the model affected?

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{tree.pred.prune=}\KeywordTok{predict}\NormalTok{(prune.HIClass,headInjury2[test,],}\DataTypeTok{type=}\StringTok{"class"}\NormalTok{)}
\NormalTok{misclass.prune=}\KeywordTok{table}\NormalTok{(tree.pred,headInjury2[test,]}\OperatorTok{$}\NormalTok{clinically.important.brain.injury)}
\KeywordTok{print}\NormalTok{(misclass.prune)}

\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(misclass.prune))}\OperatorTok{/}\NormalTok{(}\KeywordTok{sum}\NormalTok{(misclass.prune))}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
##          
## tree.pred   0   1
##         0 361  50
##         1  18  42
## [1] 0.144374
\end{verbatim}

We see that the misclassification rate is as small as before indicating
that the pruned tree is as good as the original tree for the test data.

\end{block}

\begin{block}{\(\oplus\) Questions}

Discuss the bias-variance tradeoff of a regression tree when
increasing/decreasing the number of terminal nodes, i.e:

\begin{itemize}
\item
  What happens to the variance of a prediction if we reduce the tree
  size?
\item
  What happens to the bias?
\end{itemize}

\end{block}

\end{block}

\end{frame}

\begin{frame}{Leo Breiman}

Quotation from
\href{https://en.wikipedia.org/wiki/Leo_Breiman}{Wikipedia}

Leo Breiman (January 27, 1928 -- July 5, 2005) was a distinguished
statistician at the University of California, Berkeley. He was the
recipient of numerous honors and awards, and was a member of the United
States National Academy of Science.

Breiman's work helped to bridge the gap between statistics and computer
science, particularly in the field of machine learning. His most
important contributions were his work on classification and regression
trees and ensembles of trees fit to bootstrap samples. Bootstrap
aggregation was given the name bagging by Breiman. Another of Breiman's
ensemble approaches is the random forest.

\end{frame}

\begin{frame}

From
\href{https://www.berkeley.edu/news/media/releases/2005/07/07_breiman.shtml}{Breimans
obituary}

BERKELEY -- Leo Breiman, professor emeritus of statistics at the
University of California, Berkeley.

``It is trite to say so, but Leo Breiman was indeed a Renaissance man,
and we shall miss him greatly,'' said Peter Bickel, professor of
statistics and chairman this summer of UC Berkeley's statistics
department.

Breiman retired in 1993, but as a Professor in the Graduate School, he
continued to get substantial National Science Foundation grants and
supervised three Ph.D.~students. Bickel said that some of Breiman's best
work was done after retirement.

``In particular,'' said Bickel, ``he developed one of the most
successful state-of-the-art classification programs, `Random Forest.'
This method was based on a series of new ideas that he developed in
papers during the last seven years, and it is extensively used in
government and industry.''

Breiman's best known work is considered to be ``Classification and
Regression Trees,'' a work in collaboration with three other scholars
that facilitates practical applications, such as the diagnosis of
diseases, from a multitude of symptoms.

\end{frame}

\begin{frame}[fragile]{Bagging}

Decision trees often suffer from high variance. By this we mean that the
trees are sensitive to small changes in the predictors: If we change the
observation set, we risk to get a very different tree.

Let's draw a new training set for our data and see what happens:

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{33}\NormalTok{)}
\NormalTok{N=}\KeywordTok{dim}\NormalTok{(headInjury2)[}\DecValTok{1}\NormalTok{]}
\NormalTok{train2=}\KeywordTok{sample}\NormalTok{(}\DecValTok{1}\OperatorTok{:}\NormalTok{N,}\DecValTok{850}\NormalTok{) }\CommentTok{#We draw a new training sample. The number of observations is the same as before.}

\NormalTok{tree.HIClass2=}\KeywordTok{tree}\NormalTok{(clinically.important.brain.injury}\OperatorTok{~}\NormalTok{.,headInjury2,}\DataTypeTok{subset=}\NormalTok{train2) }

\KeywordTok{plot}\NormalTok{(tree.HIClass2);}\KeywordTok{text}\NormalTok{(tree.HIClass2,}\DataTypeTok{pretty=}\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-15-1.pdf}

This classification tree is constructed by using \(850\) observations,
just like the tree in the \protect\hyperlink{classtree2}{classification
trees section}, but we get two different trees that will give different
predictions for a test set.

To reduce the variance of decision trees we can apply \emph{Bootstrap
aggregation} (\emph{Bagging}).

Assume we have \(n\) i.i.d. observations of a random variable \(X\) each
with variance \(\sigma^2\). We calculate the mean
\(\bar{X} = \frac{1}{n} \sum_{i=1}^n X_i\). The variance of the mean is
\[\text{Var}(\bar{X}) = \text{Var}\Big(\frac{1}{n}\sum_{i=1}^n X_i \Big) = \frac{1}{n^2} \sum_{i=1}^n \text{Var}(X_i) = \frac{\sigma^2}{n}.\]
By averaging one can reduce the variance. This is the basic idea behind
bagging. However, since we do not have multiple data sets, bagging is
done by drawing \(B\) bootstrap samples from the training data. If we
have \(N\) observations, it means that we draw \(N\) observations from
the dataset (with replacement) for each bootstrap sample.

For each bootstrap sample we construct a decision tree,
\(\hat{f}^{*b}(x)\) with \(b=1,...,B\) and use information from all of
the trees to draw inference. For a regression tree, we typically take
the average of all of the predictions and use this as the final result:
\[
\hat{f}_{bag}(x)=\frac{1}{B}\sum_{b=1}^B \hat{f}^{*b}(x).
\] For a classification tree we record the predicted class for each of
the \(B\) trees and use the most occurring class as the final
prediction.

\begin{block}{Out-of-bag error estimation}

Because we only use a subset of the observations in each bootstrap
sample, we can use the observations that were left out to measure the
predictive performance and thus the error of the fitted model,
\(f^{*b}(x)\). On average each bagged tree only uses around two-thirds
of the observations, giving approximately \(B/3\) predictions for
observation \(i\) (see \protect\hyperlink{Exercises}{Exercises}). The
observations left out are referred to as the \emph{out-of-bag}
observations, and the measured error of the \(B/3\) predictions is
called the \emph{out-of-bag error}. Based on these \(B/3\) predictions
we can make one single prediction (\emph{OOB prediction}) and measure
the prediction error (\emph{OOB error}).

\end{block}

\begin{block}{Example}

We can do bagging by using the function \emph{randomForest()} in the
\emph{randomForest} library.

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(randomForest)}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{1}\NormalTok{)}

\NormalTok{bag=}\KeywordTok{randomForest}\NormalTok{(clinically.important.brain.injury}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{data=}\NormalTok{headInjury2,}\DataTypeTok{subset=}\NormalTok{train,}\DataTypeTok{mtry=}\DecValTok{10}\NormalTok{,}\DataTypeTok{ntree=}\DecValTok{500}\NormalTok{,}\DataTypeTok{importance=}\OtherTok{TRUE}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The variable \emph{mtry=10} because we want to consider all \(10\)
covariates in each split of the tree. The variable \(ntree=500\) because
we want to average over \(500\) trees.

Let's have a look at the predictive performance of the bagged tree:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{yhat.bag=}\KeywordTok{predict}\NormalTok{(bag,}\DataTypeTok{newdata=}\NormalTok{headInjury2[test,])}

\NormalTok{misclass.bag=}\KeywordTok{table}\NormalTok{(yhat.bag,headInjury2[test,]}\OperatorTok{$}\NormalTok{clinically.important.brain.injury)}
\KeywordTok{print}\NormalTok{(misclass.bag)}


\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(misclass.bag))}\OperatorTok{/}\NormalTok{(}\KeywordTok{sum}\NormalTok{(misclass.bag))}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
##         
## yhat.bag   0   1
##        0 351  43
##        1  28  49
## [1] 0.150743
\end{verbatim}

We note that the misclassification rate has increased slightly for the
bagged tree.

\begin{block}{\(\oplus\) Prediction by majority vote vs.~by averaging
the probabilities}

Consider the case when you have grown a classification tree with a
binary response with classes 0 and 1. You might wonder which approach to
choose to make a final prediction: majority vote or an average of the
probabilities? Or would the prediction be the same in each case?

The difference between these two procedures can be compared to the
difference between the mean value and median of a set of numbers. If we
average the probabilities and make a classification thereafter, we have
the mean value. If we sort all of our classifications, so that the
classifications corresponding to one class would be lined up after each
other, followed by the classifications corresponding to the other class
we obtain the median value. We examine this by an example:

Suppose we have bagged a classification tree and have obtained the
following 5 estimated probabilities: \{0.4, 0.4, 0.4, 0.4, 0.9 \}. If we
average the probabilities, we get 0.5, and if we use a cut-off value of
0.5, our predicted class is 1. However, if we take a majority vote,
using the same cut of value, the predicted classes will be \{0, 0, 0, 0,
1 \}. The predicted class, based on a majority vote, would accordingly
be 0.

The two procedures thus have their pros and cons: By averaging the
predictions no information is lost. We do not only get the final
classification, but the probability for belonging to the class 0 or 1.
However, this method is not robust to outliers. By taking a majority
vote, outliers have a smaller influence on the result.

\end{block}

\end{block}

\begin{block}{Variable importance plots}

By applying ensemble methods such as bagging, boosting and random
forests, to decision trees, the predictive power can be highly improved.
However, this comes at a cost of interpretability. Instead of having one
tree, the resulting model consists of \(B\) trees, where \(B\) often is
300 or 500 (or maybe even 5000 when boosting).

Variable importance plots help to overcome this problem as these plots
show the relative importance of the covariates: the variables are sorted
according to their importance, such that the top variables have a higher
importance than the bottom variables. There are in general two types of
variable importance plots: variable importance based on decrease in node
impurity and variable importance based on randomization:

\textbf{Variable importance based on node impurity}

The term \emph{important} relates to total decrease in the node
impurity, over splits for a covariate, and is differently defined for
regression trees and classification trees.

Regression trees: The importance of each covariate is calculated using
the RSS: The algorithm records the total amount that the RSS is
decreased due to splits for each covariate. This RSS is then averaged
over the \(B\) trees. The higher the RSS, the more important the
covariate.

Classification trees: The importance of each covariate is calculated
using the Gini index. The importance is the mean decrease (over all
\(B\) trees) in the Gini index by splits of a covariate.

\textbf{Variable importance based on randomization}

Variable importance based on randomization is calculated using the OOB
sample. Computations are carried out for one bootstrap sample at a time.
Each time a tree is grown the OOB sample is used to test the predictive
power of the tree. Then for one covariate at a time, repeat the
following: permute the OOB observations for the \(j\)th variable \(X_j\)
and calculate the new OOB error. If \(X_j\) is important, permuting its
observations will decrease the predictive performance. The decrease in
accuracy as a result of the permuting is averaged over all trees.

\end{block}

\end{frame}

\begin{frame}[fragile]{Random Forest}

If there is a strong predictor in the dataset, the decision trees
produced by each of the bootstrap samples in the bagging algorithm
becomes very similar: Most of the trees will use the same strong
predictor in the top split.

We have seen this for our four example trees: \emph{GCS.15.2hours} was
chosen in the top split every time. This is probably the case for a
large amount of the bagged trees as well.

This is not optimal, because we get \(B\) trees that are highly
correlated. We don't gain a large reduction in variance by averaging
\(\hat{f}^{*b}(x)\) when the correlation between the trees is high. In
the \protect\hyperlink{bagex}{previous section} we actually saw a
(marginal) decrease in the predictive performance for the bagged tree
compared to the \protect\hyperlink{expruning}{pruned tree} and the
\protect\hyperlink{classtree2}{full tree}.

\(Random forests\) is a solution to this problem and a method for
decorrelating the trees.

We earlier saw that the variance of the average of \(n\) observations of
i.i.d random variables \(X\), each with variance \(\sigma^2\) is
\(\frac{\sigma^2}{n}\). Now, suppose we have \(n\) observations of a
random variable \(X\) which are identically distributed, each with mean
\(\mu\) and variance \(\sigma^2\), but not independent. That is, suppose
the variables have a positive correlation \(\rho\)
\[\text{Cov}(X_i, X_j) = \rho \sigma^2, \quad i \neq j.\] The variance
of the average is
\[\begin{aligned} \text{Var}(\bar{X}) &= \text{Var}\Big( \frac{1}{n}\sum_{i=1}^n X_i \Big) \\
&= \sum_{i=1}^n \frac{1}{n^2} \text{Var} (X_i) + 2 \sum_{i=2}^n \sum_{j=1}^{i-1} \frac{1}{n} \frac{1}{n} \text{Cov} (X_i, X_j) \\
&= \frac{1}{n} \sigma^2 + \frac{n-1}{n} \rho \sigma^2 \\
&= \frac{1}{n} \sigma^2 + \rho \sigma^2 - \frac{1}{n} \rho \sigma^2 \\
&= \rho \sigma^2 + \frac{1-\rho}{n}\sigma^2.\end{aligned}\] The idea
behind random forests is to improve the variance reduction of bagging by
reducing the correlation between the trees, while prevailing a low
variance. The procedure is thus as in bagging, but with the important
difference, that at each split we are only allowed to consider \(m<p\)
of the predictors. A new sample of \(m\) predictors is taken at each
split and typically \(m\approx \sqrt p\).

\begin{block}{Example}

We decorrelate the trees by using the \emph{randomForest()} function
again, but this time we set \emph{mtry=3}. This means that the algorithm
only considers three of the covariates in each split. We choose \(3\)
because we have \(10\) covariates in total and \(\sqrt{10}\approx 3\).

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{1}\NormalTok{)}

\NormalTok{rf=}\KeywordTok{randomForest}\NormalTok{(clinically.important.brain.injury}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{data=}\NormalTok{headInjury2,}\DataTypeTok{subset=}\NormalTok{train,}\DataTypeTok{mtry=}\DecValTok{3}\NormalTok{,}\DataTypeTok{ntree=}\DecValTok{500}\NormalTok{,}\DataTypeTok{importance=}\OtherTok{TRUE}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

We check the predictive performance as before:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{yhat.rf=}\KeywordTok{predict}\NormalTok{(rf,}\DataTypeTok{newdata=}\NormalTok{headInjury2[test,])}

\NormalTok{misclass.rf=}\KeywordTok{table}\NormalTok{(yhat.rf,headInjury2[test,]}\OperatorTok{$}\NormalTok{clinically.important.brain.injury)}
\KeywordTok{print}\NormalTok{(misclass.rf)}

\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(misclass.rf))}\OperatorTok{/}\NormalTok{(}\KeywordTok{sum}\NormalTok{(misclass.rf))}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
##        
## yhat.rf   0   1
##       0 367  51
##       1  12  41
## [1] 0.133758
\end{verbatim}

The misclassification rate is slightly decreased compared to the
\protect\hyperlink{bagex}{bagged tree} (and to the
\protect\hyperlink{expruning}{pruned tree}).

By using the \emph{varImpPlot()} function we can study the importance of
each covariate.

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{varImpPlot}\NormalTok{(rf)}
\end{Highlighting}
\end{Shaded}

\includegraphics{8Trees_files/figure-beamer/unnamed-chunk-20-1.pdf}

As expected \emph{GCS.15.2hours} is a strong predictor along with
\emph{basal.skull.facture} and \emph{age}. This means that most of the
trees will have these predictors in the top split.

\end{block}

\end{frame}

\begin{frame}[fragile]{Boosting}

\emph{Boosting} is an alternative approach for improving the predictions
resulting from a decision tree. In boosting the trees are grown
sequentially so that each tree is grown using information from the
previous tree. First build a decision tree with \(d\) covariates. Next,
improve the model in areas where the model didn't perform well. This is
done by fitting a decision tree to the residuals of the model. This
procedure is called learning slowly. The first decision tree is then
updated based on the residual tree. The procedure is repeated until some
stopping criterion is reached. Each of the trees can be very small, with
just a few terminal nodes.

Read and be sure you understand \emph{Algorithm 8.2} from the book
before proceeding:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  Set \(\hat{f}(x) = 0\) and \(r_i = y_i\) for all \(i\) in the training
  set.
\item
  For \(b=1,2,...,B\), repeat:

  \begin{enumerate}
  \def\labelenumii{\alph{enumii})}
  \tightlist
  \item
    Fit a tree \(\hat{f}^b\) with \(d\) splits (\(d+1\) terminal nodes)
    to the training data.\\
  \item
    Update \(\hat{f}\) by adding in a shrunken version of the new tree:
    \[\hat{f}(x) \leftarrow \hat{f}(x)+\lambda \hat{f}^b(x).\]\\
  \item
    Update the residuals,
    \[r_i \leftarrow r_i - \lambda \hat{f}^b(x_i).\]\\
  \end{enumerate}
\item
  The boosted model is
  \(\hat{f}(x) = \sum_{b=1}^B \lambda \hat{f}^b(x).\)
\end{enumerate}

Boosting has three tuning parameters which need to be addressed:

\textbf{Tuning parameters}

\begin{itemize}
\tightlist
\item
  The number of trees to be grown, \(B\). The value of \(B\) should be
  chosen using cross-validation. A too small value of \(B\) would imply
  that much information is unused (remember that boosting is a slow
  learner), whereas a too large value of \(B\) may lead to overfitting.
\item
  \(\lambda\): This is a shrinkage parameter and controls the rate at
  which boosting learns. Recall Algorithm 8.2 in the book: the role of
  \(\lambda\) is to scale the new information, when added to the
  existing tree. We add information from the \(b\)-th tree to our
  existing tree \(\hat{f}\), but scaled by the \(\lambda\). Choosing a
  small value for \(\lambda\) ensures that the algorithm learns slowly,
  but will require a larger tree ensemble. Typical values of \(\lambda\)
  is 0.1 or 0.01.\\
\item
  Interaction depth \(d\): The number of splits in each tree. This
  parameter controls the complexity of the boosted tree ensemble. By
  choosing \(d=1\) a tree stup will be fitted at each step and this
  actually gives an additive model.
\end{itemize}

\begin{block}{Example}

We use the function \emph{gbm()} in the \emph{gbm} library to fit a
boosted classification tree. Note that the \emph{gbm()} function does
not allow factors (``yes'' and ``no'') in the response, so we have to
use the dataset with \emph{clinically.important.brain.injury}
\(\in \{0,1\}\).

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(gbm)}
\KeywordTok{set.seed}\NormalTok{(}\DecValTok{1}\NormalTok{)}
\NormalTok{head2=headInjury2}
\CommentTok{#y=factor(headInjury2$clinically.important.brain.injury)}
\CommentTok{#levels(y)=c("0","1")}
\CommentTok{#head2$clinically.important.brain.injury=y}

\NormalTok{boost=}\KeywordTok{gbm}\NormalTok{(clinically.important.brain.injury}\OperatorTok{~}\NormalTok{.,}\DataTypeTok{data=}\NormalTok{head2[train,],}\DataTypeTok{distribution=}\StringTok{"bernoulli"}\NormalTok{,}\DataTypeTok{n.trees=}\DecValTok{5000}\NormalTok{,}\DataTypeTok{interaction.depth=}\DecValTok{4}\NormalTok{,}\DataTypeTok{shrinkage=}\FloatTok{0.001}\NormalTok{)}
\KeywordTok{print}\NormalTok{(boost)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## gbm(formula = clinically.important.brain.injury ~ ., distribution = "bernoulli", 
##     data = head2[train, ], n.trees = 5000, interaction.depth = 4, 
##     shrinkage = 0.001)
## A gradient boosted model with bernoulli loss function.
## 5000 iterations were performed.
## There were 10 predictors of which 0 had non-zero influence.
\end{verbatim}

The variable \emph{distribution} is set to \emph{``bernoulli''} because
we want a classification tree. Alternatively, we could have set this
variable to \emph{``gaussian''} if we wanted a regression tree. We could
also change the \emph{interaction.depth} to change the parameter \(d\)
in \emph{Algorithm 8.2}, or change \emph{shrinkage} if we want to try
another \(\lambda.\)

Next, we predict the response for the test data.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{yhat.boost=}\KeywordTok{predict}\NormalTok{(boost,}\DataTypeTok{newdata=}\NormalTok{head2[test,],}\DataTypeTok{n.trees=}\DecValTok{5000}\NormalTok{,}\DataTypeTok{type=}\StringTok{"response"}\NormalTok{)}
\NormalTok{yhat.boost=}\KeywordTok{ifelse}\NormalTok{(yhat.boost}\OperatorTok{>}\FloatTok{0.5}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{0}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The \emph{predict()} function gives us predictions between 0 and 1, i.e
probabilities, so we transform them to 0 and 1 as we want to do
classification.

As usual we compute the misclassification rate. Recall that
\emph{clinically.important.brain.injury=``yes''} corresponds to
\emph{clinically.important.brain.injury=0} now.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{misclass.boost=}\KeywordTok{table}\NormalTok{(yhat.boost,head2}\OperatorTok{$}\NormalTok{clinically.important.brain.injury[test])}
\KeywordTok{print}\NormalTok{(misclass.boost)}

\DecValTok{1}\OperatorTok{-}\KeywordTok{sum}\NormalTok{(}\KeywordTok{diag}\NormalTok{(misclass.boost))}\OperatorTok{/}\KeywordTok{sum}\NormalTok{(misclass.boost)}
\end{Highlighting}
\end{Shaded}

\begin{verbatim}
## < table of extent 0 x 2 >
## [1] NaN
\end{verbatim}

We see that this approach gives the lowest misclassification rate so
far.

\end{block}

\end{frame}

\begin{frame}{Unresolved}

\begin{itemize}
\item
  Litt keitete kode ettersom man f??r ut sannsynligheter og m??
  transformere til 0 og 1 etter boosting.
\item
  Muligens m?? vi ogs?? skrive litt mer om boosting?
\end{itemize}

\end{frame}

\begin{frame}[fragile]{Recommended exercises}

\begin{block}{1. Theoretical questions:}

\begin{enumerate}
\def\labelenumi{\alph{enumi})}
\item
  Explain why a likelihood function for a classification tree can be
  written as
  \[L(\mathbf{\theta})=\prod_{i=1}^{n} p_{i}^{y_i} (1-p_i)^{1-y_i}\]
  where \(p_i=\hat{y}_i\) is an estimator for \(y_i\) for
  \(\mathbf{x_i} \in R_m.\)
\item
  Show that each bootstrap sample will contain on average approximately
  \(2/3\) of the observations.
\end{enumerate}

\end{block}

\begin{block}{2. Understanding the algorithms:}

\begin{enumerate}
\def\labelenumi{\alph{enumi})}
\tightlist
\item
  Do Exercise 4 in the book (page 332).
\end{enumerate}

Suppose that we want to build a regression tree based on the following
dataset:

\begin{longtable}[]{@{}ccc@{}}
\toprule
\(i\) & \((x_{i1},x_{i2})\) & \(y\)\tabularnewline
\midrule
\endhead
1 & (1,3) & 2\tabularnewline
2 & (2,2) & 5\tabularnewline
3 & (3,2) & 3\tabularnewline
4 & (3,4) & 7\tabularnewline
\bottomrule
\end{longtable}

Answer the following questions without using \(R\):

\begin{enumerate}
\def\labelenumi{\alph{enumi})}
\setcounter{enumi}{1}
\item
  Find the optimal splitting variable and split point for the first
  binary splitting for these data according to the recursive binary
  splitting algorithm. \(Hint\): Draw a figure and look at possible
  divisions.
\item
  Continue the tree construction for the toy data until each terminal
  node in the tree corresponds to one single observation. Let the
  resulting tree be denoted \(T_0\).
\item
  For what values of \(\alpha\) in the cost-complexity criterion
  \(C_{\alpha}(T)\) will the unpruned tree \(T_0\) be the optimal tree?
  \(Hint:\) Prune the tree by cost complexity pruning.
\item
  Suppose that we want to predict the response \(y\) for a new
  observation at \textbf{x}=(2,3). What is the predicted value when
  using the tree \(T_0\) constructed above?
\end{enumerate}

\end{block}

\begin{block}{3. Implementation:}

In this exercise you are going to implement a spam filter for e-mails by
using tree-based methods. Data from 4601 e-mails are collected and can
be uploaded from the kernlab library as follows:

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{library}\NormalTok{(kernlab)}

\KeywordTok{data}\NormalTok{(spam)}
\end{Highlighting}
\end{Shaded}

Each e-mail is classified by \emph{type} (\emph{spam} or
\emph{nonspam}), and this will be the response in our model. In addition
there are 57 covariates in the dataset. The covariates describe the
frequency of different words in the e-mails and orthography
(capitalization, spelling, punctuation and so on).

\begin{enumerate}
\def\labelenumi{\alph{enumi})}
\item
  Study the dataset by writing \emph{?spam} in R.
\item
  Create a training set and a test set for the dataset.
\item
  Fit a tree to the training data with \emph{type} as the response and
  the rest of the variables as predictors. Study the results by using
  the \emph{summary()} function. Also create a plot of the tree. How
  many terminal nodes does it have?
\item
  Predict the response on the test data. What is the misclassification
  rate?
\item
  Use the \emph{cv.tree()} function to find the optimal tree size. Prune
  the tree according to the optimal tree size by using the
  \emph{prune.misclass()} function and plot the result. Predict the
  response on the test data by using the pruned tree. What is the
  misclassification rate in this case?
\item
  Create a decision tree by using the bagging approach. Use the function
  \emph{randomForest()} and consider all of the predictors in each
  split. Predict the response on the test data and report the
  misclassification rate.
\item
  Apply the \emph{randomForest()} function again, but this time consider
  only a subset of the predictors in each split. This corresponds to the
  random forest-algorithm. Study the importance of each variable by
  using the function \emph{importance()}. Are the results as expected
  based on earlier results? Again, predict the response for the test
  data and report the misclassification rate.
\item
  Use \emph{gbm()} to construct a boosted classification tree. Predict
  the response for the test data and report the misclassification rate.
\item
  Compare the misclassification rates in d-h. Which method gives the
  lowest misclassification rate for the test data? Are the results as
  expected?
\end{enumerate}

\end{block}

\end{frame}

\begin{frame}{ Further reading }

\begin{itemize}
\tightlist
\item
  \href{}{Videoes on YouTube by the authors of ISL, Chapter 8}, and
  corresponding \href{}{slides}
\item
  \href{}{Solutions to exercises in the book, chapter 8}
\end{itemize}

See also the references below.

\end{frame}

\begin{frame}{ R packages to install before knitting this R Markdown
file}

\end{frame}

\begin{frame}{References}

\hypertarget{refs}{}
\hypertarget{ref-Bagging}{}
Breiman, Leo. 1996. ``Bagging Predictors.'' \emph{Machine Learning} 24:
123--40.

\hypertarget{ref-RandomForest}{}
---------. 2001. ``Random Forest.'' \emph{Machine Learning} 45: 5--32.

\hypertarget{ref-ESL}{}
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. 2001. \emph{The
Elements of Statistical Learning}. Vol. 1. Springer series in statistics
New York.

\hypertarget{ref-ISL}{}
James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani.
2013. \emph{An Introduction to Statistical Learning}. Vol. 112.
Springer.

\end{frame}

\end{document}
