ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

Recursive algorithm for exact calculation of rank tests for testing statistical hypotheses

Date of submission article: 09.09.2016
UDC: 620.1
The article was published in issue no. № 2, 2017 [ pp. 257-260 ]
Abstract:The paper considers the method of generating exact distributions of nonparametric rank tests by means of the computer combinatorial theory. Relevance of the work consists in the fact that determination of exact distribution of critical values of rank tests for statistical hypotheses testing is complicated by the fact that the exact tables and recurrence formulas for many of the tests do not exist. In addi-tion, approximations often give unsatisfactory results at limited volumes of observations. The task of calculating the distribution for rank tests is a search of all possible sample permutations and calculations of rank sta-tistics, as well as cumulative frequency of their occurrence. The program of generating permutations of elements of samples for nonparametric rank criteria based on the recursive brute-force algorithm of direct enumeration of order statistics vector permutation is developed with the following limited number of op-tions: in all permutation options the elements from the same sample cannot be swapped. It is a universal condition for all the rank criteria exact distributions. The paper refers to the Internet resource that contains the software package implementation of the considered calculation algo-rithm for a rank test. This complex contains four nonparametric criteria: two-sample Wilcoxon test, Lehmann-Rosenblatt test, series test and Kruskal-Wallis test, whose accurate distribution statistics are of greatest interest for technical problems. The algorithm can be used for other rank tests of statistical hypotheses testing. The paper presents an implementation of the generation method of nonparametric rank test exact distributions by computer com-binatorial means. It is based on the developed by the authors recursive direct enumeration of options of order statistics vector permu-tation with following filtration of the results. Thus, the authors solve the problem of determining the critical values of nonparametric rank tests for testing statistical hypotheses.
Аннотация:В статье рассматривается методика генерации точных распределений ранговых непараметрических критериев средствами компьютерной комбинаторики. Актуальность работы обусловлена затруднениями в определении точных распределений критических значений ранговых критериев проверки статистических гипотез из-за того, что точные таблицы, рекуррентные формулы для многих критериев не существуют, а аппроксимации часто дают неудовлетворительный результат при ограниченных объемах наблюдений. Задача расчета распределения ранговых критериев заключается в переборе всех возможных вариантов перестановок выборок и в расчете ранговых статистик, а также накопленных частот их появления. Для ее решения разработана программа генерации перестановок элементов выборок ранговых непараметрических критериев, основанная на рекурсивном алгоритме прямого перебора вариантов перестановок вектора порядковых статистик со следующим ограничением числа вариантов: во всех вариантах перестановок элементы одной и той же выборки не могут меняться местами, что является универсальным условием для всех точных распределений ранговых критериев. В работе приводится ссылка на интернет-ресурс, содержащий программный комплекс реализации алгоритма расчета ранговых критериев. В данном комплексе рассмотрены четыре непараметрических критерия: двухвыборочный критерий Уилкоксона, критерий Лемана–Розенблатта, критерий серий и критерий Краскела–Уоллиса, точные распределения статистик которых представляют наибольший интерес для технических задач. Рассматриваемый алгоритм может быть использован и для других ранговых критериев проверки статистических гипотез. В работе представлена разработанная авторами реализация метода генерации точных распределений ранговых непараметрических критериев средствами компьютерной комбинаторики, основанная на рекурсивном прямом переборе вариантов перестановок вектора порядковых статистик с последующей фильтрацией результатов. Таким образом, решена задача определения критических значений ранговых непараметрических критериев для проверки статистических гипотез.
Authors: Agamirov L.V. (mmk@mati.ru) - MATI (Russian National Research University), Moscow, Russia, Ph.D, Vestyak V.A. (kaf311@mai.ru) - Moscow Aviation Institute (National Research University, Moscow, Russia, Ph.D, Agamirov V.L. (avl095@mail.ru) - Moscow Aviation Institute (National Research University, Moscow, Russia, Ph.D
Keywords: nonparametric rank tests, hypothesis testing, exact distribution, combinatorics, algorithm, software, javascript
Page views: 11392
PDF version article
Full issue in PDF (17.16Mb)
Download the cover in PDF (0.28Мб)

Font size:       Font:

Задача проверки статистических гипотез во всех случаях сопряжена с необходимостью определения критических значений критериев. В то же время для большинства ранговых критериев определение точных распределений является весьма непростой задачей как с математической, так и с вычислительной точки зрения. Различного рода аппроксимации зачастую дают неудовлетвори- тельный результат при ограниченных объемах наблюдений, свойственных анализу данных в технических задачах, связанных со значительным рассеянием свойств, вследствие структурной неоднородности конструкционных материалов и большой вариативности внешних факторов при проведении испытаний. Точные таблицы, рекуррентные формулы, производящие функции частот и моментов для многих критериев не существуют [1–4]. Кроме того, при современном развитии вычислительной техники более предпочтительным является точный компьютерный расчет. Подробнее эти вопросы обсуждаются в [5], в данной работе предлагается методика генерации точных распределений ранговых непараметрических критериев средствами компь- ютерной комбинаторики.

С вычислительной точки зрения распределение ранговых критериев представляет собой перебор всех возможных вариантов перестановок элементов выборочных совокупностей при некоторых граничных условиях с последующим расчетом ранговых статистик и накопленных частот их появления. Предлагаемый далее алгоритм применим для большинства критериев, для которых вычисляются выборочные ранговые статистики. Для некоторых критериев существуют более эффективные методы [5, 6], однако с целью обобщения здесь рассматриваются различные критерии независимо от наличия иных методов расчета точных распределений. Авторы сознают, что предлагаемый алгоритм имеет недостаток – перебор большого числа лишних вариантов, что зачастую, особенно при более чем двух выборках, ведет к существенному увеличению машинного времени. Так что, данный алгоритм может рассматриваться как некоторый шаг в направлении применения методов рекурсивной компьютерной комбинаторики в задачах статистического анализа. К тому же при постоянном увеличении производительности процессоров современных компьютеров проблема машинного времени постепенно отступает на второй план.

В рассматриваемой ниже программе, написанной на языке Javascript, используется метод генерации перестановок элементов выборок ранговых непараметрических критериев. Метод основан на рекурсивном прямом переборе вариантов перестановок вектора порядковых статистик объема n с последующей фильтрацией результатов с учетом универсального для всех точных распределений ранговых критериев условия: внутри данной выборки порядковые номера элементов должны сохраняться независимо от места их расположения. Естественно, что за пределами выборки порядковые номера элементов должны принимать все возможные варианты перестановок.

Для примера рассмотрим возможные варианты таких перестановок для трех выборок (k=3) объемами n1 = 1, n2 = 1, n3 = 2.

При суммарном объеме выборок  безусловное число вариантов перестановок элементов равно N!, то есть 24. С учетом указанного выше условия число таких вариантов сокращается до 12: .                           

В таблице перечислены эти варианты, выборки обозначены символами X, Y, Z.

Варианты перестановок рангов трех выборок объемами n1=1, n2=1, n3=2

Permutations of ranks of 3 samples with a volume of n1=1, n2=1, n3=2

Номер варианта

Перестановка

Вектор a

Вектор aindex

1

X1 Y1 Z1 Z2

1 2 3 4

1 2 3 3

2

X1 Z1 Y1 Z2

1 3 2 4

1 3 2 3

3

X1 Z1 Z2 Y1

1 3 4 2

1 3 3 2

4

Y1 X1 Z1 Z2

2 1 3 4

2 1 3 3

5

Y1 Z1 X1 Z2

2 3 1 4

2 3 1 3

6

Y1 Z1 Z2 X1

2 3 4 1

2 3 3 1

7

Z1 X1 Y2 Z2

3 1 2 4

3 1 2 3

8

Z1 X1 Z2 Y1

3 1 4 2

3 1 3 2

9

Z1 Y1 X1 Z2

3 2 1 4

3 2 1 3

10

Z1 Y1 Z2 X1

3 2 4 1

3 2 3 1

11

Z1 Z2 X1 Y1

3 4 1 2

3 3 1 2

12

Z1 Z2 Y1 X1

3 4 2 1

3 3 2 1

Отметим еще раз, что номера 3 и 4, обозначающие элементы третьей выборки объемом 2, во всех вариантах сохраняют порядок, что и является условием генерации точного распределения для любого рангового критерия, в то время как порядковые номера первой и второй выборок, имеющих единич- ные объемы, могут меняться местами.

Далее приведена программа генерации перестановок при наличии граничных условий.

1.

2. 56.

Программа содержит три основные функции. Первая функция – stat_crit (строки 6–20) формирует исходные данные рассмотренного выше примера и два вспомогательных вектора a и aindex размерности N, первый из которых представляет собой вектор порядковых номеров объединенной выборки, второй – вектор, содержащий номера выборок, как это показано в таблице.

Вторая функция – omega(a, aindex, n, n) (строки 23–35) является рекурсивной функцией генерации перестановок элементов от 1 до n, в строке 32 которой представлена процедура рекурсии с уменьшением на единицу объема объединенной выборки от n до 1. В этом случае (строка 26) реализуется фильтрация перестановок в соответствии с принятыми граничными условиями, для чего введена третья функция – filter(fltr, n, a, aindex) (строки 36–54). Отметим, что фильтрация производится при значении параметра fltr=true (строка 38), в противном случае выводятся все варианты перестановок. На выходе этой функции выводятся элементы вектора a с учетом граничных условий, как показано в таблице.

Все остальные действия, необходимые для расчета статистик ранговых критериев, являются достаточно тривиальной вычислительной задачей и в данной работе не обсуждаются.

Полная версия программы с открытым кодом размещена на Javascript по ссылке http://inteh.mpei.ru/programs/stat/Menu/stat_tree.html. В данном комплексе рассмотрены четыре непараметрических критерия: двухвыборочный критерий Уилкоксона [1–4], критерий серий [7], критерий Лемана–Розенблатта [8] и критерий Краскела–Уоллиса [3, 4], точные распределения статистик которых, по мнению авторов, представляют наибольший интерес, по крайней мере, для технических задач. Очевидно, что представленный алгоритм может быть использован и для других ранговых критериев проверки статистических гипотез.

Для полноты картины рассмотрим указанные критерии, за исключением критерия серий, распределение статистики которого не требует вычисления рангов, а может быть подсчитано [7, 9] более простым способом, что и реализовано в полной версии программного комплекса.

Двухвыборочный критерий Уилкоксона предназначен для проверки гипотезы об отсутствии сдвига двух независимых выборок, то есть об отсутствии различия между медианами двух совокупностей при одинаковом, но произвольном рас- пределении [1, 2]. Пусть x1, x2, …, xm – случайная выборка из F(x–qx), y1, y2, …, yn  – случайная вы- борка из F(y–qy) (m ≤ n). Функцию распределения F не предполагают симметричной, но форма распределения должна быть одинаковой для двух совокупностей. Для проверки нулевой гипотезы о том, что обе выборки извлечены из одной и той же совокупности H0: D= qy – qx = 0 против альтернативы HA: D ¹ 0 строят вариационный ряд из k = m + n наблюдений и присваивают им ранги, равные по- рядковому номеру наблюдения в общем вариационном ряду. Далее рассчитывают сумму рангов меньшей выборки в общем вариационном ряду:

.                                                     

Для проверки нулевой гипотезы H0: D = 0 при альтернативной гипотезе HA: D < 0 должно выполняться неравенство W > Wal. При альтернативной гипотезе HA: D > 0 должно выполняться неравенство W ≤ Wau. При двусторонней альтернативной гипотезе HA: D ¹ 0 должно выполняться неравенство Wal ≤ W ≤ Wau  с уровнем значимости 2a.

Критерий Лемана–Розенблатта проверяет гипотезу об однородности двух выборок. Проверяется нулевая гипотеза о том, что две выборки извлечены из одной и той же генеральной совокупности, то есть H0: F(x) = G(x) при любом x. Статистика критерия рассчитывается по формуле

,

где Ri, Sj – ранги первой выборки объемом n и второй объемом m в общем вариационном ряду. Нулевую гипотезу принимают, если с уровнем значимости a. В противном случае принимают альтернативную гипотезу.

Критерий Краскела–Уоллиса обобщает задачу о двух выборках на случай k выборок: xij, i = 1, …, k, j = 1, …, nj, с функциями распределения F(x – qj), где nj – число наблюдений в j-й выборке. Нулевая гипотеза утверждает, что  выборок из произвольных совокупностей можно рассматривать как одну (объединенную) выборку из общей совокупности, то есть подтверждается равенство параметров сдвига qj, когда не задано значение общего параметра масштаба H0: q1 = q2 = … = qk против альтернативы HA: q1, …, qk не все равны. Для проверки нулевой гипотезы строят общий вариационный ряд из  наблюдений и рассчитывают статистику:

,                           

где Ri – сумма рангов i-й выборки в общем вариа- ционном ряду.

Нулевую гипотезу принимают, если H ≤ Ha с уровнем значимости a. В противном случае прини- мают альтернативную гипотезу.

Другим способом проверки выборочной гипотезы k является попарное сравнение выборок по критерию Уилкоксона с вычислением точных критических значений.

Таким образом, разработанный алгоритм, являющийся реализацией метода рекурсивной компью- терной комбинаторики, может быть использован для решения задачи проверки статистических гипотез, связанной с определением критических значений критериев. Учитывая, что для большинства ранговых критериев определение точных распределений является сложной задачей с математической и вычислительной точек зрения, представленная в работе методика генерации точных распределений критериев средствами компьютерной комбинаторики является эффективным решением.

Литература

1.     Кендалл М.Дж., Стьюарт А. Теория распределений. М.: Наука, 1966.

2.     Кендалл М.Дж., Стьюарт А. Статистические выводы и связи. М.: Наука, 1973. 899 с.

3.     Хеттманспергер Т. Статистические выводы, основанные на рангах. М.: Финансы и статистика, 1987. 334 с.

4.     Холлендер М., Вулф Д. Непараметрические методы статистики. М.: Финансы и статистика, 1983. 518 с.

5.     Агамиров Л.В., Агамиров В.Л., Вестяк В.А. Численные методы и алгоритмы расчета точных распределений непараметрических критериев проверки статистических гипотез // Вестн. МАИ. 2013. Т. 20. № 4. С. 212–218.

6.     Агамиров Л.В. Методы статистического анализа механических испытаний. М.: Интермет Инжиниринг, 2004. 127 с.

7.     Шуленин В.П. Математическая статистика. Ч. 2: Непараметрическая статистика. Томск: Изд-во НТЛ, 2012. 388 с.

8.     Леман Э. Проверка статистических гипотез.  М.: Наука, 1964.  498 с.

9.     Липский В. Комбинаторика для программистов. М.: Мир, 1988. 200 с.


Permanent link:
http://swsys.ru/index.php?page=article&id=4280&lang=&lang=en&like=1
PDF version article
Full issue in PDF (17.16Mb)
Download the cover in PDF (0.28Мб)
The article was published in issue no. № 2, 2017 [ pp. 257-260 ]

Perhaps, you might be interested in the following articles of similar topics: