Applying Clustering to the Classification Problem

AAAI 1997

TL;DR

This paper tackles the challenge of improving classification accuracy by using clustering to generate multiple prototypes per class, rather than relying on a single prototype as in traditional minimum-distance classifiers. The authors propose and evaluate three novel methods (SNMJ, SNMC, SNMC-D) for determining the optimal number of prototypes, showing that their SNMC approach outperforms the baseline SNMJ.

What Problem Does This Paper Address?

Traditional minimum-distance classifiers, like those described by Duda & Hart (1973), represent each class with a single "mean prototype." This works well when classes are well-separated and compact. However, when classes are complex, overlapping, or have multiple distinct sub-groups, a single prototype can be insufficient for accurate representation, leading to misclassifications. The core problem this paper addresses is how to effectively represent complex classes using multiple prototypes derived from clustering, and crucially, how to determine the optimal number of these prototypes for each class.

Methods

The paper proposes three methods for determining the optimal number of clusters ($k_c$) for each class in a supervised setting:

  • SNMJ (Sum of Squared Errors): This method calculates the sum of squared errors for $k_c$ and $k_c+1$ clusters. It then compares the ratio of these errors. If the improvement in error from $k_c$ to $k_c+1$ is statistically significant (using a threshold derived from Duda & Hart), the algorithm opts for $k_c+1$ clusters.
  • SNMC (Supervised Nearest Mean Classifier with Hill-Climbing): This approach uses training set accuracy to guide the selection of $k_c$. It starts with $k_c=1$ and iteratively increments the number of clusters for each class, evaluating the classification accuracy on the training set. If accuracy increases, $k_c$ is incremented; otherwise, it's kept.
  • SNMC-D (Supervised Nearest Mean Classifier with Distance optimization): This method aims to increase the distance between prototypes of different classes. It does this by incrementing the number of prototypes for a class, which intuitively helps to spread out the representations and make them more distinct from other classes.

The core idea is to use these methods to find groups of examples within each class, generalize these groups into prototypes (using their mean representation), and then classify new examples using a nearest neighbor approach to these learned prototypes.

Datasets

The paper evaluates their methods on 20 domains from the UCI repository of machine learning databases (Murphy & Aha, 1994). The experiments involved 30 runs per domain, using 66.6% of the data for training and 33.3% for testing. No new benchmarks were introduced; existing, well-established datasets were used.

Key Insights and Ideas

  • The limitation of single prototypes: The paper clearly articulates that a single prototype is often insufficient for complex or multi-modal classes, motivating the need for multiple prototypes.
  • Clustering in a supervised context: While k-means is typically unsupervised, this paper demonstrates its utility for feature extraction and representation learning within a supervised classification framework.
  • The importance of determining $k_c$: The core contribution lies in the novel methods proposed for automatically finding the optimal number of prototypes per class, which is a critical hyperparameter.
  • Visualizing prototype separation: Figure 1 intuitively illustrates how increasing prototypes can lead to better separation between classes, a key goal of the SNMC-D method.

Key Results

The authors experimentally evaluated SNMJ and SNMC on the 20 UCI domains.

  • SNMJ achieved an average classification accuracy of 78.9%.
  • SNMC achieved a higher average classification accuracy of 82.8%. This indicates that the SNMC method, which uses training set accuracy to guide the selection of $k_c$, performs better than the SNMJ method. The paper refers to Datta & Kibler (1997) for more detailed results on SNMC.

Limitations and Future Work

  • Computational Cost: While not explicitly detailed as a limitation, iterative hill-climbing (SNMC) and error ratio calculations (SNMJ) can be computationally intensive, especially with large datasets or many classes.
  • Generalizability of SNMC-D: The SNMC-D method is described conceptually as increasing distance, but its specific implementation and quantitative evaluation are less detailed than SNMJ and SNMC in this abstract.
  • Further Exploration: The paper implicitly suggests that further research could explore variations of these methods, potentially combining aspects of SNMC and SNMC-D, or investigating other criteria for determining $k_c$. The focus on improving classification accuracy through better class representation via clustering is a fertile ground for future work.

Summary updated

BibTeX
@inproceedings{1997applying,
  title = {{Applying Clustering to the Classification Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure