Введение
Тест перестановок (также называемый тестом повторной рандомизации или тестом перестановки) – это точный статистический тест гипотез, использующий доказательство от противного. Тест перестановок включает в себя два или более образца. Нулевая гипотеза состоит в том, что все образцы взяты из одного и того же распределения. При нулевой гипотезе распределение тестовой статистики определяется путем вычисления всех возможных значений тестовой статистики при возможных перестановках наблюдаемых данных. Следовательно, тесты перестановок являются формой перевыборки. Тесты перестановок можно понимать как тестирование суррогатных данных, где суррогатные данные при нулевой гипотезе получаются путем перестановок исходных данных. Иными словами, метод, с помощью которого воздействие распределяется между объектами в экспериментальном дизайне, отражается в анализе этого дизайна. Если метки взаимозаменяемы при нулевой гипотезе, то полученные тесты дают точные уровни значимости; см. также взаимозаменяемость. На основе этих тестов можно получить доверительные интервалы. Теория развивалась на основе работ Рональда Фишера и Э. Дж. Г. Питмана в 1930-х годах. Тесты перестановок не следует путать с рандомизированными тестами.
A permutation test (also called re randomization test or shuffle test) is an exact statistical hypothesis test making use of the proof by contradiction. A permutation test involves two or more samples. The null hypothesis is that all samples come from the same distribution Under the null hypothesis, the distribution of the test statistic is obtained by calculating all possible values of the test statistic under possible rearrangements of the observed data. Permutation tests are, therefore, a form of resampling. Permutation tests can be understood as surrogate data testing where the surrogate data under the null hypothesis are obtained through permutations of the original data. In other words, the method by which treatments are allocated to subjects in an experimental design is mirrored in the analysis of that design. If the labels are exchangeable under the null hypothesis, then the resulting tests yield exact significance levels; see also exchangeability. Confidence intervals can then be derived from the tests. The theory has evolved from the works of Ronald Fisher and E. J. G. Pitman in the 1930s. Permutation tests should not be confused with randomized tests.
Метод
Чтобы проиллюстрировать основную идею перестановочного теста, предположим, что мы собираем случайные величины и для каждого индивидуума из двух групп и , средние значения выборок которых равны и , и мы хотим узнать, принадлежат ли и одному и тому же распределению. Пусть и – размеры выборок, собранных из каждой группы. Перестановочный тест предназначен для определения того, достаточно ли велика наблюдаемая разница между средними значениями выборок, чтобы отвергнуть на некотором уровне значимости нулевую гипотезу H о том, что данные, полученные из , происходят из того же распределения, что и данные, полученные из .
The test proceeds as follows. First, the difference in means between the two samples is calculated: this is the observed value of the test statistic,
Next, the observations of groups and are pooled, and the difference in sample means is calculated and recorded for every possible way of dividing the pooled values into two groups of size and (i. e., for every permutation of the group labels A and B). The set of these calculated differences is the exact distribution of possible differences (for this sample) under the null hypothesis that group labels are exchangeable (i. e., are randomly assigned). The one sided p value of the test is calculated as the proportion of sampled permutations where the difference in means was greater than The two sided p value of the test is calculated as the proportion of sampled permutations where the absolute difference was greater than Many implementations of permutation tests require that the observed data itself be counted as one of the permutations so that the permutation p value will never be zero. Alternatively, if the only purpose of the test is to reject or not reject the null hypothesis, one could sort the recorded differences, and then observe if is contained within the middle % of them, for some significance level If it is not, we reject the hypothesis of identical probability curves at the significance level. For paired samples the paired permutation test needs to be applied.
Тест проводится следующим образом. Сначала вычисляется разница между средними значениями двух выборок: это наблюдаемое значение статистики теста, . Затем наблюдения из групп и объединяются, и разница между средними значениями выборки вычисляется и записывается для каждого возможного способа разделения объединенных значений на две группы размером и (то есть для каждой перестановки меток групп A и B). Множество этих вычисленных разностей представляет собой точное распределение возможных разностей (для данной выборки) при нулевой гипотезе, согласно которой метки групп взаимозаменяемы (то есть назначены случайным образом). Одностороннее p-значение теста вычисляется как доля перестановленных выборок, в которых разница между средними значениями была больше, чем . Двустороннее p-значение теста вычисляется как доля перестановленных выборок, в которых абсолютная разница была больше, чем . Многие реализации перестановочных тестов требуют, чтобы наблюдаемые данные сами по себе учитывались как одна из перестановок, чтобы p-значение перестановочного теста никогда не было равно нулю. В качестве альтернативы, если единственная цель теста – отклонить или не отклонить нулевую гипотезу, можно отсортировать записанные разности и затем проверить, содержится ли в середине % этих разностей для некоторого уровня значимости. Если это не так, мы отвергаем гипотезу об идентичных кривых вероятности на уровне значимости . Для парных выборок необходимо применить парный перестановочный тест.
The test proceeds as follows. First, the difference in means between the two samples is calculated: this is the observed value of the test statistic,
Next, the observations of groups and are pooled, and the difference in sample means is calculated and recorded for every possible way of dividing the pooled values into two groups of size and (i. e., for every permutation of the group labels A and B). The set of these calculated differences is the exact distribution of possible differences (for this sample) under the null hypothesis that group labels are exchangeable (i. e., are randomly assigned). The one sided p value of the test is calculated as the proportion of sampled permutations where the difference in means was greater than The two sided p value of the test is calculated as the proportion of sampled permutations where the absolute difference was greater than Many implementations of permutation tests require that the observed data itself be counted as one of the permutations so that the permutation p value will never be zero. Alternatively, if the only purpose of the test is to reject or not reject the null hypothesis, one could sort the recorded differences, and then observe if is contained within the middle % of them, for some significance level If it is not, we reject the hypothesis of identical probability curves at the significance level. For paired samples the paired permutation test needs to be applied.
Преимущества
Для любой статистики существуют перестановкационные тесты, независимо от того, известно ли распределение этой статистики. Таким образом, всегда есть возможность выбрать статистику, которая наилучшим образом позволяет различить нулевую и альтернативную гипотезы и минимизировать потери. Перестановкационные тесты могут использоваться для анализа несбалансированных планов экспериментов и для объединения зависимых тестов на основе смешанных данных категориального, порядкового и количественного типов (Pesarin, 2001). Они также применимы для анализа качественных данных, преобразованных в числовую форму (то есть, квантизированных). Перестановкационные тесты могут быть особенно полезны для анализа квантизированных данных, которые не соответствуют статистическим предположениям, лежащим в основе традиционных параметрических тестов (например, t-тестов, ANOVA), см. PERMANOVA. До 1980-х годов создание эталонного распределения было непосильной задачей, за исключением наборов данных с небольшими объемами выборки. Начиная с 1980-х годов, сочетание относительно недорогих и быстрых компьютеров с разработкой новых, сложных алгоритмов, применимых в особых случаях, сделало применение методов перестановкационных тестов практичным для широкого круга задач. Это также привело к добавлению опций точных тестов в основные статистические программные пакеты и появлению специализированного программного обеспечения для проведения широкого спектра одномерных и многомерных точных тестов и вычисления "точных" доверительных интервалов, основанных на результатах тестов.
Ограничения
Важным предположением, лежащим в основе перестановочного теста, является то, что наблюдения взаимозаменяемы при нулевой гипотезе. Важным следствием этого предположения является то, что тесты на разницу в расположении (например, перестановочный t-тест) требуют равенства дисперсий при условии нормальности. В этом отношении классический перестановочный t-тест имеет ту же слабость, что и классический t-тест Стьюдента (проблема Беренса — Фишера). Эту проблему можно решить тем же способом, как классический t-тест был расширен для работы с неравными дисперсиями: путем использования статистики Уэлча с поправкой Саттертуэйта на число степеней свободы. Третьей альтернативой в этой ситуации является использование теста, основанного на бутстрэпе. Статистик Филипп Гуд объясняет разницу между перестановочными и бутстрэп-тестами следующим образом: «Перестановки проверяют гипотезы относительно распределений, а бутстрэп — гипотезы относительно параметров. В результате бутстрэп предполагает менее строгие условия». Бутстрэп-тесты не являются точными. В некоторых случаях перестановочный тест, основанный на корректно студентизированной статистике, может быть асимптотически точным, даже если предположение о взаимозаменяемости нарушено. Бутстрэп-тесты могут проверять гипотезы с нулевой гипотезой и, следовательно, подходят для проведения тестов на эквивалентность.
Испытания в Монте-Карло
Асимптотически эквивалентный перестановочный тест может быть создан, когда существует слишком много возможных упорядочений данных, чтобы позволить полное перечисление удобным способом. Это достигается путем генерации эталонного распределения с помощью метода Монте-Карло, который берет небольшую (относительно общего числа перестановок) случайную выборку из возможных повторений. Понимание того, что это можно применить к любому перестановочному тесту на любом наборе данных, стало важным прорывом в области прикладной статистики. Самые ранние известные упоминания об этом подходе встречаются у Эдена и Йейтса (1933) и Двасса (1957). Этот тип перестановочного теста известен под разными названиями: приближенный перестановочный тест, перестановочные тесты Монте-Карло или случайные перестановочные тесты. После случайных перестановок можно получить доверительный интервал для p-значения, основанный на биномиальном распределении, см. доверительный интервал для биномиальной пропорции. Например, если после случайных перестановок p-значение оценивается как , то 99% доверительный интервал для истинного (того, который был бы получен при попытке всех возможных перестановок) равен . С другой стороны, цель оценки p-значения чаще всего состоит в том, чтобы решить, где – порог, при котором нулевая гипотеза будет отвергнута (обычно ). В приведенном выше примере доверительный интервал говорит нам лишь о том, что вероятность того, что p-значение меньше 0,05, составляет примерно 50%, то есть совершенно неясно, следует ли отвергать нулевую гипотезу на уровне . Если важно знать, является ли для заданного , логично продолжать моделирование до тех пор, пока утверждение не будет установлено как истинное или ложное с очень низкой вероятностью ошибки. Учитывая ограничение на допустимую вероятность ошибки (вероятность того, что когда на самом деле или наоборот), вопрос о том, сколько перестановок генерировать, можно рассматривать как вопрос о том, когда прекратить генерацию перестановок, основываясь на результатах моделирования на данный момент, чтобы гарантировать, что заключение (которое является либо или ) верно с вероятностью не менее (обычно выбирается крайне малым значением, например, 1/1000). Для достижения этой цели разработаны правила остановки, которые могут быть включены с минимальными дополнительными вычислительными затратами. Фактически, в зависимости от истинного p-значения часто обнаруживается, что количество необходимых симуляций удивительно мало (например, всего 5 и часто не более 100), прежде чем можно будет принять решение с практически полной уверенностью.
On the other hand, the purpose of estimating the p value is most often to decide whether , where is the threshold at which the null hypothesis will be rejected (typically ). In the example above, the confidence interval only tells us that there is roughly a 50% chance that the p value is smaller than 0.05, i. e. it is completely unclear whether the null hypothesis should be rejected at a level
If it is only important to know whether for a given , it is logical to continue simulating until the statement can be established to be true or false with a very low probability of error. Given a bound on the admissible probability of error (the probability of finding that when in fact or vice versa), the question of how many permutations to generate can be seen as the question of when to stop generating permutations, based on the outcomes of the simulations so far, in order to guarantee that the conclusion (which is either or ) is correct with probability at least as large as ( will typically be chosen to be extremely small, e. g. 1/1000.) Stopping rules to achieve this have been developed which can be incorporated with minimal additional computational cost. In fact, depending on the true underlying p value it will often be found that the number of simulations required is remarkably small (e. g. as low as 5 and often not larger than 100) before a decision can be reached with virtual certainty.