mlpack: a scalable c++ machine learning library
mlpack  2.0.2
x_tree_split.hpp
Go to the documentation of this file.
1 
17 #ifndef mlpack_CORE_TREE_RECTANGLE_TREE_X_TREE_SPLIT_HPP
18 #define mlpack_CORE_TREE_RECTANGLE_TREE_X_TREE_SPLIT_HPP
19 
20 #include <mlpack/core.hpp>
21 
22 namespace mlpack {
23 namespace tree {
24 
31 const double MAX_OVERLAP = 0.2;
32 
38 template<typename TreeType>
40 {
41  public:
43  XTreeSplit();
44 
46  XTreeSplit(const TreeType* node);
47 
49  XTreeSplit(const TreeType& other);
50 
56  void SplitLeafNode(TreeType* tree, std::vector<bool>& relevels);
57 
62  bool SplitNonLeafNode(TreeType* tree, std::vector<bool>& relevels);
63 
68  typedef struct SplitHistoryStruct
69  {
71  std::vector<bool> history;
72 
73  SplitHistoryStruct(int dim) : lastDimension(0), history(dim)
74  {
75  for (int i = 0; i < dim; i++)
76  history[i] = false;
77  }
78 
79  template<typename Archive>
80  void Serialize(Archive& ar, const unsigned int /* version */)
81  {
82  ar & data::CreateNVP(lastDimension, "lastDimension");
83  ar & data::CreateNVP(history, "history");
84  }
86 
87  private:
92 
96  template<typename ElemType>
97  class sortStruct
98  {
99  public:
100  ElemType d;
101  int n;
102  };
103 
107  template<typename ElemType>
108  static bool structComp(const sortStruct<ElemType>& s1,
109  const sortStruct<ElemType>& s2)
110  {
111  return s1.d < s2.d;
112  }
113 
117  static void InsertNodeIntoTree(TreeType* destTree, TreeType* srcNode);
118 
119  public:
125  const SplitHistoryStruct& SplitHistory() const { return splitHistory; }
128 
132  template<typename Archive>
133  void Serialize(Archive& ar, const unsigned int /* version */);
134 };
135 
136 } // namespace tree
137 } // namespace mlpack
138 
139 // Include implementation
140 #include "x_tree_split_impl.hpp"
141 
142 #endif
static void InsertNodeIntoTree(TreeType *destTree, TreeType *srcNode)
Insert a node into another node.
The X tree requires that the tree records it&#39;s "split history".
Linear algebra utility functions, generally performed on matrices or vectors.
FirstShim< T > CreateNVP(T &t, const std::string &name, typename boost::enable_if< HasSerialize< T >>::type *=0)
Call this function to produce a name-value pair; this is similar to BOOST_SERIALIZATION_NVP(), but should be used for types that have a Serialize() function (or contain a type that has a Serialize() function) instead of a serialize() function.
size_t normalNodeMaxNumChildren
The max number of child nodes a non-leaf normal node can have.
void Serialize(Archive &ar, const unsigned int)
static bool structComp(const sortStruct< ElemType > &s1, const sortStruct< ElemType > &s2)
Comparator for sorting with sortStruct.
Class to allow for faster sorting.
size_t & NormalNodeMaxNumChildren()
Modify the maximum number of a normal node&#39;s children.
const SplitHistoryStruct & SplitHistory() const
Return the split history of the node assosiated with this object.
void SplitLeafNode(TreeType *tree, std::vector< bool > &relevels)
Split a leaf node using the algorithm described in "The R*-tree: An Efficient and Robust Access metho...
SplitHistoryStruct splitHistory
A struct to store the "split history" for X trees.
Include all of the base components required to write mlpack methods, and the main mlpack Doxygen docu...
XTreeSplit()
Default constructor.
SplitHistoryStruct & SplitHistory()
Modify the split history of the node assosiated with this object.
size_t NormalNodeMaxNumChildren() const
Return the maximum number of a normal node&#39;s children.
bool SplitNonLeafNode(TreeType *tree, std::vector< bool > &relevels)
Split a non-leaf node using the "default" algorithm.
A Rectangle Tree has new points inserted at the bottom.
const double MAX_OVERLAP
The X-tree paper says that a maximum allowable overlap of 20% works well.