Редукция размерности категориальных данных на основе точного критерия Фишера

Куликов Даниил Владимирович

Редукция размерности категориальных данных на основе точного критерия Фишера

Куликов Даниил Владимирович. Редукция размерности категориальных данных на основе точного критерия Фишера. Научный руководитель: к.ф.-м.н., доцент Н. П. Алексеева. Прикладная математика и информатика, вычислительная стохастика и статистические модели. В работе реализованы программы вычисления точного критерия Фишера для таблиц сопряженности большой размерности и выявления информативных признаков, проведено сравнение с известными аналогами. Предложены различные алгоритмы генерации кодов Грея. Создан новый алгоритм перечисления всевозможных точек грассманиана. С использованием реализованных программ сделан вывод о важности и взаимодействии факторов на примере данных о заболеваниях кишечника. Использовано источников: 15 Куликов, Д. В. Редукция размерности категориальных данных на основе точного критерия Фишера: бакалаврская работа: защищена 09.06.2016 / Куликов Даниил Владимирович. – СПб., 2016. – 48 с. – Библиогр.: с. 47–48.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36635f1be77c40d58e42

UUID: ed298653-decf-4b85-b689-3c11e5369eb4

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 33

Куликов Даниил Владимирович

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 518797 bytes

Поделиться работой

Санкт-Петербургский государственный университет Прикладная математика и информатика Вычислительная стохастика и статистические модели Куликов Даниил Владимирович Редукция размерности категориальных данных на основе точного критерия Фишера Бакалаврская работа Научный руководитель: к. ф.-м. н., доцент Н. П. Алексеева Рецензент: к. т. н., ст. науч. сотр. Л. А. Белякова Санкт-Петербург 2016

Saint Petersburg State University Department of Statistical Modelling Kulikov Daniil Vladimirovich Dimension reduction of categorical data based on Fisher’s exact test Bachelor’s Thesis Scientific Supervisor: Candidate of Physico-Mathematical Sciences, Associate Professor N. P. Alekseeva Reviewer: Candidate of Engineering Sciences, Senior Researcher L. A. Belyakova Saint Petersburg 2016

Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Глава 1. Критерий Фишера и виды 𝑝-значений . . . . . . . . . . . . . . . 5 1.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Множество элементарных исходов и статистический критерий . . . . . . 7 1.3. Точные двусторонние p-значения . . . . . . . . . . . . . . . . . . . . . . . 8 1.4. Двусторонние p-значения Monte Carlo . . . . . . . . . . . . . . . . . . . . 9 1.5. Асимптотические двусторонние p-значения . . . . . . . . . . . . . . . . . 11 Неупорядоченные 𝑟 × 𝑐 таблицы сопряженности . . . . . . . . . 12 2.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Таблица-пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3. Точный тест Фишера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4. Альтернативная программа . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5. Сравнение результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6. Сравнение с fisher.test() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Глава 2. Глава 3. Определение информативных признаков . . . . . . . . . . . . . 20 3.1. Алгоритм быстрого перечисления точек грассманиана . . . . . . . . . . . 20 3.2. Алгоритм перечисления точек грассманиана с использованием диаграмм 3.3. Юнга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Применение программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Глава 4. О параметризации грассманиана . . . . . . . . . . . . . . . . . . . 37 4.1. Связь грассманиана с симптомом и синдромом . . . . . . . . . . . . . . . 37 4.2. Параметризация на основе рекуррентных соотношений . . . . . . . . . . 37 Глава 5. Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Применение точного критерия Фишера . . . . . . . . . . . . . . . . . . . 41 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.1. 2

Введение В современном мире часто приходится сталкиваться с большим объемом данных и, в связи с этим, с возникающим вопросом об их влиянии на какой-то интересующий нас объект из этих данных. Так, например, любую историю болезни пациента можно пред ставить в виде большого набора категориальных признаков, каждый из которых может означать симптомы болезни, применяемое лечение или последующие осложнения, тогда хочется выяснить, какое лечение при известных начальных симптомах может привести к наименее тяжелым осложнениям или даже к их полному отсутствию. Для решения этой проблемы применяется редукция размерности этих категориальных данных и вы явление в них наиболее информативных признаков. В данной работе в качестве меры зависимости признаков будет рассмотрен точный критерий Фишера для данных боль шой размерности и его применение для решения поставленной задачи. Цель работы. Реализация программы вычисления точного критерия Фишера и редук ции размерности категориальных данных, сравнение с известными аналогами, реализа ция нового алгоритма перечисления точек грассманиана, вывод о важности и взаимо действии факторов на практическом примере. Методы исследования. Для выявления зависимостей использовался точный крите рий Фишера для таблиц сопряженности размером 𝑟 × 𝑐. Проведена редукция размер ности категориальных данных, написаны соответствующие программы на языках R и Matlab и применены на конкретных примерах. Структура работы. Работа состоит из введения, 5 глав, заключения и библиографии. В первой главе рассматриваются основные понятия и различные виды 𝑝-значений, которые были применены при составлении соответствующей программы. Во второй главе представляются методы реализации точного критерия Фишера для таблиц большой размерности, приводится принцип действия собственной программы, сравнивается результат её действия с известными аналогами и производится вывод о факторах, значимо влиящих на рецидивы болезни. В третьей главе описывается алгоритм быстрого перечисления точек грассманиана и программа, составленная на базе этого алгоритма. Программа тестируется на реаль ных данных и, основываясь на результатах выполнения программы, делается вывод о факторах послеоперационных осложнений. Также реализуется собственный алгоритм 3

перечисления точек грассманиана, основанный на составлении диаграмм Юнга и их сопоставлении матрицам клеточной формы. В четвертой главе вводятся понятия симптома, синдрома и грассманиана, выводится их взаимосвязь. Представляется изучение возможности использования cпособа выращи вания конечных подпространств на основе рекуррентных соотношений типа Фибоначчи с помощью интегрирования дизайнов. Проверяется согласованность с флагом для тако го типа параметризации грассманиана. В пятой главе представлены и обоснованы результаты применения собственных про грамм, основанных на методах, исследованных в бакалаврской работе. 4

Глава 1 Критерий Фишера и виды 𝑝-значений 1.1. Основные понятия Определение 1.1.1. Таблица сопряжённости — таблица,в которой представляется сов местное распределение двух и более переменных, используемое для исследования связи между ними. Определение 1.1.2. Точный критерий Фишера — тест статистической значимости, обычно используемый в анализе таблиц сопряжённости для исследования значимости взаимосвязи между переменными. Для вычисления точного 𝑝-значения рассматриваемой 𝑟 × 𝑐 таблицы сопряженно сти нужно выполнить следующее: 1. Определим множество элементарных исходов в виде 𝑟 × 𝑐 таблиц, в которой таб лицы имеют известную вероятность относительно нулевой гипотезы о независимо сти. 2. Упорядочим таблицы из множества элементарных исходов согласно мере отклоне ния (или статистическому критерию), определяющему степень отклонения каж дой таблицы от нулевой гипотезы. 3. Суммируем вероятности таблиц из множества элементарных исходов, которые от клоняются не больше, чем данная. Сложность его реализации состоит в том, что размер множества элементарных исхо дов растет экспоненциально с ростом размерности таблицы. Одним из решений этой проблемы был предложен алгоритм, описанный в статье [1]. Будем рассматривать статистические данные, которые записываются в таблицу сопряженности размером 𝑟 × 𝑐, где 𝑟 — количество строк, а 𝑐 — количество столбцов. Нас интересуют категориальные признаки, то есть признаки, которые не могут быть представлены в некотором интуитивном порядке или записаны числами. Таким обра зом, получим таблицу сопряженности, в которой записаны категориальные данные как 5

по строкам, так и по столбцам. Рассмотрим таблицу, в которой 𝑥𝑖𝑗 будет обозначать количество данных исследования, попадающих под категорию строки 𝑖 и столбца 𝑗. Таблица 1.1. Общий вид Rows/Cols 𝐶𝑜𝑙1 𝐶𝑜𝑙2 ··· 𝐶𝑜𝑙𝑐 RowTotal 𝑅𝑜𝑤1 𝑥11 𝑥12 ··· 𝑥1𝑐 𝑚1 𝑅𝑜𝑤2 𝑥21 𝑥22 ··· 𝑥2𝑐 𝑚2 · · · · 𝑅𝑜𝑤𝑟 𝑥𝑟1 𝑥𝑟2 ··· 𝑥𝑟𝑐 𝑚𝑟 ColTotal 𝑛1 𝑛2 ··· 𝑛𝑐 N · · Основная задача — узнать, верна ли нулевая гипотеза о независимости признаков в данной таблице сопряженности, для этого будем вычислять 𝑝-значение. Exact Tests в SPSS Statistics обеспечивают тремя видами 𝑝-значения для каждого теста. "Золо тым стандартом"является точное 𝑝-значение. К сожалению, его вычисление не всегда оптимально, поскольку для большого объема данных оно будет долгим. В таком слу чае, используют 𝑝-значение Monte Carlo, оно является очень близким приближением к точному 𝑝-значению и задает границы, в котором оно лежит. А для больших, хорошо сбалансированных объемов данных асимптотическое 𝑝-значение не сильно отличается от точного, но для проверки этого факта придется вычислить 𝑝-значение другого типа. Для вычисления точного 𝑝-значения рассматриваемой 𝑟 × 𝑐 таблицы сопряженно сти, нужно выполнить следующие пункты: 1. Определим множество элементарных исходов в виде 𝑟 × 𝑐 таблиц, в которой таб лицы имеют известную вероятность относительно нулевой гипотезы о независимо сти. 2. Упорядочим таблицы из множества элементарных исходов согласно мере отклоне ния (или статистическому критерию), определяющему степень отклонения каж дой таблицы от нулевой гипотезы. 3. Суммируем вероятности таблиц из множества элементарных исходов, которые от клоняются не больше, чем данная. Рассмотрим каждый пункт по отдельности. 6

1.2. Множество элементарных исходов и статистический критерий Будем обозначать за 𝑥 рассматриваемую таблицу сопряженности 𝑟 × 𝑐 и за 𝑥 — любую сгенерированную таблицу из множества элементарных исходов, которая может быть рассмотрена. Точная вероятность наблюдения такой сгенерированной таблицы 𝑥 зависит от используемой модели распределения. Когда и строки, и столбцы содержат только категориальные признаки, в руководстве [2] приводятся следующие три распре деления: полное полиномиальное распределение, ординальное полиномиальное распре деление и распределение Пуассона. Со всеми этими моделями вероятность получения 𝑥 зависит от неизвестных параметров, принадлежащих клеткам 𝑟 × 𝑐 таблицы. Клю чом к точному непараметрическому выводу является устранение всех неподходящих параметров из распределения 𝑥. Это достигается простым ограничением множества: берем в него только те таблицы, у которых маргинальные суммы совпадают с данной. В частности, определим множество элементарных исходов как {︂ Γ= 𝑥 : 𝑥 𝑖𝑠 𝑟 × 𝑐; 𝑐 ∑︁ 𝑥𝑖𝑗 = 𝑚𝑖 ; 𝑗=1 𝑟 ∑︁ }︂ 𝑥𝑖𝑗 = 𝑛𝑗 ∀𝑖, 𝑗 . (1.1) 𝑖=1 Затем определим, что вероятность получения 𝑥 ∈ Γ относительно нулевой гипоте зы о независимости ∏︀𝑐 𝑛𝑗 ! ∏︀𝑐 ∏︀𝑟𝑗=1 𝑃 (𝑥) = , 𝑁 ! 𝑗=1 𝑖=1 𝑥𝑖𝑗 ! ∏︀𝑟 𝑖=1 где 𝑁 = ∑︀𝑟 𝑖=1 𝑚𝑖 = ∑︀𝑐 𝑗=1 𝑚𝑖 ! (1.2) 𝑛𝑗 . Формула (1.2), не содержащая неизвестных параметров, выполняется при всех трех моделях распределения. Множество элементарных исходов Γ в некотором роде является пространством наших действий по генерации таблиц. Это множество растет с огромной скоростью, поэтому часто предлагаются алгоритмы, решающие проблему его генерации, такие, как в статье [3] и статье [4]. В ординальном полиномиальном распределении суммы по строкам фиксированы, тогда как суммы по столбцам могут варьироваться в разных моделях. В полном полиномиальном распределении и распределении Пуассона могут варьироваться значения сумм как по строкам, так и по столбцам. Для статистического анализа каждая таблица 𝑥 ∈ Γ упорядочивается по статистиче скому критерию или мере отклонения, которая количественно определяет степень от 7

