clusterscore.java

一个自然语言处理的Java开源工具包。LingPipe目前已有很丰富的功能

/*
 * LingPipe v. 3.5
 * Copyright (C) 2003-2008 Alias-i
 *
 * This program is licensed under the Alias-i Royalty Free License
 * Version 1 WITHOUT ANY WARRANTY, without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the Alias-i
 * Royalty Free License Version 1 for more details.
 *
 * You should have received a copy of the Alias-i Royalty Free License
 * Version 1 along with this program; if not, visit
 * http://alias-i.com/lingpipe/licenses/lingpipe-license-1.txt or contact
 * Alias-i, Inc. at 181 North 11th Street, Suite 401, Brooklyn, NY 11211,
 * [phone].
 */

package com.aliasi.cluster;

import com.aliasi.classify.PrecisionRecallEvaluation;

import com.aliasi.util.Collections;
import com.aliasi.util.Distance;
import com.aliasi.util.Tuple;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;


/**
 * A <code>ClusterScore</code> provides a range of cluster scoring
 * metrics for reference partitions versus response partitions.
 *
 * <P>Traditional evaluation measures for pairs of parititions involve
 * comparing the equivalence relations generated by the partitions
 * pointwise.  A partition defines an equivalence relation in the
 * usual way: a pair <code>(A,B)</code> is in the equivalence if there
 * is a cluster that contains both <code>A</code> and <code>B</code>.
 * Each element is assumed to be equal to itself.  A pair
 * <code>(A,B)</code> is a true positive if it is an equivalence in
 * the reference and response clustes, a false positive if it is in
 * the response but not the reference, and so on.  The resulting
 * precision-recall statistics over the relations is reported through
 * {@link #equivalenceEvaluation()}.
 *
 * <P>The scoring used for the Message Understanding Conferences is:
 *
 * <blockquote><code>
 * mucRecall(referencePartition,responsePartition)
 * <br> = <big><big>&Sigma;</big></big><sub><sub>c in referencePartition</sub></sub>
 *       (size(c) - overlap(c,responsePartition))
 * <br> / <big><big>&Sigma;</big></big><sub><sub>c in referencePartition</sub></sub>
 *       ( size(c) - 1 )
 * </code></blockquote>
 *
 * where <code>size(c)</code> is the number of elements in the
 * cluster <code>c</code>, and <code>overlap(c,responsePartition)</code>
 * is the number of clusters in the response partition that intersect
 * the cluster <code>c</code>.  Precision is defined dually by
 * reversing the roles of reference and response, and f-measure is defined
 * as usual.   Further details and examples can be found in:
 *
 * <blockquote>
 *   Marc Vilain, John Burger, John Aberdeen, Dennis Connolly, and
 *   Lynette Hirschman.
 *   1995.
 *   <a href="http://acl.ldc.upenn.edu/M/M95/M95-1005.pdf">A model-theoretic coreference scoring scheme.</a>
 *   In <i>Proceedings fo the 6th Message Understanding Conference (MUC6)</i>.
 *   45--52.  Morgan Kaufmann.
 * </blockquote>
 *
 * <P>B-cubed cluster scoring was defined as an alternative to the MUC
 * scoring metric.  There are two variants B-cubed cluster precision, both
 * of which are weighted averages of a per-element precision score:
 *
 * <blockquote><code>
 * b3Precision(A,referencePartition,responsePartition)
 * <br> = |cluster(responsePartition,A) INTERSECT cluster(referencePartition,A)|
 * <br> / |cluster(responsePartition,A)|
 * </code></blockquote>
 *
 * where <code>cluster(partition,a)</code> is the cluster in the
 * partition <code>partition</code> containing the element <code>a</code>;
 * in other words, this is <code>A</code>'s equivalence class and contains
 * the set of all elements equivalent to <code>A</code> in the partition.
 *
 * <P>For the uniform cluster method, each cluster in the reference partition is
 * weighted equally, and each element is weighted equally within a cluster:
 *
 * <blockquote><code>
 * b3ClusterPrecision(referencePartition,responsePartition)
 * <br> = <big><big>&Sigma;</big></big><sub><sub>a</sub></sub>
 *        b3Precision(a,referencePartition,responsePartition)
 * <br> / (|referencePartition| * |cluster(referencePartition,a)|)
 * </code></blockquote>
 *
 * <P>For the uniform element method, each element <code>a</code> is weighted uniformly:
 *
 * <blockquote><code>
 * b3ElementPrecision(ReferencePartition,ResponsePartition)
 * <br> = <big><big>&Sigma;</big></big><sub><sub>a</sub></sub>
 *        b3Precision(a,referencePartition,responsePartition) / numElements
 * </code></blockquote>
 *
 * where <code>numElements</code> is the total number of elements in
 * the partitions.  For both B-cubed approaches, recall is defined
 * dually by switching the roles of reference and response, and the
 * F<sub><sub>1</sub></sub>-measure is defined in the usual way.
 *
 * <P>The B-cubed method is described in detail in:
 *
 * <blockquote>
 *   Bagga, Amit and Breck Baldwin.
 *   1998.
 *   <a href="ftp://ftp.cis.upenn.edu/pub/breck/scoring-paper.ps.gz">Algorithms
 *   for scoring coreference chains</a>.
 *   In <i>Proceedings of the First International Conference
 *   on Language Resources and Evaluation Workshop on Linguistic
 *   Coreference.</i>
 * </blockquote>
 *
 * <P>As an example, consider the following two partitions:
 *
 * <blockquote><code>
 *   reference = { {1, 2, 3, 4, 5}, {6, 7}, {8, 9, A, B, C} }
 *   <br>
 *   response = { { 1, 2, 3, 4, 5, 8, 9, A, B, C }, { 6, 7} }
 * </code></blockquote>
 *
 * which produce the following values for method calls:
 *
 * <blockquote>
 * <table border='1' cellpadding='5'>
 * <tr><td><i>Method</i></td><td><i>Result</i></td></tr>
 * <tr><td>{@link #equivalenceEvaluation()}</td>
 *     <td>PrecisionRecallEvaluation(54,0,50,40)
 *         <br>TP=54; FN=0; FP=50; TN=40</td></tr>
 * <tr><td>{@link #mucPrecision()}</td>
 *     <td>0.9</td></tr>
 * <tr><td>{@link #mucRecall()}</td>
 *     <td>1.0</td></tr>
 * <tr><td>{@link #mucF()}</td>
 *     <td>0.947</td></tr>
 * <tr><td>{@link #b3ElementPrecision()}</td>
 *     <td>0.583</td></tr>
 * <tr><td>{@link #b3ElementRecall()}</td>
 *     <td>1.0</td></tr>
 * <tr><td>{@link #b3ElementF()}</td>
 *     <td>0.737</td></tr>
 * <tr><td>{@link #b3ClusterPrecision()}</td>
 *     <td>0.75</td></tr>
 * <tr><td>{@link #b3ClusterRecall()}</td>
 *     <td>1.0</td></tr>
 * <tr><td>{@link #b3ClusterF()}</td>
 *     <td>0.857</td></tr>
 * </table>
 * </blockquote>
 *
 * <p>Note that there are additional scoring metrics within the {@link
 * Dendrogram} class for cophenetic correlation and dendrogram-specific
 * within-cluster scatter.
 *
 * @author  Bob Carpenter
 * @version 3.0
 * @since   LingPipe2.0
 */
