MRPT  2.0.4
include/mrpt/math/kmeans.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
12 #include <mrpt/math/CMatrixFixed.h>
13 
14 namespace mrpt
15 {
16 namespace math
17 {
18 namespace detail
19 {
20 // Auxiliary method: templatized for working with float/double's.
21 template <typename SCALAR>
22 double internal_kmeans(
23  const bool use_kmeansplusplus_method, const size_t nPoints, const size_t k,
24  const size_t dims, const SCALAR* points, const size_t attempts,
25  SCALAR* out_center, int* out_assignments);
26 
27 // Auxiliary method, the actual code of the two front-end functions offered to
28 // the user below.
29 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
30 double stub_kmeans(
31  [[maybe_unused]] const bool use_kmeansplusplus_method, const size_t k,
32  const LIST_OF_VECTORS1& points, std::vector<int>& assignments,
33  LIST_OF_VECTORS2* out_centers, const size_t attempts)
34 {
36  ASSERT_(k >= 1);
37  const size_t N = points.size();
38  assignments.resize(N);
39  if (out_centers) out_centers->clear();
40  if (!N) return 0; // No points, we're done.
41  // Parse to required format:
42  size_t dims = 0;
43  const auto it_first = points.begin();
44  const auto it_end = points.end();
45  using TInnerVector = typename LIST_OF_VECTORS1::value_type;
46  using TInnerVectorCenters = typename LIST_OF_VECTORS2::value_type;
47  std::vector<typename TInnerVector::value_type> raw_vals;
48  typename TInnerVector::value_type* trg_ptr = nullptr;
49  for (typename LIST_OF_VECTORS1::const_iterator it = it_first; it != it_end;
50  ++it)
51  {
52  if (it == it_first)
53  {
54  dims = it->size();
55  ASSERTMSG_(dims > 0, "Dimensionality of points can't be zero.");
56  raw_vals.resize(N * dims);
57  trg_ptr = &raw_vals[0];
58  }
59  else
60  {
61  ASSERTMSG_(
62  size_t(dims) == size_t(it->size()),
63  "All points must have the same dimensionality.");
64  }
65 
67  trg_ptr, &(*it)[0],
68  dims * sizeof(typename TInnerVector::value_type));
69  trg_ptr += dims;
70  }
71  // Call the internal implementation:
72  std::vector<typename TInnerVectorCenters::value_type> centers(dims * k);
73  const double ret = detail::internal_kmeans(
74  false, N, k, points.begin()->size(), &raw_vals[0], attempts,
75  &centers[0], &assignments[0]);
76  // Centers:
77  if (out_centers)
78  {
79  const typename TInnerVectorCenters::value_type* center_ptr =
80  &centers[0];
81  for (size_t i = 0; i < k; i++)
82  {
83  TInnerVectorCenters c;
84  c.resize(dims);
85  for (size_t j = 0; j < dims; j++) c[j] = *center_ptr++;
86  out_centers->push_back(c);
87  }
88  }
89  return ret;
90  MRPT_END
91 }
92 } // namespace detail
93 
94 /** @name k-means algorithms
95 @{ */
96 
97 /** k-means algorithm to cluster a list of N points of arbitrary dimensionality
98  *into exactly K clusters.
99  * The list of input points can be any template CONTAINER<POINT> with:
100  * - CONTAINER can be: Any STL container:
101  *std::vector,std::list,std::deque,...
102  * - POINT can be:
103  * - std::vector<double/float>
104  * - CVectorFixedDouble<N> / CVectorFixedFloat<N>
105  *
106  * \param k [IN] Number of cluster to look for.
107  * \param points [IN] The list of N input points. It can be any STL-like
108  *containers of std::vector<float/double>, for example a
109  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
110  * \param assignments [OUT] At output it will have a number [0,k-1] for each
111  *of the N input points.
112  * \param out_centers [OUT] If not nullptr, at output will have the centers of
113  *each group. Can be of any of the supported types of "points", but the basic
114  *coordinates should be float or double exactly as in "points".
115  * \param attempts [IN] Number of attempts.
116  *
117  * \sa A more advanced algorithm, see: kmeanspp
118  * \note Uses the kmeans++ implementation by David Arthur (2009,
119  *http://www.stanford.edu/~darthur/kmpp.zip).
120  */
121 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2>
122 inline double kmeans(
123  const size_t k, const LIST_OF_VECTORS1& points,
124  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
125  const size_t attempts = 3)
126 {
127  return detail::stub_kmeans(
128  false /* standard method */, k, points, assignments, out_centers,
129  attempts);
130 }
131 
132 /** k-means++ algorithm to cluster a list of N points of arbitrary
133  *dimensionality into exactly K clusters.
134  * The list of input points can be any template CONTAINER<POINT> with:
135  * - CONTAINER can be: Any STL container:
136  *std::vector,std::list,std::deque,...
137  * - POINT can be:
138  * - std::vector<double/float>
139  * - CVectorFixedDouble<N> / CVectorFixedFloat<N>
140  *
141  * \param k [IN] Number of cluster to look for.
142  * \param points [IN] The list of N input points. It can be any STL-like
143  *containers of std::vector<float/double>, for example a
144  *std::vector<mrpt::math::CVectorDouble>, a std::list<CVectorFloat>, etc...
145  * \param assignments [OUT] At output it will have a number [0,k-1] for each
146  *of the N input points.
147  * \param out_centers [OUT] If not nullptr, at output will have the centers of
148  *each group. Can be of any of the supported types of "points", but the basic
149  *coordinates should be float or double exactly as in "points".
150  * \param attempts [IN] Number of attempts.
151  *
152  * \sa The standard kmeans algorithm, see: kmeans
153  * \note Uses the kmeans++ implementation by David Arthur (2009,
154  *http://www.stanford.edu/~darthur/kmpp.zip).
155  */
156 template <class LIST_OF_VECTORS1, class LIST_OF_VECTORS2 = LIST_OF_VECTORS1>
157 inline double kmeanspp(
158  const size_t k, const LIST_OF_VECTORS1& points,
159  std::vector<int>& assignments, LIST_OF_VECTORS2* out_centers = nullptr,
160  const size_t attempts = 3)
161 {
162  return detail::stub_kmeans(
163  true /* kmeans++ algorithm*/, k, points, assignments, out_centers,
164  attempts);
165 }
166 
167 /** @} */
168 
169 } // namespace math
170 } // namespace mrpt
#define MRPT_START
Definition: exceptions.h:241
double kmeans(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=nullptr, const size_t attempts=3)
k-means algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define ASSERT_(f)
Defines an assertion mechanism.
Definition: exceptions.h:120
double stub_kmeans([[maybe_unused]] const bool use_kmeansplusplus_method, const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers, const size_t attempts)
double kmeanspp(const size_t k, const LIST_OF_VECTORS1 &points, std::vector< int > &assignments, LIST_OF_VECTORS2 *out_centers=nullptr, const size_t attempts=3)
k-means++ algorithm to cluster a list of N points of arbitrary dimensionality into exactly K clusters...
#define ASSERTMSG_(f, __ERROR_MSG)
Defines an assertion mechanism.
Definition: exceptions.h:108
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
#define MRPT_END
Definition: exceptions.h:245
double internal_kmeans(const bool use_kmeansplusplus_method, const size_t nPoints, const size_t k, const size_t dims, const SCALAR *points, const size_t attempts, SCALAR *out_center, int *out_assignments)
void memcpy(void *dest, size_t destSize, const void *src, size_t copyCount) noexcept
An OS and compiler independent version of "memcpy".



Page generated by Doxygen 1.8.14 for MRPT 2.0.4 Git: 7b5ddf9de Fri May 29 14:02:56 2020 +0200 at vie may 29 14:15:09 CEST 2020