#!/usr/bin/perl -s
sub Help {
    print <<HELP;
Synopsis:
    Given a classification result file, calculate the precision, recall,
    and F1 values in document-wise and category-wise averages.
    Each line in the result file should have 3 columns separated by ' : ':
        "document_ID : System_generate_output : Provided_Answer"
    The categories in the system output are separated by tabs: "\\t" and each
    category may be followed by a semi-colon and then a score. Example:
        Doc_1 : cat:8 dog:4 : cat duck
        Doc_2 : goat dog : cat

Syntax:
        perl -s prf.pl [-Odetail] [-OCats=n] [-OSort=1,0] result_file.txt
    where option
        -Odetail : report averages for each category
        -OCats=n : calculate averages only for n categories
        -OSort=1,0 : 1 = Sort by DESC, 0 = Sort by ASC

Note: These averages (except the document-wise averages, which are defined
    here by Yuen-Hsien Tseng) are calculated following the way described by
    Yiming Yang in the ddlbeta discussion list. (See attached text)

Author: Yuen-Hsien Tseng
Date: September 10, 2002
HELP
exit;
}
    &Help() if $help or $h or @ARGV == 0;
    my($DocP, $DocR, $DocF, $N, %CatDoc);# %CatDoc: number of documents per Cat
    my($N, $Nerr);
    while (<>) { # read each line from each input file successively
        chomp;
        next if /^\s*$|^#/; # escape blank and comment lines
        next if $_ !~ / : /; # escape lines without correct format
        ($docID, $Output, $Ans) = split / : /, $_;
        $N++;
        @Out = split /\t/, $Output; # System output
        foreach(@Out){ s/:.*//; } # delete the score of each category, if any
        @Ans = split /\t/, $Ans; # provided Answer
#print "@Out : @Ans\n";
        %Ans = (); %Out = ();
        foreach $out (@Out) { $Out{$out}=1; } # Set hash for ease of lookin up
        foreach $ans (@Ans) { $Ans{$ans}=1; $CatDoc{$ans}++; }

# Test if there are mismatches
	$error = 0;
        foreach $ans (@Ans) { $error = 1 if not $Out{$ans}; }
        foreach $out (@Out) { $error = 1 if not $Ans{$out}; }
#print "$docID : $Output : $Ans\n" if $error;
        $Nerr++ if $error; # count the documents with categorization errors
        
        $hit = 0;
        foreach $ans (@Ans) { # Find TP and TN for category-wise microaverage
            if ($Out{$ans}) { $hit ++; $TP{$ans}++; # True positive
            } else { $FN{$ans} ++; } # False Negative
        }
        foreach $out (@Out) { # Accumulate TP and FP for microaverage
            if ($Ans{$out}) { # True positive, already accumulated
            } else { $FP{$out} ++; } # False Positive
        }
if (@Out == 0) { print "$docID has no system-generated categories\n"; exit; }
        $DocP += $hit / @Out; # accumulate P for document-wise average

        $DocR += $hit / @Ans;
    }

    foreach $c (keys %TP, keys %FP, keys %FN) { $AllCats{$c} = 1; }
#    foreach $c (keys %TP, keys %FN) { $AllCats{$c} = 1; }
    if ( $OSort == 1 )
    { @Cats = sort {$CatDoc{$a}<=>$CatDoc{$b}} keys %AllCats; }# sort ASC
    else
    { @Cats = sort {$CatDoc{$b} <=> $CatDoc{$a}} keys %AllCats; }# sort DEC
#print "Before: NumC=", scalar @Cats, "\n";
    $catP = $catR = $sumTP = $sumFN = $sumFP = $numC = 0;
    foreach $c (@Cats) {
            $out = $TP{$c} + $FP{$c};
            $ans = $TP{$c} + $FN{$c};
#            next if $ans == 0; # no P, R, F need to be computed
            $P = ($out)?&ts($TP{$c}/$out):0; # so that F=2PR/(P+R)=0 if R==0
            $R = ($ans)?&ts($TP{$c}/$ans):'Not Possible';
            $numC++;
print"$numC\tD=$CatDoc{$c}\tTP=$TP{$c}\tFP=$FP{$c}\tFN=$FN{$c}\tP=$P\tR=$R\t$c\n"if $Odetail;
# Next line is for macro-average
            $catP += ($P = $TP{$c} / $out) if($out > 0); # to avoid exception
            $catR += ($R = $TP{$c} / $ans) if($ans > 0); # to avoid exception
            $catF += 2*$P*$R/($P+$R) if ($P+$R)>0;
# Next line is for micro-average
            $sumTP += $TP{$c}; $sumFN += $FN{$c}; $sumFP += $FP{$c};
            last if $OCats == $numC; # stop calculation at top-n categories
    }

    print "\nDocuments with classification errors ($Nerr/$N)=", 
    	&ts($Nerr/$N, 4),"\n";
    print "N=$N, avgDocP=", &ts($P=$DocP/$N, 4),
    ", avgDocR=", &ts($R=$DocR/$N, 4),
    ", avgDocF=", &ts(2*$P*$R/($P+$R), 4), "\n";
    print "C=$numC, MicroP=", &ts($P=$sumTP/($sumTP+$sumFP), 4),
    ", MicroR=", &ts($R=$sumTP/($sumTP+$sumFN), 4),
    ", MicroF=", &ts(2*$P*$R/($P+$R), 4), "\n";
    print "C=$numC, MacroP=", &ts($P=$catP/$numC, 4),
    ", MacroR=", &ts($R=$catR/$numC, 4),
    ", MacroF=", &ts(2*$P*$R/($P+$R), 4),
    ", MacroF(sumF/C)=", &ts($catF/$numC, 4), "\n";
    exit;

# truncated score function
sub ts {
   my($x, $n) = @_;
   $n= 3 if not $n;
   return sprintf("%0.".$n."f", $x);
}



=Below is the message about the calculation of the averages

Subject: RE: macroaveraging
   Date: Fri, 24 May 2002 14:21:20 -0400
   From: Yiming Yang <yiming@cs.cmu.edu>
Reply-To: ddlbeta@scils.rutgers.edu
      To: ddlbeta@scils.rutgers.edu

Fabrizio,

It's a good question.  I am in a big hurry of catching up
a deadline so let me just give a brief answer.

You are right, when people use different actions for the
"undefined" cases, their results are not comparable.  And, the
actions in published results were sometimes not clearly defined.
So I take the chance to tell about what I did just in case.

In all the results I published, I did not use either "i" or "ii"
actions that you mentioned.  Instead, if the precision was not defined,
I set the F1 value to be zero; for the categories not in
the test set, no F1 was computed thus they are not counted in averaging.
In other words, recall was always defined for the test-set categories.  The
rationale for my choice is that a trivial classifier which say "no"
to every test document will have a perfect score in F1 for action "ii",
but such a system is totally useless.  Similarity, a system that tends to
say "no" for most of categories except a few (easier or common categories,
for example) is likely to have a high F1 score in macro-average for both
actions "i" and "ii", encouraging undesired bias of the system.

As a consequence, if someone uses action "i" or "ii" to evaluate a
classifier, their results would look better than they would be if using my
way of evaluation.

Best,

- Yiming


> -----Original Message-----
> From: owner-ddlbeta@scils.rutgers.edu
> [mailto:owner-ddlbeta@scils.rutgers.edu]On Behalf Of Fabrizio Sebastiani
> Sent: Thursday, May 23, 2002 4:53 AM
> To: ddlbeta@scils.rutgers.edu
> Subject: macroaveraging
>
>
> Hi all,
>
> I have a question on macroaveraging which might be of some interest
> to those who do use macroaveraging. When computing macroaveraged
> effectiveness across a set of categories, one issue is how to deal
> with categories for which the effectiveness measure of interest is
> undefined.  Specifically, for category i:
>
> a) precision, defined as Pr(i)=TP(i)\(TP(i)+FP(i)), is undefined when
> TP(i)+FP(i)=0, i.e. when the classifier says "no" to category i for
> all the test documents;
>
> b) recall, defined as Re(i)=TP(i)\(TP(i)+FN(i)), is undefined when
> TP(i)+FN(i)=0, i.e. when category i has no positive test example.
>
> In this case, there are two possible courses of actions, and they
> might both seem justified:
>
> i) macroaveraged precision is computed as the average of precision
> only on the categories for which precision is actually defined. The
> categories on which precision is undefined thus do not participate in
> the final score. Same for recall.
>
> ii) for computing macroaveraged precision, an "undefined" value for
> precision is transformed into a value of 1, with the plausible
> motivation that the classifier has never erroneously said "yes".
> Similarly, for computing macroaveraged recall, an "undefined" value
> for recall is transformed into a value of 1, with the plausible
> motivation that the classifier has never omitted to say "yes" when it
> should have said so.
>
> I realize that (unless this has escaped to me in particular cases; or
> unless there is a standard strategy I do not know of) we never say in
> our articles whether we have adopted strategy (i) or strategy (ii).
> Of course, values for e.g. macroaveraged F1 are usually higher if we
> adopt (ii); for instance, if we use the 115 Reuters-21578 categories
> that have at least one positive training example, 25 of them have no
> positive test example, so when using (ii) there are 25 more 1's to be
> contributed to macroaveraged recall.
>
> Quite by chance I have realized only now that two students of mine
> (Luigi Galavotti and Nicola Valdambrini) have implemented and used
> the two different strategies, so that the data that ended up in the
> work of the first (the ECDL-00 paper) adopts (ii) while the data that
> ended up in the work of the second (the CIKM-00 paper) adopted (i).
>
> It would thus be interesting that the people who have published
> macroaveraging results say which strategy they have used; and, in
> general, I would be happy to hear opinions in favour of one or the
> other.
>
> Cheers     Fabrizio
> --
>
> +-----------------------------------------------+
> | Fabrizio Sebastiani                           |
> | Istituto di Elaborazione dell'Informazione    |
> | Consiglio Nazionale delle Ricerche            |
> | Via Giuseppe Moruzzi, 1                       |
> | 56124 Pisa (ITALY)                            |
> |                                               |
> | Phone:  +39.050.3152892                       |
> | Fax:    +39.050.3152810                       |
> | E-mail: fabrizio@iei.pi.cnr.it                |
> | WWW:    http://faure.iei.pi.cnr.it/~fabrizio/ |
> +-----------------------------------------------+
=cut
