Unit 3: Classification & Prediction

A Decision Tree is a supervised learning algorithm that splits data into subsets using attribute tests, building a tree structure of decisions. Each internal node tests an attribute, each branch represents an outcome, and each leaf holds a class label.

Tree Building Algorithms

• ID3 (Iterative Dichotomiser 3): Uses Information Gain to select the best splitting attribute at each node. Works only with categorical attributes.
• C4.5 (successor to ID3): Uses Gain Ratio (normalizes Information Gain). Handles continuous attributes by finding optimal split thresholds and missing values.
• CART (Classification and Regression Trees): Uses Gini Index for splitting. Produces binary trees (two branches per node).

Pruning

• Pre-pruning (early stopping): Stop growing the tree before it perfectly classifies training data (max depth, min samples per leaf).
• Post-pruning: Grow the full tree first, then remove branches that don't improve validation accuracy.

Naive Bayes is a probabilistic classifier based on Bayes' Theorem with the "naive" assumption that features are conditionally independent given the class label.

Handling Text Data

• Bag-of-Words (BoW): Represents text as word frequency vectors, ignoring grammar and word order.
• TF-IDF: Weighs words by importance: TF (term frequency) × IDF (inverse document frequency).
• Laplace Smoothing: Adds +1 to all word counts to avoid zero probabilities for unseen words. P(w|class) = (count(w) + 1) / (total_words + vocabulary_size).

k-NN is an instance-based (lazy) learning algorithm that classifies a new data point based on the majority class of its k nearest neighbors in the training set. No model is built during training — all computation happens at prediction time.

Key Considerations

• k Selection: Small k (e.g., 1) captures noise; large k smooths boundaries. Use cross-validation to find optimal k.
• Feature Normalization: Critical because distance metrics are scale-sensitive. Min-Max or Z-score normalization is essential.
• Lazy Learning: No training phase — stores all data and classifies at query time. Fast to train but slow to predict.
• Curse of Dimensionality: Distance metrics become less meaningful in high dimensions. Dimensionality reduction helps.

Rule-Based Classifiers use IF-THEN rules to classify data. Each rule is a conjunction of conditions (IF) leading to a class prediction (THEN).

Rule Structure

• Rule: IF (condition₁ AND condition₂ AND ...) THEN class.
• Coverage: Number of instances satisfying the rule's conditions (antecedent).
• Accuracy: Proportion of covered instances that belong to the predicted class.

Rule Generation Methods

• Sequential Covering: Learn one rule at a time, remove covered instances, repeat until no instances remain.
• RIPPER (Repeated Incremental Pruning): Optimizes rules by growing and pruning sequentially.
• Decision Tree to Rules: Convert each root-to-leaf path into a rule (one rule per leaf).

Evaluating classification models requires metrics beyond simple accuracy, especially with imbalanced datasets.

Confusion Matrix

• True Positive (TP): Correctly predicted positive.
• True Negative (TN): Correctly predicted negative.
• False Positive (FP): Incorrectly predicted positive (Type I error).
• False Negative (FN): Incorrectly predicted negative (Type II error).

Cross-Validation

• Holdout Method: Split data into training (70%) and test (30%) sets. Simple but depends on the split.
• k-Fold Cross-Validation: Split data into k folds. Train on k-1 folds, test on 1. Repeat k times and average results. Most common: k=5 or k=10.
• Leave-One-Out (LOO): k = n (number of instances). Each instance is tested once. Computationally expensive.