Unformatted text preview:

Decision Trees Supervised LearningTodayApplication: Medical DiagnosisApplication: Medical DiagnosisApplication: Medical DiagnosisApplication: Medical DiagnosisDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision TreesDecision Tree LearningDecision Tree LearningDecision TreesDecision TreesChoosing the Best AttributeChoosing the Best AttributeChoosing the Best AttributeChoosing the Best AttributeDiscrete ProbabilityDiscrete ProbabilityIndependenceIndependenceIndependenceIndependenceConditional ProbabilityDiscrete Random VariablesExample: Pair of DiceExample: Pair of DiceExample: Pair of DiceDiscrete Random VariablesEntropyEntropy of a Coin FlipConditional EntropyInformation GainDecision Tree LearningChoosing the Best AttributeChoosing the Best AttributeWhen to StopHandling Real-Valued AttributesHandling Real-Valued AttributesHandling Real-Valued AttributesHandling Real-Valued AttributesHandling Real-Valued AttributesHandling Real-Valued AttributesDecision TreesDecision TreesNicholas RuozziUniversity of Texas at DallasBased on the slides of Vibhav Gogate and David SontagSupervised Learning• Input: labeled training data• i.e., data plus desired output• Assumption: there exists a function 𝑓𝑓 that maps data items 𝑥𝑥 to their correct labels• Goal: construct an approximation to 𝑓𝑓2Today• We’ve been focusing on linear separators• Relatively easy to learn (using standard techniques)• Easy to picture, but not clear if data will be separable• Next two lectures we’ll focus on other hypothesis spaces• Decision trees• Nearest neighbor classification3Application: Medical Diagnosis• Suppose that you go to your doctor with flu-like symptoms• How does your doctor determine if you have a flu that requires medical attention?4Application: Medical Diagnosis• Suppose that you go to your doctor with flu-like symptoms• How does your doctor determine if you have a flu that requires medical attention?• Check a list of symptoms:• Do you have a fever over 100.4 degrees Fahrenheit?• Do you have a sore throat or a stuffy nose?• Do you have a dry cough?5Application: Medical Diagnosis• Just having some symptoms is not enough, you should also not have symptoms that are not consistent with the flu• For example,• If you have a fever over 100.4 degrees Fahrenheit?• And you have a sore throat or a stuffy nose?• You probably do not have the flu (most likely just a cold)6Application: Medical Diagnosis• In other words, your doctor will perform a series of tests and ask a series of questions in order to determine the likelihood of you having a severe case of the flu• This is a method of coming to a diagnosis (i.e., a classification of your condition)• We can view this decision making process as a tree7Decision Trees• A tree in which each internal (non-leaf) node tests the value of a particular feature• Each leaf node specifies a class label (in this case whether or notyou should play tennis)8Decision Trees• Features: (Outlook, Humidity, Wind)• Classification is performed root to leaf• The feature vector (Sunny, Normal, Strong) would be classified as a yes instance9Decision Trees• Can have continuous features too• Internal nodes for continuous features correspond to thresholds10Decision Trees• Decision trees divide the feature space into axis parallel rectangles118 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Decision trees divide the feature space into axis parallel rectangles128 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Decision trees divide the feature space into axis parallel rectangles138 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Decision trees divide the feature space into axis parallel rectangles148 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Decision trees divide the feature space into axis parallel rectangles158 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Decision trees divide the feature space into axis parallel rectangles168 7 6 5 4 3210 0 1 2 3 4 5 6 7 8 +++++++−−−−−𝑥𝑥1𝑥𝑥2𝑥𝑥2> 4𝑥𝑥1≤ 6 𝑥𝑥1> 4𝑥𝑥2> 2𝑥𝑥2> 5− ++−+−Decision Trees• Worst case decision tree may require exponentially (in the dimension of the data) many nodes1710 0 1++−−𝑥𝑥1𝑥𝑥2Decision Tree Learning• Basic decision tree building algorithm:• Pick some feature/attribute• Partition the data based on the value of this attribute• Recurse over each new partition18Decision Tree Learning• Basic decision tree building algorithm:• Pick some feature/attribute (how to pick the “best”?)• Partition the data based on the value of this attribute• Recurse over each new partition (when to stop?)We’ll focus on the discrete case first (i.e., each feature takes a value in some finite set)19Decision Trees• What functions can be represented by decision trees?Every function can be represented by a sufficiently complicated decision tree• Are decision trees unique?20Decision Trees• What functions can be represented by decision trees?• Every function of +/- can be represented by a sufficiently complicated decision tree• Are decision trees unique?• No, many different decision trees are possible for the same set of labels21Choosing the Best Attribute• Because the complexity of storage and classification increases with the size of the tree, should prefer smaller trees• Simplest models that explain the data are usually preferred over more complicated ones• Finding the smallest tree is an NP-hard problem• Instead, use a greedy heuristic based approach to pick the best attribute at each


View Full Document

UTD CS 6375 - Decision Trees

Download Decision Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Decision Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Decision Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?