In this work, we introduce a novel methodology for divisive hierarchical clustering. Our divisive (``top-down'') approach is motivated by the fact that agglomerative hierarchical clustering (``bottom-up''), which is commonly used for hierarchical clustering, is not the best choice for all settings. The proposed methodology approximates the similarity matrix by a block diagonal matrix to identify clusters. While divisively clustering $p$ elements involves evaluating $2^{p-1}-1$ possible splits, which makes the task computationally costly, this approximation effectively reduces this number to at most $p(p-1)$ candidates, ensuring computational feasibility. We elaborate on the methodology and describe the incorporation of linkage functions to assess distances between clusters. We further show that these distances are ultrametric, ensuring that the resulting hierarchical cluster structure can be uniquely represented by a dendrogram, with interpretable heights. Additionally, the proposed methodology exhibits the flexibility to also optimize objectives of other clustering methods, and it can outperform these. The methodology is also applicable for constructing balanced clusters. To validate the efficiency of our approach, we conduct simulation studies and analyze real-world data. Supplementary materials for this article can be accessed online.

翻译：暂无翻译