Decision Trees - Pt.2

Stopping Criteria

• Building decision trees is a recursive algorithm

• The initial split produces children

Why does tree building stop?

• The number of records per node reaches some pre-set limit

• The depth of the tree reaches some pre-set limit

• No split can be found that increases the PURITY of any node’s CHILDREN

Partitioning the Data

• When a model is developed on training data, it can overfit the training data

• Some methods use the test data to choose parameters

• Final selected model is applied to a holdout partition (unseen data) that gives an unbiased estimate of its performance on the new data

What does is partitioning data?

• When a model is developed on training data, it can overfit the training data

• Some methods use the test data to choose the parameters, or choose among alternative models

What is the solution for overfitting data?

The final selection is applied to a holdout partition → unseen data to give unbiased estimate of its performance on the new data

What data should you NEVER use during the Model traning phase?

NEVER use the test set

What is cross validation?

Repeated partitioning the data to evaluate a model’s performance across multiple runs

What is k-fold cross-validation?

A method that divides data into k folds and uses each fold once as validation data while the remaining folds are used as TRAINING data.

What happens during each run of k-fold cross-validation?

One fold is set aside as validation data, and the remaining k-1 folds are used as training data

Do validation folds overlap in k-fold cross-validation?

No the validation folds are non-overlapping

How is performance calculated in k-fold cross-validation?

Calculate the average performance across all k runs

What is a confusion matrix?

Actual values V.S. predictive values

What are the four outcomes in a confusion matrix?

True Positive (TP), True Negative(TN), False Positive (FP), False Negative (FN)

What is a True Positive?

The actual class is positive, and the model predicts positive

What is a True Negative?

The actual class is negative, and the model predicts negative

What is a False Positive?

The actual class is negative, but the model predicts positive

What is a False Negative?

The actual is positive, but the model predicts negative

How is accuracy(correctness) calculated?

(TP + TN)/ (TP+TN+FP+FN)

How is sensitivity calculated?

TP/(TP+FN)

How is specificity calculated?

TN/(FP+TN)

How do you calculate True Positive Rate?

TP Rate = TP / (TP+FN)

How do you calculate False Positive Rate?

FP/(FP+TN) = 1 - Specificity

Precision calculation

TP/(TP+FP)

Mis-Calculation Error Calculation

(FP+FN)/(FP+FN+TP+TN)

F_Measure Calculation

2*(Precision*Recall)/(Precision+Recall)

What is an ROC Curve?

Receiver Operating Characteristic(ROC) curve depicts the TP rate vs. FP rate

What does the area under the curve represent?

Close to 1 → the classifier performs the best

Close to 0.5 → classifier performs poor

Much less than 0.5 → Performs much worse than a random guess

What does the Y-axis represent on the ROC curve?

Rate of correctly identifying Positive cases among actual positive cases

TPR = TP/(TP+FN)

What does the X-axis represent on the ROC curve?

Rate of incorrectly classifying Negative cases among actual negative cases

FPR = FP/(FP+TN)

How can an algorithm be useful in the real-world?

• Permit numeric attributes

• Allow missing values

• Be robust in the presence of noise

ID3

• Accepts categorical values

• Chooses split attribute with the highest information gain

Extending ID3

• To permit numeric attributes

• To deal with missing values

• Stability for noisy data

End result of extending ID3

Best-known and probably widely-used learning algorithm

C4.5

• Handling missing values

• Accepts continuous values

• Uses information gain ratio to decide the best split

• Best-known and most widely-used learning algorithm

C5

• Commercial successor of C4.5

• C4.5 is open source; C5 is used in commercial packages

CART (Classification and Regression Tree)

• Creates binary tree

• Works well with numeric variables

• Uses “Reduction Variance”

• Prediction is computed as the average of numerical target variables

• Performance measured by RMSE

What does RMSE stand for?

Root Mean Squared Error