DESPOTA - an algorithm to detect the partition in the extended hierarchy of a dendrogram

Davide Passaretti, Domenico Vistocco
(2018) Studies in Theoretical and Applied Statistics, (eds. Perna C, Pratesi M, Ruiz Gazen A), pp 83-93. Springer

Amazon DOI  pdf

DESPOTA is a method proposed to seek the best partition among the ones hosted in a dendrogram. The algorithm visits nodes from the tree root toward the leaves. At each node, it tests the null hypothesis that the two descending branches sustain only one cluster of units through a permutation test approach. At the end of the procedure, a partition of the data into clusters is returned. This paper focuses on the interpretation of the test statistic using a data–driven approach, exploiting a real dataset to show the details of the test statistic and the algorithm in action. The working principle of DESPOTA is shown in the light of the Lance–Williams recurrence formula, which embeds all types of agglomeration methods.