клонения таблицы от нулевой гипотезы независимости строк и столбцов. Статистиче ский критерий будет обозначаться за 𝐷(𝑥). Большие абсолютные значения 𝐷(𝑥) будут опровергать нулевую гипотезу, тогда как малые наоборот будут с ней согласовываться. Функциональная форма 𝐷(𝑥) непосредственно для каждого типа критерия будет далее приведена. В течение этого раздела, функция 𝐷(𝑥) будет определяться как общий ста тистический критерий. Конкретные случаи статистического критерия будем обозначать их собственными уникальными символами. Например, для критерия хи-квадрат Пир сона, общий символ 𝐷(𝑥) заменим на 𝐶𝐻(𝑥). Эту форму легко получить из следующих соображений: критерий хи-квадрат независимости сравнивает наблюдаемые значения в таблице с ожидаемыми значениями этих величин при нулевом распределении. Этот статистический критерий измеряет расхождение между наблюдаемыми и ожидаемыми значениями. Если расхождение больше, чем ожидалось, то считаем доказанным оши бочность нулевой гипотезы о независимости. Статистический критерий хи-квадрат Пирсона имеет вид: 𝐶𝐻(𝑥) = ∑︁ ∑︁ (𝑥𝑖𝑗 − 𝐸𝑖𝑗 )2 , 𝐸 𝑖𝑗 𝑖 𝑗 где 𝐸𝑖𝑗 — ожидаемое значение в строке 𝑖 и столбце 𝑗, то есть 𝐸𝑖𝑗 = 𝑚𝑖 𝑛𝑗 /𝑁 , а следова тельно: 𝑟 ∑︁ 𝑐 ∑︁ (𝑥𝑖𝑗 − 𝑚𝑖 𝑛𝑗 /𝑁 )2 𝐶𝐻(𝑥) = . 𝑚𝑖 𝑛𝑗 /𝑁 𝑖=1 𝑗=1 (1.3) 1.3. Точные двусторонние p-значения Точное двустороннее 𝑝-значение определяется как сумма вероятностей всех таб лиц в Γ, которые, по крайней мере, так же далеки, как и наблюдаемая таблица 𝑥 по отношению к 𝐷. В частности, 𝑝2 = ∑︁ 𝑃 (𝑦) = 𝑝𝑟[𝐷(𝑦) ≥ 𝐷(𝑥)]. (1.4) 𝐷(𝑦)≥𝐷(𝑥) Для дальнейшего использования, определим критическую область множества элемен тарных исходов: Γ* = 𝑦 ∈ Γ : 𝐷(𝑦) ≥ 𝐷(𝑥). (1.5) Вычисление уравнения (1.4) иногда довольно трудно, так как размер множества эле ментарных исходов Γ растет экспоненциально. Например, множество всех таблиц 5 × 6 8

с суммами по строкам (7, 7, 12, 4, 4) и суммами по столбцам (4, 5, 6, 5, 7, 7) содержит 1,6 миллиардов таблиц. Тем не менее, таблицы этого множества элементарных исходов довольно редки и вряд ли уступают точному 𝑝-значению, основанному на теории боль ших выборок. SPSS Exact Tests используют сетевые алгоритмы, основанные на методах Мехта и Патель (1983, 1986a, 1986b) неявного перечисления таблиц в Γ и, таким обра зом, быстро идентифицирующие их в Γ* . Это делает возможным вычисление точных 𝑝-значений для многих, кажущихся неразрешимыми, наборов данных, таких, как выше. Несмотря на наличие сетевых алгоритмов, набор данных иногда слишком большой для возможности вычисления точного 𝑝-значения. Но он может быть слишком редким для достаточной надежности асимптотического значения. В этой ситуации Exact Tests используют вариант Монте-Карло, где выбирается только небольшая часть из таблиц в Γ и получается объективная оценка точного 𝑝-значения. 1.4. Двусторонние p-значения Monte Carlo Двустороннее 𝑝-значение Монте-Карло является очень хорошим приближением к точному двустороннему 𝑝-значению, но его гораздо проще вычислить. Результаты мето да Монте-Карло могут быть использованы вместо точных результатов, когда последние слишком сложно вычислить. Метод Монте-Карло является устойчивой, надежной про цедурой, которая, в отличие от точного подхода, всегда занимает предсказуемое коли чество машинного времени. Хоть метод и не дает точного 𝑝-значения, но зато приводит довольно малый доверительный интервал, в границах которого, с высокой степенью значимости (обычно 99%), и содержится точное 𝑝-значение. В методе Монте-Карло множество таблиц, мощность которого равна некоторому 𝑀 , выбирается из множества Γ, где каждая таблица выбирается пропорционально её гипергеометрической вероятности (см. уравнение (1.2)). (Выборка таблиц пропорцио нально их вероятностям называется сырой выборкой по методу Монте-Карло.) Для каждой выбранной таблицы 𝑦𝑗 ∈ Γ определим бинарный результат 𝑧𝑗 = 1, если 𝑦𝑗 ∈ Γ* , иначе 𝑧𝑗 = 0. Среднее арифметическое этих 𝑧𝑗 берется как точечная оценка Монте-Карло точного двустороннего 𝑝-значения. 𝑀 1 ∑︁ 𝑝ˆ2 = 𝑧𝑗 . 𝑀 𝑗=1 9 (1.6)

Вычислить 𝛼% доверительный интервал в данном случае можно по следующей форму ле: √ 𝐶𝐼𝛼 = 𝑝ˆ2 ± 𝑍𝛼/2 𝜎 ˆ /( 𝑀 ), (1.7) где 𝑍𝛼/2 — коэффициент доверия, его значение возьмем из таблицы на сайте [5]. Пример 1.4.1. 99% доверительным интервалом для точного 𝑝-значения является √ 𝐶𝐼0.99 = 𝑝ˆ2 ± 2.576ˆ 𝜎 /( 𝑀 ). Техническая сложность возникает тогда, когда 𝑝ˆ2 = 1 или 𝑝ˆ2 = 0. Выборочное среднеквадратическое отклонение тогда равно нулю, а значит возникнет проблема, так как доверительный интервал должен будет быть нулевой ширины. Альтернативный способ вычисления доверительного интервала, не зависящий от 𝜎 ˆ , основан на обраще нии точного биномиального критерия для проверки гипотезы, когда встречается край ний исход. Теперь рассмотрим подробнее этот метод, получивший название Clopper Pearson, нахождения точного доверительного интервала. Точный доверительный ин тервал — это интервал от 𝑝𝑙𝑏 до 𝑝𝑢𝑏 , который удовлетворяет следующим условиям при 𝑥 = 1, 2, . . . , 𝑛 − 1: ⎛ ⎞ 𝑛 ⎝ ⎠ 𝑝𝑘𝑢𝑏 (1 − 𝑝𝑢𝑏 )𝑛−𝑘 = 𝛼/2, 𝑘 𝑘=0 ⎛ ⎞ 𝑛 ∑︁ 𝑛 ⎝ ⎠ 𝑝𝑘𝑙𝑏 (1 − 𝑝𝑙𝑏 )𝑛−𝑘 = 𝛼/2, 𝑘 𝑘=𝑥 где 𝑝𝑙𝑏 — нижняя граница интервала, 𝑝𝑢𝑏 — верхняя граница интервала, 𝑛 — количество 𝑥 ∑︁ измерений, 𝑘 — количество успехов. Нижняя граница равна 0, когда 𝑥 = 0, а верхняя равна 1, когда 𝑥 = 𝑛. Уравнения выше основаны на биномиальной функции распределения, для вычисления которой мы можем использовать бета-распределение или 𝐹 распределение. Используя формулы выше и опираясь на сайт [6] и руководство [2] получим, что если 𝑝ˆ2 = 0, то 𝛼% доверительным интервалом для точного 𝑝-значения является следующий промежуток: 𝐶𝐼 = [0, 1 − (1 − 𝛼/100)1/𝑀 ]. (1.8) Аналогичным образом, когда 𝑝ˆ2 = 1, то 𝛼% доверительным интервалом для точного 𝑝-значения является: 𝐶𝐼 = [(1 − 𝛼/100)1/𝑀 , 1]. 10 (1.9)

1.5. Асимптотические двусторонние p-значения Для всех критериев в этой главе статистический критерий 𝐷(𝑥) имеет асимпто тическое хи-квадрат распределение. Асимптотическое двустороннее 𝑝 - значение имеет вид: 𝑝˜2 = 𝑃 𝑟(χ2 ≥ 𝐷(𝑥)|𝑑𝑓 ), (1.10) где χ2 случайная величина с хи-квадрат распределением и 𝑑𝑓 — соответствующие сте пени свободы. Для тестов на неупорядоченных 𝑟 × 𝑐 таблицах сопряженности коли чество степеней свободы вычисляется следующим образом: имеем 𝑟𝑐 − 1 свободных параметров относительно гипотезы о зависимости и (𝑟 − 1) + (𝑐 − 1) свободных пара метров относительно гипотезы о независимости, следовательно степеней свободы будет 𝑟𝑐 − 1 − ((𝑟 − 1) + (𝑐 − 1)) = 𝑟𝑐 − 𝑟 − 𝑐 + 1 = (𝑟 − 1) × (𝑐 − 1). 11

Глава 2 Неупорядоченные 𝑟 × 𝑐 таблицы сопряженности В отличие от предыдущей главы, в этой главе будут рассматриваться только неупо рядоченные таблицы сопряженности, поэтому, прежде всего, стоит определить отличие неупорядоченных таблиц сопряженности от односторонне-упорядоченных и упорядо ченных таблиц. Оно состоит в том, что в таких таблицах и по строкам, и по столбцам содержатся данные, которые интуитивно не могут быть упорядочены, то есть данные, являющиеся категориальными признаками, например, пол пациента. В программе SPSS Statistics Exact Tests доступны три критерия для таких таблиц категориальных данных: критерий Хи-квадрат Пирсона, критерий отношения правдоподобия и точный критерий Фишера. Все они выполняются только для неупорядоченных таблиц сопряженности. Критерий хи-квадрат Пирсона уже был упомянут в разделе 1.2, а точный критерий Фишера будет разобран подробнее ниже, поэтому cкажем пару слов о критерии отно шения правдоподобия. Этот критерий является альтернативой критерию хи-квадрат Пирсона. Его статистический критерий вычисляется по следующей формуле: 𝐿𝐼(𝑥) = 2 𝑟 ∑︁ 𝑐 ∑︁ 𝑥𝑖𝑗 log 𝑖=1 𝑗=1 𝑥𝑖𝑗 . 𝑚𝑖 𝑛𝑗 /𝑁 Для данной формулы разница в количестве свободных параметров следующая: (𝑟𝑐 − 1) − (𝑟 + 𝑐 − 2) = 𝑟𝑐 − 𝑟 − 𝑐 + 1 = (𝑟 − 1)(𝑐 − 1). Рассчитав полученный статистический критерий, точное 𝑝-значение будет определяться через (1.4), а именно через выражение 𝑃 𝑟 (𝐿𝐼(𝑦) ≥ 𝐿𝐼(𝑥) | 𝑦 ∈ Γ). Следует отметить, что для приведенной ниже таблицы-примера точные 𝑝-значения по критериям Пирсона (0.027) и отношения правдоподобия (0.036) разнятся практически на 0.01, что являет ся довольно большой величиной, учитывая поставленную задачу подтверждения или опровержения нулевой гипотезы о независимости. Теперь перейдем к рассмотрению точного критерия Фишера. 2.1. Постановка задачи Предположим, что есть таблица сопряженности размера 𝑟 × 𝑐. За 𝑥𝑖𝑗 будем обозна чать количество данных исследования, попадающих под категорию строки 𝑖 и столбца 12

𝑗. Определим маргинальные суммы по строкам и по столбцам: 𝑚𝑖 = 𝑐 ∑︁ 𝑥𝑖𝑗 , 𝑖 = 1, 2, . . . , 𝑟, 𝑗=1 𝑛𝑗 = 𝑟 ∑︁ 𝑥𝑖𝑗 , 𝑗 = 1, 2, . . . , 𝑐. 𝑖=1 Нулевая гипотеза о независимости признаков: 𝐻𝑜 : 𝑥𝑖𝑗 = 𝑚𝑖 × 𝑛𝑗 , ∀(𝑖, 𝑗). Требуется её подтвердить или же опровергнуть, то есть объявить, что для какой-то пары (𝑖, 𝑗) нулевая гипотеза выполняться не будет (без указания какой именно пары). 2.2. Таблица-пример Для более полного понимания метода поясним его на простом примере. Предпо ложим, что были получены данные о расположении поражений ротовой полости после обследований в трех сельских районах Индии. Эти данные покажем здесь в виде табли цы сопряженности 9×3, как показано далее. Переменные, указанные в таблице: область (указывает конкретную область поражения ротовой полости) и регион (указывает гео графический положение, конкретный район). Нас интересует следующее: существенно ли отличается распределение поражений полости рта в трех географических регионах. Строки и столбцы этой таблицы — катего риальные данные, а значит можно применить все три критерия, в том числе и точный критерий Фишера. Данные в таблице сопряженности настолько редки, что обычное хи-квадрат асимптотическое распределение с 16 степенями свободы не даст точного 𝑝-значения. Теперь перейдем непосредственно к точному критерию Фишера. 2.3. Точный тест Фишера Обычно критерий Фишера ассоциируется с таблицами сопряженности размера 2 × 2. Его расширение до неупорядоченных 𝑟 × 𝑐 таблиц было впервые предложено Фрименом и Хальтоном (1951). Вот почему он также известен как критерий Freeman Halton. Этот критерий стал альтернативой критерия хи-квадрат Пирсона и критерия отношения правдоподобия для доказательства независимости строк и столбцов в неупо рядоченной таблице сопряженности большого размера. В программе SPSS Statistics 13

