21 #ifndef __mia_core_kmeans_hh
22 #define __mia_core_kmeans_hh
32 #include <boost/concept/requires.hpp>
33 #include <boost/concept_check.hpp>
40 template <
typename InputIterator,
typename OutputIterator>
41 bool kmeans_step(InputIterator ibegin, InputIterator iend, OutputIterator obegin,
42 std::vector<double>& classes,
size_t l,
int& biggest_class )
46 for (
size_t i = 0; i <= l; ++i )
47 cverb << std::setw(8) << classes[i] <<
" ";
51 const double convLimit = 0.005;
52 std::vector<double> sums(classes.size());
53 std::vector<size_t> count(classes.size());
57 while ( iter-- && !conv) {
58 sort(classes.begin(), classes.end());
60 OutputIterator ob = obegin;
62 for (InputIterator b = ibegin; b != iend; ++b, ++ob) {
73 for (
size_t i = 0; i <= l; i++) {
75 double a = sums[i] / count[i];
77 if (a &&
fabs ((a - classes[i]) / a) > convLimit)
82 if (max_count < count[i]) {
88 classes[i] = (classes[i] + classes[i + 1]) / 2.0;
90 classes[i] = (classes[i] + classes[i - 1]) / 2.0;
100 cvinfo() <<
"kmeans: " << l + 1 <<
" classes, " << 50 - iter <<
" iterations";
102 for (
size_t i = 0; i <= l; ++i )
103 cverb << std::setw(8) << classes[i] <<
" ";
110 template <
typename InputIterator,
typename OutputIterator>
112 std::vector<double>& classes,
const std::vector<bool>& fixed_center,
113 size_t l,
int& biggest_class )
117 for (
size_t i = 0; i <= l; ++i )
118 cverb << std::setw(8) << classes[i] <<
" ";
122 const double convLimit = 0.005;
123 std::vector<double> sums(classes.size());
124 std::vector<size_t> count(classes.size());
128 while ( iter-- && !conv) {
129 sort(classes.begin(), classes.end());
131 OutputIterator ob = obegin;
133 for (InputIterator b = ibegin; b != iend; ++b, ++ob) {
142 size_t max_count = 0;
144 for (
size_t i = 0; i <= l; i++) {
149 double a = sums[i] / count[i];
151 if (a &&
fabs ((a - classes[i]) / a) > convLimit)
156 if (max_count < count[i]) {
157 max_count = count[i];
162 classes[i] = (classes[i] + classes[i + 1]) / 2.0;
164 classes[i] = (classes[i] + classes[i - 1]) / 2.0;
174 cvinfo() <<
"kmeans: " << l + 1 <<
" classes, " << 50 - iter <<
" iterations";
176 for (
size_t i = 0; i <= l; ++i )
177 cverb << std::setw(8) << classes[i] <<
" ";
200 template <
typename InputIterator,
typename OutputIterator>
201 BOOST_CONCEPT_REQUIRES( ((::boost::ForwardIterator<InputIterator>))
202 ((::boost::Mutable_ForwardIterator<OutputIterator>)),
205 kmeans(InputIterator ibegin, InputIterator iend, OutputIterator obegin,
206 std::vector<
double>& classes)
208 if (classes.size() < 2)
209 throw create_exception<std::invalid_argument>(
"kmeans: requested ", classes.size(),
210 "class(es), required are at least two");
212 const size_t nclusters = classes.size();
213 const double size = std::distance(ibegin, iend);
215 if ( size < nclusters )
216 throw create_exception<std::invalid_argument>(
"kmeans: insufficient input: want ", nclusters,
217 " classes, but git only ", size,
" input elements");
221 classes[0] = sum / (size - 1);
222 classes[1] = sum / (size + 1);
224 int biggest_class = 0;
229 kmeans_step(ibegin, iend, obegin, classes, 1, biggest_class);
232 for (
size_t l = 2; l < nclusters; l++) {
233 const size_t pos = biggest_class > 0 ? biggest_class - 1 : biggest_class + 1;
234 classes[l] = 0.5 * (classes[biggest_class] + classes[pos]);
235 kmeans_step(ibegin, iend, obegin, classes, l, biggest_class);
239 for (
size_t l = 1; l < 3; l++) {
240 if (
kmeans_step(ibegin, iend, obegin, classes, nclusters - 1, biggest_class))
double fabs(const T3DVector< T > &t)
A way to get the norm of a T3DVector using faba syntax.
#define NS_MIA_BEGIN
conveniance define to start the mia namespace
#define EXPORT_CORE
Macro to manage Visual C++ style dllimport/dllexport.
#define NS_MIA_END
conveniance define to end the mia namespace
static F::result_type accumulate(F &f, const B &data)
vstream & cvinfo()
informal output that may be of interest to understand problems with a program and are of higher prior...
#define cverb
define a shortcut to the raw output stream
void kmeans(InputIterator ibegin, InputIterator iend, OutputIterator obegin, std::vector< double > &classes)
bool kmeans_step_with_fixed_centers(InputIterator ibegin, InputIterator iend, OutputIterator obegin, std::vector< double > &classes, const std::vector< bool > &fixed_center, size_t l, int &biggest_class)
bool kmeans_step(InputIterator ibegin, InputIterator iend, OutputIterator obegin, std::vector< double > &classes, size_t l, int &biggest_class)
int EXPORT_CORE kmeans_get_closest_clustercenter(const std::vector< double > &classes, size_t l, double value)