Chapter 4
Decision tree: is a supervised learning algorithm used for classification and regression. It has a hierarchal
tree structure with a root node, branches and leaf nodes.
Each path from node to leaf represents a classification rule
An internal node is a test on attribute
Leaf node is a class label
Types of goodness functions (choosing the splitting attribute):
1) Information gain
2) Information gain ration
3) Gini index
Criterion for attribute selection:
1) Choose the attribute that results in the smallest tree
2) Choose the attribute that produces the purest nodes
3) Use an impurity measure (info gain)
4) Strategy: pick the attribute with the highest info gain
Impurity/entropy: measures the level of impurity in a group of examples
Minimum impurity is log2 1 = 0
Info gain measures how much entropy is reduced
Slide 23 example:
We choose outlook because it has the highest info gain, overcast is all yes so doesn’t need any more
branches, we have to find the highest info gain for sunny and rainy. We do sunny+temprature,
sunny+humidity, sunny+windy and same for rainy
For sunny we choose humidity because it’s the highest info gain while for rain we choose windy because
it’s the highest info gain
Subsets are more likely to be pure if there is a large number of values, info gain is biased towards
choosing the attributes with large number of values which may result in overfitting model
Irrelevant attributes like ID has entropy of 0 so maximum info gain which is misleading
How to avoid overfitting:
1) Stop splitting early
2) Acquire more training data
3) Remove irrelevant attributes
How to select best tree:
1) Check accuracy on training data
2) Evaluate performance on a separate development/test set
Strengths of decision trees:
1) Fast, simple to implement
2) Can convert to rules
3) Handles noisy and missing data
4) Less effort for preprocessing
5) Can be used for classification or regression
6) Automatic feature selection
7) Handle non linear relationships
Weaknesses of decision trees:
1) Prone to overfitting
2) Large decision trees may be hard to understand
3) Unstable (a small change in data can cause large change in structure)
4) Slow to train on large datasets
5) Biased towards dominant classes
Chapter 5
After training a model we must check how well it works on unseen data
Why evaluation is needed:
1) To measure accuracy/performance
2) To compare models
3) To detect overfitting
4) To choose the best model
Workflow of traditional ML (batch learning):
1) Training dataset
2) Train the model
3) Keep part of data unseen for testing
4) Test the model
5) Measure metrics
Most common evaluation method is the hold out method
How hold out works:
1) Split your dataset into: training set (to learn the model), test set (to evaluate the model)
2) Train the model
3) Predict on the test set
4) Compare predictions with true labels
Sometimes we keep extra data aside for tuning called development set
Chapter 6
KNN: k nearest neighbor
KNN algorithm: is a supervised machine learning algorithm that is generally used for classification but
could be used for regression
If k is too small it would be sensitive to noise, if its too large it may include points from irrelevant classes
KNN is a lazy learner because it doesn’t explicitly build models
Missing or irrelevant attributes are hard to handle
Prediction accuracy decreases quickly when number of attributes grow so we either try to remove
irrelevant attributes in preprocessing step or increase k (but not too much)
Advantages of KNN:
1) Easy to understand
2) Can be applied to both regression and classification
3) Works easily on multi class problems
Disadvantages od KNN:
1) Computationally expensive
2) Sensitive to scale of data
3) Struggle with high number of independent attributes (curse of dimensionality)