Decision Trees

#install.packages("tree")
require(ISLR)
Loading required package: ISLR

Carseats data is being used, using “tree” package

dim(Carseats)
[1] 400  11

Sales is a quantitative variable. We turn this into a binary variable so that we can make it a classification problem. Cutoff is 8 sales for high and low.

Carseats$High <- as.factor(ifelse(Carseats$Sales <= 8, "No", "Yes"))

Fitting a tree based models, (removing sales from the equation because the binary response was created from it)

tree_carseats <- tree(High~.-Sales, data = Carseats)
summary(tree_carseats)

Classification tree:
tree(formula = High ~ . - Sales, data = Carseats)
Variables actually used in tree construction:
[1] "ShelveLoc"   "Price"       "Income"      "CompPrice"   "Population"  "Advertising" "Age"         "US"         
Number of terminal nodes:  27 
Residual mean deviance:  0.4575 = 170.7 / 373 
Misclassification error rate: 0.09 = 36 / 400 

The summary shows the variables used in the split (not ordered), the number of terminal nodes, deviance and misclassification error rate

Plotting the tree (we need to annotate the tree with the text, else it is just going to show the tree structure with no other information)

plot(tree_carseats)
text(tree_carseats,pretty=0)

There are so many splits in this tree, quite complex to look at! Since this is a classification problem, the terminal contains either a Yes or a No, which is the majority in that that region

The detailed summary of the tree contains details of the terminal nodes, proportion at splits, and other details at every node in the tree. Quite tough to look at really.

tree_carseats
node), split, n, deviance, yval, (yprob)
      * denotes terminal node

  1) root 400 541.500 No ( 0.59000 0.41000 )  
    2) ShelveLoc: Bad,Medium 315 390.600 No ( 0.68889 0.31111 )  
      4) Price < 92.5 46  56.530 Yes ( 0.30435 0.69565 )  
        8) Income < 57 10  12.220 No ( 0.70000 0.30000 )  
         16) CompPrice < 110.5 5   0.000 No ( 1.00000 0.00000 ) *
         17) CompPrice > 110.5 5   6.730 Yes ( 0.40000 0.60000 ) *
        9) Income > 57 36  35.470 Yes ( 0.19444 0.80556 )  
         18) Population < 207.5 16  21.170 Yes ( 0.37500 0.62500 ) *
         19) Population > 207.5 20   7.941 Yes ( 0.05000 0.95000 ) *
      5) Price > 92.5 269 299.800 No ( 0.75465 0.24535 )  
       10) Advertising < 13.5 224 213.200 No ( 0.81696 0.18304 )  
         20) CompPrice < 124.5 96  44.890 No ( 0.93750 0.06250 )  
           40) Price < 106.5 38  33.150 No ( 0.84211 0.15789 )  
             80) Population < 177 12  16.300 No ( 0.58333 0.41667 )  
              160) Income < 60.5 6   0.000 No ( 1.00000 0.00000 ) *
              161) Income > 60.5 6   5.407 Yes ( 0.16667 0.83333 ) *
             81) Population > 177 26   8.477 No ( 0.96154 0.03846 ) *
           41) Price > 106.5 58   0.000 No ( 1.00000 0.00000 ) *
         21) CompPrice > 124.5 128 150.200 No ( 0.72656 0.27344 )  
           42) Price < 122.5 51  70.680 Yes ( 0.49020 0.50980 )  
             84) ShelveLoc: Bad 11   6.702 No ( 0.90909 0.09091 ) *
             85) ShelveLoc: Medium 40  52.930 Yes ( 0.37500 0.62500 )  
              170) Price < 109.5 16   7.481 Yes ( 0.06250 0.93750 ) *
              171) Price > 109.5 24  32.600 No ( 0.58333 0.41667 )  
                342) Age < 49.5 13  16.050 Yes ( 0.30769 0.69231 ) *
                343) Age > 49.5 11   6.702 No ( 0.90909 0.09091 ) *
           43) Price > 122.5 77  55.540 No ( 0.88312 0.11688 )  
             86) CompPrice < 147.5 58  17.400 No ( 0.96552 0.03448 ) *
             87) CompPrice > 147.5 19  25.010 No ( 0.63158 0.36842 )  
              174) Price < 147 12  16.300 Yes ( 0.41667 0.58333 )  
                348) CompPrice < 152.5 7   5.742 Yes ( 0.14286 0.85714 ) *
                349) CompPrice > 152.5 5   5.004 No ( 0.80000 0.20000 ) *
              175) Price > 147 7   0.000 No ( 1.00000 0.00000 ) *
       11) Advertising > 13.5 45  61.830 Yes ( 0.44444 0.55556 )  
         22) Age < 54.5 25  25.020 Yes ( 0.20000 0.80000 )  
           44) CompPrice < 130.5 14  18.250 Yes ( 0.35714 0.64286 )  
             88) Income < 100 9  12.370 No ( 0.55556 0.44444 ) *
             89) Income > 100 5   0.000 Yes ( 0.00000 1.00000 ) *
           45) CompPrice > 130.5 11   0.000 Yes ( 0.00000 1.00000 ) *
         23) Age > 54.5 20  22.490 No ( 0.75000 0.25000 )  
           46) CompPrice < 122.5 10   0.000 No ( 1.00000 0.00000 ) *
           47) CompPrice > 122.5 10  13.860 No ( 0.50000 0.50000 )  
             94) Price < 125 5   0.000 Yes ( 0.00000 1.00000 ) *
             95) Price > 125 5   0.000 No ( 1.00000 0.00000 ) *
    3) ShelveLoc: Good 85  90.330 Yes ( 0.22353 0.77647 )  
      6) Price < 135 68  49.260 Yes ( 0.11765 0.88235 )  
       12) US: No 17  22.070 Yes ( 0.35294 0.64706 )  
         24) Price < 109 8   0.000 Yes ( 0.00000 1.00000 ) *
         25) Price > 109 9  11.460 No ( 0.66667 0.33333 ) *
       13) US: Yes 51  16.880 Yes ( 0.03922 0.96078 ) *
      7) Price > 135 17  22.070 No ( 0.64706 0.35294 )  
       14) Income < 46 6   0.000 No ( 1.00000 0.00000 ) *
       15) Income > 46 11  15.160 Yes ( 0.45455 0.54545 ) *

Creating a train-test split, building the tree on the training data and evaluating on the testing data

Total records = 400; Training dataset = 250, testing dataset = 150 observations

set.seed(1011)
index <- sample(1:nrow(Carseats), 250)
train_tree_carseats <- tree(High~.-Sales, data = Carseats, subset = index)
summary(train_tree_carseats)

Classification tree:
tree(formula = High ~ . - Sales, data = Carseats, subset = index)
Variables actually used in tree construction:
[1] "ShelveLoc"   "Price"       "Age"         "CompPrice"   "Advertising" "Education"   "Income"      "US"         
Number of terminal nodes:  23 
Residual mean deviance:  0.3498 = 79.4 / 227 
Misclassification error rate: 0.088 = 22 / 250 

Plotting the above tree

plot(train_tree_carseats)
text(train_tree_carseats, pretty = 0)

The tree is similarly complex as the one with full data.

Predicting the results on the test dataset

table(test_tree_carseats_pred)
test_tree_carseats_pred
 No Yes 
 78  72 

Confusion matrix for test dataset

with(Carseats[-index,],table(test_tree_carseats_pred,High))
                       High
test_tree_carseats_pred No Yes
                    No  58  20
                    Yes 27  45

Misclassification rate from the above table

cat("Error Rate",(58+45)/150)
Error Rate 0.6866667

Using CV to control the depth. We use misclassification error as the pruning criteria

cv_train_tree_carseats
$size
 [1] 23 17 16 14 10  8  6  5  4  2  1

$dev
 [1] 67 68 76 77 80 81 81 86 83 82 99

$k
 [1] -Inf  0.0  1.0  1.5  2.0  3.0  3.5  5.0  6.0  7.0 27.0

$method
[1] "misclass"

attr(,"class")
[1] "prune"         "tree.sequence"

The object contains the size of the tree as pruning proceeds, the deviance, k = cost complexity parameter

This plots the misclassification rate, across different sizes. The minimum seems to occur somewhere around 17-18, and we can prune the tree at that depth

prune_carseats <- prune.misclass(train_tree_carseats, best = 13)
plot(prune_carseats)
text(prune_carseats, pretty = 0)

This is a little shallower than the previous trees. This is the result of the cross-validation.

Evaluating this on the testing dataset

cv_test_tree_carseats_pred <- predict(prune_carseats, Carseats[-index,], type = "class")
table(cv_test_tree_carseats_pred)
cv_test_tree_carseats_pred
 No Yes 
 78  72 

Calculating the misclassification rate again

table(cv_test_tree_carseats_pred, Carseats$High[-index])
                          
cv_test_tree_carseats_pred No Yes
                       No  59  19
                       Yes 26  46
cat("Error Rate", (59+46)/150)
Error Rate 0.7

We get a similar performance with respect to misclassification rate, but the tree is shallower.


More complicated tree-based models using Boston Housing Data (housing values, statistics in 506 suburbs of Boston based on 1970 census)

Random Forests

require(randomForest)
Loading required package: randomForest
randomForest 4.6-14
Type rfNews() to see new features/changes/bug fixes.

This builds a lot of trees, selecting a split parameter from a subset of parameters, and averages out to reduce the variance.

Creating a train-test split with 300-206 data observations each

set.seed(101)
data(Boston)
index <- sample(1:nrow(Boston), 300)

We use random forest for regression, with ‘medv’ as the response variable and every other variable as the predictor.

rf_boston <- randomForest(medv~., data = Boston, subset = index)
rf_boston

Call:
 randomForest(formula = medv ~ ., data = Boston, subset = index) 
               Type of random forest: regression
                     Number of trees: 500
No. of variables tried at each split: 4

          Mean of squared residuals: 12.68651
                    % Var explained: 83.45

500 trees were grown. The number of variables at each split is 4, which is approximately sqrt(13), the number of parameters. The MSR is Out of Bag mean squared residuals.

m is the number of variables that is selected at each split in random. This is given by the mtry parameter in randomForest(). And this is one of the parameters that we can tune.

Building random forest decision trees with m ranging from 1 to 13 (p parameters), and recording the OOB and test errors

oob_rf_error
 [1] 22.72616 14.62290 13.73073 12.79109 12.38863 12.69210 12.41103 12.44833 12.71799 13.08525 12.91090 12.60250 12.83121

Plotting the oob and test errors across m

matplot(1:m, cbind(test_rf_error, oob_rf_error), pch = 19, col = c("red", "blue"), type = "b", ylab = "Mean Squared Error")
legend("topright", legend = c("OOB", "Test"), pch = 19, col = c("red", "blue"))

If we want to do Bagging, we can use mtry = number of parameters. The left most is value is the MSE of a single tree


Boosting

We run a simple boositng logic on the same Boston data. We use the package “gbm” (Gradient Boosted Machines)

require(gbm)
Loading required package: gbm
Loaded gbm 2.1.5

We ask for 10000 because there are a lot of shallow trees, with 4 depths. So, 4 splits choosing 4 variables.

Summary gives the variable importance plot! The two variables that seem to be important are lstat and rm

Checking out the two variables, partial dependence plots

par(mfrow = c(1,2))
plot(boost_boston, i = "lstat")

plot(boost_boston, i = "rm")

Higher the proportion of lower status people in the suburb, lower the value of the house Higher the number of rooms in the house, higher the value of the house


Looking at the test performance as a function of the number of trees

no_trees <- seq(from = 100, to = 10000, by = 100)
pred_matrix <- predict(boost_boston, newdata = Boston[-index,], n.trees = no_trees)

pred_matrix consists of a matrix of predictions of the test data. So, there are 206 observations of the test data, and 100 different tree predictions

Computing the test error

We have calculated the squared differences for each of the columns, and then we take the mean of each column. This computes the column-wise mean squared error

boost_test_error <- with(Boston[-train,], apply((pred_matrix - medv)^2, 2, mean))
Error in `[.data.frame`(Boston, -train, ) : object 'train' not found

Ploting the boosting test error and comparing it with the random forest error

plot(no_trees, boost_test_error, pch = 19, ylab = "Mean Squared Error", xlab = "# of Trees", main = "Boosting Test Error")
abline(h = min(test_rf_error), col = "red")

The test error drops down, but levels off. There is no real increase of decrease.


