[mlpack-git] master: implement Gradient() (7a9485b)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Wed Apr 29 14:43:26 EDT 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/ee384655c4462e422e343e9725437fd772ca4449...182d4a629c1b23f683dff7b284844e4e3e9f5cc4
>---------------------------------------------------------------
commit 7a9485bde3f365ef5cfeb6187beb6924c759b16c
Author: HurricaneTong <HurricaneTong at HurricaneTong.local>
Date: Sat Feb 14 22:14:37 2015 +0800
implement Gradient()
as well as GradientForSquaredDistance()
>---------------------------------------------------------------
7a9485bde3f365ef5cfeb6187beb6924c759b16c
src/mlpack/core/kernels/cosine_distance.hpp | 3 +
src/mlpack/core/kernels/epanechnikov_kernel.cpp | 33 ++++++++++
src/mlpack/core/kernels/epanechnikov_kernel.hpp | 15 +++++
src/mlpack/core/kernels/gaussian_kernel.hpp | 24 ++++++-
src/mlpack/core/kernels/kernel_traits.hpp | 5 ++
src/mlpack/core/kernels/laplacian_kernel.hpp | 15 +++++
src/mlpack/core/kernels/spherical_kernel.hpp | 5 ++
src/mlpack/core/kernels/triangular_kernel.hpp | 19 ++++++
src/mlpack/methods/mean_shift/mean_shift.hpp | 37 ++++++++++-
src/mlpack/methods/mean_shift/mean_shift_impl.hpp | 76 ++++++++++++++++-------
10 files changed, 208 insertions(+), 24 deletions(-)
diff --git a/src/mlpack/core/kernels/cosine_distance.hpp b/src/mlpack/core/kernels/cosine_distance.hpp
index 77c8142..2b79381 100644
--- a/src/mlpack/core/kernels/cosine_distance.hpp
+++ b/src/mlpack/core/kernels/cosine_distance.hpp
@@ -53,6 +53,9 @@ class KernelTraits<CosineDistance>
public:
//! The cosine kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+
+ //! The cosine kernel doesn't include a squared distance.
+ static const bool UsesSquaredDistance = false;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/epanechnikov_kernel.cpp b/src/mlpack/core/kernels/epanechnikov_kernel.cpp
index 83049f3..cc3bcef 100644
--- a/src/mlpack/core/kernels/epanechnikov_kernel.cpp
+++ b/src/mlpack/core/kernels/epanechnikov_kernel.cpp
@@ -31,6 +31,39 @@ double EpanechnikovKernel::Evaluate(const double distance) const
return std::max(0.0, 1 - std::pow(distance, 2.0) * inverseBandwidthSquared);
}
+/**
+ * Evaluate gradient of the kernel not for two points
+ * but for a numerical value.
+ */
+double EpanechnikovKernel::Gradient(const double distance) const {
+ if (std::abs(bandwidth) < std::abs(distance)) {
+ return 0;
+ } else if (std::abs(bandwidth > std::abs(distance))) {
+ return -2 * inverseBandwidthSquared * distance;
+ } else {
+ // The gradient doesn't exist.
+ return arma::datum::nan;
+ }
+}
+
+/**
+ * Evaluate gradient of the kernel not for two points
+ * but for a numerical value.
+ */
+double EpanechnikovKernel::GradientForSquaredDistance(const double
+ distanceSquared) const {
+ double bandwidthSquared = bandwidth * bandwidth;
+ if (distanceSquared < bandwidthSquared) {
+ return -1 * inverseBandwidthSquared;
+ } else if (distanceSquared > bandwidthSquared &&
+ distanceSquared >= 0) {
+ return 0;
+ } else {
+ // The gradient doesn't exist.
+ return arma::datum::nan;
+ }
+}
+
// Return string of object.
std::string EpanechnikovKernel::ToString() const
{
diff --git a/src/mlpack/core/kernels/epanechnikov_kernel.hpp b/src/mlpack/core/kernels/epanechnikov_kernel.hpp
index 4db40c6..29d3e5b 100644
--- a/src/mlpack/core/kernels/epanechnikov_kernel.hpp
+++ b/src/mlpack/core/kernels/epanechnikov_kernel.hpp
@@ -52,6 +52,19 @@ class EpanechnikovKernel
double Evaluate(const double distance) const;
/**
+ * Evaluate the Gradient of Epanechnikov kernel
+ * given that the distance between the two
+ * input points is known.
+ */
+ double Gradient(const double distance) const;
+
+ /**
+ * Evaluate the Gradient of Epanechnikov kernel
+ * given that the squared distance between the two
+ * input points is known.
+ */
+ double GradientForSquaredDistance(const double distanceSquared) const;
+ /**
* Obtains the convolution integral [integral of K(||x-a||) K(||b-x||) dx]
* for the two vectors.
*
@@ -88,6 +101,8 @@ class KernelTraits<EpanechnikovKernel>
public:
//! The Epanechnikov kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+ //! The Epanechnikov kernel includes a squared distance.
+ static const bool UsesSquaredDistance = true;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/gaussian_kernel.hpp b/src/mlpack/core/kernels/gaussian_kernel.hpp
index 22afb5e..3ba9ebf 100644
--- a/src/mlpack/core/kernels/gaussian_kernel.hpp
+++ b/src/mlpack/core/kernels/gaussian_kernel.hpp
@@ -75,8 +75,28 @@ class GaussianKernel
return exp(gamma * std::pow(t, 2.0));
}
+ /**
+ * Evaluation of the gradient of Gaussian kernel
+ * given the distance between two points.
+ *
+ * @param t The distance between the two points the kernel is evaluated on.
+ * @return K(t) using the bandwidth (@f$\mu at f$) specified in the
+ * constructor.
+ */
double Gradient(const double t) const {
- return gamma * exp(gamma * std::pow(t, 2.0));
+ return 2 * t * gamma * exp(gamma * std::pow(t, 2.0));
+ }
+
+ /**
+ * Evaluation of the gradient of Gaussian kernel
+ * given the squared distance between two points.
+ *
+ * @param t The squared distance between the two points
+ * @return K(t) using the bandwidth (@f$\mu at f$) specified in the
+ * constructor.
+ */
+ double GradientForSquaredDistance(const double t) const {
+ return gamma * exp(gamma * t);
}
/**
@@ -144,6 +164,8 @@ class KernelTraits<GaussianKernel>
public:
//! The Gaussian kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+ //! The Gaussian kernel includes a squared distance.
+ static const bool UsesSquaredDistance = true;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/kernel_traits.hpp b/src/mlpack/core/kernels/kernel_traits.hpp
index c7e7be3..d1e767c 100644
--- a/src/mlpack/core/kernels/kernel_traits.hpp
+++ b/src/mlpack/core/kernels/kernel_traits.hpp
@@ -26,6 +26,11 @@ class KernelTraits
* If true, then the kernel is normalized: K(x, x) = K(y, y) = 1 for all x.
*/
static const bool IsNormalized = false;
+
+ /**
+ * If true, then the kernel include a squared distance, ||x - y||^2 .
+ */
+ static const bool UsesSquaredDistance = false;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/laplacian_kernel.hpp b/src/mlpack/core/kernels/laplacian_kernel.hpp
index bb865ef..72f8cac 100644
--- a/src/mlpack/core/kernels/laplacian_kernel.hpp
+++ b/src/mlpack/core/kernels/laplacian_kernel.hpp
@@ -73,6 +73,19 @@ class LaplacianKernel
return exp(-t / bandwidth);
}
+ /**
+ * Evaluation of the gradient of the Laplacian kernel
+ * given the distance between two points.
+ *
+ * @param t The distance between the two points the kernel should be evaluated
+ * on.
+ * @return K(t) using the bandwidth (@f$\mu at f$) specified in the
+ * constructor.
+ */
+ double Gradient(const double t) const {
+ return exp(-t / bandwidth) / -bandwidth;
+ }
+
//! Get the bandwidth.
double Bandwidth() const { return bandwidth; }
//! Modify the bandwidth.
@@ -99,6 +112,8 @@ class KernelTraits<LaplacianKernel>
public:
//! The Laplacian kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+ //! The Laplacian kernel doesn't include a squared distance.
+ static const bool UsesSquaredDistance = false;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/spherical_kernel.hpp b/src/mlpack/core/kernels/spherical_kernel.hpp
index d8e04f8..a89e266 100644
--- a/src/mlpack/core/kernels/spherical_kernel.hpp
+++ b/src/mlpack/core/kernels/spherical_kernel.hpp
@@ -95,6 +95,9 @@ class SphericalKernel
{
return (t <= bandwidth) ? 1.0 : 0.0;
}
+ double Gradient(double t) {
+ return t == bandwidth ? arma::datum::nan : 0.0;
+ }
//! Return a string representation of the kernel.
std::string ToString() const
@@ -117,6 +120,8 @@ class KernelTraits<SphericalKernel>
public:
//! The spherical kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+ //! The spherical kernel doesn't include a squared distance.
+ static const bool UsesSquaredDistance = false;
};
}; // namespace kernel
diff --git a/src/mlpack/core/kernels/triangular_kernel.hpp b/src/mlpack/core/kernels/triangular_kernel.hpp
index 7b8020a..a28d823 100644
--- a/src/mlpack/core/kernels/triangular_kernel.hpp
+++ b/src/mlpack/core/kernels/triangular_kernel.hpp
@@ -58,6 +58,23 @@ class TriangularKernel
return std::max(0.0, (1 - distance) / bandwidth);
}
+ /**
+ * Evaluate the gradient of triangular kernel
+ * given that the distance between the two
+ * points is known.
+ *
+ * @param distance The distance between the two points.
+ */
+ double Gradient(const double distance) const {
+ if (distance < 1) {
+ return -1.0 / bandwidth;
+ } else if (distance > 1) {
+ return 0;
+ } else {
+ return arma::datum::nan;
+ }
+ }
+
//! Get the bandwidth of the kernel.
double Bandwidth() const { return bandwidth; }
//! Modify the bandwidth of the kernel.
@@ -84,6 +101,8 @@ class KernelTraits<TriangularKernel>
public:
//! The triangular kernel is normalized: K(x, x) = 1 for all x.
static const bool IsNormalized = true;
+ //! The triangular kernel doesn't include a squared distance.
+ static const bool UsesSquaredDistance = false;
};
}; // namespace kernel
diff --git a/src/mlpack/methods/mean_shift/mean_shift.hpp b/src/mlpack/methods/mean_shift/mean_shift.hpp
index c45a759..9463cc3 100644
--- a/src/mlpack/methods/mean_shift/mean_shift.hpp
+++ b/src/mlpack/methods/mean_shift/mean_shift.hpp
@@ -10,7 +10,9 @@
#include <mlpack/core.hpp>
#include <mlpack/core/kernels/gaussian_kernel.hpp>
+#include <mlpack/core/kernels/kernel_traits.hpp>
#include <mlpack/core/metrics/lmetric.hpp>
+#include <boost/utility.hpp>
namespace mlpack {
namespace meanshift /** Mean Shift clustering. */ {
@@ -58,13 +60,13 @@ class MeanShift
* Give an estimation of radius based on given dataset.
* @param data Dataset for estimation.
*/
- double estimateRadius(const MatType& data);
+ double EstimateRadius(const MatType& data);
/**
* Perform Mean Shift clustering on the data, returning a list of cluster
* assignments and centroids.
*
- * @tparam MatType Type of matrix (arma::mat or arma::sp_mat).
+ * @tparam MatType Type of matrix.
* @param data Dataset to cluster.
* @param assignments Vector to store cluster assignments in.
* @param centroids Matrix in which centroids are stored.
@@ -91,6 +93,34 @@ class MeanShift
private:
/**
+ * If the kernel doesn't include a squared distance,
+ * general way will be applied to calculate the weight of a data point.
+ *
+ * @param centroid The centroid to calculate the weight
+ * @param point Calculate its weight
+ * @param weight Store the weight
+ * @return If true, the @point is near enough to the @centroid and @weight is valid,
+ * If false, the @point is far from the @centroid and @weight is invalid.
+ */
+ template <typename Kernel = KernelType>
+ typename std::enable_if<!kernel::KernelTraits<Kernel>::UsesSquaredDistance, bool>::type
+ CalcWeight(const arma::colvec& centroid, const arma::colvec& point, double& weight);
+
+ /**
+ * If the kernel includes a squared distance,
+ * the weight of a data point can be calculated faster.
+ *
+ * @param centroid The centroid to calculate the weight
+ * @param point Calculate its weight
+ * @param weight Store the weight
+ * @return If true, the @point is near enough to the @centroid and @weight is valid,
+ * If false, the @point is far from the @centroid and @weight is invalid.
+ */
+ template <typename Kernel = KernelType>
+ typename std::enable_if<kernel::KernelTraits<Kernel>::UsesSquaredDistance, bool>::type
+ CalcWeight(const arma::colvec& centroid, const arma::colvec& point, double& weight);
+
+ /**
* If distance of two centroids is less than radius, one will be removed.
* Points with distance to current centroid less than radius will be used
* to calculate new centroid.
@@ -106,6 +136,9 @@ class MeanShift
//! Instantiated kernel.
KernelType kernel;
+ metric::EuclideanDistance metric;
+
+
};
}; // namespace meanshift
diff --git a/src/mlpack/methods/mean_shift/mean_shift_impl.hpp b/src/mlpack/methods/mean_shift/mean_shift_impl.hpp
index 86fb811..480252d 100644
--- a/src/mlpack/methods/mean_shift/mean_shift_impl.hpp
+++ b/src/mlpack/methods/mean_shift/mean_shift_impl.hpp
@@ -7,6 +7,7 @@
#include "mean_shift.hpp"
#include <mlpack/core/kernels/gaussian_kernel.hpp>
+#include <mlpack/core/kernels/kernel_traits.hpp>
#include <mlpack/core/metrics/lmetric.hpp>
#include <mlpack/methods/neighbor_search/neighbor_search.hpp>
#include <mlpack/methods/neighbor_search/neighbor_search_stat.hpp>
@@ -49,7 +50,7 @@ template<typename KernelType,
double MeanShift<
KernelType,
MatType>::
-estimateRadius(const MatType &data) {
+EstimateRadius(const MatType &data) {
neighbor::NeighborSearch<
neighbor::NearestNeighborSort,
@@ -71,11 +72,54 @@ estimateRadius(const MatType &data) {
// Get max distance for each point.
arma::rowvec maxDistances = max(distances);
- // Calc and return the duplicate thresh.
+ // Calculate and return the radius.
return sum(maxDistances) / (double)data.n_cols;
}
+// General way to calculate the weight of a data point.
+template <typename KernelType,
+ typename MatType>
+template <typename Kernel>
+typename std::enable_if<!kernel::KernelTraits<Kernel>::
+ UsesSquaredDistance, bool>::type
+MeanShift<
+ KernelType,
+ MatType>::
+CalcWeight(const arma::colvec& centroid, const arma::colvec& point,
+ double& weight) {
+
+ double distance = metric.Evaluate(centroid, point);
+ if (distance >= radius || distance == 0) {
+ return false;
+ }
+ distance /= radius;
+ weight = kernel.Gradient(distance) / distance;
+ return true;
+
+}
+
+// Faster way to calculate the weight of a data point.
+template <typename KernelType,
+ typename MatType>
+template <typename Kernel>
+typename std::enable_if<kernel::KernelTraits<Kernel>::
+ UsesSquaredDistance, bool>::type
+MeanShift<
+ KernelType,
+ MatType>::
+CalcWeight(const arma::colvec& centroid, const arma::colvec& point,
+ double& weight) {
+
+ double squaredDist = std::pow(metric.Evaluate(centroid, point), 2);
+ if (squaredDist >= squaredRadius || squaredDist == 0) {
+ return false;
+ }
+ squaredDist /= squaredRadius;
+ weight = kernel.GradientForSquaredDistance(squaredDist);
+ return true;
+}
+
/**
* Perform Mean Shift clustering on the data, returning a list of cluster
* assignments and centroids.
@@ -91,7 +135,7 @@ Cluster(const MatType& data,
if (radius <= 0) {
// An invalid radius is given, an estimation is needed.
- Radius(estimateRadius(data));
+ Radius(EstimateRadius(data));
}
// all centroids before remove duplicate ones.
@@ -115,21 +159,10 @@ Cluster(const MatType& data,
// Go through all the points
for (size_t j = 0; j < data.n_cols; ++j) {
- // Calculate the distance between old centroid and current point.
- double squaredDist = metric::SquaredEuclideanDistance::
- Evaluate(allCentroids.col(i), data.col(j));
-
- // If current point is near the old centroid
- if (squaredDist < squaredRadius) {
-
- // calculate weight for current point
- double weight = kernel.Gradient(squaredDist / squaredRadius);
-
+ double weight = 0;
+ if (CalcWeight<KernelType>(allCentroids.col(i), data.col(j), weight)) {
sumWeight += weight;
-
- // update new centroid.
newCentroid += weight * data.col(j);
-
}
}
@@ -139,11 +172,8 @@ Cluster(const MatType& data,
// calc the mean shift vector.
arma::Col<double> mhVector = newCentroid - allCentroids.col(i);
- // update the centroid.
- allCentroids.col(i) = newCentroid;
-
- // If the 2-norm of mean shift vector is small enough, it has converged.
- if (arma::norm(mhVector, 2) < 1e-3 * radius) {
+ // If the mean shift vector is small enough, it has converged.
+ if (metric.Evaluate(newCentroid, allCentroids.col(i)) < 1e-3 * radius) {
// Determine if the new centroid is duplicate with old ones.
bool isDuplicated = false;
@@ -171,6 +201,10 @@ Cluster(const MatType& data,
break;
}
+
+ // update the centroid.
+ allCentroids.col(i) = newCentroid;
+
}
}
More information about the mlpack-git
mailing list