mlpack  2.0.1
cosine_tree.hpp
Go to the documentation of this file.
1 
14 #ifndef __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
15 #define __MLPACK_CORE_TREE_COSINE_TREE_COSINE_TREE_HPP
16 
17 #include <mlpack/core.hpp>
18 #include <boost/heap/priority_queue.hpp>
19 
20 namespace mlpack {
21 namespace tree {
22 
23 // Predeclare classes for CosineNodeQueue typedef.
24 class CompareCosineNode;
25 class CosineTree;
26 
27 // CosineNodeQueue typedef.
28 typedef boost::heap::priority_queue<CosineTree*,
29  boost::heap::compare<CompareCosineNode> > CosineNodeQueue;
30 
31 class CosineTree
32 {
33  public:
42  CosineTree(const arma::mat& dataset);
43 
53  CosineTree(CosineTree& parentNode, const std::vector<size_t>& subIndices);
54 
69  CosineTree(const arma::mat& dataset,
70  const double epsilon,
71  const double delta);
72 
76  ~CosineTree();
77 
87  void ModifiedGramSchmidt(CosineNodeQueue& treeQueue,
88  arma::vec& centroid,
89  arma::vec& newBasisVector,
90  arma::vec* addBasisVector = NULL);
91 
104  double MonteCarloError(CosineTree* node,
105  CosineNodeQueue& treeQueue,
106  arma::vec* addBasisVector1 = NULL,
107  arma::vec* addBasisVector2 = NULL);
108 
114  void ConstructBasis(CosineNodeQueue& treeQueue);
115 
121  void CosineNodeSplit();
122 
129  void ColumnSamplesLS(std::vector<size_t>& sampledIndices,
130  arma::vec& probabilities, size_t numSamples);
131 
138  size_t ColumnSampleLS();
139 
152  size_t BinarySearch(arma::vec& cDistribution, double value, size_t start,
153  size_t end);
154 
162  void CalculateCosines(arma::vec& cosines);
163 
168  void CalculateCentroid();
169 
171  void GetFinalBasis(arma::mat& finalBasis) { finalBasis = basis; }
172 
174  const arma::mat& GetDataset() const { return dataset; }
175 
177  std::vector<size_t>& VectorIndices() { return indices; }
178 
180  void L2Error(const double error) { this->l2Error = error; }
182  double L2Error() const { return l2Error; }
183 
185  arma::vec& Centroid() { return centroid; }
186 
188  void BasisVector(arma::vec& bVector) { this->basisVector = bVector; }
189 
191  arma::vec& BasisVector() { return basisVector; }
192 
194  CosineTree* Parent() const { return parent; }
196  CosineTree*& Parent() { return parent; }
197 
199  CosineTree* Left() const { return left; }
201  CosineTree*& Left() { return left; }
202 
204  CosineTree* Right() const { return right; }
206  CosineTree*& Right() { return right; }
207 
209  size_t NumColumns() const { return numColumns; }
210 
212  double FrobNormSquared() const { return frobNormSquared; }
213 
215  size_t SplitPointIndex() const { return indices[splitPointIndex]; }
216 
217  private:
219  const arma::mat& dataset;
221  double delta;
223  arma::mat basis;
225  CosineTree* parent;
227  CosineTree* left;
229  CosineTree* right;
231  std::vector<size_t> indices;
233  arma::vec l2NormsSquared;
235  arma::vec centroid;
237  arma::vec basisVector;
241  size_t numColumns;
243  double l2Error;
246 };
247 
249 {
250  public:
251 
252  // Comparison function for construction of priority queue.
253  bool operator() (const CosineTree* a, const CosineTree* b) const
254  {
255  return a->L2Error() < b->L2Error();
256  }
257 };
258 
259 } // namespace tree
260 } // namespace mlpack
261 
262 #endif
void CalculateCosines(arma::vec &cosines)
Calculate cosines of the columns present in the node, with respect to the sampled splitting point...
CosineTree * left
Left child of the node.
double FrobNormSquared() const
Get the Frobenius norm squared of columns in the node.
std::vector< size_t > indices
Indices of columns of input matrix in the node.
Linear algebra utility functions, generally performed on matrices or vectors.
size_t SplitPointIndex() const
Get the column index of split point of the node.
size_t numColumns
Number of columns of input matrix in the node.
arma::vec l2NormsSquared
L2-norm squared of columns in the node.
void CosineNodeSplit()
This function splits the cosine node into two children based on the cosines of the columns contained ...
double MonteCarloError(CosineTree *node, CosineNodeQueue &treeQueue, arma::vec *addBasisVector1=NULL, arma::vec *addBasisVector2=NULL)
Estimates the squared error of the projection of the input node&#39;s matrix onto the current vector subs...
size_t splitPointIndex
Index of split point of cosine node.
void GetFinalBasis(arma::mat &finalBasis)
Returns the basis of the constructed subspace.
CosineTree * Right() const
Get pointer to the right child of the node.
CosineTree * Left() const
Get pointer to the left child of the node.
CosineTree *& Parent()
Modify the pointer to the parent node.
size_t ColumnSampleLS()
Sample a point from the Length-Squared distribution of the cosine node.
arma::vec centroid
Centroid of columns of input matrix in the node.
const arma::mat & dataset
Matrix for which cosine tree is constructed.
arma::vec & Centroid()
Get pointer to the centroid vector.
void ConstructBasis(CosineNodeQueue &treeQueue)
Constructs the final basis matrix, after the cosine tree construction.
~CosineTree()
Clean up the CosineTree: release allocated memory (including children).
CosineTree(const arma::mat &dataset)
CosineTree constructor for the root node of the tree.
void BasisVector(arma::vec &bVector)
Set the basis vector of the node.
size_t BinarySearch(arma::vec &cDistribution, double value, size_t start, size_t end)
Sample a column based on the cumulative Length-Squared distribution of the cosine node...
arma::vec & BasisVector()
Get the basis vector of the node.
void CalculateCentroid()
Calculate centroid of the columns present in the node.
size_t NumColumns() const
Get number of columns of input matrix in the node.
CosineTree * parent
Parent of the node.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
arma::vec basisVector
Orthonormalized basis vector of the node.
CosineTree * right
Right child of the node.
CosineTree *& Right()
Modify the pointer to the left child of the node.
const arma::mat & GetDataset() const
Get pointer to the dataset matrix.
void ModifiedGramSchmidt(CosineNodeQueue &treeQueue, arma::vec &centroid, arma::vec &newBasisVector, arma::vec *addBasisVector=NULL)
Calculates the orthonormalization of the passed centroid, with respect to the current vector subspace...
boost::heap::priority_queue< CosineTree *, boost::heap::compare< CompareCosineNode > > CosineNodeQueue
Definition: cosine_tree.hpp:25
double l2Error
Monte Carlo error for this node.
arma::mat basis
Subspace basis of the input dataset.
CosineTree *& Left()
Modify the pointer to the left child of the node.
double frobNormSquared
Frobenius norm squared of columns in the node.
void ColumnSamplesLS(std::vector< size_t > &sampledIndices, arma::vec &probabilities, size_t numSamples)
Sample &#39;numSamples&#39; points from the Length-Squared distribution of the cosine node.
void L2Error(const double error)
Set the Monte Carlo error.
double L2Error() const
Get the Monte Carlo error.
CosineTree * Parent() const
Get pointer to the parent node.
std::vector< size_t > & VectorIndices()
Get the indices of columns in the node.
double delta
Cumulative probability for Monte Carlo error lower bound.