Таблица 2.1. Пример Географический регион Kerala Gujarat Andhra слизистая губы 1 слизистая щеки Область поражения 8 1 спайка губ 1 десна 1 твердое нёбо 1 мягкое нёбо 1 язык 1 8 диафрагма полости рта 1 1 альвеолярный отросток 1 1 асимптотические результаты доступны только для таблиц 2 × 2, однако точные значе ния и значения Монте-Карло доступны и для больших таблиц. Для любой исследуемой таблицы сопряженности статистический критерий 𝐷(𝑥) обозначим за 𝐹 𝐼(𝑥). Он вычис ляется по следующей формуле из руководства [2]: 𝐹 𝐼(𝑥) = −2 log(𝛾𝑃 (𝑥)), где (𝑟−1)(𝑐−1)/2 𝛾 = (2𝜋) 𝑁 −(𝑟𝑐−1)/2 𝑟 ∏︁ (2.1) (𝑐−1)/2 (𝑚𝑖 ) 𝑖=1 𝑐 ∏︁ (𝑛𝑗 )(𝑟−1)/2 . 𝑗=1 Разберем эту формулу на частном случае таблицы сопряженности 2 × 2: (︂ )︂ 𝑟 𝑐 ∏︁ ∏︁ 1/2 −3/2 1/2 1/2 𝐹 𝐼(𝑥) = −2 log (2𝜋) 𝑁 (𝑚𝑖 ) (𝑛𝑗 ) 𝑃 (𝑥) , 𝑖=1 𝑗=1 где ∏︀2 𝑃 (𝑥) = где 𝑁 = ∑︀2 𝑖=1 𝑚𝑖 = ∑︀2 𝑗=1 𝑖=1 𝑁! 𝑚𝑖 ! ∏︀2 𝑗=1 ∏︀2 𝑛𝑗 ! ∏︀2 𝑥𝑖𝑗 ! 𝑗=1 𝑖=1 , 𝑛𝑗 . Следовательно получаем следующий вид: (︂ 𝐹 𝐼(𝑥) = −2 log (2𝜋) 1/2 𝑁 −3/2 𝑟 ∏︁ 𝑖=1 14 1/2 (𝑚𝑖 ) 𝑐 ∏︁ 𝑗=1 (𝑛𝑗 ) 1/2 )︂ 𝑃 (𝑥) .

Если заменить гипергеометрическое распределение на вероятностное распределение multinominal(𝑁, 𝜋1,1 , . . . , 𝜋𝑟,𝑐 ), где каждая из 𝑁 независимых величин 𝜋𝑖,𝑗 — это веро ятность попадания этой величины в ячейку таблицы (𝑖, 𝑗). Получим, что вероятность наблюдения таблицы сопряженности из множества элементарных исходов — это: 𝑃 (𝑋) = 𝑐 𝑡 𝑟 ∏︁ 𝑐 ∏︁ 𝜋𝑖,𝑗𝑖,𝑗 𝑖=1 𝑗=1 где 𝑐 = 1/ 𝑡𝑖,𝑗 ! , 𝜏 𝑟 ∏︁ 𝑐 ∑︁ ∏︁ 𝜋𝑖,𝑗𝑖,𝑗 (𝜏𝑖,𝑗 ) 𝑖=1 𝑗=1 𝜏𝑖,𝑗 ! , где суммирование проводится по всем таблицам 𝜏𝑖,𝑗 из множества таблиц с теми же маргинальными значениями. Для вычисления этого значения можно работать с −2(log 𝑃 (𝑋)−log 𝑐), чтобы избежать излишних вычислений. После чего домножить полученное на вычисленное значение 𝑐. Вычислим теперь для таблицы-примера значение статистического критерия 𝐹 𝐼(𝑥). Сначала вычислим 𝑃 (𝑥) по формуле (1.2), оно будет равно 0,0000053. Далее выясним значение 𝛾 = 9, 73. Таким образом получим 𝐹 𝐼(𝑥) = 19, 72. Точное 𝑝-значение определяется через (1.4), а именно 𝑝𝑟[𝐹 𝐼(𝑦) ≥ 19.72 | 𝑦 ∈ Γ]. То есть генерируем множество таблиц, потом для каждой считаем значение статисти ческого критерия, и, если оно больше 19.72, то добавляем его к текущему 𝑝-значению. Точное 𝑝-значение равно 0,010, а значит существует значительное взаимодействие меж ду областью поражения и географическим положением. Иногда набор данных слишком велик для точного анализа, и вместо него дол жен быть использован метод Монте-Карло. Так, например, мы получим объективную оценку точного 𝑝-значения для точного критерия Фишера на основе сырой выборки по методу Монте-Карло при выборке 10000 таблиц из множества элементарных исходов. Генерируем множество мощности 10000, для каждой таблицы из этого множества счи таем значение статистического критерия, и, основываясь на нем, получаем множество Γ* . Далее вычисляем 𝑝ˆ2 , используя (1.6) и 𝜎 ˆ , используя (??). Вычислив эти значения, сможем рассчитать доверительный интервал через (1.7) или, в отдельных случаях, че рез (1.8) и (1.9). В данном примере нижняя граница будет равна 0.007, а верхняя гра ница — 0.013. Пусть метод Монте-Карло производит 99% доверительный интервал для точного 𝑝-значения. Таким образом, хоть эта точечная оценка может слегка измениться, если взять выборку с другой начальной точки или другой генератор случайных чисел, 15

мы можем быть на 99% уверены, что точное 𝑝-значение содержится в интервале от 0,007 до 0,013. Кроме того, мы всегда можем взять большее количество таблиц, чтобы уменьшить ширину этого интервала. Очевидно, что критерий по методу Монте-Карло приводит к такому же выводу, что и при точном критерии, и показывает, что существу ет значительная взаимосвязь строк и столбцов в этой таблице сопряженности. В данном примере асимптотический результат не сможет продемонстрировать значимости. 2.4. Альтернативная программа Казалось бы, что алгоритм понятен и прост, но (1.4) сложно вычислить при ро сте размера таблицы, так как размер множества элементарных исходов Γ будет расти экспоненциально. Для облегчения вычисления можно использовать сетевой алгоритм, описанный в статье [7], или алгоритм Pagano and Halvorsen, описанный в статье [8]. Однако я буду использовать алгоритмы, описанные в статьях [9] и [10], основанные на методе Monte Carlo и использовании теста 𝜒2 . Язык написания программы — Matlab R2013a. Для повышения вычислительной точности я составил отдельные программы для простых случаев таблиц, а именно: 2 × 2, 2 × 3, 2 × 4, 3 × 3. Позднее действие дан ной программы сравним с результатами, полученными с помощью SPSS Exact Tests на примере, приведенном ниже. Для использования программы в файле SetTable.m в единственной строке fisherRxC([...]) внутри квадратных скобок введем таблицу сопряженности по следующему правилу — вводим построчно элементы таблицы через пробел, строки разделяем точкой с запятой. Функция fisherRxC включает в себя частные случаи, имеющие отдельные функции, а именно: fisher2x2, fisher2x3, fisher2x4, fisher3x3. На выходе получим точное 𝑝-значение или 𝑝-значение Монте Карло. 2.5. Сравнение результатов Применим мою программу на некоторых сравнениях. Далее сравним полученные в моей программе точные 𝑝-значения со значениями в программе SPSS Statistics. Для более точной проверки будем брать таблицы сопряженности разных размеров. Основы ваясь на данных таблицы 5.7 и убедившись в правильности (то есть абсолютно малом отклонении от значений, полученных с помощью программы SPSS) полученных значе 16

ний, можно сделать вывод о том, что программа работает корректно. Таблица 2.2. Результаты выполнения программы Точный критерий Фишера 0.7495 Критерий Фишера с МК 0.7455 Хи-квадрат Пирсона 0.8252 Отношение правдоподобия 0.9261 Таблица 2.3. Таблица сопряженности НИС и T-стадии НИС/Т-стадия 1 2 3 4 Итого низкий 8 2 2 2 14 средний 17 2 3 2 24 крупный 1 1 0 0 2 высокий 2 0 1 0 3 Итого 28 5 6 4 43 Таблица 2.4. Сравнение НИС и T-стадии в SPSS Точный критерий Фишера 0.749 Хи-квадрат Пирсона 0.825 Отношение правдоподобия 0.926 Программа, реализующая точный критерий Фишера, тестировалась на различных таблицах сопряженности, а также с использованием различных статистических крите риев, как показано в примере 2.5.1. Пример 2.5.1. Пуста дана таблица сопряженности, показанная в таблице 2.3. В ре зультате выполнения собственной программы получатся значения из таблицы 2.2. Как видно из таблицы 2.4 значение, полученное с помощью статистического кри терия точного критерия Фишера, более точно, что имеет немаловажное значение. 17

2.6. Сравнение с fisher.test() В языке R уже существует функция, реализующая точный тест Фишера. Это: fisher.test(x, workspace, alternative, conf.int, conf.level, simulate.p.value, B), где x — табли ца сопряженности, workspace — размерность пространства в сетевом алгоритме, alternative — отвечает за тип вычисляемого 𝑝-значения, conf.int и conf.level — дают возможность вы числить доверительные интервалы с заданным уровнем значимости, а simulate.p.value и B — отвечает за вычисление методом Монте-Карло и количество вычислений соответ ственно. Для таблиц размерности 2 × 2 в языке R можно дополнительно вычислить довери тельный интервал, а также левостороннее, правостороннее и двустороннее 𝑝-значение по отдельности. В моей программе представлены все типы 𝑝-значений одновременно, а также показывается значение, полученное с помощью метода Монте-Карло. Также есть возможность вычисления 𝑝-значения с помощью различных статистических критериев. В языке R для перечисления таблиц сопряженности 𝑟 × 𝑐, где 𝑟, 𝑐 ≥ 2, используются сетевые алгоритмы. Поскольку точное 𝑝-значение трудно вычислимо из-за сложности перебора всех таблиц Γ* (1.5), в основе этого метода полагается представление этого мно ∏︀ ∑︀ жества Γ* в виде сети из узлов и дуг. Введем обозначение 𝐷 = ( 𝑟𝑗=1 𝑚𝑗 )!/( 𝑟𝑗=1 𝑚𝑗 )!, где 𝑚𝑗 взяты из уравнения (1.1). При таком представлении в виде сети можно заменить исходную задачу перебора таблиц на эквивалентную задачу нахождения всех путей в се ти, длина которых не будет превосходить значения 𝐷 * 𝑃 (𝑋) (1.2), где 𝑋—наблюдаемая таблица сопряженности. Построим сеть из 𝑐 + 1 уровня, на каждом уровне определим множество узлов (𝑘, 𝑚1𝑘 , . . . , 𝑚𝑟𝑘 ), притом от каждого узла будет исходить дуга ровно к одному узлу на каждом нижнем уровне. Таким образом получим набор различных путей узлами разных уровней. Остается сделать отбор подходящих путей. Для этого введем 𝑆𝑃 (𝑘, 𝑚1𝑘 , . . . , 𝑚𝑟𝑘 ) и 𝐿𝑃 (𝑘, 𝑚1𝑘 , . . . , 𝑚𝑟𝑘 ), равные самому короткому пути из узла 𝑘 в узел 0 и самому длинному пути соответственно, и 𝑃 𝐴𝑆𝑇 — длину пути из текущего узла в узел 𝑘. Тогда при выполнении условий 𝑃 𝐴𝑆𝑇 * 𝑆𝑃 (𝑘) ≤ 𝐷 * 𝑃 (𝑋) и 𝑃 𝐴𝑆𝑇 * 𝐿𝑃 (𝑘) > 𝐷 * 𝑃 (𝑋) мы получим подходящие пути и как раз перечислим нужные таблицы. В моей же работе используется непосредственно последовательный перебор относительно свободных ячеек. Замечание 1. Собственную программу, реализующую точный критерий Фишера для таблиц сопряженности размерности 𝑟 × 𝑐 категориальных признаков, будем применять 18

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

Глава 3 Определение информативных признаков С помощью изученного в предыдущей главе точного критерия Фишера можно было сделать вывод о значимости взаимосвязи между признаками, поэтому попытаемся расширить его применение для определения наиболее важных со статистической точки зрения симптомов, влияющих на определенный исход болезни пациента. Для этого мы введем понятие грассманиана и изучим метод быстрого перечисления его точек. 3.1. Алгоритм быстрого перечисления точек грассманиана Определение 3.1.1. [11] Всевозможные 𝑘-мерные подпространства данного простран ства 𝑉𝑚 = (F𝑞 )𝑚 образуют грассманиан 𝐺𝑟𝑞 (𝑘, 𝑚), точкой которого является одно 𝑘-мерное подпространство. Рассматриваемое множество подпространств не является естественным образом упорядоченным, а также включения могут иметь место только для подпространств различных размерностей, поэтому для организации перебора представляется естествен ным вопрос перенумерации всех подпространств фиксированной размерности, т.е. то чек некоторого грассманиана. Данный алгоритм основан на предложенной в диссер тации [11] его векторной параметризации и ориентирован на сокращение количества операций для построения каждой следующей точки за счет использования кода Грея и соответствующего ему отношения линейного порядка. Определение 3.1.2. Двоичный код Грея порядка 𝑛 — набор всевозможных 2𝑛 𝑛-битных кодов, при этом любые два соседних кода в наборе различаются только в одном разряде. Докажем существование таких кодов Грея по индукции. Доказательство. Рассмотрим базу индукции: при 𝑛 = 0 кодом Грея будет являться пустая последовательность. Рассмотри индукционный переход: допустим, что в результате генерации были получе ны 2 последовательности, а именно 𝐺𝑛 и 𝐺𝑖𝑛𝑣 𝑛 , где первая — последовательность кодов Грея порядка 𝑛, а вторая — та же последовательность, только записанная в обратном порядке. Набор следующего порядка 𝐺𝑛+1 можно получить, дописав нуль слева к кодам 20

из 𝐺𝑛 и единицу слева к кодам из 𝐺𝑖𝑛𝑣 𝑛 , после чего составив из полученного один набор, т.е. 𝐺𝑛+1 = 0𝐺𝑛 ∪ 1𝐺𝑖𝑛𝑣 𝑛 . При таком построении два соседних кода будут различаться только в одном разряде, что соответствует свойству кодов Грея. Нам требуется максимальное сокращение количества операций для построения каждой следующей точки грассманиана. Поставим задачу следующим образом: нужно вывести все подмножества множества из 𝑛 элементов в таком порядке, что каждое следующее подмножество будет отличаться от предыдущего удалением или добавлением одного элемента. Таким образом получим перечисление в порядке минимального изменения. Любому набору элементов из этого множества можно сопоставить 𝑛-битный двоичный код и свести задачу к перебору дво ичных кодов Грея. Можно составить алгоритм рекурсивного перебора на основе полученной рекуррент ной формулы 𝐺𝑛+1 = 0𝐺𝑛 ∪ 1𝐺𝑖𝑛𝑣 𝑛 , то есть будем проходить от нулевого двоичного кода порядка 𝑛, на каждой итерации получая код увеличенного на 1 порядка. Пример 3.1.1. Запишем алгоритмически способ генерации кодов Грея на языке 𝐶♯: const n = Console . ReadLine ( ) ; //считали порядок кода Грея int [ ] gray = new int [ n ] ; // создание массива под коды void GrayCodeGen ( int s t e p ) { i f ( s t e p == n+1) Console . WriteLine ( gray ) ; // вывод кодов else { gray [ s t e p ] = 0 ; GrayCode ( s t e p + 1 ) ; //шаг с прибавлением 0 слева gray [ s t e p ] = 1 ; InvGrayCode ( s t e p + 1 ) ; // с прибавлением 1 слева } } void InvGrayCodeGen ( int s t e p ) { i f ( s t e p == n+1) Console . WriteLine ( gray ) ; else { gray [ s t e p ] = 1 ; GrayCode ( s t e p + 1 ) ; //шаг с прибавлением 1 слева 21

gray [ s t e p ] = 0 ; InvGrayCode ( s t e p + 1 ) ; // с прибавлением 0 слева } } void Main ( s t r i n g [ ] a r g s ) { for ( int i =1; i <= n ; i ++) gray [ i ] = 0 ; // создание нулевого двоичного кода порядка n GrayCodeGen ( 1 ) ; // запуск рекурсивного алгоритма } Пример 3.1.2. Пример построенного по приведенному алгоритму двоичного кода Грея длины три: 1 итерация: берем код 0 1, отражаем зеркально — 1 0, добавляем 0 перед взятым кодом и 1 перед отраженным, получаем: 00 01 11 10 2 итерация: берем полученный на предыдущем шаге код, зеркально его отражаем и получаем последовательность: 000 001 011 010 110 111 101 100, являющуюся кодом Грея. Определение 3.1.3. 𝑁 -арным кодом Грея порядка 𝑘 называется последовательность всех 𝑁 𝑘 кодов длины 𝑘, в которой любые два соседних кода различаются ровно в одном разряде. Рассмотрим 2 частных случая, когда 𝑁 — четное и когда нечетное, и алгоритмы для генерации кодов Грея в этих случаях: Случай 1: Пусть 𝑁 — четное, тогда можно генерировать коды Грея так же, как и в бинарном случае, то есть с помощью рекурсивной процедуры, с единственным отличием в том, что числа кода будут варьироваться уже не от 0 до 1, а от 0 до 𝑁 − 1. 22

Пример 3.1.3. Пример построенного по приведенному алгоритму четверичного кода Грея длины два: Берем код 0 1 2 3, отражаем зеркально — 3 2 1 0, добавляем 0 перед взятым кодом и 1 перед отраженным, повторяем эти действия вплоть до 3, получаем: 00 01 02 03 13 12 11 10 20 21 22 23 33 32 31 30 Случай 2: Пусть 𝑁 — нечетное, тогда генерировать коды Грея с помощью рекур сивной процедуры не получится, так как в итоге получим разницу во всех разрядах первого и последнего элемента кода. Пример 3.1.4. Пример построенного по рекурсивному алгоритму троичного кода Грея длины два: 00 01 02 12 11 10 20 21 22, как видно из примера коды 22 и 00 отличаются больше, чем в 1 разряде. Для построения кода Грея в случае нечетного 𝑁 можно использовать итеративный алгоритм: Нам требуется построить 𝑁 𝑘 кодов длины 𝑘, для этого выпишем все числа 𝑥 от 0 до 𝑁 − 1 — эти числа будут соответствовать месту нашего кода в последовательности. Далее выполним следующий алгоритм: 1)𝑖 = 0, 𝑥0 = 𝑥 2)𝑥𝑖+1 = ⌊𝑥/𝑁 𝑖 ⌋ 3)𝑑𝑖 = (𝑥𝑖 − 𝑥𝑖+1 ) (mod 𝑁 ), где 𝑑𝑖 — цифры кода, начиная с младшего разряда 4)𝑥𝑖 ̸= 0 → 𝑖 = 𝑖 + 1 и возвращаемся к пункту 2, иначе добавляем недостающие нули и заканчиваем алгоритм. Пример 3.1.5. Вычислим 7-ое число последовательности в случае, когда 𝑁 = 3, 𝑘 = 3. 𝑥0 = 𝑁 − 1 = 6, 𝑥1 = 2 → 𝑑0 = 4 (mod 3) = 1 𝑥2 = 0, → 𝑑1 = 2 (mod 3) = 2 23

𝑥2 = 0, 𝑘 = 3 → 𝑑2 = 0 Выпишем полученное число в порядке от 𝑑𝑘−1 до 𝑑0 — это код 021. Аналогично выпишем все остальные коды в последовательности. Пример 3.1.6. Пример построенного по приведенному итеративному алгоритму тро ичного кода Грея длины три: 000 001 002 012 010 011 021 022 020 120 121 122 102 100 101 111 112 110 210 211 212 222 220 221 201 202 200, как видно из примера коды 200 и 000 отличаются ровно в одном разряде. Данный код уже не будет рефлексивным, но сохранит свою цикличность и не избыточность. Далее введем соответствующее двоичному коду Грея отношение линейного поряд ка. Отметим, что введенное отношение линейного порядка обязано согласовываться с флагом. Определение 3.1.4. [11] Отношение линейного порядка ≻𝑔 называется обобщенным ′ ′ порядком Грея, если (𝑎1 , . . . , 𝑎𝑚 ) ≻𝑔 (𝑎1 , . . . , 𝑎𝑚 ) тогда и только тогда, когда ′ ′ ′ ′ ′ (𝑎1 ⊕ · · · ⊕ 𝑎𝑚 , 𝑎2 ⊕ · · · ⊕ 𝑎𝑚 , . . . , 𝑎𝑚 ) ≻𝑙 (𝑎1 ⊕ · · · ⊕ 𝑎𝑚 , 𝑎2 ⊕ · · · ⊕ 𝑎𝑚 , . . . , 𝑎𝑚 ), где ⊕ — суммирование по модулю 𝑞, а ≻𝑙 — лексикографический порядок: ∑︀ ∑︀ ′ ′ ′ 𝑖−1 𝑖−1 (𝑎1 , . . . , 𝑎𝑚 ) ≻𝑙 (𝑎1 , . . . , 𝑎𝑚 ) ↔ 𝑚 ≥ 𝑚 . 𝑖=1 𝑎𝑖 𝑞 𝑖=1 𝑎𝑖 𝑞 Упорядочивание множества векторов пространства 𝑉𝑚 над полем F𝑞 , соответству ющее обобщенному порядку Грея с ограничением на старший разряд, что для 𝑋𝜏𝑖 ∈ 𝑉𝑚 и 𝑋𝜏𝑖 = 𝑎𝑖1 𝑋1 + · · · + 𝑎𝑖𝑚 𝑋𝑚 выполняется равенство (𝑎𝑖1 , . . . , 𝑎𝑖𝑚 ) = (𝑎𝑖1 , . . . , 𝑎𝑖𝑠 , 1, 0, . . . , 0) при 𝑠 ≤ 𝑚, реализует перестановку, минимизирующую количество используемой па мяти и гарантирующую одинаковое количество операций для формирования любого нового вектора. 24

Пример 3.1.7. Коды, соответствующие обобщенному порядку Грея над F2 : 𝑎𝑏𝑐 = 𝑎 * 22 + (𝑎 + 𝑏) (mod 2) * 21 + (𝑎 + 𝑏 + 𝑐) (mod 2) * 20 000 = 0 * 22 + 0 * 21 + 0 * 20 = 0 001 = 0 * 22 + 0 * 21 + 1 * 20 = 1 011 = 0 * 22 + 1 * 21 + 0 * 20 = 2 010 = 0 * 22 + 1 * 21 + 1 * 20 = 3 110 = 1 * 22 + 0 * 21 + 0 * 20 = 4 111 = 1 * 22 + 0 * 21 + 1 * 20 = 5 101 = 1 * 22 + 1 * 21 + 0 * 20 = 6 100 = 1 * 22 + 1 * 21 + 1 * 20 = 7 Пример 3.1.8. Коды, соответствующие обобщенному порядку Грея над F3 : 𝑎𝑏𝑐 = 𝑎 * 32 + (𝑎 + 𝑏) (mod 3) * 31 + (𝑎 + 𝑏 + 𝑐) (mod 3) * 30 000 = 0 * 32 + 0 * 31 + 0 * 30 = 0 001 = 0 * 32 + 0 * 31 + 1 * 30 = 1 002 = 0 * 32 + 0 * 31 + 2 * 30 = 2 012 = 0 * 32 + 1 * 31 + 0 * 30 = 3 010 = 0 * 32 + 1 * 31 + 1 * 30 = 4 011 = 0 * 32 + 1 * 31 + 2 * 30 = 5 021 = 0 * 32 + 2 * 31 + 0 * 30 = 6 022 = 0 * 32 + 2 * 31 + 1 * 30 = 7 022 = 0 * 32 + 2 * 31 + 2 * 30 = 8 и т.д. Для того, чтобы перечислить всевозможные 𝑘-мерные векторные подпространства пространства, порожденного набором линейно независимых векторов (𝑋1 , . . . , 𝑋𝑚 ), до статочно перебрать базисы этих подпространств, а именно всевозможные наборы ли нейно независимых векторов 𝑋𝜏1 , . . . , 𝑋𝜏𝑘 , при этом нужно избежать повторений учи тывания одинаковых подпространств. Векторы 𝑋𝜏𝑖 являются линейно независимыми комбинациями векторов из известного нам набора (𝑋1 , . . . , 𝑋𝑚 ), а коэффициенты этой линейной комбинации будут задавать 𝑖-ую строку матрицы. Таким образом получим матрицу из коэффициентов размером 25

