Classification of imbalanced data with a geometric digraph family. (English) Zbl 1392.62190

Manukyan, Artür; Ceyhan, Elvan

J. Mach. Learn. Res. 17, Paper No. 189, 40 p. (2016).

Summary: We use a geometric digraph family called class cover catch digraphs (CCCDs) to tackle the class imbalance problem in statistical classification. CCCDs provide graph theoretic solutions to the class cover problem and have been employed in classification. We assess the classification performance of CCCD classifiers by extensive Monte Carlo simulations, comparing them with other classifiers commonly used in the literature. In particular, we show that CCCD classifiers perform relatively well when one class is more frequent than the other in a two- class setting, an example of the class imbalance problem. We also point out the relationship between class imbalance and class overlapping problems, and their influence on the performance of CCCD classifiers and other classification methods as well as some state-of-the-art algorithms which are robust to class imbalance by construction. Experiments on both simulated and real data sets indicate that CCCD classifiers are robust to the class imbalance problem. CCCDs substantially undersample from the majority class while preserving the information on the discarded points during the undersampling process. Many state- of-the-art methods, however, keep this information by means of ensemble classifiers, but CCCDs yield only a single classifier with the same property, making it both appealing and fast.

MSC:

62H30	Classification and discrimination; cluster analysis (statistical aspects)
05C20	Directed graphs (digraphs), tournaments
05C90	Applications of graph theory
65C05	Monte Carlo methods

Keywords:

class cover catch digraphs; class cover problem; class imbalance problem; class overlapping problem; graph domination; prototype selection; support estimation

Software:

AdaBoost.MH; R; cccd; e1071; C4.5; JStatCom; KEEL; LIBSVM; UCI-ml; dd_tools