Hybrid classification method for imbalanced datasets

Tianxiang Gao

April 17, 2015

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
• Conclusion and future research

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
• Conclusion and future research

Contents

• Motivation
• Introduction
  • Classifier - Decision tree
  • Evaluate performance
  • Nature of problem
• Methodology
• Experimental results
• Conclusion and future research

Classifier

Classification problem is to correctly classifiy the previously unseen testing dataset based on the given training dataset. We deal with binary cases, positive class and negative class.

An algorithm that implements classification is known as a Classifier.

Decision tree is a tree-like classifier.

Contents

• Motivation
• Introduction
  • Classifier - Decision tree
  • Evaluate performace
  • Nature of problem
• Methodology
• Experimental results
• Conclusion and future research

Why?

• Multiple classifiers are available
• For each classifier, multiple choices are available for settings
• To choose best classifier

Cutoff value

Most algorithms classify via a 2-steps process:

Default cutoff value is 0.5

• If >= 0.5, classify as $positive$.
• If < 0.5, classify as $negative$.

Confusion Matrix

Accuracy

$ ACC = \frac{TP+TN}{TP + TN + FN + FP}$

May not very useful if imbalanced datasets.

TPR & FPR

True positive rate (TPR) $= \frac{TP}{TP + FN} $

False positive rate (FPR) $= \frac{FP}{FP + TN} $

ROC curve

-Wikipedia

ROC & AUC

Area Under the ROC curve (AUC) is to quantify the overal performance of a classifier.

Contents

• Motivation
• Introduction
  • Classifier - Decision tree
  • Evaluate performance
  • Nature of problem
• Methodology
• Experimental results
• Conclusion and future research

Nature of problem

Overlap, within-class imbalance, disjunct rules, authenticity of data.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
• Conclusion and future research

Contents

• Motivation
• Introduction
• Methodology
  • Sampling
  • Instance Selection
  • Hybrid method
• Experimental results
• Conclusion and future research

Sampling

• Undersampling
• Oversampling (with replacement)
• SMOTE

- Chawla, Nitesh V., et al 2002.

Contents

• Motivation
• Introduction
• Methodology
  • Sampling
  • Instance Selection
  • Hybrid method
• Experimental results
• Conclusion and future research

Instance Selection

Selects subset of training dataset such that removes superfluous instances, maintain performances.

Wrapper and Filter

Wrapper selects a subset of instances based on accuracy of a predefined classifier.

Filter ranks instances through non-classifier based function and then selects the instances from the ranking.

Greedy Selection

Greedy selection is a two-steps wrapper method: generates a number of candidate subsets, and starts with one candidate subset and continuouly combines the other subsets if combining improves the performance of classifier.

- W. Bennette and S. Olafsson 2013.

Greedy Selection

tuning parameter

• number of candidate subsets
• size of each subset

Contents

• Motivation
• Introduction
• Methodology
  • Sampling
  • Instance Selection
  • Hybrid method
• Experimental results
• Conclusion and future research

Hybrid Method

• Hyrid method is a combination method of SMOTE and greedy selection.

• Generate synthetic instances for minority class, and combines those synthetic instances with majority instances.
• Select the ideal subset from the SMOTEd instances by using greedy selection as the final training dataset.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
  • Characteristics of Datasets
  • SMOTEd Training Datasets
  • Greedy-Selected Training Datasets
  • Hybrid-Selected Training Datasets
  • Results
• Conclusion and future research

Characteristics of Datasets

4 well-known imbalanced datasets in UCI machine learning repository, and one medical dataset

- Chawla, Nitesh V. 2002.

- Gang Wu 2003.

- Nathalie Japkowicz 2004.

- Haibo He 2009.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
  • Characteristics of Datasets
  • SMOTEd Training Datasets
  • Greedy-Selected Training Datasets
  • Hybrid-Selected Training Datasets
• Conclusion and future research

SMOTE Training Datasets

tuning parameters

• number of nearest neighbors
• percentage of oversampling
• percentage of undersampling

Number of nearest neighbors

Default value is 5.

percentage of undersampling

The percentage of undersampling is not percentage of undersampling the entire majority class.

Instead, it is to maintain percentage of majority class with respective to SMOTEd minority class. In another word, it depends on percentage of oversampling minority class.

Arbitrarily sets it to 200%.

Note:if undersampling majority instances is more than its original instances, majority class would oversample with replacement.

percentage of oversampling

We implemented 10-fold cross validation to select the ideal percentage of oversampling among 100% to 1000%.

We used both ACC and AUC as assessment metrics to evaluate performances.

percentage of oversampling

From the previous figures and this table, 200% has been selected for yearst5 dataset since it has highest AUC, competitive accuracy, more stable, and simpler.

percentage of oversampling

Based on the strategy, the selected percentages for all dataset are listed in the table.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
  • Characteristics of Datasets
  • SMOTEd Training Datasets
  • Greedy-Selected Training Datasets
  • Hybrid-Selected Training Datasets
  • Results
• Conclusion and future research

Greedy Selection

tuning parameters

• number of candidate subset
• size of each candiate subset

tuning parameters

Usually over 90 percent of time comsumption is to find approporate tuning parameters. It's not very efficient.

Instead, we simply divided a dataset into 100 parts. Then, in each part, the size of subset has been fixed automatically.

The key is to choose an appropriate assessment metric.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
  • Characteristics of Datasets
  • SMOTEd Training Datasets
  • Greedy-Selected Training Datasets
  • Hybrid-Selected Training Datasets
• Conclusion and future research

Hybrid-Selected Training Datasets

tuning parameters

• number of nearest neighbors
• percentage of oversampling
• percentage of undersampling
• number of candidate subsets
• size of each candidate subset

tuning parameters

Usually assigns 5 to number of nearest neighbors.

Also use 10-fold cross validation to choose a good sampling percentages.

Separate dataset into 100 parts and the size of each candidate subsets has been fixed.

tunning parameters

Based on the strategy, the selected percentages for each dataset are listed in the table.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
  • Characteristics of Datasets
  • SMOTEd Training Datasets
  • Greedy-Selected Training Datasets
  • Hybrid-Selected Trianing Datasets
  • Results
• Conclusion and future research

Results

Randomly select 4/5 of a dataset as original training dataset, and the rest is testing dataset.

Implement those strategies to preprocess the dataset and we got four different training datasets: Control, Greedy Selection, SMOTE, and Hybrid.

Fit those four different training datasets through regular decision tree.

Predict the test dataset.

Process these steps over 100 times among each dataset. Then, evaluate predications through computing AUC, CBA, and ACC.

Contents

• Motivation
• Introduction
• Methodology
• Experimental results
• Conclusion and future research

Conclusion

• Hybrid Classification method makes decision tree works better.
• Robust
• Selecting an appropriate assessment metric is essential to wrapper-based method.
• Comprehensive assessment metric works better than non-comprehensive.

Future research

• Choices of different assessment metrics
• Choices of various selection techniques

Questions?