package jsat.datatransform.featureselection;

import static java.lang.Math.log;

import java.util.Set;

import jsat.DataSet;
import jsat.classifiers.*;
import jsat.datatransform.*;
import jsat.exceptions.FailedToFitException;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.utils.IndexTable;
import jsat.utils.IntSet;

/**
 * Performs greedy feature selection based on Mutual Information of the features
 * with respect to the class values. This is an attempt to select features that 
 * are discriminative for classification tasks. 
* The method of performing Mutual Information on numeric attributes is * controlled by {@link NumericalHandeling} * * @author Edward Raff */ public class MutualInfoFS extends RemoveAttributeTransform { private static final long serialVersionUID = -4394620220403363542L; private int featureCount; private NumericalHandeling numericHandling; /** * The definition for mutual information for continuous attributes requires * an integration of an unknown function, as such requires some form of * approximation. This controls how the approximation is done */ public enum NumericalHandeling { /** * Mutual information for numeric attributes is not computed, so no * numeric attributes will be removed - and are ignored completely. The * number of features to select does not include the numeric attributes * in this case. */ NONE, /** * Numeric attributes are treated as nominal features with binary * values. The false value is if the value is zero, and the true value * is any non zero value. */ BINARY, } /** * Creates a new Mutual Information feature selection object that attempts * to select up to 100 features. Numeric attributes are handled by * {@link NumericalHandeling#BINARY} * */ public MutualInfoFS() { this(100); } /** * Creates a new Mutual Information feature selection object. Numeric * attributes are handled by {@link NumericalHandeling#BINARY} * * @param featureCount the number of features to select */ public MutualInfoFS(int featureCount) { this(featureCount, NumericalHandeling.BINARY); } /** * Creates a new Mutual Information feature selection object. Numeric * attributes are handled by {@link NumericalHandeling#BINARY} * * @param dataSet the classification data set to perform feature selection * from * @param featureCount the number of features to select */ public MutualInfoFS(ClassificationDataSet dataSet, int featureCount) { this(dataSet, featureCount, NumericalHandeling.BINARY); } /** * Copy constructor * @param toCopy the object to copy */ protected MutualInfoFS(MutualInfoFS toCopy) { super(toCopy); this.featureCount = toCopy.featureCount; this.numericHandling = toCopy.numericHandling; } /** * Creates a new Mutual Information feature selection object. * * @param featureCount the number of features to select * @param numericHandling the way to handle the computation of mutual * information for numeric attributes */ public MutualInfoFS(int featureCount, NumericalHandeling numericHandling) { super(); setFeatureCount(featureCount); setHandling(numericHandling); } /** * Creates a new Mutual Information feature selection object. * * @param dataSet the classification data set to perform feature selection * from * @param featureCount the number of features to select * @param numericHandling the way to handle the computation of mutual * information for numeric attributes */ public MutualInfoFS(ClassificationDataSet dataSet, int featureCount, NumericalHandeling numericHandling) { this(featureCount, numericHandling); } @Override public void fit(DataSet data) { if(!(data instanceof ClassificationDataSet)) throw new FailedToFitException("MutualInfoFS only works for classification data sets, not " + data.getClass().getSimpleName()); ClassificationDataSet dataSet = (ClassificationDataSet) data; final int N = dataSet.getSampleSize(); double[] classPriors = dataSet.getPriors(); double[] logClassPriors = new double[classPriors.length]; for(int i = 0; i < logClassPriors.length; i++) logClassPriors[i] = log(classPriors[i]); int numCatVars; int consideredCount = numCatVars = dataSet.getNumCategoricalVars(); if(numericHandling != NumericalHandeling.NONE) consideredCount = dataSet.getNumFeatures(); /** * 1st index is the feature * 2nd index is the option # */ double[][] featPriors = new double[consideredCount][]; CategoricalData[] catInfo = dataSet.getCategories(); /** * 1st index is the feature * 2nd index is the option # * 3rd index is the class */ double[][][] jointProb = new double[consideredCount][][]; for(int i = 0; i < jointProb.length; i++) { if(i < dataSet.getNumCategoricalVars())//Cat value { int options = catInfo[i].getNumOfCategories(); jointProb[i] = new double[options][logClassPriors.length]; featPriors[i] = new double[options]; } else//Numeric value { //Yes/No, but only keep track of the yes values jointProb[i] = new double[2][logClassPriors.length]; featPriors[i] = new double[1];//feature for numeric is just 1.0-other } } double weightSum = 0.0; for(int i = 0; i < dataSet.getSampleSize(); i++) { DataPoint dp = dataSet.getDataPoint(i); int trueClass = dataSet.getDataPointCategory(i); double weight = dp.getWeight(); weightSum += weight; int[] catVals = dp.getCategoricalValues(); for(int j = 0; j < catVals.length; j++) { featPriors[j][catVals[j]] += weight; jointProb[j][catVals[j]][trueClass] += weight; } if(numericHandling == NumericalHandeling.BINARY) { Vec numeric = dp.getNumericalValues(); for(IndexValue iv : numeric) { featPriors[iv.getIndex()+numCatVars][0] += weight; jointProb[iv.getIndex()+numCatVars][0][trueClass] += weight; } } } /** * Mutual Information for each index */ double[] mis = new double[consideredCount]; for(int i = 0; i < consideredCount; i++) { double mi = 0.0; if( i < dataSet.getNumCategoricalVars())//Cat attribute { for(int tVal = 0; tVal < jointProb[i].length; tVal++) { double featPrior = featPriors[i][tVal]/weightSum; if(featPrior == 0.0) continue; double logFeatPrior = log(featPrior); for (int tClass = 0; tClass < logClassPriors.length; tClass++) { double jp = jointProb[i][tVal][tClass] / weightSum; if (jp == 0) continue; mi += jp * (log(jp) - logFeatPrior - logClassPriors[tClass]); } } } else//Numeric attribute & it is binary { for(int tClass = 0; tClass < classPriors.length; tClass++) { double jpNeg = jointProb[i][0][tClass]/weightSum; double jpPos = (classPriors[tClass]*N - jointProb[i][0][tClass])/weightSum; double posPrio = featPriors[i][0]/weightSum; double negPrio = 1.0-posPrio; if (jpNeg != 0 && negPrio != 0) mi += jpNeg * (log(jpNeg) - log(negPrio) - logClassPriors[tClass]); if (jpPos != 0 && posPrio != 0) mi += jpPos * (log(jpPos) - log(posPrio) - logClassPriors[tClass]); } } mis[i] = mi; } IndexTable sortedOrder = new IndexTable(mis); Set catToRemove = new IntSet(); Set numToRemove = new IntSet(); for(int i = 0; i < consideredCount-featureCount; i++) { int removingIndex = sortedOrder.index(i); if(removingIndex < numCatVars) catToRemove.add(removingIndex); else numToRemove.add(removingIndex-numCatVars); } setUp(dataSet, catToRemove, numToRemove); } @Override public MutualInfoFS clone() { return new MutualInfoFS(this); } /** * Sets the number of features to select * * @param featureCount the number of features to select */ public void setFeatureCount(int featureCount) { if (featureCount < 1) throw new IllegalArgumentException("Number of features must be positive, not " + featureCount); this.featureCount = featureCount; } /** * Returns the number of features to select * * @return the number of features to select */ public int getFeatureCount() { return featureCount; } /** * Sets the method of numericHandling numeric features * * @param handling the numeric numericHandling */ public void setHandling(NumericalHandeling handling) { this.numericHandling = handling; } /** * Returns the method of numericHandling numeric features * * @return the method of numericHandling numeric features */ public NumericalHandeling getHandling() { return numericHandling; } }

Ads help maintain this website.