Nos tutelles

CNRS Dauphine PSL *



8 novembre 2018: 1 événement


  • Séminaires du Pôle 3 : "Sciences des données"

    Jeudi 8 novembre 13:45-15:00 - Vincent Cohen-Addad - LIP6

    Hierarchical clustering : Objective functions and algorithms

    Résumé : Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good’ hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties.We take an axiomatic approach to defining `good’ objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of “admissible” objective functions (that includes Dasgupta’s one) that have the property that when the input admits a `natural’ hierarchical clustering, it has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better algorithms. For similarity-based hierarchical clustering, Dasgupta showed that the divisive sparsest-cut approach achieves an O(log^3/2 n)-approximation. We give a refined analysis of the algorithm and show that it in fact achieves an O(\sqrtlog n)-approx. (Charikar and Chatziafratis independently proved that it is a O(\sqrtlog n)-approx.). This improves upon the LP-based O(logn)-approx. of Roy and Pokutta. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approx., and provide a simple and better algorithm that gives a factor 3/2 approx..Finally, we consider `beyond-worst-case’ scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta’s cost function has desirable properties for these inputs and we provide a simple 1 + o(1)-approximation in this setting.
    Joint work with Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu.

    Lieu : C110

    En savoir plus : Séminaires du Pôle 3 : "Sciences des données"