public class ClusterScore<E> {

    private final PrecisionRecallEvaluation mPrEval;

    private final Set<? extends Set<? extends E>> mReferencePartition;
    private final Set<? extends Set<? extends E>> mResponsePartition;

    /**
     * Construct a cluster score object from the specified reference and
     * response partitions.  A partition is a set of disjoint sets of
     * elements.  A partition defines an equivalence relation where the
     * disjoint sets represent the equivalence classes.
     *
     * <P>The reference partition is taken to represent the "truth"
     * or the "correct" answer, also known as the "gold standard".
     * The response partition is the partition to evaluate against the
     * reference partition.
     *
     * <P>If the specified partitions are not over the same sets
     * or if the equivalence classes are not disjoint, an illegal
     * argument exception is raised.
     *
     * @param referencePartition Partition of reference elements.
     * @param responsePartition Partition of response elements.
     * @throws IllegalArgumentException If the partitions are not
     * valid partitions over the same set of elements.
     */
    public ClusterScore(Set<? extends Set<? extends E>> referencePartition,
                        Set<? extends Set<? extends E>> responsePartition) {
        assertPartitionSameSets(referencePartition,responsePartition);
        mReferencePartition = referencePartition;
        mResponsePartition = responsePartition;
        mPrEval = calculateConfusionMatrix();
    }

