---
subtitle: "TMA4268 Statistical Learning V2018"
title: "Compulsory exercise 3, version 16.04.2018"
author: "Contact person: Andreas Strand, andreas.strand@ntnu.no"
date: "To be handed in on Blackboard: deadline May 4 at 16.00"
output: #3rd letter intentation hierarchy
   pdf_document:
   # html_document:
   #   toc: true
   #   toc_float: true
# bibliography: ref.bib
nocite: |
  @ESL, @ISL
#editor_options: 
#  chunk_output_type: console
---
  
```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE,results="hold",message = FALSE,warning=FALSE)
```

(12.04: added extra supervision times, 16.04: added random seed in svm-task.)

# Introduction

Maximal score is 10 points. You need a score of 4/10 for the exercise to be approved. Your score will make up 10% points of your final grade.

## Supervision

* Fridays in April 12-14 in Smia, in addition 
* Wednesday April 25, 10-12 in EL1
* Wednesday May 2, 10-12 in 656, 6.etg. sentralbygg 2.
* If needed: Friday May 4 at 10-12 in Andreas' office at Materialteknisk 3-1281.

## Practical issues

* Maximal group size is 3 - join a group (self enroll) before handing in on Blackboard.
* Remember to write your names and group number on top of your submission.
* The exercise should be handed in as one R Markdown file and a pdf-compiled version of the R Markdown file (if you are not able to produce a pdf-file directly please make an html-file, open it in your browser and save as pdf - no, not landscape - but portrait please). We will print the pdf-files (and you get written comments) and use the Rmd file in case we need to check details in your submission.
* In the R-chunks please use both `echo=TRUE` and `eval=TRUE` to make it simpler for us to read and grade.
* Please do not include all the text from this file (that you are reading now) - we want your R code, plots and written solutions - see the template below.
* Please not more than 10 pages in your pdf-file! (This is a request, not a requirement.)
* Please save us time and NOT submit word or zip - or only Rmd - that only results in extra work for us!

Template file for submission of Compulsory exercise 3 is here: <https://www.math.ntnu.no/emner/TMA4268/2018v/CompEx3mal.Rmd>

You need to install the following packages in R:

```{r,eval=FALSE,echo=TRUE}
install.packages("caret")
install.packages("tree")
install.packages("pROC")
install.packages("RandomForest")
install.packages("corrplot")
install.packages("knitr")
install.packages("e1071")
install.packages("keras") 
```

The `keras` package will call Python, so Python must be installed on your machine. After installing the `keras` package, the installation of keras and dependencies should be done only once:

```{r,eval=FALSE,echo=TRUE}
library(keras)            # Load R package Keras
install_keras()           # Install Keras and dependencies
```

# Problem 1 - Classification with trees [4 points]

