[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