/*
 * 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.