Stereotype Extraction with Default Clustering

Julien Velcin, Jean-Gabriel GanasciaIJCAI 2005

Introduction

Traditional conceptual clustering algorithms, such as k-means, EM, or Cobweb, are designed to find "prototypes"—statistical averages or most frequent members—within a dataset. However, these methods falter when faced with extremely sparse data, where missing values can reach up to 90%. In such scenarios, "averaging" becomes mathematically unstable and often leads to cluster descriptions that logically contradict the very examples they are meant to represent. This paper introduces Default Clustering and the PRESS algorithm, a logic-based framework designed to extract meaningful "stereotypes" from highly incomplete data.

Methodology: From Prototypes to Stereotypes

The core innovation lies in moving away from statistical prototypes toward logical stereotypes. A stereotype is defined as a structured association of characteristic features that provides a consistent "image" of a cluster.

Default Subsumption

Drawing from Raymond Reiter’s "Default Logic," the authors utilize default subsumption to compare descriptions with missing information. If two descriptions do not explicitly contradict each other, one can "subsume" the other by default. This allows the system to fill gaps using the broader context of the cluster.

The PRESS Algorithm

To identify the optimal set of stereotypes, the authors frame clustering as a combinatorial optimization problem. They employ the PRESS algorithm, which uses Tabu Search—a local search meta-heuristic—to navigate the space of possible stereotype sets. This approach prevents the algorithm from getting trapped in the local optima that frequently plague iterative refinement methods like k-means.

Constraints for Quality

PRESS incorporates two critical constraints to ensure the quality of extracted stereotypes:

  1. No-redundancy: Ensures that extracted stereotypes are distinct and provide contrast.
  2. Cognitive Cohesion: A novel requirement ensuring that any two features in a stereotype are linked by a "correlation path" of real examples, preventing the grouping of unrelated features just because they aren't contradictory.

Experimental Results

The authors evaluated PRESS against standard methods (EM, k-modes, and Cobweb) using both artificial and real-world datasets.

Robustness to Data Loss

Artificial tests involved 250 examples with 30 binary attributes, with missing data simulated up to 90%. As shown below, the PRESS algorithm demonstrates remarkable robustness. It recovered nearly 100% of initial descriptors even at 75% missing data. At the extreme 90% threshold, PRESS maintained a recovery rate of nearly 50%, significantly outperforming EM, k-modes, and Cobweb.

Robustness of PRESS in recovering descriptors under high missing data rates.

Logical Consistency and Real-World Application

The algorithm was also tested on the "Le Matin" newspaper archive, a real-world dataset regarding 19th-century French political disorder with an 87% missing data rate.

As detailed in the performance table, PRESS achieved a perfect 0% contradiction rate. In contrast, standard methods like k-modes and EM produced descriptions that contradicted between 27% and 57% of their own cluster members. Furthermore, PRESS was the only method to satisfy the "cognitive cohesion" constraint, producing descriptions that were both logically consistent and human-readable.

Comparative performance metrics showing PRESS achieving zero contradictions and cognitive cohesion.

Conclusion

By prioritizing logic over statistics, the PRESS algorithm provides a stable foundation for induction in sparse data environments. Stereotypes act as "caricatures" that are often more effective for fast classification and prediction than traditional prototypes. While computationally more intensive than simple iterative methods, the ability of PRESS to maintain logical consistency and high recovery rates makes it a powerful tool for analyzing fragmented historical or biological datasets.

Summary updated

BibTeX
@inproceedings{velcin2005stereotype,
  author = {Julien Velcin and Jean-Gabriel Ganascia},
  title = {{Stereotype Extraction with Default Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure