1 /** 2 * @file core/metrics/lmetric.hpp 3 * @author Ryan Curtin 4 * 5 * Generalized L-metric, allowing both squared distances to be returned as well 6 * as non-squared distances. The squared distances are faster to compute. 7 * 8 * This also gives several convenience typedefs for commonly used L-metrics. 9 * 10 * mlpack is free software; you may redistribute it and/or modify it under the 11 * terms of the 3-clause BSD license. You should have received a copy of the 12 * 3-clause BSD license along with mlpack. If not, see 13 * http://www.opensource.org/licenses/BSD-3-Clause for more information. 14 */ 15 #ifndef MLPACK_CORE_METRICS_LMETRIC_HPP 16 #define MLPACK_CORE_METRICS_LMETRIC_HPP 17 18 #include <mlpack/prereqs.hpp> 19 20 namespace mlpack { 21 namespace metric { 22 23 /** 24 * The L_p metric for arbitrary integer p, with an option to take the root. 25 * 26 * This class implements the standard L_p metric for two arbitrary vectors @f$ x 27 * @f$ and @f$ y @f$ of dimensionality @f$ n @f$: 28 * 29 * @f[ 30 * d(x, y) = \left( \sum_{i = 1}^{n} | x_i - y_i |^p \right)^{\frac{1}{p}}. 31 * @f] 32 * 33 * The value of p is given as a template parameter. 34 * 35 * In addition, the function @f$ d(x, y) @f$ can be simplified, neglecting the 36 * p-root calculation. This is done by specifying the TakeRoot template 37 * parameter to be false. Then, 38 * 39 * @f[ 40 * d(x, y) = \sum_{i = 1}^{n} | x_i - y_i |^p 41 * @f] 42 * 43 * It is faster to compute that distance, so TakeRoot is by default off. 44 * However, when TakeRoot is false, the distance given is not actually a true 45 * metric -- it does not satisfy the triangle inequality. Some mlpack methods 46 * do not require the triangle inequality to operate correctly (such as the 47 * BinarySpaceTree), but setting TakeRoot = false in some cases will cause 48 * incorrect results. 49 * 50 * A few convenience typedefs are given: 51 * 52 * - ManhattanDistance 53 * - EuclideanDistance 54 * - SquaredEuclideanDistance 55 * 56 * @tparam Power Power of metric; i.e. Power = 1 gives the L1-norm (Manhattan 57 * distance). 58 * @tparam TakeRoot If true, the Power'th root of the result is taken before it 59 * is returned. Setting this to false causes the metric to not satisfy the 60 * Triangle Inequality (be careful!). 61 */ 62 template<int TPower, bool TTakeRoot = true> 63 class LMetric 64 { 65 public: 66 /** 67 * Default constructor does nothing, but is required to satisfy the Metric 68 * policy. 69 */ LMetric()70 LMetric() { } 71 72 /** 73 * Computes the distance between two points. 74 * 75 * @tparam VecTypeA Type of first vector (generally arma::vec or 76 * arma::sp_vec). 77 * @tparam VecTypeB Type of second vector. 78 * @param a First vector. 79 * @param b Second vector. 80 * @return Distance between vectors a and b. 81 */ 82 template<typename VecTypeA, typename VecTypeB> 83 static typename VecTypeA::elem_type Evaluate(const VecTypeA& a, 84 const VecTypeB& b); 85 86 //! Serialize the metric (nothing to do). 87 template<typename Archive> serialize(Archive &,const unsigned int)88 void serialize(Archive& /* ar */, const unsigned int /* version */) { } 89 90 //! The power of the metric. 91 static const int Power = TPower; 92 //! Whether or not the root is taken. 93 static const bool TakeRoot = TTakeRoot; 94 }; 95 96 // Convenience typedefs. 97 98 /** 99 * The Manhattan (L1) distance. 100 */ 101 typedef LMetric<1, false> ManhattanDistance; 102 103 /** 104 * The squared Euclidean (L2) distance. Note that this is not technically a 105 * metric! But it can sometimes be used when distances are required. 106 */ 107 typedef LMetric<2, false> SquaredEuclideanDistance; 108 109 /** 110 * The Euclidean (L2) distance. 111 */ 112 typedef LMetric<2, true> EuclideanDistance; 113 114 /** 115 * The L-infinity distance. 116 */ 117 typedef LMetric<INT_MAX, false> ChebyshevDistance; 118 119 120 } // namespace metric 121 } // namespace mlpack 122 123 // Include implementation. 124 #include "lmetric_impl.hpp" 125 126 #endif 127