[mlpack-svn] r16694 - in mlpack/trunk/src/mlpack: core/tree/rectangle_tree methods/neighbor_search
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Mon Jun 23 14:49:02 EDT 2014
Author: andrewmw94
Date: Mon Jun 23 14:49:01 2014
New Revision: 16694
Log:
bug fixes
Modified:
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp Mon Jun 23 14:49:01 2014
@@ -15,6 +15,7 @@
inline double RTreeDescentHeuristic::EvalNode(const HRectBound<>& bound, const arma::vec& point)
{
+ std::cout << "eval node called" << std::endl;
return bound.Contains(point) ? 0 : bound.MinDistance(point);
}
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp Mon Jun 23 14:49:01 2014
@@ -25,31 +25,46 @@
void RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree)
{
- // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
- // Spatial Searching" It is simplified since we don't handle rectangles, only points.
- // It assumes that the tree uses Euclidean Distance.
- int i = 0;
- int j = 0;
- GetPointSeeds(*tree, &i, &j);
+
+ std::cout << "splitting a leaf node." << std::endl;
// If we are splitting the root node, we need will do things differently so that the constructor
// and other methods don't confuse the end user by giving an address of another node.
if(tree->Parent() == NULL) {
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> copy = *tree; // We actually want to copy this way. Pointers and everything.
+ std::cout << "copy made ." << std::endl;
+
copy.Parent() = tree;
tree->Count() = 0;
- tree->Children()[++(tree->NumChildren())] = © // Because this was a leaf node, numChildren must be 0.
+ tree->Children()[(tree->NumChildren())++] = © // Because this was a leaf node, numChildren must be 0.
+ RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(©);
+ std::cout << "finished split" << std::endl;
return;
}
+ // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
+ // Spatial Searching" It is simplified since we don't handle rectangles, only points.
+ // We assume that the tree uses Euclidean Distance.
+ int i = 0;
+ int j = 0;
+ GetPointSeeds(*tree, &i, &j);
+
+ std::cout << "point seeds found." << std::endl;
+
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeOne = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*(tree->Parent()));
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeTwo = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*(tree->Parent()));
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+ std::cout << "new trees made." << std::endl;
+
+
// This will assign the ith and jth point appropriately.
AssignPointDestNode(tree, treeOne, treeTwo, i, j);
+ std::cout << "assignments made." << std::endl;
+
+
//Remove this node and insert treeOne and treeTwo
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* par = tree->Parent();
int index = 0;
@@ -62,13 +77,17 @@
par->Children()[index] = treeOne;
par->Children()[par->NumChildren()++] = treeTwo;
+
+ std::cout << "points copied." << std::endl;
+
+
//because we copied the points to treeOne and treeTwo, we can just delete this node
- delete tree;
+ // I THINK?
+ //delete tree;
// we only add one at a time, so we should only need to test for equality
// just in case, we use an assert.
assert(par->NumChildren() <= par->MaxNumChildren());
-
if(par->NumChildren() == par->MaxNumChildren()) {
SplitNonLeafNode(par);
}
@@ -93,9 +112,9 @@
GetBoundSeeds(*tree, &i, &j);
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*(tree->Parent()));
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*(tree->Parent()));
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
// This will assign the ith and jth rectangles appropriately.
AssignNodeDestNode(tree, treeOne, treeTwo, i, j);
@@ -106,7 +125,8 @@
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> copy = *tree; // We actually want to copy this way. Pointers and everything.
copy.Parent() = tree;
tree->NumChildren() = 0;
- tree->Children()[++(tree->NumChildren())] = © // Because this was a leaf node, numChildren must be 0.
+ tree->Children()[(tree->NumChildren())++] = ©
+ RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(©);
return true;
}
@@ -218,15 +238,28 @@
const int intI,
const int intJ)
{
+
int end = oldTree->Count();
assert(end > 1); // If this isn't true, the tree is really weird.
+
+ // Restart the point counts since we are going to move them.
+ oldTree->Count() = 0;
+ treeOne->Count() = 0;
+ treeTwo->Count() = 0;
+
+ std::cout << " about to assign i and j" << std::endl;
+
treeOne->InsertPoint(oldTree->Dataset().col(intI));
+ std::cout << "assignment of i made." << std::endl;
+
oldTree->Dataset().col(intI) = oldTree->Dataset().col(--end); // decrement end
treeTwo->InsertPoint(oldTree->Dataset().col(intJ));
oldTree->Dataset().col(intJ) = oldTree->Dataset().col(--end); // decrement end
+ std::cout << "i and j assigned" << std::endl;
+
int numAssignedOne = 1;
int numAssignedTwo = 1;
@@ -237,7 +270,10 @@
// The below is safe because if end decreases and the right hand side of the second part of the conjunction changes
// on the same iteration, we added the point to the node with fewer points anyways.
- while(end > 1 && end < oldTree->MinLeafSize() - std::min(numAssignedOne, numAssignedTwo)) {
+ while(end > 0 && end > oldTree->MinLeafSize() - std::min(numAssignedOne, numAssignedTwo)) {
+
+ std::cout << "while loop entered with end = "<< end << std::endl;
+
int bestIndex = 0;
double bestScore = DBL_MAX;
int bestRect = 1;
@@ -283,16 +319,20 @@
// Assign the point that causes the least increase in volume
// to the appropriate rectangle.
- if(bestRect == 1)
+ if(bestRect == 1) {
treeOne->InsertPoint(oldTree->Dataset().col(bestIndex));
- else
+ numAssignedOne++;
+ }
+ else {
treeTwo->InsertPoint(oldTree->Dataset().col(bestIndex));
+ numAssignedTwo++;
+ }
oldTree->Dataset().col(bestIndex) = oldTree->Dataset().col(--end); // decrement end.
}
-
+
// See if we need to satisfy the minimum fill.
- if(end > 1) {
+ if(end > 0) {
if(numAssignedOne < numAssignedTwo) {
for(int i = 0; i < end; i++) {
treeOne->InsertPoint(oldTree->Dataset().col(i));
@@ -330,7 +370,7 @@
// In each iteration, we go through all of the nodes and find the one that causes the least
// increase of volume when added to one of the two new rectangles. We then add it to that
// rectangle.
- while(end > 1 && end < oldTree->MinNumChildren() - std::min(numAssignTreeOne, numAssignTreeTwo)) {
+ while(end > 0 && end > oldTree->MinNumChildren() - std::min(numAssignTreeOne, numAssignTreeTwo)) {
int bestIndex = 0;
double bestScore = DBL_MAX;
int bestRect = 0;
@@ -376,15 +416,19 @@
// Assign the rectangle that causes the least increase in volume
// to the appropriate rectangle.
- if(bestRect == 1)
+ if(bestRect == 1) {
insertNodeIntoTree(treeOne, oldTree->Children()[bestIndex]);
- else
+ numAssignTreeOne++;
+ }
+ else {
insertNodeIntoTree(treeTwo, oldTree->Children()[bestIndex]);
+ numAssignTreeTwo++;
+ }
oldTree->Children()[bestIndex] = oldTree->Children()[--end]; // Decrement end.
}
// See if we need to satisfy the minimum fill.
- if(end > 1) {
+ if(end > 0) {
if(numAssignTreeOne < numAssignTreeTwo) {
for(int i = 0; i < end; i++) {
insertNodeIntoTree(treeOne, oldTree->Children()[i]);
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp Mon Jun 23 14:49:01 2014
@@ -43,13 +43,20 @@
{
stat = StatisticType(*this);
+ std::cout << ToString() << std::endl;
+
+
// For now, just insert the points in order.
RectangleTree* root = this;
- for(int i = firstDataIndex; i < data.n_cols; i++) {
+ for(int i = firstDataIndex; i < 54 /*data.n_cols*/; i++) {
+ std::cout << "inserting point number: " << i << std::endl;
root->InsertPoint(data.col(i));
+ std::cout << "finished inserting point number: " << i << std::endl;
if(root->Parent() != NULL) {
root = root->Parent(); // OK since the level increases by at most one per iteration.
}
+ std::cout << "hi" << std::endl;
+ std::cout << ToString() << std::endl;
}
}
@@ -60,8 +67,8 @@
typename MatType>
RectangleTree<SplitType, DescentType, StatisticType, MatType>::RectangleTree(
RectangleTree<SplitType, DescentType, StatisticType, MatType>* parentNode):
- maxNumChildren(parentNode.MaxNumChildren()),
- minNumChildren(parentNode.MinNumChildren()),
+ maxNumChildren(parentNode->MaxNumChildren()),
+ minNumChildren(parentNode->MinNumChildren()),
numChildren(0),
children(maxNumChildren+1),
parent(parentNode),
@@ -71,7 +78,7 @@
minLeafSize(parentNode->MinLeafSize()),
bound(parentNode->Bound().Dim()),
parentDistance(0),
- dataset(new MatType(static_cast<int>(parentNode->Bound().Dim()), static_cast<int>((maxLeafSize)+1))) // Add one to make splitting the node simpler
+ dataset(new MatType(static_cast<int>(parentNode->Bound().Dim()), static_cast<int>(maxLeafSize)+1)) // Add one to make splitting the node simpler
{
stat = StatisticType(*this);
}
@@ -119,11 +126,14 @@
void RectangleTree<SplitType, DescentType, StatisticType, MatType>::
InsertPoint(const arma::vec& point)
{
+
+ std::cout << "insert point called" << std::endl;
// Expand the bound regardless of whether it is a leaf node.
bound |= point;
-
+
// If this is a leaf node, we stop here and add the point.
if(numChildren == 0) {
+ std::cout << "count = " << count << std::endl;
dataset->col(count++) = point;
SplitNode();
return;
@@ -133,6 +143,7 @@
// to which we recurse.
double minScore = DescentType::EvalNode(children[0]->Bound(), point);
int bestIndex = 0;
+
for(int i = 1; i < numChildren; i++) {
double score = DescentType::EvalNode(children[i]->Bound(), point);
if(score < minScore) {
@@ -317,9 +328,13 @@
if(count < maxLeafSize)
return; // We don't need to split.
+ std::cout << "we are actually splitting the node." << std::endl;
// If we are full, then we need to split (or at least try). The SplitType takes
// care of this and of moving up the tree if necessary.
- SplitType::SplitLeafNode(this);
+ SplitType::SplitLeafNode(this);
+ std::cout << "we finished actually splitting the node." << std::endl;
+
+ std::cout << ToString() << std::endl;
}
@@ -340,8 +355,12 @@
convert << " Bound: " << std::endl;
convert << mlpack::util::Indent(bound.ToString(), 2);
convert << " Statistic: " << std::endl;
- convert << mlpack::util::Indent(stat.ToString(), 2);
+ //convert << mlpack::util::Indent(stat.ToString(), 2);
convert << " Max leaf size: " << maxLeafSize << std::endl;
+ convert << " Min leaf size: " << minLeafSize << std::endl;
+ convert << " Max num of children: " << maxNumChildren << std::endl;
+ convert << " Min num of children: " << minNumChildren << std::endl;
+ convert << " Parent address: " << parent << std::endl;
// How many levels should we print? This will print the root and it's children.
if(parent == NULL) {
Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp (original)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/allknn_main.cpp Mon Jun 23 14:49:01 2014
@@ -278,7 +278,6 @@
arma::mat>
refTree(referenceData, leafSize, leafSize/3, 5, 2, 0);
Timer::Stop("tree_building");
-
}
}
else // Cover trees.
More information about the mlpack-svn
mailing list