The progressive Single Linkage Algorithm Based on Minkowski Ultrametrics

This paper focuses on the problem to find an ultrametric whose distortion is close to optimal. We introduce the Minkowski ultrametric distances of the n statistical units obtained by a hierarchical cluster method (single linkage). We consider the distortion matrix which measures the difference between the initial dissimilarity and the ultrametric approximation. We propose an algorithm which by the application of the Minkowski ultrametrics reaches a minimum approximation. The convergence of the algorithm allows us to identify when the ultrametric approximation is at the local minimum.