/*
* 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.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.ListIterator;
import jsat.DataSet;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
/**
* Determines the importance of features by measuring the decrease in impurity
* caused by each feature used, weighted by the amount of data seen by the node
* using the feature.
* This method only works for classification datasets as it uses the
* {@link ImpurityScore} class, but may use any impurity measure supported.
*
* For more info, see:
*
* - Louppe, G., Wehenkel, L., Sutera, A., & Geurts, P. (2013).
* Understanding variable importances in forests of randomized trees. In
* C. j. c. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. q. Weinberger
* (Eds.), Advances in Neural Information Processing Systems 26 (pp. 431–439).
* Retrieved from
* here
* - Breiman, L. (2002). Manual on setting up, using, and understanding random
* forests v3.1. Statistics Department University of California Berkeley, CA,
* USA.
*
*
*
* @author Edward Raff
*/
public class MDI implements TreeFeatureImportanceInference
{
private ImpurityScore.ImpurityMeasure im;
public MDI(ImpurityScore.ImpurityMeasure im)
{
this.im = im;
}
public MDI()
{
this(ImpurityScore.ImpurityMeasure.GINI);
}
@Override
public double[] getImportanceStats(TreeLearner model, DataSet data)
{
double[] features = new double[data.getNumFeatures()];
if(!(data instanceof ClassificationDataSet))
throw new RuntimeException("MDI currently only supports classification datasets");
List> allData = ((ClassificationDataSet)data).getAsDPPList();
final int K = ((ClassificationDataSet)data).getClassSize();
ImpurityScore score = new ImpurityScore(K, im);
for(DataPointPair d : allData)
score.addPoint(d.getDataPoint(), d.getPair());
visit(model.getTreeNodeVisitor(), score, allData, features, score.getSumOfWeights(), K);
return features;
}
private void visit(TreeNodeVisitor node, ImpurityScore score, List> data, final double[] features , final double N, final int K)
{
if (node == null || node.isLeaf() )//invalid path or no split, so skip
return;
double curScore = score.getScore();
double curN = score.getSumOfWeights();
//working space to split data up into new subsets
List>> splitsData = new ArrayList>>(node.childrenCount());
List splitScores = new ArrayList(node.childrenCount());
splitsData.add(data);
splitScores.add(score);
for(int i = 0; i < node.childrenCount()-1; i++)
{
splitsData.add(new ArrayList>());
splitScores.add(new ImpurityScore(K, im));
}
//loop through and split up our data
for(ListIterator> iter = data.listIterator(); iter.hasNext();)
{
DataPointPair curPoint = iter.next();
final int tc = curPoint.getPair();
DataPoint dp = curPoint.getDataPoint();
int path = node.getPath(dp);
if(path < 0)//NaN will cause -1
score.removePoint(dp, tc);
else if(path > 0)//0 will be cur data and score obj, else we move to right location
{
score.removePoint(dp, tc);
splitScores.get(path).addPoint(dp, tc);
splitsData.get(path).add(curPoint);
iter.remove();
}
}
double chageInImp = curScore;
for(ImpurityScore s : splitScores)
chageInImp -= s.getScore()*(s.getSumOfWeights()/(1e-5+curN));
Collection featuresUsed = node.featuresUsed();
for (int feature : featuresUsed)
features[feature] += chageInImp*curN/N;
//now visit our children
for(int path = 0; path < splitScores.size(); path++)
visit(node.getChild(path), splitScores.get(path), splitsData.get(path), features, N, K);
}
}
Ads help maintain this website.