𝑘 × 𝑚. Для составления такой матрицы будем формировать вектора 𝑋𝜏𝑖 . Алгоритм: Цикл 1 Для набора 𝑋 (1) = (𝑋1 , . . . , 𝑋𝑚 ) перебираем наборы (𝑎1 , . . . , 𝑎𝑚 )в порядке (1) Грея. Формируем на каждой итерации (𝑋𝜏1 )𝑖𝑡𝑒𝑟1 = (𝑋𝜏1 )𝑖𝑡𝑒𝑟𝑖 −1 + 𝑎1𝑡 𝑋𝑡 , где 𝑎1𝑡 — от (1) личающийся элемент, 𝑋𝑡 = 𝑋𝑡 . Для вектора (𝑋𝜏1 )𝑖𝑡𝑒𝑟1 и соответствующего набора (𝑎11 , . . . , 𝑎1𝑠1 , 1, 0, . . . , 0) определяем номер 𝑗1 = 𝑠1 + 1 последней единицы из набора. Цикл 2 Для набора 𝑋 (2) = (𝑋1 , . . . , 𝑋𝑗1 −1 , 𝑋𝑗1 +1 , . . . , 𝑋𝑚 ) перебираем все оставши еся наборы (𝑎21 , . . . , 𝑎2(𝑚−1) ) в порядке Грея, начиная с набора (0, . . . , 0, 1, 0, . . . , 0) с единицей на 𝑗1 месте. После чего формируем на каждой итерации значение (2) (2) (𝑋𝜏2 )𝑖𝑡𝑒𝑟2 = (𝑋𝜏2 )𝑖𝑡𝑒𝑟2 −1 + 𝑎2𝑡 𝑋𝑡 , где 𝑎2𝑡 — отличающийся элемент, 𝑋𝑡 — вектор на месте t в 𝑋 (2) . Для вектора (𝑋𝜏2 )𝑖𝑡𝑒𝑟2 и соответствующего набора коэффициен тов (𝑎21 , . . . , 𝑎2𝑠2 , 1, 0, . . . , 0) определяем номер 𝑗2 = 𝑠2 + 1 последней единицы из набора. ... Цикл i Для набора 𝑋 (𝑖) — набора 𝑋 (1) без векторов 𝑋𝑗1 , . . . , 𝑋𝑗(𝑖−1) перебира ем наборы (𝑎𝑖1 , . . . , 𝑎𝑖(𝑚−(𝑖−2)) ) в порядке Грея, начиная с набора (0, . . . , 1, . . . , 0) с единицей на 𝑗𝑖−1 + 2 − 𝑖 месте. Формируем на каждой итерации значе (𝑖) (𝑖) ние (𝑋𝜏𝑖 )𝑖𝑡𝑒𝑟𝑖 = (𝑋𝜏𝑖 )𝑖𝑡𝑒𝑟𝑖 −1 + 𝑎𝑖𝑡 𝑋𝑡 , где 𝑎𝑖𝑡 — отличающийся элемент, 𝑋𝑡 — вектор на месте t в 𝑋 (𝑖) . Для вектора (𝑋𝜏𝑖 )𝑖𝑡𝑒𝑟𝑖 и соответствующего набора (𝑎𝑖1 , . . . , 𝑎𝑖𝑠𝑖 , 1, 0, . . . , 0) определяем номер 𝑗𝑖 = 𝑠𝑖 + 1 последней единицы из набора. ... Цикл k Для набора 𝑋 (𝑘) — набора 𝑋 (1) без векторов 𝑋𝑗1 , . . . , 𝑋𝑗(𝑘−1) перебираем наборы коэффициентов (𝑎𝑘1 , . . . , 𝑎𝑘(𝑚−(𝑘−2)) ) в порядке Грея, начиная с такого набора (0, . . . , 1, . . . , 0), где единица стоит на 𝑗𝑘−1 +2−𝑘 (𝑘) месте. Формируем на каждой итерации (𝑋𝜏𝑘 )𝑖𝑡𝑒𝑟𝑘 = (𝑋𝜏𝑘 )𝑖𝑡𝑒𝑟𝑘 −1 +𝑎𝑘𝑡 𝑋𝑡 , (𝑘) где 𝑎𝑘𝑡 — отличающийся элемент, 𝑋𝑡 — вектор на месте t в 𝑋 (𝑘) . (𝑖𝑡𝑒𝑟) Составляем базис подпространства 𝑉𝑘 Конец цикла k ... Конец цикла i ... 26 = ⟨(𝑋𝜏1 )𝑖𝑡𝑒𝑟1 , . . . , (𝑋𝜏𝑘 )𝑖𝑡𝑒𝑟𝑘 ⟩.

Конец цикла 2 Конец цикла 1 В результате работы алгоритма получим матрицы коэффициентов со следующими свой ствами: 1) в каждой строке найдется коэффициент 𝑎𝑖,𝑠 = 1, где 𝑠 - максимальный номер столб ца, удовлетворяющий этому условию, после которого идут все нули. 2) в каждой строке найдется коэффициент 𝑎𝑗,𝑙 = 1, такой, что 𝑖 < 𝑗 и 𝑠 < 𝑙, то есть последняя единица в каждой строке будет расположена правее, чем в предыдущих. 3) под каждой последней единицей, описанной в первом пункте, в последующих строках идут все нули. Данные матрицы гарантируют перечисление всех точек грассманиана без повторений и в порядке минимального изменения[11] и имеют общий вид: Таблица 3.1. Общий вид матрицы 𝑋1 ⎛ 𝑋 𝜏1 ⎜ .. ⎜ . ⎜ ⎜ ⎜ 𝑋 𝜏𝑖 ⎜ ⎜ .. ⎜ . ⎜ ⎝ 𝑋 𝜏𝑘 ... ... 𝑋𝑗 ... * .. . ... .. . * 1 0 ... .. .. .. . . . . . . 0 .. . 0 .. . 0 ... .. . . . . * .. . ... ... * 0 * ... .. .. .. . . . . . . * .. . 1 .. . 0 ... .. . . . . * ... * 0 * ... * 0 * ... 𝑋𝑚 ⎞ 0 ⎟ .. ⎟ . ⎟ ⎟ ⎟ 0 ⎟ ⎟ .. ⎟ . ⎟ ⎠ 0 Пример 3.1.9. Применим этот алгоритм для перечисления точек грассманиана 𝐺𝑟4 (3, 5): В первом цикле начнем перебор всех кодов в порядке Грея: 00000 = 0 * 44 + 0 * 43 + 0 * 42 + 0 * 41 + 0 * 40 = 0 00001 = 0 * 44 + 0 * 43 + 0 * 42 + 0 * 41 + 1 * 40 = 1 00002 = 0 * 44 + 0 * 43 + 0 * 42 + 0 * 41 + 2 * 40 = 2 00003 = 0 * 44 + 0 * 43 + 0 * 42 + 0 * 41 + 3 * 40 = 3 00013 = 0 * 44 + 0 * 43 + 0 * 42 + 1 * 41 + 0 * 40 = 4 00010 = 0 * 44 + 0 * 43 + 0 * 42 + 1 * 41 + 1 * 40 = 5 00011 = 0 * 44 + 0 * 43 + 0 * 42 + 1 * 41 + 2 * 40 = 6 00012 = 0 * 44 + 0 * 43 + 0 * 42 + 1 * 41 + 3 * 40 = 7 00022 = 0 * 44 + 0 * 43 + 0 * 42 + 2 * 41 + 0 * 40 = 8 27

и т.д. Под единицей, имеющей максимальный индекс в строке 𝑎𝑖,𝑠 , стоят в последующих стро ках нули. При этом последняя единица в строках ниже расположена правее последней единицы в предыдущей строке. Поэтому выполняем последующий перебор без учета столбца с индексом 𝑎𝑖,𝑠 и начиная с варианта, где у последней единицы индекс столбца имеет большее значение, чем индекс 𝑠, что соответствует алгоритму. Так, если в результате действия алгоритма для 𝑋𝜏1 будет получена строка коэффици ентов с индексом столбца последней единицы равным 3, а именно (*, *, 1, 0, 0), где под * обозначен некоторый полученный элемент из поля F4 = [0, 1, 2, 3], то для последующих 𝑋𝜏2 и 𝑋𝜏3 индекс столбца последней единицы однозначно будет равен соответственно 4 и 5, исходя из условий вида матрицы. При таких условиях получаемая матрица коэффициентов будет иметь вид: 𝑋1 ⎛ * ⎜ ⎜ 𝑋𝜏 2 ⎜ * ⎝ 𝑋𝜏 3 * 𝑋𝜏 1 𝑋2 𝑋3 * 1 𝑋4 0 * 0 1 * 0 0 𝑋5 0 ⎞ ⎟ ⎟ 0 ⎟ ⎠ 1 Далее, если в результате действия алгоритма для 𝑋𝜏1 будет получена строка коэффици ентов с индексом столбца последней единицы равным 2, а именно (*, 1, 0, 0, 0), где под * обозначен некоторый полученный элемент из поля F4 = [0, 1, 2, 3], то для последую щих 𝑋𝜏2 и 𝑋𝜏3 индекс столбца последней единицы уже может варьироваться, при этом удовлетворяя условиям вида матрицы. Максимальный индекс столбца с единицей для 𝑋𝜏2 = [3, 4], и соответственно для 𝑋𝜏3 = [(4, 5), 5]. В качестве примера рассмотрим частный случай, когда индексы столбцов с максималь ной единицей равны (2, 4, 5), и получаемая матрица коэффициентов будет иметь вид: 𝑋𝜏 1 ⎛ 𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 * 1 0 0 0 ⎜ ⎜ 𝑋𝜏 2 ⎜ * ⎝ 𝑋𝜏 3 * 0 * 1 0 * 0 ⎞ ⎟ ⎟ 0 ⎟ ⎠ 1 Особое внимание стоит уделить варианту, когда в результате действия алгоритма для 𝑋𝜏1 будет получена строка коэффициентов с индексом столбца последней единицы рав ным 1, а именно (1, 0, 0, 0, 0), то для последующих 𝑋𝜏2 и 𝑋𝜏3 индекс столбца последней 28

единицы варьируется очень сильно, при этом удовлетворяя условиям вида матрицы, так максимальный индекс столбца с единицей для 𝑋𝜏2 = [2, 3, 4], и соответственно для 𝑋𝜏3 = [(3, 4, 5), (4, 5), 5]. В общем виде можно выразить максимальный индекс столбца с единицей для 2-ой и 3-ей строки следующим образом: обозначим индекс столбца последней единицы для 𝑋𝜏1 за 𝑖1 = [1, . . . , 𝑚 + 𝑟 − 𝑘], где 𝑟 — индекс рассматриваемой строки, тогда индексы последней единицы для 𝑋𝜏2 могут принимать значения 𝑖2 = [𝑖1 + 1, . . . , 𝑚 + 𝑟 − 𝑘], а для 𝑋𝜏3 — значения 𝑖3 = [𝑖2 + 1, . . . , 𝑚 + 𝑟 − 𝑘]. В качестве примера рассмотрим частный случай, когда индексы столбцов с максимальной единицей равны (1, 2, 3), и получаемая матрица коэффициентов будет иметь вид: 𝑋1 𝑋𝜏 1 ⎛ 1 ⎜ ⎜ 𝑋𝜏 2 ⎜ 0 ⎝ 𝑋𝜏 3 0 𝑋2 𝑋3 𝑋4 0 0 0 1 0 0 0 1 0 𝑋5 0 ⎞ ⎟ ⎟ 0 ⎟ ⎠ 0 Таким образом, алгоритм перечисляет всевозможные 3-мерные векторные подпростран ства пространства (F4 )5 . 3.2. Алгоритм перечисления точек грассманиана с использованием диаграмм Юнга В разделе 3.1 рассматривалось перечисление точек грассманиана 𝐺𝑟𝑞 (𝑘, 𝑚) с ис пользованием 𝑘 вложенных циклов и переборов кодов в порядке Грея, в этом разделе рассмотрим альтернативный способ перечисления его точек. Как уже говорилось ранее, точки грассманиана представимы в виде треугольных матриц размера 𝑘 × 𝑚, имеющих вид 3.1. Определение 3.2.1. [14] Клеткой Шуберта называется подмножество 𝑆𝐼 ⊂ 𝐺𝑟𝑞 (𝑘, 𝑚), которое состоит из всевозможных подпространств 𝑉𝐼 определенного комбинаторного ти па 𝐼, где 𝐼 = (𝑖1 , . . . , 𝑖𝑘 ) — вектор длины 𝑘, состоящий из строго возрастающих номеров 1 ≤ 𝑖1 < 𝑖2 < · · · < 𝑖𝑘 ≤ 𝑚. Определение 3.2.2. Флаг 𝐹 — строго возрастающая последовательность подпространств 𝑉0 ⊂ 𝑉1 ⊂ · · · ⊂ 𝑉𝑚 пространства 𝑉 . 29

