  In data containing heterogeneous subpopulations, classification performance
benefits from incorporating the knowledge of cluster structure in the
classifier. Previous methods for such combined clustering and classification
either are classifier-specific and not generic or independently perform
clustering and classifier training, which may not form clusters that can
potentially benefit classifier performance. The question of how to perform
clustering to improve the performance of classifiers trained on the clusters
has received scant attention in previous literature despite its importance in
several real-world applications. In this paper, we theoretically analyze when
and how clustering may help in obtaining accurate classifiers. We design a
simple, efficient, and generic framework called Classification Aware Clustering
(CAC), to find clusters that are well suited for being used as training
datasets by classifiers for each underlying subpopulation. Our experiments on
synthetic and real benchmark datasets demonstrate the efficacy of CAC over
previous methods for combined clustering and classification.
