Hierarchical Clustering: Objective Functions and Algorithms. Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F., & Mathieu, C. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, of Proceedings, pages 378-397. Society for Industrial and Applied Mathematics.
Hierarchical Clustering: Objective Functions and Algorithms [link]Paper  doi  abstract   bibtex   
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, [19] 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, such as in order to achieve optimal cost, disconnected components must be separated first and that in ‘structureless’ graphs, i.e., cliques, all clusterings achieve the same cost. 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 the one introduced by Dasgupta) that have the property that when the input admits a ‘natural’ ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. For similarity-based hierarchical clustering, [19] showed that a simple recursive sparsest-cut based approach achieves an O(log3/2 n)-approximation on worst-case inputs. We give a more refined analysis of the algorithm and show that it in fact achieves an -approximation1. This improves upon the LP-based O(log n)-approximation of [33]. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approximation, and provide a simple and better algorithm that gives a factor 3/2 approximation. This aims at explaining the success of these heuristics in practice. Finally, we consider a ‘beyond-worst-case’ scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function also has desirable properties for these inputs and we provide a simple algorithm that for graphs generated according to this model yields a 1 + o(1) factor approximation.
@incollection{cohen-addadHierarchicalClusteringObjective2018,
  title = {Hierarchical {{Clustering}}: {{Objective Functions}} and {{Algorithms}}},
  url = {https://epubs.siam.org/doi/10.1137/1.9781611975031.26},
  shorttitle = {Hierarchical {{Clustering}}},
  abstract = {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, [19] 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, such as in order to achieve optimal cost, disconnected components must be separated first and that in ‘structureless’ graphs, i.e., cliques, all clusterings achieve the same cost. 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 the one introduced by Dasgupta) that have the property that when the input admits a ‘natural’ ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. For similarity-based hierarchical clustering, [19] showed that a simple recursive sparsest-cut based approach achieves an O(log3/2 n)-approximation on worst-case inputs. We give a more refined analysis of the algorithm and show that it in fact achieves an -approximation1. This improves upon the LP-based O(log n)-approximation of [33]. For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approximation, and provide a simple and better algorithm that gives a factor 3/2 approximation. This aims at explaining the success of these heuristics in practice. Finally, we consider a ‘beyond-worst-case’ scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function also has desirable properties for these inputs and we provide a simple algorithm that for graphs generated according to this model yields a 1 + o(1) factor approximation.},
  volumes = {0},
  booktitle = {Proceedings of the {{Twenty}}-{{Ninth Annual ACM}}-{{SIAM Symposium}} on {{Discrete Algorithms}}},
  series = {Proceedings},
  publisher = {{Society for Industrial and Applied Mathematics}},
  urldate = {2019-05-17},
  date = {2018-01-01},
  pages = {378-397},
  author = {Cohen-Addad, V. and Kanade, V. and Mallmann-Trenn, F. and Mathieu, C.},
  file = {/home/dimitri/Nextcloud/Zotero/storage/VHDL9VUB/Cohen-Addad et al. - 2018 - Hierarchical Clustering Objective Functions and A.pdf;/home/dimitri/Nextcloud/Zotero/storage/EJTTUVNP/1.9781611975031.html},
  doi = {10.1137/1.9781611975031.26}
}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021