Timezone: »

Hierarchical Clustering with Structural Constraints
Evangelos Chatziafratis · Rad Niazadeh · Moses Charikar

Wed Jul 11 02:30 AM -- 02:40 AM (PDT) @ K11

Hierarchical clustering is a popular unsuperviseddata analysis method. For many real-world applications,we would like to exploit prior informationabout the data that imposes constraintson the clustering hierarchy, and is not capturedby the set of features available to the algorithm.This gives rise to the problem of hierarchicalclustering with structural constraints. Structuralconstraints pose major challenges for bottom-upapproaches like average/single linkage and eventhough they can be naturally incorporated intotop-down divisive algorithms, no formal guaranteesexist on the quality of their output. In thispaper, we provide provable approximation guaranteesfor two simple top-down algorithms, usinga recently introduced optimization viewpoint ofhierarchical clustering with pairwise similarity information(Dasgupta, 2016). We show how to findgood solutions even in the presence of conflictingprior information, by formulating a constraint-basedregularization of the objective. Furthemore, weexplore a variation of this objective for dissimilarityinformation (Cohen-Addad et al., 2018) andimprove upon current techniques. Finally, we demonstrate our approach on a real dataset for the taxonomy application.

Author Information

Vaggos Chatziafratis (Stanford University)

I am a 3rd year PhD student at Stanford University working with Prof. Tim Roughgarden, Moses Charikar and Jan Vondrak. My research interests are in Algorithms and Learning Theory.

Niazadeh Niazadeh (Stanford University)
Moses Charikar (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors