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

Last change on this file since 1644 was 1575, checked in by Jari Häkkinen, 13 years ago

Added missing $ tag.

  • 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// $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
34namespace theplu {
35namespace yat {
36namespace 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
Note: See TracBrowser for help on using the repository browser.