Report

Decision Trees Daisy Guevara Gilberto Jiménez Orlando Ruiz Jan Salomón What is a rooted tree? It is a tree in which one vertex has been designated as the root and every edge is directed away from the root. What are decision trees? It is a rooted tree in which internal vertex correspond to a decision, with a sub-tree at these vertices for each possible outcome of the decision. The possible solution of the problem correspond to the paths to the leaves of this rooted tree. Elements of a Decision Tree The set of decision (or strategies) The set of possible outcomes and/or the probabilities of these outcomes. The results for the various combination and outcomes. Once these elements are known, it is possible to find the “optimal” solution or decision of the problem. Types of Decision Trees Decision Tree Forests Types of Decision Trees Classification and Regression Trees Types of Decision Trees Binary Survival Tree Advantages of Decision Trees Are simple to understand and interpret. Have value even with little hard data. Important insights can be generated based on experts describing a situation (its alternatives, probabilities, and costs) and their preferences for outcomes. Possible scenarios can be added Worst, best and expected values can be determined for different scenarios. Can be combined with other decision techniques. Example: An application of decision trees in Project Management A company named SciTools Incorporated, is invited to make a bid on a government contract. The company with the lower bid obtain the contract. The cost of prepared a bid is the $5,000. The cost of the project is $95,000. The total cost for the company is $100,000. Then, to obtain gain the company has to bid an amount greater than $100,000. The first decision for SciTools is bid or not bid. Bid? Yes No End The second decision for SciTools is how much to bid? Bid? Yes How much to bid? No End SciTools prepared the following analysis: Amount of money in the bid Gain Loss $115,000 $15,000 $5,000 $120,000 $20,000 $5,000 $125,000 $25,000 $5,000 The third decision is consider if there will be other competitors in the bid? Bid? Yes $125k How much to bid? End $115k $120k Any competing bit? Any competing bid? No Any competing bid? The company, based on previous experience believes there is a 30% chance that there will be no competing bids. Bid? Yes How much to bid? $125k No End $115k $120k Any competing bit? 70% Yes Win bid? Any competing bid? 30% No Win 25K 70% Yes Win bid? Any competing bid? 30% No Win $20K 70% Yes Win bid? 30% No Win $15k The fourth decision is to consider the probability to win the bid. Bid? Yes How much to bid? $125k No End $115k $120k Any competing bit? 70% Yes Win bid? Any competing bid? 30% No Win 25K 70% Yes Win bid? Any competing bid? 30% No Win $20K 70% Yes Win bid? 30% No Win $15k SciTools prepared the following analysis: Amount of money in the bid Probability of win the bid Probability of loss the bid $115,000 80% 20% $120,000 40% 60% $125,000 10% 90% The fifth decision is how much SciTools will gain or lose. Bid? Yes How much to bid? $125k No End $115k $120k Any competing bit? 70% Yes 30% No Win bid? 10% Yes Gain $25K Any competing bid? 70% Yes Win 25K 90% No Loss $5K Gain $20k 70% Yes 30% No Win bid? 40% Yes Any competing bid? Win $20K 60% No Loss $5k 30% No Win bid? 80% Yes Gain $15k Win $15k 20% No Loss $5k Example of Heads or Tails Two persons enter in a bid of whom will obtain two heads or two tails. The options are presented in the following decision tree: H H Win H T Toss 1 H T Toss 2 H Win H Toss 3 T H Win T Win H Toss 3 Toss 2 T Win T T Win T Example of Green, Yellow, Red Card Test 1 Test 2 Test 2 Test 3 Quiz Test 3 Quiz Quiz Test 3 Quiz Quiz Test 3 Quiz Quiz Quiz Example of Dinner’s Dilemma A group of friends go out to dinner. They decided before arriving to the restaurant to share the bill. They are expecting to eat better and cheaper than paying individually. Menu Price Mofongo with Lobster $25 Rice and Crab $18 Rice with Meat Stew $12