V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 410–420, Prague, June 2007. c⃝2007 Association for Computational Linguistics V-Measure: A conditional entropy-based external cluster evaluation measure Andrew Rosenberg and Julia Hirschberg Department of Computer Science Columbia University New York, NY 10027 {amaxwell,julia}@cs.columbia.edu Abstract We present V-measure, an external entropy- based cluster evaluation measure. V- measure provides an elegant solution to many problems that affect previously de- fined cluster evaluation measures includ- ing 1) dependence on clustering algorithm or data set, 2) the “problem of matching”, where the clustering of only a portion of data points are evaluated and 3) accurate evalu- ation and combination of two desirable as- pects of clustering, homogeneity and com- pleteness. We compare V-measure to a num- ber of popular cluster evaluation measures and demonstrate that it satisfies several de- sirable properties of clustering solutions, us- ing simulated clustering results. Finally, we use V-measure to evaluate two clustering tasks: document clustering and pitch accent type clustering. 1 Introduction Clustering techniques have been used successfully for many natural language processing tasks, such as document clustering (Willett, 1988; Zamir and Etzioni, 1998; Cutting et al., 1992; Vempala and Wang, 2005), word sense disambiguation (Shin and Choi, 2004), semantic role labeling (Baldewein et al., 2004), pitch accent type disambiguation (Levow, 2006). They are particularly appealing for tasks in which there is an abundance of language data available, but manual annotation of this data is very resource-intensive. Unsupervised clustering can eliminate the need for (full) manual annotation of the data into desired classes, but often at the cost of making evaluation of success more difficult. External evaluation measures for clustering can be applied when class labels for each data point in some evaluation set can be determined a priori. The clustering task is then to assign these data points to any number of clusters such that each cluster con- tains all and only those data points that are members of the same class Given the ground truth class la- bels, it is trivial to determine whether this perfect clustering has been achieved. However, evaluating how far from perfect an incorrect clustering solution is a more difficult task (Oakes, 1998) and proposed approaches often lack rigor (Meila, 2007). In this paper, we describe a new entropy-based external cluster evaluation measure, V-MEASURE1, designed to address the problem of quantifying such imperfection. Like all external measures, V-measure compares a target clustering — e.g., a manually an- notated representative subset of the available data — against an automatically generated clustering to de- termine now similar the two are. We introduce two complementary concepts, completeness and homo- geneity, to capture desirable properties in clustering tasks. In Section 2, we describe V-measure and how it is calculated in terms of homogeneity and complete- ness. We describe several popular external cluster evaluation measures and draw some comparisons to V-measure in Section 3. In Section 4, we discuss how some desirable properties for clustering are sat- isfied by …

Content truncated to 500 words