#include <M5Tree.hh>

Inheritance diagram for M5Tree:

Classes
struct	tree_experience
struct	tree_node
Public Member Functions
tree_node *	allocateNode ()
void	buildTree (tree_node node, const std::vector< tree_experience > &instances, bool changed)
float	calcSDforSet (const std::vector< tree_experience * > &instances)
float	calcSDR (int dim, float val, const std::vector< tree_experience * > &instances, float sd, std::vector< tree_experience * > &left, std::vector< tree_experience * > &right)
void	compareSplits (float sdr, int dim, float val, const std::vector< tree_experience * > &left, const std::vector< tree_experience * > &right, int nties, float bestSDR, int bestDim, float bestVal, std::vector< tree_experience * > bestLeft, std::vector< tree_experience > *bestRight)
void	copyTree (tree_node newNode, tree_node origNode)
void	deallocateNode (tree_node *node)
void	deleteTree (tree_node *node)
int	fitLinearModel (tree_node node, const std::vector< tree_experience > &instances, std::vector< bool > featureMask, int nFeats, float *resSum)
int	fitSimpleLinearModel (tree_node node, const std::vector< tree_experience > &instances, std::vector< bool > featureMask, int nFeats, float *resSum)
virtual float	getConf (const std::vector< float > &input)
virtual M5Tree *	getCopy ()
tree_node *	getCorrectChild (tree_node *node, const std::vector< float > &input)
void	getFeatsUsed (tree_node node, std::vector< bool > featsUsed)
std::set< float >	getUniques (int dim, const std::vector< tree_experience * > &instances, float &minVal, float &maxVal)
void	implementSplit (tree_node node, const std::vector< tree_experience > &instances, float bestSDR, int bestDim, float bestVal, const std::vector< tree_experience * > &left, const std::vector< tree_experience * > &right, bool changed)
void	initNodes ()
void	initTree ()
void	initTreeNode (tree_node *node)
void	leafPrediction (tree_node t, const std::vector< float > &in, std::map< float, float > retval)
	M5Tree (int id, int trainMode, int trainFreq, int m, float featPct, bool simple, bool allowAllFeats, float min_sdr, Random rng)
	M5Tree (const M5Tree &)
void	makeLeaf (tree_node *node)
bool	passTest (int dim, float val, const std::vector< float > &input)
void	printTree (tree_node *t, int level)
void	pruneTree (tree_node node, const std::vector< tree_experience > &instances)
void	rebuildTree ()
void	removeChildren (tree_node *node)
float *	sortOnDim (int dim, const std::vector< tree_experience * > &instances)
virtual void	testInstance (const std::vector< float > &input, std::map< float, float > *retval)
void	testPossibleSplits (const std::vector< tree_experience * > &instances, float bestSDR, int bestDim, float bestVal, std::vector< tree_experience > bestLeft, std::vector< tree_experience > *bestRight)
virtual bool	trainInstance (classPair &instance)
virtual bool	trainInstances (std::vector< classPair > &instances)
tree_node *	traverseTree (tree_node *node, const std::vector< float > &input)
	~M5Tree ()
Public Attributes
bool	COPYDEBUG
bool	DTDEBUG
bool	INCDEBUG
bool	LMDEBUG
int	nExperiences
bool	NODEDEBUG
float	SPLIT_MARGIN
bool	SPLITDEBUG
bool	STOCH_DEBUG
Private Attributes
tree_experience	allExp [N_M5_EXP]
tree_node	allNodes [N_M5_NODES]
const bool	ALLOW_ALL_FEATS
std::vector< tree_experience * >	experiences
float	featPct
std::vector< int >	freeNodes
const int	freq
bool	hadError
const int	id
tree_node *	lastNode
const int	M
int	maxnodes
const float	MIN_SDR
const int	mode
int	nfeat
int	nnodes
int	nOutput
Random	rng
tree_node *	root
const bool	SIMPLE
int	totalnodes

Detailed Description

M5 regression tree class

Definition at line 27 of file M5Tree.hh.

Constructor & Destructor Documentation

M5Tree::M5Tree	(	int	id,
		int	trainMode,
		int	trainFreq,
		int	m,
		float	featPct,
		bool	simple,
		bool	allowAllFeats,
		float	min_sdr,
		Random	rng
	)

Default constructor

Parameters:

id	id of the tree for debug
trainMode	build every step? only on errors? every freq steps?
trainFreq	frequency of model building if using latter mode
m	# of visits for a given state-action to be considered known
featPct	pct of features to remove from set used for each tree split
simple	do simple linear regression (predict from one variable) rather than full multivariate linear regression
allowAllFeats	all linear regression to use all features, regardless of if they were in the subtree being replaced
min_sdr	Minimum standard deviation reduction for a split to be implemented.
rng	Random Number Generator

true;

Definition at line 22 of file M5Tree.cc.

M5Tree::M5Tree ( const M5Tree & m5 )

Copy constrcutor.

Definition at line 66 of file M5Tree.cc.

M5Tree::~M5Tree ( )

Definition at line 156 of file M5Tree.cc.

Member Function Documentation

M5Tree::tree_node * M5Tree::allocateNode ( )

Allocate a new node from our pre-allocated store of tree nodes

Definition at line 1587 of file M5Tree.cc.

void M5Tree::buildTree	(	tree_node *	node,
		const std::vector< tree_experience * > &	instances,
		bool	changed
	)

Build the tree with the given instances from the given tree node

Definition at line 565 of file M5Tree.cc.

float M5Tree::calcSDforSet ( const std::vector< tree_experience * > & instances )

Calculate the standard deviation for the given vector of experiences

Definition at line 1406 of file M5Tree.cc.

float M5Tree::calcSDR	(	int	dim,
		float	val,
		const std::vector< tree_experience * > &	instances,
		float	sd,
		std::vector< tree_experience * > &	left,
		std::vector< tree_experience * > &	right
	)

Calculate the reduction in standard deviation on each side of the proposed tree split

Definition at line 1356 of file M5Tree.cc.

void M5Tree::compareSplits	(	float	sdr,
		int	dim,
		float	val,
		const std::vector< tree_experience * > &	left,
		const std::vector< tree_experience * > &	right,
		int *	nties,
		float *	bestSDR,
		int *	bestDim,
		float *	bestVal,
		std::vector< tree_experience * > *	bestLeft,
		std::vector< tree_experience * > *	bestRight
	)

Compare the current split to determine if it is the best split.

Definition at line 1303 of file M5Tree.cc.

void M5Tree::copyTree	(	tree_node *	newNode,
		tree_node *	origNode
	)

Make a copy of the subtree from origNode to newNode

Definition at line 120 of file M5Tree.cc.

void M5Tree::deallocateNode ( tree_node * node )

Return tree node back to store of nodes

Definition at line 1606 of file M5Tree.cc.

void M5Tree::deleteTree ( tree_node * node )

Delete this tree node and all nodes below it in the tree.

Definition at line 492 of file M5Tree.cc.

int M5Tree::fitLinearModel	(	tree_node *	node,
		const std::vector< tree_experience * > &	instances,
		std::vector< bool >	featureMask,
		int	nFeats,
		float *	resSum
	)

Fit a multivariate linear regression model to the given instances.

Definition at line 808 of file M5Tree.cc.

int M5Tree::fitSimpleLinearModel	(	tree_node *	node,
		const std::vector< tree_experience * > &	instances,
		std::vector< bool >	featureMask,
		int	nFeats,
		float *	resSum
	)

Fit a simple linear regression model to the given instances.

Definition at line 1011 of file M5Tree.cc.

float M5Tree::getConf ( const std::vector< float > & input ) [virtual]

Implements Classifier.

Definition at line 416 of file M5Tree.cc.

M5Tree * M5Tree::getCopy ( ) [virtual]

Implements Classifier.

Definition at line 151 of file M5Tree.cc.

M5Tree::tree_node * M5Tree::getCorrectChild	(	tree_node *	node,
		const std::vector< float > &	input
	)

Get the correct child of this node for a given input

Definition at line 528 of file M5Tree.cc.

void M5Tree::getFeatsUsed	(	tree_node *	node,
		std::vector< bool > *	featsUsed
	)

Determine the features used for splits in the given subtree

Definition at line 1223 of file M5Tree.cc.

std::set< float > M5Tree::getUniques	(	int	dim,
		const std::vector< tree_experience * > &	instances,
		float &	minVal,
		float &	maxVal
	)

Get all the unique values of the features on dimension dim

Definition at line 1432 of file M5Tree.cc.

void M5Tree::implementSplit	(	tree_node *	node,
		const std::vector< tree_experience * > &	instances,
		float	bestSDR,
		int	bestDim,
		float	bestVal,
		const std::vector< tree_experience * > &	left,
		const std::vector< tree_experience * > &	right,
		bool	changed
	)

Implement the given split at the given node

Definition at line 1125 of file M5Tree.cc.

void M5Tree::initNodes ( )

Initialize our store of tree nodes

Definition at line 1575 of file M5Tree.cc.

void M5Tree::initTree ( )

Initialize the tree

Definition at line 445 of file M5Tree.cc.

void M5Tree::initTreeNode ( tree_node * node )

Initialize the tree_node struct

Definition at line 461 of file M5Tree.cc.

void M5Tree::leafPrediction	(	tree_node *	t,
		const std::vector< float > &	in,
		std::map< float, float > *	retval
	)

Get the prediction for the given inputs at the leaf node t

Definition at line 1553 of file M5Tree.cc.

void M5Tree::makeLeaf ( tree_node * node )

Make the given node into a leaf node.

Definition at line 651 of file M5Tree.cc.

bool M5Tree::passTest	(	int	dim,
		float	val,
		const std::vector< float > &	input
	)

Determine if the input passes the test defined by dim, val, type

Definition at line 553 of file M5Tree.cc.

void M5Tree::printTree	(	tree_node *	t,
		int	level
	)

Print the tree for debug purposes.

Definition at line 1516 of file M5Tree.cc.

void M5Tree::pruneTree	(	tree_node *	node,
		const std::vector< tree_experience * > &	instances
	)

Possibly prune the tree back at this node. Compare sub tree error with error of a linear regression model.

Definition at line 685 of file M5Tree.cc.

void M5Tree::rebuildTree ( )

Rebuild the tree

Definition at line 387 of file M5Tree.cc.

void M5Tree::removeChildren ( tree_node * node )

Remove the children of the given node (to turn it into a regression node)

Definition at line 667 of file M5Tree.cc.

float * M5Tree::sortOnDim	(	int	dim,
		const std::vector< tree_experience * > &	instances
	)

Returns an array of the values of features at the index dim, sorted from lowest to highest

Definition at line 1461 of file M5Tree.cc.

void M5Tree::testInstance	(	const std::vector< float > &	input,
		std::map< float, float > *	retval
	)		`[virtual]`

Implements Classifier.

Definition at line 396 of file M5Tree.cc.

void M5Tree::testPossibleSplits	(	const std::vector< tree_experience * > &	instances,
		float *	bestSDR,
		int *	bestDim,
		float *	bestVal,
		std::vector< tree_experience * > *	bestLeft,
		std::vector< tree_experience * > *	bestRight
	)