Unit 2: Classification with Decision Trees

Question 1

Classification

Definition

Answer 1

Given a collection of records (dataset)
- Each record is characterised by a tuple (x, y), where x is the attribute set and y is the class label.

Task:
- Learn a model that maps each attribute set x into one of the predefined class labels y.

Question 2

Inference

Answer 2

The process of using a model in order to infer the class or a given record.

Question 3

Gini impurity

Answer 3

A metric describing how pure or mixed the data labels in a node are.

Pure nodes have Gini Impurity close to 0, where impure notes have a Gini impurity value closer to 0.5.

Question 4

Information Gain of a Split

Answer 4

Refers to the amount of information gained by choosing one of the possible splits.

Information Gain
EQUALS
Impurity of the Parent
MINUS
Weighted Average Impurity of the Children

Question 5

CART Algorithm

Answer 5

Grow (Data, attributes):

if (number of rows |Data| < h):
* Create (a leaf that has the dominant label of the Data)
* Return the leaf with its label.

Else:
* AttributesGain = InfoGain(Attributes)
* attribute = Max(AttributesGain)
* bsNode = Create (attribute)
* For each value of the attribute,
* - Data = Split(attribute, value)
* - Child = Grow (Data, Attributes)
* - bsNode = Add (Child to bsNode)

Question 6

Entropy Formula

Answer 6

-Σᵢ₌₁ⁿ pᵢ log(pᵢ)

Question 7

Gini Formula

Answer 7

Σᵢ₌₁ⁿ pᵢ (1 - pᵢ)

Question 8

Classification error

Answer 8

1 - max(pᵢ)

Question 9

Accuracy of a classifier

Answer 9

The proportion of correctly classified instances

(TP + TN) / N

Question 10

Error rate

Answer 10

Proportion of incorrectly classified instances.

(FP + FN) / N

Question 11

General Structure of Hunt’s Algorithm

Answer 11

Let Dₜ be the set of training records that read a node t

General Procedure:
- If Dₜ contains records that belong to the same class yₜ, then t is a leaf node labeled as yₜ
- If Dₜ contains records that belong to more than one class, use an attribute test to split the data into smaller subsets.

Recursively apply the procedure to each subset.

Question 12

Hunt’s Algorithm

2 Design Issues of Decision Tree Induction

Answer 12

How should training records be split?
- Method for specifying the test condition (which depends on attribute types).
- Measure for evaluating the goodness of a test condition.

How should the splitting procedure stop?
- Stop splitting if all the records belong to the same class or have identical attribute values.
- Early termination.

Question 13

4 Attribute types in a DT test condition

Answer 13

• Binary
• Nominal
• Ordinal
• Continuous

Question 14

2 ways of splitting based on continuous attributes

Answer 14

1. Discretization to form an ordinal categorical
   attribute.
   Ranges can be found by equal interval bucketing, equal frequency bucketing (percentiles), or clustering.
2. Binary Decision (A < v) or (A ≥ v)
   Consider all possible splits and finds the best cut. This can be more compute intensive.

Question 15

Decision trees

Finding the best split

Answer 15

1. Compute the impurity measure (P) before splitting
2. Compute the impurity measure (M) after splitting. M is the weighted impurity of child nodes.
3. Choose the attribute test condition that produces the highest gain.

Gaim = P - M

Question 16

5 Advantages of Decision-Tree based classification

Answer 16

• Relatively inexpensive to construct
• Extremely fast at classifying unknown records
• Easy to interpret for small-sized trees
• Robust to noise (especially when methods to avoid overfitting are employed)
• Can easily handle redundant or irrelevant attributes (unless the attributes are interacting)

Question 17

2 Disadvantages of Decision Tree-based classification

Answer 17

• Due to the greedy nature of the splitting criterion, interacting attributes may be passed over in favour of other attributes that are less discriminating.
• Each decision boundary involves only a single attribute.

Question 18

Type I error

Answer 18

False Positive

Question 19

Type II error

Answer 19

False Negative

Question 20

Holistic Metrics

Answer 20

Metrics that look at both horizontal and vertical views and involve both positive and negative classes.

E.g. F1 score & Matthew Correlation Coefficient

Question 21

Precision

Answer 21

Refers to the precision of the prediction of the classifier with respect to the positive class.

A.k.a. Positive prediction value

Question 22

Recall

true positive rate / hit rate

Answer 22

Measures how good the classifier is at detecting the actual positive cases.

Question 23

positive detection rate

p(detect₊)

Answer 23

TP / (TP + FN)

How many of the positives were caught by the model?

Question 24

NOT positive detection rate

¬ p(detect₊)

Answer 24

FN / (TP + FN)

How many of the positives were missed by the model?

Question 25

negative detection rate

p(detect₋)

Answer 25

TN / (TN + FP)

How many of the negatives were caught by the model?

Question 26

NOT negative detection rate

¬p(detect₋)

Answer 26

FP / (TN + FP)

How many of the negatives were missed by the model?

Question 27

positive prediction rate

p(predict₊)

Answer 27

TP / (TP + FP)

How many of those predicted to be positive, were actually positive?

Question 28

NOT positive prediction rate

¬p(predict₊)

Answer 28

FP / (TP + FP)

How many of those predicted to be positive, were actually negative?

Question 29

negative prediction rate

p(predict₋)

Answer 29

TN / (TN + FN)

How many of those predicted to be negative, were actually negartive?

Question 30

NOT negative prediction rate

¬p(predict₋)

Answer 30

FN / (TN + FN)

How many of those predicted to be negative, were actually positive?

Question 31

Accuracy for a multi-class problem

Answer 31

∑ᵢ{ TCᵢ } / N

TCᵢ is the count of the correctly classified instances of class Cᵢ

Question 32

Holistic metric for multiclass p(detect) or p(predict)

recall score / balanced accuracy score / precision score

Answer 32

1. Take the arithmetic mean of these rates.
2. Take a weighted average of the detection rates. This allows assigning different weights for the different classes.

Question 33

Holistic metric for multiclass: F1 Score

Answer 33

To generalise the F1 score to multi-class problems, we can:
1. Either use overall recall and precision and then apply the harmonic mean, as in the binary class problem.
2. We can treat the classes as one vs. the rest and obtain the F1 score for each class separately. We can then take the average of the F1 score for all these classes.

Question 34

Model generalisation

Answer 34

Using the training set to come up with a general relationship between the features and the class that can be utilised to later classify unseen examples.