Abstract
Traditional conceptual clustering systems primarily rely on intrinsic object features to form categories. This paper presents OPUS, a system that extends this paradigm by incorporating relational information—how objects interact with or relate to one another. By dynamically generating new attributes from these relationships, OPUS can distinguish between objects that appear identical based on local features but occupy different roles within a system.
Introduction
The task of conceptual clustering involves grouping objects into classes and providing descriptions for those classes. Historically, this process has focused on "narrow domains" where objects are defined by intrinsic properties like color, size, or shape. However, in many real-world domains, an object's identity is inextricably linked to its relationships. For instance, in genetics, a "purebred" and a "hybrid" plant may be phenotypically identical but are distinguished by their reproductive relationships. OPUS (implemented in Prolog) was developed to bridge this gap by integrating relational data into the clustering process.
Methodology
OPUS builds hierarchical classification trees in a top-down manner, guided by three core components:
- Clustering Algorithm: Based on the RUMMAGE algorithm, OPUS selects attributes that best partition a set of objects. It evaluates "quality" by balancing Simplicity (how easy is the class to describe?) and Inter-cluster difference (how distinct are the groups from one another?).
- Relational Chunks: When standard features are exhausted and objects still cannot be separated, OPUS generates new attributes. It does this by composing a relation with a feature. For example, it might combine the relation
eat(X, Y)with the featuresize(Y)to create a new attribute:eat_size. - Level-n Relations: The system can look deeper than immediate neighbors, defining "level two" relations (e.g., "what does the thing that my prey eats look like?"). To prevent a combinatorial explosion, it only explores new relations based on those that successfully helped refine classes at the previous level.
Experimental Evaluation
The system was evaluated on two qualitative "toy" domains that demonstrate its unique capabilities:
- Food Chain Domain: A set of 14 animals described by two features (size, locomotion) and 51 relational facts (the
eatrelationship). - Genetics Domain: Data modeled after Gregor Mendel’s pea plant experiments, including observable features (color, shape) and relational data (parent/offspring).
Key Results and Discussion
OPUS demonstrated a unique ability to "hallucinate" complex attributes to resolve classification ambiguities. In the food chain domain, it successfully distinguished between hawks and owls—both medium-sized flyers—by discovering the eat_eaten_size attribute. This attribute revealed that these birds differ based on the size of the animals that their prey consumes.
In the genetics domain, OPUS correctly identified the classes of hybrids and purebreds. By analyzing the relationship between parents and offspring, it reconstructed the nine classes Mendel identified in his multi-trait experiments, purely by analyzing the relationship between generations.
Conclusion and Future Work
OPUS highlights that an object's identity is often defined by its context within a system, not just its internal properties. While successful in these domains, the current implementation faces limitations: it requires batch processing of all data and is restricted to binary relations. Future research will focus on developing an incremental version of the system and extending it to handle n-ary relations, which are common in complex domains like chemistry.
Summary updated