STAT318-20S2 (C) / STAT462-20S2 (C) Data Mining

1.   (a) Suppose that we have the following 100 market basket transactions.

For example, there are 10 transactions of the form {apple, carrot}

i.  Compute the support of {orange}, {banana, carrot}, and {banana, carrot, orange}.

ii.  Compute the confidence of the association rules:           {banana, carrot} → {orange};  and

{orange} → {banana, carrot}.

Is confidence a symmetric measure? Justify your answer.

iii.  Find the 3-itemset(s) with the largest support.

iv.  If minsup = 0.2,  is {banana, carrot, orange} a maximal frequent itemset?

Justify your answer.

v.  Lift is defined as

s(X n Y)

Lift(X → Y) =

where s( ) denotes support. What does it mean if Lift(X → Y) < 1.

(b) This question examines linear discriminant analysis (LDA) and quadratic discrimi-

nant analysis (QDA) for a 2-class classification problem.

i.  Under what conditions are Bayes classifier and LDA equivalent classifiers?

ii.  Explain the difference between LDA and QDA.

iii.  In general, as the sample size increases, do we expect the test prediction ac- curacy of QDA relative to LDA to improve, decline, or be unchanged? Why?

2.   (a)  Describe two potential advantages of regression trees over other statistical learning methods.

(b) This question uses the CART partition given below. The points in each box denote

the training data and the numbers next to them are their response values.

3

1         14

2   . 1    .                        14.

.16       .10

X2        1                                                                   10

.

2

.

0                5                          

- 1       .3   .        .4                                .12

2      3       4       5       6       7       8       9      10

X 1

i. Sketch the decision tree corresponding to the CART partition.

ii.  Predict the  response values for the following observations  using your tree, where x = (x1 , x2 ):

a = (5, 1);   b = (3.5, 2);    and   c = (11, −2.)

iii. What is the training MSE for your tree?

(c) The predictive performance of a single regression tree can be substantially improved by aggregating many decision trees.

i.  Briefly explain the method of bagging regression trees.

ii.  Explain the difference between bagging and random forest.

iii.  Briefly explain two differences between boosted regression trees and random forest.

3.   (a)  Using one or two sentences, explain the main difference between regression and classification problems.

(b) The expected test MSE, for a given x0 , can be decomposed into the sum of three

fundamental quantities:

E[y0 − fˆ(x0 )]2  = V (fˆ(x0 )) + [Bias(fˆ(x0 ))]2 + V (∈). Briefly explain each of these three quantities.

(c)  Briefly explain what is meant by over-fitting and under-fitting the training data.

(d)  Provide a sketch typical of training error, testing error, and the irreducible error, on a single plot, against the flexibility of a statistical learning method. The x-axis should represent the flexibility and the y-axis should represent the error. Make sure the plot is clearly labelled.  Explain why each of the three curves has the shape displayed in your plot.

(e)  Indicate on your plot in part (d) where we would generally expect to find a regression

tree with five splits,  a  random forest,  and  k-nearest  neighbour  regression with k = 3. Explain why you have placed these methods where you have.

(f) Would we generally expect the training MSE of an un-pruned regression tree to be better or worse than a pruned regression tree? Why?