INDEXED DENDROGRAMS ON RANDOM DISSIMILARITIES

This paper studies the random indexed dendrograms produced by agglomer ative hierarchical algorithms under the non-classifiability hypothesis of independent identically distributed (i.i.d.) dissimilarities. New tests for classifiability are deduced. The corresponding test statisti cs are random variables attached to the indexed dendrograms, such as t he indices, the survival time of singletons, the value of the ultramet ric between two given points, or the size of classes in the different levels of the dendrogram. For an indexed dendrogram produced by the Si ngle Link method on i.i.d. dissimilarities, the distribution of these random variables is computed, thus leading to explicit tests. For the case of the Average and Complete Link methods, some asymptotic results are presented. The proofs rely essentially on the theory of random gr aphs.