[mlpack-svn] r16973 - in mlpack/trunk/src/mlpack: core/tree/rectangle_tree tests
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Tue Aug 5 12:50:53 EDT 2014
Author: andrewmw94
Date: Tue Aug 5 12:50:52 2014
New Revision: 16973
Log:
Point deletion bug fix.
Modified:
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
mlpack/trunk/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp
Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp Tue Aug 5 12:50:52 2014
@@ -88,6 +88,7 @@
// }
return;
}
+
int bestOverlapIndexOnBestAxis = 0;
int bestAreaIndexOnBestAxis = 0;
@@ -261,6 +262,7 @@
return true;
}
+
// If we haven't yet reinserted on this level, we try doing so now.
if(relevels[tree->TreeDepth()]) {
relevels[tree->TreeDepth()] = false;
@@ -319,6 +321,7 @@
return false;
}
+
int bestOverlapIndexOnBestAxis = 0;
int bestAreaIndexOnBestAxis = 0;
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 Tue Aug 5 12:50:52 2014
@@ -523,16 +523,23 @@
{
// First delete the node if we need to. There's no point in shrinking the bound first.
if (IsLeaf() && count < minLeafSize && parent != NULL) { //We can't delete the root node
- for (size_t i = 0; i < parent->NumChildren(); i++) {
+
+for (size_t i = 0; i < parent->NumChildren(); i++) {
if (parent->Children()[i] == this) {
parent->Children()[i] = parent->Children()[--parent->NumChildren()]; // decrement numChildren
- parent->ShrinkBoundForBound(bound); // We want to do this before reinserting points.
-
- // Reinsert the points at the root node.
+
+ // We find the root and shrink bounds at the same time.
+ bool stillShrinking = true;
RectangleTree<SplitType, DescentType, StatisticType, MatType>* root = parent;
- while (root->Parent() != NULL)
+ while (root->Parent() != NULL) {
+ if(stillShrinking)
+ stillShrinking = root->ShrinkBoundForBound(bound);
root = root->Parent();
+ }
+ if(stillShrinking)
+ stillShrinking = root->ShrinkBoundForBound(bound);
+ // Reinsert the points at the root node.
for (size_t j = 0; j < count; j++) {
root->InsertPoint(points[j], relevels);
}
@@ -546,19 +553,25 @@
// Control should never reach here.
assert(true == false);
} else if (!IsLeaf() && numChildren < minNumChildren) {
-
if (parent != NULL) { // The normal case. We need to be careful with the root.
for (size_t j = 0; j < parent->NumChildren(); j++) {
if (parent->Children()[j] == this) {
parent->Children()[j] = parent->Children()[--parent->NumChildren()]; // decrement numChildren
- parent->ShrinkBoundForBound(bound); // We want to do this before reinserting nodes.
-
size_t level = TreeDepth();
- // Reinsert the nodes at the root node.
- RectangleTree<SplitType, DescentType, StatisticType, MatType>* root = this;
- while (root->Parent() != NULL)
+
+ // We find the root and shrink bounds at the same time.
+ bool stillShrinking = true;
+ RectangleTree<SplitType, DescentType, StatisticType, MatType>* root = parent;
+ while (root->Parent() != NULL) {
+ if(stillShrinking)
+ stillShrinking = root->ShrinkBoundForBound(bound);
root = root->Parent();
- for (size_t i = 0; i < numChildren; i++)
+ }
+ if(stillShrinking)
+ stillShrinking = root->ShrinkBoundForBound(bound);
+
+ // Reinsert the nodes at the root node.
+ for (size_t i = 0; i < numChildren; i++)
root->InsertNode(children[i], level, relevels);
parent->CondenseTree(point, relevels, usePoint); // This will check the MinFill of the parent.
@@ -579,6 +592,7 @@
}
count = child->Count();
child->SoftDelete();
+ return;
}
}
@@ -629,20 +643,23 @@
}
}
} else {
- for (size_t i = 0; i < point.n_elem; i++) {
+ for (size_t i = 0; i < bound.Dim(); i++) {
if (bound[i].Lo() == point[i]) {
double min = DBL_MAX;
- double max = -1 * DBL_MAX;
for (size_t j = 0; j < numChildren; j++) {
if (children[j]->Bound()[i].Lo() < min)
min = children[j]->Bound()[i].Lo();
- if (children[j]->Bound()[i].Hi() > max)
- max = children[j]->Bound()[i].Hi();
}
if (bound[i].Lo() < min) {
shrunk = true;
bound[i].Lo() = min;
}
+ } else if(bound[i].Hi() == point[i]) {
+ double max = -1 * DBL_MAX;
+ for (size_t j = 0; j < numChildren; j++) {
+ if (children[j]->Bound()[i].Hi() > max)
+ max = children[j]->Bound()[i].Hi();
+ }
if (bound[i].Hi() > max) {
shrunk = true;
bound[i].Hi() = max;
Modified: mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp (original)
+++ mlpack/trunk/src/mlpack/tests/rectangle_tree_test.cpp Tue Aug 5 12:50:52 2014
@@ -143,6 +143,87 @@
return;
}
+/**
+ * A function to check that containment is as tight as possible.
+ */
+void checkExactContainment(const RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RTreeDescentHeuristic,
+ NeighborSearchStat<NearestNeighborSort>,
+ arma::mat>& tree) {
+ if(tree.NumChildren() == 0) {
+ for(size_t i = 0; i < tree.Bound().Dim(); i++) {
+ double min = DBL_MAX;
+ double max = -1.0 * DBL_MAX;
+ for(size_t j = 0; j < tree.Count(); j++) {
+ if(tree.LocalDataset().col(j)[i] < min)
+ min = tree.LocalDataset().col(j)[i];
+ if(tree.LocalDataset().col(j)[i] > max)
+ max = tree.LocalDataset().col(j)[i];
+ }
+ BOOST_REQUIRE_EQUAL(max, tree.Bound()[i].Hi());
+ BOOST_REQUIRE_EQUAL(min, tree.Bound()[i].Lo());
+ }
+ } else {
+ for(size_t i = 0; i < tree.Bound().Dim(); i++) {
+ double min = DBL_MAX;
+ double max = -1.0 * DBL_MAX;
+ for(size_t j = 0; j < tree.NumChildren(); j++) {
+ if(tree.Child(j).Bound()[i].Lo() < min)
+ min = tree.Child(j).Bound()[i].Lo();
+ if(tree.Child(j).Bound()[i].Hi() > max)
+ max = tree.Child(j).Bound()[i].Hi();
+ }
+
+ if(max != tree.Bound()[i].Hi())
+ std::cout<<"error max"<<std::endl<<std::endl<<std::endl<<tree.ToString()<<std::endl<<std::endl;
+ if(min != tree.Bound()[i].Lo())
+ std::cout<<"error min"<<std::endl;
+ BOOST_REQUIRE_EQUAL(max, tree.Bound()[i].Hi());
+ BOOST_REQUIRE_EQUAL(min, tree.Bound()[i].Lo());
+ }
+ for(size_t i = 0; i < tree.NumChildren(); i++)
+ checkExactContainment(tree.Child(i));
+ }
+}
+
+/**
+ * A function to check that containment is as tight as possible.
+ */
+void checkExactContainment(const RectangleTree<tree::RStarTreeSplit<tree::RStarTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
+ tree::RStarTreeDescentHeuristic,
+ NeighborSearchStat<NearestNeighborSort>,
+ arma::mat>& tree) {
+ if(tree.NumChildren() == 0) {
+ for(size_t i = 0; i < tree.Bound().Dim(); i++) {
+ double min = DBL_MAX;
+ double max = -1.0 * DBL_MAX;
+ for(size_t j = 0; j < tree.Count(); j++) {
+ if(tree.LocalDataset().col(j)[i] < min)
+ min = tree.LocalDataset().col(j)[i];
+ if(tree.LocalDataset().col(j)[i] > max)
+ max = tree.LocalDataset().col(j)[i];
+ }
+ BOOST_REQUIRE_EQUAL(max, tree.Bound()[i].Hi());
+ BOOST_REQUIRE_EQUAL(min, tree.Bound()[i].Lo());
+ }
+ } else {
+ for(size_t i = 0; i < tree.Bound().Dim(); i++) {
+ double min = DBL_MAX;
+ double max = -1.0 * DBL_MAX;
+ for(size_t j = 0; j < tree.NumChildren(); j++) {
+ if(tree.Child(j).Bound()[i].Lo() < min)
+ min = tree.Child(j).Bound()[i].Lo();
+ if(tree.Child(j).Bound()[i].Hi() > max)
+ max = tree.Child(j).Bound()[i].Hi();
+ }
+ BOOST_REQUIRE_EQUAL(max, tree.Bound()[i].Hi());
+ BOOST_REQUIRE_EQUAL(min, tree.Bound()[i].Lo());
+ }
+ for(size_t i = 0; i < tree.NumChildren(); i++)
+ checkExactContainment(tree.Child(i));
+ }
+}
+
// Test to see if the bounds of the tree are correct. (Cover all bounds and points
// beneath this node of the tree).
BOOST_AUTO_TEST_CASE(RectangleTreeContainmentTest) {
@@ -154,6 +235,7 @@
NeighborSearchStat<NearestNeighborSort>,
arma::mat> tree(dataset, 20, 6, 5, 2, 0);
checkContainment(tree);
+ checkExactContainment(tree);
}
/**
@@ -308,7 +390,7 @@
for (int i = 0; i < numIter; i++) {
tree.DeletePoint(999 - i);
- }
+ }
// Do a few sanity checks. Ensure each point is unique, the tree has the correct
// number of points, the tree has legal containment, and the tree's data is in sync.
@@ -330,6 +412,7 @@
BOOST_REQUIRE_EQUAL(tree.NumDescendants(), 1000 - numIter);
checkContainment(tree);
checkSync(tree);
+ checkExactContainment(tree);
mlpack::neighbor::NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
@@ -407,6 +490,7 @@
BOOST_REQUIRE_EQUAL(tree.NumDescendants(), 1000 + numIter);
checkContainment(tree);
checkSync(tree);
+ checkExactContainment(tree);
// Now we will compare the output of the R Tree vs the output of a naive search.
arma::Mat<size_t> neighbors1;
@@ -510,7 +594,7 @@
BOOST_REQUIRE_EQUAL(RTree.NumDescendants(), 1000);
checkSync(RTree);
checkContainment(RTree);
-
+ checkExactContainment(RTree);
allknn1.Search(5, neighbors1, distances1);
More information about the mlpack-svn
mailing list