mlpack: src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp Source File
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.
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.
const SplitHistoryStruct & SplitHistory() const
Return the split history of the node assosiated with this object.
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.
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.
size_t NormalNodeMaxNumChildren() const
Return the maximum number of a normal node&#39;s children.
const double MAX_OVERLAP
The X-tree paper says that a maximum allowable overlap of 20% works well.