Decision Trees in Data Mining

Study Notes

A decision tree is a structured flowchart where internal nodes represent tests on attributes, branches denote outcomes, and leaf nodes indicate class labels.
Serves as a supervised learning approach for classification and regression tasks.
Facilitates decision-making by creating models that separate datasets into smaller subsets.
Allows handling of both categorical and numerical data.
Nodes can be classified as decision nodes, with at least two branches, and leaf nodes representing outcomes or classifications.

No domain knowledge required: Can be applied across various domains.
Ease of comprehension: Visual representation makes it accessible for experts and novices alike.
Simple learning and classification: Efficient processes yield quick results.

The ID3 algorithm, developed by J. Ross Quinlan in 1980, is the foundational algorithm for decision trees.
C4.5 is a successor to ID3, adopting a greedy approach for tree construction without backtracking.
Builds trees recursively through a top-down divide-and-conquer strategy based on parameters like data partition, attribute list, and attribute selection method.
Attributes can be selected using measures like information gain or Gini index, which influence binary structure outcomes.

The time complexity for growing a decision tree is O(n × |D| × log(|D|)), where n is the number of attributes and |D| is the number of tuples in the training set.
Incremental decision tree versions restructure based on new data without needing to rebuild from scratch.

Understanding and interpretation: Decision trees present a clear model for both experts and non-experts.
Data versatility: Capable of integrating numerical and categorical data types.
Handling large datasets: Can accommodate extensive data and adapt to new information.
Classification and regression: Applicability in predicting both discrete and continuous outcomes.

Overfitting risk: Complexity may hinder generalization to unseen data, leading to performance issues.
Data sensitivity: Minor data changes can significantly alter the structure of the tree.
Attribute bias: Preference towards attributes with numerous levels; may perform poorly with attributes that have fewer levels.

Attribute selection determines how training tuples are split into classes, ranking attributes for effective partitioning.
Key measures include:
- Entropy
- Information Gain
- Gain Ratio
Some measures allow for multi-way splits, enhancing tree versatility.

If a dataset contains tuples of the same class, the node becomes a leaf labeled with that class.
If the class is not uniform, the algorithm employs attribute selection to identify the best splitting criterion.
This criterion helps to define the attribute to test, the nature of the branches, and aims for partitions that are as pure as possible.
Continuous attributes create branches based on split points, while discrete values lead to branches based on known values.