package jsat.classifiers.trees;
import java.util.*;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.classifiers.trees.ImpurityScore.ImpurityMeasure;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.random.RandomUtil;
/**
* The ExtraTree is an Extremely Randomized Tree. Splits are chosen at random,
* and the features that are selected are also chosen at random for each new
* node in the tree.
* If set to randomly select one feature for each node, it becomes a Totally
* Randomized Tree
* See:
* Geurts, P., Ernst, D.,&Wehenkel, L. (2006). Extremely randomized trees
* . Machine learning, 63(1), 3–42. doi:10.1007/s10994-006-6226-1
*
* @author Edward Raff
*/
public class ExtraTree implements Classifier, Regressor, TreeLearner, Parameterized
{
//TODO in both of the train methods, 2 passes are done for numeric features. This can be done in one pass by fiding the min/max when we split, and passing that info in the argument parameters
private static final long serialVersionUID = 7433728970041876327L;
private int stopSize;
private int selectionCount;
protected CategoricalData predicting;
private boolean binaryCategoricalSplitting = true;
/**
* Just stores the number of numeric features that were in the dataset for
* that the getFeatures method can be implemented correctly for categorical
* variables.
*/
private int numNumericFeatures;
private ImpurityScore.ImpurityMeasure impMeasure = ImpurityMeasure.NMI;
private TreeNodeVisitor root;
/**
* Creates a new Extra Tree that will use all features in the training set
*/
public ExtraTree()
{
this(Integer.MAX_VALUE, 5);
}
/**
* Creates a new Extra Tree
*
* @param selectionCount the number of features to select
* @param stopSize the stop size
*/
public ExtraTree(int selectionCount, int stopSize)
{
this.stopSize = stopSize;
this.selectionCount = selectionCount;
this.impMeasure = ImpurityMeasure.NMI;
}
/**
* Copy constructor.
* @param toCopy the object to copy
*/
public ExtraTree(ExtraTree toCopy)
{
this.stopSize = toCopy.stopSize;
this.selectionCount = toCopy.selectionCount;
if(toCopy.predicting != null)
this.predicting = toCopy.predicting;
this.numNumericFeatures = toCopy.numNumericFeatures;
this.binaryCategoricalSplitting = toCopy.binaryCategoricalSplitting;
this.impMeasure = toCopy.impMeasure;
if(toCopy.root != null)
this.root = toCopy.root.clone();
}
/**
* Sets the impurity measure used during classification tree construction to
* select the best of the features.
* @param impurityMeasure the impurity measure to use
*/
public void setImpurityMeasure(ImpurityMeasure impurityMeasure)
{
this.impMeasure = impurityMeasure;
}
/**
* Returns the impurity measure in use
* @return the impurity measure in use
*/
public ImpurityMeasure getImpurityMeasure()
{
return impMeasure;
}
/**
* Sets the stopping size for tree growth. When a node has less than or
* equal to stopSize data points to train from, it terminates and
* produces a leaf node.
* @param stopSize the size of the testing set to refuse to split
*/
public void setStopSize(int stopSize)
{
if(stopSize <= 0)
throw new ArithmeticException("The stopping size must be a positive value");
this.stopSize = stopSize;
}
/**
* Returns the stopping size for tree growth
* @return the stopping size for tree growth
*/
public int getStopSize()
{
return stopSize;
}
/**
* The ExtraTree will select the best of a random subset of features at each
* level, this sets the number of random features to select. If set larger
* than the number of features in the training set, all features will be
* eligible for selection at every level.
* @param selectionCount the number of random features to select
*/
public void setSelectionCount(int selectionCount)
{
this.selectionCount = selectionCount;
}
/**
* Returns the number of random features chosen at each level in the tree
* @return the number of random features to chose
*/
public int getSelectionCount()
{
return selectionCount;
}
/**
* The normal implementation of ExtraTree always produces binary splits,
* including for categorical features. If set to false categorical
* features will expand out for each value in the category. This reduces the
* randomness of the tree.
* @param binaryCategoricalSplitting whether or not to use the original
* splitting algorithm, or to fully expand nominal features
*/
public void setBinaryCategoricalSplitting(boolean binaryCategoricalSplitting)
{
this.binaryCategoricalSplitting = binaryCategoricalSplitting;
}
/**
* Returns whether or not binary splitting is used for nominal features
* @return whether or not binary splitting is used for nominal features
*/
public boolean isBinaryCategoricalSplitting()
{
return binaryCategoricalSplitting;
}
@Override
public CategoricalResults classify(DataPoint data)
{
return root.classify(data);
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
Random rand = RandomUtil.getRandom();
Stack>> reusableLists = new Stack<>();
IntList features = new IntList(dataSet.getNumFeatures());
ListUtils.addRange(features, 0, dataSet.getNumFeatures(), 1);
List> data = dataSet.getAsDPPList();
predicting = dataSet.getPredicting();
ImpurityScore score = new ImpurityScore(predicting.getNumOfCategories(), impMeasure);
for(DataPointPair dpp : data)
score.addPoint(dpp.getDataPoint(), dpp.getPair());
numNumericFeatures = dataSet.getNumNumericalVars();
root = trainC(score, data, features, dataSet.getCategories(), rand, reusableLists);
}
/**
* Creates a new tree top down
* @param setScore the impurity score for the set of data points being evaluated
* @param subSet the set of data points to perform a split on
* @param features the features available to split on
* @param catInfo the categorical information
* @param rand the source of randomness
* @param reusableLists a stack of already allocated lists that can be added and removed from
* @return the new top node created for the given data
*/
private TreeNodeVisitor trainC(ImpurityScore setScore, List> subSet, List features, CategoricalData[] catInfo, Random rand, Stack>> reusableLists)
{
//Should we stop? Stop split(S)
if(subSet.size() < stopSize || setScore.getScore() == 0.0)
{
if(subSet.isEmpty())
return null;
return new NodeC(setScore.getResults());
}
double bestGain = Double.NEGATIVE_INFINITY;
double bestThreshold = Double.NaN;
int bestAttribute = -1;
ImpurityScore[] bestScores = null;
List>> bestSplit = null;
Set bestLeftSide = null;
/*
* TODO use smarter random feature selection based on how many features
* we need relative to how many are available
*/
Collections.shuffle(features);
//It is possible, if we test all attribute - that one was categorical and no longer an option
final int goTo = Math.min(selectionCount, features.size());
for(int i = 0; i < goTo; i++)
{
double gain;
double threshold = Double.NaN;
Set leftSide = null;
ImpurityScore[] scores;
int a = features.get(i);
List>> aSplit;
if(a < catInfo.length)
{
final int vals = catInfo[a].getNumOfCategories();
if(binaryCategoricalSplitting || vals == 2)
{
scores = createScores(2);
Set catsValsInUse = new IntSet(vals*2);
for(DataPointPair dpp : subSet)
catsValsInUse.add(dpp.getDataPoint().getCategoricalValue(a));
if(catsValsInUse.size() == 1)
return new NodeC(setScore.getResults());
leftSide = new IntSet(vals);
int toUse = rand.nextInt(catsValsInUse.size()-1)+1;
ListUtils.randomSample(catsValsInUse, leftSide, toUse, rand);
//Now we have anything in leftSide is path 0, we can do the bining
aSplit = new ArrayList<>(2);
fillList(2, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
DataPoint dp = dpp.getDataPoint();
int dest = leftSide.contains(dpp.getDataPoint().getCategoricalValue(a)) ? 0 : 1;
scores[dest].addPoint(dp, dpp.getPair());
aSplit.get(dest).add(dpp);
}
}
else//split on each value
{
scores = createScores(vals);
//Bin all the points to get their scores
aSplit = new ArrayList<>(vals);
fillList(vals, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
DataPoint dp = dpp.getDataPoint();
scores[dp.getCategoricalValue(a)].addPoint(dp, dpp.getPair());
aSplit.get(dp.getCategoricalValue(a)).add(dpp);
}
}
}
else
{
int numerA = a - catInfo.length;
double min = Double.POSITIVE_INFINITY, max = Double.NEGATIVE_INFINITY;
for(DataPointPair dpp : subSet)
{
double val = dpp.getVector().get(numerA);
min = Math.min(min, val);
max = Math.max(max, val);
}
//Uniform random threshold
threshold = rand.nextDouble()*(max-min)+min;
scores = createScores(2);
aSplit = new ArrayList<>(2);
fillList(2, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
double val = dpp.getVector().get(numerA);
int toAddTo = val <= threshold ? 0 : 1;
aSplit.get(toAddTo).add(dpp);
scores[toAddTo].addPoint(dpp.getDataPoint(), dpp.getPair());
}
}
gain = ImpurityScore.gain(setScore, scores);
if(gain > bestGain)
{
bestGain = gain;
bestAttribute = a;
bestThreshold = threshold;
bestScores = scores;
if(bestSplit != null)
fillStack(reusableLists, bestSplit);
bestSplit = aSplit;
bestLeftSide = leftSide;
}
else
fillStack(reusableLists, aSplit);
}
//Best attribute has been selected
//We are no longer using the full array of all values
fillStack(reusableLists, Arrays.asList(subSet));
NodeBase toReturn;
if(bestAttribute < 0)
return null;
if(bestAttribute < catInfo.length)
if(bestSplit.size() == 2)//2 paths only
toReturn = new NodeCCat(bestAttribute, bestLeftSide, setScore.getResults());
else
{
toReturn = new NodeCCat(goTo, bestSplit.size(), setScore.getResults());
features.remove(new Integer(bestAttribute));//Feature nolonger viable in this case
}
else
toReturn = new NodeCNum(bestAttribute-catInfo.length, bestThreshold, setScore.getResults());
for(int i = 0; i < toReturn.children.length; i++)
{
toReturn.children[i] = trainC(bestScores[i], bestSplit.get(i), features, catInfo, rand, reusableLists);
}
return toReturn;
}
/**
* Creates a new tree top down
* @param setScore the impurity score for the set of data points being evaluated
* @param subSet the set of data points to perform a split on
* @param features the features available to split on
* @param catInfo the categorical information
* @param rand the source of randomness
* @param reusableLists a stack of already allocated lists that can be added and removed from
* @return the new top node created for the given data
*/
private TreeNodeVisitor train(OnLineStatistics setScore, List> subSet, List features, CategoricalData[] catInfo, Random rand, Stack>> reusableLists)
{
//Should we stop? Stop split(S)
if(subSet.size() < stopSize || setScore.getVarance() <= 0.0 || Double.isNaN(setScore.getVarance()))
return new NodeR(setScore.getMean());
double bestGain = Double.NEGATIVE_INFINITY;
double bestThreshold = Double.NaN;
int bestAttribute = -1;
OnLineStatistics[] bestScores = null;
List>> bestSplit = null;
Set bestLeftSide = null;
/*
* TODO use smarter random feature selection based on how many features
* we need relative to how many are available
*/
Collections.shuffle(features);
//It is possible, if we test all attribute - that one was categorical and no longer an option
final int goTo = Math.min(selectionCount, features.size());
for(int i = 0; i < goTo; i++)
{
double gain;
double threshold = Double.NaN;
Set leftSide = null;
OnLineStatistics[] stats;
int a = features.get(i);
List>> aSplit;
if(a < catInfo.length)
{
final int vals = catInfo[a].getNumOfCategories();
if(binaryCategoricalSplitting || vals == 2)
{
stats = createStats(2);
Set catsValsInUse = new IntSet(vals*2);
for(DataPointPair dpp : subSet)
catsValsInUse.add(dpp.getDataPoint().getCategoricalValue(a));
if(catsValsInUse.size() == 1)
return new NodeR(setScore.getMean());
leftSide = new IntSet(vals);
int toUse = rand.nextInt(catsValsInUse.size()-1)+1;
ListUtils.randomSample(catsValsInUse, leftSide, toUse, rand);
//Now we have anything in leftSide is path 0, we can do the bining
aSplit = new ArrayList<>(2);
fillList(2, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
DataPoint dp = dpp.getDataPoint();
int dest = leftSide.contains(dpp.getDataPoint().getCategoricalValue(a)) ? 0 : 1;
stats[dest].add(dpp.getPair(), dp.getWeight());
aSplit.get(dest).add(dpp);
}
}
else//split on each value
{
stats = createStats(vals);
//Bin all the points to get their scores
aSplit = new ArrayList<>(vals);
fillList(vals, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
DataPoint dp = dpp.getDataPoint();
stats[dp.getCategoricalValue(a)].add(dpp.getPair(), dp.getWeight());
aSplit.get(dp.getCategoricalValue(a)).add(dpp);
}
}
}
else
{
int numerA = a - catInfo.length;
double min = Double.POSITIVE_INFINITY, max = Double.NEGATIVE_INFINITY;
for(DataPointPair dpp : subSet)
{
double val = dpp.getVector().get(numerA);
min = Math.min(min, val);
max = Math.max(max, val);
}
//Uniform random threshold
threshold = rand.nextDouble()*(max-min)+min;
stats = createStats(2);
aSplit = new ArrayList<>(2);
fillList(2, reusableLists, aSplit);
for(DataPointPair dpp : subSet)
{
double val = dpp.getVector().get(numerA);
int toAddTo = val <= threshold ? 0 : 1;
aSplit.get(toAddTo).add(dpp);
stats[toAddTo].add(dpp.getPair(), dpp.getDataPoint().getWeight());
}
}
gain = 1;
double varNorm = setScore.getVarance();
double varSum = setScore.getSumOfWeights();
for(OnLineStatistics stat : stats)
gain -= stat.getSumOfWeights()/varSum*(stat.getVarance()/varNorm);
if(gain > bestGain)
{
bestGain = gain;
bestAttribute = a;
bestThreshold = threshold;
bestScores = stats;
if(bestSplit != null)
fillStack(reusableLists, bestSplit);
bestSplit = aSplit;
bestLeftSide = leftSide;
}
else
fillStack(reusableLists, aSplit);
}
//Best attribute has been selected
//We are no longer using the full array of all values
fillStack(reusableLists, Arrays.asList(subSet));
NodeBase toReturn;
if (bestAttribute >= 0)
{
if (bestAttribute < catInfo.length)
if (bestSplit.size() == 2)//2 paths only
toReturn = new NodeRCat(bestAttribute, bestLeftSide, setScore.getMean());
else
{
toReturn = new NodeRCat(goTo, bestSplit.size(), setScore.getMean());
features.remove(new Integer(bestAttribute));//Feature nolonger viable in this case
}
else
toReturn = new NodeRNum(bestAttribute - catInfo.length, bestThreshold, setScore.getMean());
for (int i = 0; i < toReturn.children.length; i++)
{
toReturn.children[i] = train(bestScores[i], bestSplit.get(i), features, catInfo, rand, reusableLists);
}
return toReturn;
}
return new NodeR(setScore.getMean());
}
@Override
public boolean supportsWeightedData()
{
return true;
}
@Override
public ExtraTree clone()
{
return new ExtraTree(this);
}
@Override
public TreeNodeVisitor getTreeNodeVisitor()
{
return root;
}
/**
* Add lists to a list of lists
* @param the content type of the list
* @param listsToAdd the number of lists to add
* @param reusableLists available pre allocated lists for reuse
* @param aSplit the list of lists to add to
*/
static private void fillList(final int listsToAdd, Stack> reusableLists, List> aSplit)
{
for(int j = 0; j < listsToAdd; j++)
if(reusableLists.isEmpty())
aSplit.add(new ArrayList<>());
else
aSplit.add(reusableLists.pop());
}
/**
* Adds the lists from the list of lists to the stack of reusable lists. The
* lists will not be removed from aSplit, despite being added to
* resuableLists
*
* @param the content type of the list
* @param reusableLists available pre allocated lists for reuse
* @param aSplit the lists of lists to add all elements of to the reusable
* lists
*/
static private void fillStack(Stack> reusableLists, List> aSplit)
{
for(List list : aSplit)
{
list.clear();
reusableLists.push(list);
}
}
private ImpurityScore[] createScores(int count)
{
ImpurityScore[] scores = new ImpurityScore[count];
for(int j = 0; j < scores.length; j++)
scores[j] = new ImpurityScore(predicting.getNumOfCategories(), impMeasure);
return scores;
}
@Override
public double regress(DataPoint data)
{
return root.regress(data);
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
train(dataSet);
}
@Override
public void train(RegressionDataSet dataSet)
{
Random rand = RandomUtil.getRandom();
Stack>> reusableLists = new Stack<>();
IntList features = new IntList(dataSet.getNumFeatures());
ListUtils.addRange(features, 0, dataSet.getNumFeatures(), 1);
List> data = dataSet.getAsDPPList();
OnLineStatistics score = new OnLineStatistics();
for(DataPointPair dpp : data)
score.add(dpp.getPair(), dpp.getDataPoint().getWeight());
numNumericFeatures = dataSet.getNumNumericalVars();
root = train(score, data, features, dataSet.getCategories(), rand, reusableLists);
}
private OnLineStatistics[] createStats(int count)
{
OnLineStatistics[] stats = new OnLineStatistics[count];
for(int i = 0; i < stats.length; i++)
stats[i] = new OnLineStatistics();
return stats;
}
/**
* Node for classification that splits on a categorical feature
*/
private class NodeCCat extends NodeC
{
private static final long serialVersionUID = 7413428280703235600L;
/**
* Categorical attribute to split on
*/
private int catAtt;
/**
* The cat values that go to the left branch, or null if no binary cats are being used
*/
private int[] leftBranch;
public NodeCCat(int catAtt, int children, CategoricalResults crResult)
{
super(crResult, children);
this.catAtt = catAtt;
this.leftBranch = null;
}
public NodeCCat(int catAtt, Set left, CategoricalResults crResult)
{
super(crResult, 2);
this.catAtt = catAtt;
this.leftBranch = new int[left.size()];
int pos = 0;
for(int i : left)
leftBranch[pos++] = i;
Arrays.sort(leftBranch);
}
public NodeCCat(NodeCCat toClone)
{
super(toClone);
this.catAtt = toClone.catAtt;
if(toClone.leftBranch != null)
this.leftBranch = Arrays.copyOf(toClone.leftBranch, toClone.leftBranch.length);
}
@Override
public int getPath(DataPoint dp)
{
int[] catVals = dp.getCategoricalValues();
if (leftBranch == null)
return catVals[catAtt];
else
{
if (Arrays.binarySearch(leftBranch, catVals[catAtt]) < 0)
return 1;
else
return 0;
}
}
@Override
public TreeNodeVisitor clone()
{
return new NodeCCat(this);
}
@Override
public Collection featuresUsed()
{
IntList used = new IntList(1);
used.add(catAtt+numNumericFeatures);
return used;
}
}
/**
* Node for classification that splits on a numeric feature
*/
private static class NodeCNum extends NodeC
{
private static final long serialVersionUID = 3967180517059509869L;
private int numerAtt;
private double threshold;
public NodeCNum(int numerAtt, double threshold, CategoricalResults crResult)
{
super(crResult, 2);
this.numerAtt = numerAtt;
this.threshold = threshold;
}
public NodeCNum(NodeCNum toClone)
{
super(toClone);
this.numerAtt = toClone.numerAtt;
this.threshold = toClone.threshold;
}
@Override
public int getPath(DataPoint dp)
{
double val = dp.getNumericalValues().get(numerAtt);
if( val <= threshold)
return 0;
else
return 1;
}
@Override
public TreeNodeVisitor clone()
{
return new NodeCNum(this);
}
@Override
public Collection featuresUsed()
{
IntList used = new IntList(1);
used.add(numerAtt);
return used;
}
}
/**
* Base node for classification
*/
private static class NodeC extends NodeBase
{
private static final long serialVersionUID = -3977497656918695759L;
private CategoricalResults crResult;
/**
* Creates a new leaf node
* @param crResult the results to return
*/
public NodeC(CategoricalResults crResult)
{
super();
this.crResult = crResult;
children = null;
}
/**
* Creates a new node with children that start out with null (path disabled)
* @param crResult the results to return
* @param children the number of children this node has
*/
public NodeC(CategoricalResults crResult, int children)
{
super(children);
this.crResult = crResult;
}
public NodeC(NodeC toClone)
{
super(toClone);
this.crResult = toClone.crResult.clone();
}
@Override
public CategoricalResults localClassify(DataPoint dp)
{
return crResult;
}
@Override
public int getPath(DataPoint dp)
{
return -1;
}
@Override
public TreeNodeVisitor clone()
{
return new NodeC(this);
}
@Override
public Collection featuresUsed()
{
return Collections.EMPTY_SET;
}
}
/**
* Base node for regression and classification
*/
private static abstract class NodeBase extends TreeNodeVisitor
{
private static final long serialVersionUID = 6783491817922690901L;
protected TreeNodeVisitor[] children;
public NodeBase()
{
}
public NodeBase(int children)
{
this.children = new TreeNodeVisitor[children];
}
public NodeBase(NodeBase toClone)
{
if(toClone.children != null)
{
children = new TreeNodeVisitor[toClone.children.length];
for(int i = 0; i < toClone.children.length; i++)
if(toClone.children[i] != null)
children[i] = toClone.children[i].clone();
}
}
@Override
public int childrenCount()
{
return children.length;
}
@Override
public boolean isLeaf()
{
if(children == null)
return true;
for(int i = 0; i < children.length; i++)
if(children[i] != null)
return false;
return true;
}
@Override
public TreeNodeVisitor getChild(int child)
{
if(child < 0 || child > childrenCount())
return null;
return children[child];
}
@Override
public void disablePath(int child)
{
if(!isLeaf())
children[child] = null;
}
@Override
public boolean isPathDisabled(int child)
{
if(isLeaf())
return true;
return children[child] == null;
}
}
/**
* Base node for regression
*/
private static class NodeR extends NodeBase
{
private static final long serialVersionUID = -2461046505444129890L;
private double result;
/**
* Creates a new leaf node
* @param result the result to return
*/
public NodeR(double result)
{
super();
this.result = result;
}
/**
* Creates a new node with children that start out with null (path disabled)
* @param crResult the results to return
* @param children the number of children this node has
*/
public NodeR(double result, int children)
{
super(children);
this.result = result;
}
public NodeR(NodeR toClone)
{
super(toClone);
this.result = toClone.result;
}
@Override
public double localRegress(DataPoint dp)
{
return result;
}
@Override
public int getPath(DataPoint dp)
{
return -1;
}
@Override
public TreeNodeVisitor clone()
{
return new NodeR(this);
}
@Override
public Collection featuresUsed()
{
return Collections.EMPTY_SET;
}
}
/**
* Base node for regression that splits no a numeric feature
*/
private static class NodeRNum extends NodeR
{
private static final long serialVersionUID = -6775472771777960211L;
private int numerAtt;
private double threshold;
public NodeRNum(int numerAtt, double threshold, double result)
{
super(result, 2);
this.numerAtt = numerAtt;
this.threshold = threshold;
}
public NodeRNum(NodeRNum toClone)
{
super(toClone);
this.numerAtt = toClone.numerAtt;
this.threshold = toClone.threshold;
}
@Override
public int getPath(DataPoint dp)
{
double val = dp.getNumericalValues().get(numerAtt);
if( val <= threshold)
return 0;
else
return 1;
}
@Override
public TreeNodeVisitor clone()
{
return new NodeRNum(this);
}
@Override
public Collection featuresUsed()
{
IntList used = new IntList(1);
used.add(numerAtt);
return used;
}
}
private class NodeRCat extends NodeR
{
private static final long serialVersionUID = 5868393594474661054L;
/**
* Categorical attribute to split on
*/
private int catAtt;
/**
* The cat values that go to the left branch, or null if no binary cats are being used
*/
private int[] leftBranch;
public NodeRCat(int catAtt, int children, double result)
{
super(result, children);
this.catAtt = catAtt;
this.leftBranch = null;
}
public NodeRCat(int catAtt, Set left, double result)
{
super(result, 2);
this.catAtt = catAtt;
this.leftBranch = new int[left.size()];
int pos = 0;
for(int i : left)
leftBranch[pos++] = i;
Arrays.sort(leftBranch);
}
public NodeRCat(NodeRCat toClone)
{
super(toClone);
this.catAtt = toClone.catAtt;
if(toClone.leftBranch != null)
this.leftBranch = Arrays.copyOf(toClone.leftBranch, toClone.leftBranch.length);
}
@Override
public int getPath(DataPoint dp)
{
int[] catVals = dp.getCategoricalValues();
if (leftBranch == null)
return catVals[catAtt];
else
{
if (Arrays.binarySearch(leftBranch, catVals[catAtt]) < 0)
return 1;
else
return 0;
}
}
@Override
public Collection featuresUsed()
{
IntList used = new IntList(1);
used.add(catAtt+numNumericFeatures);
return used;
}
@Override
public TreeNodeVisitor clone()
{
return new NodeRCat(this);
}
}
}
Ads help maintain this website.