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