[mlpack-git] master: New stub method for (hopefully) good Elkan prune. This allows us to prune without even needing to recurse. (9515f01)

gitdub at big.cc.gt.atl.ga.us gitdub at big.cc.gt.atl.ga.us
Thu Mar 12 16:02:06 EDT 2015


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

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/eddd7167d69b6c88b271ef2e51d1c20e13f1acd8...70342dd8e5c17e0c164cfb8189748671e9c0dd44

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

commit 9515f01939b97c7cdc31b35c250d2416184f3573
Author: Ryan Curtin <ryan at ratml.org>
Date:   Wed Jan 14 17:05:38 2015 -0500

    New stub method for (hopefully) good Elkan prune. This allows us to prune without even needing to recurse.


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

9515f01939b97c7cdc31b35c250d2416184f3573
 .../methods/kmeans/dual_tree_kmeans_rules.hpp      |  8 ++++++++
 .../methods/kmeans/dual_tree_kmeans_rules_impl.hpp | 22 ++++++++++++++++++++++
 2 files changed, 30 insertions(+)

diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules.hpp
index 2fedea0..896da5d 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules.hpp
@@ -72,6 +72,14 @@ class DualTreeKMeansRules
       potentialChild) const;
 
   /**
+   * See if an Elkan-type overall prune can be performed.  This means that the
+   * previous iteration owner _must_ be the owner during this iteration.
+   *
+   * This is not a function of the query node, so it does not need to be passed.
+   */
+  double ElkanOverallTypeScore(TreeType& queryNode);
+
+  /**
    * See if an Elkan-type prune can be performed.  If so, return DBL_MAX;
    * otherwise, return a score.  The Elkan-type prune can occur when the minimum
    * distance between the query node and the current best query node for the
diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
index 321de5d..df1b065 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
@@ -206,6 +206,28 @@ bool DualTreeKMeansRules<MetricType, TreeType>::IsDescendantOf(
 }
 
 template<typename MetricType, typename TreeType>
+double DualTreeKMeansRules<MetricType, TreeType>::ElkanOverallTypeScore(
+    TreeType& referenceNode)
+{
+  // Does the reference node have an owner?
+  if (referenceNode.Owner() < centroids.n_cols)
+  {
+    // Has the owner stayed stationary enough and no other centroids moved
+    // enough that this owner _must_ be the continued owner?
+    if (referenceNode.MaxQueryNodeDistance() +
+        clusterDistances[referenceNode.Owner()] <
+        referenceNode.SecondClosestQueryNodeDistance() -
+        clusterDistances[centroids.n_cols])
+    {
+      return DBL_MAX;
+      // Not yet handled: when to add this to the finished counts?
+    }
+  }
+
+  return 0.0;
+}
+
+template<typename MetricType, typename TreeType>
 double DualTreeKMeansRules<MetricType, TreeType>::ElkanTypeScore(
     TreeType& queryNode,
     TreeType& referenceNode)



More information about the mlpack-git mailing list