Elamur Research
☰
home / papers / 2007 / V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure

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

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D07-1043.pdf

Summary

External clustering evaluation compares an automatic clustering with gold class labels. Many existing scores are hard to interpret or unreliable. Purity and Entropy only reward clusters that are internally pure. Matching-based scores such as clustering F-measure first pair each cluster with a class, so they ignore unmatched clusters (the "problem of matching") and partly judge the mapping instead of the clustering. Rosenberg and Hirschberg propose V-measure to fix this. It combines two normalized conditional-entropy criteria. Homogeneity asks whether each cluster holds a single class. Completeness asks whether each class falls into a single cluster. V-measure is their weighted harmonic mean, built much like F-measure. Using simulated clusterings, the authors show it behaves better than Purity, Entropy, F-measure, VI and Q2. They then apply it to document clustering and to k-means clustering of pitch accent types. Because the score looks at every data point and needs no cluster-to-class mapping, it can be compared across datasets and diagnoses clustering errors more clearly.

Key points

  • Definitions:
    • Homogeneity is 1 − H(C|K)/H(C).
    • Completeness is 1 − H(K|C)/H(K).
    • V_β = (1+β)·h·c / (β·h + c). Setting β>1 favours completeness, and β<1 favours homogeneity.
  • Problem of matching: in toy examples, clusterings with the same F-measure get clearly different V-measures.
    • Two solutions at F-measure 0.5 score 0.14 vs 0.39.
    • Two solutions at F-measure 0.6 score 0.30 vs 0.41.
  • Document clustering: V-measure and Q2 both peak at 35 clusters, but Q2 falls more steeply as the number of clusters grows.
  • Pitch accent data and features:
    • Accented words are drawn from the Boston Directions Corpus, specifically its read-speech section, and are labelled with the five ToBI accent types (H*, L*, L+H*, L*+H, H+!H*).
    • Only a random 10% of H* tokens were kept, to reduce class skew.
    • Ten acoustic features were extracted with Praat.
  • Pitch accent results:
    • Q2 peaks at k=10, which the authors attribute to its MDL bias toward fewer clusters.
    • V-measure keeps rising beyond about 30 clusters, because homogeneity improves while completeness stays stable.
    • VI depends closely on k.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

