type
Post
Created date
Jun 16, 2022 01:21 PM
category
Data Science
tags
Machine Learning
Machine Learning
status
Published
Language
From
summary
slug
password
Author
Priority
Featured
Featured
Cover
Origin
Type
URL
Youtube
Youtube
icon
Definition
- The goal is to try to minimise the entropy to 0.
- It has multiple algorithms to decide to split a node into two or more sub-nodes.
- The creation of sub-nodes increases the homogeneity (同質) of resultant sub-nodes. In other words, we can say that the purity of the node increases with respect to the target variable.
- It starts with a root node and ends with a decision made by leaves.
Theory
Term [KDnuggets]
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F65bb50d0-f30b-4f93-bdb5-749c6e68e483%2FUntitled.png%3Ftable%3Dblock%26id%3D04618e79-eda2-4fa9-933d-fa9965bf4424%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DdoyQrw7it6Hnj766VfVIMYGUGr6hH2Kw5XenIAFIcEc?table=block&id=04618e79-eda2-4fa9-933d-fa9965bf4424&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F12d00cba-68af-44b1-9e86-b7bfd08c6d9e%2Ftree-notation.jpeg%3Ftable%3Dblock%26id%3Deb972779-06b0-4c7f-9005-649b745ac2d9%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3Db84isVCduO7XvpIZY219gN48y2m4bfO-470fG7qfZzI?table=block&id=eb972779-06b0-4c7f-9005-649b745ac2d9&cache=v2)
- Root Node: It represents the entire population or sample and this further gets divided into two or more homogeneous sets.
- Splitting: It is a process of dividing a node into two or more sub-nodes.
- Decision Node: When a sub-node splits into further sub-nodes, then it is called the decision node.
- Leaf / Terminal Node: Nodes do not split is called Leaf or Terminal node.
- Pruning: When we remove sub-nodes of a decision node, this process is called pruning. You can say the opposite process of splitting.
- Branch / Sub-Tree: A subsection of the entire tree is called a branch or sub-tree.
- Parent and Child Node: A node, which is divided into sub-nodes is called a parent node of sub-nodes whereas sub-nodes are the child of a parent node.
Assumption
- Initially, whole training data is considered as root.
- Records are distributed recursively on the basis of the attribute value.
Mechanism
- Works by repeatedly partitioning the data into multiple sub-spaces, so that the outcomes in each final sub-space are as homogeneous as possible. This approach is technically called recursive partitioning. [STHDA]
The tree will stop growing by the following three criteria: [STHDA]
- all leaf nodes are pure with a single class;
- a pre-specified minimum number of training observations that cannot be assigned to each leaf node with any splitting methods; (MINSPLIT)
- If my
MINSPLIT
= 5
, only my node has 5, then I can keep splitting. - Another word: the minimum number of samples for each spilt. [Vidhya]
- For example, we can use a minimum of 10 samples to reach a decision. That means if a node has less than 10 samples then using this parameter, we can stop the further splitting of this node and make it a leaf node. [Vidhya]
- The number of observations in the leaf node reaches the pre-specified minimum one. (MINBUCKET)
- If my
MINBUCKET
= 5,
my last node has to contain at least 5 observations.
The training error will decrease if we increase the max_depth value, but it might increase the test error — meaning overfitting.
Example
Brendi
Extend the entropy formula so that it can be used to describe the impurity for a possible split of the data
into two subsets.
reThat is, it needs to be the sum of the impurity for both left and right subsets of data.
![1a-entropy](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F7ad4e705-bd6e-4c35-9efe-2ecf7fab72da%2F1c-impurity.jpeg%3Ftable%3Dblock%26id%3D90529bb8-54ec-405a-a326-5b2701db9356%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3Dd_EMG7I2GZp3fc5ZxZYFmBNFptpn4bmsjeCBwbrdo6M?table=block&id=90529bb8-54ec-405a-a326-5b2701db9356&cache=v2)
![1c-impurity](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fe4ce6bcf-dbb8-4112-a236-a4ce8bfa0213%2F1a-entropy.jpeg%3Ftable%3Dblock%26id%3D0340bff2-a65c-4c3a-a5f7-549bff493bea%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DbwsUSTmJWKgZoC5Ym8OIQ_AiIvcPP4Av887o40eCiWw?table=block&id=0340bff2-a65c-4c3a-a5f7-549bff493bea&cache=v2)
![1b-derivatives](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F44c6efad-0713-4c33-8629-8da8972ca162%2F1b-derivatives.jpeg%3Ftable%3Dblock%26id%3Df7bd64c8-edf5-4cc9-ba2c-b7abfc57e261%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3D_MFX1FH6VCflyWVb4eIlwxtLkyLoY9Udn2V3L4mNEnc?table=block&id=f7bd64c8-edf5-4cc9-ba2c-b7abfc57e261&cache=v2)
![2a-splits](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F6b8c15d2-5a56-4a1a-8b89-36b4a3094b18%2F2a-splits.jpeg%3Ftable%3Dblock%26id%3Dc80de450-f015-4b0d-afb7-b8f0227b0f57%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DIfgLGCt9AviMSzNnZWOCK6oSq3JRw_jquTCHHL-aeRg?table=block&id=c80de450-f015-4b0d-afb7-b8f0227b0f57&cache=v2)
![2b-classification-rule](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fa839e567-cfb0-43e4-bed8-fb59d6f72734%2F2b-classification-rule.jpeg%3Ftable%3Dblock%26id%3De7cef16f-1b16-4f2f-9067-e7817a7cec30%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3Dd9r15LbUc9BTkNlaLEkA_wcuvwThMQATh3CsKG_QfB8?table=block&id=e7cef16f-1b16-4f2f-9067-e7817a7cec30&cache=v2)
![3a-olive-split](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F95eaaaee-f841-4740-93d9-db5582162eef%2F3a-olive-split.jpeg%3Ftable%3Dblock%26id%3Ddfd607b1-697b-4799-b01a-00903c351f47%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3D431gsJ78PT8tfrDFZWAvzhPYaWaeoc9AeYb0Cw6Gkhc?table=block&id=dfd607b1-697b-4799-b01a-00903c351f47&cache=v2)
Pruning
Problem:
A fully grown tree will overfit the training data and the resulting model might not be good for predicting the outcome of new test data.
Solution
pruning controls this problem.
- You trim off the branches of the tree, i.e., remove the decision nodes starting from the leaf node such that the overall accuracy is not disturbed. [KDnuggets]
- This is done by segregating the actual training set into two sets: training data set, D and validation data set, V. Prepare the decision tree using the segregated training data set, D. Then continue trimming the tree accordingly to optimize the accuracy of the validation data set, V. [KDnuggets]
- We have pre-prune and post-prune
R code
Some good links:
olive <- read_csv("http://www.ggobi.org/book/data/olive.csv") %>% rename(name=`...1`) %>% dplyr::select(-name, -area) %>% mutate(region = factor(region)) tree_spec <- decision_tree() %>% set_engine("rpart") class_tree_spec <- tree_spec %>% set_mode("classification") olive_rp <- class_tree_spec %>% fit(region~., data=olive) olive_rp ## You can change the cp value according to your data set. Please note lower cp value means bigger the tree. ## If you are using too lower cp that leads to overfitting also. printcp(olive_rp$fit)
Plot
library(rpart.plot) olive_rp %>% extract_fit_engine() %>% rpart.plot() # ======= examine using ggplot ggplot(olive, aes(x=eicosenoic, y=linoleic, colour=region)) + geom_point() + scale_color_brewer("", palette="Dark2") + geom_vline(xintercept=6.5) + annotate("line", x=c(0, 6.5), y=c(1053.5, 1053.5)) + theme(aspect.ratio = 1)
Tuning params
## rpart.control(minsplit = 20, minbucket = round(minsplit/3), maxdepth = 30) ## Arguments: ## -minsplit: Set the minimum number of observations in the node before the algorithm perform a split ## -minbucket: Set the minimum number of observations in the final note i.e. the leaf ## -maxdepth: Set the maximum depth of any node of the final tree. The root node is treated a depth 0 control <- rpart.control(minsplit = 4, minbucket = round(5 / 3), maxdepth = 3, cp = 0) tune_fit <- rpart(survived~., data = data_train, method = 'class', control = control) accuracy_tune(tune_fit)
R interpretation
We predict the model and then use confusion to calculate the measure.
FAQ
Gini vs Entropy (more here)
• Gini Index has values inside the interval [0, 0.5] whereas the interval of the Entropy is [0, 1]. In the following figure, both of them are represented. The gini index has also been represented multiplied by two to see concretely the differences between them, which are not very significant.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fc649e6d3-dc55-4b75-a35b-58d8db0a91af%2FUntitled.png%3Ftable%3Dblock%26id%3D071696f9-2116-45c5-8d87-e2a0f63b63a7%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DHK9QVFlElcCUh8Zfjguo-z6KoXjIRZoPf7uLI-8YSlw?table=block&id=071696f9-2116-45c5-8d87-e2a0f63b63a7&cache=v2)
• Computationally, entropy is more complex since it makes use of logarithms and consequently, the calculation of the Gini Index will be faster.
Math
The sum is computed across the different categories or classes in the outcome variable. [KDnuggets]
For the classification tree, two measures of purity are Gini impurity and Entropy; both of which vary from 0 (greatest purity) to 1 (maximum degree of impurity) [KDnuggets]
Gini impurity
- Worse case split occurs at p(1-p) 25%.
- Understand it as a COST FUNCTION used to evaluate splits in the dataset
Higher value of Gini index implies higher inequality, higher heterogeneity.
Example from ETC3250 lecture
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F02ca0547-44db-4122-83ae-dd98b8096a0f%2FUntitled.png%3Ftable%3Dblock%26id%3Dd8c0fbd2-8059-4056-b014-6b791288f115%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DZv3L6aUUgSbzGn01MS8L6TkmCdbO7lEJ2QforcdgNZY?table=block&id=d8c0fbd2-8059-4056-b014-6b791288f115&cache=v2)
Entropy (Measure of disorder)
where p is the proportion of misclassified observations within the subpartition.- Worse case split is at 50%, where entropy value is the highest. Best split is 0
Example from FIT3152 lecture
![initial state](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F6e074d0e-20c1-4805-ad80-7539fdfc5443%2FUntitled.png%3Ftable%3Dblock%26id%3D16b537d9-af4d-45f7-9f50-255af24d1d2d%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DiPJxvc0GAMVqXGnxtHnR2eHWPN3TzyCYaqou96hIYfA?table=block&id=16b537d9-af4d-45f7-9f50-255af24d1d2d&cache=v2)
For the regression tree, we use RMSE (root mean squared error) to measure [TTP]
The prediction error is measured by the RMSE, which corresponds to the average difference between the observed known values of the outcome and the predicted value by the model
- The lower the RMSE, the better the model.
- The best
cp
(complexity parameter) value is the one that minimizes the prediction error RMSE (root mean squared error).
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fa66562a2-1f22-4ef0-890d-4baefbbfb15d%2FUntitled.png%3Ftable%3Dblock%26id%3D6b9bfeb2-ee95-49ae-b19d-855608b1540f%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725847200000%26signature%3DC-vee7z0o1fpWk8kvIK7i08tv2Mlz04CohVphYXqp5g?table=block&id=6b9bfeb2-ee95-49ae-b19d-855608b1540f&cache=v2)
- Further maths is here.
Reference
Slides
Extra Resource
Video
Exercise for entropy / Gini
- Author:Jason Siu
- URL:https://jason-siu.com/52b1ad9bacb347c2a70a371906517725
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts