Conceptual Clustering of Complex Objects: A Generalization Space based Approach

I. BOURNAUD, J.-G. GANASCIA

IBP-Laforia 1995/20: Rapport de Recherche Laforia / Laforia research reports
16 pages - Janvier/January 1996 - Document en anglais.

PostScript : 63 Ko /Kb

Titre / Title: Conceptual Clustering of Complex Objects: A Generalization Space based Approach

Résumé : Un des objectifs de l'apprentissage à partir d'observations est de construire une classification d'un ensemble donné d'objets ou de situations. La problématique des méthodes de regroupement conceptuel est ainsi de reconnaître des régularités dans un ensemble d'objets non préclassifiés de façon à pouvoir les organiser en une hiérarchie de concepts. Les premières méthodes se sont limitées à des domaines non structurés dans lesquels les objets sont décrits par un ensemble de paires attribut-valeur. Les approches récentes destinées à des domaines structurés représentent les objets à l'aide de formalismes basés sur la logique du premier ordre. Cet article présente une telle approche dans laquelle les objets complexes sont représentés à l'aide du formalisme des graphes conceptuels. Nous proposons une méthode originale de regroupement conceptuel qui extrait une classification hiérarchique d'un espace de hiérarchies de concepts explicitement construit: l' Espace de Généralisations. Nous donnons l'algorithme général et présentons quelques résultats sur sa complexité. Cet algorithme a été implémenté dans le système coing. Nous présentons quelques résultats empiriques de l'utilisation de coing dans le cadre de la construction de hiérarchies de caractères chinois.

Abstract : A key issue in learning from observations is to build a classification of given objects or situations. Conceptual clustering methods address this problem of recognizing regularities among a set of objects that have not been pre-classified, so as to organize them into a hierarchy of concepts. Early approaches have been limited to unstructured domains, in which objects are described by fixed sets of attribute-value pairs. Recent approaches in structured domains use a first order logic based representation to represent complex objects. The problem addressed in this paper is to provide a basis for the analysis of complex objects clustering represented using conceptual graphs formalism. We propose a new clustering method that extracts a hierarchical categorization of the provided objects from an explicit space of concepts hierarchies, called Generalization Space. We give a general algorithm and expose several complexity factors. This algorithm has been implemented in a system called coing. We provide some empirical results on its use to cluster a large database of Chinese characters.

Publications internes Laforia 1995 / Laforia research reports 1995