Содержание к диссертации
Введение
1 Основные понятия и обозначения 17
1.1 Статистические решающие функции 17
1.2 Метод минимизации эмпирического риска 18
1.2.1 Постановка задачи классификации с учителем . 18
1.2.2 Емкость класса решающих функций 20
1.3 Метод структурной минимизации эмпирического риска . 24
1.3.1 Описание метода 24
1.3.2 Метод кросс-проверки 27
1.4 Индуктивное построение баз знаний. Подход КЕХ 29
1.4.1 Терминология и обозначения 29
1.4.2 Определение базы знаний 31
1.4.3 Алгоритм КЕХ 33
1.4.4 Базы знаний и решающие функции 35
1.5 Статистические критерии проверки гипотез 37
1.5.1 Критерий согласия %2 37
1.5.2 Критерий однородности %2 38
1.5.3 Критерий знаков 39
1.6 Упорядочение признаков. Алгоритм ReliefF 39
1.7 Дискретизация непрерывных признаков 42
1.7.1 Постановка задачи дискретизации и терминология . 42
1.7.2 Алгоритм дискретизации системы КЕХ 44
1.7.3 Алгоритм дискретизации ChiMerge 47
1.7.4 Алгоритм дискретизации САШ 49
1.7.5 Алгоритм дискретизации TSE 50
Индуктивное построение баз знаний 52
2.1 Процедуры генерации комбинаций 53
2.1.1 Построение баз знаний по возрастанию длины антецедента 53
2.1.2 Построение баз знаний по возрастанию количества наиболее информативных признаков антецедента 60
2.2 Поиск оптимального класса решающих функций 63
2.2.1 Схемы реализации метода структурной минимизации эмпирического риска 63
2.2.2 Нахождение оптимального класса решающих функций по возрастанию длины антецедента . 67
2.2.3 Нахождение оптимального класса решающих функций по возрастанию количества наиболее информативных признаков антецедента 76
Предварительная обработка обучающей выборки 79
3.1 Нахождение множества наиболее информативных признаков 80
3.1.1 Постановка задачи 80
3.1.2 Пошаговый алгоритм нахождения множества наиболее информативных признаков 81
3.1.3 Результаты вычислительных экспериментов . 85
3.2 Дискретизация непрерывных признаков 91
3.2.1 Постановка задачи 91
3.2.2 Алгоритм ChiSplit 92
3.2.3 Результаты вычислительных экспериментов 97
3.3 Система СТАТКОП 99
3.3.1 Описание системы СТАТКОП 99
3.3.2 Определение факторов риска в кардиологии . 100
3.3.3 Проективные стратегии и современный
потенциал сельских домохозяйств Карелии 102
4 Индуктивное построение баз знаний статистических экспертных систем 105
4.1 Наилучшие совместные критерии 106
4.1.1 Постановка задачи 106
4.1.2 Наилучшие двусторонние статистические критерии 108
4.1.3 Использование эмпирической информации о возможных альтернативах для построения совместных статистических критериев 113
4.2 Использование частичной априорной информации для построения двусторонних критериев 116
4.2.1 Постановка задачи 116
4.2.2 Псевдонаилучшие двусторонние критерии 118
4.2.3 Интерактивное назначение априорного распределения 121
4.2.4 Алгоритм интерактивного построения
псевдонаилучших двусторонних критериев 122
Заключение 126
Литература
- Постановка задачи классификации с учителем
- Построение баз знаний по возрастанию количества наиболее информативных признаков антецедента
- Пошаговый алгоритм нахождения множества наиболее информативных признаков
- Использование эмпирической информации о возможных альтернативах для построения совместных статистических критериев
Введение к работе
Одним из наиболее успешно развивающихся направлений в области искусственного интеллекта и первым, нашедшим широкий выход в различные области человеческой деятельности (наука, техника, медицина, геология и многие другие), являются экспертные системы (ЭС). Ключевой проблемой в теории и практике современных ЭС является проблема построения ее базы знаний (БЗ) [23, 22]. На современном этапе (примерно в последние 15-20 лет) развития технологии ЭС широкое распространение получила парадигма построения БЗ непосредственно из данных, возможно с минимальным участием эксперта. Процесс приобретения знаний непосредственно из данных носит название индуктивного обучения [71]. Преимущества такого подхода состоят в том, что он позволяет (при наличии обучающей выборки достаточного объема) в кратчайшие сроки и с минимальными затратами осуществлять построение БЗ [42]. Поэтому разработка методов и алгоритмов индуктивного построения БЗ в настоящее время представляет собой чрезвычайно актуальную задачу как в теоретическом, так и в прикладном плане.
Отечественные работы в области индуктивного обучения ведутся с 50-х годов и в значительной степени связаны с работами Новосибирской математической школы по машинному обнаружению закономерностей (Вапник В.Н., Червоненкис Л.Я., Загоруйко Н.Г., Лбов Г.С. и другие [11, 14,15]). Большое влияние на развитие исследований в этой области оказали отечественные алгоритмы "Кора" [8, 6] и алгоритм метода "обобщенного портрета" [9]. Под влиянием этих идей в Отделе математических методов Карельского научного центра в начале 90-х годов была разработана система "СПОР" [7], предназначенная для автоматизации
поиска регрессионных закономерностей.
В качестве моделей представления знаний, применяемых при индуктивном построении БЗ, в настоящее время широко используются нейронные и байесовские сети [86, 49, 87], деревья решений и регрессий (классическими считаются алгоритмы семейства TDITD [77], на основе которых были разработаны программы индуктивного обучения С4 [79], CART [43] и ASSISTANT [44]), модели, основанные на теории нечетких множеств [34] и системы правил различного типа. Системы правил обладают рядом достоинств по сравнению с другими моделями представления знаний:
правила легко интерпретируются ввиду их синтаксической формы и высокой модульности [45] (отдельное правило может быть легко понято вне контекста других правил) и, вследствии этого, широко используются для представления знаний в ЭС [23, 22];
определенные типы априорной информации легко могут быть встроены в алгоритмы индуктивного обучения систем правил [75];
как неоднократно отмечалось многими исследователями, системы правил, как инструмент классификации, часто обеспечивают точность, сравнимую с нейронными и байесовскими сетями и обычно превосходящую точность деревьев решений (см., например, [74, 78]).
Указанные достоинства систем правил стимулировали появление направления, в рамках которого разрабатываются алгоритмы преобразования нейронных и байесовских сетей, деревьев решений в системы правил для их дальнейшего использования в БЗ [57, 55]. Наиболее известные алгоритмы индуктивного построения систем правил AQ [72] и CN2 [48], ориентированы на извлечение правил в ситуациях, когда существуют детерминированные зависимости между набором входных признаков и классовым признаком.
Рассматриваемые в диссертации системы правил ориентированы на представление стохастических зависимостей и, по существу, могут рас-
сматриваться как некоторый классификатор. Известно, что статистические свойства классификатора существенно зависят от множества (класса) решающих функций (р.ф.); среди которых ищется классификатор. Чем шире класс решающих функций (к.р.ф.), тем меньшим будет эмпирический риск, т.е. частота ошибок, совершаемых классификатором на обучающей выборке. Однако, чрезмерное расширение к.р.ф. (не сбалансированное с объемом обучающей выборки) приводит к тому, что качество работы классификатора на новых данных (не вошедших в обучающую выборку) может быть плохим, несмотря на малость эмпирического риска. Этот эффект является отражением общего явления, известного как переподгонка (overfitting) и проявляющегося в самых различных областях статистики (регрессионный1 и ковариационный анализы, анализ временных рядов и др.). Суть переподогонки заключается в том, что вероятностно-статистическая модель, построенная по некоторой выборке, фактически описывает только саму эту выборку и непригодна в качестве модели всей рассматриваемой генеральной совокупности. Проблеме переподгонки посвящена обширная литература (см., например [18, 83, 84]).
Среди наиболее значительных подходов к решению проблемы переподгонки можно выделить информационный критерий Акайка (AIC) [35], байесовский информационный критерий Шварца (BIC) [82], принцип описания минимальной длины Риссанена (MDL) [80]. Большой теоретический вклад в развитие этого направления внес А.Н. Колмогоров, разработавший теорию сложности функций [19].
Один из подходов в борьбе с переподгонкой (в задачах классификации) заключается в определении оптимального (в некотором смысле) к.р.ф., среди которых ищется классификатор. Важным достижением в этой области стал развитый в работах Вапника В.Н. и Червоненкиса Л.Я. [10,11]
классическим случаем переподгонки является построение полиномиальной регрессионной модели, точно описывающей наблюденную зависимость между откликом и независимой переменной, но бесполезной для прогнозирования
метод минимизации эмпирического риска (ММЭР). Введенное ими понятие емкости, как меры разнообразия к.р.ф. (получившее название размерности Вапника-Червоненкиса), позволило определить необходимые и достаточные условия состоятельности ММЭР и дать оценку объема обучающей выборки, необходимой для осуществления классификации с заданной точностью для наименее благоприятного распределения. Развитием ММЭР является метод структурной (упорядоченной) минимизации эмпирического риска (МСМЭР) [11], позволяющий сбалансировать емкость к.р.ф. и объем обучающей выборки.
В середине 90-х годов в работах [39, 61] был представлен индуктивный алгоритм и описана система Knowledge EXplorer (КЕХ) предназначенная для автоматизации построения БЗ с представлением знаний в виде систем правил вида "ЕСЛИ (УСЛОВИЕ) ТО (СЛЕДСТВИЕ) С ВЕСОМ (Wy\ аналогичным использовавшимся в классических ЭС PROSPECTOR [53, 54] и MYCIN [85]. Алгоритм КЕХ обеспечивает формирование БЗ по обучающей выборке, признаки которой измерены в номинальной шкале, без поддержки эксперта. Условие, или антецедент правила представляет собой конъюнкцию элементов вида "признак = значение" {комбинацию) значений некоторых признаков, называмых входными1, следствие представляет собой указание назначение (уровень) некоторого выделенного признака, называемого классовым, а вес правила является количественной мерой влияния условия на частоту значения классового признака входящего в следствие. Заметим, что такие БЗ фактически представляют собой вероятностно-статистическую модель наблюдаемого явления, построенную по обучающей выборке и индуцирующую некоторый классификатор. Алгоритм КЕХ, по видимому, является единственным алгоритмом, предназначенным для построения БЗ
указанного вида. Важным достоинством таких БЗ является то, что кро-
1гг.е., условие правила состоит в том, что ряд входных признаков приняли определенные значения
ме классификации они могут использоваться также в качестве инструмента статистического анализа [4]. Заметим, что алгоритм обеспечивает построение минимальных БЗ (не содержащих избыточной информации).
Существенным недостатком системы является то, что в ней отсутствуют возможности для борьбы с переподгонкой и процедура генерации комбинаций алгоритма КЕХ требует определенной модификации для использования в МСМЭР. Заметим также, что алгоритм КЕХ весьма затратен с точки зрения времени вычислений и, учитывая то, что существующие схемы реализации МСМЭР (использующие метод кросс-проверки) требуют многократного прогона этого алгоритма, вопрос разработки экономичных с точки зрения времени вычислений схем реализации МСМЭР весьма актуален. Эффективность системы снижает и отсутствие возможностей для интегрирования в процесс индуктивного обучения априорной информации об информативности признаков, позволяющее уменьшить количество правил БЗ (что важно с точки зрения робастности классификатора) без потери точности классификации. Наконец, алгоритм дискретизации непрерывных признаков, специально разработанный авторами для системы КЕХ, часто приводит к разбиению на слишком большое число интервалов (что снижает точность классификации, поскольку в каждый такой интервал попадает недостаточное для корректного применения статистических критериев количество примеров обучающей выборки) и, фактически, может использоваться только для признаков, измеренных в порядковой шкале (что отмечалось и авторами КЕХ [40]).
Второй круг вопросов, рассмотренных в диссертации связан с построением БЗ статистических ЭС. Одной из основных задач при построении таких БЗ состоит в формировании рекомендаций пользователю по выбору параметров статистических методов, наиболее подходящих в конкретной ситуации [59]. При проверке статистических гипотез важнейшим параметром является уровень значимости критерия. В диссертации
рассматривается задача выбора уровней значимости статистических критериев, совместно применяемых для проверки одной и той же нулевой гипотезы против нескольких классов альтернатив. Хорошо известно [20], что чем меньше вероятность альтернатив некоторого класса, тем меньшим должен выбираться уровень значимости соответствующего критерия в описанной выше схеме. Однако, конкретные процедуры, реализующие этот принцип на основе априорной информации того или иного вида, не разработаны, в связи с чем исследователю приходится полагаться на свой опыт и интуицию.
Связь данной тематики с задачей индуктивного построения БЗ заключается в том, что (как показано в диссертации) задача совместного применения статистических критериев при наличии обучающей выборки о возможных альтернативах может рассматриваться как задача классификации и ММЭР является состоятельным для ее решения, т.е. имеет место сходимость по вероятности риска совместного критерия, построенного на основе ММЭР, к риску наилучшего совместного критерия (понятие наилучшего совместного критерия (н.с.к.), являющегося частным случаем наилучшего критерия Большева Л.Н. [5], введено автором [27]) при неограниченном возрастании объема выборки. Другая параллель между этими направлениями состоит в том, что в обоих случаях предложены подходы, основанные на использовании частичной (неполной) информации при принятии решений.
В связи с вышесказанным целями диссертации являлись
разработка методов и алгоритмов индуктивного построения БЗ, позволяющих избеоісать эффекта переподгонки на основе МСМЭР и учитывающих априорную информацию;
разработка методов и алгоритмов построения наилучшего совместного критерия, при наличии информации о возмооюных альтернативах.
В соответствии с данными целями предметом исследований являлись процедуры генерации комбинаций и индуктивные алгоритмы построения БЗ, схемы реализации МСМЭР, методы и алгоритмы нахождения и упорядочения множества наиболее информативных признаков и дискретизации, статистические критерии проверки гипотез и методы назначения априорных распределений. Основными методами исследований являлись вероятностные и статистические методы, в частности методы байесовской и робастной статистики. При сравнении качества алгоритмов дискретизации и алгоритмов поиска и упорядочения множества наиболее информативных признаков использовалась методика эмпирического сравнения соответствующих индуктивных алгоритмов на реальных задачах из коллекции (репозитария) задач Калифорнийского университета [73]. Заметим, что такой подход является общепринятым в области индуктивного обучения (см., например, [50]).
Диссертация состоит из введения, четырех глав, заключения, списка литературы и 4 приложений.
Постановка задачи классификации с учителем
Пусть X = (Х\, Х2, , Хп) — случайный вектор с множеством возможных значений X и с распределением Р(х). Предполагается, что существует "учитель", который классифицирует значения св. X, т.е. относит их к одному из к классов, помеченных метками из множества D = {0,1,..., к — 1} в соответствии со значением случайной величины У, имеющей распределение Р(?/х), у Є D. Координаты вектора X будут далее называться входными признаками, а св. Y классовым признаком. Как распределение -Р(х), так и Р{у\х) неизвестны, однако известно, что они существуют, т. е. существует совместное распределение Р(х,у) = Р(х)Р(ух).
Пусть также определено некоторое множество р.ф. Т = Щх) : х Є X, а Л} , то есть при любом а Є Л функция /а(х) : X — D (параметр а может быть как скалярной, так и векторной величиной). Качество R(a) р.ф. /а(х) или риск определяется как вероятность различной классификации вектора х учителем и с помощью р.ф. /а(х): R(a) = P{Y ф /а(Х)} . (1.2) Эта величина носит также название вероятности ошибочной классификации (в.о.к.). Введем функцию %а( У) \1, У Ш-Легко видеть, что риск R(a) может быть записан в виде R(a)= J Xa(x,v)dP{x,y). (1.3) XxD Обозначим ао = arg min R(a) .
Предположим, что имеется случайная выборка V из распределения Р(х,у) объема /: Ъ = {(xi,2/i), (х2,2/2),. - -, (х/,г//)} , (1.4) называемая обучающей выборкой. Элементы обучающей выборки R( = (хі,уі), і = 1,2,...,1 называются примерами. Задача нахождения р.ф. /ао(х), минимизирующей риск (1.2) по обучающей выборке (1.4) для произвольного распределения Р(х,у), называется задачей классификации с учителем. Решающие функции /а(х) в задаче классификации с учителем мы будем далее называть также классификаторами, а отображение, сопоставляющее каждой обучающей выборке некоторый классификатор индуктивным алгоритмом. Поскольку по выборке V конечного объема невозможно точно определить величины R(a), а Є Л, то точное нахождение р.ф. /а0(х), минимизирующей риск R(a), невозможно и необходимо привлекать приближенные методы.
Одним из методов решения этой задачи является ММЭР [10, 11]. Заменим риск (1.3) функцией
1 Remp(0i) = RemP(0i, V) = - Xafc, Уі) , (1.5) «=1 построенной по обучающей выборке (1.4). Величина Remp(a): называемая эмпирическим риском, представляет собой частоту ошибочной классификации с помощью р.ф. /а(х) на обучающей выборке V. Суть ММЭР состоит в том, что в качестве р.ф. выбирается функция /Q«(x), где a = argmin#emp(a).
Теория ММЭР дает ответ на вопрос, при каких условиях имеет место сходимость по вероятности R(a ) к R(ao), т.е., когда для произвольного распределения Р(х, у) и любого є 0 Р{Д(а0) - Д(а ) є} - 0 пРи / - оо .
Известно [11], что в случае конечного числа р.ф. всегда имеет место сходимость по вероятности R{a ) к R(ao). Если же число р.ф. бесконечно, то необходима более тонкая мера разнообразия к.р.ф. Такая мера, носящая название емкости или размерности Ваппика—Червоненкиса, рассматривается в следующем подразделе.
Построение баз знаний по возрастанию количества наиболее информативных признаков антецедента
В этом подразделе приведен алгоритм (мы будем ссылаться на него как на A3), основанный на описанной в предыдущем подразделе схеме реализации МСМЭР. В алгоритме реализована также дополнительная возможность — определение оптимального режимного параметра (уровня значимости критерия, используемого для проверки статистической значимости импликаций). Алгоритм использует процедуру генерации комбинаций по возрастанию их длины (см. подраздел 2.1.1).
Индуктивные алгоритмы, как правило, содержат набор параметров, от задания которых существенно зависит качество построенных с их помощью БЗ. По этой причине при построении БЗ крайне желательно иметь статистические оценки характеристик качества БЗ хотя бы для нескольких значений основных режимных параметров рассматриваемого индуктивного алгоритма, чтобы выбрать их оптимальные значения. В рассматриваемом нами случае, как отмечалось в подразделе 1.4.4, БЗ индуцирует некоторый классификатор. Качество БЗ в этом случае определяется в.о.к. этого классификатора. Если количество данных достаточно велико, то обычным приемом для получения статистической оценки в.о.к. явля ется расщепление выборки на обучающую, используемую для построения классификатора, и тестовую, на которой проверяется качество классификатора. Если же (наиболее часто встречающаяся ситуация) данных немного, то необходимо использовать одни и те же данные для построения классификатора и для оценки его качества. В этом случае может использоваться метод кросс-проверки (см. подраздел 1.3.2). Как правило, системы для индуктивного построения классификаторов, основанных на различных моделях представления знаний (нейронные и байесовские сети, деревья решений, системы правил и т.д.), предусматривают возможность использования той или иной разновидности кросс-проверки для оценки качества построенного классификатора. Однако, вследствии высоких вычислительных затрат, использовать кросс-проверку для определения оптимальных входных параметров алгоритма (обеспечивающих минимальную, или близкую к ней в.о.к.) как правило не удается. Между тем, как показано в работе [63], посвященной использованию кросс-проверки для выбора минимального числа листьев в деревьях решений, выигрыш от такой оптимизации может быть значителен. Для индуктивных алгоритмов, описанных в предыдущем разделе такой подход оказывается осуществим, т.к. наиболее "затратные" в вычислительном отношении блоки алгоритма, отвечающие за генерацию комбинаций могут выполняться сразу для нескольких уровней значимости.
В алгоритме предусиотрена также возможность интерактивного останова алгоритма после любого количества блоков кросс-проверки. Эта возможность полезна в тех случаях, когда после визуального анализа оценок в.о.к., полученных после обработки нескольких блоков, становится ясно, что какие-то параметры алгоритма выбраны неудачно и требуется прогон алгоритма с другими параметрами. Эта возможность часто позволяет существенно сократить время построения БЗ. Блок-схема алгоритма A3 приведена на рис. 2.3.1
Отметим, что алгоритм A3 и алгоритм А4 (приведенный в следующем подразделе) Введем следующие обозначения: KB(V , L, а) — БЗ, построенная по обучающей выборке V, где L — максимальная длина антецедента правил БЗ и а — уровень значимости критерия К;
Ei(L,a) — количество ошибок, совершенных классификатором, индуцированным KB{V L, а) на і — м удаленном блоке.
Алгоритм A3 последовательно вычисляет оценки в.о.к. Pj(L,a), и их стандартное отклонение crj(L,a) по J удаленным блокам (J = 1,2,..., М, где М-число блоков кросс-проверки) для классификаторов, индуцированных KB(V,L,a). Также осуществляется оценка м.о. числа правил Nj(L,a) в JCB(V,L,a).
Пошаговый алгоритм нахождения множества наиболее информативных признаков
Приведенный в подразделе 2.2.3 алгоритм А4 позволяет интегрировать в процесс нахождения оптимального к.р.ф. априорную информацию о "степени полезности" (информативности) признаков Х\,Х2,...,Хп для классификации. Использование этой информации позволяет сократить число признаков, категории которых входят в антецеденты правил БЗ. Одной из важных причин, по которой желательно чтобы антецеденты правил БЗ содержали небольшое число признаков, являются затраты, связанные с получением информации о значениях большого числа признаков. Кроме того, это позволяет сократить число правил БЗ, что важно с точки зрения робастности соответствующего классификатора.
Априорная информация такого вида не всегда имеется в распоряжении исследователя. Тем не менее, такое упорядочение может быть осуществлено с помощью различных алгоритмов. Одним из универсальных алгоритмов такого упорядочения, хорошо зарекомендовавшим себя на практике в сочетании с рядом индуктивных алгоритмов, является алгоритм ReliefF [66, 81], описанный в разделе 1.6. В работе автора [28] рассматривался подход, основанный на предварительном упорядочении признаков обучающей выборки с использованием этого алгоритма и дальнейшем применении алгоритма А4 для выбора оптимального (в смысле МСМЭР) числа признаков. Было показано, что такая процедура часто позволяет значительно сократить количество признаков, категории которых входят в антецедент правил БЗ, и уменьшить число правил без значимого уменьшения точности соответствующего классификатора. Однако, учитывая то, что алгоритм ReliefF непосредственно не использует особенности алгоритма А4, естественно попытаться осуществить упорядочение признаков непосредственно в терминах точности классифика ции. В качестве характеристики точности классификации, учитывая то, что в основе рассматриваемых в диссертации алгоритмов лежит ММЭР, естественно использовать эмпирический риск. Предлагаемый алгоритм аналогичен пошаговой процедуре отбора множества наиболее информативных признаков в регрессионном анализе [3]. В частности, на каждом шаге алгоритма происходит либо включение, либо исключение некоторого признака из множества наиболее информативных признаков, сформированное к этому шагу. На заключительном шаге алгоритма признаки упорядочиваются в соответствии с порядком их включения в множество наиболее информативных признаков.
Обозначим через JCB(Xai,Xa2,.. . ,XaJ, оц G {1,2,..., п}, г п БЗ, содержащую правила, антецедент которых включает только категории входных признаков Ха1, Ха2,..., Хаг. Через Remp(Xai, Ха2,..., Хаг) будем обозначать эмпирический риск соответствующего классификатора. Через X будет обозначаться динамически изменяемый в процессе работы алгоритма список включенных информативных признаков, упорядоченный по очередности их включения в X (включаемые признаки помещаются в конец текущего списка). Переменная In (принимающая значения 0 и 1) используется как индикатор включения на текущей итерации алгоритма (1 - включение произошло, 0 - нет). Алгоритм заканчивает работу, если все признаки включены в X , либо невозможно ни включение, ни исключение признаков в соответствии с заданными критериями.
Описание алгоритма Вход: V — обучаюшая выборка; Ьтах — максимально допустимая длина антецедента правил; fmin, fmax, Pmin, Ртах, Qmin, Qmax Параметры, Определяющие MHO жество допустимых импликаций А; Rin — порог включения признаков; Rout — порог исключения признаков. Выход:
Список X признаков XQl,Ха2,... ,Хаг, г п, упорядоченных в порядке убывания их информативности. Описание блок-схемы алгоритма:
1. в соответствии с алгоритмом А1 строится КВ{Х\,Х2,... ,Хп). Из алгоритма построения следует, что данная БЗ включает в себя каждую БЗ, содержащую меньшее количество правил. Инициализируется список X = 0;
2. для каждого і = 1,2,..., п из JCB(Xi,X2,..., Хп) выбираются правила, антецедент которых содержит только категории признака ХІ, т.е. строится КВ{Х{). Вычисляются Remp{ i)j и в качестве наиболее информативного для классификации Y выбирается признак Х , минимизирующий эту величину, то есть г і = axgmmRemp(Xi). Признак Х помещается в список X ;
3. В качестве следующего информативного признака для классифика ции Y выбирается признак Х , і-і ф г і, минимизирующий эмпири ческий риск Remv{Xix,Xi )\
Использование эмпирической информации о возможных альтернативах для построения совместных статистических критериев
В этом подразделе рассматривается случай 9 С R1. Хорошо известно (см., например [17]), что даже для экспоненциальных распределений с монотонным отношением правдоподобия не существует равномерно наиболее мощного (р.н.м.) критерия проверки простой нулевой гипотезы 108 Щ : в = во против двусторонней альтернативы Н : в ф во. В этом случае критическая область /Са двустороннего критерия Ка с уровнем значимости /3 обычно выбирается как Ка = K, t U /С+2, где а — (cxi,a2), ot\ + 0 = (3 и /С х, /С+ критические области левостороннего и правостороннего р.н.м. критериев с уровнями значимости Q I и осі соответственно (заметим, что а фиксировано). Такой выбор оправдывается тем, что построенный таким образом критерий является р.н.м. критерием в классе всех несмещенных критериев, т.е. критериев, для которых мощность критерия при любой альтернативе не меньше уровня значимости критерия. Легко видеть, что двусторонний критерий Ка может рассматриваться как совместный критерий при т = 2, если в качестве Ki и Кг взять левосторонний и правосторонний критерии. Приведем пример наилучшего двустороннего совместного критерия. Пусть X = (Xi, Х2,... ,Хп) — случайная выборка из нормального распределения с неизвестным м.о. в и известной дисперсией а2. Обозначим через Ki р.н.м. критерий для проверки простой нулевой гипотезы Щ : в = во против левосторонней альтернативы #i : в во , и Кг р.н.м. критерий проверки той же самой нулевой гипотезы Но против правосторонней альтернативы Нч : в во. Критерии Ki и Кг определяются критическими областями [17] ; = { : ( -ад - } и а _ 1 п соответственно, где х = — ]Г) Xi, a —ta означает а-квантиль стандартного Пі=1 нормального закона, т.е. Ф(—ta) = а и
Предположим, что фиксирована верхняя граница j = о \ + 0 для уровня значимости а н.с.к. К с критической областью Ка = /С U /С 2- Заметим, что вследствии равенства /С П /С+ = 0 уровень значимости (3 в точности равен 7- Определим дискретное априорное распределение П на множестве альтернатив 0# = R1\ {0} следующим образом: ЩЄ = в1)=р1 и Щв = 92)=р2, щер\+р2 = 1 и в\ во 02 (легко видеть, что в случаях 0\ 02 9о или 0о 9\ 02 н.с.к. совпадает с критерием Кі или Кг соответственно). Не ограничивая общности, можно считать 0Q = 0, что, в целях упрощения записи, и предполагается в дальнейшем. Из соотношений (4.3) и (4.4) следует, что риск R{a) — R(U, а) в этом случае может быть записан в виде д(а) = piP ад+ / ) = = рі(Р {Х І /С" } + Рв1{Х і /С+})+
Обозначим с\ = -Q— и С2 = 2J . Учитывая, что при условии справедливости альтернативных гипотез 0 = 0І , г = 1,2 статистика ж распределена по нормальному закону с м.о. 0{ и дисперсией а2/п, легко показать, что (4.6) R(a) = рі[Ф(-сі + іу_аі)-Ф(-сі-гаі)]+ + Р2[Щ-С2 + Ц-аі)-Ф(-С2-Іаі)]. Учитывая то, что Ф( 7_аі) = 1-7 + «і и Ф(іаі) = 1 - ал , нетрудно получить, что для любого с Ф с+VaJ = /2- 7- и (0- ) = 6- /2 + .(4.7) Из (4.6) и (4.7) получаем: R ai(a) = pie_c?(eClty-ai - e_Cl i) +p2e c2(eC2Vai - е-С2 ). (4.8) Рассмотрим подробнее случай —9\ = 02 = а 0. Тогда (4.8) принимает вид: R ai(a) = pi(e_ctY- i _ e «i) +P2(ectr-ai _ e_ci«i), (4.9) где с = — - . Преобразуя выражение (4.9) и приравнивая его нулю, получаем следующее уравнение для точек экстремума функции R(a): (e c( «i + 7-оп) _ і) (piect i - р2е 7-«1) = 0. (4.10)
Поскольку, как легко видеть, первый сомножитель в (4.10) в условиях рассматриваемой задачи отличен от нуля, то уравнение (4.10) эквивалентно следующему: ai - t-r-ai = 7= ІП С4 11) ayfn р! Функция tai — t7_ai на интервале а\ Є (0,7) монотонно убывает от +оо до —со . Поэтому решение уравнения (4.11) существует и единственно. Пусть а\ решение уравнения (4.11) и а\ = j — а{. Непосредственным дифференцированием (4.8) нетрудно показать, что R a ) 0 и, таким образом, а = (а а ) точка минимума R(a). Из уравнения (4.11) следует, что при р\ — Р2 — 0.5 н.с.к. совпадает с несмещенным критерием: а\ = а\ = 0.5 . В случае рг/рі — 0 получаем а\ — 7 , OL\ — 0 и н.с.к. в пределе совпадает с левосторонним критерием. Аналогично, если Р2/Р1 — +оо, получаем в пределе правосторонний критерий. На рис. 4.1 приведены графики а\ в зависимости от 0 р\ 1 для значений параметра а равных 0.1, 0.3 и 0.5, расчитанные с помощью метода Монте-Карло. Значение дисперсии а = 1 и объем выборки п = 30. На рис. 4.2 приведены соответствующие графики для разности между риском двустороннего критерия и н.с.к. R(a ) в зависимости от р\.
