ISOM3360 Data Mining for Business Analytics, Session 4
Decision Trees (I)
Instructor: Department of ISOM Spring 2022
Copyright By PowCoder代写 加微信 powcoder
Recap: Data Understanding
Preliminary investigation of the data to better understand its specific characteristics
❖ Help in selecting appropriate data mining algorithms
Things to look at
❖ Class imbalance
❖ Dispersion of data attribute values ❖ Skewness, outliers, missing values ❖ Correlation analysis
Visualization tools are important ❖ Histograms, box plots
❖ Scatter plot
Recap: Data Preprocessing
Data transformation might be needed ❖ Handling missing values
❖ Handling categorical variables
❖ Feature transformation
e.g., log transformation
Normalization (back to this when clustering is discussed)
❖ Feature discretization
Which of the following normalization method(s) may transform the original variable to a negative value: min-max, z-score, or both, or neither?
I0，1 score
z training set
Do you apply normalization on training or testing set?
age i25 j income testing set
20，000 gender
age 25 j income 20 ooo gender
mean SDofhainingset todonormalization of testing set
What Induction Algorithm Shall We Use?
Commonly Used Induction Algorithms
Post-mortem analysis of a popular data mining competition
Why Decision Trees?
Decision trees are one of the most popular data mining tools.
❖ Classification trees (used when target variable is categorical)
❖ Regression trees (used when target variable is numeric) They are easy to understand, implement and use, and
computationally cheap.
The model comprehensibility is important for communication to non-DM-savvy stakeholders.
Classification Tree
Thetreeusually wn4
accuracy on havelwg training example
Objective: predicting borrowers who will default on loan payments.
Classification Tree: Upside-Down
Class = Not Default
Class = Not Default
Class = Not Default
Class = Default
Classification Tree: Divide and Conquer
“Recursive Partitioning”
❖ Each node represents one attribute
❖ Tests on nominal attribute: number of splits (branches) is number of possible values or 2 (one value vs. rest)
❖ Continuous attributes are discretized
Yes No Class = Not
Class = Not Default
❖ A class assignment (e.g., default /not default)
❖ Also provide a distribution over all possible classes (e.g., default with probability 0.25, not default with prob. 0.75)
Class = Not Default
Class = Default
How a Tree is Used for Classification ?
To determine the class of a new example: e,g., Mark, age 40, retired, balance 38K.
Yes ❖ The example is routed down the tree Class = Not
according to values of attributes .
❖ At each node, a test is applied to one attribute.
❖ When a leaf is reached, the example is assigned to a class—or alternatively to a distribution over the possible classes (e.g., default with probability 0.25, not default with prob. 0.75).
Class = Not Default
Class = Not Default
Class = Default
Assigning Probability Estimates
Entire Population
Age >=45 Age <45
Age >=45 Age < 45
Balance >= 50k Balance < 50k
Training set
Q: How would you assign estimates of class probability (e.g., probability of default/not default) based on such trees?
Exercise: Assume this is the classification tree you learned from the A Process View to a Business Problem
past defaulting data. A new guy, who is 45 and has 20K balance, is applying a credit card issued by your company. Can you predict if this new guy is gonna default? How confident are you about your prediction? Another girl is also applying the same credit card. But the only information we have about her is she has 70k balance. Can you predict if she will default? How sure about that?
nyfrot Default in
Classification Tree Learning
Objective: based on customer attributes, partition the customers into subgroups that are less impure – with respect to the class (i.e., such that in each group most instances belong to the same class)
Classification Tree Learning
Partitioning into “purer” groups Orange Bodies
Yes Yes Yes
Purple Bodies
Yes Yes No
Classification Tree Learning
Partitioning into “purer” groups recursively Purple Bodies
Classification Tree Learning
Purple Bodies
Classification Tree Learning
Partitioning into “purer” groups Orange Bodies
Yes Yes Yes
Purple Bodies
Yes Yes No
Classification Tree Learning
Partitioning into “purer” groups recursively Orange Bodies
Yes Yes Yes
Yes Yes No
Classification Tree Learning
Orange Bodies
Blue Limbs
Yellow Limbs
Classification Tree Learning
Orange Bodies
Purple Bodies
No No No No
Blue Limbs
Yes Yes Yes
Yellow Limbs
Summary: Classification Tree Learning
A tree is constructed by recursively partitioning the examples.
With each partition, the examples are split into subgroups that are “increasingly pure”.
The Idea of Partitioning
Let’s play a game. I have someone in my mind, and your job is to guess this person. You can only ask yes/no question.
This person is an entrepreneur.
Some important questions without being answered yet:
❖ How to automatically choose which attribute to be used to split the data?
❖ When to stop the splitting?
How to Choose Which Attribute to Split Over?
Objectives
❖ For each splitting node, choose the attribute that best
partitions the population into less impure groups. ❖ All else being equal, fewer nodes is better (more
comprehensible, easy to use, reduce overfitting)
Impurity measures: many available but most common one (from information theory) is: entropy.
is the proportion of class in the data
For example: our initial population is composed of 16 cases
of class “Default” and 14 cases of class “Not default”
Entropy (entire population of examples) =
HighImpurity or
Entropy Exercise
A dataset is composed of 10 cases of class “Positive” and 10 cases of class “Negative”
A 0.5 A dataset is composed of 0
cases of class “Positive” and 20 cases of class “Negative”
𝑡𝑖𝑝: 0 log2 0 = 0
% of one class
Two-class entropy function 28
Information Gain (based on Entropy)
The information gain is based on the reduction in entropy after a dataset is split on an attribute
Information Gain =
entropy (parent) – [weighted average] entropy (children)
where weight of each child is given by the proportion of the examples in that child.
Balance<50k
Balance>=50k
information
Information Gain Example
30 instances
Balance < 50k
Balance >= 50k
Entopywultorly
decrease or noremain unchange aftersplit
17 instances
13 instances
(Weighted) Average Impurity of Children =
Information Gain = 0.997 – 0.615 = 0.382
What If We Split Over “oAge” First? 30 instances
1092告十点以方 15 instances
0，836 Exercise!
15 instances Impurity = ? ogzz
Impurity = ?
0722 十 号 0.836 二0.779
Information Gain = ?
, gain from first splitting on “Balance” = 0.382
Our Original Question
Now, ready to answer anxiously awaiting question:
How to choose which attribute to split over?
Answer: at each node, choose the attribute that obtains maximum information gain!
Decision Tree Algorithm (Full Tree)
❑ Step 1: Calculate the information gain from splitting over each attribute using the dataset
❑ Step 2: Split the set into subsets using the attribute for which
maxliufgainl
❑ Step 3: Make a decision tree node containing that attribute, divide the dataset by its branches and repeat the same process on every node.
❑ Step 4a: A node with entropy of 0, or cannot partition further, or obtain no information gain from additional split, is a leaf.
the information gain is maximum
❑ Step 4b: Otherwise, the node needs further splitting.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com