Decision Tree Classification

• Focus is on classification using decision trees and their induction.

Classification

• Predicts categorical class labels.
• Classifies data by constructing a model based on training sets and class labels.
• Model is then used to classify new data.
• Categorizes, for example, bank loan applications as either safe or risky.

Numeric Prediction

• Models continuous-valued functions.
• Predicts unknown or missing values, like predicting potential customer expenditures on computer equipment based on income and occupation.

Typical Applications

• Credit approval
• Target marketing
• Medical diagnosis
• Treatment effectiveness analysis

Classification Process (Two-Step)

• Step 1: Model construction.
• Each tuple/sample belongs to a predefined class determined by the class label attribute.
• The training set is the set of tuples used for model construction.
• Training samples are the individual tuples making up the training set.
• Supervised learning involves learning the model with a given training set.
• The learned model is represented by classification rules, decision trees, or mathematical formulae.
• Step 2: Model usage.
• The model is used to classify future or unseen objects.
• Model accuracy is estimated by comparing the known label of a test sample with the model's classified result.
• Accuracy rate is the percentage of test set samples correctly classified.
• The test set must be independent of the training set to avoid over-fitting.
• If the accuracy is acceptable, the model is used to classify future data tuples with unknown class labels.

Supervised Learning

• Training data includes labels indicating the class of observations.
• New data is classified based on this training set.

Unsupervised Learning

• Class labels of training data are unknown.
• Aims to establish the existence of classes or clusters in the data using measurements and observations.

Issues in Classification and Prediction (1): Data Preparation

• Data cleaning: Preprocessing to reduce noise and handle missing values.
• Relevance analysis (feature selection): Removing irrelevant or redundant attributes to improve efficiency and scalability.
• Data transformation: Generalizing data to higher-level concepts and normalizing it when distance measurements are involved.

Issues in Classification and Prediction (2): Evaluating Classification Methods

• Predictive accuracy
• Speed and scalability (time to construct and use the model)
• Robustness (handling noise and missing values)
• Scalability (efficiency in disk-resident databases)
• Interpretability (understanding and insight provided by the model)
• Goodness of rules (decision tree size, compactness of classification rules)

Classification by Decision Tree Induction

• Decision tree: A flow-chart-like tree structure.
• Internal node: Denotes a test on an attribute.
• Branch: Represents an outcome of the test.
• Leaf nodes: Represent class labels or class distribution.
• Uses attribute values of a sample against the decision tree to classify it.

Decision Tree Induction

• Automatically discovers a decision tree from data.
• Tree construction: All training examples are at the root and partitioned recursively based on selected attributes.
• Tree pruning: Identifies and removes branches that reflect noise or outliers.
• The basic algorithm is a greedy, top-down, recursive divide-and-conquer approach.
• Partitioned recursively based on selected attributes and the attributes are categorical or discretized in advance.
• The recursive partitioning stops when all samples for a given node belong to the same class, there are no remaining attributes to partition on, or there are no samples for the branch.

Decision Tree Algorithm

• If all samples are the same class, the node becomes a leaf labeled with that class.
• Otherwise, use a statistical measure like information gain to select the attribute that best separates samples, making it the test or decision attribute.
• A branch is created for each known value of the test attribute and samples are partitioned, and after an attribute at a node it need not be considered again.

Algorithm Conditions

• The recursive partitioning stops when :
  • All samples for a given node belong to the same class.
  • There are no remaining attributes on which to partition; majority voting is employed.
  • There are no samples for the branch; a leaf is created with the majority class in samples.

Information Gain (ID3/C4.5)

• Entropy function measures the degree of diversity.
• The information gain measures the encoding information that would be gained by branching on A, calculated as Gain(A) = I(p,n) – E(A).
• The attribute with the highest information gain is chosen as the test attribute.

Gain Ratio

• Gain Ratio is a successor to ID3 and overcomes the bias of information gain.
• Normalizes information gain using a 'split information’ value, representing potential information generated by the training dataset.
• The attribute with the maximum gain ratio is selected as the splitting attribute, and the gain ratio considers the number of tuples having that outcome with respect to the total number of tuples
• SplitInfo(D) = - Σ (|Dj|/|D|) * log2(|Dj|/|D|).
• Where Dj contains those tuples in D, corresponding to the v outcomes of a test on attribute A

Extracting Classification Rules from Trees

• Represent knowledge in IF-THEN rules, with one rule per path from root to leaf.
• Each attribute-value pair along a path forms a conjunction, and the leaf node holds the class prediction, making rules easier for humans to understand.

Classification in Large Databases

• Decision tree induction in data mining is used to solve the scaling problem
• It is relatively faster, can be converted to simple rules, and has comparable classification accuracy.