Теорема 3.2.1. Выбор флага 𝐹 подпространств в (F𝑞 )𝑚 определяет клеточное разбие ние грассманиана, при этом матрицы коэффициентов такого разбиения будут иметь вид 3.1. Доказательство. Возьмем 𝑈 — некоторую 𝑘-плоскость в 𝐺𝑟𝑞 (𝑘, 𝑚), определим флаг и 𝑉𝑖 = (𝑒1 , . . . , 𝑒𝑖 ) ⊂ (F𝑞 )𝑚 . Для каждой плоскости рассмотрим возрастающую последова тельность подпространств: 0 ⊂ 𝑈 ∩ 𝑉1 ⊂ 𝑈 ∩ 𝑉2 ⊂ · · · ⊂ 𝑈 ∩ 𝑉𝑛−1 ⊂ 𝑈 ∩ 𝑉𝑛 = 𝑈 Отметим, что 𝑈 ∩ 𝑉𝑖 при 𝑖 ≤ 𝑛 − 𝑘 нулевое, а другие имеют размерность (𝑖 + 𝑘 − 𝑚). Возьмем некоторую последовательность целых чисел (𝑎1 , . . . , 𝑎𝑘 ) и для неё определим множество следующего вида: 𝑄𝑎1 ,...,𝑎𝑘 = {𝑈 : 𝑑𝑖𝑚(𝑈 ∩ 𝑉𝑚−𝑘+𝑖−𝑎𝑖 ) = 𝑖} Размерность подмножества (𝑈 ∩ 𝑉𝑚−𝑘+𝑖−𝑎𝑖 ) = 𝑚 − 𝑎𝑖 , а значит 𝑄𝑎1 ,...,𝑎𝑘 не пусто толь ко при условии того, что (𝑎1 , . . . , 𝑎𝑘 ) — невозрастающая последовательность, при этом ∀𝑎𝑖 ≤ 𝑚−𝑘. Тогда в 𝑈 ∈ 𝑄𝑎1 ,...,𝑎𝑘 выберем базис (𝑣1 , . . . , 𝑣𝑘 ) таким образом, что вектор 𝑣𝑖 при 𝑖 ∈ (1, . . . , 𝑘), будет порождать пространство (𝑈 ∩ 𝑉𝑚−𝑘+𝑖−𝑎𝑖 ) с такой нормировкой, что ⟨𝑣𝑖 , 𝑒𝑚−𝑘+𝑗−𝑎𝑗 ⟩ равен 0 при 𝑗 < 𝑖 и 1 при 𝑗 = 𝑖. Следует отметить, что получается итеративная процедура выбора вектора 𝑣𝑖 , который на каждом шаге будет определен однозначно. Составив матрицу из векторов (𝑣1 , . . . , 𝑣𝑘 ) получим матрицу вида 3.1, при чём матрице такого вида будет отвечать 𝑈 ∈ 𝑄𝑎1 ,...,𝑎𝑘 . В результате получили, что выбор флага определяет множество 𝑄𝑎1 ,...,𝑎𝑘 , которое, в свою очередь, задает клеточное разбиение грассманиана 𝐺𝑟𝑞 (𝑘, 𝑚) на клетки, имеющие вид 3.1. Следует обратить внимание, что построенное в дказательстве множество является клеткой Шуберта, а следовательно грассманиан разбивается в дизъюнктное объедине ние подмножеств 𝑆𝐼 [12]. Пусть получен возрастающий набор чисел 𝐼 = (𝑖1 , . . . , 𝑖𝑘 ), где 𝑖𝑥 < 𝑖𝑦 при 𝑥 < 𝑦, где при подставлении в матрицу размера 𝑘 × 𝑚 построчно единиц на места 𝑖𝑗 из набора 𝐼 будут выполняться следующие условия, согласные построению в доказательстве: 1. Правее последней единицы в строке стоят только нули. 30

2. Под этими единицами в последующих строках стоят всюду нули. 3. Оставшиеся неопределенными числа являются произвольными из поля F𝑞 . Таким образом, с помощью такого набора 𝐼 можно задавать матрицы коэффициентов вида 3.1, являющиеся описанием конкретных точек грассманиана. Разобьем грассмани ан 𝐺𝑟𝑞 (𝑘, 𝑚) в дизъюнктное объединение подмножеств 𝑆𝐼 , где 𝑆𝐼 — клетка Шуберта. Чтобы перечислить все точки грассманиана можно было бы перечислить всевозможные наборы 𝐼, и на их основе построить матрицы коэффициентов, но, с практической точки зрения, эта задача трудновыполнима, поэтому чаще применяют диаграммы Юнга. Определение 3.2.3. [13] Диаграмма Юнга 𝜆 — это конечный невозрастающий на бор чисел, чаще представимый в виде набора клеток, выровненных по левой границе, количество которых в каждой строке соответствует числу из набора. Диаграмму Юнга 𝜆 можно задать в виде вектора (𝜆1 , . . . , 𝜆𝑘 ), при этом стоит обратить внимание на то, что наборы 𝐼 = (𝑖1 , . . . , 𝑖𝑘 ) и 𝜆 = (𝜆1 , . . . , 𝜆𝑘 ) находятся в биективном соответствии, и 𝜆𝑘+1−𝑗 = 𝑖𝑗 − 𝑗 при 𝑗 = (1, . . . , 𝑘). Обычно диаграммы Юнга описывают в виде таблиц из клеток, где в строке 𝑗 будет находиться 𝜆𝑗 клеток. Стоит обратить внимание, что набор 𝜆 является невозрастающим и 0 ≤ 𝜆𝑗 ≤ (𝑚 − 𝑘). Пример 3.2.1. Аналогично примеру 3.1.9 рассмотрим грассманиан 𝐺𝑟4 (3, 5), 𝑘 = 3, 𝑚 = 5. Рассмотрим набор 𝐼 = (1, 2, 5), построим соответствующую ему диаграмму Юнга: 𝜆1 = 𝑖3 − 3 = 5 − 3 = 2; 𝜆2 = 𝑖2 − 2 = 2 − 2 = 0; 𝜆3 = 𝑖1 − 1 = 1 − 1 = 0; то есть 𝜆 = (2, 0, 0). Принцип построения матрицы коэффициентов: при известной диаграммме Юнга нужно, начиная с самой последней нижней строки и двигаясь вверх к первой, сдвигать индекс последней единицы в строке с крайнего левого возможного положения, равного номеру строки, на число, стоящее в 𝜆𝑗 , начиная отсчёт с первого элемента из набора 𝜆. Так диаграмме Юнга (2, 0, 0) будет сопоставляться матрица вида: ⎛ ⎞ 1 0 * * 0 ⎜ ⎟ ⎜ ⎟ ⎜0 1 * * 0⎟ ⎝ ⎠ 0 0 0 0 1 31

Таким образом, существует однозначное соответствие между заданной диаграммой Юн га и видом матрицы, задающей клетку Шуберта. Пример 3.2.2. Ниже аналогично приведены примеры некоторых соответствий диа грамм Юнга и клеток Шуберта грассманиана 𝐺𝑟4 (3, 5), где под * обозначен произволь ный элемент из поля F4 : Таблица 3.2. Примеры сопоставления диаграмм Юнга и клеток Шуберта Диаграмма Юнга 𝜆 Клетка Шуберта 𝑆𝜆 ⎛ ⎞ 1 0 0 * * ⎜ ⎟ ⎜ ⎟ (0, 0, 0) ⎜0 1 0 * * ⎟ ⎝ ⎠ 0 0 1 * * ⎛ ⎞ 1 0 * 0 * ⎜ ⎟ ⎜ ⎟ (1, 0, 0) ⎜0 1 * 0 * ⎟ ⎝ ⎠ 0 0 0 1 * ⎛ ⎞ 1 * 0 0 * ⎜ ⎟ ⎜ ⎟ (1, 1, 0) ⎜0 0 1 0 * ⎟ ⎝ ⎠ 0 0 0 1 * ⎛ ⎞ 0 1 0 0 * ⎜ ⎟ ⎜ ⎟ (1, 1, 1) ⎜0 0 1 0 * ⎟ ⎝ ⎠ 0 0 0 1 * ⎛ ⎞ 0 1 0 * 0 ⎜ ⎟ ⎜ ⎟ (2, 1, 1) ⎜0 0 1 * 0⎟ ⎝ ⎠ 0 0 0 0 1 ⎛ ⎞ 0 1 * 0 0 ⎜ ⎟ ⎜ ⎟ (2, 2, 1) ⎜0 0 0 1 0⎟ ⎝ ⎠ 0 0 0 0 1 ⎛ ⎞ 0 0 1 0 0 ⎜ ⎟ ⎜ ⎟ (2, 2, 2) ⎜0 0 0 1 0 ⎟ ⎝ ⎠ 0 0 0 0 1 𝑑𝑖𝑚𝑆𝜆 6−0=6 6−1=5 6−2=4 6−3=3 6−4=2 6−5=1 6−6=0 Размерность 𝑆𝜆 можно получить, вычислив значение 𝑘(𝑚 − 𝑘) − 32 ∑︀𝑘 𝑖=1 𝜆𝑖 .

Для преобразования полученных клеток Шуберта к виду матрицы коэффициентов 3.1 нужно полученную матрицу для клетки Шуберта 𝑆𝜆 преобразовать в матрицу коэффи циентов 𝐴 = 𝐶𝑚×𝑚 𝑆𝜆 𝐶𝑘×𝑘 , где 𝐶𝑛×𝑛 — нулевая квадратная матрица размера 𝑛 × 𝑛 с единицами на побочной диагонали. На основе выводов, приведенных выше, можно построить алгоритм перечисления точек грассманиана 𝐺𝑟𝑞 (𝑘, 𝑚). Алгоритм: 1. Генерируем в порядке Грея коды (𝜆1 , . . . , 𝜆𝑘 ) длины 𝑘 в поле 𝐹𝑚−𝑘 согласно алго ритму 3.1.1. 2. Рассматриваем код, как 𝑘-значное число, выполняем проверку с помощью попар ного сравнения двух соседних разрядов. Отбираем из полученных кодов только удовлетворяющие условию невозрастания. 3. Каждому отобранному коду сопоставляем матрицу коэффициентов клетки Шу берта: а. Генерируем матрицу размера 𝑘 × 𝑚 из элементов, равных −1. б. В каждую строку 𝑖 таблицы записываем 1 в столбец с индексом 𝑖 + 𝜆𝑘+1−𝑖 . в. Слева от полученных единиц в каждой строке записываем всюду нули. г. В строках выше над полученными единицами записать всюду нули. 4. Для полученных в предыдущем пункте матриц рассматриваем все оставшиеcя неизмененными элементы, равные −1. Подсчитываем их количество 𝑡 и в 𝑡 вло женных циклах прогоняем значения этих элементов от 0 до 𝑞 − 1. 5. Для всех полученных в результате действия алгоритма матриц проводим оконча тельное преобразование к матрицам . Очевидно, полученный алгоритм приводит к результатам аналогичным алгоритму быст рого перечисления точек грассманиана, следовательно корректен. В результате работы алгоритма получим требуемые матрицы коэффициентов, с помо щью которых осуществляется перебор всех точек грассманиана, то есть всевозможных 𝑘-мерных подпространств пространства (F𝑞 )𝑚 . Преимущества алгоритма: Для приведенного выше алгоритма требуется всего лишь 33

