Classification par arbre : la forme de l'arbre inféré dépend du schéma algorithmique retenu

Deux schémas algorithmiques sont largement utilisés pour construire une distance d'arbre à partir d'une dissimilarité. Le premier, initialement employé pour les hiérarchies, consiste à agglomérer itérativement des paires de feuilles jusqu'à ce qu'il n'en reste plus que trois ce qui correspond à une unique structure d'arbre. Le second commence par un arbre à trois feuilles et greffe itérativement les objets sur l'arbre préalablement construit. À ces deux schémas de construction s'ajoute l'échange de sous-arbres, qui est utilisé pour améliorer itérativement les arbres obtenus grâce à l'un ou l'autre des schémas précédents. Nous montrons ici que, indépendamment du critère optimisé, ces schémas induisent en général des arbres de formes bien différentes. Le schéma agglomératif tend à produire des arbres compacts et de faible diamètre, tandis que le greffage et l'échange tendent à générer des arbres plus étendus ayant un diamètre important. Ce phénomène s'explique par la différence entre les distributions de probabilité a priori induites par chacun de ces schémas. Nous illustrons cette différence, très nette, à l'aide des données de l'Eve mitochondriale.