Data Mining Algorithms for Classification

Overview of Data Mining Activities

• Optimization Techniques:

  • GA (Genetic Algorithms)

  • PSO (Particle Swarm Optimization)

  • D/E (Differential Evolution)

  • EDA (Estimation of Distribution Algorithms)

  • ES (Evolutionary Strategies)

• Pre-processing Stages:

  • Normalization

  • Feature selection

  • Handling missing data

  • Outliers identification and management

  • PCA (Principal Component Analysis)

  • Signal-to-noise ratio assessment

• Modelling and Learning Algorithms:

  • Naive Bayes

  • KNN (k-Nearest Neighbors) and wkNN (weighted k-Nearest Neighbors)

  • Decision Trees

  • Linear Regression

  • Neural Networks

  • k-means clustering

  • Association Rules

• Evaluation and Performance Metrics:

  • Cross-validation techniques

  • Metrics in classification

  • Metrics in regression

  • Significance tests

Na ive Bayes Classification

• Foundational Principles:

  • Uses the Bayes theorem for reasoning and statistical inference.

  • Each data feature contributes to a "portfolio of evidence" for classification.

  • Independence Assumption: Assumes that all data features are statistically independent of each other. While this is rarely true in real-world data, the algorithm remains effective.

• Mathematical Representation of Independence:

  • Under the assumption that evidence $E_1, E_2, E_3$ are independent given hypothesis $H$:

  • $Pr(E_1, E_2, E_3|H) = Pr(E_1|H) \times Pr(E_2|H) \times Pr(E_3|H)$

• Credit Scoring Example (Applied Na ive Bayes):

  • Variables and Counts:

    • Debt: High (Good Risk: 1, Poor Risk: 1); Low (Good Risk: 1, Poor Risk: 2).

    • Income: High (Good Risk: 2, Poor Risk: 1); Low (Good Risk: 0, Poor Risk: 2).

    • Married: Yes (Good Risk: 2, Poor Risk: 2); No (Good Risk: 0, Poor Risk: 1).

    • Total Counts: Good Risk (GR) = 2, Poor Risk (PR) = 3.

  • Probabilities:

    • $Pr(D = H|GR) = 0.50$, $Pr(D = H|PR) = 0.33$

    • $Pr(D = L|GR) = 0.50$, $Pr(D = L|PR) = 0.67$

    • $Pr(I = H|GR) = 1.00$, $Pr(I = H|PR) = 0.33$

    • $Pr(I = L|GR) = 0.00$, $Pr(I = L|PR) = 0.67$

    • $Pr(MS = Y|GR) = 1.00$, $Pr(MS = Y|PR) = 0.67$

    • $Pr(MS = N|GR) = 0.00$, $Pr(MS = N|PR) = 0.33$

• Classification for "Joe" (High Debt, High Income, Married):

  • $Pr(GR|Joe) = \frac{Pr(D = H|GR) \times Pr(I = H|GR) \times Pr(MS = Y|GR) \times Pr(GR)}{Pr(E)}$

  • $Pr(GR|Joe) = \frac{0.5 \times 1.0 \times 1.0 \times 0.4}{Pr(E)}$

  • $Pr(PR|Joe) = \frac{Pr(D = H|PR) \times Pr(I = H|PR) \times Pr(MS = Y|PR) \times Pr(PR)}{Pr(E)}$

  • $Pr(PR|Joe) = \frac{0.33 \times 0.33 \times 0.67 \times 0.6}{Pr(E)}$

  • Result: Since $Pr(GR|Joe) > Pr(PR|Joe)$, Joe is classified as "Good Risk."

• Sample Predicted vs. Actual Risk:

  • Joe: Predicted Good (0.82), Actual Good.

  • Sue (Low Debt, High Income, Married): Predicted Good (0.69), Actual Good.

  • John (Low Debt, High Income, No Marriage): Predicted Poor (1.0), Actual Poor.

  • Mary (High Debt, Low Income, Married): Predicted Poor (1.0), Actual Poor.

  • Fred (Low Debt, Low Income, Married): Predicted Poor (1.0), Actual Poor.

Advanced Na ive Bayes Concepts

• Laplace Correction:

  • Problem: If no training samples exist for a specific feature value in a class, the probability becomes 0, zeroing out the entire calculation regardless of other evidence.

  • Solution: Use the Laplace correction formula:

  • $Pr(X=x|C=c) = \frac{count(x_c) + 1}{count(c) + n}$, where $n$ represents the number of possible values for the attribute (simplified as $+1$ in some contexts to ensure non-zero return).

  • This prevents distortions as long as $count(c)$ is sufficiently large.

• Explanatory Power:

  • Models have high explanatory power (similar to Decision Trees).

  • Identifies key attributes; e.g., Income and Marital Status essentially determine risk factors.

  • A typical "Good Risk" profile is defined as someone who is married and has high income.

• Handling Missing Values:

  • In Training Set: Exclude those instances from the probability estimate calculations.

  • In Inference (Instance to be Classified): If an attribute value is missing, set the corresponding conditional probability to 1 for ALL class outcomes to avoid biasing the product.

• Handling Continuous Data:

  • Binning: Discretizing numeric features into non-overlapping sub-ranges.

  • Gaussian Assumption: Assume values follow a Normal Distribution.

  • Formula for probability density:

  • $Pr(X = x|C = c) = \frac{1}{\sqrt{2\pi\sigma_c^2}} e^{-\frac{(x-\mu_c)^2}{2\sigma_c^2}}$

  • Where $\mu_c$ is the sample mean and $\sigma_c^2$ is the sample variance across class $c$.

• General Characteristics:

  • Highly efficient; requires only one pass through the training data.

  • Bayesian Network: An advanced version used when a large number of features are highly dependent on each other to prevent substantial accuracy drops.

Decision Trees

• Recursive Procedure:

  • Uses a top-down, "divide and conquer" approach.

  • An attribute is selected for the root node, and a branch is created for each possible value.

  • Instances are split into subsets and the procedure repeats recursively for each branch.

  • Stopping Criteria: Stops if all instances belong to the same class or if no further attributes/instances remain.

• Attribute Selection Criterion:

  • Objective: Choose the attribute that results in the smallest tree.

  • Heuristic: Choose attributes that produce the "purest" nodes.

  • Information Gain: Popular purity criterion measured in bits.

• Entropy and Information Gain Formulas:

  • Entropy represents the information required to predict an event from a distribution.

  • $Entropy(p_1, p_2, \dots, p_n) = \sum_{i=1}^n -p_i \log_2(p_i)$

  • Example (Outlook Attribute):

    • Sunny: [2, 3] nodes → $Entropy(2/5, 3/5) = 0.971$ bits.

    • Overcast: [4, 0] nodes → $Entropy(1, 0) = 0$ bits.

    • Rainy: [3, 2] nodes → $Entropy(3/5, 2/5) = 0.971$ bits.

    • Info after split: $(5/14) \times 0.971 + (4/14) \times 0 + (5/14) \times 0.971 = 0.693$ bits.

    • Gain Calculation: $Gain = Info(\text{Before split}) - Info(\text{After split})$.

    • $Gain(\text{Outlook}) = 0.940 - 0.693 = 0.247$ bits.

• Splitting Factors (Weather Data):

  • $Gain(\text{Temperature}) = 0.571$ bits.

  • $Gain(\text{Humidity}) = 0.971$ bits.

  • $Gain(\text{Windy}) = 0.020$ bits.

• Leaf Node Properties:

  • Not all leaves must be pure. Non-pure leaves are labeled with the majority class.

• Advantages:

  • Inexpensive to construct and extremely fast at classification.

  • Highly interpretable for small trees.

  • Accuracy is comparable to other popular techniques across many datasets.

Underfitting and Overfitting

• Underfitting:

  • Occurs when the model fails to learn the patterns in the data.

  • Result: Poor accuracy on both training and test data.

  • Cause: Algorithm is unable to find patterns; for Decision Trees, this happens when the tree lacks sufficient depth/size.

• Overfitting:

  • The model learns training data patterns too well, including noise.

  • Result: High training accuracy, but very low test (generalization) accuracy.

  • Primary Causes:

    • Noise: Errors in class labels that distort decision boundaries.

    • Insufficient Data: Lack of examples in certain regions causes the tree to use irrelevant records to justify partitions.

  • Visualization: A decision boundary distorted to capture a single "noise point" indicates overfitting.

• Addressing Overfitting (Post-pruning):

  • Grow the tree to its full extent.

  • Trim nodes bottom-up.

  • If generalization error improves (estimated via various methods), replace the sub-tree with a leaf node labeled with the majority class.

Python Libraries for Classification (Lab 3 Tools)

• Pandas and Data Frames:

  • Stored in rectangular grids (rows = instances, columns = variables).

  • Components: Data, Index (row indicator), and Columns (feature labels).

  • .iloc[row][column]: Selects data by integer-based position.

  • .loc[row][column]: Selects data by label.

• NumPy Arrays:

  • Homogeneous n-dimensional arrays optimized for math.

  • .reshape(): Changes dimensions (e.g., $2 \times 5$ to $5 \times 2$) if total elements remain constant.

  • .ravel(): Flattens multi-dimensional arrays into a single dimension.

  • .shape(): Returns the dimensions of the array.

  • Indexing: a[2,3] retrieves the element at row index 2, column index 3 (0-indexed). a[2,:] returns all columns for the 3rd row.

• Scikit-learn:

  • Comprehensive library built on NumPy, SciPy (science/tech computing), Matplotlib (visualization), and Pandas.

  • Designed for modeling, not for data engineering (loading/manipulating).

  • Supported Algorithms: Regression, Clustering, Decision Trees (induction and pruning), Neural Networks, SVMs, Na ive Bayes, and Ensemble methods.

References and Reading

• Primary Text: Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.) by Ian Witten and Eibe Frank (2011), Chapter 4.

• Na ive Bayes Kernel Functions: John, G. H., & Langley, P., Estimating Continuous Distributions in Bayesian Classifiers.

• Bayesian Networks: Cooper, G., & Herskovitz, E. (1992), A Bayesian method for the induction of probabilistic networks from data, Machine Learning, 9, 330–347.