1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // weighted_p_square_quantile.hpp |
3 | // |
4 | // Copyright 2005 Daniel Egloff. 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_P_SQUARE_QUANTILE_HPP_DE_01_01_2006 |
9 | #define BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_P_SQUARE_QUANTILE_HPP_DE_01_01_2006 |
10 | |
11 | #include <cmath> |
12 | #include <functional> |
13 | #include <boost/array.hpp> |
14 | #include <boost/parameter/keyword.hpp> |
15 | #include <boost/mpl/placeholders.hpp> |
16 | #include <boost/type_traits/is_same.hpp> |
17 | #include <boost/accumulators/framework/accumulator_base.hpp> |
18 | #include <boost/accumulators/framework/extractor.hpp> |
19 | #include <boost/accumulators/numeric/functional.hpp> |
20 | #include <boost/accumulators/framework/parameters/sample.hpp> |
21 | #include <boost/accumulators/statistics_fwd.hpp> |
22 | #include <boost/accumulators/statistics/count.hpp> |
23 | #include <boost/accumulators/statistics/sum.hpp> |
24 | #include <boost/accumulators/statistics/parameters/quantile_probability.hpp> |
25 | |
26 | namespace boost { namespace accumulators |
27 | { |
28 | |
29 | namespace impl { |
30 | /////////////////////////////////////////////////////////////////////////////// |
31 | // weighted_p_square_quantile_impl |
32 | // single quantile estimation with weighted samples |
33 | /** |
34 | @brief Single quantile estimation with the \f$P^2\f$ algorithm for weighted samples |
35 | |
36 | This version of the \f$P^2\f$ algorithm extends the \f$P^2\f$ algorithm to support weighted samples. |
37 | The \f$P^2\f$ algorithm estimates a quantile dynamically without storing samples. Instead of |
38 | storing the whole sample cumulative distribution, only five points (markers) are stored. The heights |
39 | of these markers are the minimum and the maximum of the samples and the current estimates of the |
40 | \f$(p/2)\f$-, \f$p\f$ - and \f$(1+p)/2\f$ -quantiles. Their positions are equal to the number |
41 | of samples that are smaller or equal to the markers. Each time a new sample is added, the |
42 | positions of the markers are updated and if necessary their heights are adjusted using a piecewise- |
43 | parabolic formula. |
44 | |
45 | For further details, see |
46 | |
47 | R. Jain and I. Chlamtac, The P^2 algorithm for dynamic calculation of quantiles and |
48 | histograms without storing observations, Communications of the ACM, |
49 | Volume 28 (October), Number 10, 1985, p. 1076-1085. |
50 | |
51 | @param quantile_probability |
52 | */ |
53 | template<typename Sample, typename Weight, typename Impl> |
54 | struct weighted_p_square_quantile_impl |
55 | : accumulator_base |
56 | { |
57 | typedef typename numeric::functional::multiplies<Sample, Weight>::result_type weighted_sample; |
58 | typedef typename numeric::functional::fdiv<weighted_sample, std::size_t>::result_type float_type; |
59 | typedef array<float_type, 5> array_type; |
60 | // for boost::result_of |
61 | typedef float_type result_type; |
62 | |
63 | template<typename Args> |
64 | weighted_p_square_quantile_impl(Args const &args) |
65 | : p(is_same<Impl, for_median>::value ? 0.5 : args[quantile_probability | 0.5]) |
66 | , heights() |
67 | , actual_positions() |
68 | , desired_positions() |
69 | { |
70 | } |
71 | |
72 | template<typename Args> |
73 | void operator ()(Args const &args) |
74 | { |
75 | std::size_t cnt = count(args); |
76 | |
77 | // accumulate 5 first samples |
78 | if (cnt <= 5) |
79 | { |
80 | this->heights[cnt - 1] = args[sample]; |
81 | |
82 | // In this initialization phase, actual_positions stores the weights of the |
83 | // initial samples that are needed at the end of the initialization phase to |
84 | // compute the correct initial positions of the markers. |
85 | this->actual_positions[cnt - 1] = args[weight]; |
86 | |
87 | // complete the initialization of heights and actual_positions by sorting |
88 | if (cnt == 5) |
89 | { |
90 | // TODO: we need to sort the initial samples (in heights) in ascending order and |
91 | // sort their weights (in actual_positions) the same way. The following lines do |
92 | // it, but there must be a better and more efficient way of doing this. |
93 | typename array_type::iterator it_begin, it_end, it_min; |
94 | |
95 | it_begin = this->heights.begin(); |
96 | it_end = this->heights.end(); |
97 | |
98 | std::size_t pos = 0; |
99 | |
100 | while (it_begin != it_end) |
101 | { |
102 | it_min = std::min_element(it_begin, it_end); |
103 | std::size_t d = std::distance(it_begin, it_min); |
104 | std::swap(*it_begin, *it_min); |
105 | std::swap(this->actual_positions[pos], this->actual_positions[pos + d]); |
106 | ++it_begin; |
107 | ++pos; |
108 | } |
109 | |
110 | // calculate correct initial actual positions |
111 | for (std::size_t i = 1; i < 5; ++i) |
112 | { |
113 | this->actual_positions[i] += this->actual_positions[i - 1]; |
114 | } |
115 | } |
116 | } |
117 | else |
118 | { |
119 | std::size_t sample_cell = 1; // k |
120 | |
121 | // find cell k such that heights[k-1] <= args[sample] < heights[k] and adjust extreme values |
122 | if (args[sample] < this->heights[0]) |
123 | { |
124 | this->heights[0] = args[sample]; |
125 | this->actual_positions[0] = args[weight]; |
126 | sample_cell = 1; |
127 | } |
128 | else if (this->heights[4] <= args[sample]) |
129 | { |
130 | this->heights[4] = args[sample]; |
131 | sample_cell = 4; |
132 | } |
133 | else |
134 | { |
135 | typedef typename array_type::iterator iterator; |
136 | iterator it = std::upper_bound( |
137 | this->heights.begin() |
138 | , this->heights.end() |
139 | , args[sample] |
140 | ); |
141 | |
142 | sample_cell = std::distance(this->heights.begin(), it); |
143 | } |
144 | |
145 | // increment positions of markers above sample_cell |
146 | for (std::size_t i = sample_cell; i < 5; ++i) |
147 | { |
148 | this->actual_positions[i] += args[weight]; |
149 | } |
150 | |
151 | // update desired positions for all markers |
152 | this->desired_positions[0] = this->actual_positions[0]; |
153 | this->desired_positions[1] = (sum_of_weights(args) - this->actual_positions[0]) |
154 | * this->p/2. + this->actual_positions[0]; |
155 | this->desired_positions[2] = (sum_of_weights(args) - this->actual_positions[0]) |
156 | * this->p + this->actual_positions[0]; |
157 | this->desired_positions[3] = (sum_of_weights(args) - this->actual_positions[0]) |
158 | * (1. + this->p)/2. + this->actual_positions[0]; |
159 | this->desired_positions[4] = sum_of_weights(args); |
160 | |
161 | // adjust height and actual positions of markers 1 to 3 if necessary |
162 | for (std::size_t i = 1; i <= 3; ++i) |
163 | { |
164 | // offset to desired positions |
165 | float_type d = this->desired_positions[i] - this->actual_positions[i]; |
166 | |
167 | // offset to next position |
168 | float_type dp = this->actual_positions[i + 1] - this->actual_positions[i]; |
169 | |
170 | // offset to previous position |
171 | float_type dm = this->actual_positions[i - 1] - this->actual_positions[i]; |
172 | |
173 | // height ds |
174 | float_type hp = (this->heights[i + 1] - this->heights[i]) / dp; |
175 | float_type hm = (this->heights[i - 1] - this->heights[i]) / dm; |
176 | |
177 | if ( ( d >= 1. && dp > 1. ) || ( d <= -1. && dm < -1. ) ) |
178 | { |
179 | short sign_d = static_cast<short>(d / std::abs(d)); |
180 | |
181 | // try adjusting heights[i] using p-squared formula |
182 | float_type h = this->heights[i] + sign_d / (dp - dm) * ( (sign_d - dm) * hp + (dp - sign_d) * hm ); |
183 | |
184 | if ( this->heights[i - 1] < h && h < this->heights[i + 1] ) |
185 | { |
186 | this->heights[i] = h; |
187 | } |
188 | else |
189 | { |
190 | // use linear formula |
191 | if (d>0) |
192 | { |
193 | this->heights[i] += hp; |
194 | } |
195 | if (d<0) |
196 | { |
197 | this->heights[i] -= hm; |
198 | } |
199 | } |
200 | this->actual_positions[i] += sign_d; |
201 | } |
202 | } |
203 | } |
204 | } |
205 | |
206 | result_type result(dont_care) const |
207 | { |
208 | return this->heights[2]; |
209 | } |
210 | |
211 | // make this accumulator serializeable |
212 | // TODO split to save/load and check on parameters provided in ctor |
213 | template<class Archive> |
214 | void serialize(Archive & ar, const unsigned int file_version) |
215 | { |
216 | ar & p; |
217 | ar & heights; |
218 | ar & actual_positions; |
219 | ar & desired_positions; |
220 | } |
221 | |
222 | private: |
223 | float_type p; // the quantile probability p |
224 | array_type heights; // q_i |
225 | array_type actual_positions; // n_i |
226 | array_type desired_positions; // n'_i |
227 | }; |
228 | |
229 | } // namespace impl |
230 | |
231 | /////////////////////////////////////////////////////////////////////////////// |
232 | // tag::weighted_p_square_quantile |
233 | // |
234 | namespace tag |
235 | { |
236 | struct weighted_p_square_quantile |
237 | : depends_on<count, sum_of_weights> |
238 | { |
239 | typedef accumulators::impl::weighted_p_square_quantile_impl<mpl::_1, mpl::_2, regular> impl; |
240 | }; |
241 | struct weighted_p_square_quantile_for_median |
242 | : depends_on<count, sum_of_weights> |
243 | { |
244 | typedef accumulators::impl::weighted_p_square_quantile_impl<mpl::_1, mpl::_2, for_median> impl; |
245 | }; |
246 | } |
247 | |
248 | /////////////////////////////////////////////////////////////////////////////// |
249 | // extract::weighted_p_square_quantile |
250 | // extract::weighted_p_square_quantile_for_median |
251 | // |
252 | namespace extract |
253 | { |
254 | extractor<tag::weighted_p_square_quantile> const = {}; |
255 | extractor<tag::weighted_p_square_quantile_for_median> const = {}; |
256 | |
257 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_p_square_quantile) |
258 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_p_square_quantile_for_median) |
259 | } |
260 | |
261 | using extract::weighted_p_square_quantile; |
262 | using extract::weighted_p_square_quantile_for_median; |
263 | |
264 | }} // namespace boost::accumulators |
265 | |
266 | #endif |
267 | |