  Hierarchical clustering is a class of algorithms that seeks to build a
hierarchy of clusters. It has been the dominant approach to constructing
embedded classification schemes since it outputs dendrograms, which capture the
hierarchical relationship among members at all levels of granularity,
simultaneously. Being greedy in the algorithmic sense, a hierarchical
clustering partitions data at every step solely based on a similarity /
dissimilarity measure. The clustering results oftentimes depend on not only the
distribution of the underlying data, but also the choice of dissimilarity
measure and the clustering algorithm. In this paper, we propose a method to
incorporate prior domain knowledge about entity relationship into the
hierarchical clustering. Specifically, we use a distance function in
ultrametric space to encode the external ontological information. We show that
popular linkage-based algorithms can faithfully recover the encoded structure.
Similar to some regularized machine learning techniques, we add this distance
as a penalty term to the original pairwise distance to regulate the final
structure of the dendrogram. As a case study, we applied this method on real
data in the building of a customer behavior based product taxonomy for an
Amazon service, leveraging the information from a larger Amazon-wide browse
structure. The method is useful when one wants to leverage the relational
information from external sources, or the data used to generate the distance
matrix is noisy and sparse. Our work falls in the category of semi-supervised
or constrained clustering.
