mlpack
1.0.12
|
A density estimation tree is similar to both a decision tree and a space partitioning tree (like a kd-tree). More...
Public Member Functions | |
DTree () | |
Create an empty density estimation tree. More... | |
DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t totalPoints) | |
Create a density estimation tree with the given bounds and the given number of total points. More... | |
DTree (arma::mat &data) | |
Create a density estimation tree on the given data. More... | |
DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t start, const size_t end, const double logNegError) | |
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end and the specified error. More... | |
DTree (const arma::vec &maxVals, const arma::vec &minVals, const size_t totalPoints, const size_t start, const size_t end) | |
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end, and calculating the error with the total number of points given. More... | |
~DTree () | |
Clean up memory allocated by the tree. More... | |
double | AlphaUpper () const |
Return the upper part of the alpha sum. More... | |
double | ComputeValue (const arma::vec &query) const |
Compute the logarithm of the density estimate of a given query point. More... | |
void | ComputeVariableImportance (arma::vec &importances) const |
Compute the variable importance of each dimension in the learned tree. More... | |
size_t | End () const |
Return the first index of a point not contained in this node. More... | |
int | FindBucket (const arma::vec &query) const |
Return the tag of the leaf containing the query. More... | |
double | Grow (arma::mat &data, arma::Col< size_t > &oldFromNew, const bool useVolReg=false, const size_t maxLeafSize=10, const size_t minLeafSize=5) |
Greedily expand the tree. More... | |
DTree * | Left () const |
Return the left child. More... | |
double | LogNegativeError (const size_t totalPoints) const |
Compute the log-negative-error for this point, given the total number of points in the dataset. More... | |
double | LogNegError () const |
Return the log negative error of this node. More... | |
double | LogVolume () const |
Return the inverse of the volume of this node. More... | |
const arma::vec & | MaxVals () const |
Return the maximum values. More... | |
arma::vec & | MaxVals () |
Modify the maximum values. More... | |
const arma::vec & | MinVals () const |
Return the minimum values. More... | |
arma::vec & | MinVals () |
Modify the minimum values. More... | |
double | PruneAndUpdate (const double oldAlpha, const size_t points, const bool useVolReg=false) |
Perform alpha pruning on a tree. More... | |
double | Ratio () const |
Return the ratio of points in this node to the points in the whole dataset. More... | |
DTree * | Right () const |
Return the right child. More... | |
bool | Root () const |
Return whether or not this is the root of the tree. More... | |
size_t | SplitDim () const |
Return the split dimension of this node. More... | |
double | SplitValue () const |
Return the split value of this node. More... | |
size_t | Start () const |
Return the starting index of points contained in this node. More... | |
size_t | SubtreeLeaves () const |
Return the number of leaves which are descendants of this node. More... | |
double | SubtreeLeavesLogNegError () const |
Return the log negative error of all descendants of this node. More... | |
int | TagTree (const int tag=0) |
Index the buckets for possible usage later; this results in every leaf in the tree having a specific tag (accessible with BucketTag()). More... | |
std::string | ToString () const |
Returns a string representation of this object. More... | |
bool | WithinRange (const arma::vec &query) const |
Return whether a query point is within the range of this node. More... | |
void | WriteTree (FILE *fp, const size_t level=0) const |
Print the tree in a depth-first manner (this function is called recursively). More... | |
Private Member Functions | |
bool | FindSplit (const arma::mat &data, size_t &splitDim, double &splitValue, double &leftError, double &rightError, const size_t minLeafSize=5) const |
Find the dimension to split on. More... | |
size_t | SplitData (arma::mat &data, const size_t splitDim, const double splitValue, arma::Col< size_t > &oldFromNew) const |
Split the data, returning the number of points left of the split. More... | |
Private Attributes | |
double | alphaUpper |
Upper part of alpha sum; used for pruning. More... | |
int | bucketTag |
The tag for the leaf, used for hashing points. More... | |
size_t | end |
The index of the last point in the dataset contained in this node (and its children). More... | |
DTree * | left |
The left child. More... | |
double | logNegError |
log-negative-L2-error of the node. More... | |
double | logVolume |
The logarithm of the volume of the node. More... | |
arma::vec | maxVals |
Upper half of bounding box for this node. More... | |
arma::vec | minVals |
Lower half of bounding box for this node. More... | |
double | ratio |
Ratio of the number of points in the node to the total number of points. More... | |
DTree * | right |
The right child. More... | |
bool | root |
If true, this node is the root of the tree. More... | |
size_t | splitDim |
The splitting dimension for this node. More... | |
double | splitValue |
The split value on the splitting dimension for this node. More... | |
size_t | start |
The index of the first point in the dataset contained in this node (and its children). More... | |
size_t | subtreeLeaves |
Number of leaves of the subtree. More... | |
double | subtreeLeavesLogNegError |
Sum of the error of the leaves of the subtree. More... | |
A density estimation tree is similar to both a decision tree and a space partitioning tree (like a kd-tree).
Each leaf represents a constant-density hyper-rectangle. The tree is constructed in such a way as to minimize the integrated square error between the probability distribution of the tree and the observed probability distribution of the data. Because the tree is similar to a decision tree, the density estimation tree can provide very fast density estimates for a given point.
For more information, see the following paper:
mlpack::det::DTree::DTree | ( | ) |
Create an empty density estimation tree.
mlpack::det::DTree::DTree | ( | const arma::vec & | maxVals, |
const arma::vec & | minVals, | ||
const size_t | totalPoints | ||
) |
Create a density estimation tree with the given bounds and the given number of total points.
Children will not be created.
maxVals | Maximum values of the bounding box. |
minVals | Minimum values of the bounding box. |
totalPoints | Total number of points in the dataset. |
mlpack::det::DTree::DTree | ( | arma::mat & | data | ) |
Create a density estimation tree on the given data.
Children will be created following the procedure outlined in the paper. The data will be modified; it will be reordered similar to the way BinarySpaceTree modifies datasets.
data | Dataset to build tree on. |
mlpack::det::DTree::DTree | ( | const arma::vec & | maxVals, |
const arma::vec & | minVals, | ||
const size_t | start, | ||
const size_t | end, | ||
const double | logNegError | ||
) |
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end and the specified error.
Children of this node will not be created recursively.
maxVals | Upper bound of bounding box. |
minVals | Lower bound of bounding box. |
start | Start of points represented by this node in the data matrix. |
end | End of points represented by this node in the data matrix. |
error | log-negative error of this node. |
mlpack::det::DTree::DTree | ( | const arma::vec & | maxVals, |
const arma::vec & | minVals, | ||
const size_t | totalPoints, | ||
const size_t | start, | ||
const size_t | end | ||
) |
Create a child node of a density estimation tree given the bounding box specified by maxVals and minVals, using the size given in start and end, and calculating the error with the total number of points given.
Children of this node will not be created recursively.
maxVals | Upper bound of bounding box. |
minVals | Lower bound of bounding box. |
start | Start of points represented by this node in the data matrix. |
end | End of points represented by this node in the data matrix. |
mlpack::det::DTree::~DTree | ( | ) |
Clean up memory allocated by the tree.
|
inline |
Return the upper part of the alpha sum.
Definition at line 276 of file dtree.hpp.
References alphaUpper.
double mlpack::det::DTree::ComputeValue | ( | const arma::vec & | query | ) | const |
Compute the logarithm of the density estimate of a given query point.
query | Point to estimate density of. |
void mlpack::det::DTree::ComputeVariableImportance | ( | arma::vec & | importances | ) | const |
Compute the variable importance of each dimension in the learned tree.
importances | Vector to store the calculated importances in. |
|
inline |
int mlpack::det::DTree::FindBucket | ( | const arma::vec & | query | ) | const |
Return the tag of the leaf containing the query.
This is useful for generating class memberships.
query | Query to search for. |
|
private |
Find the dimension to split on.
double mlpack::det::DTree::Grow | ( | arma::mat & | data, |
arma::Col< size_t > & | oldFromNew, | ||
const bool | useVolReg = false , |
||
const size_t | maxLeafSize = 10 , |
||
const size_t | minLeafSize = 5 |
||
) |
Greedily expand the tree.
The points in the dataset will be reordered during tree growth.
data | Dataset to build tree on. |
oldFromNew | Mappings from old points to new points. |
useVolReg | If true, volume regularization is used. |
maxLeafSize | Maximum size of a leaf. |
minLeafSize | Minimum size of a leaf. |
|
inline |
double mlpack::det::DTree::LogNegativeError | ( | const size_t | totalPoints | ) | const |
Compute the log-negative-error for this point, given the total number of points in the dataset.
totalPoints | Total number of points in the dataset. |
|
inline |
Return the log negative error of this node.
Definition at line 259 of file dtree.hpp.
References logNegError.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
double mlpack::det::DTree::PruneAndUpdate | ( | const double | oldAlpha, |
const size_t | points, | ||
const bool | useVolReg = false |
||
) |
Perform alpha pruning on a tree.
Returns the new value of alpha.
oldAlpha | Old value of alpha. |
points | Total number of points in dataset. |
useVolReg | If true, volume regularization is used. |
|
inline |
|
inline |
|
inline |
|
private |
Split the data, returning the number of points left of the split.
|
inline |
|
inline |
Return the split value of this node.
Definition at line 257 of file dtree.hpp.
References splitValue.
|
inline |
|
inline |
Return the number of leaves which are descendants of this node.
Definition at line 263 of file dtree.hpp.
References subtreeLeaves.
|
inline |
Return the log negative error of all descendants of this node.
Definition at line 261 of file dtree.hpp.
References subtreeLeavesLogNegError.
int mlpack::det::DTree::TagTree | ( | const int | tag = 0 | ) |
Index the buckets for possible usage later; this results in every leaf in the tree having a specific tag (accessible with BucketTag()).
This function calls itself recursively.
tag | Tag for the next leaf; leave at 0 for the initial call. |
std::string mlpack::det::DTree::ToString | ( | ) | const |
Returns a string representation of this object.
bool mlpack::det::DTree::WithinRange | ( | const arma::vec & | query | ) | const |
Return whether a query point is within the range of this node.
void mlpack::det::DTree::WriteTree | ( | FILE * | fp, |
const size_t | level = 0 |
||
) | const |
Print the tree in a depth-first manner (this function is called recursively).
fp | File to write the tree to. |
level | Level of the tree (should start at 0). |
|
private |
Upper part of alpha sum; used for pruning.
Definition at line 242 of file dtree.hpp.
Referenced by AlphaUpper().
|
private |
|
private |
|
private |
|
private |
log-negative-L2-error of the node.
Definition at line 221 of file dtree.hpp.
Referenced by LogNegError().
|
private |
The logarithm of the volume of the node.
Definition at line 236 of file dtree.hpp.
Referenced by LogVolume().
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
The splitting dimension for this node.
Definition at line 215 of file dtree.hpp.
Referenced by SplitDim().
|
private |
The split value on the splitting dimension for this node.
Definition at line 218 of file dtree.hpp.
Referenced by SplitValue().
|
private |
|
private |
Number of leaves of the subtree.
Definition at line 227 of file dtree.hpp.
Referenced by SubtreeLeaves().
|
private |
Sum of the error of the leaves of the subtree.
Definition at line 224 of file dtree.hpp.
Referenced by SubtreeLeavesLogNegError().