Hierarchical Clustering with Prior Knowledge
This work addresses the need for more robust hierarchical clustering in semi-supervised settings, such as leveraging external relational information or handling noisy data, but it is incremental as it builds on existing linkage-based algorithms with a regularization approach.
The paper tackles the problem of hierarchical clustering's sensitivity to distance measures and data distribution by incorporating prior domain knowledge through an ultrametric distance penalty, resulting in a method that can recover encoded structures and was applied to build a customer behavior-based product taxonomy for Amazon.
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.