одна реализация кодов Грея и не требуется использование 𝑘 вложенных циклов с внут ренней генерацией, поэтому данный алгоритм проводит более быструю реализацию пе речисления, при этом перечисляемые подпространства будут генерироваться в порядке понижения размерности соответствующих клеток Шуберта, что даёт четкую порядко вую структуру перечисления этих подпространств. 3.3. Применение программы Задача редукции размерности сводится к задаче поиска некоторого случайного вектора заданной размерности, с помощью которого можно было бы описать данный нами эксперимент. То есть нужно отыскать матрицы коэффициентов 𝑀 , такие, как по лученные нами с помощью алгоритма перечисления точек грассманиана, чтобы разница ˆ = 𝑀𝑋 между данным нам вектором 𝑋 = (𝑋1 , . . . , 𝑋𝑚 ) и преобразованным вектором 𝑋 была как можно меньшей. В качестве меры различия будем использовать точный крите рий Фишера, исследованный нами в разделе 2.3. С использованием данного алгоритма была составлена программа на языке R, вычисляющая наилучший синдром 𝑘-ой раз мерности. Результат выполнения программы записывается в текстовый файл, в первой строке которого записывается комбинация, с помощью которой получаются симптомы, а под ней строки с соответствующим симптомам значениями данных. Применим её на реальных данных об операциях при тяжелых кишечных заболеваниях. Из всех данных выделим только наиболее интересующий нас набор данных, характеризующих после операционные осложнения, а именно их появление или отсутствие. Используем программу и применим её к этим данным для поиска синдрома перво го порядка, задаваемого парой симптомов 𝑋𝜏1 и 𝑋𝜏2 , тем самым выделив два основных фактора тяжести послеоперационных осложнений. В результате действия программы были получены два симптома. Первый из них: 𝑋𝜏1 = 𝑋1 + 𝑋4 + 𝑋5, то есть, соглас но таблице 3.3, взаимодействие увеличения диаметра, утолщения и слоистости стенки. Представим его значения в зависимости от исходных данных послеоперационных ослож нений в таблице 3.4. Значение точного критерий Фишера в данном случае равно 0.02593. Здесь нулевое значение фактора 𝑋𝜏1 получается при отсутствии изменений в стен ке кишки и слоистости при увеличении диаметра стенки или утолщении стенки, а также расширении и утолщении, не повлекшем слоистости стенки. Единичное значение фак 34

Таблица 3.3. Набор послеоперационных осложнений Признак Название Определение X1 УДК Увеличение диаметра кишки (0—нет, 1—да) X2 ГНК Гиперпневматоз кишки (0—нет, 1—да) X3 УЖ Повышенный уровень жидкости в кишке (0—нет, 1—да) X4 УСК Утолщение стенки кишки (0—нет, 1—да) X5 ССК Слоистость стенки (0—нет, 1—да) X6 УБр Уплотнение брыжейки (0—нет, 1—да) X7 РГ Реактивный гидроторакс (0—нет, 1—да) X8 АЛ Ателектаз легких (0—нет, 1—да) Таблица 3.4. Значения первого фактора 𝑋𝜏 1 УДК УСК ССК Объем 0 0 0 16 0 1 1 5 1 0 1 5 1 1 0 5 0 0 1 16 0 1 0 3 1 0 0 5 1 1 1 8 0 1 35

тор принимает при слоистости, увеличении и утолщении без других изменений и при полном изменении поведения стенки кишки. Таким образом, фактор 𝑋𝜏1 будет означать тяжесть изменений стенки кишки (0 — при тяжелом, 1 — при облегченном). Второй симптом 𝑋𝜏2 = 𝑋4 + 𝑋7, то есть, согласно таблице 3.3, взаимодействие утолщения стенки и реактивного гидроторакса. Представим его значения в зависимости от исходных данных послеоперационных осложнений в таблице 3.5. Значение точного критерия Фишера в данном случае равно 0.003304. Таблица 3.5. Значения второго фактора 𝑋 𝜏2 УСК РГ Объем 0 0 27 1 1 5 0 1 15 1 0 16 0 1 Нулевое значение фактора 𝑋𝜏2 получается при отсутствии утолщения стенки и гидроторакса или при одновременном их появлении, при этом утолщение стенки мо жет благотворно влиять при появлении гидроторакса, а отсутствие этих осложнений заметно ускорит выздоровление пациента. Единичное значение будет приниматься при раздельном появлении осложнений. Возникновение реактивного гидроторакса при ис тонченной стенке кишки может вызвать ряд ещё более крупных осложнений. Таким образом, фактор 𝑋𝜏2 будет означать тяжесть возможных последующих осложнений в грудной области (0 — легкие, 1 — тяжелые). 36

Глава 4 О параметризации грассманиана 4.1. Связь грассманиана с симптомом и синдромом Пусть существует случайный вектор 𝑋 = (𝑋1 , . . . , 𝑋𝑚 )T , компоненты которого принимают значения в поле F𝑞 . Определение 4.1.1. [15] Обозначим за 𝜏 = (𝑡1 , . . . , 𝑡𝑘 ) ⊆ (1, . . . , 𝑚) 𝑘-подмножество из 𝑚 натуральных чисел. Зададим вектор-строку 𝐴𝜏 = (𝑎1 , . . . , 𝑎𝑚 ), где 𝑎𝑖 = 1, если 𝑖 ∈ 𝜏 , иначе 𝑎𝑖 = 0. Линейная комбинация вида 𝑋𝜏 = 𝐴𝜏 𝑋 (mod 𝑞) называется симптомом ранга 𝑘. Определение 4.1.2. [15] Пусть имеется 𝑘 + 1 симптомов 𝑋0 , . . . , 𝑋𝑘 . Совокупность 𝑞 𝑘+1 − 1 симптомов вида 𝛽0 𝑋0 + · · · + 𝛽𝑘 𝑋𝑘 (mod 𝑞), где 𝛽𝑖 ∈ F𝑞 не равны нулю одновре менно, называется синдромом 𝑘-го порядка. Разберем связь между грассманианом и понятиями симптома и синдрома. Рас смотрим частный случай 𝑞 = 2. Набор из 𝑚 различных линейно независимых векто ров (𝑋1 , . . . , 𝑋𝑚 ) над полем F2 является базисом некоторого 𝑚-мерного пространства 𝑉𝑚 = (F2 )𝑚 . Любой вектор этого пространства можно разложить по базису в виде ли нейной комбинации 𝑋𝜏 = 𝑎1 𝑋1 + · · · + 𝑎𝑚 𝑋𝑚 , где 𝑎𝑖 — элементы поля F2 и 𝜏 = {𝑎𝑖 }𝑎𝑖 ̸=0 . Получаем, что векторы этого 𝑚-мерного пространства — симптомы некоторого ранга. Далее рассмотрим набор полученных линейно независимых векторов (𝑋𝜏0 , . . . , 𝑋𝜏𝑘 ) как базис, который образует 𝑉𝑘 = ⟨𝑋𝜏0 , . . . , 𝑋𝜏𝑘 ⟩ 𝑘 +1-мерное подпространство пространства 𝑉𝑚 . Аналогично получаем, что 𝑉𝑘 — синдром 𝑘-го порядка. 4.2. Параметризация на основе рекуррентных соотношений Согласно определению синдрома 4.1.2, синдром нулевого порядка будет являться единичным симптомом. Синдром первого порядка будет состоять из трех симптомов 𝑋𝜏 , 𝑋𝜈 , 𝑋𝜏 𝜈 , где 𝑋𝜏 𝜈 = 𝑋𝜏 + 𝑋𝜈 . Эти симптомы можно считать за точки проективной прямой. Синдром второго порядка будет устроен как проективная геометрия 𝑃22 и бу дет получаться из синдрома первого порядка добавлением к нему нового признака 𝑋𝑘 и 37

симптомов, образованных линейной комбинацией синдрома первого порядка и симпто ма 𝑋𝑘 . Аналогично по индукции получаем, что синдром 𝑘 + 1-го порядка можно задать следующим образом: 𝑆𝑘+1 = (𝑆𝑘 , 𝑋𝑖 , 𝑆𝑘 + 𝑋𝑖 (mod 2)), 𝑋𝑖 ∈ / 𝑆𝑘 . (4.1) При этом симптом, стоящий на месте 2𝑖 в синдроме 𝑆𝑘 будем называть базовым. Таким образом получили последовательность синдромов, построенных в конечном по ле в результате рекуррентных соотношений типа Фибоначчи. На основании этого мож но предположить возможность использования cпособа выращивания конечных подпро странств на основе рекуррентных соотношений для параметризации грассманиана. Для проверки этого предположения введем несколько понятий. Введем понятие согласованности линейного порядка с флагом 3.2.2. Определение 4.2.1. Отношение линейного порядка ≺ на 𝑉𝑚 = (F𝑞 )𝑚 согласовано с флагом 𝐹 , если для ∀𝑖 = (0, 1, . . . , 𝑚 − 1) и 𝑣 ∈ 𝑉𝑖 , 𝜔 ∈ 𝑉𝑚 ∖ 𝑉𝑖 имеет место 𝑣 ≺ 𝜔. Введем понятие дизайна. Определение 4.2.2. [15] Дизайн 𝐷(𝑣, 𝑏, 𝑟, 𝑘, 𝜆) — размещение 𝑣 элементов по 𝑏 блокам, каждый элемент встречается 𝑟 раз, блоки размера 𝑘, а каждая пара встречается 𝜆 раз. При этом выполняется 𝑣𝑟 = 𝑏𝑘, 𝑟(𝑘 − 1) = 𝜆(𝑣 − 1). Дизайн называется симметричным, если 𝑣 = 𝑏, 𝑟 = 𝑘. Обозначается 𝐷(𝑣, 𝑘, 𝜆). Дизайн называется каноническим над полем 𝐹𝑞 , если в блоках сумма элементов над 𝐹𝑞 равна нулю. Обозначается 𝐷0 (𝑣, 𝑏, 𝑟, 𝑘, 𝜆|𝐹𝑞 ). Синдром 𝑆𝑛−1 можно описывать как проективную геометрию с точками-симпто мами, так и как структуру симметрий 𝑛-мерной аффинной геометрии в виде канониче ского дизайна над 𝐹2𝑛 . Согласно теореме Зингера [15] гиперплоскости геометрии 𝑃𝑞𝑛 , 𝑞 = 𝑝𝑟 , взятые в каче стве блоков, и точки, взятые в качестве элементов, образуют симметричный дизайн 𝐷𝑛 = 𝐷(𝑘𝑛 , 𝑘𝑛−1 , 𝑘𝑛−2 ), где 𝑘𝑛 = (𝑞 𝑛 − 1)/(𝑞 − 1). Как получить дизайн через синдромы? Рассмотрим на примере синдромов первого и второго порядков. В качестве множества элементов примем синдром 𝑆2 , в качестве бло ков — синдром 𝑆1 , тогда получится канонический дизайн 𝐷(7, 3, 1|𝑆2 ). Канонические дизайны можно построить, используя метод интегрирования дизайнов [15], 38

основанный на многократных отражениях конечных геометрий в пространствах боль шей размерности. Операция интегрирования является индуктивной и начинается с ба зы индукции, которой является проективная прямая 𝑃𝑞1 , которая представима в виде вырожденного дизайна 𝐷(𝑞 + 1, 1, 0). Переход будет осуществляться на основе рекур рентного соотношения типа Фибоначчи, то есть 𝜑𝑗+1 = 𝜑𝑗 + 𝛼𝜑𝑗−1 , где 𝜑𝑗 принадлежит множеству точек 𝑃𝑞𝑛 как элементов дизайна 𝐷𝑛 , которое обозначим за Ω𝑛𝑞 . Начальными условиям для рекуррентной последовательности будет являться 𝜑0 ∈ Ω𝑞𝑛−1 и 𝜑1 ∈ Ω𝑛𝑞 , при 𝑗 = 2, . . . , 𝑛. По а параметр рекуррентности 𝛼 выбирается так, что 𝜑𝑗 ∈ Ω𝑛𝑞 ∖ Ω𝑛−1 𝑞 следовательность 𝜑𝑗 будет импульсной, а набор [𝜑1 , . . . , 𝜑𝑞 ] будем называть импульсным модулем 𝜋(𝜑0 |𝜑1 ), и соответственно для блока 𝐵 = [𝑥1 , . . . , 𝑥𝑘 ] 𝜋(𝐵|𝜑1 ) — импульсным модулем блока. Тогда для любого блока 𝐵 = [𝑥1 , . . . , 𝑥𝑘 ], 𝑥𝑖 ∈ Ω𝑞𝑛−1 дизайна 𝐷𝑛−1 су ществует разбиение Ω𝑛𝑞 ∖ Ω𝑛−1 при помощи некоторого набора векторов {𝑦}, такое, что 𝑞 импульсные модули блока относительно этого набора не будут пересекаться, а в сумме будут давать само множество. Тогда блоки вида [𝐵, 𝜋(𝐵𝑖 |𝑦𝑗 )] вместе с блоком из элемен тов Ω𝑛−1 образуют соответствующий 𝑃𝑞𝑛 дизайн 𝐷𝑛+1 , а блоки 𝜋(𝐵𝑖 |𝑦𝑗 )] — канонический 𝑞 дизайн, соответствующий евклидовой геометрии 𝐸𝑞𝑛 . Теперь остается выбрать базовые симптомы для синдрома 𝑆𝑛 . Всевозможные вариан ты будут исчерпываться группой, изоморфной группе автоморфизмов 𝑃𝑞𝑛 . Для дизайна 𝐷𝑛−1 , 𝑞 = 2 это будет группа 𝑆𝐿𝐹𝑛2 невырожденных матриц 𝑛 × 𝑛 над полем 𝐹2 порядка (𝑞 𝑛 −1) . . . (𝑞 𝑛 −𝑞 𝑛−1 ). Матрица этой группы 𝐴 будет состоять из 𝑛 ненулевых 𝑛-столбцов над 𝐹2 , соответствующих элементам поля 𝐹𝑞 и ни один из векторов не будет являться линейной комбинацией других. Таким образом параметризацию грассманиана можно будет задать отображением из множества исходных векторов в произведение матрицы 𝐴 на соответствующий векторам дизайн. Теорема 4.2.1. Порядок на основе рекуррентных соотношений несогласован с полным флагом на пространстве 𝑉𝑚 = (F𝑞 )𝑚 . Доказательство. Зададим базис пространства 𝑉𝑚 как набор ⟨𝑋1 , . . . , 𝑋𝑚 ⟩. Зададим базис подпространтсва 𝑉𝑘 как набор ⟨𝑋𝜏1 , . . . , 𝑋𝜏𝑘 ⟩, где 𝑋𝜏𝑖 , 𝑖 = (1, . . . , 𝑘) — линейная комбинация над векторами из базиса пространства. Зададим полный флаг на пространстве 𝑉𝑚 : 𝑉0 = {0} ⊂ 𝑉1 = ⟨𝑋1 ⟩ ⊂ · · · ⊂ 𝑉𝑚 = ⟨𝑋1 , . . . , 𝑋𝑚 ⟩. 39

