An Ensemble Approach for Graph-Based Classification

Music City Center 

Class Cover Catch Digraphs (CCCDs) constitute graph theoretic solutions to the class cover problem and have been employed in classification. Two main variants are Pure-CCCDs (P-CCCDs) that construct a pure, proper cover and Random Walk-CCCDs (RW-CCCDs) that construct an (potentially) impure, improper cover. Previous results showed CCCD classifiers were robust to class imbalance, but not class overlap. Classification performance in settings of class imbalance and class overlap of CCCDs was worse than other tested strong classifiers. In this work, we developed a novel CCCD framework, called FlexiBalls. We provide theoretical justification for using FlexiBall as opposed to other CCCD variants through both VC dimension and computational cost as the basis for boosting. We detail the boosted FlexiBall classifier algorithm which we call the AdaCover Digraph Classifier (ACDC). We close by presenting results of ACDC versus other strong models in both synthetic Monte Carlo simulations and real data settings under AUC, F1-Score, and G-Mean metrics. ACDC is competitive to other strong models selected in all settings, and typically performs better for each metric when classes are heavily overlapped and imbalanced.

classification

graph-based classifiers

ensemble learning

class imbalance

boosting 

Section on Statistical Learning and Data Science