Hierarchical clustering is a popular unsupervised data analysis method. For
many real-world applications, we would like to exploit prior information about
the data that imposes constraints on the clustering hierarchy, and is not
captured by the set of features available to the algorithm. This gives rise to
the problem of "hierarchical clustering with structural constraints".
Structural constraints pose major challenges for bottom-up approaches like
average/single linkage and even though they can be naturally incorporated into
top-down divisive algorithms, no formal guarantees exist on the quality of
their output. In this paper, we provide provable approximation guarantees for
two simple top-down algorithms, using a recently introduced optimization
viewpoint of hierarchical clustering with pairwise similarity information
[Dasgupta, 2016]. We show how to find good solutions even in the presence of
conflicting prior information, by formulating a constraint-based regularization
of the objective. We further explore a variation of this objective for
dissimilarity information [Cohen-Addad et al., 2018] and improve upon current
techniques. Finally, we demonstrate our approach on a real dataset for the
taxonomy application.

本文研究了带有结构约束条件的层次聚类问题，提出了两种基于优化视角的自顶向下算法，并且通过公式化约束性正则化的方法在存在冲突先验信息的情况下得出了良好的解，同时探讨了基于差异性信息变化的目标函数的变形并进一步优化了当前技术，最后将该方法应用于实际数据集的分类学应用