How to explain that a "divide and conquer" type of clustering simplifies the classification problem

Question

I am trying to justify the following way of thinking about a classification problem, not necessarily in a strictly rigorous way.

Assume that we have a large dataset, $S$, size of $N$ and we have $C$ classes. The dataset is balanced, nearly all classes have equal amount of samples. Further assume that we have disjoint class subsets $C_0, C_1, \dots C_{n-1}$ such that $C_0 \cup C_1 \cup \dots C_{n-1} = C$. We call the set $S_{C_i}$ the subset of $S$, containing only the samples having the class labels in $C_i$, with $0 \leq i \leq n-1$. Additionally, we know that this partitioning scheme according to class labels is done in a way, such that the classes in the same subsets are "similar" to each other, such that they are easily confused for each other by classifiers, while they are "different" from other classes in other subsets, such that they are misclassified rarely.

Now, assume that we have a clustering mechanism, which is able to cluster the data into subsets $S_{C_0},S_{C_1},\dots,S_{C_{n-1}}$, almost perfectly, such that a negligible quantity of samples are falsely clustered in wrong subsets; both in the training and testing.

I hypothesise that, training a classifier, which is directly using the dataset $S$ as it is in order to classify the samples into $C$ classes are a harder problem compared to training $n$ distinct classifiers on the subsets $S_{C_0},S_{C_1},\dots,S_{C_{n-1}}$ to do the same; given that our clustering scheme works almost perfectly (cheap to execute as well) and a negligible amount of samples are misclustered into wrong subsets both in the training and test. By a "harder" problem, I mean that we can use simpler classifiers for every subset $S_{C_i}$ compared to the original one, which is directly working on $S$ to obtain the same level of accuracy. My explanation for that would be that the task for each classifier becomes more easier; each classifier becomes an "expert" for the classes in its data subset, learning the optimal representations and discriminators to separate them, while ignoring others, which is an easier optimization problem, if the dataset does not show an unusual pattern somehow. Of course, when a sample not belonging to the subset of a classifier is misclustered to it, it will be most probably misclassified as well, but we know that we can rely on the clustering system in that scenario.

Is my thought pattern logical here? How can this be explained better, maybe in a more theoretical way? I am open to any suggestions.

Answer 1

Clustering is much much harder than classification. So your prerequisite - a fast and high quality clustering - already implies the classification process will be almost perfect without any clustering.

Consider e.g. k-means clustering. Arguably the only "fast" clusterer. In essence it is a nearest-center classifier that additionally needs to learn the classes. It will not outperform a supervised nearest neighbor classifier!

Furthermore, you forget the actual use case, you are too much stuck in the train-test evaluation. If the classifier was tested successfully, you will then need to apply it to new data, one point at a time, as the data arrives to your production system. Do not assume you could cluster the test data (because you usually won't be able to wait until you have hundreds or thousands of new records), but you may only process it on instance at a time to get a realistic scenario. So you cannot rely on finding clusters at deployment time.