CS361(Artificial Intelligence) Lecture 7 Supervised Machine Learning: Decision Trees via ID3 Dr. Hala Abdel-Galil & Dr. Amr S. Ghoneim (Computer Science Dept.) Helwan University Fall 2019 Lecture is based on its counterparts in the following courses: o Applied Machine Learning, University of Pennsylvania (School of Engineering and Applied Science)
Today’s Key Concepts o Machine Learning o Classical Supervised Machine Learning o Why use learning? o Supervised Learning: Training & Testing o Decision Trees (the ID3 algorithm; a Greedy heuristic – based on information gain – originally developed for discrete features) o Decision Trees: An Introduction o Basic Decision Trees Learning Algorithm o Picking the Root Attribute: Entropy & Information Gain o Which feature to split on? o An Illustrative Example o Decision Trees Induction o Weka; the Waikato Environment for Knowledge Analysis (Machine Learning Software in Java) o An Application to Business Intelligence o What is Business Intelligence (BI) & Business Analytics (BA) .. ? o Why BI? .. Business Management Issues o A Framework for Business Intelligence (BI’s Architecture & Components) o A Case Study: The German Credit Data Analysis (Statlog Dataset)
Machine Learning? {A r t i f i c i a l I n t e l l i g e n c e} M a c h i n e L e a r n i n g M a p 3
Supervised Learning Input Output 𝒙 ∈ 𝑿 System 𝑦 ∈ 𝒀 An item 𝒙 𝑦 = 𝑓(𝒙) An item 𝑦 drawn from an drawn from an input space 𝑿 output space 𝒀 We consider systems that apply a function 𝒇( ) to input items x and return an output 𝒚 = 𝒇(𝒙).
Supervised Learning Input Output 𝒙 ∈ 𝑿 System 𝑦 ∈ 𝒀 An item 𝒙 𝑦 = 𝑓(𝒙) An item 𝑦 drawn from an drawn from an input space 𝑿 output space 𝒀 In (supervised) machine learning, we deal with systems whose 𝒇(𝒙) is learned from examples.
Why use learning? We typically use machine learning when the function 𝒇(𝒙) we want the system to apply is unknown to us, and we cannot “think” about it. The function could actually be simple.
Supervised Learning Input Output Target function 𝑦 = 𝑓(𝒙) 𝒙 ∈ 𝑿 Learned Model 𝑦 ∈ 𝒀 𝑦 = 𝑔(𝒙) An item 𝒙 An item 𝑦 drawn from an drawn from a instance space 𝑿 label space 𝒀
Supervised learning: Training o Give the learner examples in 𝑫𝒕𝒓𝒂𝒊𝒏. o The learner returns a model 𝐠 𝒙 . Labeled Training Data 𝑫𝒕𝒓𝒂𝒊𝒏 Learned (𝒙 ,𝑦 ) Learning 1 1 model (𝒙 ,𝑦 ) Algorithm 2 2 𝑔(𝒙) … (𝒙𝑁,𝑦𝑁) 𝒈(𝒙) is the model we’ll use in our application
Supervised learning: Testing o Reserve some labeled data for testing Labeled Test Data Raw Test 𝑫𝑡𝑒𝑠𝑡 Test Data (𝒙’ ,𝑦’ ) Labels 1 1 𝑿𝑡𝑒𝑠𝑡 (𝒙’ ,𝑦’2) 𝒀𝑡𝑒𝑠𝑡 2 𝒙’1 … 𝑦’1 𝒙’2 (𝒙’ ,𝑦’ ) 𝑦’2 𝑀 𝑀 … ... 𝒙’𝑀 𝑦’ 𝑀
Supervised learning: Testing o Apply the model to the raw test data. o Evaluate by comparing predicted labels against the test labels. Raw Test Predicted Test Data Labels Labels 𝑿𝑡𝑒𝑠𝑡 Learned 𝑔(𝑿𝑡𝑒𝑠𝑡) 𝒀𝑡𝑒𝑠𝑡 𝒙’ model 𝑔(𝒙’ ) 𝑦’1 1 1 𝒙’ 𝑔(𝒙) 𝑔(𝒙’ ) 𝑦’2 2 2 … … … 𝒙’ 𝑔(𝒙’ ) 𝑦’𝑀 𝑀 𝑀
Representing Data Think about a large table, N attributes, and assume you want to know something about the people represented as entries in this table. E.g. own an expensive car or not. o Simplest way: Histogram on the first attribute – own o Then, histogram on first and second (own & gender) But, what if the # of attributes is larger: N=16 o How large are the 1-d histograms (contingency tables)? .. 16 numbers o How large are the 2-d histograms?.. 16-choose-2 = 120 numbers o How large are the 3-d tables? .. 560 numbers o With 100 attributes, the 3-d tables need 161,700 numbers - We need to figure out a way to represent data in a better way, and figure out what are the important attributes to look at first. - Information theory has something to say about it – we will use it to better represent the data.
Decision Trees o A hierarchical data structure that represents data by implementing a divide and conquer strategy. o Given a collection of examples, learn a decision tree that represents it. o Use this representation to classify new examples. C B A
The Representation Decision Trees are classifiers for instances represented as feature vectors color={red, blue, green}; shape={circle, triangle, rectangle}; label= {A, B, C} o Nodes are tests for feature values o There is one branch for each value of the feature o Leaves specify the category (labels) o Can categorize instances into multiple disjoint categories Color C B A Shape B Shape B A C B A
Decision Trees o Can represent any Boolean Function. o Can be viewed as a way to compactly represent a lot of data. o The evaluation of the Decision Tree Classifier is easy. o Clearly, given data, there are many ways to represent it as a decision tree. o Learning a good representation from data is the challenge. Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes
Will I play tennis today? Features Outlook: { Sun, Overcast, Rain } Temperature: { Hot, Mild, Cool } Humidity: { High, Normal, Low } Wind: { Strong, Weak } Labels Binary classification task: Y = {+, -}
Will I play tennis today? O T H W Play? 1 S H H W - 2 S H H S - Outlook: S(unny), O(vercast), 3 O H H W + R(ainy) 4 R M H W + 5 R C N W + Temperature: H(ot), M(edium), 6 R C N S - C(ool) 7 O C N S + 8 S M H W - Humidity: H(igh), 9 S C N W + N(ormal), L(ow) 10 R M N W + 11 S M N S + Wind: S(trong), 12 O M H S + W(eak) 13 O H N W + 14 R M H S -
Basic Decision Trees Learning Algorithm O T H W Play? 1 S H H W - o Data is processed in Batch (i.e. all the 2 S H H S - data available) 3 O H H W + o Recursively build a decision tree top 4 R M H W + down. 5 R C N W + 6 R C N S - Outlook 7 O C N S + 8 S M H W - Rain Sunny Overcast 9 S C N W + Humidity Wind Yes 10 R M N W + 11 S M N S + High Normal Strong Weak No Yes No Yes 12 O M H S + 13 O H N W + 14 R M H S -
Basic Decision Tree Algorithm Let S be the set of Examples Label is the target attribute (the prediction) Attributes is the set of measured attributes ID3(S, Attributes, Label) If all examples are labeled the same return a single node tree with Label Otherwise Begin A = attribute in Attributes that best classifies S (Create a Root node for tree) for each possible value v of A Add a new tree branch corresponding to A=v Let Sv be the subset of examples in S with A=v if Sv is empty: add leaf node with the common value of Label in S Else: below this branch add the subtree ID3(Sv, Attributes - {a}, Label) End Return Root
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!