    /**
     * Returns the precision-recall evaluation corresponding to
     * equalities in the reference and response clusterings.
     *
     * @return The precision-recall evaluation.
     */
    public PrecisionRecallEvaluation equivalenceEvaluation() {
        return mPrEval;
    }


    /**
     * Returns the precision as defined by MUC.  See the class
     * documentation above for definitions.
     *
     * @return The precision as defined by MUC.
     */
    public double mucPrecision() {
        return mucRecall(mResponsePartition,mReferencePartition);
    }

    /**
     * Returns the recall as defined by MUC.  See the class
     * documentation above for definitions.
     *
     * @return The recall as defined by MUC.
     */
    public double mucRecall() {
        return mucRecall(mReferencePartition,mResponsePartition);
    }

    /**
     * Returns the F<sub><sub>1</sub></sub> measure of the MUC recall
     * and precision. See the class
     * documentation above for definitions.
     *
     * @return The F measure as defined by MUC.
     */
    public double mucF() {
        return f(mucPrecision(),mucRecall());
    }


    /**
     * Returns the precision as defined by B<sup>3</sup> metric with
     * equal cluster weighting.  See the class documentation above for
     * definitions.
     *
     * @return The B-cubed equal cluster precision.
     */
    public double b3ClusterPrecision() {
        return b3ClusterRecall(mResponsePartition,mReferencePartition);
    }

    /**
     * Returns the recall as defined by B<sup>3</sup> metric with
     * equal cluster weighting.  See the class documentation above for
     * definitions.
     *
     * @return The B-cubed equal cluster recall.
     */
    public double b3ClusterRecall() {
        return b3ClusterRecall(mReferencePartition,mResponsePartition);
    }

    /**
     * Returns the F<sub><Sub>1</sub></sub> measure of the
     * B<sup>3</sup> precision and recall metrics with equal cluster
     * weighting.  See the class documentation above for definitions.
     *
     * @return The B-cubed equal cluster F measure.
     */
    public double b3ClusterF() {
        return f(b3ClusterPrecision(),
                 b3ClusterRecall());
    }

    /**
     * Returns the precision as defined by B<sup>3</sup> metric with
     * equal element weighting.  See the class documentation above for
     * definitions.
     *
     * @return The B-cubed equal element precision.
     */
    public double b3ElementPrecision() {
        return b3ElementRecall(mResponsePartition,mReferencePartition);
    }

    /**
     * Returns the recall as defined by B<sup>3</sup> metric with
     * equal element weighting.  See the class documentation above for
     * definitions.
     *
     * @return The B-cubed equal element recall.
     */
    public double b3ElementRecall() {
        return b3ElementRecall(mReferencePartition,mResponsePartition);
    }

    /**
     * Returns the F<sub><Sub>1</sub></sub> measure of the
     * B<sup>3</sup> precision and recall metrics with equal element
     * weighting.  See the class documentation above for definitions.
     *
     * @return The B-cubed equal element F measure.
     */
    public double b3ElementF() {
        return f(b3ElementPrecision(),
                 b3ElementRecall());
    }

    /**
     * Returns the set of true positive relations for this scoring.
     * Each relation is an instance of {@link Tuple}.  These true
     * positives will include both <code>(x,y)</code> and
     * <code>(y,x)</code> for a true positive relation between
     * <code>x</code> and <code>y</code>.