Loading...
Searching...
No Matches
DecisionTree.h
Go to the documentation of this file.
/* ----------------------------------------------------------------------------
* GTSAM Copyright 2010, Georgia Tech Research Corporation,
* Atlanta, Georgia 30332-0415
* All Rights Reserved
* Authors: Frank Dellaert, et al. (see THANKS for the full author list)
* See LICENSE for the license information
* -------------------------------------------------------------------------- */
#pragma once
#include <gtsam/base/Testable.h>
#include <gtsam/base/types.h>
#include <gtsam/discrete/Assignment.h>
#include <boost/serialization/nvp.hpp>
#include <boost/shared_ptr.hpp>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
namespace gtsam {
template<typename L, typename Y>
class DecisionTree {
protected:
static bool DefaultCompare(const Y& a, const Y& b) {
return a == b;
}
public:
using LabelFormatter = std::function<std::string(L)>;
using ValueFormatter = std::function<std::string(Y)>;
using CompareFunc = std::function<bool(const Y&, const Y&)>;
using Unary = std::function<Y(const Y&)>;
using UnaryAssignment = std::function<Y(const Assignment<L>&, const Y&)>;
using Binary = std::function<Y(const Y&, const Y&)>;
using LabelC = std::pair<L, size_t>;
struct Leaf;
struct Choice;
struct Node {
using Ptr = boost::shared_ptr<const Node>;
#ifdef DT_DEBUG_MEMORY
static int nrNodes;
#endif
// Constructor
Node() {
#ifdef DT_DEBUG_MEMORY
std::cout << ++nrNodes << " constructed " << id() << std::endl;
std::cout.flush();
#endif
}
// Destructor
virtual ~Node() {
#ifdef DT_DEBUG_MEMORY
std::cout << --nrNodes << " destructed " << id() << std::endl;
std::cout.flush();
#endif
}
// Unique ID for dot files
const void* id() const { return this; }
// everything else is virtual, no documentation here as internal
virtual void print(const std::string& s,
const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter) const = 0;
virtual void dot(std::ostream& os, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter,
bool showZero) const = 0;
virtual bool sameLeaf(const Leaf& q) const = 0;
virtual bool sameLeaf(const Node& q) const = 0;
virtual bool equals(const Node& other, const CompareFunc& compare =
&DefaultCompare) const = 0;
virtual const Y& operator()(const Assignment<L>& x) const = 0;
virtual Ptr apply(const Unary& op) const = 0;
virtual Ptr apply(const UnaryAssignment& op,
const Assignment<L>& assignment) const = 0;
virtual Ptr apply_f_op_g(const Node&, const Binary&) const = 0;
virtual Ptr apply_g_op_fL(const Leaf&, const Binary&) const = 0;
virtual Ptr apply_g_op_fC(const Choice&, const Binary&) const = 0;
virtual Ptr choose(const L& label, size_t index) const = 0;
virtual bool isLeaf() const = 0;
private:
friend class boost::serialization::access;
template <class ARCHIVE>
void serialize(ARCHIVE& ar, const unsigned int /*version*/) {}
};
public:
using NodePtr = typename Node::Ptr;
NodePtr root_;
protected:
template<typename It, typename ValueIt>
NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY) const;
template <typename M, typename X>
NodePtr convertFrom(const typename DecisionTree<M, X>::NodePtr& f,
std::function<L(const M&)> L_of_M,
std::function<Y(const X&)> Y_of_X) const;
public:
DecisionTree();
explicit DecisionTree(const Y& y);
DecisionTree(const L& label, const Y& y1, const Y& y2);
DecisionTree(const LabelC& label, const Y& y1, const Y& y2);
DecisionTree(const std::vector<LabelC>& labelCs, const std::vector<Y>& ys);
DecisionTree(const std::vector<LabelC>& labelCs, const std::string& table);
template<typename Iterator>
DecisionTree(Iterator begin, Iterator end, const L& label);
DecisionTree(const L& label, const DecisionTree& f0,
const DecisionTree& f1);
template <typename X, typename Func>
DecisionTree(const DecisionTree<L, X>& other, Func Y_of_X);
template <typename M, typename X, typename Func>
DecisionTree(const DecisionTree<M, X>& other, const std::map<M, L>& map,
Func Y_of_X);
void print(const std::string& s, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter) const;
// Testable
bool equals(const DecisionTree& other,
const CompareFunc& compare = &DefaultCompare) const;
virtual ~DecisionTree() = default;
bool empty() const { return !root_; }
bool operator==(const DecisionTree& q) const;
const Y& operator()(const Assignment<L>& x) const;
template <typename Func>
void visit(Func f) const;
template <typename Func>
void visitLeaf(Func f) const;
template <typename Func>
void visitWith(Func f) const;
size_t nrLeaves() const;
template <typename Func, typename X>
X fold(Func f, X x0) const;
std::set<L> labels() const;
DecisionTree apply(const Unary& op) const;
DecisionTree apply(const UnaryAssignment& op) const;
DecisionTree apply(const DecisionTree& g, const Binary& op) const;
DecisionTree choose(const L& label, size_t index) const {
NodePtr newRoot = root_->choose(label, index);
return DecisionTree(newRoot);
}
DecisionTree combine(const L& label, size_t cardinality,
const Binary& op) const;
DecisionTree combine(const LabelC& labelC, const Binary& op) const {
return combine(labelC.first, labelC.second, op);
}
void dot(std::ostream& os, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter, bool showZero = true) const;
void dot(const std::string& name, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter, bool showZero = true) const;
std::string dot(const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter,
bool showZero = true) const;
// internal use only
explicit DecisionTree(const NodePtr& root);
// internal use only
template<typename Iterator> NodePtr
compose(Iterator begin, Iterator end, const L& label) const;
private:
friend class boost::serialization::access;
template <class ARCHIVE>
void serialize(ARCHIVE& ar, const unsigned int /*version*/) {
ar& BOOST_SERIALIZATION_NVP(root_);
}
}; // DecisionTree
template <class L, class Y>
struct traits<DecisionTree<L, Y>> : public Testable<DecisionTree<L, Y>> {};
template<typename L, typename Y>
DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
const typename DecisionTree<L, Y>::Unary& op) {
return f.apply(op);
}
template<typename L, typename Y>
DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
const typename DecisionTree<L, Y>::UnaryAssignment& op) {
return f.apply(op);
}
template<typename L, typename Y>
DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
const DecisionTree<L, Y>& g,
const typename DecisionTree<L, Y>::Binary& op) {
return f.apply(g, op);
}
template <typename L, typename T1, typename T2>
std::pair<DecisionTree<L, T1>, DecisionTree<L, T2> > unzip(
const DecisionTree<L, std::pair<T1, T2> >& input) {
return std::make_pair(
DecisionTree<L, T1>(input, [](std::pair<T1, T2> i) { return i.first; }),
DecisionTree<L, T2>(input,
[](std::pair<T1, T2> i) { return i.second; }));
}
} // namespace gtsam
types.h
Typedefs for easier changing of types.
Testable.h
Concept check for values that can be used in unit tests.
Assignment.h
An assignment from labels to a discrete value index (size_t).
gtsam
Global functions in a separate testing namespace.
Definition chartTesting.h:28
gtsam::unzip
std::pair< DecisionTree< L, T1 >, DecisionTree< L, T2 > > unzip(const DecisionTree< L, std::pair< T1, T2 > > &input)
unzip a DecisionTree with std::pair values.
Definition DecisionTree.h:440
gtsam::apply
DecisionTree< L, Y > apply(const DecisionTree< L, Y > &f, const typename DecisionTree< L, Y >::Unary &op)
free versions of apply
Definition DecisionTree.h:413
gtsam::traits
A manifold defines a space in which there is a notion of a linear tangent space that can be centered ...
Definition concepts.h:30
gtsam::Testable
A helper that implements the traits interface for GTSAM types.
Definition Testable.h:151
gtsam::Assignment
An assignment from labels to value index (size_t).
Definition Assignment.h:37
gtsam::DecisionTree::Leaf
Definition DecisionTree-inl.h:52
gtsam::DecisionTree::Choice
Definition DecisionTree-inl.h:172
gtsam::DecisionTree
a decision tree is a function from assignments to values.
Definition DecisionTree.h:61
gtsam::DecisionTree::apply
DecisionTree apply(const Unary &op) const
apply Unary operation "op" to f
Definition DecisionTree-inl.h:889
gtsam::DecisionTree::choose
DecisionTree choose(const L &label, size_t index) const
create a new function where value(label)==index It's like "restrict" in Darwiche09book pg329,...
Definition DecisionTree.h:358
gtsam::DecisionTree::convertFrom
NodePtr convertFrom(const typename DecisionTree< M, X >::NodePtr &f, std::function< L(const M &)> L_of_M, std::function< Y(const X &)> Y_of_X) const
Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.
Definition DecisionTree-inl.h:671
gtsam::DecisionTree::combine
DecisionTree combine(const LabelC &labelC, const Binary &op) const
combine with LabelC for convenience
Definition DecisionTree.h:368
gtsam::DecisionTree::DecisionTree
DecisionTree(Iterator begin, Iterator end, const L &label)
Create DecisionTree from others.
Definition DecisionTree-inl.h:523
gtsam::DecisionTree::create
NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY) const
Internal recursive function to create from keys, cardinalities, and Y values.
Definition DecisionTree-inl.h:630
gtsam::DecisionTree::~DecisionTree
virtual ~DecisionTree()=default
Make virtual.
gtsam::DecisionTree::DefaultCompare
static bool DefaultCompare(const Y &a, const Y &b)
Default method for comparison of two objects of type Y.
Definition DecisionTree.h:64
gtsam::DecisionTree< L, double >::NodePtr
typename Node::Ptr NodePtr
Definition DecisionTree.h:143
gtsam::DecisionTree::DecisionTree
DecisionTree(const std::vector< LabelC > &labelCs, const std::string &table)
Create from keys and string table.
Definition DecisionTree-inl.h:509
gtsam::DecisionTree::labels
std::set< L > labels() const
Retrieve all unique labels as a set.
Definition DecisionTree-inl.h:853
gtsam::DecisionTree::DecisionTree
DecisionTree(const DecisionTree< L, X > &other, Func Y_of_X)
Convert from a different value type.
Definition DecisionTree-inl.h:539
gtsam::DecisionTree::apply
DecisionTree apply(const DecisionTree &g, const Binary &op) const
apply binary operation "op" to f and g
Definition DecisionTree-inl.h:913
gtsam::DecisionTree::empty
bool empty() const
Check if tree is empty.
Definition DecisionTree.h:257
gtsam::DecisionTree::visit
void visit(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:736
gtsam::DecisionTree::visitLeaf
void visitLeaf(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:773
gtsam::DecisionTree< L, double >::Unary
std::function< double(const double &)> Unary
Definition DecisionTree.h:74
gtsam::DecisionTree::DecisionTree
DecisionTree(const Y &y)
Create a constant.
Definition DecisionTree-inl.h:472
gtsam::DecisionTree::apply
DecisionTree apply(const UnaryAssignment &op) const
Apply Unary operation "op" to f while also providing the corresponding assignment.
Definition DecisionTree-inl.h:900
gtsam::DecisionTree::fold
X fold(Func f, X x0) const
Fold a binary function over the tree, returning accumulator.
Definition DecisionTree-inl.h:833
gtsam::DecisionTree< L, double >::root_
NodePtr root_
Definition DecisionTree.h:146
gtsam::DecisionTree::print
void print(const std::string &s, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter) const
GTSAM-style print.
Definition DecisionTree-inl.h:872
gtsam::DecisionTree::combine
DecisionTree combine(const L &label, size_t cardinality, const Binary &op) const
combine subtrees on key with binary operation "op"
Definition DecisionTree-inl.h:937
gtsam::DecisionTree::dot
std::string dot(const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
output to graphviz format string
Definition DecisionTree-inl.h:973
gtsam::DecisionTree::visitWith
void visitWith(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:816
gtsam::DecisionTree::DecisionTree
DecisionTree(const LabelC &label, const Y &y1, const Y &y2)
Allow Label+Cardinality for convenience.
Definition DecisionTree-inl.h:488
gtsam::DecisionTree::operator()
const Y & operator()(const Assignment< L > &x) const
evaluate
Definition DecisionTree-inl.h:884
gtsam::DecisionTree::dot
void dot(std::ostream &os, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
output to graphviz format, stream version
Definition DecisionTree-inl.h:949
gtsam::DecisionTree::dot
void dot(const std::string &name, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
output to graphviz format, open a file
Definition DecisionTree-inl.h:959
gtsam::DecisionTree::DecisionTree
DecisionTree(const DecisionTree< M, X > &other, const std::map< M, L > &map, Func Y_of_X)
Convert from a different value type X to value type Y, also transate labels via map from type M to L.
Definition DecisionTree-inl.h:549
gtsam::DecisionTree::DecisionTree
DecisionTree(const std::vector< LabelC > &labelCs, const std::vector< Y > &ys)
Create from keys and a corresponding vector of values.
Definition DecisionTree-inl.h:501
gtsam::DecisionTree::operator==
bool operator==(const DecisionTree &q) const
equality
Definition DecisionTree-inl.h:879
gtsam::DecisionTree< L, double >::LabelC
std::pair< L, size_t > LabelC
Definition DecisionTree.h:79
gtsam::DecisionTree::DecisionTree
DecisionTree(const L &label, const Y &y1, const Y &y2)
Create tree with 2 assignments y1, y2, splitting on variable label.
Definition DecisionTree-inl.h:478
gtsam::DecisionTree::nrLeaves
size_t nrLeaves() const
Return the number of leaves in the tree.
Definition DecisionTree-inl.h:823
gtsam::DecisionTree::DecisionTree
DecisionTree()
Default constructor (for serialization).
Definition DecisionTree-inl.h:462
gtsam::DecisionTree::DecisionTree
DecisionTree(const L &label, const DecisionTree &f0, const DecisionTree &f1)
Create DecisionTree from two others.
Definition DecisionTree-inl.h:530
gtsam::DecisionTree::Node::access
friend class boost::serialization::access
Serialization function.
Definition DecisionTree.h:135