Clustering around medoids based on ultrametric properties

摘要

The FFUCA (Fast and Flexible Unsupervised Clustering Algorithm) is a fast clustering method based on ultrametric properties. It aggregates data in the same way as partitional methods. But, it elects representatives differently. Indeed, in FFUCA the cluster representatives are deduced from an ultrametric structure built from a sample data. This ultrametric structure gives the data behavior according to used distance. Thus the results are independent from the cluster representatives. We propose in this paper an extension named FFUCAAM to change for better the quality of clusters. Indeed, we improve the election of these representatives. We substitute them by mediods after every new aggregation. This extension increases the complexity in the average case to O(Σ^ki=1 m²i) where k is the number of the resulting clusters and mi is the size of the cluster Ci. In fact, its computational cost is increased but it still less than O(n²), thus it remains applicable to large databases.