LS0tDQp0aXRsZTogIlIgTm90ZWJvb2siDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIyNEZWNpc2lvbiBUcmVlcw0KDQpgYGB7cn0NCiNpbnN0YWxsLnBhY2thZ2VzKCJ0cmVlIikNCnJlcXVpcmUoSVNMUikNCnJlcXVpcmUodHJlZSkNCmBgYA0KDQpDYXJzZWF0cyBkYXRhIGlzIGJlaW5nIHVzZWQsIHVzaW5nICJ0cmVlIiBwYWNrYWdlDQoNCmBgYHtyfQ0KZGF0YShDYXJzZWF0cykNCmRpbShDYXJzZWF0cykNCmhpc3QoQ2Fyc2VhdHMkU2FsZXMpDQpgYGANCg0KU2FsZXMgaXMgYSBxdWFudGl0YXRpdmUgdmFyaWFibGUuIFdlIHR1cm4gdGhpcyBpbnRvIGEgYmluYXJ5IHZhcmlhYmxlIHNvIHRoYXQgd2UgY2FuIG1ha2UgaXQgYSBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLiBDdXRvZmYgaXMgOCBzYWxlcyBmb3IgaGlnaCBhbmQgbG93Lg0KDQpgYGB7cn0NCkNhcnNlYXRzJEhpZ2ggPC0gYXMuZmFjdG9yKGlmZWxzZShDYXJzZWF0cyRTYWxlcyA8PSA4LCAiTm8iLCAiWWVzIikpDQpgYGANCg0KRml0dGluZyBhIHRyZWUgYmFzZWQgbW9kZWxzLCAocmVtb3Zpbmcgc2FsZXMgZnJvbSB0aGUgZXF1YXRpb24gYmVjYXVzZSB0aGUgYmluYXJ5IHJlc3BvbnNlIHdhcyBjcmVhdGVkIGZyb20gaXQpDQoNCmBgYHtyfQ0KdHJlZV9jYXJzZWF0cyA8LSB0cmVlKEhpZ2h+Li1TYWxlcywgZGF0YSA9IENhcnNlYXRzKQ0Kc3VtbWFyeSh0cmVlX2NhcnNlYXRzKQ0KDQpgYGANCg0KVGhlIHN1bW1hcnkgc2hvd3MgdGhlIHZhcmlhYmxlcyB1c2VkIGluIHRoZSBzcGxpdCAobm90IG9yZGVyZWQpLCB0aGUgbnVtYmVyIG9mIHRlcm1pbmFsIG5vZGVzLCBkZXZpYW5jZSBhbmQgbWlzY2xhc3NpZmljYXRpb24gZXJyb3IgcmF0ZQ0KDQpQbG90dGluZyB0aGUgdHJlZSAod2UgbmVlZCB0byBhbm5vdGF0ZSB0aGUgdHJlZSB3aXRoIHRoZSB0ZXh0LCBlbHNlIGl0IGlzIGp1c3QgZ29pbmcgdG8gc2hvdyB0aGUgdHJlZSBzdHJ1Y3R1cmUgd2l0aCBubyBvdGhlciBpbmZvcm1hdGlvbikNCmBgYHtyfQ0KcGxvdCh0cmVlX2NhcnNlYXRzKQ0KdGV4dCh0cmVlX2NhcnNlYXRzLHByZXR0eT0wKQ0KYGBgDQoNClRoZXJlIGFyZSBzbyBtYW55IHNwbGl0cyBpbiB0aGlzIHRyZWUsIHF1aXRlIGNvbXBsZXggdG8gbG9vayBhdCEgU2luY2UgdGhpcyBpcyBhIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0sIHRoZSB0ZXJtaW5hbCBjb250YWlucyBlaXRoZXIgYSBZZXMgb3IgYSBObywgd2hpY2ggaXMgdGhlIG1ham9yaXR5IGluIHRoYXQgdGhhdCByZWdpb24NCg0KVGhlIGRldGFpbGVkIHN1bW1hcnkgb2YgdGhlIHRyZWUgY29udGFpbnMgZGV0YWlscyBvZiB0aGUgdGVybWluYWwgbm9kZXMsIHByb3BvcnRpb24gYXQgc3BsaXRzLCBhbmQgb3RoZXIgZGV0YWlscyBhdCBldmVyeSBub2RlIGluIHRoZSB0cmVlLiBRdWl0ZSB0b3VnaCB0byBsb29rIGF0IHJlYWxseS4NCmBgYHtyfQ0KdHJlZV9jYXJzZWF0cw0KYGBgDQoNCi0tLQ0KDQpDcmVhdGluZyBhIHRyYWluLXRlc3Qgc3BsaXQsIGJ1aWxkaW5nIHRoZSB0cmVlIG9uIHRoZSB0cmFpbmluZyBkYXRhIGFuZCBldmFsdWF0aW5nIG9uIHRoZSB0ZXN0aW5nIGRhdGENCg0KVG90YWwgcmVjb3JkcyA9IDQwMDsgVHJhaW5pbmcgZGF0YXNldCA9IDI1MCwgdGVzdGluZyBkYXRhc2V0ID0gMTUwIG9ic2VydmF0aW9ucw0KYGBge3J9DQpzZXQuc2VlZCgxMDExKQ0KaW5kZXggPC0gc2FtcGxlKDE6bnJvdyhDYXJzZWF0cyksIDI1MCkNCg0KdHJhaW5fdHJlZV9jYXJzZWF0cyA8LSB0cmVlKEhpZ2h+Li1TYWxlcywgZGF0YSA9IENhcnNlYXRzLCBzdWJzZXQgPSBpbmRleCkNCnN1bW1hcnkodHJhaW5fdHJlZV9jYXJzZWF0cykNCmBgYA0KDQpQbG90dGluZyB0aGUgYWJvdmUgdHJlZQ0KYGBge3J9DQpwbG90KHRyYWluX3RyZWVfY2Fyc2VhdHMpDQp0ZXh0KHRyYWluX3RyZWVfY2Fyc2VhdHMsIHByZXR0eSA9IDApDQpgYGANCg0KVGhlIHRyZWUgaXMgc2ltaWxhcmx5IGNvbXBsZXggYXMgdGhlIG9uZSB3aXRoIGZ1bGwgZGF0YS4NCg0KUHJlZGljdGluZyB0aGUgcmVzdWx0cyBvbiB0aGUgdGVzdCBkYXRhc2V0DQpgYGB7cn0NCnRlc3RfdHJlZV9jYXJzZWF0c19wcmVkIDwtIHByZWRpY3QodHJhaW5fdHJlZV9jYXJzZWF0cywgbmV3ZGF0YSA9IENhcnNlYXRzWy1pbmRleCxdLCB0eXBlID0gImNsYXNzIikNCnRhYmxlKHRlc3RfdHJlZV9jYXJzZWF0c19wcmVkKQ0KYGBgDQoNCkNvbmZ1c2lvbiBtYXRyaXggZm9yIHRlc3QgZGF0YXNldA0KYGBge3J9DQp0YWJsZSh0ZXN0X3RyZWVfY2Fyc2VhdHNfcHJlZCwgQ2Fyc2VhdHMkSGlnaFstaW5kZXhdKQ0KDQp3aXRoKENhcnNlYXRzWy1pbmRleCxdLHRhYmxlKHRlc3RfdHJlZV9jYXJzZWF0c19wcmVkLEhpZ2gpKQ0KYGBgDQoNCk1pc2NsYXNzaWZpY2F0aW9uIHJhdGUgZnJvbSB0aGUgYWJvdmUgdGFibGUNCmBgYHtyfQ0KY2F0KCJFcnJvciBSYXRlIiwoNTgrNDUpLzE1MCkNCmBgYA0KDQpVc2luZyBDViB0byBjb250cm9sIHRoZSBkZXB0aC4gV2UgdXNlIG1pc2NsYXNzaWZpY2F0aW9uIGVycm9yIGFzIHRoZSBwcnVuaW5nIGNyaXRlcmlhDQoNCmBgYHtyfQ0KY3ZfdHJhaW5fdHJlZV9jYXJzZWF0cyA8LSBjdi50cmVlKHRyYWluX3RyZWVfY2Fyc2VhdHMsIEZVTiA9IHBydW5lLm1pc2NsYXNzKQ0KY3ZfdHJhaW5fdHJlZV9jYXJzZWF0cw0KYGBgDQoNClRoZSBvYmplY3QgY29udGFpbnMgdGhlIHNpemUgb2YgdGhlIHRyZWUgYXMgcHJ1bmluZyBwcm9jZWVkcywgdGhlIGRldmlhbmNlLCBrID0gY29zdCBjb21wbGV4aXR5IHBhcmFtZXRlcg0KDQpgYGB7cn0NCnBsb3QoY3ZfdHJhaW5fdHJlZV9jYXJzZWF0cykNCmBgYA0KDQpUaGlzIHBsb3RzIHRoZSBtaXNjbGFzc2lmaWNhdGlvbiByYXRlLCBhY3Jvc3MgZGlmZmVyZW50IHNpemVzLiBUaGUgbWluaW11bSBzZWVtcyB0byBvY2N1ciBzb21ld2hlcmUgYXJvdW5kIDE3LTE4LCBhbmQgd2UgY2FuIHBydW5lIHRoZSB0cmVlIGF0IHRoYXQgZGVwdGgNCg0KYGBge3J9DQpwcnVuZV9jYXJzZWF0cyA8LSBwcnVuZS5taXNjbGFzcyh0cmFpbl90cmVlX2NhcnNlYXRzLCBiZXN0ID0gMTMpDQpwbG90KHBydW5lX2NhcnNlYXRzKQ0KdGV4dChwcnVuZV9jYXJzZWF0cywgcHJldHR5ID0gMCkNCmBgYA0KDQpUaGlzIGlzIGEgbGl0dGxlIHNoYWxsb3dlciB0aGFuIHRoZSBwcmV2aW91cyB0cmVlcy4gVGhpcyBpcyB0aGUgcmVzdWx0IG9mIHRoZSBjcm9zcy12YWxpZGF0aW9uLg0KDQpFdmFsdWF0aW5nIHRoaXMgb24gdGhlIHRlc3RpbmcgZGF0YXNldA0KYGBge3J9DQpjdl90ZXN0X3RyZWVfY2Fyc2VhdHNfcHJlZCA8LSBwcmVkaWN0KHBydW5lX2NhcnNlYXRzLCBDYXJzZWF0c1staW5kZXgsXSwgdHlwZSA9ICJjbGFzcyIpDQp0YWJsZShjdl90ZXN0X3RyZWVfY2Fyc2VhdHNfcHJlZCkNCmBgYA0KDQpDYWxjdWxhdGluZyB0aGUgbWlzY2xhc3NpZmljYXRpb24gcmF0ZSBhZ2Fpbg0KYGBge3J9DQp0YWJsZShjdl90ZXN0X3RyZWVfY2Fyc2VhdHNfcHJlZCwgQ2Fyc2VhdHMkSGlnaFstaW5kZXhdKQ0KY2F0KCJFcnJvciBSYXRlIiwgKDU5KzQ2KS8xNTApDQpgYGANCg0KV2UgZ2V0IGEgc2ltaWxhciBwZXJmb3JtYW5jZSB3aXRoIHJlc3BlY3QgdG8gbWlzY2xhc3NpZmljYXRpb24gcmF0ZSwgYnV0IHRoZSB0cmVlIGlzIHNoYWxsb3dlci4NCg0KLS0tDQoNCk1vcmUgY29tcGxpY2F0ZWQgdHJlZS1iYXNlZCBtb2RlbHMgdXNpbmcgQm9zdG9uIEhvdXNpbmcgRGF0YSAoaG91c2luZyB2YWx1ZXMsIHN0YXRpc3RpY3MgaW4gNTA2IHN1YnVyYnMgb2YgQm9zdG9uIGJhc2VkIG9uIDE5NzAgY2Vuc3VzKQ0KDQojIyNSYW5kb20gRm9yZXN0cw0KDQpgYGB7cn0NCnJlcXVpcmUoTUFTUykNCnJlcXVpcmUocmFuZG9tRm9yZXN0KQ0KYGBgDQoNClRoaXMgYnVpbGRzIGEgbG90IG9mIHRyZWVzLCBzZWxlY3RpbmcgYSBzcGxpdCBwYXJhbWV0ZXIgZnJvbSBhIHN1YnNldCBvZiBwYXJhbWV0ZXJzLCBhbmQgYXZlcmFnZXMgb3V0IHRvIHJlZHVjZSB0aGUgdmFyaWFuY2UuDQoNCkNyZWF0aW5nIGEgdHJhaW4tdGVzdCBzcGxpdCB3aXRoIDMwMC0yMDYgZGF0YSBvYnNlcnZhdGlvbnMgZWFjaA0KYGBge3J9DQpzZXQuc2VlZCgxMDEpDQpkYXRhKEJvc3RvbikNCmluZGV4IDwtIHNhbXBsZSgxOm5yb3coQm9zdG9uKSwgMzAwKQ0KYGBgDQoNCldlIHVzZSByYW5kb20gZm9yZXN0IGZvciByZWdyZXNzaW9uLCB3aXRoICdtZWR2JyBhcyB0aGUgcmVzcG9uc2UgdmFyaWFibGUgYW5kIGV2ZXJ5IG90aGVyIHZhcmlhYmxlIGFzIHRoZSBwcmVkaWN0b3IuDQoNCg0KYGBge3J9DQpyZl9ib3N0b24gPC0gcmFuZG9tRm9yZXN0KG1lZHZ+LiwgZGF0YSA9IEJvc3Rvbiwgc3Vic2V0ID0gaW5kZXgpDQpyZl9ib3N0b24NCmBgYA0KDQo1MDAgdHJlZXMgd2VyZSBncm93bi4gVGhlIG51bWJlciBvZiB2YXJpYWJsZXMgYXQgZWFjaCBzcGxpdCBpcyA0LCB3aGljaCBpcyBhcHByb3hpbWF0ZWx5IHNxcnQoMTMpLCB0aGUgbnVtYmVyIG9mIHBhcmFtZXRlcnMuIFRoZSBNU1IgaXMgT3V0IG9mIEJhZyBtZWFuIHNxdWFyZWQgcmVzaWR1YWxzLg0KDQptIGlzIHRoZSBudW1iZXIgb2YgdmFyaWFibGVzIHRoYXQgaXMgc2VsZWN0ZWQgYXQgZWFjaCBzcGxpdCBpbiByYW5kb20uIFRoaXMgaXMgZ2l2ZW4gYnkgdGhlIG10cnkgcGFyYW1ldGVyIGluIHJhbmRvbUZvcmVzdCgpLiBBbmQgdGhpcyBpcyBvbmUgb2YgdGhlIHBhcmFtZXRlcnMgdGhhdCB3ZSBjYW4gdHVuZS4NCg0KQnVpbGRpbmcgcmFuZG9tIGZvcmVzdCBkZWNpc2lvbiB0cmVlcyB3aXRoIG0gcmFuZ2luZyBmcm9tIDEgdG8gMTMgKHAgcGFyYW1ldGVycyksIGFuZCByZWNvcmRpbmcgdGhlIE9PQiBhbmQgdGVzdCBlcnJvcnMNCg0KYGBge3J9DQpvb2JfcmZfZXJyb3IgPC0gZG91YmxlKDEzKQ0KdGVzdF9yZl9lcnJvciA8LSBkb3VibGUoMTMpDQoNCmZvcihtIGluIDE6MTMpDQp7DQogIGZpdCA8LSByYW5kb21Gb3Jlc3QobWVkdn4uLCBkYXRhID0gQm9zdG9uLCBzdWJzZXQgPSBpbmRleCwgbXRyeSA9IG0sIG50cmVlID0gNDAwKQ0KICBvb2JfcmZfZXJyb3JbbV0gPC0gZml0JG1zZVs0MDBdDQogIHByZWQgPC0gcHJlZGljdChmaXQsIEJvc3RvblstaW5kZXgsXSkNCiAgdGVzdF9yZl9lcnJvclttXSA8LSB3aXRoKEJvc3RvblstaW5kZXgsXSwgbWVhbigobWVkdiAtIHByZWQpXjIpKQ0KICBjYXQobSwiICIpDQp9DQoNCmBgYA0KDQoNClBsb3R0aW5nIHRoZSBvb2IgYW5kIHRlc3QgZXJyb3JzIGFjcm9zcyBtDQoNCi0gdHlwZSA9ICJiIiBtZWFucyBpdCBwbG90cyBib3RoIHRoZSBwb2ludHMgYW5kIGNvbm5lY3RzIHRoZW0gd2l0aCBsaW5lcw0KYGBge3J9DQptYXRwbG90KDE6bSwgY2JpbmQodGVzdF9yZl9lcnJvciwgb29iX3JmX2Vycm9yKSwgcGNoID0gMTksIGNvbCA9IGMoInJlZCIsICJibHVlIiksIHR5cGUgPSAiYiIsIHlsYWIgPSAiTWVhbiBTcXVhcmVkIEVycm9yIikNCmxlZ2VuZCgidG9wcmlnaHQiLCBsZWdlbmQgPSBjKCJPT0IiLCAiVGVzdCIpLCBwY2ggPSAxOSwgY29sID0gYygicmVkIiwgImJsdWUiKSkNCmBgYA0KDQpJZiB3ZSB3YW50IHRvIGRvIEJhZ2dpbmcsIHdlIGNhbiB1c2UgbXRyeSA9IG51bWJlciBvZiBwYXJhbWV0ZXJzLiBUaGUgbGVmdCBtb3N0IGlzIHZhbHVlIGlzIHRoZSBNU0Ugb2YgYSBzaW5nbGUgdHJlZQ0KDQotLS0NCg0KIyMjQm9vc3RpbmcNCg0KV2UgcnVuIGEgc2ltcGxlIGJvb3NpdG5nIGxvZ2ljIG9uIHRoZSBzYW1lIEJvc3RvbiBkYXRhLiBXZSB1c2UgdGhlIHBhY2thZ2UgImdibSIgKEdyYWRpZW50IEJvb3N0ZWQgTWFjaGluZXMpDQoNCmBgYHtyfQ0KcmVxdWlyZShnYm0pDQpgYGANCg0KV2UgYXNrIGZvciAxMDAwMCBiZWNhdXNlIHRoZXJlIGFyZSBhIGxvdCBvZiBzaGFsbG93IHRyZWVzLCB3aXRoIDQgZGVwdGhzLiBTbywgNCBzcGxpdHMgY2hvb3NpbmcgNCB2YXJpYWJsZXMuDQoNCmBgYHtyfQ0KYm9vc3RfYm9zdG9uIDwtIGdibShtZWR2fi4sIGRhdGEgPSBCb3N0b25baW5kZXgsXSwgZGlzdHJpYnV0aW9uID0gImdhdXNzaWFuIiwgbi50cmVlcyA9IDEwMDAwLCBzaHJpbmthZ2UgPSAwLjAxLCBpbnRlcmFjdGlvbi5kZXB0aCA9NCkNCnN1bW1hcnkoYm9vc3RfYm9zdG9uKQ0KYGBgDQoNClN1bW1hcnkgZ2l2ZXMgdGhlIHZhcmlhYmxlIGltcG9ydGFuY2UgcGxvdCEgVGhlIHR3byB2YXJpYWJsZXMgdGhhdCBzZWVtIHRvIGJlIGltcG9ydGFudCBhcmUgbHN0YXQgYW5kIHJtDQoNCkNoZWNraW5nIG91dCB0aGUgdHdvIHZhcmlhYmxlcywgcGFydGlhbCBkZXBlbmRlbmNlIHBsb3RzDQpgYGB7cn0NCnBhcihtZnJvdyA9IGMoMSwyKSkNCnBsb3QoYm9vc3RfYm9zdG9uLCBpID0gImxzdGF0IikNCnBsb3QoYm9vc3RfYm9zdG9uLCBpID0gInJtIikNCmBgYA0KDQpIaWdoZXIgdGhlIHByb3BvcnRpb24gb2YgbG93ZXIgc3RhdHVzIHBlb3BsZSBpbiB0aGUgc3VidXJiLCBsb3dlciB0aGUgdmFsdWUgb2YgdGhlIGhvdXNlDQpIaWdoZXIgdGhlIG51bWJlciBvZiByb29tcyBpbiB0aGUgaG91c2UsIGhpZ2hlciB0aGUgdmFsdWUgb2YgdGhlIGhvdXNlDQoNCi0tLQ0KDQpMb29raW5nIGF0IHRoZSB0ZXN0IHBlcmZvcm1hbmNlIGFzIGEgZnVuY3Rpb24gb2YgdGhlIG51bWJlciBvZiB0cmVlcw0KDQpgYGB7cn0NCm5vX3RyZWVzIDwtIHNlcShmcm9tID0gMTAwLCB0byA9IDEwMDAwLCBieSA9IDEwMCkNCnByZWRfbWF0cml4IDwtIHByZWRpY3QoYm9vc3RfYm9zdG9uLCBuZXdkYXRhID0gQm9zdG9uWy1pbmRleCxdLCBuLnRyZWVzID0gbm9fdHJlZXMpDQoNCmBgYA0KDQpwcmVkX21hdHJpeCBjb25zaXN0cyBvZiBhIG1hdHJpeCBvZiBwcmVkaWN0aW9ucyBvZiB0aGUgdGVzdCBkYXRhLiBTbywgdGhlcmUgYXJlIDIwNiBvYnNlcnZhdGlvbnMgb2YgdGhlIHRlc3QgZGF0YSwgYW5kIDEwMCBkaWZmZXJlbnQgdHJlZSBwcmVkaWN0aW9ucw0KDQpDb21wdXRpbmcgdGhlIHRlc3QgZXJyb3INCg0KV2UgaGF2ZSBjYWxjdWxhdGVkIHRoZSBzcXVhcmVkIGRpZmZlcmVuY2VzIGZvciBlYWNoIG9mIHRoZSBjb2x1bW5zLCBhbmQgdGhlbiB3ZSB0YWtlIHRoZSBtZWFuIG9mIGVhY2ggY29sdW1uLiBUaGlzIGNvbXB1dGVzIHRoZSBjb2x1bW4td2lzZSBtZWFuIHNxdWFyZWQgZXJyb3INCmBgYHtyfQ0KYm9vc3RfdGVzdF9lcnJvciA8LSB3aXRoKEJvc3RvblstaW5kZXgsXSwgYXBwbHkoKHByZWRfbWF0cml4IC0gbWVkdileMiwgMiwgbWVhbikpDQpgYGANCg0KDQpQbG90aW5nIHRoZSBib29zdGluZyB0ZXN0IGVycm9yIGFuZCBjb21wYXJpbmcgaXQgd2l0aCB0aGUgcmFuZG9tIGZvcmVzdCBlcnJvcg0KDQpgYGB7cn0NCnBsb3Qobm9fdHJlZXMsIGJvb3N0X3Rlc3RfZXJyb3IsIHBjaCA9IDE5LCB5bGFiID0gIk1lYW4gU3F1YXJlZCBFcnJvciIsIHhsYWIgPSAiIyBvZiBUcmVlcyIsIG1haW4gPSAiQm9vc3RpbmcgVGVzdCBFcnJvciIpDQphYmxpbmUoaCA9IG1pbih0ZXN0X3JmX2Vycm9yKSwgY29sID0gInJlZCIpDQpgYGANCg0KVGhlIHRlc3QgZXJyb3IgZHJvcHMgZG93biwgYnV0IGxldmVscyBvZmYuIFRoZXJlIGlzIG5vIHJlYWwgaW5jcmVhc2Ugb2YgZGVjcmVhc2UuDQoNCi0tLQ0K