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