Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / accumulators / statistics / weighted_median.hpp @ 2486

History | View | Annotate | Download (8 kB)

1
///////////////////////////////////////////////////////////////////////////////
2
// weighted_median.hpp
3
//
4
//  Copyright 2006 Eric Niebler, Olivier Gygi. Distributed under the Boost
5
//  Software License, Version 1.0. (See accompanying file
6
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7

    
8
#ifndef BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_MEDIAN_HPP_EAN_28_10_2005
9
#define BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_MEDIAN_HPP_EAN_28_10_2005
10

    
11
#include <boost/mpl/placeholders.hpp>
12
#include <boost/range/iterator_range.hpp>
13
#include <boost/accumulators/framework/accumulator_base.hpp>
14
#include <boost/accumulators/framework/extractor.hpp>
15
#include <boost/accumulators/numeric/functional.hpp>
16
#include <boost/accumulators/framework/parameters/sample.hpp>
17
#include <boost/accumulators/framework/depends_on.hpp>
18
#include <boost/accumulators/statistics_fwd.hpp>
19
#include <boost/accumulators/statistics/count.hpp>
20
#include <boost/accumulators/statistics/median.hpp>
21
#include <boost/accumulators/statistics/weighted_p_square_quantile.hpp>
22
#include <boost/accumulators/statistics/weighted_density.hpp>
23
#include <boost/accumulators/statistics/weighted_p_square_cumul_dist.hpp>
24

    
25
namespace boost { namespace accumulators
26
{
27

    
28
namespace impl
29
{
30
    ///////////////////////////////////////////////////////////////////////////////
31
    // weighted_median_impl
32
    //
33
    /**
34
        @brief Median estimation for weighted samples based on the \f$P^2\f$ quantile estimator
35

36
        The \f$P^2\f$ algorithm for weighted samples is invoked with a quantile probability of 0.5.
37
    */
38
    template<typename Sample>
39
    struct weighted_median_impl
40
      : accumulator_base
41
    {
42
        // for boost::result_of
43
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type result_type;
44

    
45
        weighted_median_impl(dont_care) {}
46

    
47
        template<typename Args>
48
        result_type result(Args const &args) const
49
        {
50
            return weighted_p_square_quantile_for_median(args);
51
        }
52
    };
53

    
54
    ///////////////////////////////////////////////////////////////////////////////
55
    // with_density_weighted_median_impl
56
    //
57
    /**
58
        @brief Median estimation for weighted samples based on the density estimator
59

60
        The algorithm determines the bin in which the \f$0.5*cnt\f$-th sample lies, \f$cnt\f$ being
61
        the total number of samples. It returns the approximate horizontal position of this sample,
62
        based on a linear interpolation inside the bin.
63
    */
64
    template<typename Sample>
65
    struct with_density_weighted_median_impl
66
      : accumulator_base
67
    {
68
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
69
        typedef std::vector<std::pair<float_type, float_type> > histogram_type;
70
        typedef iterator_range<typename histogram_type::iterator> range_type;
71
        // for boost::result_of
72
        typedef float_type result_type;
73

    
74
        template<typename Args>
75
        with_density_weighted_median_impl(Args const &args)
76
          : sum(numeric::fdiv(args[sample | Sample()], (std::size_t)1))
77
          , is_dirty(true)
78
        {
79
        }
80

    
81
        void operator ()(dont_care)
82
        {
83
            this->is_dirty = true;
84
        }
85

    
86
        template<typename Args>
87
        result_type result(Args const &args) const
88
        {
89
            if (this->is_dirty)
90
            {
91
                this->is_dirty = false;
92

    
93
                std::size_t cnt = count(args);
94
                range_type histogram = weighted_density(args);
95
                typename range_type::iterator it = histogram.begin();
96
                while (this->sum < 0.5 * cnt)
97
                {
98
                    this->sum += it->second * cnt;
99
                    ++it;
100
                }
101
                --it;
102
                float_type over = numeric::fdiv(this->sum - 0.5 * cnt, it->second * cnt);
103
                this->median = it->first * over + (it + 1)->first * ( 1. - over );
104
            }
105

    
106
            return this->median;
107
        }
108

    
109
    private:
110
        mutable float_type sum;
111
        mutable bool is_dirty;
112
        mutable float_type median;
113
    };
114

    
115
    ///////////////////////////////////////////////////////////////////////////////
116
    // with_p_square_cumulative_distribution_weighted_median_impl
117
    //
118
    /**
119
        @brief Median estimation for weighted samples based on the \f$P^2\f$ cumulative distribution estimator
120

121
        The algorithm determines the first (leftmost) bin with a height exceeding 0.5. It
122
        returns the approximate horizontal position of where the cumulative distribution
123
        equals 0.5, based on a linear interpolation inside the bin.
124
    */
125
    template<typename Sample, typename Weight>
126
    struct with_p_square_cumulative_distribution_weighted_median_impl
127
      : accumulator_base
128
    {
129
        typedef typename numeric::functional::multiplies<Sample, Weight>::result_type weighted_sample;
130
        typedef typename numeric::functional::fdiv<weighted_sample, std::size_t>::result_type float_type;
131
        typedef std::vector<std::pair<float_type, float_type> > histogram_type;
132
        typedef iterator_range<typename histogram_type::iterator> range_type;
133
        // for boost::result_of
134
        typedef float_type result_type;
135

    
136
        with_p_square_cumulative_distribution_weighted_median_impl(dont_care)
137
          : is_dirty(true)
138
        {
139
        }
140

    
141
        void operator ()(dont_care)
142
        {
143
            this->is_dirty = true;
144
        }
145

    
146
        template<typename Args>
147
        result_type result(Args const &args) const
148
        {
149
            if (this->is_dirty)
150
            {
151
                this->is_dirty = false;
152

    
153
                range_type histogram = weighted_p_square_cumulative_distribution(args);
154
                typename range_type::iterator it = histogram.begin();
155
                while (it->second < 0.5)
156
                {
157
                    ++it;
158
                }
159
                float_type over = numeric::fdiv(it->second - 0.5, it->second - (it - 1)->second);
160
                this->median = it->first * over + (it + 1)->first * ( 1. - over );
161
            }
162

    
163
            return this->median;
164
        }
165
    private:
166
        mutable bool is_dirty;
167
        mutable float_type median;
168
    };
169

    
170
} // namespace impl
171

    
172
///////////////////////////////////////////////////////////////////////////////
173
// tag::weighted_median
174
// tag::with_density_weighted_median
175
// tag::with_p_square_cumulative_distribution_weighted_median
176
//
177
namespace tag
178
{
179
    struct weighted_median
180
      : depends_on<weighted_p_square_quantile_for_median>
181
    {
182
        /// INTERNAL ONLY
183
        ///
184
        typedef accumulators::impl::weighted_median_impl<mpl::_1> impl;
185
    };
186
    struct with_density_weighted_median
187
      : depends_on<count, weighted_density>
188
    {
189
        /// INTERNAL ONLY
190
        ///
191
        typedef accumulators::impl::with_density_weighted_median_impl<mpl::_1> impl;
192
    };
193
    struct with_p_square_cumulative_distribution_weighted_median
194
      : depends_on<weighted_p_square_cumulative_distribution>
195
    {
196
        /// INTERNAL ONLY
197
        ///
198
        typedef accumulators::impl::with_p_square_cumulative_distribution_weighted_median_impl<mpl::_1, mpl::_2> impl;
199
    };
200

    
201
}
202

    
203
///////////////////////////////////////////////////////////////////////////////
204
// extract::weighted_median
205
//
206
namespace extract
207
{
208
    extractor<tag::median> const weighted_median = {};
209

    
210
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_median)
211
}
212

    
213
using extract::weighted_median;
214
// weighted_median(with_p_square_quantile) -> weighted_median
215
template<>
216
struct as_feature<tag::weighted_median(with_p_square_quantile)>
217
{
218
    typedef tag::weighted_median type;
219
};
220

    
221
// weighted_median(with_density) -> with_density_weighted_median
222
template<>
223
struct as_feature<tag::weighted_median(with_density)>
224
{
225
    typedef tag::with_density_weighted_median type;
226
};
227

    
228
// weighted_median(with_p_square_cumulative_distribution) -> with_p_square_cumulative_distribution_weighted_median
229
template<>
230
struct as_feature<tag::weighted_median(with_p_square_cumulative_distribution)>
231
{
232
    typedef tag::with_p_square_cumulative_distribution_weighted_median type;
233
};
234

    
235
}} // namespace boost::accumulators
236

    
237
#endif