Regroupement hiérarchique

Dans le domaine de l'analyse et de la classification automatique de données, le regroupement hiérarchique est un partitionnement de données ou clustering, au moyen de diverses méthodes, dites « ascendantes » et « descendantes ». Les méthodes dites « descendantes » partent d’une solution générale vers une autre plus spécifique. Les méthodes de cette catégorie démarrent avec une seule classe contenant la totalité puis se divisent à chaque étape selon un critère jusqu’à l’obtention d’un ensemble de classes différentes. À l'inverse des méthodes dites « descendantes », la classification ascendante hiérarchique est dite « ascendante » part d'une situation où tous les individus sont seuls dans une classe, puis sont rassemblés en classes de plus en plus grandes. Le qualificatif « hiérarchique » vient du fait qu'elle produit une hiérarchie H, l'ensemble des classes à toutes les étapes de l'algorithme, qui vérifie les propriétés suivantes : au sommet de la hiérarchie, lorsqu'on groupe de manière à obtenir une seule classe, tous les individus sont regroupés ; en bas de la hiérarchie, tous les individus se trouvent seuls ; ou ou : si l’on considère deux classes du regroupement, alors soit elles n'ont pas d’individu en commun, soit l'une est incluse dans l’autre. C'est une méthode de classification automatique utilisée en analyse des données ; à partir d'un ensemble de n individus, son but est de répartir ces individus dans un certain nombre de classes. La méthode suppose qu'on dispose d'une mesure de dissimilarité entre les individus ; dans le cas de points situés dans un espace euclidien, on peut utiliser la distance comme mesure de dissimilarité. La dissimilarité entre des individus x et y sera notée . Initialement, chaque individu forme une classe, soit n classes. On cherche à réduire le nombre de classes à , ce qui se fait itérativement. À chaque étape, on fusionne deux classes choisies comme les plus « proches », donc à la dissimilarité minimale. Cette valeur de dissimilarité, appelée indice d'agrégation, va croître d'itération en itération, la première étant par principe la plus petite.