001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.experiment.evaluation.cluster.analyser;
031
032import java.util.Map;
033
034import org.openimaj.experiment.evaluation.AnalysisResult;
035
036import gov.sandia.cognition.math.MathUtil;
037
038/**
039 * Gather the true positives, true negatives, false positives, false negatives for a {@link DecisionAnalysis} instance
040 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
041 * @param <T> the type of analysis
042 */
043public abstract class DecisionClusterAnalyser<T extends AnalysisResult> implements ClusterAnalyser<T> {
044
045        @Override
046        public T analyse(int[][] correct, int[][] estimated) {
047                DecisionAnalysis ret = new DecisionAnalysis();
048                Map<Integer,Integer> invCor = ClusterAnalyserUtils.invert(correct);
049                long positive = 0;
050                long negative = 0;
051                long remainingTotal = 0;
052                long[] remaining = new long[correct.length];
053                long[] classCount = new long[correct.length];
054                // Count the remaining items not yet clustered, and the remaining items in each class not yet clustered
055                for (int i = 0; i < correct.length; i++) {
056                        remainingTotal += correct[i].length;
057                        remaining[i] = correct[i].length;
058                }
059                ret.TP = ret.FN = 0;
060                // Go through each estimated class
061                for (int[] cluster : estimated) {
062                        // The potential correct pairings is calculated as a cluster length pick 2
063                        if(cluster.length > 1)
064                                positive += MathUtil.binomialCoefficient(cluster.length, 2);
065                        remainingTotal -= cluster.length;
066                        // The potential negative pairings is the size of this class times the remaining items
067                        negative += remainingTotal  * cluster.length;
068
069                        // We count the number of each class contained in this cluster
070                        for (int i : cluster) {
071                                Integer integer = invCor.get(i);
072                                if(integer  == null) continue;
073                                classCount[integer]++;
074                        }
075                        // For each class, if its count is more than one update the true positives.
076                        // calculate the false negative pairings by considering the number for this class NOT in this cluster
077                        for (int i = 0; i < classCount.length; i++) {
078                                if(classCount[i] > 1){
079                                        ret.TP += MathUtil.binomialCoefficient((int)classCount[i], 2);
080                                }
081                                remaining[i] -= classCount[i];
082                                ret.FN += remaining[i] * classCount[i];
083                                classCount[i] = 0; // reset the class count
084                        }
085                }
086                ret.FP = positive - ret.TP;
087                ret.TN = negative - ret.FN;
088                
089                return analysisResults(ret);
090        }
091
092        /**
093         * Given a {@link DecisionAnalysis}, construct an analysis
094         * @param ret
095         * @return an analysis
096         */
097        public abstract T analysisResults(DecisionAnalysis ret) ;
098
099}