source: trunk/yat/normalizer/Spearman.h @ 1546

Last change on this file since 1546 was 1512, checked in by Peter, 13 years ago

fixes #439 - and also took care of ties

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