Interactive Steering of Hierarchical Clustering

Weikai Yang1   Xiting Wang2   Jie Lu1   Wenwen Dou3   Shixia Liu1

1Tsinghua University       2Microsoft Research Asia       3University of North Carolina at Charlotte

Teaser Image
Teaser Image

ReVision: (a) the control panel to load constraints and update clustering results; (b) the constraint tree; (c) the hierarchical clustering results. The colors encode the first-level categories of the constraint tree; (d) the information panel to facilitate understanding and customization of clustering.

Abstract

Hierarchical clustering is an important technique to organize big data for exploratory data analysis. However, existing one-size-fits-all hierarchical clustering methods often fail to meet the diverse needs of different users. To address this challenge, we present an interactive steering method to visually supervise constrained hierarchical clustering by utilizing both public knowledge (e.g., Wikipedia) and private knowledge from users. The novelty of our approach includes 1) automatically constructing constraints for hierarchical clustering using knowledge (knowledge-driven) and intrinsic data distribution (data-driven), and 2) enabling the interactive steering of clustering through a visual interface (user-driven). Our method first maps each data item to the most relevant items in a knowledge base. An initial constraint tree is then extracted using the ant colony optimization algorithm. The algorithm balances the tree width and depth and covers the data items with high confidence. Given the constraint tree, the data items are hierarchically clustered using evolutionary Bayesian rose tree. To clearly convey the hierarchical clustering results, an uncertainty-aware tree visualization has been developed to enable users to quickly locate the most uncertain sub-hierarchies and interactively improve them. The quantitative evaluation and case study demonstrate that the proposed approach facilitates the building of customized clustering trees in an efficient and effective manner.

Materials
arxiv pdf video preview presentation bib