package jsat.classifiers.trees;

import java.io.Serializable;
import java.util.Collection;
import java.util.List;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.DataPoint;
import jsat.linear.DenseVector;

/**
 * Provides an abstracted mechanism for traversing and predicting from nodes in 
 * a tree meant for a supervised learning problem. Paths and children
 *  are used interchangeably, every node has one path to one child
* Paths to children nodes can be disabled, but not removed. This is done so * that the implementation does not have to worry about changes in the indices * to children nodes, which would be complicated to implement. Once a path is * disabled, it can not be re-enabled.
* If all paths to any children have been disabled, {@link #childrenCount() } * may choose to return 0, otherwise - it must return the original number of * paths to children nodes. * * The implementation for a given tree should override * {@link #localClassify(jsat.classifiers.DataPoint) } and * {@link #localRegress(jsat.classifiers.DataPoint) } if the operations are * supported. * * @author Edward Raff * @see TreeLearner * @see TreePruner */ public abstract class TreeNodeVisitor implements Serializable, Cloneable { private static final long serialVersionUID = 4026847401940409114L; /** * Returns the number of children this node of the tree has, and may return * a non zero value even if the node is a leaf * @return the number of children this node has */ abstract public int childrenCount(); /** * Returns true if the node is a leaf, meaning it has no valid paths to any * children * * @return true if the node is purely a leaf node */ abstract public boolean isLeaf(); /** * Returns the node for the specific child, or null if the child index was * not valid * @param child the index of the child node to obtain * @return the node for the child */ abstract public TreeNodeVisitor getChild(int child); /** * Disables the selected path to the specified child from the current node. * All child indices will not be effected by this operation. * * @param child the index of the child to disable the path too */ abstract public void disablePath(int child); /** * Optional operation!
* This method, if supported, will set the path so that the child is set to the given value. *
* The implementation may choose to throw an exception if the NodeVisitor is not of the same * implementing class. * @param child the child path * @param node the node to make the child */ public void setPath(int child, TreeNodeVisitor node) { throw new UnsupportedOperationException("setPath is an optional operation."); } /** * Returns true if the path to the specified child is disabled, meaning it * can not be traveled to. It will also return true for an invalid child * path, since a non existent node can not be reached. * * @param child the child index to check the path for * @return true if the path is unavailable, false if the * path is good. */ abstract public boolean isPathDisabled(int child); /** * Returns the classification result that would have been obtained if the * current node was a leaf node. * * @param dp the data point to localClassify * @return the classification result * @throws UnsupportedOperationException if the tree node does not support * or was not trained for classification */ public CategoricalResults localClassify(DataPoint dp) { throw new UnsupportedOperationException("This tree does not support classification"); } /** * Returns the path down the tree the given data point would have taken, or * -1 if this node was a leaf node OR if a missing value prevent traversal * down the path * @param dp the data point to send down the tree * @return the path that would be taken */ abstract public int getPath(DataPoint dp); /** * Returns the relative weight of each path, which should be an indication * of how much of the training data went down each path. By default, returns 1.0/{@link #childrenCount() * }. The result should sum to one * * @param path the path to select * @return the fraction of data estimated to travel the specified path, with * respect to data that reaches this node. */ public double getPathWeight(int path) { return 1.0/childrenCount(); } public CategoricalResults classify(DataPoint dp) { TreeNodeVisitor node = this; while(!node.isLeaf()) { int path = node.getPath(dp); if(path < 0 )//missing value case { double sum = 0; DenseVector resultSum = null; for(int child = 0; child < childrenCount(); child++) { if(node.isPathDisabled(child)) continue; CategoricalResults child_result = node.getChild(child).classify(dp); if(resultSum == null) resultSum = new DenseVector(child_result.size()); sum += node.getPathWeight(child); resultSum.mutableAdd(node.getPathWeight(child), child_result.getVecView()); } if(resultSum == null)//all paths disabled? break;//break out and do local classify if(sum < 1.0-1e-5)//re-normalize our result resultSum.mutableDivide(sum+1e-6); return new CategoricalResults(resultSum.arrayCopy()); } if(node.isPathDisabled(path))//return local classification dec break; node = node.getChild(path); } return node.localClassify(dp); } /** * Returns the regression result that would have been obtained if the * current node was a leaf node. * * @param dp the data point to regress * @return the classification result * @throws UnsupportedOperationException if the tree node does not support * or was not trained for classification */ public double localRegress(DataPoint dp) { throw new UnsupportedOperationException("This tree does not support classification"); } /** * Performs regression on the given data point by following it down the tree * until it finds the correct terminal node. * * @param dp the data point to regress * @return the regression result from the tree starting from the current node */ public double regress(DataPoint dp) { TreeNodeVisitor node = this; while(!node.isLeaf()) { int path = node.getPath(dp); if(path < 0 )//missing value case { double sum = 0; double resultSum = 0; for(int child = 0; child < childrenCount(); child++) { if(node.isPathDisabled(child)) continue; double child_result = node.getChild(child).regress(dp); sum += node.getPathWeight(child); resultSum += node.getPathWeight(child)*child_result; } if(sum == 0)//all paths disabled? break;//break out and do local classify if(sum < 1.0-1e-5)//re-normalize our result resultSum /= (sum+1e-6); return resultSum; } if(node.isPathDisabled(path))//if missing value makes path < 0, return local regression dec break; node = node.getChild(path); } return node.localRegress(dp); } /** * Returns a collection of the indices of the features used by this node in * the tree to make its decision about what branch to use next. Numeric * features start from zero, and categorical features start from the number * of numeric features. * * @return the integers indicating which features were used for this node in * the tree. */ abstract public Collection featuresUsed(); @Override abstract public TreeNodeVisitor clone(); }

Ads help maintain this website.