/////////////////////////////////////////////////////////////////////////////// | |
// weighted_median.hpp | |
// | |
// Copyright 2006 Eric Niebler, Olivier Gygi. Distributed under the Boost | |
// Software License, Version 1.0. (See accompanying file | |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
#ifndef BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_MEDIAN_HPP_EAN_28_10_2005 | |
#define BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_MEDIAN_HPP_EAN_28_10_2005 | |
#include <boost/mpl/placeholders.hpp> | |
#include <boost/range/iterator_range.hpp> | |
#include <boost/accumulators/framework/accumulator_base.hpp> | |
#include <boost/accumulators/framework/extractor.hpp> | |
#include <boost/accumulators/numeric/functional.hpp> | |
#include <boost/accumulators/framework/parameters/sample.hpp> | |
#include <boost/accumulators/framework/depends_on.hpp> | |
#include <boost/accumulators/statistics_fwd.hpp> | |
#include <boost/accumulators/statistics/count.hpp> | |
#include <boost/accumulators/statistics/median.hpp> | |
#include <boost/accumulators/statistics/weighted_p_square_quantile.hpp> | |
#include <boost/accumulators/statistics/weighted_density.hpp> | |
#include <boost/accumulators/statistics/weighted_p_square_cumulative_distribution.hpp> | |
namespace boost { namespace accumulators | |
{ | |
namespace impl | |
{ | |
/////////////////////////////////////////////////////////////////////////////// | |
// weighted_median_impl | |
// | |
/** | |
@brief Median estimation for weighted samples based on the \f$P^2\f$ quantile estimator | |
The \f$P^2\f$ algorithm for weighted samples is invoked with a quantile probability of 0.5. | |
*/ | |
template<typename Sample> | |
struct weighted_median_impl | |
: accumulator_base | |
{ | |
// for boost::result_of | |
typedef typename numeric::functional::average<Sample, std::size_t>::result_type result_type; | |
weighted_median_impl(dont_care) {} | |
template<typename Args> | |
result_type result(Args const &args) const | |
{ | |
return weighted_p_square_quantile_for_median(args); | |
} | |
}; | |
/////////////////////////////////////////////////////////////////////////////// | |
// with_density_weighted_median_impl | |
// | |
/** | |
@brief Median estimation for weighted samples based on the density estimator | |
The algorithm determines the bin in which the \f$0.5*cnt\f$-th sample lies, \f$cnt\f$ being | |
the total number of samples. It returns the approximate horizontal position of this sample, | |
based on a linear interpolation inside the bin. | |
*/ | |
template<typename Sample> | |
struct with_density_weighted_median_impl | |
: accumulator_base | |
{ | |
typedef typename numeric::functional::average<Sample, std::size_t>::result_type float_type; | |
typedef std::vector<std::pair<float_type, float_type> > histogram_type; | |
typedef iterator_range<typename histogram_type::iterator> range_type; | |
// for boost::result_of | |
typedef float_type result_type; | |
template<typename Args> | |
with_density_weighted_median_impl(Args const &args) | |
: sum(numeric::average(args[sample | Sample()], (std::size_t)1)) | |
, is_dirty(true) | |
{ | |
} | |
void operator ()(dont_care) | |
{ | |
this->is_dirty = true; | |
} | |
template<typename Args> | |
result_type result(Args const &args) const | |
{ | |
if (this->is_dirty) | |
{ | |
this->is_dirty = false; | |
std::size_t cnt = count(args); | |
range_type histogram = weighted_density(args); | |
typename range_type::iterator it = histogram.begin(); | |
while (this->sum < 0.5 * cnt) | |
{ | |
this->sum += it->second * cnt; | |
++it; | |
} | |
--it; | |
float_type over = numeric::average(this->sum - 0.5 * cnt, it->second * cnt); | |
this->median = it->first * over + (it + 1)->first * ( 1. - over ); | |
} | |
return this->median; | |
} | |
private: | |
mutable float_type sum; | |
mutable bool is_dirty; | |
mutable float_type median; | |
}; | |
/////////////////////////////////////////////////////////////////////////////// | |
// with_p_square_cumulative_distribution_weighted_median_impl | |
// | |
/** | |
@brief Median estimation for weighted samples based on the \f$P^2\f$ cumulative distribution estimator | |
The algorithm determines the first (leftmost) bin with a height exceeding 0.5. It | |
returns the approximate horizontal position of where the cumulative distribution | |
equals 0.5, based on a linear interpolation inside the bin. | |
*/ | |
template<typename Sample, typename Weight> | |
struct with_p_square_cumulative_distribution_weighted_median_impl | |
: accumulator_base | |
{ | |
typedef typename numeric::functional::multiplies<Sample, Weight>::result_type weighted_sample; | |
typedef typename numeric::functional::average<weighted_sample, std::size_t>::result_type float_type; | |
typedef std::vector<std::pair<float_type, float_type> > histogram_type; | |
typedef iterator_range<typename histogram_type::iterator> range_type; | |
// for boost::result_of | |
typedef float_type result_type; | |
with_p_square_cumulative_distribution_weighted_median_impl(dont_care) | |
: is_dirty(true) | |
{ | |
} | |
void operator ()(dont_care) | |
{ | |
this->is_dirty = true; | |
} | |
template<typename Args> | |
result_type result(Args const &args) const | |
{ | |
if (this->is_dirty) | |
{ | |
this->is_dirty = false; | |
range_type histogram = weighted_p_square_cumulative_distribution(args); | |
typename range_type::iterator it = histogram.begin(); | |
while (it->second < 0.5) | |
{ | |
++it; | |
} | |
float_type over = numeric::average(it->second - 0.5, it->second - (it - 1)->second); | |
this->median = it->first * over + (it + 1)->first * ( 1. - over ); | |
} | |
return this->median; | |
} | |
private: | |
mutable bool is_dirty; | |
mutable float_type median; | |
}; | |
} // namespace impl | |
/////////////////////////////////////////////////////////////////////////////// | |
// tag::weighted_median | |
// tag::with_density_weighted_median | |
// tag::with_p_square_cumulative_distribution_weighted_median | |
// | |
namespace tag | |
{ | |
struct weighted_median | |
: depends_on<weighted_p_square_quantile_for_median> | |
{ | |
/// INTERNAL ONLY | |
/// | |
typedef accumulators::impl::weighted_median_impl<mpl::_1> impl; | |
}; | |
struct with_density_weighted_median | |
: depends_on<count, weighted_density> | |
{ | |
/// INTERNAL ONLY | |
/// | |
typedef accumulators::impl::with_density_weighted_median_impl<mpl::_1> impl; | |
}; | |
struct with_p_square_cumulative_distribution_weighted_median | |
: depends_on<weighted_p_square_cumulative_distribution> | |
{ | |
/// INTERNAL ONLY | |
/// | |
typedef accumulators::impl::with_p_square_cumulative_distribution_weighted_median_impl<mpl::_1, mpl::_2> impl; | |
}; | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// extract::weighted_median | |
// | |
namespace extract | |
{ | |
extractor<tag::median> const weighted_median = {}; | |
BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_median) | |
} | |
using extract::weighted_median; | |
// weighted_median(with_p_square_quantile) -> weighted_median | |
template<> | |
struct as_feature<tag::weighted_median(with_p_square_quantile)> | |
{ | |
typedef tag::weighted_median type; | |
}; | |
// weighted_median(with_density) -> with_density_weighted_median | |
template<> | |
struct as_feature<tag::weighted_median(with_density)> | |
{ | |
typedef tag::with_density_weighted_median type; | |
}; | |
// weighted_median(with_p_square_cumulative_distribution) -> with_p_square_cumulative_distribution_weighted_median | |
template<> | |
struct as_feature<tag::weighted_median(with_p_square_cumulative_distribution)> | |
{ | |
typedef tag::with_p_square_cumulative_distribution_weighted_median type; | |
}; | |
}} // namespace boost::accumulators | |
#endif |