Résumé: Nous proposons dans cet article une méthode originale de détermination du nombre et de la composition des agrégats (i.e. classes au sens non supervisé) présents dans une base de données à partir de l'analyse d'une hiérarchie indicée. Notre méthode est basée sur le principe d'une coupure multi-niveaux dans la hiérarchie permettant d'adapter l'échelle à laquelle considérer les données pour déterminer les agrégats. Pour cela, nous proposons un critère permettant de détecter la présence d'un agrégat unique dans un sous-arbre de la hiérarchie. Ceci permet d'aborder les configurations (très fréquentes dans la pratique) présentant des agrégats de densités variables. De plus, notre algorithme ne nécessite pas de retour sur les données, mais exploite uniquement l'information disponible dans la hiérarchie.
Abstract
This article deals with an original hierarchical clustering
algorithm which automatically determines the number and
composition of clusters in a database. The method is based
upon a multi-level cutting in the hierarchy which allows
one to deal with high density variations in the data
(frequently encountered in real databases). The algorithm
proceeds by an in depth exploration of the hierarchy,
deciding a cutting when a single cluster is detected in the
current sub-tree. This detection is performed by an original
statistical criterion. Moreover, the clustering algorithm is
particularly fast, since it does not require any computation
involving original data, but exclusively exploits the
information provided by the hierarchy.