1 | #ifndef _theplu_yat_normalizer_spearman_ |
---|
2 | #define _theplu_yat_normalizer_spearman_ |
---|
3 | |
---|
4 | // $Id: Spearman.h 1575 2008-10-14 07:19:48Z jari $ |
---|
5 | |
---|
6 | /* |
---|
7 | Copyright (C) 2008 Peter Johansson |
---|
8 | |
---|
9 | This file is part of the yat library, http://dev.thep.lu.se/yat |
---|
10 | |
---|
11 | The yat library is free software; you can redistribute it and/or |
---|
12 | modify it under the terms of the GNU General Public License as |
---|
13 | published by the Free Software Foundation; either version 3 of the |
---|
14 | License, or (at your option) any later version. |
---|
15 | |
---|
16 | The yat library is distributed in the hope that it will be useful, |
---|
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
19 | General Public License for more details. |
---|
20 | |
---|
21 | You should have received a copy of the GNU General Public License |
---|
22 | along with yat. If not, see <http://www.gnu.org/licenses/>. |
---|
23 | */ |
---|
24 | |
---|
25 | #include "yat/utility/DataIterator.h" |
---|
26 | #include "yat/utility/iterator_traits.h" |
---|
27 | #include "yat/utility/sort_index.h" |
---|
28 | #include "yat/utility/WeightIterator.h" |
---|
29 | |
---|
30 | #include <algorithm> |
---|
31 | #include <functional> |
---|
32 | #include <vector> |
---|
33 | |
---|
34 | namespace theplu { |
---|
35 | namespace yat { |
---|
36 | namespace normalizer { |
---|
37 | |
---|
38 | /** |
---|
39 | \brief Replace elements with normalized rank |
---|
40 | |
---|
41 | \since New in yat 0.5 |
---|
42 | */ |
---|
43 | class Spearman |
---|
44 | { |
---|
45 | public: |
---|
46 | /** |
---|
47 | \brief default constructor |
---|
48 | */ |
---|
49 | Spearman(void){} |
---|
50 | |
---|
51 | /** |
---|
52 | It is possible to centralize a range "in place"; it is |
---|
53 | permissible for the iterators \a first and \a result to be the |
---|
54 | same. |
---|
55 | |
---|
56 | Each element x is replaced by \f$ \frac{\sum I(x_i-x) |
---|
57 | w_i}{\sum w_i} \f$ where I(x) = 1 for x>0, I(x) = 0.5 for x=0, |
---|
58 | and I(x) = 0 for x<0. |
---|
59 | |
---|
60 | \return result + (last-first) |
---|
61 | */ |
---|
62 | template<typename ForwardIterator, typename RandomAccessIterator> |
---|
63 | RandomAccessIterator operator()(ForwardIterator first, ForwardIterator last, |
---|
64 | RandomAccessIterator result) const |
---|
65 | { |
---|
66 | typename utility::weighted_iterator_traits<ForwardIterator>::type tag; |
---|
67 | return normalize(first, last, result, tag); |
---|
68 | } |
---|
69 | |
---|
70 | |
---|
71 | private: |
---|
72 | // unweighted version |
---|
73 | template<typename ForwardIterator, typename RandomAccessIterator> |
---|
74 | RandomAccessIterator normalize(ForwardIterator first, ForwardIterator last, |
---|
75 | RandomAccessIterator result, |
---|
76 | utility::unweighted_iterator_tag) const |
---|
77 | { |
---|
78 | std::vector<size_t> perm; |
---|
79 | utility::sort_index(first, last, perm); |
---|
80 | double n = perm.size(); |
---|
81 | size_t i=0; |
---|
82 | while ( i<perm.size() ) { |
---|
83 | size_t min_i = i; |
---|
84 | while (i<perm.size() && first[perm[i]]<=first[perm[min_i]]) |
---|
85 | ++i; |
---|
86 | double res = static_cast<double>(i + min_i)/(2*n); |
---|
87 | for ( ; min_i < i; ++min_i) |
---|
88 | result[perm[min_i]] = res; |
---|
89 | } |
---|
90 | return result + std::distance(first, last); |
---|
91 | } |
---|
92 | |
---|
93 | |
---|
94 | // weighted version |
---|
95 | template<typename ForwardIterator, typename RandomAccessIterator> |
---|
96 | RandomAccessIterator normalize(ForwardIterator first, ForwardIterator last, |
---|
97 | RandomAccessIterator result, |
---|
98 | utility::weighted_iterator_tag) const |
---|
99 | { |
---|
100 | std::copy(utility::weight_iterator(first), |
---|
101 | utility::weight_iterator(last), |
---|
102 | utility::weight_iterator(result)); |
---|
103 | // set values with w=0 to 0 to avoid problems with NaNs |
---|
104 | utility::iterator_traits<ForwardIterator> trait; |
---|
105 | for (ForwardIterator i=first; i!=last; ++i) |
---|
106 | if (trait.weight(i)==0) |
---|
107 | trait.data(i)=0.0; |
---|
108 | |
---|
109 | std::vector<size_t> perm(std::distance(first, last)); |
---|
110 | utility::sort_index(utility::data_iterator(first), |
---|
111 | utility::data_iterator(last), perm); |
---|
112 | utility::iterator_traits<RandomAccessIterator> rtrait; |
---|
113 | |
---|
114 | double sum_w=0; |
---|
115 | size_t i=0; |
---|
116 | while ( i<perm.size() ) { |
---|
117 | double w=0; |
---|
118 | size_t min_i = i; |
---|
119 | while (i<perm.size() && (trait.weight(first+perm[i])==0 || |
---|
120 | trait.data(first+perm[i]) <= |
---|
121 | trait.data(first+perm[min_i])) ) { |
---|
122 | w += trait.weight(first+perm[i]); |
---|
123 | ++i; |
---|
124 | } |
---|
125 | double res=sum_w + 0.5*w; |
---|
126 | for ( size_t j=min_i; j<i; ++j) |
---|
127 | rtrait.data(result+perm[j]) = res; |
---|
128 | sum_w += w; |
---|
129 | } |
---|
130 | |
---|
131 | size_t n = std::distance(first, last); |
---|
132 | std::transform(utility::data_iterator(result), |
---|
133 | utility::data_iterator(result+n), |
---|
134 | utility::data_iterator(result), |
---|
135 | std::bind2nd(std::divides<double>(), sum_w)); |
---|
136 | return result + n; |
---|
137 | } |
---|
138 | |
---|
139 | }; |
---|
140 | |
---|
141 | }}} // end of namespace normalizer, yat and thep |
---|
142 | #endif |
---|