ClassificationMeasures.java
001 /**
002  *  Copyright (c) 1995-2012, The University of Sheffield. See the file
003  *  COPYRIGHT.txt in the software or at http://gate.ac.uk/gate/COPYRIGHT.txt
004  *
005  *  This file is part of GATE (see http://gate.ac.uk/), and is free
006  *  software, licenced under the GNU Library General Public License,
007  *  Version 2, June 1991 (in the distribution as file licence.html,
008  *  and also available at http://gate.ac.uk/gate/licence.html).
009  *
010  *  $Id: ContingencyTable.java 12125 2010-01-04 14:44:43Z ggorrell $
011  */
012 
013 package gate.util;
014 
015 import gate.AnnotationSet;
016 import gate.Annotation;
017 
018 import java.text.NumberFormat;
019 import java.util.ArrayList;
020 import java.util.Arrays;
021 import java.util.Collection;
022 import java.util.Collections;
023 import java.util.HashMap;
024 import java.util.HashSet;
025 import java.util.List;
026 import java.util.Locale;
027 import java.util.SortedSet;
028 import java.util.TreeSet;
029 
030 
031 /**
032  * Given two annotation sets, a type and a feature,
033  * compares the feature values. It finds matching annotations and treats
034  * the feature values as classifications. Its purpose is to calculate the
035  * extent of agreement between the feature values in the two annotation
036  * sets. It computes observed agreement and Kappa measures.
037  */
038 public class ClassificationMeasures {
039   
040   /** Array of dimensions categories * categories. */
041   private float[][] confusionMatrix;
042   
043   /** Cohen's kappa. */
044   private float kappaCohen = 0;
045   
046   /** Scott's pi or Siegel & Castellan's kappa */
047   private float kappaPi = 0;
048   
049   private boolean isCalculatedKappas = false;
050   
051   /** List of feature values that are the labels of the confusion matrix */
052   private TreeSet<String> featureValues;
053 
054   public ClassificationMeasures() {
055     // empty constructor
056   }
057 
058   /**
059    * Portion of the instances on which the annotators agree.
060    @return a number between 0 and 1. 1 means perfect agreements.
061    */
062   public float getObservedAgreement()
063   {
064     float agreed = getAgreedTrials();
065     float total = getTotalTrials();
066     if(total>0) {
067       return agreed/total;
068     else {
069       return 0;
070     }
071   }
072 
073   /**
074    * Kappa is defined as the observed agreements minus the agreement
075    * expected by chance.
076    * The Cohen’s Kappa is based on the individual distribution of each
077    * annotator.
078    @return a number between -1 and 1. 1 means perfect agreements.
079    */
080   public float getKappaCohen()
081   {
082     if(!isCalculatedKappas){
083       computeKappaPairwise();
084       isCalculatedKappas = true;
085     }
086     return kappaCohen;
087   }
088 
089   /**
090    * Kappa is defined as the observed agreements minus the agreement
091    * expected by chance.
092    * The Siegel & Castellan’s Kappa is based on the assumption that all the
093    * annotators have the same distribution.
094    @return a number between -1 and 1. 1 means perfect agreements.
095    */
096   public float getKappaPi()
097   {
098     if(!isCalculatedKappas){
099       computeKappaPairwise();
100       isCalculatedKappas = true;
101     }
102     return kappaPi;
103   }
104   
105   /**
106    * To understand exactly which types are being confused with which other
107    * types you will need to view this array in conjunction with featureValues,
108    * which gives the class labels (annotation types) in the correct order.
109    @return confusion matrix describing how annotations in one
110    * set are classified in the other and vice versa
111    */
112   public float[][] getConfusionMatrix(){
113       return confusionMatrix.clone();
114   }
115   
116   /**
117    * This is necessary to make sense of the confusion matrix.
118    @return list of annotation types (class labels) in the
119    * order in which they appear in the confusion matrix
120    */
121   public SortedSet<String> getFeatureValues(){
122     return Collections.unmodifiableSortedSet(featureValues);
123   }
124   
125   /**
126    * Create a confusion matrix in which annotations of identical span
127    * bearing the specified feature name are compared in terms of feature value.
128    * Compiles list of classes (feature values) on the fly.
129    *
130    @param aS1 annotation set to compare to the second
131    @param aS2 annotation set to compare to the first
132    @param type annotation type containing the features to compare
133    @param feature feature name whose values will be compared
134    @param verbose message error output when ignoring annotations
135    */
136   public void calculateConfusionMatrix(AnnotationSet aS1, AnnotationSet aS2,
137     String type, String feature, boolean verbose)
138   {   
139     // We'll accumulate a list of the feature values (a.k.a. class labels)
140     featureValues = new TreeSet<String>();
141     
142     // Make a hash of hashes for the counts.
143     HashMap<String, HashMap<String, Float>> countMap =
144       new HashMap<String, HashMap<String, Float>>();
145     
146     // Get all the annotations of the correct type containing
147     // the correct feature
148     HashSet<String> featureSet = new HashSet<String>();
149     featureSet.add(feature);
150     AnnotationSet relevantAnns1 = aS1.get(type, featureSet);
151     AnnotationSet relevantAnns2 = aS2.get(type, featureSet);
152     
153     // For each annotation in aS1, find the match in aS2
154     for (Annotation relevantAnn1 : relevantAnns1) {
155 
156       // First we need to check that this annotation is not identical in span
157       // to anything else in the same set. Duplicates should be excluded.
158       List<Annotation> dupeAnnotations = new ArrayList<Annotation>();
159       for (Annotation aRelevantAnns1 : relevantAnns1) {
160         if (aRelevantAnns1.equals(relevantAnn1)) { continue}
161         if (aRelevantAnns1.coextensive(relevantAnn1)) {
162           dupeAnnotations.add(aRelevantAnns1);
163           dupeAnnotations.add(relevantAnn1);
164         }
165       }
166 
167       if (dupeAnnotations.size() 1) {
168         if (verbose) {
169           Out.prln("ClassificationMeasures: " +
170             "Same span annotations in set 1 detected! Ignoring.");
171           Out.prln(Arrays.toString(dupeAnnotations.toArray()));
172         }
173       else {
174         // Find the match in as2
175         List<Annotation>  coextensiveAnnotations = new ArrayList<Annotation>();
176         for (Annotation relevantAnn2 : relevantAnns2) {
177           if (relevantAnn2.coextensive(relevantAnn1)) {
178             coextensiveAnnotations.add(relevantAnn2);
179           }
180         }
181 
182         if (coextensiveAnnotations.size() == 0) {
183           if (verbose) {
184             Out.prln("ClassificationMeasures: Annotation in set 1 " +
185               "with no counterpart in set 2 detected! Ignoring.");
186             Out.prln(relevantAnn1.toString());
187           }
188         else if (coextensiveAnnotations.size() == 1) {
189 
190           // What are our feature values?
191           String featVal1 = String.valueOf(relevantAnn1.getFeatures().get(feature));
192           String featVal2 = String.valueOf(coextensiveAnnotations.get(0).getFeatures().get(feature));
193 
194           // Make sure both are present in our feature value list
195           featureValues.add(featVal1);
196           featureValues.add(featVal2);
197 
198           // Update the matrix hash of hashes
199           // Get the right hashmap for the as1 feature value
200           HashMap<String, Float> subHash = countMap.get(featVal1);
201           if (subHash == null) {
202             // This is a new as1 feature value, since it has no subhash yet
203             HashMap<String, Float> subHashForNewAS1FeatVal =
204               new HashMap<String, Float>();
205 
206             // Since it is a new as1 feature value, there can be no existing
207             // as2 feature values paired with it. So we make a new one for this
208             // as2 feature value
209             subHashForNewAS1FeatVal.put(featVal2, (float1);
210 
211             countMap.put(featVal1, subHashForNewAS1FeatVal);
212           else {
213             // Increment the count
214             Float count = subHash.get(featVal2);
215             if (count == null) {
216               subHash.put(featVal2, (float1);
217             else {
218               subHash.put(featVal2, (floatcount.intValue() 1);
219             }
220 
221           }
222         else if (coextensiveAnnotations.size() 1) {
223           if (verbose) {
224             Out.prln("ClassificationMeasures: " +
225               "Same span annotations in set 2 detected! Ignoring.");
226             Out.prln(Arrays.toString(coextensiveAnnotations.toArray()));
227           }
228         }
229       }
230     }
231     
232     // Now we have this hash of hashes, but the calculation implementations
233     // require an array of floats. So for now we can just translate it.
234     confusionMatrix = convert2DHashTo2DFloatArray(countMap, featureValues);
235   }
236   
237   /**
238    * Given a list of ClassificationMeasures, this will combine to make
239    * a megatable. Then you can use kappa getters to get micro average
240    * figures for the entire set.
241    @param tables tables to combine
242    */
243   public ClassificationMeasures(Collection<ClassificationMeasures> tables) {
244     /* A hash of hashes for the actual values.
245      * This will later be converted to a 2D float array for
246      * compatibility with the existing code. */
247     HashMap<String, HashMap<String, Float>> countMap =
248       new HashMap<String, HashMap<String, Float>>();
249     
250     /* Make a new feature values set which is a superset of all the others */
251     TreeSet<String> newFeatureValues = new TreeSet<String>();
252     
253     /* Now we are going to add each new contingency table in turn */
254 
255     for (ClassificationMeasures table : tables) {
256       int it1index = 0;
257       for (String featureValue1 : table.featureValues) {
258         newFeatureValues.add(featureValue1);
259         int it2index = 0;
260         for (String featureValue2 : table.featureValues) {
261 
262           /* So we have the labels of the count we want to add */
263           /* What is the value we want to add? */
264           Float valtoadd = table.confusionMatrix[it1index][it2index];
265 
266           HashMap<String, Float> subHash = countMap.get(featureValue1);
267           if (subHash == null) {
268             /* This is a new as1 feature value, since it has no subhash yet */
269             HashMap<String, Float> subHashForNewAS1FeatVal =
270               new HashMap<String, Float>();
271 
272             /* Since it is a new as1 feature value, there can be no existing
273              *  as2 feature values paired with it. So we make a new one for this
274              *  as2 feature value */
275             subHashForNewAS1FeatVal.put(featureValue2, valtoadd);
276 
277             countMap.put(featureValue1, subHashForNewAS1FeatVal);
278           else {
279             /* Increment the count */
280             Float count = subHash.get(featureValue2);
281             if (count == null) {
282               subHash.put(featureValue2, valtoadd);
283             else {
284               subHash.put(featureValue2, count.intValue() + valtoadd);
285             }
286           }
287           it2index++;
288         }
289         it1index++;
290       }
291     }
292     
293     confusionMatrix = convert2DHashTo2DFloatArray(countMap, newFeatureValues);
294     featureValues = newFeatureValues;
295     isCalculatedKappas = false;
296   }
297   
298   /** Compute Cohen's and Pi kappas for two annotators.
299    */
300   protected void computeKappaPairwise()
301   {
302     // Compute the agreement
303     float observedAgreement = getObservedAgreement();
304     int numCats = featureValues.size();
305     // compute the agreement by chance
306     // Get the marginal sum for each annotator
307     float[] marginalArrayC = new float[numCats];
308     float[] marginalArrayR = new float[numCats];
309     float totalSum = 0;
310     for(int i = 0; i < numCats; ++i) {
311       float sum = 0;
312       for(int j = 0; j < numCats; ++j)
313         sum += confusionMatrix[i][j];
314       marginalArrayC[i= sum;
315       totalSum += sum;
316       sum = 0;
317       for(int j = 0; j < numCats; ++j)
318         sum += confusionMatrix[j][i];
319       marginalArrayR[i= sum;
320     }
321     
322     // Compute Cohen's p(E)
323     float pE = 0;
324     if(totalSum > 0) {
325       float doubleSum = totalSum * totalSum;
326       for(int i = 0; i < numCats; ++i)
327         pE += (marginalArrayC[i* marginalArrayR[i]) / doubleSum;
328     }
329     
330     // Compute Cohen's Kappa
331     if (pE == 1.0F) { // prevent division by zero
332       kappaCohen = 1.0F;
333     }
334     else if (totalSum > 0
335       kappaCohen = (observedAgreement - pE(1.0F - pE);
336     else kappaCohen = 0;
337     
338     // Compute S&C's chance agreement
339     pE = 0;
340     if(totalSum > 0) {
341       float doubleSum = * totalSum;
342       for(int i = 0; i < numCats; ++i) {
343         float p = (marginalArrayC[i+ marginalArrayR[i]) / doubleSum;
344         pE += p * p;
345       }
346     }
347     
348     if (pE == 1.0F) { // prevent division by zero
349       kappaPi = 1.0F;
350     }
351     else if (totalSum > 0)
352       kappaPi = (observedAgreement - pE(1.0F - pE);
353     else kappaPi = 0;
354     
355     // Compute the specific agreement for each label using marginal sums
356     float[][] sAgreements = new float[numCats][2];
357     for(int i = 0; i < numCats; ++i) {
358       if(marginalArrayC[i+ marginalArrayR[i]>0
359         sAgreements[i][0(* confusionMatrix[i][i])
360           (marginalArrayC[i+ marginalArrayR[i]);
361       else sAgreements[i][00.0f;
362       if(* totalSum - marginalArrayC[i- marginalArrayR[i]>0)
363         sAgreements[i][1((totalSum - marginalArrayC[i]
364           - marginalArrayR[i+ confusionMatrix[i][i]))
365           (* totalSum - marginalArrayC[i- marginalArrayR[i]);
366       else sAgreements[i][10.0f;
367     }
368   }
369   
370   /** Gets the number of annotations for which the two annotation sets
371    * are in agreement with regards to the annotation type.
372    @return Number of agreed trials
373    */
374   public float getAgreedTrials(){
375     float sumAgreed = 0;
376     for(int i = 0; i < featureValues.size(); ++i) {
377       sumAgreed += confusionMatrix[i][i];
378     }
379     return sumAgreed;
380   }
381   
382   /** Gets the total number of annotations in the two sets.
383    * Note that only matched annotations (identical span) are
384    * considered.
385    @return Number of trials
386    */
387   public float getTotalTrials(){
388     float sumTotal = 0;
389     for(int i = 0; i < featureValues.size(); ++i) {
390       for(int j = 0; j < featureValues.size(); ++j) {
391         sumTotal += confusionMatrix[i][j];
392       }
393     }
394     return sumTotal;
395   }
396   
397   /**
398    @param title matrix title
399    @return confusion matrix as a list of list of String
400    */
401   public List<List<String>> getConfusionMatrix(String title) {
402     List<List<String>> matrix = new ArrayList<List<String>>();
403     List<String> row = new ArrayList<String>();
404     row.add(" ");
405     matrix.add(row)// spacer
406     row = new ArrayList<String>();
407     row.add(title);
408     matrix.add(row)// title
409     SortedSet<String> features = new TreeSet<String>(getFeatureValues());
410     row = new ArrayList<String>();
411     row.add("A \\ B");
412     row.addAll(features);
413     matrix.add(row)// heading horizontal
414     for (float[] confusionValues : getConfusionMatrix()) {
415       row = new ArrayList<String>();
416       row.add(features.first())// heading vertical
417       features.remove(features.first());
418       for (float confusionValue : confusionValues) {
419         row.add(String.valueOf((intconfusionValue));
420       }
421       matrix.add(row)// confusion values
422     }
423     return matrix;
424   }
425 
426   public List<String> getMeasuresRow(Object[] measures, String documentName) {
427     NumberFormat f = NumberFormat.getInstance(Locale.ENGLISH);
428     f.setMaximumFractionDigits(2);
429     f.setMinimumFractionDigits(2);
430     List<String> row = new ArrayList<String>();
431     row.add(documentName);
432     row.add(String.valueOf((intgetAgreedTrials()));
433     row.add(String.valueOf((intgetTotalTrials()));
434     for (Object object : measures) {
435       String measure = (Stringobject;
436       if (measure.equals("Observed agreement")) {
437         row.add(f.format(getObservedAgreement()));
438       }
439       if (measure.equals("Cohen's Kappa")) {
440         float result = getKappaCohen();
441         row.add(Float.isNaN(result"" : f.format(result));
442       }
443       if (measure.equals("Pi's Kappa")) {
444         float result = getKappaPi();
445         row.add(Float.isNaN(result"" : f.format(result));
446       }
447     }
448     return row;
449   }
450 
451   /**
452    * Convert between two formats of confusion matrix.
453    * A hashmap of hashmaps is easier to populate but an array is better for
454    * matrix computation.
455    @param countMap count for each label as in confusion matrix
456    @param featureValues sorted set of labels that will define the dimensions
457    @return converted confusion matrix as an 2D array
458    */
459   private float[][] convert2DHashTo2DFloatArray(
460     HashMap<String, HashMap<String, Float>> countMap,
461     TreeSet<String> featureValues)
462   {
463     int dimensionOfContingencyTable = featureValues.size();
464     float[][] matrix =
465       new float[dimensionOfContingencyTable][dimensionOfContingencyTable];
466     int i=0;
467     int j=0;
468     for (String featureValue1 : featureValues) {
469       HashMap<String, Float> hashForThisAS1FeatVal =
470         countMap.get(featureValue1);
471       j = 0;
472       for (String featureValue2 : featureValues) {
473         Float count = null;
474         if (hashForThisAS1FeatVal != null) {
475           count = hashForThisAS1FeatVal.get(featureValue2);
476         }
477         if (count != null) {
478           matrix[i][j= count;
479         else {
480           matrix[i][j0;
481         }
482         j++;
483       }
484       i++;
485     }    
486     return matrix;
487   }
488   
489 }