[mlpack-git] master, mlpack-1.0.x: Clean up some namespacing, and add a test for sparse AllkNN using kd-trees. Also add one for cover trees, although it does not work yet. (3e5a9f6)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

>---------------------------------------------------------------

commit 3e5a9f6f11214e5a8fd3425bd12ef8a5b803c7c9
Author: Ryan Curtin <ryan at ratml.org>
Date:   Thu Feb 20 00:31:40 2014 +0000

    Clean up some namespacing, and add a test for sparse AllkNN using kd-trees.
    Also add one for cover trees, although it does not work yet.


>---------------------------------------------------------------

3e5a9f6f11214e5a8fd3425bd12ef8a5b803c7c9
 src/mlpack/tests/allknn_test.cpp | 106 ++++++++++++++++++++++++++++++++++-----
 1 file changed, 94 insertions(+), 12 deletions(-)

diff --git a/src/mlpack/tests/allknn_test.cpp b/src/mlpack/tests/allknn_test.cpp
index b3ad224..126038e 100644
--- a/src/mlpack/tests/allknn_test.cpp
+++ b/src/mlpack/tests/allknn_test.cpp
@@ -7,11 +7,15 @@
 #include <mlpack/methods/neighbor_search/neighbor_search.hpp>
 #include <mlpack/methods/neighbor_search/unmap.hpp>
 #include <mlpack/core/tree/cover_tree.hpp>
+#include <mlpack/core/tree/example_tree.hpp>
 #include <boost/test/unit_test.hpp>
 #include "old_boost_test_definitions.hpp"
 
 using namespace mlpack;
 using namespace mlpack::neighbor;
+using namespace mlpack::tree;
+using namespace mlpack::metric;
+using namespace mlpack::bound;
 
 BOOST_AUTO_TEST_SUITE(AllkNNTest);
 
@@ -586,14 +590,12 @@ BOOST_AUTO_TEST_CASE(SingleCoverTreeTest)
 
   arma::mat naiveQuery(data); // For naive AllkNN.
 
-  tree::CoverTree<metric::LMetric<2>, tree::FirstPointIsRoot,
-      NeighborSearchStat<NearestNeighborSort> > tree = tree::CoverTree<
-      metric::LMetric<2>, tree::FirstPointIsRoot,
-      NeighborSearchStat<NearestNeighborSort> >(data);
+  CoverTree<LMetric<2>, FirstPointIsRoot,
+      NeighborSearchStat<NearestNeighborSort> > tree = CoverTree<LMetric<2>,
+      FirstPointIsRoot, NeighborSearchStat<NearestNeighborSort> >(data);
 
-  NeighborSearch<NearestNeighborSort, metric::LMetric<2>,
-      tree::CoverTree<metric::LMetric<2>, tree::FirstPointIsRoot,
-          NeighborSearchStat<NearestNeighborSort> > >
+  NeighborSearch<NearestNeighborSort, LMetric<2>, CoverTree<LMetric<2>,
+      FirstPointIsRoot, NeighborSearchStat<NearestNeighborSort> > >
       coverTreeSearch(&tree, data, true);
 
   AllkNN naive(naiveQuery, true);
@@ -630,13 +632,13 @@ BOOST_AUTO_TEST_CASE(DualCoverTreeTest)
   arma::mat kdDistances;
   tree.Search(5, kdNeighbors, kdDistances);
 
-  tree::CoverTree<metric::LMetric<2, true>, tree::FirstPointIsRoot,
-      NeighborSearchStat<NearestNeighborSort> > referenceTree = tree::CoverTree<
-      metric::LMetric<2, true>, tree::FirstPointIsRoot,
+  CoverTree<LMetric<2, true>, FirstPointIsRoot,
+      NeighborSearchStat<NearestNeighborSort> > referenceTree = CoverTree<
+      LMetric<2, true>, FirstPointIsRoot,
       NeighborSearchStat<NearestNeighborSort> >(dataset);
 
-  NeighborSearch<NearestNeighborSort, metric::LMetric<2, true>,
-      tree::CoverTree<metric::LMetric<2, true>, tree::FirstPointIsRoot,
+  NeighborSearch<NearestNeighborSort, LMetric<2, true>,
+      CoverTree<LMetric<2, true>, FirstPointIsRoot,
       NeighborSearchStat<NearestNeighborSort> > >
       coverTreeSearch(&referenceTree, dataset);
 
@@ -651,4 +653,84 @@ BOOST_AUTO_TEST_CASE(DualCoverTreeTest)
   }
 }
 
+// Make sure sparse nearest neighbors works with kd trees.
+BOOST_AUTO_TEST_CASE(SparseAllkNNKDTreeTest)
+{
+  typedef BinarySpaceTree<HRectBound<2>,
+      NeighborSearchStat<NearestNeighborSort>, arma::sp_mat> SparseKDTree;
+
+  // The dimensionality of these datasets must be high so that the probability
+  // of a completely empty point is very low.  In this case, with dimensionality
+  // 70, the probability of all 70 dimensions being zero is 0.8^70 = 1.65e-7 in
+  // the reference set and 0.9^70 = 6.27e-4 in the query set.
+  arma::sp_mat queryDataset;
+  queryDataset.sprandu(50, 5000, 0.2);
+  arma::sp_mat referenceDataset;
+  referenceDataset.sprandu(50, 8000, 0.1);
+  arma::mat denseQuery(queryDataset);
+  arma::mat denseReference(referenceDataset);
+
+  typedef NeighborSearch<NearestNeighborSort, EuclideanDistance, SparseKDTree>
+      SparseAllkNN;
+
+  SparseAllkNN a(queryDataset, referenceDataset);
+  AllkNN naive(denseQuery, denseReference, true);
+
+  arma::mat sparseDistances;
+  arma::Mat<size_t> sparseNeighbors;
+  a.Search(10, sparseNeighbors, sparseDistances);
+
+  arma::mat naiveDistances;
+  arma::Mat<size_t> naiveNeighbors;
+  naive.Search(10, naiveNeighbors, naiveDistances);
+
+  for (size_t i = 0; i < naiveNeighbors.n_cols; ++i)
+  {
+    for (size_t j = 0; j < naiveNeighbors.n_rows; ++j)
+    {
+      BOOST_REQUIRE_EQUAL(naiveNeighbors(j, i), sparseNeighbors(j, i));
+      BOOST_REQUIRE_CLOSE(naiveDistances(j, i), sparseDistances(j, i), 1e-5);
+    }
+  }
+}
+
+/*
+BOOST_AUTO_TEST_CASE(SparseAllkNNCoverTreeTest)
+{
+  typedef CoverTree<LMetric<2, true>, FirstPointIsRoot,
+      NeighborSearchStat<NearestNeighborSort>, arma::sp_mat> SparseCoverTree;
+
+  // The dimensionality of these datasets must be high so that the probability
+  // of a completely empty point is very low.  In this case, with dimensionality
+  // 70, the probability of all 70 dimensions being zero is 0.8^70 = 1.65e-7 in
+  // the reference set and 0.9^70 = 6.27e-4 in the query set.
+  arma::sp_mat queryDataset;
+  queryDataset.sprandu(50, 5000, 0.2);
+  arma::sp_mat referenceDataset;
+  referenceDataset.sprandu(50, 8000, 0.1);
+  arma::mat denseQuery(queryDataset);
+  arma::mat denseReference(referenceDataset);
+
+  typedef NeighborSearch<NearestNeighborSort, EuclideanDistance,
+      SparseCoverTree> SparseAllkNN;
+
+  arma::mat sparseDistances;
+  arma::Mat<size_t> sparseNeighbors;
+  a.Search(10, sparseNeighbors, sparseDistances);
+
+  arma::mat naiveDistances;
+  arma::Mat<size_t> naiveNeighbors;
+  naive.Search(10, naiveNeighbors, naiveDistances);
+
+  for (size_t i = 0; i < naiveNeighbors.n_cols; ++i)
+  {
+    for (size_t j = 0; j < naiveNeighbors.n_rows; ++j)
+    {
+      BOOST_REQUIRE_EQUAL(naiveNeighbors(j, i), sparseNeighbors(j, i));
+      BOOST_REQUIRE_CLOSE(naiveDistances(j, i), sparseDistances(j, i), 1e-5);
+    }
+  }
+}
+*/
+
 BOOST_AUTO_TEST_SUITE_END();