[mlpack-git] master: Added some tests for DiscreteHilbertValue. Fixed errors in the Hilbert value calculation. (2f4a56b)
gitdub at mlpack.org
gitdub at mlpack.org
Thu Jun 16 14:55:03 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/37fda23945b4f998cd5fa6ec011ae345236c8552...479eca0c625cc4255a3b1a354a4788dae10f1b01
>---------------------------------------------------------------
commit 2f4a56b2d7fac7e78c38ee53ddaaa8bbe90abbf6
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date: Thu Jun 16 21:55:03 2016 +0300
Added some tests for DiscreteHilbertValue.
Fixed errors in the Hilbert value calculation.
>---------------------------------------------------------------
2f4a56b2d7fac7e78c38ee53ddaaa8bbe90abbf6
.../tree/rectangle_tree/discrete_hilbert_value.hpp | 35 +++----
.../rectangle_tree/discrete_hilbert_value_impl.hpp | 17 +++-
src/mlpack/tests/rectangle_tree_test.cpp | 113 +++++++++++++++++++++
3 files changed, 146 insertions(+), 19 deletions(-)
diff --git a/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp b/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp
index 6d85211..ab7f8a0 100644
--- a/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp
@@ -155,6 +155,24 @@ class DiscreteHilbertValue
void UpdateHilbertValues(TreeType* parent, size_t firstSibling,
size_t lastSibling);
+ /**
+ * Calculate the Hilbert value of the point pt.
+ * @param pt The point for which the Hilbert value should be calculated.
+ */
+ template<typename VecType>
+ static arma::Col<HilbertElemType> CalculateValue(const VecType& pt,
+ typename boost::enable_if<IsVector<VecType>>* = 0);
+
+ /**
+ * Compare two Hilbert values. It returns 1 if the first value is greater than
+ * the second one, -1 if the first value is less than the second one and
+ * 0 if the values are equal. This method does not compute the Hilbert values.
+ * @param value1 The first value.
+ * @param value2 The second value.
+ */
+ static int CompareValues(const arma::Col<HilbertElemType>& value1,
+ const arma::Col<HilbertElemType>& value2);
+
//! Return the number of values
size_t NumValues() const
{ return numValues; }
@@ -192,23 +210,6 @@ class DiscreteHilbertValue
bool ownsValueToInsert;
/**
- * Calculate the Hilbert value of the point pt.
- * @param pt The point for which the Hilbert value should be calculated.
- */
- template<typename VecType>
- static arma::Col<HilbertElemType> CalculateValue(const VecType& pt,
- typename boost::enable_if<IsVector<VecType>>* = 0);
-
- /**
- * Compare two Hilbert values. It returns 1 if the first value is greater than
- * the second one, -1 if the first value is less than the second one and
- * 0 if the values are equal. This method does not compute the Hilbert values.
- * @param value1 The first value.
- * @param value2 The second value.
- */
- static int CompareValues(const arma::Col<HilbertElemType>& value1,
- const arma::Col<HilbertElemType>& value2);
- /**
* Returns true if the node has the largest Hilbert value.
*/
bool HasValue() const;
diff --git a/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp b/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp
index 358f7b0..a9b4783 100644
--- a/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp
@@ -95,6 +95,9 @@ CalculateValue(const VecType& pt,typename boost::enable_if<IsVector<VecType>>*)
VecElemType normalizedVal = std::frexp(pt(i),&e);
bool sgn = std::signbit(normalizedVal);
+ if (pt(i) == 0)
+ e = std::numeric_limits<VecElemType>::min_exponent;
+
if (sgn)
normalizedVal = -normalizedVal;
@@ -104,17 +107,27 @@ CalculateValue(const VecType& pt,typename boost::enable_if<IsVector<VecType>>*)
e = std::numeric_limits<VecElemType>::min_exponent;
normalizedVal /= tmp;
}
+
// Extract the mantissa
HilbertElemType tmp = (HilbertElemType)1 << numMantBits;
- res(i) = std::floor(normalizedVal / tmp);
+ res(i) = std::floor(normalizedVal * tmp);
+
// Add the exponent
+ assert(res(i) < ((HilbertElemType)1 << numMantBits));
res(i) |= ((HilbertElemType)(e - std::numeric_limits<VecElemType>::min_exponent)) << numMantBits;
+ assert(res(i) < ((HilbertElemType)1 << (order - 1)) - 1);
// Negative values should be inverted
if (sgn)
+ {
res(i) = ((HilbertElemType)1 << (order - 1)) - 1 - res(i);
+ assert((res(i) >> (order - 1)) == 0);
+ }
else
+ {
res(i) |= (HilbertElemType)1 << (order - 1);
+ assert((res(i) >> (order - 1)) == 1);
+ }
}
HilbertElemType M = (HilbertElemType)1 << (order - 1);
@@ -161,7 +174,7 @@ CalculateValue(const VecType& pt,typename boost::enable_if<IsVector<VecType>>*)
size_t bit = (i * pt.n_rows + j) % order;
size_t row = (i * pt.n_rows + j) / order;
- rearrangedResult(row) |= (res(j) & (1 << i)) >> (i - bit);
+ rearrangedResult(row) |= (((res(j) >> (order - 1 - i)) & 1) << (order - 1 - bit));
}
return rearrangedResult;
diff --git a/src/mlpack/tests/rectangle_tree_test.cpp b/src/mlpack/tests/rectangle_tree_test.cpp
index 2af8ec3..ec85aeb 100644
--- a/src/mlpack/tests/rectangle_tree_test.cpp
+++ b/src/mlpack/tests/rectangle_tree_test.cpp
@@ -703,6 +703,44 @@ BOOST_AUTO_TEST_CASE(DiscreteHilbertOrderingTest)
CheckHilbertOrdering(&hilbertRTree);
}
+template<typename TreeType>
+void CheckDiscreteHilbertValueSync(const TreeType* tree)
+{
+ typedef DiscreteHilbertValue<typename TreeType::ElemType>
+ HilbertValue;
+ typedef typename HilbertValue::HilbertElemType HilbertElemType;
+
+ if (tree->IsLeaf())
+ {
+ const HilbertValue &value = tree->AuxiliaryInfo().HilbertValue();
+
+ for (size_t i = 0; i < tree->NumPoints(); i++)
+ {
+ arma::Col<HilbertElemType> pointValue =
+ HilbertValue::CalculateValue(tree->Dataset().col(tree->Points()[i]));
+
+ int equal = HilbertValue::CompareValues(value.LocalDataset()->col(i), pointValue);
+
+ BOOST_REQUIRE_EQUAL(equal, 0);
+ }
+ }
+ else
+ for (size_t i = 0; i < tree->NumChildren(); i++)
+ CheckDiscreteHilbertValueSync(tree->Children()[i]);
+}
+
+BOOST_AUTO_TEST_CASE(DiscreteHilbertValueSyncTest)
+{
+ arma::mat dataset;
+ dataset.randu(8, 1000); // 1000 points in 8 dimensions.
+
+ typedef DiscreteHilbertRTree<EuclideanDistance,
+ NeighborSearchStat<NearestNeighborSort>,arma::mat> TreeType;
+ TreeType hilbertRTree(dataset, 20, 6, 5, 2, 0);
+
+ CheckDiscreteHilbertValueSync(&hilbertRTree);
+}
+
/*
BOOST_AUTO_TEST_CASE(RecursiveHilbertOrderingTest)
{
@@ -719,6 +757,54 @@ BOOST_AUTO_TEST_CASE(RecursiveHilbertOrderingTest)
BOOST_AUTO_TEST_CASE(DiscreteHilbertValueTest)
{
+ arma::vec point01(1);
+ arma::vec point02(1);
+
+ point01[0] = -DBL_MAX;
+ point02[0] = DBL_MAX;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = -DBL_MAX;
+ point02[0] = -100;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = -100;
+ point02[0] = -1;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = -1;
+ point02[0] = -std::numeric_limits<double>::min();
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = -std::numeric_limits<double>::min();
+ point02[0] = 0;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = 0;
+ point02[0] = std::numeric_limits<double>::min();
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = std::numeric_limits<double>::min();
+ point02[0] = 1;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = 1;
+ point02[0] = 100;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
+ point01[0] = 100;
+ point02[0] = DBL_MAX;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point01,point02), -1);
+
arma::vec point1(2);
arma::vec point2(2);
@@ -761,6 +847,33 @@ BOOST_AUTO_TEST_CASE(DiscreteHilbertValueTest)
point2[1] = DBL_MAX * 0.25;
BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point1,point2), 1);
+
+ arma::vec point3(4);
+ arma::vec point4(4);
+
+ point3[0] = -DBL_MAX;
+ point3[1] = -DBL_MAX;
+ point3[2] = -DBL_MAX;
+ point3[3] = -DBL_MAX;
+
+ point4[0] = 1.0;
+ point4[1] = 1.0;
+ point4[2] = 1.0;
+ point4[3] = 1.0;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point3,point4), -1);
+
+ point3[0] = -DBL_MAX;
+ point3[1] = DBL_MAX;
+ point3[2] = DBL_MAX;
+ point3[3] = DBL_MAX;
+
+ point4[0] = DBL_MAX;
+ point4[1] = DBL_MAX;
+ point4[2] = DBL_MAX;
+ point4[3] = DBL_MAX;
+
+ BOOST_REQUIRE_EQUAL(DiscreteHilbertValue<double>::ComparePoints(point3,point4), -1);
}
// Test the tree splitting. We set MaxLeafSize and MaxNumChildren rather low
More information about the mlpack-git
mailing list