Free cookie consent management tool by TermsFeed Policy Generator

# source:branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views/3.3/KruskalWallis.cs@9316

Last change on this file since 9316 was 9316, checked in by ascheibe, 11 years ago

#1886 implemented Kruskal-Wallis Test

File size: 4.2 KB
Line
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24
25namespace HeuristicLab.Analysis.AlgorithmBehavior.Analyzers {
26  // Kruskal Wallis test based on R's kruskal.test()
27  public class KruskalWallis {
28    public static double Test(double[][] data) {
29      double[] g;
30      double[] x = FlattenArray(data, out g);
31      int n = x.Length;
32      int parameter = data.Length - 1;
33
34      int[] r = Rank(x);
35      double[][] ties = CountDuplicates(x);
36      double statistic = CalculateStatistic(r, g);
37      double tiesCorrection = CalculateTiesCorrection(ties);
38      statistic = ((12 * statistic / (n * (n + 1)) - 3 * (n + 1)) /
39                  (1 - tiesCorrection / (Math.Pow(n, 3) - n)));
40
41      return alglib.chisquarecdistribution(parameter, statistic);
42    }
43
44    private static double CalculateStatistic(int[] r, double[] g) {
45      double result = 0.0;
46      double lastG = g[0];
47      double curSum = 0.0;
48      int cnt = 0;
49      for (int i = 0; i < r.Length; i++) {
50        if (lastG == g[i]) {
51          curSum += r[i];
52          cnt++;
53        } else {
54          double sum = Math.Pow(curSum, 2);
55          sum /= cnt;
56          result += sum;
57
58          lastG = g[i];
59          curSum = r[i];
60          cnt = 1;
61        }
62      }
63
64      double lastSum = Math.Pow(curSum, 2);
65      lastSum /= cnt;
66      result += lastSum;
67
68      return result;
69    }
70
71    private static double CalculateTiesCorrection(double[][] ties) {
72      double sum = 0.0;
73      for (int i = 0; i < ties[1].Length; i++) {
74        double tic = Math.Pow(ties[1][i], 3) - ties[1][i];
75        sum += tic;
76      }
77      return sum;
78    }
79
80    public static double[] FlattenArray(double[][] x, out double[] indizes) {
81      int compLenght = 0;
82      for (int i = 0; i < x.Length; i++) {
83        compLenght += x[i].Length;
84      }
85
86      double[] result = new double[compLenght];
87      indizes = new double[compLenght];
88
89      int resultPos = 0;
90      for (int i = 0; i < x.Length; i++) {
91        Array.Copy(x[i], 0, result, resultPos, x[i].Length);
92
93        for (int j = resultPos; j < resultPos + x[i].Length; j++) {
94          indizes[j] = i;
95        }
96        resultPos += x[i].Length;
97      }
98
99      return result;
100    }
101
102    public static double[][] CountDuplicates(double[] x) {
103      List<double> number = new List<double>();
104      List<double> cnt = new List<double>();
105      double[] sortedX = new double[x.Length];
106
107      Array.Copy(x, sortedX, x.Length);
108      Array.Sort(sortedX);
109
110      double last = x[0];
113
114      for (int i = 1; i < x.Length; i++) {
115        if (last != x[i]) {
117          last = x[i];
119        } else {
120          cnt[cnt.Count - 1] += 1;
121        }
122      }
123
124      double[][] result = new double[2][];
125      result[0] = number.ToArray();
126      result[1] = cnt.ToArray();
127
128      return result;
129    }
130
131    public static int[] Rank(double[] x) {
132      double[] keys = new double[x.Length];
133      int[] items = new int[x.Length];
134      int[] ranks = new int[x.Length];
135
136      Array.Copy(x, keys, x.Length);
137      for (int i = 0; i < x.Length; i++) items[i] = i;
138
139      Array.Sort(keys, items);
140
141      for (int i = 0; i < x.Length; i++) {
142        ranks[items[i]] = i + 1;
143      }
144      return ranks;
145    }
146  }
147}
Note: See TracBrowser for help on using the repository browser.