BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:372@lincs.fr
DTSTART;TZID=Europe/Paris:20180514T150000
DTEND;TZID=Europe/Paris:20180514T153000
DTSTAMP:20180515T060542Z
URL:https://www.lincs.fr/events/hierarchical-clustering-objective-function
 s-and-algorithms/
SUMMARY:Hierarchical clustering: Objective functions and algorithms
DESCRIPTION: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.\nWe 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.\nEquipped 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\nachieves
 an O(\\sqrt{log n})-approx. (Charikar and Chatziafratis independently
 proved that it is a O(\\sqrt{log 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..\nFinally\, 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.\n\nJoint work with Varun Kanade\,
 Frederik Mallmann-Trenn\, and Claire Mathieu.
CATEGORIES:Seminars,Youtube
LOCATION:LINCS / EIT Digital\, 23 avenue d'Italie\, 75013 Paris\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23 avenue d'Italie\, 75013
 Paris\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS / EIT Digital:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20180325T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR