Decision Trees and Classification Rules

Output Knowledge Representation

• Tables are used to represent knowledge, such as weather data
• Decision tables or regression tables are examples
• Tables may involve selecting a subset of attributes

Output: Linear Model

• Linear models, like CPU performance, can be used
• In binary classification problems, the model produces a line that separates the two classes (decision boundary)
• The line can be compared to a hyperplane in higher dimensions

Trees

• Decision trees are used for knowledge representation (contact lens, labor)
• Nodes test attributes, often by comparisons with constant values
• Leaf nodes provide classifications or probabilities
• Nominal attributes are not usually re-tested while numerical attributes may be re-tested later
• Testing numerical attributes creates two branches (< constant, >= constant), but there is also a third for missing values
• For real-valued data, exact equality is rare
• Intervals are often specified (Above, Within, Below)
• Missing values have their own branches
• Decision trees allow for alternative splits (option nodes)

Decision Trees for Regression

• For numeric outcomes, each leaf node contains the average of training instances reaching that branch (regression tree)
• Regression trees are more complex
• However, generally more accurate than linear equations, especially for non-linear data
• Tree structures are more complex than linear equations, but are usually more accurate for data that aren't perfectly linear
• More complex than linear equations but easier for comprehension

Model Tree

• Combining regression equations and regression trees is possible
• Leaves in a model tree contain linear expressions
• Model trees model continuous functions using linear patches
• Model trees are smaller and easier to understand, often more accurate

Output: Rules

• Antecedents form the conditions (often conjunctions)
• Consequents are classes or probability distributions
• This system includes Classification Rules and Association Rules

Classification Rules

• Classification rules can be derived directly from a decision tree
• Rule sets can be more complex than necessary
• Simplifying the ruleset is possible through pruning
• It isn't always easy to generate a tree from rules

Replicated Subtree Problem

• A decision tree may contain replicated subtrees, leading to inefficiency

Exclusive-Or Problem

• This problem is exemplified by a figure, illustrating patterns of dependent conditional statements

Rules

• Rules are a popular choice due to the independent nature of each new rule
• Individual rules can be added to an existing ruleset without needing to re-structure the entire set
• However, rules may have conflicts, requiring order or a conflict resolution algorithm for an ordered rule set or an unordered rule set, requiring conflict resolution

Unordered Rulesets

• Multiple possible classifications exist for a given example
• A lack of classification or using the most probable outcome from training data
• No classification applies: using the most frequent class

Simple Example

• Boolean classes don't allow conflicts.
• All outcomes are expressed with the assumption of a closed world.

Exceptions

• Fixing rule sets is more complex than expected
• Changing boundaries might re-classify existing examples and some previously good exceptions could be bad exceptions.
• Expert input may be required to identify and fix exceptions
• Exception clauses can be established to adjust rule sets incrementally

More Expressive Rules

• Further examples are presented elsewhere to illustrate more expressive rules

Instance-Based Representation

• Lazy learning vs. eager learning (nearest-neighbor k-value)
• Distance metric (Euclidean distance often used with normalized data)
• Nominal attributes require considerations in the distance metric
• Training instance selection

Instance Selection

• Not all training instances must be stored
• Regions of attribute space are more stable than others
• Fewer samples are needed for stable regions
• More exemplars near class boundaries

IBL (Instance-based Learning)

• Instance-based methods don't explicitly detail the learning structure

Rectangular Regions

• Rectangular regions are similar to rules but often are more conservative

Prototypes

• Nearest-Prototype method(s)
• Using Prototypes instead of Neighbors

Cluster

• When using clustering rather than classification, the output is a diagram showing how instances group.

Multiple Membership

• Instances can belong to more than one cluster.
• Data represented with Venn Diagrams

Probabilities or Fuzzy Memberships

• Clusters can be associated with probabilities or fuzzy membership degrees

Hierarchical Clusters

• Some algorithms implement hierarchical structures
• Showing the hierarchical relationship is often shown with a dendrogram

Clustering

• Clustering operations might be followed by stages that associate instances to clusters using rulesets or decision trees

This quiz explores key concepts related to decision trees and classification rules in machine learning. It covers the specifics of node testing, handling missing values, and the differences between regression trees and linear models. Test your knowledge on how these models are structured and function in various scenarios.