  Clustering evaluation measures are frequently used to evaluate the
performance of algorithms. However, most measures are not properly normalized
and ignore some information in the inherent structure of clusterings. We model
the relation between two clusterings as a bipartite graph and propose a general
component-based decomposition formula based on the components of the graph.
Most existing measures are examples of this formula. In order to satisfy
consistency in the component, we further propose a split-merge framework for
comparing clusterings of different data sets. Our framework gives measures that
are conditionally normalized, and it can make use of data point information,
such as feature vectors and pairwise distances. We use an entropy-based
instance of the framework and a coreference resolution data set to demonstrate
empirically the utility of our framework over other measures.