Выбор такого полного флага даёт возможность определить точное соответствие между клеточным разбиением Грассманиана и клеточными матрицами вида 3.1. Зафиксируем вектор 𝑡, содержащий коэффициенты 𝑎𝑖 матрицы 3.1, притом для некоторого индекса 𝑘 коэффициент 𝑎𝑘 = 1, после него идут нули, а до него любые элементы из поля F𝑞 . Очевидно, что этот вектор будет удовлетворять виду клеточной матрицы разбиения, а значит 𝑡 ∈ 𝑉𝑘 ∖ 𝑉𝑘−1 . Однако при рассмотрении других векторов в 𝑉𝑘 ∖ 𝑉𝑘−1 появится проблема в невозможности перестановки в порядке, определенном рекуррентными со отношениями, без нарушения согласованности с флагом, поскольку найдется элемент 𝑣 ∈ 𝑉𝑖 и 𝜔 ∈ 𝑉𝑚 ∖ 𝑉𝑖 , при котором будет выполняться 𝜔 ≺ 𝑣, что противоречит опреде лению 4.2.1. Таким образом, получаем, что метод неприменим в связи с отсутствием согласо ванности такого порядка с флагом. 40

Глава 5 Приложения 5.1. Применение точного критерия Фишера Рассмотрим группу больных с заболеваниями щитовидной железы. Им проводи лась операция по удалению части или всей железы. Требуется рассмотреть зависимость вероятности рецидива от методов лечения и протекания болезни. Факторы: ∙ Объем операции — ТЭ (тиреоидэктомия — полное удаление ткани щитовидной железы), либо ТЭ + ЦЛ, либо ТЭ + ЦЛ + БЛ. ∙ РЙТ — радиойодтерапия. Радиойодтерапия применяется при лечении тиреотокси коза, сопровождающего диффузный токсический зоб, автономно функционирую щие аденомы. Радиоактивный йод также используют при лечении дифференциро ванного рака щитовидной железы в качестве дополнительного метода и/или при терапии рецидивов заболевания (повторное заболевание), регионарных и отдален ных метастазов после хирургического этапа. ∙ НИС проточник (в %) — натрий/йод симпортер. Этот белок модифицирует транс порт йода не только в щитовидную, но и в лактирующую молочную железу, а также в некоторые другие ткани. Его вариабельная экспрессия характерна и для рака щитовидной железы, и для рака молочной железы. НИС рассматривается как потенциальный переносчик циторедуктивных препаратов в ткань рака щито видной железы и может использоваться в диагностике этого заболевания. ∙ BRAF — это ген, который вместе с рецепторами эпидермального фактора роста (EGFR) отвечает за один из сигнальных путей в клетке. В нормальной клетке сигнальный путь находится в неактивном состоянии, поскольку факторы роста связаны со своими рецепторами EGFR. При развитии мутации патологический ген начинает продуцировать активированный белок. Этот белок запускает меха низм избыточного переноса сигнала к факторам роста. Результатом является в несколько раз ускоренное размножение клеток и рост новообразования. 41

∙ Стадии. Определение стадии – это способ описания рака, т.е. определение его ло кализации, распространения и влияния на функции других органов тела. Врачи используют диагностические тесты для определения стадии рака, поэтому до окон чания всех тестов определение стадии не может быть завершено. Знание стадии помогает врачу определить наиболее подходящий вид лечения и сделать прогноз выздоровления. Существуют различные описания стадий при различных видах рака. Одним из инструментов определения стадии является система TNM. Эта система использует для оценки стадии рака три критерия: саму опухоль, близле жащие лимфоузлы и распространение опухоли на другие части тела. Для опре деления стадии рака результаты объединяются. Существуют пять стадий: стадия 0(нулевая стадия) и стадии I – IV. Стадия даёт возможность общего способа опи сания рака и совместной работы врачей для наилучшего планирования лечения. TNM – аббревиатура от T(опухоль), N(узел) и M(метастазы). Врачи рассматри вают три эти фактора для определения стадии рака: 1. Насколько велика первичная опухоль и где она расположена? ( Опухоль, T) 2. Распространилась ли опухоль на лимфоузлы? (Узел, N) 3. Есть ли метастазы рака в других частях тела? (Метастазы, M) ∙ Появление рецидива. ∙ Время наступления рецидива. Основные факторы риска: мутация гена BRAF, стадии заболевания и НИС проточник, поэтому необходимо ответить на следующие вопросы: 1. есть ли зависимость между уровнем НИС (в %) и положительным BRAF стату сом? 2. есть ли зависимость НИС (в %) от T-стадии? 3. есть ли зависимость НИС (в %) от N-стадии? 4. есть ли зависимость стадии болезни от наличия мутации BRAF? 5. зависит ли время наступления рецидива от уровня НИС (в %)? 42

6. чаще ли наступает рецидив у больных с положительным BRAF и низким НИС (1% и менее) по сравнению с остальными? Определять зависимость будем с помощью точного критерия Фишера и соответствую щей программы SPSS. Будем отвечать на данные вопросы по порядку. Уровень НИС (в %) разобьем на 4 категории: низкий (≤ 1%), средний (1% – 5%), крупный (5% – 10%) и высокий (≥ 10%). На основании полученных данных составим таблицы сопряженности для ответов на вопросы выше, после чего их проанализируем. Пусть точное 𝑝-значение > 0.05, тогда будем считать факторы независимыми, в противном случае будет доказана существенная зависимость. Основываясь на анализе этих таблиц сопряженности (таблицы 2.3 – 5.7) можем прийти к следствию о том, что факторами, влияющими на наличие рецидива, являются: T-стадия, уровень НИС и объем проведенной операции, при этом также близка к зависимости мутация BRAF и T-стадия. Таким образом можно сделать вывод о том, что ключевые факторы риска — это мутация BRAF и уровень НИС, но при корректной операции и правильной оценке начальной стадии рецидива болезни можно избежать в большинстве случаев. Ниже в таблицах 5.1 – 5.7 представлены результаты, полученные моей программой, и также для сравнения приведены результаты выполнения аналогичной программы в SPSS Statistics. Таблица 5.1. Таблица сопряженности BRAF и T-стадии BRAF/Т-стадия 1 норма 12 5 3 1 21 мутантный 16 0 3 3 22 Итого 28 5 6 4 43 43 2 3 4 Итого

Таблица 5.2. Сравнение BRAF и T-стадии в SPSS Точный критерий Фишера 0.088 Хи-квадрат Пирсона 0.096 Отношение правдоподобия 0.085 Таблица 5.3. Таблица сопряженности BRAF и N-стадии BRAF/N-стадия 0 1 Итого норма 13 8 21 мутантный 8 14 22 Итого 21 22 43 Таблица 5.4. Сравнение BRAF и N-стадии в SPSS Точный критерий Фишера 0.131 Хи-квадрат Пирсона 0.131 Отношение правдоподобия 0.131 Таблица 5.5. Таблица сопряженности объема операции и наличия рецидива Объем/Рецидив нет есть Итого ТЭ 8 4 12 ТЭ + ЦЛ 19 0 19 ТЭ + ЦЛ + БЛ 6 6 12 Итого 33 10 43 44

Таблица 5.6. Сравнение объема операции и наличия рецидива в SPSS Точный критерий Фишера 0.001 Хи-квадрат Пирсона 0.006 Отношение правдоподобия 0.001 Таблица 5.7. Таблица полученных моей программой значений Сравнение Значение точного критерия Фишера НИС и Т-стадия 0.7509 BRAF и Т-стадия 0.0871 BRAF и N-стадия 0.1308 Объем операции и наличие рецидива 0.0007 45

Заключение Результатом выполнения бакалаврской работы стало детальное изучение точного критерия Фишера для различных размерностей, составлены программы для частных случаев 2 × 2, 2 × 3, 2 × 4, 3 × 3 размерностей таблиц сопряженности, в дальнейшем обоб щенные на общий случай таблиц 𝑟 × 𝑐. Изучено применение грассманиана в задачах статистики, понятия симптома, синдрома, их взаимосвязь и применение. Реализован алгоритм быстрого перечисления точек грассманиана с выбором наилучшего синдро ма. Рассмотрен альтернативный способ перечисления точек грассманиана, основанный на перечислении диаграмм Юнга. Обе программы применены на реальных данных и на их основе сделан вывод о значимых факторах, влияющих на исход болезни, а также выявлена взаимосвязь между исходными симптомами болезни, лечением и послеопера ционными осложнениями. 46

Литература 1. Agresti A. Categorical data analysis // New York: Wiley. –– 1990. 2. Mehta C. R., Patel N. R. –– IBM SPSS Exact tests. –– IBM Corporation, 2011. 3. Suzukiyz T., Aokiyx S., Murotay K. Use of primal - dual technique in the network algorithm for two - way contingency tables // Japan Journal of Industrial and Applied Mathematics. –– 2004. –– Vol. 22. –– P. 133–145. 4. Verbeek A. A survey of algorithms for exact distributions of test statistics in r x c contingency tables with fixed margins // Computational Statistics and Data Analysis. –– 1985. –– Vol. 3. –– P. 159–185. 5. URL: http://www.statisticshowto.com/tables/z-table/. 6. URL: http://www.sigmazone.com/binomial_confidence_interval.htm. 7. Mehta C., Patel N. A network algorithm for performing fisher’s exact test in 𝑟 × 𝑐 contingency tables // Journal of the American Statistical Association. –– 1983. –– Vol. 78:382. –– P. 427–434. 8. Pagano M., Halvorsen K. An algorithm for finding the exact significance levels of 𝑟 × 𝑐 contingency tables // Journal of the American Statistical Association. –– 1981. –– Vol. 78. –– P. 427–434. 9. Smith P., Forster J., McDonald J. Monte carlo exact tests for square contingency tables // Journal of the Royal Statistical Society A. –– 1996. –– Vol. 159. –– P. 309–321. 10. Yates F. Contingency tables involving small numbers and the 𝜒2 test // Journal of Royal Statistical Society, Supplementary. –– 1934. –– Vol. 1. –– P. 217–235. 11. Ананьевская П. В. Исследование конечно-линейных статистических моделей, опти мизация и избыточность : дис. на соискание степени к. ф.-м. н. / П. В. Ананьевская ; С. - Петербургский государственный университет. — 2013. — 142 с. 12. Гриффитс Ф., Харрис Д. Принципы алгебраической геометрии. — Мир, 1982. 13. Городенцев А. Л. Алгебра-1. — МЦНМО, 2011. — С. 526. 47

14. Казарян М. Э. Введение в теорию когомологий. — МИАН, 2006. — Т. 3. — С. 106. 15. Алексеева Н. П. Анализ медико-биологических систем // Издательство С. - Петер бургского университета. — 2012. — 185 с. 48

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв