The NVI Clustering Evaluation Measure

Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL), pages 165–173, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics The NVI Clustering Evaluation Measure Roi Reichart ICNC Hebrew University of Jerusalem roiri@cs.huji.ac.il Ari Rappoport Institute of Computer Science Hebrew University of Jerusalem arir@cs.huji.ac.il Abstract Clustering is crucial for many NLP tasks and applications. However, evaluating the results of a clustering algorithm is hard. In this paper we focus on the evaluation setting in which a gold standard solution is available. We discuss two existing information theory based mea- sures, V and VI, and show that they are both hard to use when comparing the performance of different algorithms and different datasets. The V measure favors solutions having a large number of clusters, while the range of scores given by VI depends on the size of the dataset. We present a new measure, NVI, which nor- malizes VI to address the latter problem. We demonstrate the superiority of NVI in a large experiment involving an important NLP appli- cation, grammar induction, using real corpus data in English, German and Chinese. 1 Introduction Clustering is a major technique in machine learn- ing and its application areas. It lies at the heart of unsupervised learning, which has great potential advantages over supervised learning. This is es- pecially true for NLP, due to the high efforts and costs incurred by the human annotations required for training supervised algorithms. Recent NLP prob- lems addressed by clustering include POS induction (Clark, 2003; Goldwater and Griffiths, 2007), word sense disambiguation (Shin and Choi, 2004), seman- tic role labeling (Baldewein et al., 2004), pitch ac- cent type disambiguation (Levow, 2006) and gram- mar induction (Klein, 2005). Evaluation of clustering results is a challenging task. In this paper we address the external measures setting, where a correct assignment of elements to classes is available and is used for evaluating the quality of another assignment of the elements into clusters. Many NLP works have used external clus- tering evaluation measures (see Section 2). Recently, two measures have been proposed that avoid many of the weaknesses of previous measures and exhibit several attractive properties (see Sec- tions 2 and 3): the VI measure (Meila, 2007) and the V measure (Rosenberg and Hirschberg, 2007). However, each of these has a serious drawback. The possible values of VI lie in [0, 2log N], where N is the size of the clustered dataset. Hence it has lim- ited use when comparing performance on different datasets. V measure values lie in [0, 1] regardless of the dataset, but the measure strongly favors a cluster- ing having many small clusters. In addition, V does not have many of the attractive properties of VI. This paper has two contributions. First, we pro- pose the NVI measure, a normalization of VI which guarantees that the score of clusterings that VI con- siders good lies in [0,1], regardless of dataset size. Most of VI’s attractive properties are retained by NVI. Second, we compare the behavior of …

Content truncated to 500 words