Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Similarity-based hierarchical clustering can be interpreted as a combinatorial optimization problem, where a `good' hierarchical clustering is one that minimizes some cost function. Following work by Dasgupta, we take an axiomatic approach to defining `good' objective functions. We can then analyze several algorithms: divisive sparsest-cut, average-linkage, and a simple algorithm that we prove has good performance in a certain `beyond-worst-case' scenario.
This is based on joint work with Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn.
Talk slidesBack to the workshop page