What is the Shape of a Cluster?
Vinay Deolalikar · 2014
Even today, most interfaces to document clustering present clusters to users and applications as a "bag of descriptive terms"? a technique that was proposed two decades ago. Consequently, users and applications are not able to obtain sophisticated structural knowledge that is indeed lying hidden in document clusters. In particular, the structural information about interaction of concepts that the cluster speaks about is completely missing from the bag of terms presentation. As the needs of unstructured information management increase, this shortcoming is coming into sharper focus. To address this shortcoming, we propose a rich representation of document clusters that surfaces the concept interactions within a cluster into the representation. We show that these interactions give a "shape" to the cluster. This "shape" is conveniently captured using a directed, colored, vertex-weighted graph, called the shape graph or, simply, the shape of the cluster. We show that shapes convey important structural information about document clusters, and can be computed efficiently.