Adaptive Prototype-Based Classification via Graph Theoretic and Topological Methods

Abstract

In statistical learning, many modern methods represent data using graphs to capture structure and relationships. Among these, class cover catch digraphs (CCCDs) were origi- nally introduced to address the class cover problem (CCP) and have since been applied to classification and clustering tasks. This dissertation addresses two distinct, yet complemen- tary, challenges in statistical learning: (i) classification performance degradation under class imbalance and class overlap, and (ii) reducing data cardinality through a novel, principled prototype selection method. We propose modified CCCD variants that improve robustness and generalization in imbalanced and overlapped class settings while preserving the geomet- ric intuition of the original CCCD framework. These contributions enhance the practical utility of CCCD classifiers. In addition, we introduce a topological data analysis (TDA)- based framework for selecting representative subsets (prototypes) from large datasets. We show that this approach preserves classification performance while substantially reducing data size. Such methods are crucial in resource-constrained environments where memory and computation are limited. Together, these contributions advance both algorithmic and geometric aspects of prototype learning and offer practical tools for scalable, interpretable, and efficient classification.