package jsat.linear.distancemetrics;

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.ExecutorService;
import jsat.linear.IndexValue;
import jsat.linear.Vec;

/**
 * A valid distance metric formed from the Pearson Correlation between two vectors.
 * The distance in the range of [0, 1]. 
 * 
 * @author Edward Raff
 */
public class PearsonDistance implements DistanceMetric
{

    private static final long serialVersionUID = 1090726755301934198L;
    private boolean bothNonZero;
    private boolean absoluteDistance;

    /**
     * Creates a new standard Pearson Distance that does not ignore zero values 
     * and anti-correlated values are considered far away. 
     */
    public PearsonDistance()
    {
        this(false, false);
    }

    /**
     * Creates a new Pearson Distance object
     * @param bothNonZero {@code true} if non zero values should be treated as 
     * "missing" or "no vote", and will not contribute. But this will not 
     * change the mean value used. {@code false} produces the standard Pearson value. 
     * @param absoluteDistance {@code true} to use the absolute correlation, meaning 
     * correlated and anti-correlated values will have the same distance. 
     */
    public PearsonDistance(boolean bothNonZero, boolean absoluteDistance)
    {
        this.bothNonZero = bothNonZero;
        this.absoluteDistance = absoluteDistance;
    }

    @Override
    public double dist(Vec a, Vec b)
    {
        double r = correlation(a, b, bothNonZero);
        if(Double.isNaN(r))
            return Double.MAX_VALUE;
        if(absoluteDistance)
            return Math.sqrt(1-r*r);
        else
            return Math.sqrt((1-r)*0.5);
    }

    @Override
    public boolean isSymmetric()
    {
        return true;
    }

    @Override
    public boolean isSubadditive()
    {
        return true;
    }

    @Override
    public boolean isIndiscemible()
    {
        return true;
    }

    @Override
    public double metricBound()
    {
        return 1;
    }

    @Override
    public PearsonDistance clone()
    {
        return new PearsonDistance(bothNonZero, absoluteDistance);
    }
    
    /**
     * Computes the Pearson correlation between two vectors. If one of the vectors is all zeros, the result is undefined. 
     * In cases where both are zero vectors, 1 will be returned to indicate they are the same. In cases where one of the 
     * numerator coefficients is zero, its value will be bumped up to an epsilon to provide a near result. 
*
* In cases where {@code bothNonZero} is {@code true}, and the vectors have no overlapping non zero values, 0 will * be returned. * @param a the first vector * @param b the second vector * @param bothNonZero {@code false} is the normal Pearson correlation. {@code true} will make the computation ignore * all indexes where one of the values is zero, the mean will be from all non zero values in each vector. * @return the Pearson correlation in [-1, 1] */ public static double correlation(Vec a, Vec b, boolean bothNonZero) { final double aMean; final double bMean; if(bothNonZero) { aMean = a.sum()/a.nnz(); bMean = b.sum()/b.nnz(); } else { aMean = a.mean(); bMean = b.mean(); } double r = 0; double aSqrd = 0, bSqrd = 0; if (a.isSparse() || b.isSparse()) { Iterator aIter = a.getNonZeroIterator(); Iterator bIter = b.getNonZeroIterator(); //if one is empty, then a zero forms on the denomrinator if (!aIter.hasNext() && !bIter.hasNext()) return 1; if (!aIter.hasNext() || !bIter.hasNext()) return Double.MAX_VALUE; IndexValue aCur = null; IndexValue bCur = null; boolean newA = true, newB = true; int lastObservedIndex = -1; do { if (newA) { if (!aIter.hasNext()) break; aCur = aIter.next(); newA = false; } if (newB) { if (!bIter.hasNext()) break; bCur = bIter.next(); newB = false; } if (aCur.getIndex() == bCur.getIndex()) { //accumulate skipped positions where both are zero if(!bothNonZero) r += aMean * bMean * (aCur.getIndex()-lastObservedIndex - 1); lastObservedIndex = aCur.getIndex(); double aVal = aCur.getValue() - aMean; double bVal = bCur.getValue() - bMean; r += aVal * bVal; aSqrd += aVal * aVal; bSqrd += bVal * bVal; newA = newB = true; } else if (aCur.getIndex() > bCur.getIndex()) { if (!bothNonZero) { //accumulate skipped positions where both are zero r += aMean * bMean * (bCur.getIndex()-lastObservedIndex - 1); lastObservedIndex = bCur.getIndex(); double bVal = bCur.getValue() - bMean; r += -aMean * bVal; bSqrd += bVal * bVal; } newB = true; } else if (aCur.getIndex() < bCur.getIndex()) { if (!bothNonZero) { //accumulate skipped positions where both are zero r += aMean * bMean * (aCur.getIndex()-lastObservedIndex - 1); lastObservedIndex = aCur.getIndex(); double aVal = aCur.getValue() - aMean; r += aVal * -bMean; aSqrd += aVal * aVal; } newA = true; } } while (true); if (!bothNonZero) { //only one of the loops bellow will execute while (!newA || (newA && aIter.hasNext())) { if(newA) aCur = aIter.next(); //accumulate skipped positions where both are zero r += aMean * bMean * (aCur.getIndex()-lastObservedIndex - 1); lastObservedIndex = aCur.getIndex(); double aVal = aCur.getValue() - aMean; r += aVal * -bMean; aSqrd += aVal * aVal; newA = true; } while (!newB || (newB && bIter.hasNext())) { if(newB) bCur = bIter.next(); //accumulate skipped positions where both are zero r += aMean * bMean * (bCur.getIndex()-lastObservedIndex - 1); lastObservedIndex = bCur.getIndex(); double bVal = bCur.getValue() - bMean; r += -aMean * bVal; bSqrd += bVal * bVal; newB = true; } r += aMean * bMean * (a.length()-lastObservedIndex - 1); aSqrd += aMean * aMean * (a.length()-a.nnz()); bSqrd += bMean * bMean * (b.length()-b.nnz()); } } else//dense! { for(int i = 0; i < a.length(); i++) { double aTmp = a.get(i); double bTmp = b.get(i); if(bothNonZero && (aTmp == 0 || bTmp == 0)) continue; double aVal = aTmp-aMean; double bVal = bTmp-bMean; r += aVal*bVal; aSqrd += aVal*aVal; bSqrd += bVal*bVal; } } if(bSqrd == 0 && aSqrd == 0) return 0; else if(bSqrd == 0 || aSqrd == 0) return r/Math.sqrt((aSqrd+1e-10)*(bSqrd+1e-10)); return r/Math.sqrt(aSqrd*bSqrd); } /* * TODO Accerlation for Pearson can be done, its a little complicated (you * cache the means and Sqrd values - so that you can do just 1 pass over all * values). But thats a good bit of code, and the above needs to be cleaned * up before implementing that. */ }

Ads help maintain this website.