confusionmatrix.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.classify;

import com.aliasi.stats.Statistics;

import com.aliasi.util.Math;

import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;

/**
 * An instance of <code>ConfusionMatrix</code> represents a
 * quantitative comparison between two classifiers over a fixed set of
 * categories on a number of test cases.  For convenience, one
 * classifier is termed the &quot;reference&quot; and the other the
 * &quot;response&quot;.
 *
 * <P>Typically the reference will be determined by a human or other
 * so-called &quot;gold standard&quot;, whereas the response will be
 * the result of an automatic classification.  This is how confusion
 * matrices are created from test cases in {@link
 * ClassifierEvaluator}.  With this confusion matrix implementation,
 * two human classifiers or two automatic classifications may also be
 * compared.  For instance, human classifiers that label corpora for
 * training sets are often evaluated for inter-annotator agreement;
 * the usual form of reporting for this is the kappa statistic, which
 * is available in three varieties from the confusion matrix.  A set
 * of systems may also be compared pairwise, such as those arising
 * from a competitive evaluation.
 *
 * <P>Confusion matrices may be initialized on construction; with no
 * matrix argument, they will be constructed with zero values in all
 * cells.  The values can then be incremented by category name with
 * category name with {@link #increment(String,String)} or by
 * category index with {@link #increment(int,int)}. There is also
 * a {@link #incrementByN(int,int,int)} which allows explicit control
 * over matrix values.
 *
 * <P>Consider the following confusion matrix, which reports on the
 * classification of 27 wines by grape variety.  The reference in
 * this case is the true variety and the response arises from the
 * blind evaluation of a human judge.
 *
 * <blockquote>
 * <table border='1' cellpadding='5'>
 * <tr><td colspan='5'><b>Many-way Confusion Matrix</b></td></tr>
 * <tr><td colspan='2' rowspan='2'>&nbsp;</td>
 *     <td colspan='3' align='center'><b><i>Response</i></b></td></tr>
 * <tr>
 *     <td><i>Cabernet</i></td>
 *     <td><i>Syrah</i></td>
 *     <td><i>Pinot</i></td></tr>
 * <tr><td rowspan='3'><i><b>Refer-<br>ence</b></i></td><td><i>Cabernet</i></td>
 *     <td bgcolor='#CCCCFF'>9</td><td>3</td><td>0</td></tr>
 * <tr><td><i>Syrah</i></td>
 *     <td>3</td><td bgcolor='#CCCCFF'>5</td><td>1</td></tr>
 * <tr><td><i>Pinot</i></td>
 *     <td>1</td><td>1</td><td bgcolor='#CCCCFF'>4</td></tr>
 * </table>
 * </blockquote>
 *
 * Each row represents the results of classifying objects belonging to
 * the category designated by that row.  For instance, the first row
 * is the result of 12 cabernet classifications.  Reading across, 9 of
 * those cabernets were correctly classified as cabernets, 3 were
 * misclassified as syrahs, and none were misclassified as pinot noir.
 * In the next row are the results for 9 syrahs, 3 of which were
 * misclassified as cabernets and 1 of which was misclassified as a
 * pinot.  Similarly, the six pinots being classified are represented
 * on the third row.  In total, the classifier categorized 13 wines as
 * cabernets, 9 wines as syrahs, and 5 wines as pinots.  The sum of
 * all numbers in the graph is equal to the number of trials, in this
 * case 27.  Further note that the correct answers are the ones on the
 * diagonal of the matrix.  The individual entries are recoverable
 * using the method {@link #count(int,int)}.  The positive and
 * negative counts per category may be recovered from the result of
 * {@link #oneVsAll(int)}.
 *
 * <P>Collective results are either averaged per category (macro
 * average) or averaged per test case (micro average).  The results
 * reported here are for a single operating point of results.  Very
 * often in the research literature, results are returned for the best
 * possible post-hoc system settings, established either globally or
 * per category.
 *
 * <P>The multiple outcome classification can be decomposed into a
 * number of one-versus-all classification problems.  For each
 * category, a classifier that categorizes objects as either belonging
 * to that category or not.  From an <i>n</i>-way classifier, a
 * one-versus-all classifier can be constructed automatically by
 * treating an object to be classified as belonging to the category if
 * the category is the result of classifying it.  For the above
 * three-way confusion matrix, the following three one-versus-all
 * matrices are returned as instances of {@link
 * PrecisionRecallEvaluation} through the method {@link
 * #oneVsAll(int)}:
 *
 * <blockquote>
 * <table border='0' cellpadding='5'>
 * <tr>

 * <td>
 * <table border='1' cellpadding='3'>
 * <tr><td colspan='4'><b>Cab-vs-All</b></td></tr>
 * <tr><td colspan='2' rowspan='2' bordercolor='white'>&nbsp;</td>
 *     <td colspan='3' align='center'><b><i>Response</i></b></td></tr>
 * <tr>
 *     <td><i>Cab</i></td>
 *     <td><i>Other</i></td></tr>
 * <tr><td rowspan='3'><i><b>Refer<br>-ence</b></i></td><td><i>Cab</i></td>
 *     <td bgcolor='#CCCCFF'>9</td><td>3</td></tr>
 * <tr><td><i>Other</i></td>
 *     <td>4</td><td bgcolor='#CCCCFF'>11</td></tr>
 * </table>
 * </td>
 *
 * <td>
 * <table border='1' cellpadding='3'>
 * <tr><td colspan='4'><b>Syrah-vs-All</b></td></tr>
 * <tr><td colspan='2' rowspan='2' bordercolor='white'>&nbsp;</td>
 *     <td colspan='3' align='center'><b><i>Response</i></b></td></tr>
 * <tr>
 *     <td><i>Syrah</i></td>
 *     <td><i>Other</i></td></tr>
 * <tr><td rowspan='3'><i><b>Refer<br>-ence</b></i></td><td><i>Syrah</i></td>
 *     <td bgcolor='#CCCCFF'>5</td><td>4</td></tr>
 * <tr><td><i>Other</i></td>
 *     <td>4</td><td bgcolor='#CCCCFF'>14</td></tr>
 * </table>
 * </td>
 *
 * <td>
 * <table border='1' cellpadding='3'>
 * <tr><td colspan='4'><b>Pinot-vs-All</b></td></tr>
 * <tr><td colspan='2' rowspan='2' bordercolor='white'>&nbsp;</td>
 *     <td colspan='3' align='center'><b><i>Response</i></b></td></tr>
 * <tr>
 *     <td><i>Pinot</i></td>
 *     <td><i>Other</i></td></tr>
 * <tr><td rowspan='3'><i><b>Refer<br>-ence</b></i></td><td><i>Pinot</i></td>
 *     <td bgcolor='#CCCCFF'>4</td><td>2</td></tr>
 * <tr><td><i>Other</i></td>
 *     <td>1</td><td bgcolor='#CCCCFF'>20</td></tr>
 * </table>
 * </td>
 *
 * </tr>
 * </table>
 *
 * </blockquote>
 *
 * Note that each has the same true-positive number as in the
 * corresponding cell of the original confusion matrix.  Further note
 * that the sum of the cells in each derived matrix is the same as in
 * the original matrix.  Finally note that if the original
 * classification problem was two dimensional, the derived matrix will
 * be the same as the original matrix.  The results of the various
 * precision-recall evaluation methods for these matrices are shown
 * in the class documentation for {@link PrecisionRecallEvaluation}.
 *
 * <P>Macro-averaged results are just the average of the per-category
 * results.  These include precision, recall and f-measure.  Yule's Q
 * and Y statistics along with the per-category chi squared results
 * are also computed based on the one-versus all matrices.
 *
 * <P>Micro-averaged results are reported based on another derived
 * matrix: the sum of the scores in the one-versus-all matrices.  For
 * the above case, the result given as a {@link PrecisionRecallEvaluation}
 * by the method {@link #microAverage()} is:
 *
 * <blockquote>
 * <table border='1' cellpadding='3'>
 * <tr><td colspan='4'><b>Sum of One-vs-All Matrices</b></td></tr>
 * <tr><td colspan='2' rowspan='2' bordercolor='white'>&nbsp;</td>
 *     <td colspan='3' align='center'><b><i>Response</i></b></td></tr>
 * <tr>
 *     <td><i>True</i></td>
 *     <td><i>False</i></td></tr>
 * <tr><td rowspan='3'><i><b>Refer<br>-ence</b></i></td><td><i>True</i></td>
 *     <td bgcolor='#CCCCFF'>18</td><td>9</td></tr>
 * <tr><td><i>False</i></td>
 *     <td>9</td><td bgcolor='#CCCCFF'>45</td></tr>
 * </table>
 * </blockquote>
 *
 * Note that the true positive cell will be the sum of the
 * true-positive cells of the original matrix (9+5+4=18 in the running
 * example).  A little algebra shows that the false positive cell will
 * be equal to the sum of the off-diagonal elements in the original
 * confusion matrix (3+3+1+1+1=9); symmetry then shows that the false
 * negative value will be the same.  Finally, the true negative cell
 * will bring the total up to the number of categories times the sum
 * of the entries in the original matrix (here 27*3-18-9-9=45); it is
 * also equal to two times the number of true positives plus the
 * number of false negatives (here 2*18+9=45).  Thus for
 * one-versus-all confusion matrices derived from many-way confusion
 * matrices, the micro-averaged precision, recall and f-measure will
 * all be the same.
 *
 * <P>For the above confusion matrix and derived matrices, the
 * no-argument and category-indexed methods will return the values in
 * the following tables. The hot-linked method documentation defines
 * each statistic in detail.
 *
 * <blockquote>
 * <table border='1' cellpadding='5'>
 * <tr><td><i>Method</i></td><td><i>Method()</i></td></tr>
 * <tr><td>{@link #categories()}</code></td>
 *     <td><code>{ &quot;Cabernet&quot;,
 *               &quot;Syrah&quot;,
 *               &quot;Pinot&quot; }</code></td></tr>
 * <tr><td>{@link #totalCount()}</td>
 *     <td>27</td></tr>
 * <tr><td>{@link #totalCorrect()}</td>
 *     <td>18</td></tr>
 * <tr><td>{@link #totalAccuracy()}</td>
 *     <td>0.6667</td></tr>
 * <tr><td>{@link #confidence95()}</td>
 *     <td>0.1778</td></tr>
 * <tr><td>{@link #confidence99()}</td>
 *     <td>0.2341</td></tr>
 * <tr><td>{@link #macroAvgPrecision()}</td>
 *     <td>0.6826</td></tr>
 * <tr><td>{@link #macroAvgRecall()}</td>
 *     <td>0.6574</td></tr>
 * <tr><td>{@link #macroAvgFMeasure()}</td>
 *     <td>0.6676</td></tr>
 * <tr><td>{@link #randomAccuracy()}</td>
 *     <td>0.3663</td></tr>
 * <tr><td>{@link #randomAccuracyUnbiased()}</td>
 *     <td>0.3663</td></tr>
 * <tr><td>{@link #kappa()}</td>
 *     <td>0.4740</td></tr>
 * <tr><td>{@link #kappaUnbiased()}</td>
 *     <td>0.4735</td></tr>
 * <tr><td>{@link #kappaNoPrevalence()}</td>
 *     <td>0.3333</td></tr>
 * <tr><td>{@link #referenceEntropy()}</td>
 *     <td>1.5305</td></tr>
 * <tr><td>{@link #responseEntropy()}</td>
 *     <td>1.4865</td></tr>
 * <tr><td>{@link #crossEntropy()}</td>
 *     <td>1.5376</td></tr>
 * <tr><td>{@link #jointEntropy()}</td>
 *     <td>2.6197</td></tr>
 * <tr><td>{@link #conditionalEntropy()}</td>
 *     <td>1.0892</td></tr>
 * <tr><td>{@link #mutualInformation()}</td>
 *     <td>0.3973</td></tr>
 * <tr><td>{@link #klDivergence()}</td>
 *     <td>0.007129</td></tr>
 * <tr><td>{@link #chiSquaredDegreesOfFreedom()}</td>
 *     <td>4</td></tr>
 * <tr><td>{@link #chiSquared()}</td>
 *     <td>15.5256</td></tr>
 * <tr><td>{@link #phiSquared()}</td>
 *     <td>0.5750</td></tr>
 * <tr><td>{@link #cramersV()}</td>
 *     <td>0.5362</td></tr>
 * <tr><td>{@link #lambdaA()}</td>
 *     <td>0.4000</td></tr>
 * <tr><td>{@link #lambdaB()}</td>
 *     <td>0.3571</td></tr>
 * </table>
 * </blockquote>
 *
 * <blockquote>
 * <table border='1' cellpadding='5'>
 * <tr><td><i>Method</i></td>
 *     <td><i>0 (Cabernet)</i></td>
 *     <td><i>1 (Syrah)</i></td>
 *     <td><i>2 (Pinot)</i></td></tr>
 * <tr><td>{@link #conditionalEntropy(int)}</td>
 *     <td>0.8113</td><td>1.3516</td><td>1.2516</td></tr>
 * </table>
 * </blockquote>
 *
 * @author  Bob Carpenter
 * @version 2.0
 * @since   LingPipe2.0
 */
public class ConfusionMatrix {

    private final String[] mCategories;
    private final int[][] mMatrix;
    private final Map mCategoryToIndex = new HashMap();

    /**
     * Construct a confusion matrix with all zero values from the
     * specified array of categories.
     *
     * @param categories Array of categories for classification.
     */
    public ConfusionMatrix(String[] categories) {
        mCategories = categories;
        int len = categories.length;
        mMatrix = new int[len][len];
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < len; ++j)
                mMatrix[i][j] = 0;
        for (int i = 0; i < len; ++i)
            mCategoryToIndex.put(categories[i],new Integer(i));

    }

    /**
     * Construct a confusion matrix with the specified set of
     * categories and values.  The values are arranged in
     * reference-category dominant ordering.  
     *
     * <P>For example, the many-way confusion matrix shown in
     * the class documentation above would be initialized
     * as:
     *
     * <pre>
     * String[] categories = new String[] 
     *     { "Cabernet", "Syrah", "Pinot" };
     * int[][] wineTastingScores = new int[][]
     *     { { 9, 3, 0 },
     *       { 3, 5, 1 },
     *       { 1, 1, 4 } };
     * ConfusionMatrix matrix 
     *   = new ConfusionMatrix(categories,wineTastingScores);
     * </pre>
     *
     * @param categories Array of categories for classification.
     * @param matrix Matrix of initial values.
     * @throws IllegalArgumentException If the categories and matrix
     * do not agree in dimension or the matrix contains a negative
     * value.
     */
    public ConfusionMatrix(String[] categories, int[][] matrix) {
        mCategories = categories;
        mMatrix = matrix;
        if (categories.length != matrix.length) {
            String msg = "Categories and matrix must be of same length."
                + " Found categories length=" + categories.length
                + " and matrix length=" + matrix.length;
            throw new IllegalArgumentException(msg);
        }
        for (int j = 0; j < matrix.length; ++j) {
            if (categories.length != matrix[j].length) {
                String msg = "Categories and all matrix rows must be of same length."
                    + " Found categories length=" + categories.length
                    + " Found row " + j + " length=" + matrix[j].length;
		throw new IllegalArgumentException(msg);
            }
        }
        int len = matrix.length;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                if (matrix[i][j] < 0) {
                    String msg = "Matrix entries must be non-negative."
                        + " matrix[" + i + "][" + j + "]=" + matrix[i][j];
                    throw new IllegalArgumentException(msg);
                }
            }
        }
    }

    /**
     * Return the array of categories for this confusion matrix.  The
     * order of categories here is the same as that in the matrix and
     * consistent with that returned by <code>getIndex()</code>.  For
     * a category <code>c</code> in the set of categories:

     * <blockquote><code>
     * categories()[getIndex(c)].equals(c)
     * </code></blockquote>

     * and for  an index <code>i</code> in range:
     *
     * <blockquote><code>
     * getIndex(categories()[i]) = i
     * </code></blockquote>
     *
     * @return The array of categories for this matrix.
     * @see #getIndex(String)