text: <PAPER>
  	<S sid="0">V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure</S><ABSTRACT>
  		<S sid="1" ssid="1">We present V-measure, an external entropybased cluster evaluation measure.</S>
  		<S sid="2" ssid="2">V measure provides an elegant solution tomany problems that affect previously defined 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 datapoints are evaluated and 3) accurate evaluation and combination of two desirable aspects of clustering, homogeneity and completeness.</S>
  		<S sid="3" ssid="3">We compare V-measure to a num ber of popular cluster evaluation measuresand demonstrate that it satisfies several desirable properties of clustering solutions, us ing simulated clustering results.</S>
  		<S sid="4" ssid="4">Finally, we use V-measure to evaluate two clustering tasks: document clustering and pitch accent type clustering.</S>
  	</ABSTRACT>
  	<SECTION title="Introduction" number="1">
  			<S sid="5" ssid="5">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).</S>
  			<S sid="6" ssid="6">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.</S>
  			<S sid="7" ssid="7">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.</S>
  			<S sid="8" ssid="8">External evaluation measures for clustering can be applied when class labels for each data point in some evaluation set can be determined a priori.</S>
  			<S sid="9" ssid="9">The clustering task is then to assign these data points toany number of clusters such that each cluster con tains all and only those data points that are membersof the same class Given the ground truth class la bels, it is trivial to determine whether this perfect clustering has been achieved.</S>
  			<S sid="10" ssid="10">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).</S>
  			<S sid="11" ssid="11">In this paper, we describe a new entropy-based external cluster evaluation measure, V-MEASURE1 , designed to address the problem of quantifying such imperfection.</S>
  			<S sid="12" ssid="12">Like all external measures, V-measurecompares 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.</S>
  			<S sid="13" ssid="13">We introduce twocomplementary concepts, completeness and homo geneity, to capture desirable properties in clustering tasks.</S>
  			<S sid="14" ssid="14">In Section 2, we describe V-measure and how itis calculated in terms of homogeneity and complete ness.</S>
  			<S sid="15" ssid="15">We describe several popular external cluster evaluation measures and draw some comparisons to V-measure in Section 3.</S>
  			<S sid="16" ssid="16">In Section 4, we discusshow some desirable properties for clustering are satisfied by V-measure vs. other measures.</S>
  			<S sid="17" ssid="17">In Sec tion 5, we present two applications of V-measure, ondocument clustering and on pitch accent type clus tering.</S>
  	</SECTION>
  	<SECTION title="V-Measure and Its Calculation" number="2">
  			<S sid="18" ssid="1">V-measure is an entropy-based measure which explicitly measures how successfully the criteria of homogeneity and completeness have been satisfied.</S>
  			<S sid="19" ssid="2">Vmeasure is computed as the harmonic mean of dis tinct homogeneity and completeness scores, just as1The ?V? stands for ?validity?, a common term used to de scribe the goodness of a clustering solution.</S>
  			<S sid="20" ssid="3">410 precision and recall are commonly combined into F-measure (Van Rijsbergen, 1979).</S>
  			<S sid="21" ssid="4">As F-measure scores can be weighted, V-measure can be weightedto favor the contributions of homogeneity or com pleteness.For the purposes of the following discussion, as sume a data set comprising N data points, and two partitions of these: a set of classes, C = {ci|i = 1, . . .</S>
  			<S sid="22" ssid="5">, n} and a set of clusters, K = {ki|1, . . .</S>
  			<S sid="23" ssid="6">,m}.Let A be the contingency table produced by the clus tering algorithm representing the clustering solution, such that A = {aij} where aij is the number of data points that are members of class ci and elements of cluster kj .To discuss cluster evaluation measures we introduce two criteria for a clustering solution: homogeneity and completeness.</S>
  			<S sid="24" ssid="7">A clustering result sat isfies homogeneity if all of its clusters contain only data points which are members of a single class.</S>
  			<S sid="25" ssid="8">A clustering result satisfies completeness if all the data points that are members of a given class are elementsof the same cluster.</S>
  			<S sid="26" ssid="9">The homogenity and completeness of a clustering solution run roughly in opposition: Increasing the homogeneity of a clustering so lution often results in decreasing its completeness.</S>
  			<S sid="27" ssid="10">Consider, two degenerate clustering solutions.</S>
  			<S sid="28" ssid="11">In one, assigning every datapoint into a single cluster, guarantees perfect completeness ? all of the datapoints that are members of the same class are triv ially elements of the same cluster.</S>
  			<S sid="29" ssid="12">However, this cluster is as unhomogeneous as possible, since allclasses are included in this single cluster.</S>
  			<S sid="30" ssid="13">In another solution, assigning each data point to a dis tinct cluster guarantees perfect homogeneity ? each cluster trivially contains only members of a singleclass.</S>
  			<S sid="31" ssid="14">However, in terms of completeness, this so lution scores very poorly, unless indeed each classcontains only a single member.</S>
  			<S sid="32" ssid="15">We define the dis tance from a perfect clustering is measured as theweighted harmonic mean of measures of homogene ity and completeness.</S>
  			<S sid="33" ssid="16">Homogeneity: In order to satisfy our homogeneity criteria, a clustering must assign only those datapoints that are members of a single class to a single cluster.</S>
  			<S sid="34" ssid="17">That is, the class distribution within each cluster should beskewed to a single class, that is, zero entropy.</S>
  			<S sid="35" ssid="18">We de termine how close a given clustering is to this ideal by examining the conditional entropy of the class distribution given the proposed clustering.</S>
  			<S sid="36" ssid="19">In the perfectly homogeneous case, this value, H(C|K), is 0.</S>
  			<S sid="37" ssid="20">However, in an imperfect situation, the size of this value, in bits, is dependent on the size of thedataset and the distribution of class sizes.</S>
  			<S sid="38" ssid="21">There fore, instead of taking the raw conditional entropy, we normalize this value by the maximum reduction in entropy the clustering information could provide, specifically, H(C).</S>
  			<S sid="39" ssid="22">Note that H(C|K) is maximal (and equals H(C)) when the clustering provides no new information ? the class distribution within each cluster is equal to the overall class distribiution.</S>
  			<S sid="40" ssid="23">H(C|K) is 0 when each cluster contains only members of a single class,a perfectly homogenous clustering.</S>
  			<S sid="41" ssid="24">In the degen erate case where H(C) = 0, when there is only a single class, we define homogeneity to be 1.</S>
  			<S sid="42" ssid="25">For a perfectly homogenous solution, this normalization, H(C|K) H(C) , equals 0.</S>
  			<S sid="43" ssid="26">Thus, to adhere to the conventionof 1 being desirable and 0 undesirable, we define ho mogeneity as: h = { 1 if H(C,K) = 0 1?</S>
  			<S sid="44" ssid="27">H(C|K)H(C) else (1) where H(C|K) = ? |K| ? k=1 |C| ? c=1 ack N log ack ?|C| c=1 ack H(C) = ? |C| ? c=1 ?|K| k=1 ack n log ?|K| k=1 ack n Completeness: Completeness is symmetrical to homogeneity.</S>
  			<S sid="45" ssid="28">Inorder to satisfy the completeness criteria, a clustering must assign all of those datapoints that are members of a single class to a single cluster.</S>
  			<S sid="46" ssid="29">To eval uate completeness, we examine the distribution of cluster assignments within each class.</S>
  			<S sid="47" ssid="30">In a perfectlycomplete clustering solution, each of these distribu tions will be completely skewed to a single cluster.We can evaluate this degree of skew by calculat ing the conditional entropy of the proposed clusterdistribution given the class of the component dat apoints, H(K|C).</S>
  			<S sid="48" ssid="31">In the perfectly complete case, H(K|C) = 0.</S>
  			<S sid="49" ssid="32">However, in the worst case scenario, 411each class is represented by every cluster with a dis tribution equal to the distribution of cluster sizes, H(K|C) is maximal and equals H(K).</S>
  			<S sid="50" ssid="33">Finally, in the degenerate case where H(K) = 0, when there is a single cluster, we define completeness to be 1.</S>
  			<S sid="51" ssid="34">Therefore, symmetric to the calculation above, we define completeness as: c = { 1 if H(K,C) = 0 1 ? H(K|C)H(K) else (2) where H(K|C) = ? |C| ? c=1 |K| ? k=1 ack N log ack ?|K| k=1 ack H(K) = ? |K| ? k=1 ?|C| c=1 ack n log ?|C| c=1 ack n Based upon these calculations of homogeneity and completeness, we then calculate a clustering solution?s V-measure by computing the weighted harmonic mean of homogeneity and completeness,V? = (1+?)?h?c(??h)+c . Similarly to the familiar F measure, if ? is greater than 1 completeness is weighted more strongly in the calculation, if ? is less than 1, homogeneity is weighted more strongly.</S>
  			<S sid="52" ssid="35">Notice that the computations of homogeneity,completeness and V-measure are completely inde pendent of the number of classes, the number ofclusters, the size of the data set and the clustering al gorithm used.</S>
  			<S sid="53" ssid="36">Thus these measures can be applied toand compared across any clustering solution, regard less of the number of data points (n-invariance), thenumber of classes or the number of clusters.</S>
  			<S sid="54" ssid="37">More over, by calculating homogeneity and completenessseparately, a more precise evaluation of the perfor mance of the clustering can be obtained.</S>
  	</SECTION>
  	<SECTION title="Existing Evaluation Measures. " number="3">
  			<S sid="55" ssid="1">Clustering algorithms divide an input data set into a number of partitions, or clusters.</S>
  			<S sid="56" ssid="2">For tasks wheresome target partition can be defined for testing purposes, we define a ?clustering solution?</S>
  			<S sid="57" ssid="3">as a map ping from each data point to its cluster assignments in both the target and hypothesized clustering.</S>
  			<S sid="58" ssid="4">In the context of this discussion, we will refer to the target partitions, or clusters, as CLASSES, referring only to hypothesized clusters as CLUSTERS.Two commonly used external measures for as sessing clustering success are Purity and Entropy (Zhao and Karypis, 2001), defined as, Purity = ?kr=1 1n maxi(nir) Entropy = ?kr=1 nrn (?</S>
  			<S sid="59" ssid="5">1log q ?q i=1 nir nr log nir nr ) where q is the number of classes, k the number of clusters, nr is the size of cluster r, and nir is the number of data points in class i clustered in cluster r. Both these approaches represent plausable ways to evaluate the homogeneity of a clustering solution.However, our completeness criterion is not measured at all.</S>
  			<S sid="60" ssid="6">That is, they do not address the question of whether all members of a given class are in cluded in a single cluster.</S>
  			<S sid="61" ssid="7">Therefore the Purity and Entropy measures are likely to improve (increased Purity, decreased Entropy) monotonically withthe number of clusters in the result, up to a degen erate maximum where there are as many clusters as data points.</S>
  			<S sid="62" ssid="8">However, clustering solutions rated high by either measure may still be far from ideal.Another frequently used external clustering evaluation measure is commonly refered to as ?cluster ing accuracy?.</S>
  			<S sid="63" ssid="9">The calculation of this accuracy isinspired by the information retrieval metric of F Measure (Van Rijsbergen, 1979).</S>
  			<S sid="64" ssid="10">The formula for this clustering F-measure as described in (Fung et al., 2003) is shown in Figure 3.</S>
  			<S sid="65" ssid="11">Let N be the number of data points, C the set of classes, K the set of clusters and nij be the number of members of class ci ? C that are elements of cluster kj ? K. F (C, K) = X ci?C |ci| N maxkj?K {F (ci, kj)} (3) F (ci, kj) = 2 ? R(ci, kj) ? P (ci, kj) R(ci, kj) + P (ci, kj) R(ci, kj) = nij |ci| P (ci, kj) = nij |kj | Figure 1: Calculation of clustering F-measure This measure has a significant advantage over Purity and Entropy, in that it does measure boththe homogeneity and the completeness of a cluster ing solution.</S>
  			<S sid="66" ssid="12">Recall is calculated as the portion of items from class i that are present in cluster j, thus measuring how complete cluster j is with respect toclass i. Similarly, Precision is calculated as the por 412 Solution A Solution B F-Measure=0.5 F-Measure=0.5 V-Measure=0.14 V-Measure=0.39 Solution C Solution D F-Measure=0.6 F-Measure=0.6 V-Measure=0.30 V-Measure=0.41 Figure 2: Examples of the Problem of Matchingtion of cluster j that is a member of class i, thus mea suring how homogenous cluster j is with respect to class i.Like some other external cluster evaluation tech niques (misclassification index (MI) (Zeng et al, 2002), H (Meila and Heckerman, 2001), L (Larsenand Aone, 1999), D (van Dongen, 2000), micro averaged precision and recall (Dhillon et al, 2003)), F-measure relies on a post-processing step in which each cluster is assigned to a class.</S>
  			<S sid="67" ssid="13">These techniques share certain problems.</S>
  			<S sid="68" ssid="14">First, they calculate the goodness not only of the given clustering solution, but also of the cluster-class matching.</S>
  			<S sid="69" ssid="15">Therefore, in order for the goodness of two clustering solutions to be compared using one these measures, an identicalpost-processing algorithm must be used.</S>
  			<S sid="70" ssid="16">This problem can be trivially addressed by fixing the classcluster matching function and including it in the def inition of the measure as in H . However, a secondand more critical problem is the ?problem of matching?</S>
  			<S sid="71" ssid="17">(Meila, 2007).</S>
  			<S sid="72" ssid="18">In calculating the similarity between a hypothesized clustering and a ?true?</S>
  			<S sid="73" ssid="19">cluster ing, these measures only consider the contributions from those clusters that are matched to a target class.This is a major problem, as two significantly differ ent clusterings can result in identical scores.</S>
  			<S sid="74" ssid="20">In figure 2, we present some illustrative examples of the problem of matching.</S>
  			<S sid="75" ssid="21">For the purposes of thisdiscussion we will be using F-Measure as the mea sure to describe the problem of matching, however, these problems affect any measure which requires a mapping from clusters to classes for evaluation.In the figures, the shaded regions represent CLUS TERS, the shapes represent CLASSES.</S>
  			<S sid="76" ssid="22">In a perfect clustering, each shaded region would contain all and only the same shapes.</S>
  			<S sid="77" ssid="23">The problem of matchingcan manifest itself either by not evaluating the en tire membership of a cluster, or by not evaluating every cluster.</S>
  			<S sid="78" ssid="24">The former situation is presented in the figures A and B in figure 2.</S>
  			<S sid="79" ssid="25">The F-Measure ofboth of these clustering solutions in 0.6.</S>
  			<S sid="80" ssid="26">(The preci sion and recall for each class is 35 .) That is, for each class, the best or ?matched?</S>
  			<S sid="81" ssid="27">cluster contains 3 of 5 elements of the class (Recall) and 3 of 5 elements of the cluster are members of the class (Precision).</S>
  			<S sid="82" ssid="28">The make up of the clusters beyond the majority class is not evaluated by F-Measure.</S>
  			<S sid="83" ssid="29">Solution B is a better clustering solution than solution A, in terms of both homogeneity (crudely, ?each cluster contains fewer2 classes?)</S>
  			<S sid="84" ssid="30">and completeness (?each class is containedin fewer clusters?).</S>
  			<S sid="85" ssid="31">Indeed, the V-Measure of so lution B (0.387) is greater than that of solution A (0.135).</S>
  			<S sid="86" ssid="32">Solutions C and D represent a case in which not every cluster is considered in the evaluation of F-Measure.</S>
  			<S sid="87" ssid="33">In this example, the F-Measure of both solutions is 0.5 (the harmonic mean of 35 and 37 ).</S>
  			<S sid="88" ssid="34">The small ?unmatched?</S>
  			<S sid="89" ssid="35">clusters are not measured at allin the calculation of F-Measure.</S>
  			<S sid="90" ssid="36">Solution D is a bet ter clustering than solution C ? there are no incorrect clusterings of different classes in the small clusters.</S>
  			<S sid="91" ssid="37">V-Measure reflects this, solution C has a V-measure of 0.30 while the V-measure of solution D is 0.41.</S>
  			<S sid="92" ssid="38">A second class of clustering evaluation techniquesis based on a combinatorial approach which examines the number of pairs of data points that are clustered similarly in the target and hypothesized clus tering.</S>
  			<S sid="93" ssid="39">That is, each pair of points can either be 1)clustered together in both clusterings (N11), 2) clustered separately in both clusterings (N00), 3) clustered together in the hypothesized but not the tar get clustering (N01) or 4) clustered together in the target but not in the hypothesized clustering (N10).</S>
  			<S sid="94" ssid="40">Based on these 4 values, a number of measures have been proposed, including Rand Index (Rand, 1971), 2Homogeneity is not measured by V-measure as a count of the number of classes contained by a cluster but ?fewer?</S>
  			<S sid="95" ssid="41">is an acceptable way to conceptualize this criterion for the purposes of these examples.</S>
  			<S sid="96" ssid="42">413 Adjusted Rand Index (Hubert and Arabie, 1985), ?statistic (Hubert and Schultz, 1976), Jaccard (Mil ligan et al, 1983), Fowlkes-Mallows (Fowlkes andMallows, 1983) and Mirkin (Mirkin, 1996).</S>
  			<S sid="97" ssid="43">We il lustrate this class of measures with the calculation of Rand Index.</S>
  			<S sid="98" ssid="44">Rand(C,K) = N11+N00n(n?1)/2 Rand Index can be interpreted as the probability that a pair of points is clustered similarly (together or separately) in C and K .Meila (2007) describes a number of poten tial problems of this class of measures posed by (Fowlkes and Mallows, 1983) and (Wallace, 1983).</S>
  			<S sid="99" ssid="45">The most basic is that these measures tend not to vary over the interval of [0, 1].</S>
  			<S sid="100" ssid="46">Transformations likethose applied by the adjusted Rand Index and a mi nor adjustment to the Mirkin measure (see Section4) can address this problem.</S>
  			<S sid="101" ssid="47">However, pair matching measures also suffer from distributional problems.</S>
  			<S sid="102" ssid="48">The baseline for Fowlkes-Mallows varies sig nificantly between 0.6 and 0 when the ratio of datapoints to clusters is greater than 3 ? thus including nearly all real-world clustering problems.</S>
  			<S sid="103" ssid="49">Similarly, the Adjusted Rand Index, as demonstrated using Monte Carlo simulations in (Fowlkes and Mal lows, 1983), varies from 0.5 to 0.95.</S>
  			<S sid="104" ssid="50">This variance in the measure?s baseline prompts Meila to ask if the assumption of linearity following normalization can be maintained.</S>
  			<S sid="105" ssid="51">If the behavior of the measure is so unstable before normalization can users reasonably expect stable behavior following normalization?</S>
  			<S sid="106" ssid="52">A final class of cluster evaluation measures arebased on information theory.</S>
  			<S sid="107" ssid="53">These measures analyze the distribution of class and cluster member ship in order to determine how successful a givenclustering solution is or how different two parti tions of a data set are.</S>
  			<S sid="108" ssid="54">We have already examined one member of this class of measures, Entropy.</S>
  			<S sid="109" ssid="55">From a coding theory perspective, Entropy is theweighted average of the code lengths of each cluster.</S>
  			<S sid="110" ssid="56">Our V-measure is a member of this class of clustering measures.</S>
  			<S sid="111" ssid="57">One significant advantage that in formation theoretic evaluation measures have is that they provide an elegant solution to the ?problem of matching?.</S>
  			<S sid="112" ssid="58">By examining the relative sizes of the classes and clusters being evaluated, these measures all evaluate the entire membership of each cluster ? not just a ?matched?</S>
  			<S sid="113" ssid="59">portion.</S>
  			<S sid="114" ssid="60">Dom?s Q0 measure (Dom, 2001) uses conditional entropy, H(C|K) to calculate the goodness of a clustering solution.</S>
  			<S sid="115" ssid="61">That is, given the hypothesized partition, what is the number of bits necessary to represent the true clustering?</S>
  			<S sid="116" ssid="62">However, this term ? like the Purity andEntropy measures ? only evaluates the homogene ity of a solution.</S>
  			<S sid="117" ssid="63">To measure the completeness of the hypothesized clustering, Dom includes a model cost term calculated using a coding theory argument.</S>
  			<S sid="118" ssid="64">The overall clustering quality measure presented is the sum of the costs of representing the data (H(C|K)) and the model.</S>
  			<S sid="119" ssid="65">The motivation for this approachis an appeal to parsimony: Given identical condi tional entropies, H(C|K), the clustering solution with the fewest clusters should be preferred.</S>
  			<S sid="120" ssid="66">Dom also presents a normalized version of this term, Q2, which has a range of (0, 1] with greater scores being representing more preferred clusterings.</S>
  			<S sid="121" ssid="67">Q0(C,K) = H(C|K)+ 1 n |K| ? k=1 log (h(k) + |C| ? 1 |C| ? 1 )where C is the target partition, K is the hypothe sized partition and h(k) is the size of cluster k. Q2(C,K) = 1 n ?|C| c=1 log (h(c)+|C|?1 |C|?1 ) Q0(C,K) We believe that V-measure provides two significantadvantages over Q0 that make it a more useful diag nostic tool.</S>
  			<S sid="122" ssid="68">First, Q0 does not explicitly calculate the degree of completeness of the clustering solution.</S>
  			<S sid="123" ssid="69">The cost term captures some of this information, since a partition with fewer clusters is likely to be more complete than a clustering solution with more clusters.</S>
  			<S sid="124" ssid="70">However, Q0 does not explicitly address the interaction between the conditional entropy and the cost of representing the model.</S>
  			<S sid="125" ssid="71">While this is an application of the minimum description length (MDL) principle (Rissanen, 1978; Rissanen, 1989), it does not provide an intuitive manner for assessingour two competing criteria of homogeneity and com pleteness.</S>
  			<S sid="126" ssid="72">That is, at what point does an increase inconditional entropy (homogeneity) justify a reduc tion in the number of clusters (completeness).</S>
  			<S sid="127" ssid="73">Another information-based clustering measure is variation of information (V I) (Meila, 2007), V I(C,K) = H(C|K)+H(K|C).</S>
  			<S sid="128" ssid="74">V I is presented 414 as a distance measure for comparing partitions (or clusterings) of the same data.</S>
  			<S sid="129" ssid="75">It therefore does notdistinguish between hypothesized and target cluster ings.</S>
  			<S sid="130" ssid="76">V I has a number of useful properties.</S>
  			<S sid="131" ssid="77">First, it satisfies the metric axioms.</S>
  			<S sid="132" ssid="78">This quality allowsusers to intuitively understand how V I values combine and relate to one another.</S>
  			<S sid="133" ssid="79">Secondly, it is ?con vexly additive?.</S>
  			<S sid="134" ssid="80">That is to say, if a cluster is split, the distance from the new cluster to the original is the distance induced by the split times the size of the cluster.</S>
  			<S sid="135" ssid="81">This property guarantees that all changes to the metric are ?local?: the impact of splitting ormerging clusters is limited to only those clusters in volved, and its size is relative to the size of these clusters.</S>
  			<S sid="136" ssid="82">Third, VI is n-invariant: the number of data points in the cluster do not affect the value of the measure.</S>
  			<S sid="137" ssid="83">V I depends on the relative sizes of the partitions of C and K , not on the number of points in these partitions.</S>
  			<S sid="138" ssid="84">However, V I is bounded by themaximum number of clusters in C or K , k?.</S>
  			<S sid="139" ssid="85">With out manual modification however, k?</S>
  			<S sid="140" ssid="86">= n, where each cluster contains only a single data point.</S>
  			<S sid="141" ssid="87">Thus, while technically n-invariant, the possible values of V I are heavily dependent on the number of datapoints being clustered.</S>
  			<S sid="142" ssid="88">Thus, it is difficult to compare V I values across data sets and clustering algorithms without fixing k?, as V I will vary over differ ent ranges.</S>
  			<S sid="143" ssid="89">It is a trivial modification to modify V I such that it varies over [0,1].</S>
  			<S sid="144" ssid="90">Normalizing, V I by log n or 1/2 log k?</S>
  			<S sid="145" ssid="91">guarantee this range.</S>
  			<S sid="146" ssid="92">However, Meila (2007) raises two potential problems with thismodification.</S>
  			<S sid="147" ssid="93">The normalization should not be applied if data sets of different sizes are to be com pared ? it negates the n-invariance of the measure.Additionally, if two authors apply the latter normal ization and do not use the same value for k?, their results will not be comparable.</S>
  			<S sid="148" ssid="94">While V I has a number of very useful distance properties when analyzing a single data set across a number of settings, it has limited utility as a general purpose clustering evaluation metric for use across disparate clusterings of disparate data sets.</S>
  			<S sid="149" ssid="95">Our homogeneity (h) and completeness (c) terms both range over [0,1] and are completely n-invariant andk?-invariant.</S>
  			<S sid="150" ssid="96">Furthermore, measuring each as a ra tio of bit lengths has greater intuitive appeal than a more opportunistic normalization.</S>
  			<S sid="151" ssid="97">V-measure has another advantage as a clusteringevaluation measure over V I and Q0.</S>
  			<S sid="152" ssid="98">By evaluating homogeneity and completeness in a symmetrical, complementary manner, the calculation of V measure makes their relationship clearly observable.Separate analyses of homogeneity and completeness are not possible with any other cluster evalu ation measure.</S>
  			<S sid="153" ssid="99">Moreover, by using the harmonic mean to combine homogeneity and completeness, V-measure is unique in that it can also prioritize one criterion over another, depending on the clustering task and goals.</S>
  	</SECTION>
  	<SECTION title="Comparing Evaluation Measures. " number="4">
  			<S sid="154" ssid="1">Dom (2001) describes a parametric technique for generating example clustering solutions.</S>
  			<S sid="155" ssid="2">He then proceeds to define five ?desirable properties?</S>
  			<S sid="156" ssid="3">that clustering accuracy measures should display, basedon the parameters used to generate the clustering solution.</S>
  			<S sid="157" ssid="4">To compare V-measure more directly to alter native clustering measures, we evaluate V-measure and other measures against these and two additional desirable properties.The parameters used in generating a clustering so lution are as follows.</S>
  			<S sid="158" ssid="5">|C| The number of classes ? |K| The number of clusters ? |Knoise| Number of ?noise?</S>
  			<S sid="159" ssid="6">clusters; |Knoise| &lt; |K| ? |Cnoise| Number of ?noise?</S>
  			<S sid="160" ssid="7">classes; |Cnoise| &lt; |C| ? ?</S>
  			<S sid="161" ssid="8">Error probability; ? = ?1 + ?2 + ?3.</S>
  			<S sid="162" ssid="9">? ?1 The error mass within ?useful?</S>
  			<S sid="163" ssid="10">class-cluster pairs ? ?2 The error mass within noise clusters ? ?3 The error mass within noise classes The construction of a clustering solution begins with a matching of ?useful?</S>
  			<S sid="164" ssid="11">clusters to ?useful?</S>
  			<S sid="165" ssid="12">classes3.</S>
  			<S sid="166" ssid="13">There are |Ku| = |K| ? |Knoise| ?useful?</S>
  			<S sid="167" ssid="14">clusters and |Cu| = |C| ? |Cnoise| ?useful?</S>
  			<S sid="168" ssid="15">classes.</S>
  			<S sid="169" ssid="16">The claim is useful classes and clusters are matched to each other and matched pairs contain more data points than unmatched pairs.</S>
  			<S sid="170" ssid="17">Probability mass of1 ? ?</S>
  			<S sid="171" ssid="18">is evenly distributed across each match.</S>
  			<S sid="172" ssid="19">Er ror mass of ?1 is evenly distributed across each pair 3The operation of this matching is omitted in the interest of space.</S>
  			<S sid="173" ssid="20">Interested readers should see (Dom, 2001).</S>
  			<S sid="174" ssid="21">415 of non-matching useful class/cluster pairs.</S>
  			<S sid="175" ssid="22">Noise clusters are those that contain data points equally from each cluster.</S>
  			<S sid="176" ssid="23">Error mass of ?2 is distributed across every ?noise?-cluster/ ?useful?-class pair.</S>
  			<S sid="177" ssid="24">We extend the parameterization technique described in (Dom, 2001) in with |Cnoise| and ?3.</S>
  			<S sid="178" ssid="25">Noise classes are those that contain data points equally from each cluster.</S>
  			<S sid="179" ssid="26">Error mass of ?3 is distributed across every?useful?-cluster/?noise?-class pair.</S>
  			<S sid="180" ssid="27">An example so lution, along with its generating parameters is given in Figure 3.</S>
  			<S sid="181" ssid="28">C1 C2 C3 Cnoise1 K1 12 12 2 3 K2 2 2 12 3 Knoise1 4 4 4 0 Figure 3: Sample parametric clustering solution with n = 60, |K| = 3, |Knoise| = 1, |C| = 3, |Cnoise| = 1, ?1 = .1, ?2 = .2, ?3 = .1 The desirable properties proposed by Dom aregiven as P1-P5 in Table 1.</S>
  			<S sid="182" ssid="29">We include two additional properties (P6,P7) relating the examined mea sure value to the number of ?noise?</S>
  			<S sid="183" ssid="30">classes and ?3.</S>
  			<S sid="184" ssid="31">P1 For |Ku| &lt; |C| and ?|Ku| ?</S>
  			<S sid="185" ssid="32">(|C| ? |Ku|), ?M ?|Ku| &gt; 0 P2 For |Ku| ? |C|, ?M?|Ku| &lt; 0 P3 ?M?|Knoise| &lt; 0, if ?2 &gt; 0 P4 ?M??1 ? 0, with equality only if |Ku| = 1 P5 ?M??2 ? 0, with equality only if |Knoise| = 0 P6 ?M?|Cnoise| &lt; 0, if ?3 &gt; 0 P7 ?M??3 ? 0, with equality only if |Cnoise| = 0 Table 1: Desirable Properties of a cluster evaluation measure MTo evaluate how different clustering measures satisfy each of these properties, we systematically var ied each parameter, keeping |C| = 5 fixed.</S>
  			<S sid="186" ssid="33">|Ku|: 10 values: 2, 3,.</S>
  			<S sid="187" ssid="34">, 11 ? |Knoise|: 7 values: 0, 1,.</S>
  			<S sid="188" ssid="35">, 6 ? |Cnoise|: 7 values: 0, 1,.</S>
  			<S sid="189" ssid="36">, 6 ? ?1: 4 values: 0, 0.033, 0.066, 0.1 ? ?2: 4 values: 0, 0.066, 0.133, 0.2 ? ?3: 4 values: 0, 0.066, 0.133, 0.2 We evaluated the behavior of V-Measure, Rand, Mirkin, Fowlkes-Mallows, Gamma, Jaccard, VI,Q0, F-Measure against the desirable properties P1 P74.</S>
  			<S sid="190" ssid="37">Based on the described systematic modificationof each parameter, only V-measure, VI and Q0 empirically satisfy all of P1-P7 in all experimental con ditions.</S>
  			<S sid="191" ssid="38">Full results reporting how frequently each evaluated measure satisfied the properties based on these experiments can be found in table 2.All evaluated measures satisfy P4 and P7.</S>
  			<S sid="192" ssid="39">However, Rand, Mirkin, Fowlkes-Mallows, Gamma, Jac card and F-Measure all fail to satisfy P3 and P6 inat least one experimental configuration.</S>
  			<S sid="193" ssid="40">This indi cates that the number of ?noise?</S>
  			<S sid="194" ssid="41">classes or clusterscan be increased without reducing any of these mea sures.</S>
  			<S sid="195" ssid="42">This implies a computational obliviousness topotentially significant aspects of an evaluated clus tering solution.</S>
  	</SECTION>
  	<SECTION title="Applying V-measure. " number="5">
  			<S sid="196" ssid="1">In this section, we present two clustering experiments.</S>
  			<S sid="197" ssid="2">We describe a document clustering experiment and evaluate its results using V-measure, high lighting the interaction between homogeneity and completeness.</S>
  			<S sid="198" ssid="3">Second, we present a pitch accent type clustering experiment.</S>
  			<S sid="199" ssid="4">We present results fromboth of these experiments in order to show how V measure can be used to drawn comparisons across data sets.</S>
  			<S sid="200" ssid="5">5.1 Document Clustering.</S>
  			<S sid="201" ssid="6">Clustering techniques have been used widely to sort documents into topic clusters.</S>
  			<S sid="202" ssid="7">We reproduce such an experiment here to demonstrate the usefulnessof V-measure.</S>
  			<S sid="203" ssid="8">Using a subset of the TDT-4 cor pus (Strassel and Glenn, 2003) (1884 English newswire and broadcast news documents manually la beled with one of 12 topics), we ran clustering experiments using k-means clustering (McQueen, 1967) and evaluated the results using V-Measure,VI and Q0 ? those measures that satisfied the desirable properties defined in section 4.</S>
  			<S sid="204" ssid="9">The top ics and relative distributions are as follows: Acts 4The inequalities in the desirable properties are inverted inthe evaluation of VI, Q0 and Mirkin as they are defined as dis tance, as opposed to similarity, measures.</S>
  			<S sid="205" ssid="10">416 Property Rand Mirkin Fowlkes ? Jaccard F-measure Q0 VI V-Measure P1 0.18 0.22 1.0 1.0 1.0 1.0 1.0 1.0 1.0 P2 1.0 1.0 0.76 1.0 0.89 0.98 1.0 1.0 1.0 P3 0.0 0.0 0.30 0.19 0.21 0.0 1.0 1.0 1.0 P4 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 P5 0.50 0.57 1.0 1.0 1.0 1.0 1.0 1.0 1.0 P6 0.20 0.20 0.41 0.26 0.52 0.87 1.0 1.0 1.0 P7 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 Table 2: Rates of satisfaction of desirable propertiesof Violence/War (22.3%), Elections (14.4%), Diplomatic Meetings (12.9%), Accidents (8.75%), Natural Disasters (7.4%), Human Interest (6.7%), Scan dals (6.5%), Legal Cases (6.4%), Miscellaneous (5.3%), Sports (4.7), New Laws (3.2%), Science and Discovery (1.4%).We employed stemmed (Porter, 1980), tf*idf weighted term vectors extracted for each document as the clustering space for these experiments, which yielded a very high dimension space.</S>
  			<S sid="206" ssid="11">To reduce this dimensionality, we performed a simple feature selection procedure including in the feature vector only those terms that represented the highest tf*idf value for at least one data point.</S>
  			<S sid="207" ssid="12">This resulted in a feature vector containing 484 tf*idf values for each document.</S>
  			<S sid="208" ssid="13">Results from k-means clustering are are shown in Figure 4.</S>
  			<S sid="209" ssid="14">0 0.1 0.2 0.3 0.4 0.5 1 10 100 1000 3 3.5 4 4.5 5 5.5V m ea su re a nd Q 2 va lue s VI v al ue s number of clusters V-Measure VI Q2 Figure 4: Results of document clustering measured by V-Measure, VI and Q2 The first observation that can be drawn from these results is the degree to which VI is dependent on the number of clusters (k).</S>
  			<S sid="210" ssid="15">This dependency severelylimits the usefulness of VI: it is inappropriate in selecting an appropriate parameter for k or for evaluating the distance between clustering solutions gen erated using different values of k. V-measure and Q2 demonstrate similar behavior in evaluating these experimental results.</S>
  			<S sid="211" ssid="16">They both reach a maximal value with 35 clusters, however, Q2shows a greater descent as the number of clusters in creases.</S>
  			<S sid="212" ssid="17">We will discuss this quality in greater detail in section 5.2.</S>
  			<S sid="213" ssid="18">5.2 Pitch Accent Clustering.</S>
  			<S sid="214" ssid="19">Pitch accent is how speakers of many languages make a word intonational prominent.</S>
  			<S sid="215" ssid="20">In mostpitch accent languages, words can also be accented in different ways to convey different meanings (Hirschberg, 2002).</S>
  			<S sid="216" ssid="21">In the ToBI labeling con ventions for Standard American English (Silvermanet al, 1992), for example, there are five different ac cent types (H*, L*, H+!H*, L+H*, L*+H).</S>
  			<S sid="217" ssid="22">We extracted a number of acoustic features from accented words within the read portion of the Boston Directions Corpus (BDC) (Nakatani et al, 1995) andexamined how well clustering in these acoustic dimensions correlates to manually annotated pitch ac cent types.</S>
  			<S sid="218" ssid="23">We obtained a very skewed distribution,with a majority of H* pitch accents.5 We there fore included only a randomly selected 10% sample of H* accents, providing a more even distribution of pitch accent types for clustering: H* (54.4%), L*(32.1%), L+H* (26.5%), L*+H (2.8%), H+!H* (2.1%).We extracted ten acoustic features from each ac cented word to serve as the clustering space for this experiment.</S>
  			<S sid="219" ssid="24">Using Praat?s (Boersma, 2001) Get Pitch (ac)... function, we calculated the mean F0and ?F0, as well as z-score speaker normalized ver sions of the same.</S>
  			<S sid="220" ssid="25">We included in the feature vector the relative location of the maximum pitch value inthe word as well as the distance between this max5Pitch accents containing a high tone may also be downstepped, or spoken in a compressed pitch range.</S>
  			<S sid="221" ssid="26">Here we col lapsed all DOWNSTEPPED instances of each pitch accent with the corresponding non-downstepped instances.</S>
  			<S sid="222" ssid="27">417 imum and the point of maximum intensity.</S>
  			<S sid="223" ssid="28">Finally, we calculated the raw and speaker normalized slope from the start of the word to the maximum pitch, and from the maximum pitch to the end of the word.</S>
  			<S sid="224" ssid="29">Using this feature vector, we performed k-meansclustering and evaluate how successfully these di mensions represent differences between pitch accenttypes.</S>
  			<S sid="225" ssid="30">The resulting V-measure, VI and Q0 calcula tions are shown in Figure 5.</S>
  			<S sid="226" ssid="31">0 0.05 0.1 0.15 0.2 1 10 100 1000 2 3 4 5 6 7 8V m ea su re a nd Q 2 va lue s VI v al ue s number of clusters VI V-measure Q2Figure 5: Results of pitch accent clustering mea sured by V-Measure, VI and Q0 In evaluating the results from these experiments,Q2 and V-measure reveal considerably different behaviors.</S>
  			<S sid="227" ssid="32">Q2 shows a maximum at k = 10, and de scends at k increases.</S>
  			<S sid="228" ssid="33">This is an artifact of the MDLprinciple.</S>
  			<S sid="229" ssid="34">Q2 makes the claim that a clustering so lution based on fewer clusters is preferable to one using more clusters, and that the balance between the number of clusters and the conditional entropy, H(C|K), should be measured in terms of codinglength.</S>
  			<S sid="230" ssid="35">With V-measure, we present a different argu ment.</S>
  			<S sid="231" ssid="36">We contend that the a high value of k does notinherently reduce the goodness of a clustering solu tion.</S>
  			<S sid="232" ssid="37">Using these results as an example, we find that at approximately 30 clusters an increase of clusters translates to an increase in V-Measure.</S>
  			<S sid="233" ssid="38">This is due to an increased homogeneity (H(C|K)H(C) ) and a relatively stable completeness (H(K|C)H(K) ).</S>
  			<S sid="234" ssid="39">That is, inclusion of more clusters leads to clusters with a more skewedwithin-cluster distribution and a equivalent distribu tion of cluster memberships within classes.</S>
  			<S sid="235" ssid="40">This is intuitively preferable ? one criterion is improved, the other is not reduced ? despite requiring additionalclusters.</S>
  			<S sid="236" ssid="41">This is an instance in which the MDL principle limits the usefulness of Q2.</S>
  			<S sid="237" ssid="42">We again (see sec tion 5.1) observe the close dependency of VI and k.Moreover, in considering figures 5 and 4, simulta neously, we see considerably higher values achieved by the document clustering experiments.</S>
  			<S sid="238" ssid="43">Given the na??ve approaches taken in these experiments, this is expected ? and even desired ? given the previous work on these tasks: document clustering has been notably more successfully applied than pitch accent clustering.</S>
  			<S sid="239" ssid="44">These examples allow us to observe how transparently V-measure can be used to compare the behavior across distinct data sets.</S>
  	</SECTION>
  	<SECTION title="Conclusion. " number="6">
  			<S sid="240" ssid="1">We have presented a new external cluster evaluation measure, V-measure, and compared it with existing clustering evaluation measures.</S>
  			<S sid="241" ssid="2">V-measure is basedupon two criteria for clustering usefulness, homogeneity and completeness, which capture a clustering solution?s success in including all and only data points from a given class in a given cluster.</S>
  			<S sid="242" ssid="3">We havealso demonstrated V-measure?s usefulness in com paring clustering success across different domainsby evaluating document and pitch accent cluster ing solutions.</S>
  			<S sid="243" ssid="4">We believe that V-measure addressessome of the problems that affect other cluster measures.</S>
  			<S sid="244" ssid="5">1) It evaluates a clustering solution indepen dent of the clustering algorithm, size of the data set, number of classes and number of clusters.</S>
  			<S sid="245" ssid="6">2) It does not require its user to map each cluster to a class.Therefore, it only evaluates the quality of the clustering, not a post-hoc class-cluster mapping.</S>
  			<S sid="246" ssid="7">3) It eval uates the clustering of every data point, avoiding the ?problem of matching?.</S>
  			<S sid="247" ssid="8">4) By evaluating the criteria of both homogeneity and completeness, V-measure is more comprehensive than those that evaluate onlyone.</S>
  			<S sid="248" ssid="9">5) Moreover, by evaluating these criteria separately and explicitly, V-measure can serve as an el egant diagnositic tool providing greater insight into clustering behavior.</S>
  			<S sid="249" ssid="10">Acknowledgments The authors thank Kapil Thadani, Martin Jansche and Sasha Blair-Goldensohn and for their feedback.</S>
  			<S sid="250" ssid="11">This work was funded in part by the DARPA GALE program under a subcontract to SRI International.</S>
  			<S sid="251" ssid="12">418</S>
  	</SECTION>
  </PAPER>
  