We will use the _German credit data set_ from the [UC Irvine machine learning repository](https://archive.ics.uci.edu/ml/index.php). Our aim is to classify a customer as _good_ or _bad_ with respect to credit risk. A set of 20 covariates (attributes) are available (both numerical and categorical) for 300 customers with bad credit risk and 700 customers with good credit risk.

More information on the 20 covariates are found that the UCI archive [data set description](https://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29)


```{r,echo=TRUE,eval=TRUE}
library(caret) 
#read data, divide into train and test
germancredit = read.table("http://archive.ics.uci.edu/ml/machine-learning-databases/statlog/german/german.data")
colnames(germancredit) = c("checkaccount", "duration", "credithistory", "purpose", "amount", "saving", "presentjob", "installmentrate", "sexstatus", "otherdebtor", "resident", "property", "age", "otherinstall", "housing", "ncredits", "job", "npeople", "telephone", "foreign", "response")
germancredit$response = as.factor(germancredit$response) #2=bad
table(germancredit$response)
str(germancredit) # to see factors and integers, numerics

set.seed(4268) #keep this -easier to grade work
in.train <- createDataPartition(germancredit$response, p=0.75, list=FALSE)
# 75% for training, one split
germancredit.train <- germancredit[in.train,]; dim(germancredit.train)
germancredit.test <- germancredit[-in.train,];dim(germancredit.test)
```

We will now look at classification trees, bagging, and random forests.

Remark: in description of the data set it is hinted that we may use unequal cost of misclassification for the two classes, but we have not covered unequal misclassification costs in this course, and will therefore not address that in this problem set.

## a) Full classification tree [1 point]

```{r,echo=TRUE,eval=FALSE}
# construct full tree
library(tree)
library(pROC)
fulltree=tree(response~.,germancredit.train,split="deviance")
summary(fulltree)
plot(fulltree)
text(fulltree)
print(fulltree)
fullpred=predict(fulltree,germancredit.test,type="class")
testres=confusionMatrix(data=fullpred,reference=germancredit.test$response)
print(testres)
1-sum(diag(testres$table))/(sum(testres$table))
predfulltree = predict(fulltree,germancredit.test, type = "vector")
testfullroc=roc(germancredit.test$response == "2", predfulltree[,2])
auc(testfullroc)
plot(testfullroc)
```

Run the code and study the output.

* Q1. Explain briefly how `fulltree` is constructed. The explanation should include the words: greedy, binary, deviance, root, leaves.

## b) Pruned classification tree [1 point]

```{r, echo=TRUE, eval=FALSE}
# prune the full tree
set.seed(4268)
fullcv=cv.tree(fulltree,FUN=prune.misclass,K=5)
plot(fullcv$size,fullcv$dev,type="b", xlab="Terminal nodes",ylab="misclassifications")
print(fullcv)
prunesize=fullcv$size[which.min(fullcv$dev)]
prunetree=prune.misclass(fulltree,best=prunesize) 
plot(prunetree)
text(prunetree,pretty=1)
predprunetree = predict(prunetree,germancredit.test, type = "class")
prunetest=confusionMatrix(data=predprunetree,reference=germancredit.test$response)
print(prunetest)
1-sum(diag(prunetest$table))/(sum(prunetest$table))
predprunetree = predict(prunetree,germancredit.test, type = "vector")
testpruneroc=roc(germancredit.test$response == "2", predprunetree[,2])
auc(testpruneroc)
plot(testpruneroc)
```

Run the code and study the output.

* Q2. Why do we want to prune the full tree? 
* Q3. How is amount of pruning decided in the code? 
* Q4. Compare the the full and pruned tree classification method with focus on interpretability and the ROC curves (AUC).

## c) Bagged trees [1 point]

```{r,echo=TRUE,eval=FALSE}
library(randomForest)
set.seed(4268)
bag=randomForest(response~., data=germancredit,subset=in.train,
                 mtry=20,ntree=500,importance=TRUE)
bag$confusion
1-sum(diag(bag$confusion))/sum(bag$confusion[1:2,1:2])
yhat.bag=predict(bag,newdata=germancredit.test)
misclass.bag=confusionMatrix(yhat.bag,germancredit.test$response)
print(misclass.bag)
1-sum(diag(misclass.bag$table))/(sum(misclass.bag$table))
predbag = predict(bag,germancredit.test, type = "prob")
testbagroc=roc(germancredit.test$response == "2", predbag[,2])
auc(testbagroc)
plot(testbagroc)
varImpPlot(bag,pch=20)
```

Run the code and study the output.

* Q5. What is the main motivation behind bagging?
* Q6. Explain what the importance plots show, and give your interpretation for the data set.
* Q7. Compare the performance of bagging with the best of the full and pruned tree model above with focus on interpretability and the ROC curves (AUC).

## d) Random forest [1 point]

```{r,echo=TRUE,eval=FALSE}
set.seed(4268)
rf=randomForest(response~.,
                 data=germancredit,subset=in.train,
                 mtry=4,ntree=500,importance=TRUE)
rf$confusion
1-sum(diag(rf$confusion))/sum(rf$confusion[1:2,1:2])
yhat.rf=predict(rf,newdata=germancredit.test)
misclass.rf=confusionMatrix(yhat.rf,germancredit.test$response)
print(misclass.rf)
1-sum(diag(misclass.rf$table))/(sum(misclass.rf$table))
predrf = predict(rf,germancredit.test, type = "prob")
testrfroc=roc(germancredit.test$response == "2", predrf[,2])
auc(testrfroc)
plot(testrfroc)
varImpPlot(rf,pch=20)
```

Run the code and study the output.

* Q8. The parameter `mtry=4` is used. What does this parameter mean, and what is the motivation behind choosing exactly this value?
* Q9. The value of the parameter `mtry` is the only difference between bagging and random forest. What is the effect of choosing `mtry` to be a value less than the number of covariates?
* Q10. Would you prefer to use bagging or random forest to classify the credit risk data?

# Problem 2 - Nonlinear class boundaries and support vector machine [2 points]

## a) Bayes decision boundary [1 point]

We will study classification applied to a simulated data set with two classes from @ESL, where the data set is supplied together with the Bayes decision boundary. The boundary is plotted below, together with a training set.

```{r,echo=TRUE, eval=TRUE}
load(url("https://web.stanford.edu/~hastie/ElemStatLearn/datasets/ESL.mixture.rda"))
#names(ESL.mixture) 
#prob gives probabilites for each class when the true density functions are known
#px1 and px2 are coordinates in x1 (length 69) and x2 (length 99) where class probabilites are calculated
rm(x,y)
attach(ESL.mixture)
dat=data.frame(y=factor(y),x)
xgrid=expand.grid(X1=px1,X2=px2)
par(pty="s")
plot(xgrid, pch=20,cex=.2)
points(x,col=y+1,pch=20)
contour(px1,px2,matrix(prob,69,99),level=0.5,add=TRUE,col="blue",lwd=2) #optimal boundary
```

* Q11. What is a Bayes classifier, Bayes decision boundary and Bayes error rate? Hint: pages 37-39 in @ISL.
* Q12. When the Bayes decision boundary is known, do we then need a test set?

## b) Support vector machine [1 point]

```{r,echo=TRUE,eval=TRUE}
library(e1071)
# support vector classifier
svcfits=tune(svm,factor(y)~.,data=dat,scale=FALSE,kernel="linear",ranges=list(cost=c(1e-2,1e-1,1,5,10)))
summary(svcfits)
svcfit=svm(factor(y)~.,data=dat,scale=FALSE,kernel="linear",cost=0.01)
# support vector machine with radial kernel
set.seed(4268)
svmfits=tune(svm,factor(y)~.,data=dat,scale=FALSE,kernel="radial",ranges=list(cost=c(1e-2,1e-1,1,5,10),gamma=c(0.01,1,5,10)))
summary(svmfits)
svmfit=svm(factor(y)~.,data=dat,scale=FALSE,kernel="radial",cost=1,gamma=5)

# the same as in a - the Bayes boundary
par(pty="s")
plot(xgrid, pch=20,cex=.2)
points(x,col=y+1,pch=20)
contour(px1,px2,matrix(prob,69,99),level=0.5,add=TRUE,col="blue",lwd=2) #optimal boundary

# decision boundaries from svc and svm added
svcfunc=predict(svcfit,xgrid,decision.values=TRUE)
svcfunc=attributes(svcfunc)$decision
contour(px1,px2,matrix(svcfunc,69,99),level=0,add=TRUE,col="red") #svc boundary
svmfunc=predict(svmfit,xgrid,decision.values=TRUE)
svmfunc=attributes(svmfunc)$decision
contour(px1,px2,matrix(svmfunc,69,99),level=0,add=TRUE,col="orange") #svm boundary
```

* Q13. What is the difference between a support vector classifier and a support vector machine?
* Q14. What are parameters for the support vector classifier and the support vector machine? How are these chosen above?
* Q15. How would you evaluate the support vector machine decision boundary compared to the Bayes decision boundary?

# Problem 3 - Unsupervised methods [2 points]

## a) Principal component analysis [1 point]

We will study data on consumption of different beverages for a selection of countries, and perform principal component analysis.

```{r,echo=TRUE,eval=TRUE}
# reading data on consumption of different beverages for countries
drink <- read.csv("https://www.math.ntnu.no/emner/TMA4267/2017v/drikke.TXT",sep=",",header=TRUE)
drink <- na.omit(drink)
# looking at correlation between consumptions
drinkcorr=cor(drink)
library(corrplot)
corrplot(drinkcorr,method="circle")
# now for PCA
pcaS <- prcomp(drink,scale=TRUE) # scale: variables are scaled 
pcaS$rotation
summary(pcaS)
biplot(pcaS,scale=0,cex=0.6) # scale=0: arrows scaled to represent the loadings
```

* Q16. Explain what you see in the `biplot` in relation to the loadings for the first two principal components. 
* Q17. Does this analysis give you any insight into the consumption of beverages and similarities between countries? 

## b) Hierarchical clustering [1 point]

Within the research area of phylogeny similarities between species are studied, and below you find a distance matrix for five species. The distances are calculated from mitochondrial DNA sequences from the species.

```{r,echo=TRUE, eval=TRUE}
library(knitr)
species=c("Human","Chimpanzee","Gorilla","Orangutan","Gibbon")
distJC <- matrix(c(0,1,3,9,12,
                   1,0,2,8,11,
                   3,2,0,6,11,
                   9,8,6,0,11,
                   12,11,11,11,0),5,5)
dimnames(distJC) <- list(species,species)
kable(distJC)
```

![](speciesclust.png)

Above you see three dendrogrammes labelled A, B and C, constructed from the distance matrix above. The dendrograms show agreement on how to cluster the species, but differ in branch lenghts when species are fused together in clusters. 

* Q18. Describe how the distance between _clusters_ are defined for single, complete and average linkage. 
* Q19. Identify which of the three dendrograms (A, B, C) correspond to the three methods single, complete and average linkage. Justify your solution.

# Problem 4 - Neural networks [2 points]

During our lectures, we have used a densely connected neural network to classify a movie review as either positive or negative using the IMDB data set. We will use the same data here, refer to the lecture slides for reading the data set and setting up the network.

More specifically, we have defined a linear stack of dense layers, containing two intermediate layers containing 16 hidden units each with reLu activation functions. 

```
model <- keras_model_sequential() %>%
  layer_dense(units = 16, activation = "relu", input_shape = c(10000)) %>%
  layer_dense(units = 16, activation = "relu") %>%
  layer_dense(units = 1, activation = "sigmoid")
```

* Q20. What is the advantage of using a non-linear activation function such as `relu`?
* Q21. Why do we need to use a different activation function (`sigmoid`) in the output layer instead of using `relu` again? 

In one of our lectures, we have fitted the model above and plotted training and validation loss as well as accuracy, as illustrated in the figure below.

![](imdb_validation.png)

Keep two intermediate layers in the network. Try creating a simpler model with 4 hidden units instead of 16 and a more complex model with 32 hidden units instead of 16.

* Q22. Plot the training and validation loss and accuracy for the simpler and more complex model mentioned above. How do they compare with the model with 16 hidden units?
* Q23. Besides reducing the network's size, what other methods can be used to avoid overfitting with neural network models? Briefly describe the intuition behind each one.

# References