113 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 107 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{rosenberg2007v,
  title = {{V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure}},
  author = {Rosenberg, Andrew and Hirschberg, Julia},
  booktitle = {EMNLP-CoNLL 2007},
  year = {2007},
  url = {https://aclanthology.org/D07-1043/}
}

References

34 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Ulrike Baldewein, Katrin Erk, Sebastian Pado, and Detlef Prescher. 2004. Semantic role labelling with similarity-based generalization using EM-based clustering. In Proceedings of Senseval’04, Barcelona. find
  2. Paul Boersma. 2001. Praat, a system for doing phonetics by computer. Glot International, 5(9-10):341–345. find
  3. Douglass R. Cutting, Jan O. Pedersen, David Karger, and John W. Tukey. 1992. Scatter/gather: A cluster-based approach to browsing large document collections. In Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 318–329. find
  4. I. S. Dhillon, S. Mallela, and D. S. Modha. 2003. Information-theoretic co-clustering. In Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2003), pages 89–98. find
  5. Byron E. Dom. 2001. An information-theoretic external cluster-validity measure. Technical Report RJ10219, IBM, October. find
  6. E. B. Fowlkes and C. L. Mallows. 1983. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, 78:553–569. find
  7. Benjamin C. M. Fung, Ke Wang, and Martin Ester. 2003. Hierarchical document clustering using frequent itemsets. In Proc. of the SIAM International Conference on Data Mining. find
  8. Julia Hirschberg. 2002. The pragmatics of intonational meaning. In Proc. Speech Prosody, pages 65–68. find
  9. L. Hubert and P. Arabie. 1985. Comparing partitions. Journal of Classification, 2:193–218. find
  10. L. Hubert and J. Schultz. 1976. Quadratic assignment as a general data analysis strategy. British Journal of Mathematical and Statistical Psychology, 29:190–241. find
  11. Bjornar Larsen and Chinatsu Aone. 1999. Fast and effective text mining using linear-time document clustering. In KDD ’99: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 16–22, New York, NY, USA. ACM Press. find
  12. Gina-Anne Levow. 2006. Unsupervised and semi-supervised learning of tone and pitch accent. In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, pages 224–231, Morristown, NJ, USA. Association for… find
  13. J. McQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proc. of the Fifty Berkeley Symposium on Mathematical Statistics and Probability, pages 281–297. find
  14. Marina Meila and David Heckerman. 2001. An experimental comparison of model-based clustering methods. Mach. Learn., 42(1/2):9–29. find
  15. Marina Meila. 2007. Comparing clusterings – an information based distance. Journal of Multivariate Analysis, 98:873– 895. find
  16. G. W. Milligan, S. C. Soon, and L. M. Sokol. 1983. The effect of cluster size, dimensionality and the number of clustes on recovery of true cluster structure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5:40–47. find
  17. Boris G. Mirkin. 1996. Mathematical classification and clustering. Kluwer Academic Press. find
  18. Christine Nakatani, Julia Hirschberg, and Barbara Grosz. 1995. Discourse structure in spoken language: Studies on speech corpora. In Working Notes of AAAI-95 Spring Symposiom on Empirical Methods in Discourse Interpretation. find
  19. Michael P. Oakes. 1998. Statistics for Corpus Linguistics. Edinburgh University Press. find
  20. M. Porter. 1980. An algorithm for suffix stripping. Program, 14(3):130–137. find
  21. William M. Rand. 1971. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846–850, Dec. find
  22. J. Rissanen. 1978. Modeling by shortest data description. Automatica, 14:465–471. find
  23. J. Rissanen. 1989. Stochastic complexity in statistical inquiry. World Scientific Series in Computer Science, 15. find
  24. Sa-Im Shin and Key-Sun Choi. 2004. Automatic word sense clustering using collocation for sense adaptation. In The Second Global Wordnet Conference. find
  25. K. Silverman, M. Beckman, J. Pitrelli, M. Ostendorf, C. Wightman, P. Price, J. Pierrehumbert, and J. Hirschberg. 1992. Tobi: A standard for labeling english prosody. In Proc. of the 1992 International Conference on Spoken Language Processing, volume 2, pages 12–16. find
  26. Strassel and M. Glenn. 2003. Creating the annotated tdt-4 y2003 evaluation corpus. http://www.nist.gov/speech/tests/tdt/tdt2003/papers/ldc.ppt. ↗
  27. Stijn van Dongen. 2000. Performance criteria for graph clustering and markov cluster experiments. Technical report, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, The Netherlands. find
  28. C. J. Van Rijsbergen. 1979. Information Retrieval, 2nd edition. Dept. of Computer Science, University of Glasgow. find
  29. Santosh Vempala and Grant Wang. 2005. The benefit of spectral projection for document clustering. In Workshop on Clustering High Dimensional Data and its Applications Held in conjunction with Fifth SIAM International Conference on Data Mining (SDM 2005). find
  30. D. L. Wallace. 1983. Comment. Journal of the American Statistical Association, 78:569–576. find
  31. Peter Willett. 1988. Recent trends in hierarchic document clustering: a critical review. Inf. Process. Manage., 24(5):577– 597. find
  32. Oren Zamir and Oren Etzioni. 1998. Web document clustering: A feasibility demonstration. In Research and Development in Information Retrieval, pages 46–54. find
  33. Yujing Zeng, Jianshan Tang, Javier Garcia-Frias, and Guang R. Gao. 2002. An adaptive meta-clustering approach: Combining the information from different clustering results. csb, 00:276. find
  34. Ying Zhao and George Karypis. 2001. Criterion functions for ducument clustering: Experiments and analysis. Technical Report TR 01–40, Department of Computer Science, University of Minnesota. find