package jsat.classifiers.trees;
import static java.lang.Math.*;
import java.util.Arrays;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
/**
* ImpurityScore provides a measure of the impurity of a set of data points
* respective to their class labels. The impurity score is maximized when the
* classes are evenly distributed, and minimized when all points belong to one
* class.
* The gain in purity can be computed using the static gain methods of
* the class. However, not all impurity measures can be used for arbitrary data
* and splits. Some may only support binary splits, and some may only support
* binary target classes.
*
* @author Edward Raff
*/
public class ImpurityScore implements Cloneable
{
/**
* Different methods of measuring the impurity in a set of data points
* based on nominal class labels
*/
public enum ImpurityMeasure
{
INFORMATION_GAIN,
INFORMATION_GAIN_RATIO,
/**
* Normalized Mutual Information. The {@link #getScore() } value will be
* the same as {@link #INFORMATION_GAIN}, however - the gain returned
* is considerably different - and is a normalization of the mutual
* information between the split and the class label by the class and
* split entropy.
*/
NMI,
GINI,
CLASSIFICATION_ERROR
}
private double sumOfWeights;
private double[] counts;
private ImpurityMeasure impurityMeasure;
/**
* Creates a new impurity score that can be updated
*
* @param classCount the number of target class values
* @param impurityMeasure
*/
public ImpurityScore(int classCount, ImpurityMeasure impurityMeasure)
{
sumOfWeights = 0.0;
counts = new double[classCount];
this.impurityMeasure = impurityMeasure;
}
/**
* Copy constructor
* @param toClone
*/
private ImpurityScore(ImpurityScore toClone)
{
this.sumOfWeights = toClone.sumOfWeights;
this.counts = Arrays.copyOf(toClone.counts, toClone.counts.length);
this.impurityMeasure = toClone.impurityMeasure;
}
/**
* Removes one point from the impurity score
* @param dp the data point to add
* @param targetClass the class of the point to add
*/
public void removePoint(DataPoint dp, int targetClass)
{
removePoint(dp.getWeight(), targetClass);
}
/**
* Removes one point from the impurity score
* @param weight the weight of the point to add
* @param targetClass the class of the point to add
*/
public void removePoint(double weight, int targetClass)
{
counts[targetClass] -= weight;
sumOfWeights -= weight;
}
/**
* Adds one more point to the impurity score
* @param dp the data point to add
* @param targetClass the class of the point to add
*/
public void addPoint(DataPoint dp, int targetClass)
{
addPoint(dp.getWeight(), targetClass);
}
/**
* Adds one more point to the impurity score
* @param weight the weight of the point to add
* @param targetClass the class of the point to add
*/
public void addPoint(double weight, int targetClass)
{
counts[targetClass] += weight;
sumOfWeights += weight;
}
/**
* Computes the current impurity score for the points that have been added.
* A higher score is worse, a score of zero indicates a perfectly pure set
* of points (all one class).
* @return the impurity score
*/
public double getScore()
{
if(sumOfWeights <= 0)
return 0;
double score = 0.0;
if (impurityMeasure == ImpurityMeasure.INFORMATION_GAIN_RATIO
|| impurityMeasure == ImpurityMeasure.INFORMATION_GAIN
|| impurityMeasure == ImpurityMeasure.NMI)
{
for (Double count : counts)
{
double p = count / sumOfWeights;
if (p > 0)
score += p * log(p) / log(2);
}
}
else if (impurityMeasure == ImpurityMeasure.GINI)
{
score = 1;
for (double count : counts)
{
double p = count / sumOfWeights;
score -= p * p;
}
}
else if (impurityMeasure == ImpurityMeasure.CLASSIFICATION_ERROR)
{
double maxClass = 0;
for (double count : counts)
maxClass = Math.max(maxClass, count / sumOfWeights);
score = 1.0 - maxClass;
}
return abs(score);
}
/**
* Returns the sum of the weights for all points currently in the impurity
* score
* @return the sum of weights
*/
public double getSumOfWeights()
{
return sumOfWeights;
}
/**
* Returns the impurity measure being used
* @return the impurity measure being used
*/
public ImpurityMeasure getImpurityMeasure()
{
return impurityMeasure;
}
/**
* Obtains the current categorical results by prior probability
*
* @return the categorical results for the current score
*/
public CategoricalResults getResults()
{
CategoricalResults cr = new CategoricalResults(counts.length);
for(int i = 0; i < counts.length; i++)
cr.setProb(i, counts[i]/sumOfWeights);
return cr;
}
/*
* NOTE: for calulating the entropy in a split, if S is the current set of
* all data points, and S_i denotes one of the subsets gained from splitting
* The Gain for a split is
*
* n
* ===== |S |
* \ | i|
* Gain = Entropy(S) - > ---- Entropy/S \
* / |S| \ i/
* =====
* i = 1
*
* Gain
* GainRatio = ----------------
* SplitInformation
*
* n
* ===== |S | /|S |\
* \ | i| || i||
* SplitInformation = - > ---- log|----|
* / |S| \ |S|/
* =====
* i = 1
*/
/**
* Computes the gain in score from a splitting of the data set
*
* @param wholeData the score for the whole data set
* @param splits the scores for each of the splits
* @return the gain for the values given
*/
public static double gain(ImpurityScore wholeData, ImpurityScore... splits)
{
return gain(wholeData, 1.0, splits);
}
/**
* Computes the gain in score from a splitting of the data set
*
* @param wholeData the score for the whole data set
* @param wholeScale a constant to scale the wholeData counts and sums by, useful for handling missing value cases
* @param splits the scores for each of the splits
* @return the gain for the values given
*/
public static double gain(ImpurityScore wholeData, double wholeScale, ImpurityScore... splits)
{
double sumOfAllSums = wholeScale*wholeData.sumOfWeights;
if(splits[0].impurityMeasure == ImpurityMeasure.NMI)
{
double mi = 0, splitEntropy = 0.0, classEntropy = 0.0;
for(int c = 0; c < wholeData.counts.length; c++)//c: class
{
final double p_c = wholeScale*wholeData.counts[c]/sumOfAllSums;
if(p_c <= 0.0)
continue;
double logP_c = log(p_c);
classEntropy += p_c*logP_c;
for(int s = 0; s < splits.length; s++)//s: split
{
final double p_s = splits[s].sumOfWeights/sumOfAllSums;
if(p_s <= 0)
continue;
final double p_cs = splits[s].counts[c]/sumOfAllSums;
if(p_cs <= 0)
continue;
mi += p_cs * (log(p_cs) - logP_c - log(p_s));
if(c == 0)
splitEntropy += p_s * log(p_s);
}
}
splitEntropy = abs(splitEntropy);
classEntropy = abs(classEntropy);
return 2*mi/(splitEntropy+classEntropy);
}
//Else, normal cases
double splitScore = 0.0;
boolean useSplitInfo = splits[0].impurityMeasure == ImpurityMeasure.INFORMATION_GAIN_RATIO;
if(useSplitInfo)
{
/*
* TODO should actualy be 0, but performance bug is consistently
* occuring if I use another value. Needs serious investigation.
* I was testing on (Oracle) 1.7u51 & u20 smoething and both had the
* issue, on OSX and Windows.
*
* I was unable to replicate the issue with a smaller self contained
* program. So I suspect I might be at some threshold / corner case
* of the optimizer
*
* Adding a -1 at the final results causes the performance
* degredation agian. Occures with both client and server JVM
*
* Using the same code with an if stament seperating the 2 (see old revision) was originally backwards. Changing the correct way revealed the behavior. I'm leaving them seperated to ease investiation later.
*/
double splitInfo = 1.0;
for(ImpurityScore split : splits)
{
double p = split.getSumOfWeights()/sumOfAllSums;
if(p <= 0)//log(0) is -Inft, so skip and treat as zero
continue;
splitScore += p * split.getScore();
splitInfo += p * -log(p);
}
return (wholeData.getScore()-splitScore)/splitInfo;
}
else
{
for(ImpurityScore split : splits)
{
double p = split.getSumOfWeights()/sumOfAllSums;
if(p <= 0)//log(0) is -Inft, so skip and treat as zero
continue;
splitScore += p*split.getScore();
}
return wholeData.getScore()-splitScore;
}
}
@Override
protected ImpurityScore clone()
{
return new ImpurityScore(this);
}
}
Ads help maintain this website.