Reliable Agglomerative Clustering

We analyze the general behavior of agglomerative clustering methods, and argue that their strategy yields establishment of a new reliable linkage at each step. However, in order to provide adaptive, density-consistent and flexible solutions, we propose to extract all the reliable linkages at each step, instead of the smallest one. This leads to a new agglomerative clustering strategy, called reliable agglomerative clustering, which similar to the standard agglomerative variant can be applied with all common criteria. Moreover, we prove that this strategy with the single linkage criterion yields a minimum spanning tree algorithm. We perform experiments on several real-world datasets to demonstrate the superior performance of this strategy, compared to the standard alternative.