module_4 complete module_4 completmodule_4 complet (1).pptx

module_4 completmodule_4 completmodule_4 completmodule_4 completmodule_4 completmodule_4 completmodule_4 complet

1. MODULE - 4 DECISION TREE LEARNING

2. Decision tree learning is a supervised predictive learning model, classifies data instances with high accuracy. The model performs inductive inference that reaches a general conclusion from observed examples. Used for complex classification applications. Decision tree is a concept tree which summarizes the information contained in the training dataset in the form of a tree structure. Once the concept model is built, test data can be easily classified. 2

3. DECISION TREE REPRESENTATION F I G U R E: A decision tree for the concept PlayTennis . An example is classified by sorting it through the tree to the appropriate leaf node, then returning the classification associated with this leaf 8

4. 11 Decision trees represent a disjunction of conjunctions of constraints on the attribute values of instances. Each path from the tree root to a leaf corresponds to a conjunction of attribute tests, and the tree itself to a disjunction of these conjunctions For example, The decision tree shown in above figure corresponds to the expression (Outlook = Sunny ∧ Humidity = Normal) ∨ ∨ (Outlook = Overcast) (Outlook = Rain ∧ Wind = Weak)

5. 13 THE BASIC DECISION TREE LEARNING ALGORITHM Mos t a lg o rith m s that have b een dev e loped for lear n ing de c ision trees are variations on a core algorithm that employs a top-down, greedy search through the space of possible decision trees. This approach is exemplified by the ID3 algorithm and its successor C4.5

6. ENTROPY MEASURES HOMOGENEITY OF EXAMPLES Entropy measures the impurity of a collection of examples. It is the amount of uncertainty or randomness in the outcome of a random variable or an event. Given a collection S, containing positive and negative examples of some target concept, the entropy of S relative to this Boolean classification is Where, p + is the proportion of positive examples in S p - is the proportion of negative examples in S. 14

7. Example: Entropy Suppose S is a collection of 14 examples of some boolean concept, including 9 positive and 5 negative examples. Then the entropy of S relative to this boolean classification is 15

8. 16 The entropy is 0 if all members of S belong to the same class The entropy is 1 when the collection contains an equal number of positive and negative examples If the collection contains unequal numbers of positive and negative examples, the entropy is between 0 and 1

9. 18

10. 21 What is the ID3 algorithm? ID3 stands for Iterative Dichotomiser 3 ID3 is a precursor to the C4.5 Algorithm. The ID3 algorithm was invented by Ross Quinlan in 1975 Used to generate a decision tree from a given data set by employing a top-down, greedy search, to test each attribute at every node of the tree. The resulting tree is used to classify future samples.

11. 23 ID3 algorithm

12. 24 Which Attribute Is the Best Classifier? The central choice in the ID3 algorithm is selecting which attribute to test at each node in the tree. A st a tis t ic a l property c al l ed inf o r m a t i on g a in that m easures how w e ll a g iven attribute separates the training examples according to their target classification. ID3 uses information gain measure to select among the candidate attributes at each step while growing the tree.

13. INFORMATION GAIN MEASURES THE EXPECTED REDUCTION IN ENTROPY Information gain, is the expected reduction in entropy caused by partitioning the examples according to this attribute. The infor m ation g a in, Gain( S, A ) of an attri b ute A , rel a tive to a c o ll e c t i on of examples S, is defined as 25

14. 26 Example: Information gain Let, Values ( Wind ) = { Weak , Strong } S S Weak S St r ong = [9+, 5−] = [6+, 2−] = [3+, 3−] Information gain of attribute Wind : Gain ( S , Wind ) = Entropy ( S ) − 8/14 Entropy ( S Weak ) − 6/14 Entropy ( S Strong ) = 0.94 – (8/14)* 0.811 – (6/14) *1.00 = 0.048

15. ID3 Algorithm — Purpose and Role ID3 is used in machine learning to: 🔹 1. Classify Data Using Decision Trees ID3 creates a decision tree that can be used to classify new instances by following the path from the root to a leaf node based on feature values. 🔹 2. Learn from Examples It learns patterns from labeled training data (supervised learning). Example: Given data about weather conditions, ID3 can learn to decide whether to play tennis. 🔹 3. Select Features Based on Information Gain It uses information gain (based on entropy) to choose the best feature to split the data at each step. The goal is to maximize purity in child nodes (i.e., group similar labels together). 🔹 4. Produce a Readable Model The output is a human-understandable decision tree structure, useful for interpretation and explanation.

16. Example Use Cases Medical diagnosis (e.g., classifying disease presence based on symptoms) Loan approval systems Spam detection Customer segmentation

17. What is Information Gain? Information Gain (IG) is a metric used to decide which feature to split the data on when building a decision tree (like in the ID3 algorithm). It measures how much “information” a feature gives us about the target variable . Purpose of Information Gain: To select the attribute that best splits the data into pure subsets (i.e., subsets where most or all samples belong to the same class). Formula:

18. What is Entropy ? Entropy is a measure of impurity , uncertainty , or disorder in a dataset. It is used in decision tree algorithms like ID3 , C4.5 , etc., to quantify the heterogeneity of a dataset. Entropy Formula :

19. Entropy Formula:

20. 44 An Illustrative Example To illustrate the operation of ID3, consider the learning task represented by the training examples of below table. Here t h e ta r get a ttrib ut e Pl a y T ennis , w h ich c an have v al ues yes o r n o f o r different days. Consider the first step through the algorithm, in which the topmost node of the decision tree is created.

21. 45 Day Outlook Temperature Humidity Wind PlayTennis 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 D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No

22. ID3 determines the information gain for each candidate attribute (i.e., Outlook, Temperature, Humidity, and Wind), then selects the one with highest information gain 46

23. 49 = 0.246 = 0.151 = 0.048 The information gain values for all four attributes are Gain(S, Outlook) Gain(S, Humidity) Gain(S, Wind) Gain(S, Temperature) = 0.029 According to the information gain measure, the Outlook attribute provides the best prediction of the target attribute, PlayTennis , over the training examples. Therefore, Outlook is selected as the decision attribute for the root node, and branches are created below the root for each of its possible values i.e., Sunny, Overcast, and Rain.

24. 50

25. S Rain = { D4, D5, D6, D10, D14} Gain (S Rain , Humidity) = 0.970 – (2/5)1.0 – (3/5)0.917 = 0.019 Gain (S Rain , Temperature) = 0.970 – (0/5)0.0 – (3/5)0.918 – (2/5)1.0 = 0.019 Gain (S Rain , Wind) = 0.970 – (3/5)0.0 – (2/5)0.0 = 0.970 51

26. 53

27. C4.5 CONSTRUCTION

28. C4.5

29. Validation and Pruning

30. PRUNING Using the number of instances classified correctly and instances classified wrongly Average Squad Error

31. BAYESIAN LEARNING

32. CAR THEFT classify a Red Domestic SUV is getting stolen or not

33. Since 0.144 > 0.048, Which means given the features RED SUV and Domestic, our example gets classified as ’NO’ the car is not stolen.

34. Step -1