Decision Tree Supervised Learning Chapter 3 PDF
Document Details
Uploaded by Deleted User
Tags
Summary
This document explains decision tree induction, a type of supervised learning algorithm used in machine learning. It covers the concept of breaking down training examples into smaller subsets, how decision trees are constructed. It's a significant data analysis technique in AI applications.
Full Transcript
Decision Tree Decision Tree Decision tree induction is a simple but powerful learning paradigm. In this method a set of training examples is broken down into smaller and smaller subsets while at the same time an associated decision tree get incrementally developed. At the end...
Decision Tree Decision Tree Decision tree induction is a simple but powerful learning paradigm. In this method a set of training examples is broken down into smaller and smaller subsets while at the same time an associated decision tree get incrementally developed. At the end of the learning process, a decision tree covering the training set is returned. The decision tree can be thought of as a set sentences (in Disjunctive Normal Form) written propositional logic(Mitchell 1997, Russell & Norvig 2003). Decision Tree Some characteristics of problems that are well suited to Decision Tree Learning are: Attribute-value paired elements Discrete target function Disjunctive descriptions (of target function) Works well with missing or erroneous training data You want to eat at mang inasal? Mang Inasal Some Full True Wait >60 mins 30-60 mins10-30 mins 0-10 mins Fals Alternat Hungr True e e y Yes No No Yes True Raining Alternat True e Yes No Yes No Fals Raining True True e Yes No Fals True e Expressiveness Decision tree can be express any function of the input attributes. A B A XOR A B F T T T F T F T B B F T T F T F T F F F F T T F Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D1 Rain Mild Normal Weak Yes 0 D1 Sunny Mild Normal Strong Yes 1 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes 3 D1 Rain Mild High Strong No 4 [See: Tom M. Mitchell, Machine Learning, McGraw-Hill, 1997] Attributes: Outlook Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis S = [9+, 5-] 9 9 5 5 D1 Sunny Hot High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− log 2 − log 2 =0.94 14 14 14 14 D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes Sunny = [2+, 3-] D5 Rain Cool Normal Weak Yes 71 D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes Overcast = [4+, 0-] D8 Sunny Mild High Weak No 4 4 0 0 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡 )=− log 2 − log 2 =0 D9 Sunny Cool Normal Weak Yes 4 4 4 4 D1 Rain Mild Normal Weak Yes 0 Rain = [3+, 2-] D1 Sunny Mild Normal Strong Yes 71 1 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes |𝑆𝑣| 3 𝐺𝑎𝑖𝑛 ( 𝑆 ,𝑂𝑢𝑡𝑙𝑜𝑜𝑘 )=Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣 ) D1 Rain Mild High Strong No 𝑣 ∊(𝑆𝑢𝑛𝑛𝑦 , 𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡 , 𝑅𝑎𝑖𝑛) |𝑆| 4 5 4 5 5 4 5 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 )=Entropy ( s ) − Entropy ( SSunny ) − Entropy ( SOvercast ) − Entropy ( SRain ) = 0.94 − 0.971 − 0− 0.971=0.246 7 14 14 14 14 14 14 Attributes: Temp Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis S = [9+, 5-] 9 9 5 5 D1 Sunny Hot High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− log 2 − log 2 =0.94 14 14 14 14 D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes Hot = [2+, 2-] 2 2 2 2 D5 Rain Cool Normal Weak Yes 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐻𝑜𝑡 )= − log 2 − log2 =1.0 4 4 4 4 D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes Mild = [4+, 2-] D8 Sunny Mild High Weak No 4 4 2 2 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑀𝑖𝑙𝑑 ) =− log2 − log2 =0.9183 D9 Sunny Cool Normal Weak Yes 6 6 6 6 D1 Rain Mild Normal Weak Yes 0 Cool = [3+, 1-] D1 Sunny Mild Normal Strong Yes 3 3 1 1 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐶𝑜𝑜𝑙 ) =− log2 − log2 =0. 8113 1 4 4 4 4 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes |𝑆𝑣| 3 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣) D1 Rain Mild High Strong No 𝑣∊ (𝐻𝑜𝑡 ,𝐶𝑜𝑙𝑑 ,𝑀𝑖𝑙𝑑) |𝑆| 4 5 4 5 4 6 4 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =Entropy ( s ) − Entropy ( SHot ) − Entropy ( SCold ) − Entropy ( SMild ) = 0.94 − 1.0 − 0.9183 − 0. 8113=0.0289 14 14 14 14 14 14 Attributes: Humidity Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis S = [9+, 5-] 9 9 5 5 D1 Sunny Hot High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− log 2 − log 2 =0.94 14 14 14 14 D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes High = [3+, 4-] 3 3 4 4 D5 Rain Cool Normal Weak Yes 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆𝑡𝑟𝑜𝑛𝑔 )=− log2 − log2 =0.9852 7 7 7 7 D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes Normal = [6+, 1-] D1 Rain Mild Normal Weak Yes 6 6 1 1 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑊𝑒𝑎𝑘 ) =− log 2 − log 2 =0.5916 0 7 7 7 7 D1 Sunny Mild Normal Strong Yes 1 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes |𝑆𝑣| 3 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣 ) D1 Rain Mild High Strong No 𝑣 ∊(𝑆𝑡𝑟𝑜𝑛𝑔 ,𝑊𝑒𝑎𝑘) |𝑆| 4 7 7 7 7 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =Entropy ( s ) − Entropy ( SHigh ) − Entropy ( SNormal ) = 0.94 − 0.9852 − 0. 5916=0.1516 14 14 14 14 Attributes: Wind Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis S = [9+, 5-] 9 9 5 5 D1 Sunny Hot High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− log 2 − log 2 =0.94 14 14 14 14 D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes Strong = [3+, 3-] 3 3 3 3 D5 Rain Cool Normal Weak Yes 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆𝑡𝑟𝑜𝑛𝑔 )=− log2 − log2 =1.0 3 3 3 3 D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes Weak = [6+, 2-] D1 Rain Mild Normal Weak Yes 6 6 2 2 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑊𝑒𝑎𝑘 ) =− log 2 − log 2 =0.8113 0 8 8 8 8 D1 Sunny Mild Normal Strong Yes 1 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes |𝑆𝑣| 3 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑊𝑖𝑛𝑑 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣 ) D1 Rain Mild High Strong No 𝑣 ∊(𝑆𝑡𝑟𝑜𝑛𝑔 ,𝑊𝑒𝑎𝑘) |𝑆| 4 5 4 6 8 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =Entropy ( s ) − Entropy ( SStrong ) − Entropy ( SWeak ) = 0.94 − 1.0 − 0. 8113=0.0478 14 14 14 14 Decision Tree Learning Day Outlook Temperature Humidity Wind Play Tennis 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 )=0.2464 D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =0.0289 D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =0.1516 D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D1 Rain Mild Normal Weak Yes 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =0.0478 0 D1 Sunny Mild Normal Strong Yes 1 D1 Overcast Mild High Strong Yes 2 D1 Overcast Hot Normal Weak Yes 3 D1 Rain Mild High Strong No 4 [See: Tom M. Mitchell, Machine Learning, McGraw-Hill, 1997] {D1, D2, …, D14} [9+,5-] Outlook Sunny Overcast Overcast {D1, D2, D8, D9, D11} {D3, D7, D8, D12, D13} {D4, D5, D6, D10, D14} [2+, 3-] [4+, 0-] [3+, 2-] ? Yes ? {D1, D2, D8, D9, D11} Attribute: Temp [2+, 3-] Day Tem Humidit Wind Play 2 2 3 3 S = [2+, 3-] 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− log2 − log2 =0.9 7 p y Tenni 5 5 5 5 s Hot = [0+, 2-] D1 Hot High Weak No 0 0 2 2 Mild = [1+, 1-] 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐻𝑜𝑡 )= − log 2 − log2 =0.0 D2 Hot High Strong No 2 2 2 2 Cool = [1+, 0-] D8 Mild High Weak No 1 1 1 1 D9 Cool Normal Weak Yes 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑀𝑖𝑙𝑑 ) =− log 2 − log 2 =1.0 2 2 2 2 D11 Mild Normal Strong Yes 1 1 0 0 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐶𝑜𝑜𝑙 ) =− log 2 − log2 =0.0 1 1 1 1 |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑇𝑒𝑚𝑝 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣) 𝑣∊ (𝐻𝑜𝑡 ,𝐶𝑜𝑙𝑑 ,𝑀𝑖𝑙𝑑) |𝑆| {D1, D2, D8, D9, D11} Attribute: Humidity [2+, 3-] Day Tem Humidit Wind Play S = [2+, 3-] 7 p y Tenni s High = [0+, 3-] D1 Hot High Weak No 0 0 3 3 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆𝑡𝑟𝑜𝑛𝑔 )=− log2 − log2 =0.0 Normal = [2+, 0-] 3 3 3 3 D2 Hot High Strong No D8 Mild High Weak No 0 D9 Cool Normal Weak Yes D11 Mild Normal Strong Yes |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣 ) 𝑣 ∊(𝑆𝑡𝑟𝑜𝑛𝑔 ,𝑊𝑒𝑎𝑘) |𝑆| 3 2 3 2 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =Entropy ( s ) − Entropy ( SHigh) − Entropy ( SNormal ) = 0.97 − 0.0 − 0.0=0. 97 5 5 5 5 {D1, D2, D8, D9, D11} Attribute: Wind [2+, 3-] Day Tem Humidit Wind Play S = [2+, 3-] 7 p y Tenni s Strong = [1+, 1-] 1 1 1 1 D1 Hot High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆𝑡𝑟𝑜𝑛𝑔 )=− log2 − log2 =1.0 Weak = [1+, 2-] 1 1 1 1 D2 Hot High Strong No D8 Mild High Weak No 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑊𝑒𝑎𝑘 ) =− 1 1 2 2 log 2 − log 2 =0.9183 3 3 3 3 D9 Cool Normal Weak Yes D11 Mild Normal Strong Yes |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 , 𝑊𝑖𝑛𝑑 ) =Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣 ) 𝑣 ∊(𝑆𝑡𝑟𝑜𝑛𝑔 ,𝑊𝑒𝑎𝑘) |𝑆| {D1, D2, D8, D9, D11} [2+, 3-] Day Tem Humidit Wind Play p y Tenni s 𝐺𝑎𝑖𝑛 ( 𝑆 𝑠𝑢𝑛𝑛𝑦 , 𝑇𝑒𝑚𝑝 ) =0.570 D1 Hot High Weak No D2 Hot High Strong No 𝐺𝑎𝑖𝑛 ( 𝑆 𝑠𝑢𝑛𝑛𝑦 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 ) =0.97 D8 Mild High Weak No D9 Cool Normal Weak Yes 𝐺𝑎𝑖𝑛 ( 𝑆 𝑠𝑢𝑛𝑛𝑦 , 𝑇𝑒𝑚𝑝 ) =0.0192 D11 Mild Normal Strong Yes {D1, D2, …, D14} [9+,5-] Outlook Sunny Overcast Rain {D1, D2, D8, D9, D11} {D3, D7, D8, D12, D13} {D4, D5, D6, D10, D14} [2+, 3-] [4+, 0-] [3+, 2-] Humidity Yes ? High Normal {D1, D2, D8} {D9, D11} No Yes {D1, D2, D8, D9, D11} Attribute: Temp [2+, 3-] Day Tem Humidit Wind Play SRain = [3+, 2-]𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− 3 log2 3 − 2 log2 2 =0.9 7 p y Tenni 5 5 5 5 s Hot = [0+, 0-] D4 Mild High Weak Yes 0 0 0 0 Mild = [2+, 1-] 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐻𝑜𝑡 )= − log 2 − log2 =0.0 D5 Cool Normal Weak Yes 0 0 0 0 Cool = [1+, 1-] D6 Cool Normal Strong No 2 2 1 1 D10 Mild Normal Weak Yes 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑀𝑖𝑙𝑑 ) =− log 2 − log 2 =0.9183 3 3 3 3 D14 Mild High Strong No 1 1 1 1 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝐶𝑜𝑜𝑙 ) =− log 2 − log2 =1.0 1 1 1 1 |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 𝑅𝑎𝑖𝑛 ,𝑇𝑒𝑚𝑝 )=Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣) 𝑣 ∊ (𝐻𝑜𝑡 ,𝐶𝑜𝑙𝑑, 𝑀𝑖𝑙𝑑) |𝑆| {D1, D2, D8, D9, D11} Attribute: Humidity [2+, 3-] Day Tem Humidit Wind Play SRain = [3+, 2-] 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− 3 log2 3 − 2 log2 2 =0.9 7 p y Tenni 5 5 5 5 s High= [1+, 1-] D4 Mild High Weak Yes ( 𝐻 𝑖𝑔h ) =1.0 Normal = [2+,𝐸𝑛𝑡𝑟𝑜𝑝𝑦 1-] D5 Cool Normal Weak Yes D6 Cool Normal Strong No 2 2 1 1 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑁𝑜𝑟𝑚𝑎𝑙 ) =− log2 − log 2 =0.9183 D10 Mild Normal Weak Yes 3 3 3 3 D14 Mild High Strong No |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 𝑅𝑎𝑖𝑛 ,𝑇𝑒𝑚𝑝 )=Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣) 𝑣 ∊ (𝐻𝑜𝑡 ,𝐶𝑜𝑙𝑑, 𝑀𝑖𝑙𝑑) |𝑆| {D1, D2, D8, D9, D11} Attribute: Wind [2+, 3-] Day Tem Humidit Wind Play SRain = [3+, 2-] 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 ( 𝑆 )=− 3 log2 3 − 2 log2 2 =0.9 7 p y Tenni 5 5 5 5 s Weak= [0+, 2-] D4 Mild High Weak Yes ( 𝐻 𝑖𝑔h ) =0.0 Strong = [3+,𝐸𝑡𝑟𝑜𝑝𝑦 0-] D5 Cool Normal Weak Yes D6 Cool Normal Strong No 𝐸𝑡𝑟𝑜𝑝𝑦 ( 𝑆𝑡𝑟𝑜𝑛𝑔 )=0.0 D10 Mild Normal Weak Yes D14 Mild High Strong No |𝑆𝑣| 𝐺𝑎𝑖𝑛 ( 𝑆 𝑅𝑎𝑖𝑛 ,𝑇𝑒𝑚𝑝 )=Entropy (s) − ∑ 𝐸𝑛𝑡𝑟𝑜𝑝h𝑦 (𝑆𝑣) 𝑣 ∊ (𝐻𝑜𝑡 ,𝐶𝑜𝑙𝑑, 𝑀𝑖𝑙𝑑) |𝑆| {D1, D2, D8, D9, D11} Attribute: Wing [2+, 3-] Day Tem Humidit Wind Play p y Tenni s 𝐺𝑎𝑖𝑛 ( 𝑆 𝑅𝑎𝑖𝑛 ,𝑇𝑒𝑚𝑝 )=0.0192 D4 Mild High Weak Yes D5 Cool Normal Weak Yes 𝐺𝑎𝑖𝑛 ( 𝑆 𝑅𝑎𝑖𝑛 , 𝐻𝑢𝑚𝑖𝑑𝑖𝑡𝑦 )=0.0192 D6 Cool Normal Strong No D10 Mild Normal Weak Yes 97 D14 Mild High Strong No {D1, D2, …, D14} [9+,5-] Outlook Sunny Overcast Rain {D1, D2, D8, D9, D11} {D3, D7, D8, D12, D13} {D4, D5, D6, D10, D14} [2+, 3-] [4+, 0-] [3+, 2-] Humidity Yes Wind High Normal Weak Strong {D1, D2, D8} {D9, D11} {D6, D14} {D4, D5, D10} No Yes No Yes
