/*
* Copyright (C) 2016 Edward Raff
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*/
package jsat.classifiers.trees;
import java.util.Random;
import jsat.DataSet;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.evaluation.Accuracy;
import jsat.classifiers.evaluation.ClassificationScore;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.regression.evaluation.MeanSquaredError;
import jsat.regression.evaluation.RegressionScore;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* Mean Decrease in Accuracy (MDA) measures feature importance by applying the
* classifier for each feature, and corruption one feature at a time as each
* dataum its pushed through the tree. The importance of a feature is them
* measured as the percent change in the target score when that feature was
* corrupted.
*
* This approach is based off of Breiman, L. (2001). Random forests.
* Machine Learning, 45(1), 5–32.
*
* @author Edward Raff
*/
public class MDA implements TreeFeatureImportanceInference
{
private ClassificationScore cs_base = new Accuracy();
private RegressionScore rs_base = new MeanSquaredError();
@Override
public double[] getImportanceStats(TreeLearner model, DataSet data)
{
double[] features = new double[data.getNumFeatures()];
double baseScore;
boolean percentIncrease;
Random rand = RandomUtil.getRandom();
if(data instanceof ClassificationDataSet)
{
ClassificationDataSet cds = (ClassificationDataSet) data;
ClassificationScore cs = cs_base.clone();
cs.prepare(cds.getPredicting());
for(int i = 0; i < cds.getSampleSize(); i++)
{
DataPoint dp = cds.getDataPoint(i);
cs.addResult(((Classifier)model).classify(dp), cds.getDataPointCategory(i), dp.getWeight());
}
baseScore = cs.getScore();
percentIncrease = cs.lowerIsBetter();
//for every feature
for(int j = 0; j < data.getNumFeatures(); j++)
{
cs.prepare(cds.getPredicting());
for(int i = 0; i < cds.getSampleSize(); i++)
{
DataPoint dp = cds.getDataPoint(i);
int true_label = cds.getDataPointCategory(i);
TreeNodeVisitor curNode = walkCorruptedPath(model, dp, j, rand);
cs.addResult(curNode.localClassify(dp), true_label, dp.getWeight());
}
double newScore = cs.getScore();
features[j] = percentIncrease ? (newScore-baseScore)/(baseScore+1e-3) : (baseScore-newScore)/(baseScore+1e-3);
}
}
else if(data instanceof RegressionDataSet)
{
RegressionDataSet rds = (RegressionDataSet) data;
RegressionScore rs = rs_base.clone();
rs.prepare();
for(int i = 0; i < rds.getSampleSize(); i++)
{
DataPoint dp = rds.getDataPoint(i);
rs.addResult(((Regressor)model).regress(dp), rds.getTargetValue(i), dp.getWeight());
}
baseScore = rs.getScore();
percentIncrease = rs.lowerIsBetter();
//for every feature
for(int j = 0; j < data.getNumFeatures(); j++)
{
rs.prepare();
for(int i = 0; i < rds.getSampleSize(); i++)
{
DataPoint dp = rds.getDataPoint(i);
double true_label = rds.getTargetValue(i);
TreeNodeVisitor curNode = walkCorruptedPath(model, dp, j, rand);
rs.addResult(curNode.localRegress(dp), true_label, dp.getWeight());
}
double newScore = rs.getScore();
features[j] = percentIncrease ? (newScore-baseScore)/(baseScore+1e-3) : (baseScore-newScore)/(baseScore+1e-3);
}
}
return features;
}
/**
* walks the tree down to a leaf node, adding corruption for a specific feature
* @param model the tree model to walk
* @param dp the data point to push down the tree
* @param j the feature index to corrupt
* @param rand source of randomness
* @return the leaf node
*/
private TreeNodeVisitor walkCorruptedPath(TreeLearner model, DataPoint dp, int j, Random rand)
{
TreeNodeVisitor curNode = model.getTreeNodeVisitor();
while(!curNode.isLeaf())
{
int path = curNode.getPath(dp);
int numChild = curNode.childrenCount();
if(curNode.featuresUsed().contains(j))//corrupt the feature!
{
//this gets us a random OTHER path, wont be the same b/c we would need to wrap around 1 farther
path = (path + rand.nextInt(numChild)) % numChild;
}
if(curNode.isPathDisabled(path))
break;
else
curNode = curNode.getChild(path);
}
return curNode;
}
}
Ads help maintain this website.