The progressive single linkage algorithm based on Minkowski ultrametrics

The paper focuses on the problem to find an ultrametric whose distortion is close to optimal. We introduce the Minkowski ultrametric distances of the statistical units obtained by a hierarchical Cluster method (single linkage). Let X be a matrix of quantitative variables observed on n statistical units. We consider the distortion matrix which measures the difference between the initial dissimilarity and the ultrametric approximation. We propose an Algorithm that by means of the Minkowski ultrametrics reaches a minimum approximation. The convergence of the algorithm allows to identify when the ultrametric approximation is at the local minimum. We highlight the validity of the Algorithm by its application to sets of real data.