автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метод минимизации эмпирического риска при индуктивном построении баз знаний

На правах рукописи

Чистяков Сергей Павлович

МЕТОД МИНИМИЗАЦИИ ЭМПИРИЧЕСКОГО РИСКА ПРИ ИНДУКТИВНОМ ПОСТРОЕНИИ БАЗ ЗНАНИЙ

05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Петрозаводск 2006

Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН.

Научный руководитель: доктор физико-математических наук, профессор Павлов Ю.Л.

Официальные оппоненты: доктор технических наук, доцент Рогов A.A. кандидат физико-математических наук, с.н.с. Полин А.К.

Ведущая организация: Пермский государственный университет

Защита состоится " <✓ " 2006г. в часов на за-

седании диссертационного совета Д 212.190.03 в Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

С диссертацией можно ознакомиться в библиотеке Петрозаводского государственного университета.

Автореферат разослан ХиДа-рЯ 2006г.

Ученый секретарь диссертационного совета Д 212.190.03 - Поляков B.B.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Ключевой проблемой теории и практики экспертных систем (ЭС) является проблема построения баз знаний (БЗ). На современном этапе развития технологии ЭС широкое распространение получила парадигма построения БЗ непосредственно из данных. Процесс приобретения знаний непосредственно из данных носит название индуктивного обучения. Достоинства такого подхода состоят в том, что он позволяет в кратчайшие сроки и с минимальными затратами осуществлять построение БЗ. Поэтому разработка методов и алгоритмов индуктивного построения БЗ в настоящее время представляет собой чрезвычайно актуальную задачу как в теоретическом, так и в прикладном плане.

В диссертации рассматривается две проблемы. Первая состоит в индуктивном построении БЗ, использующих модель представления знаний в виде систем правил с весами, которые могут рассматриваться как некоторый классификатор. Основное внимание было уделено разработке и модификации схем реализации и алгоритмов метода структурной минимизации эмпирического риска (МСМЭР), позволяющих избежать переподгонки (оуегйМп^) — явления, хорошо известного в статистике и состоящего в том, что вероятностно-статистическая модель, построенная по некоторой выборке, фактически описывает только саму эту выборку и непригодна в качестве модели всей рассматриваемой генеральной совокупности. Актуальность этой проблематики в задаче индуктивного построения БЗ определяется тем, что переподгонка приводит к снижению качества классификатора, индуцированного построенной БЗ.

Второй круг вопросов связан с построением БЗ статистических ЭС. В диссертации рассматривается задача использования априорной информации для оптимального выбора уровней значимости статистических критериев, совместно применяемых для проверки одной и той же нулевой гипотезы против нескольких классов альтернатив. Актуальность этой задачи состоит в том, что возможный характер отклонений от нулевой гипотезы известен не всегда и, вследствии этого, не всегда можно из нескольких критериев проверки одной и той же нулевой гипотезы против различных классов альтернатив выбрать критерий, наиболее подходящий в конкретной ситуации. Поэтому для повышения достоверности статистических выводов часто приходится осуществлять проверку нулевой г то несколь-

ким статистическим критериям, что расширяет область альтернатив и позволяет минимизировать количество ошибок второго рода.

Цель исследования. Целью диссертации являлась разработка методов и алгоритмов индуктивного построения БЗ на основе МСМ-ЭР, позволяющих избежать эффекта переподгонки и учитывающих априорную информацию, а также разработка методов и алгоритмов построения наилучшего совместного критерия при наличии информации о возможных альтернативах.

Объекты исследования. Объектом исследований были индуктивные алгоритмы построения БЗ, схемы реализации МСМЭР, методы и алгоритмы нахождения и упорядочения множества наиболее информативных признаков, статистические критерии проверки гипотез и методы назначения априорных распределений.

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

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

Основные положения диссертации, выносимые на защиту. На защиту выносятся:

1. Схемы реализации МСМЭР и соответствующие алгоритмы, использующие частичную информацию о качестве классификаторов, индуцированных последовательностью минимальных БЗ.

2. Алгоритмы предварительной обработки обучающей выборки, ориентированные на индуктивное построение БЗ.

3. Методы и алгоритмы построения наилучшего совместного кри-

терия при наличии априорной, частичной априорной или эмпирической информации о возможных альтернативах.

4. Комплекс программ индуктивного построения БЗ и результаты его применения при решении задач кардиологии и социологии.

Связь работы с крупными научными программами, темами. Результаты диссертации получены в рамках двух научно-исследовательских тем Института прикладных математических исследований Карельского научного центра РАН: "Исследование и разработка методов создания интеллектуальных систем статистического анализа данных" (К'гос. регистрации 01.9.80009162) и "Разработка методов исследования случайных структур и их применения при принятии статистических решений" (№гос. регистрации 01.200.202223). В 19971998 годах работа по теме диссертации была поддержана грантом РФФИ №97-01-00554 "Моделирование процесса принятия решений при выборе методов статистического анализа".

Апробация результатов диссертации. Основные результаты работы докладывались на Шестой научной конференции стран СНГ "Применение многомерного статистического анализа в экономике и оценке качества продукции" (Москва, 1997г.), Юбилейной научной конференции Карельского научного центра Российской академии наук посвященной 275-летию РАН (Петрозаводск, 1999г.), Пятой Петрозаводской международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2001г.), четвертом Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003г.) и на Ученом совете Института прикладных математических исследований Карельского научного центра РАН.

Публикация результатов. Основные результаты диссертации опубликованы в двенадцати работах, из них: одна статья в центральном журнале, две статьи в сборниках трудов международных конференций, шесть статей в сборниках трудов Института прикладных математических исследований КарНЦ РАН и Петрозаводского государственного университета.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, списка литературы, заключения и четырех приложений. Общий объем диссертации составляет 142 страницы. Список литературы содержит 87 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава носит вспомогательный характер. В ней приведены определения основных понятий и описаны методы и алгоритмы, использующиеся в последующих главах: статистические решающие функции (р.ф.)> метод минимизации эмпирического риска (ММЭР) и МСМЭР, кросс-проверка, дается определение БЗ, используемое в диссертации, описаны статистические критерии, алгоритмы дискретизации и упорядочения признаков.

Пусть X = (Xi, Х2, ■ . •, Хп) — случайный вектор с множеством возможных значений X и с распределением Р(х). Предполагается, что существует "учитель", который классифицирует значения X, т.е. относит их к одному из к классов, помеченных метками из множества £> = {0,1,...,А-1} в соответствии со значением случайной величины (с.в.) У, имеющей распределение Р(у\х), у е D. Координаты вектора X называются входными признаками, а с.в. Y классовым признаком. Распределения Р(х) и Р(у|х) неизвестны, однако известно, что они существуют, т. е. существует совместное распределение Р(х, у) = Р(х)Р(у|х). Пусть также определено некоторое множество р.ф. Т = {fa(х) : х € X, а € Л} , то есть при любом а € Л функция /а(х) : X —у D. Качество R(a) р.ф. /а(х) или риск определяется как вероятность различной классификации вектора х учителем и с помощью р.ф. /а(х), а именно Ща) — Р{Y ф /а(Х)} . Эта величина носит также название вероятности ошибочной классификации (в.о.к.). Обозначим с*о = argmina€A Ä(°0 и предположим, что имеется случайная выборка V = {(xi, 3/1), (х2, у2)> • • • > (хь Ui)} из распределения Р(х,у) объема I, назьгоаемая обучающей выборкой. Задача нахождения р.ф. /Qo(x), минимизирующей риск R(a) по обучающей выборке V для произвольного распределения Р(х, у), называется задачей классификации с учителем. Решающие функции fa (х) в задаче классификации с учителем называются также классификаторами, а отображение, сопоставляющее каждой обучающей выборке некоторый классификатор, индуктивным алгоритмом. Одним из методов приближенного нахождения fao (х) является ММЭР. Обозначим

Ха (*) У) j

Заменим риск Д(а) его оценкой (эмпирическим риском):

•Йетр(а) = Яетр{а,Т)) = у Уг)-

1=1

Суть ММЭР состоит в том, что в качестве р.ф., приближающей }ао (х), выбирается функция /а. (х), где

Развитием ММЭР является МСМЭР. Пусть имеется набор классов р.ф. (к.р.ф.) Тг = {/0(х) : х € X, а € А,}, » = 0,1,..., ЛГ, таких, что То с С Т2 С ... С Тм и Ф — некоторый функционал, определенный на множестве р.ф. Ты, т.е. Ф : Ты —* Я1- Пусть (х) — р.ф., минимизирующая эмпирический риск в классе Тг. Тогда

определяет номер к.р.ф., оптимальный с точки зрения МСМЭР, а р.ф. /<*• (х) представляет собой оптимальный классификатор по МСМЭР. Функционал Ф, рассматриваемый в диссертации, сопоставляет р.ф. /„(х) статистическую оценку в.о.к. Я(а), получаемую при помощи метода блочной кросс-проверки.

В диссертации рассматривается частный случай задачи классификации с учителем, в котором входные признаки Х\, Х2,..., Хп являются дискретными с.в., принимающими конечное число значений. Упорядоченную пару "признак — значение" будем называть категорией и обозначать Хх (признак X принял значение х). Категории классового признака У обозначаются С* = Уг, г — 0,1,..., к — 1. Через С* будем обозначать произвольную категорию классового признака. Комбинацией С = Ха1ха1/з1&1,Ха1ха2р28г.. .8гХагхаг1зг , где а* = 1,2, ...,п, /Зг = 1,2,... ,Г{, г — 1,2,..., г назьгаается конъюнкция категорий, не содержащая двух одинаковых признаков, т.е. Ха< Ф Ха] при { Ф з- Длиной комбинации 1епдШ(С) ~ г назовем число включенных в нее категорий. Комбинация С\ называется подком-бинацией комбинации С2 (обозначение С\ с С2), если каждая категория из С\ также включена ив С2. Введем также пустую комбинацию С0 с нулевой длиной. По определению Т>(С°) = V и С0 с С для

а* = а^ттЛетр(а)-

абЛ

го = агй тт Ф(/а.)

г=0,1,...,Л/ •

(2)

любой комбинации С. Упорядоченную пару комбинации С и некоторой категории классового признака С* назовем эмпирической импликацией и будем обозначать С С*. Эмпирическую импликацию с приписанным ей весом т е (0,1) будем называть правилом и обозначать С => С* (и)). Левую часть правила С будем называть антецедентом, а правую С* — консеквентом правила. Под априорными правилами понимаются правила вида С0 Множество апри-

орных правил будем обозначать 710. Для двух правил С\ С* (1и{) и С2 => С*{т2) с одинаковым консеквентом С* определена операция композиции весов ф:

№1102

М1®ы2 =-—г.-гт:-г •

и]\и}2 + (1 - - IV2)

Пусть Л некоторое множество (система) правил, содержащее все априорные правила, т.е. Но С К. Для произвольной комбинации С и категории С* определим композиционный вес \¥(С*\С,Н) как результат применения операции композиции ф к весам всех правил из Н вида С" С* (и>) , где С' с С. Обозначим через Д некоторое фиксированное подмножество множества всех импликаций. Импликации из множества Д будут называться допустимыми. Определение 1. Пусть имеется обучающая выборка V, оператор композиции статистический критерий К, множество допустимых импликаций Д и классовый признак У. Множество правил К.В = КВ(Т>, 0, К, Д, У) будем называть (классификационной) базой знаний (по отношению к Р,Ф, К, Л, У), если

1. К.В содержит все априорные правила, т.е. Но С К.В;

2. для любой комбинации С входных признаков такой, что импликация С => С* допустима, нулевая гипотеза Я0 : Р(С*| С) = Ш(С'\ С,КВ) не отвергается критерием К против соответствующей двусторонней альтернативы.

Определение 2. База знаний К.В будет называться минимальной, если она есть подмножество каждого множества правил, являющегося базой знаний по отношению к Т>, ф, К, Д, У.

Пусть К.В — некоторая БЗ. Определим р.ф. (классификатор) /кв :Х->£) следующим образом:

Да,(х) = ах8тахЩСг*| С(х),/С0), %

где х = (xi, Х2, ■ ■ ., хп) е X и комбинация С(х) определяется соотношением С(х) = Х1Х1&Х2Х2& ■ ■ ■ &Х„хп . Функцию /юз(х) будем называть р.ф., индуцированной К.В.

Во второй главе приведены схемы реализации МСМЭР и соответствующие алгоритмы, использующие частичную информацию о качестве классификаторов, индуцированных последовательностью минимальных БЗ.

В первом разделе описаны индуктивные алгоритмы построения последовательности минимальных БЗ, использующие способы генерации комбинаций по возрастанию их длины и количества входящих в них наиболее информативных признаков. Обозначим ííi(X), L = 0,1,..., п — множество систем правил с длиной антецедента, не превосходящей L и !F\(L) — к.р.ф., индуцированный fíi(L). Легко видеть, что fii(O) С fti(l) С ... С ííi(n) и ^i(O) С JFi(l) С ... С Fi(n). Обозначим через Ai (L), L = 0,1,..., п — множество допустимых импликаций с длиной антецедента не более L. В Следующая теорема устанавливает свойства индуктивного алгоритма построения БЗ, использующего способ генерации комбинаций по возрастанию их длины (величина Lmax является параметром алгоритмов и ее смысл понятен из формулировок нижеприведенных теорем).

Теорема 1. 1. каждая комбинация с допустимой частотой генерируется алгоритмом, причем только один раз;

2. к моменту генерации первой комбинации длины

k = 1,2,..., Lmax все комбинации меньшей длины уже были сгенерированы;

3. для каждого L — 0,1,..., Lmax множество правил БЗ fCB(L) С K.B(Lmax) = К.В с длиной антецедента не более L является минимальной базой знаний по отношению к Р,®,К ,Аг(Ь),У.

Пусть признаки Х\, Х2,..., Х„ расположены в порядке уменьшения априорной вероятности того, что данный признак понадобится при классификации, L = 0,1,...,п — множество систем правил, антецеденты которых содержат не более L первых признаков из данного упорядоченного списка и Fi(L) — к.р.ф., индуцированный Ü2(L). Легко видеть, что Í12(0) С П2(1) С ... С

И ^2(0) С Т2(1) С ... С Т2(п). Обозначим Д2(Ь), Ь = 0,1,...,п — множество допустимых импликаций с количеством наиболее информативных признаков антецедента не более Ь. Следующая теорема устанавливает свойства индуктивного алгоритма построения БЗ, использующего способ генерации комбинаций по возрастанию количества входящих в них наиболее информативных признаков.

Теорема 2. 1. каждая комбинация с допустимой частотой генерируется алгоритмом, причем только один раз;

8. к моменту генерации первой комбинации, содержащей некоторую категорию признака Хь, все комбинации, содержащие только категории признаков Хг,Х2, ■ ■ ■,Х^-х, уже были сгенерированы;

3. для каждого Ь = 0,1,..., Ьтах множество правил КВ(Ь) с КВ, состоящее из правил, антецеденты которых содержат только категории признаков Х\, Х2, ■ ■. является минимальной базой знаний по отношению к V, ©, К, А2(Ь), ^■

Во втором разделе приведены схемы реализации МСМЭР, основанные на использовании частичной информации о качестве оптимальных классификаторов во всех к.р.ф. и дающие возможность осуществления автоматического или интерактивного управления процессом вычислений.

Пусть PJ{L) — оценка в.о.к. оптимального классификатора ¡а-ь (х) в классе Ть, Ь = 0,1,..., п, полученная по 3 блокам кросс-проверки 3 = 1,2,..., М. Определим величины

Схема, предназначенная для автоматического управления поиском оптимального к.р.ф. включает следующие два этапа:

1. получение оценок в.о.к. оптимальных классификаторов во всех к.р.ф. по заданному числу блоков < М;

2. оставшиеся М — ./о блоков обрабатываются по последовательной схеме начиная с класса То со следующим критерием прекраще-

ния поиска: остановить вычисления, как только

Рм(К)

О

> а и

Величины 7о,а>1и/3>1 являются параметрами критерия остановки процесса вычислений. Предложенная схема, помимо учета информации об оценках в.о.к. оптимальных классификаторов в К к.р.ф., полученных после обработки всех М блоков кросс-проверки учитывает и частичную информацию об оценках в.о.к. оптимальных классификаторов в И—К к.р.ф., полученных после обработки За < М блоков кросс-проверки, что повышает надежность решений о прекращении вычислений за счет некоторого увеличения времени.

Более гибкие возможности управления представляет схема реализации МСМЭР, предназначенная для интерактивного управления поиском оптимального к.р.ф. Она предполагает, что каждый блок обрабатывается последовательно по возрастанию номеров к.р.ф. и происходит параллельный пересчет оценок в.о.к., так что в любой момент график текущих оценок в.о.к. визуально доступен для лица, осуществляющего управление ходом вычислений. Управляющее воздействие состоит в том, что происходит отказ от дальнейшей оценки в.о.к. в блоках ■ ■ •, Тп, К < п, причем такое воздействие

может осуществляться несколько раз в ходе процесса вычислений.

В разделе приведены алгоритмы, реализующие описанные выше схемы реализации МСМЭР и позволяющие одновременно осуществлять выбор оптимального уровня значимости критерия, используемого для проверки импликаций на статистическую значимость. Приведены результаты тестирования алгоритмов на реальных задачах, показывающие, что предложенные схемы позволяют значительно сократить время вычислений.

В третьей главе описаны алгоритмы предварительной обработки (применение которых предполагается до процесса индуктивного обучения) и результаты их тестирования на реальных задачах (для проверки на статистическую значимость использовался односторонний критерий знаков). Алгоритмы учитывают особенности индуктивных алгоритмов главы 2. Приведено описание прототипа программного комплекса СТАТКОП для индуктивного построения БЗ и результаты его применения при решении задач кардиологии и социологии.

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

Обозначим №3(Xai, Ха2,... ,Xar), а* е {1,2,... ,п}, г < п минимальную БЗ, содержащую правила, антецедент которых включает только категории входных признаков Xai, ,..., Хаг. В разработанном алгоритме поиска и и упорядочения множества наиболее информативных признаков в качестве меры информативности набора признаков Xai, Ха2,..., Хаг (учитывая то, что в основе рассматриваемых в диссертации алгоритмов лежит ММЭР) используется эмпирический риск Remp(Xai, Ха2,..., Хаг) классификатора, индуцированного соответствующей минимальной БЗ. Результаты тестирования алгоритма на реальных задачах, показывают, что применение алгоритма в сочетании с индуктивными алгоритмами главы 2 позволяет:

1. значимо (при уровне значимости 0.05) уменьшить количество отобранных информативных признаков по сравнению с алгоритмом упорядочения признаков ReliefF;

2. значимо (при уровне значимости 0.05) уменьшить количество правил в БЗ по сравнению с подходом, не использующим отбор наиболее информативных признаков.

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

Приведены результаты тестирования алгоритма на реальных задачах, показывающие, что применение алгоритма ChiSplit на стадии предварительной обработки статистически значимо (при уровне значимости 0.05) уменьшает в.о.к. соответствующих классификаторов по сравнению с алгоритмами ChiMerge, CAIM, TSE, КЕХ.

Во третьем разделе приводится краткое описание комплекса программ индуктивного построения БЗ " СТАТистический КОнструктор Правил" (СТАТКОП) и результаты его применения при решении задач кардиологии и социологии.

Программное ядро СТАТКОП основано на алгоритмах, приведенных в главах 2 и 3 диссертации. Прототип является функционально полным, т.е. в нем реализованы все модули необходимые для его нормального функционирования, как вспомогательного характера (ввод и контроль обучающей выборки, сохранение и ввод ранее построенных БЗ для классификации), предварительной обработки (нахождение и упорядочение множества наиболее информативных признаков, дискретизация непрерывных признаков), модули обеспечивающие реализацию основной задачи (построение БЗ) и модули, обеспечивающие использование построенных БЗ для классификации.

В области кардиологии СТАТКОП использовался для определения факторов риска ранней госпитальной кардиальной летальности и построения классификаторов, позволяющих прогнозировать исход операции. Исходными данными для анализа послужили истории болезней 116 пациентов, которым выполнялась одномоментная коррекция клапанного порока и аортокоронарное шунтирование с 1991 по 1996 гг. в Научном центре сердечно-сосудистой хирургии им. А.Н. Бакулева РАМН. Обучающая выборка содержала 16 входных признаков, описывающих как предоперационное состояние пациентов, так и некоторые характеристики проведенных им операций (вид коррекции клапанов, количество шунтов и др.), а в качестве классового признака фигурировал исход операции (хороший или летальный). Для повышения достоверности выводов наряду с построением БЗ были применены и другие статистические методы, а именно, анализ таблиц сопряженности признаков и построение деревьев решений. Отметим, что классификаторы, индуцированные построенной БЗ и деревом решений основывались на одних и тех же трех признаках — предыдущие операции на сердце, кальциноз и коррекция клапанов (одноклапанная или многоклапанная). Содержательный анализ результатов применения всех упомянутых методов позволил отнести к наиболее важным факторам риска для рассматриваемой операции следующие: предыдущие операции на сердце, кальциноз, вид коррекции клапанов, тип порока и количество шунтов.

В области социологии СТАТКОП был использован при решении

задачи установления взаимосвязей между современным потенциалом сельских домохозяйств Карелии и их проективными стратегиями. Исходными данными для анализа послужили результаты выборочного обследования 186 сельских домохозяйств Республики Карелия, проведенного в 2004 году социологами Карельского научного центра РАН. Потенциал домохозяйств выражался через несколько групп структурных признаков: демографических, социальных, производственно-хозяйственных, бюджетных, потребительских, занятости. Структурные признаки в обучающей выборке играли роль входных признаков (их количество составило 87). В качестве классового использовался признак, характеризующий предполагаемые намерения (проективные стратегии) домохозяйств и отражающий адаптационный процесс на уровне социальных ориентаций и предпочтений. Анализ и интерпретация правил БЗ, построенной с помощью СТАТКОП, позволил выявить наиболее характерные черты потенциала групп домохозяйств с одним и тем же типом проективной стратегии ("самодостаточные", "активные", "активно-пассивные", "пассивные", "эксклюзивные").

В четвертой главе рассматривается задача совместного применения статистических критериев. Пусть К!,Кг,.. • ,Кт — статистические критерии проверки нулевой гипотезы Н0 против альтернатив #1, #2-, • • •; Нт соответственно. Обозначим через К критерий проверки нулевой гипотезы Н0 против "объединенной" альтернативы Я = #1 и#2 и ... и Нт который отвергает гипотезу Но, если хотя бы один из критериев Кг, К2,..., Кт отвергает Н0. Критерии такого вида будем называть совместными. Для уровня значимости /3 совместного критерия К выполнены неравенства шах(а] • • •, ат) ^ 0 < £*1 + <*2 + • • • + «то , где «1, а2, • • •, «то — уровни значимости критериев К1,Кз,. • •, Кт соответствено. Выбор ац, а2,..., ат, являющийся предметом рассмотрения данной главы, в значительной степени опре- г

деляется наличием (или отсутствием) у исследователя априорной информации о вероятностях альтернатив того или иного класса.

Пусть X — случайная величина (с.в.) с функцией распределения ВД, принадлежащей классу распределений Р = {^(х, в),в е 9} , © С Кк. Обозначим X = (X, ,Х2,...,Х„) случайную выборку из распределения с.в. X. Множество значений случайного вектора X будем обозначать X. Предположим, что каждое альтернативное распределение определяется вектором в 6 0я С в, и пусть на в# существует априорное распределение П. Пусть вектор а = (а\,а2,..., ат)

и Ка означает соответствующий совместный критерий. Обозначим Л7 = {а : с*! + а2 + ... + ат — 7} . Определим риск Д(П, а) критерия Ка следующим образом:

Д(П,а) = J Рв(Х<£Ка)ЩМ), вн

где Ка — критическая область критерия Ка, определяемая соотношением ,т.

Ка = {х е X : х 6 [J Ка,, ос € Л,} ,

а Каз — критическая область критерия Кj, j = 1,2,... ,m. Совместный критерий KQo будем называть наилучшим совместным критерием (н.с.к.), если

а0 = arg min /?(П, а).

абЛ-,

Предположим, что альтернативные распределения случайно генерируются в соответствии с (неизвестным) априорным распределением П. Пусть в\, в2,. .., Oi € О/у — случайная выборка из распределения П и Х| = (хц, хг2, ■ ■ ■, xln), г = 1,2,..., i — случайная выборка из распределения F(x,9,). Обозначим Т-,(Х) статистику критерия Kj, Fj(x) функцию распределения с.в. Тл(Х) в случае истинности нулевой гипотезы Но-

Теорема 3. 1. Существует с.в. Y с множеством возможных значений {0,1}, множество р.ф.

T={/a(v): v е Вт, а е Ау) ,

определенных на единичном кубе Dm со значениями в {0,1} и распределение W(dvdy) на Dm х {0,1} такие, что

Д(П, а) = J Рв(Х i Ka)TL{d9) = J (у - fa(v))2W{dvdy).

ен ümx{o,i}

2. Пусть критические области Kaj критериев Kj, j = 1,2,..., то имеют вид Kaj — {х : Т3 (х) Jj caj} , где F3 (caj) = 1 - а3. Тогда для любого е > О

Р{|Д(П,а0) - Я(П,а*)| > с} -> 0 при I -»■ оо,

где а* = а^ шш Яетпр(а) и

абЛ-,

1=1

Во втором разделе рассматривается задача использования частичной априорной информации (ч.а.и.) для построения двусторонних статистических критериев. Пусть Ка — двусторонний критерий проверки простой нулевой гипотезы Но : в = во против двусторонней альтернативы Я : в ф во, определяемый критической областью 1Са — К~х и 1С+2, где а = («1, а2) и 1С~1 и К +2 критические области левостороннего и правостороннего критериев с уровнями значимости а г и а2 соответственно. Пусть Ч = (<?1> 92, • • •, 9т) и р = (рьр2, • • • ,рот_ 1)

т—1

таковы, что < й < •. • < 9т и рг = 1 . Обозначим

«=1

Г = {П : П(# £ ©,) —рг , г = 1,2,... ,т — 1}, в, = («„ ®+х] , (3) Др (а) = вир Д(П, а) , Др(а) = шГ Д(П,а).

П€Г пег

Теорема 4. Пусть функция мощности №(К.а ;в) критерия К„ монотонно убывает на интервале (—оо,втгп) и монотонно возрастает на интервале (вт1П,+оо). Тогда нижняя Д^ (а) и верхняя Др («) границы риска критерия Ка определяются следующими соотношениями:

т—1 т—1

Д+(а) = 1 - у; Рг Ы Ш{Ка -в), Дг(«) = 1-Ур, вир \У{Ка ; в), где

<=1 ебв* ^ *€в,

^(/Са ;0тт), © < 0тт <

"1ШП

вир еев.

тах{Щ/Са ;©), Щ/Со, ;д<-и)}> д, < вт1П < qi+^

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Алекян Б.Г., Скопин И.И., Никитина Т.Г., Капутин М.Ю., Захаров И.В., Стаферов A.B., ТрошеваТ.В., Чистяков С.П. Коронарная ангиопластика в этапном лечении больных приобретенными пороками сердца в сочетании с ИБС // Грудная и сердечнососудистая хирургия. - 2001. Вып. 6. - С. 73-76.

2. Белая Р. В., Морозова Т. В., Чистяков С. П. Проективные стратегии и современный потенциал сельских домохозяйств //Тр. ИПМИ КарНЦ РАН. - 2005. - Вып. 5. - С. 21-34.

3. Павлов Ю. Д., Харин В.Н.,Чистяков С. П. Применение статистических методов для оценки точности решений экспертных систем // Тр. Петрозаводского гос. университета, сер. "Прикладная математика и информатика". -1997. - Вып. 6. - С. 179186.

4. Чистяков С.П. Об определении уровней значимости одновременно применяемых статистических критериев // Тр. ИПМИ КарНЦ РАН. - 1999. - Вып. 1. - С. 55-60.

5. Чистяков С.П. Применение метода структурной минимизации эмпирического риска при индуктивном построении баз знаний // Тр. ИПМИ КарНЦ РАН. - 2002. - Вып. 3. - С. 213-225.

6. Чистяков С.П. Об одном алгоритме дискретизации непрерывных признаков // Тр. ИПМИ КарНЦ РАН. - 2004. Вып. 4. -С. 203-212.

7. Чистяков С.П. О поиске множества наиболее информативных признаков при индуктивном построении баз знаний // Тр. ИПМИ КарНЦ РАН, Вып. 5, 2004. - С. 128-135.

8. Чистяков С.П. Об автоматизации построения баз знаний экспертных систем // Обозрение прикладной и промышленной математики, т. 8, вып. 1, 2001. - С. 375-376.

9. Чистяков С.П. Об использовании априорной информации для определения уровней значимости совместно применяемых статистических критериев // Обозрение прикладной и промышленной математики, Т. 7, 2001. - С. 152-153.

10. Чистяков С.П. Применение кросс-проверки для оптимизации выбора параметров индуктивных алгоритмов построения систем правил // Обозрение прикладной и промышленной математики. - 2003. Т. 10, вып. 1. - С. 252.

11. Chistjakov S.P. On using of partial prior information for statistical tests construction // Proceeding of the sixth international conference "Computer Data Analysis and Modelling: Robustness and computer intensive methods", Minsk, 2001. - P. 104-109.

12. Chistjakov S.P. On joint using of statistical tests // Proceeding of Fifth International Petrozavodsk conference on Probability methods in discrete mathematics. VSP, Utrecht, 2004. - P. 159162.

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 17.01.06. Формат 60x84 '/)6. Бумага офсетная. Гарнитура «Times». Уч.-изд. л. 1,0. Усл. печ. л. 1,1. Тираж 100 экз. Изд. № 15. Заказ 561

Карельский научный центр РАН Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50

242в

Введение

1 Основные понятия и обозначения

1.1 Статистические решающие функции.

1.2 Метод минимизации эмпирического риска.

1.2.1 Постановка задачи классификации с учителем

1.2.2 Емкость класса решающих функций.

1.3 Метод структурной минимизации эмпирического риска

1.3.1 Описание метода.

1.3.2 Метод кросс-проверки

1.4 Индуктивное построение баз знаний. Подход КЕХ.

1.4.1 Терминология и обозначения.

1.4.2 Определение базы знаний.

1.4.3 Алгоритм КЕХ.

1.4.4 Базы знаний и решающие функции.

1.5 Статистические критерии проверки гипотез.

1.5.1 Критерий согласия %2.

1.5.2 Критерий однородности %2.

1.5.3 Критерий знаков.

1.6 Упорядочение признаков. Алгоритм ПеПеЛ5,.

1.7 Дискретизация непрерывных признаков.

1.7.1 Постановка задачи дискретизации и терминология

1.7.2 Алгоритм дискретизации системы КЕХ.

1.7.3 Алгоритм дискретизации СЫМе^е.

1.7.4 Алгоритм дискретизации САШ

1.7.5 Алгоритм дискретизации ТБЕ

2 Индуктивное построение баз знаний

2.1 Процедуры генерации комбинаций.

2.1.1 Построение баз знаний по возрастанию длины антецедента.

2.1.2 Построение баз знаний по возрастанию количества наиболее информативных признаков антецедента.

2.2 Поиск оптимального класса решающих функций.

2.2.1 Схемы реализации метода структурной минимизации эмпирического риска

2.2.2 Нахождение оптимального класса решающих функций по возрастанию длины антецедента

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

3 Предварительная обработка обучающей выборки

3.1 Нахождение множества наиболее информативных признаков. ф 3.1.1 Постановка задачи.

3.1.2 Пошаговый алгоритм нахождения множества наиболее информативных признаков.

3.1.3 Результаты вычислительных экспериментов

3.2 Дискретизация непрерывных признаков

3.2.1 Постановка задачи. 3.2.2 Алгоритм СЫБрШ.

3.2.3 Результаты вычислительных экспериментов.

3.3 Система СТАТКОП.

3.3.1 Описание системы СТАТКОП

3.3.2 Определение факторов риска в кардиологии

3.3.3 Проективные стратегии и современный потенциал сельских домохозяйств Карелии.

4 Индуктивное построение баз знаний статистических экспертных систем

4.1 Наилучшие совместные критерии.

4.1.1 Постановка задачи.

4.1.2 Наилучшие двусторонние статистические критерии

4.1.3 Использование эмпирической информации о возможных альтернативах для построения совместных статистических критериев.

4.2 Использование частичной априорной информации для построения двусторонних критериев

4.2.1 Постановка задачи.

4.2.2 Псевдонаилучшие двусторонние критерии.

4.2.3 Интерактивное назначение априорного распределения

4.2.4 Алгоритм интерактивного построения псевдонаилучших двусторонних критериев.

Одним из наиболее успешно развивающихся направлений в области искусственного интеллекта и первым, нашедшим широкий выход в различные области человеческой деятельности (наука, техника, медицина, геология и многие другие), являются экспертные системы (ЭС). Ключевой проблемой в теории и практике современных ЭС является проблема построения ее базы знаний (БЗ) [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] и системы правил различного типа. Системы правил обладают рядом достоинств по сравнению с другими моделями представления знаний:

1. правила легко интерпретируются ввиду их синтаксической формы и высокой модульности [45] (отдельное правило может быть легко понято вне контекста других правил) и, вследствии этого, широко используются для представления знаний в ЭС [23, 22];

2. определенные типы априорной информации легко могут быть встроены в алгоритмы индуктивного обучения систем правил [75];

3. как неоднократно отмечалось многими исследователями, системы правил, как инструмент классификации, часто обеспечивают точность, сравнимую с нейронными и байесовскими сетями и обычно превосходящую точность деревьев решений (см., например, [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 (КЕХ) предназначенная для автоматизации построения БЗ с представлением знаний в виде систем правил вида "ЕСЛИ (УСЛОВИЕ) ТО (СЛЕДСТВИЕ) С ВЕСОМ (W)", аналогичным использовавшимся в классических ЭС PROSPECTOR [53, 54] и MYCIN [85]. Алгоритм КЕХ обеспечивает формирование БЗ по обучающей выборке, признаки которой измерены в номинальной шкале, без поддержки эксперта. Условие, или антецедент, правила представляет собой конъюнкцию элементов вида "признак = значение" (комбинацию) значений некоторых признаков, называмых входными1, следствие представляет собой указание назначение (уровень) некоторого выделенного признака, называемого классовым, а вес правила является количественной мерой влияния условия на частоту значения классового признака входящего в следствие. Заметим, что такие БЗ фактически представляют собой вероятностно-статистическую модель наблюдаемого явления, построенную по обучающей выборке и индуцирующую некоторый классификатор. Алгоритм КЕХ, по видимому, является единственным алгоритмом, предназначенным для построения БЗ указанного вида. Важным достоинством таких БЗ является то, что кро

1гг.е., условие правила состоит в том, что ряд входных признаков приняли определенные значения ме классификации они могут использоваться также в качестве инструмента статистического анализа [4]. Заметим, что алгоритм обеспечивает построение минимальных БЗ (не содержащих избыточной информации).

Существенным недостатком системы является то, что в ней отсутствуют возможности для борьбы с переподгонкой и процедура генерации комбинаций алгоритма КЕХ требует определенной модификации для использования в МСМЭР. Заметим также, что алгоритм КЕХ весьма затратен с точки зрения времени вычислений и, учитывая то, что существующие схемы реализации МСМЭР (использующие метод кросс-проверки) требуют многократного прогона этого алгоритма, вопрос разработки экономичных с точки зрения времени вычислений схем реализации МСМЭР весьма актуален. Эффективность системы снижает и отсутствие возможностей для интегрирования в процесс индуктивного обучения априорной информации об информативности признаков, позволяющее уменьшить количество правил БЗ (что важно с точки зрения робастности классификатора) без потери точности классификации. Наконец, алгоритм дискретизации непрерывных признаков, специально разработанный авторами для системы КЕХ, часто приводит к разбиению на слишком большое число интервалов (что снижает точность классификации, поскольку в каждый такой интервал попадает недостаточное для корректного применения статистических критериев количество примеров обучающей выборки) и, фактически, может использоваться только для признаков, измеренных в порядковой шкале (что отмечалось и авторами КЕХ [40]).

Второй круг вопросов, рассмотренных в диссертации связан с построением БЗ статистических ЭС. Одной из основных задач при построении таких БЗ состоит в формировании рекомендаций пользователю по выбору параметров статистических методов, наиболее подходящих в конкретной ситуации [59]. При проверке статистических гипотез важнейшим параметром является уровень значимости критерия. В диссертации ю рассматривается задача выбора уровней значимости статистических критериев, совместно применяемых для проверки одной и той же нулевой гипотезы против нескольких классов альтернатив. Хорошо известно [20], что чем меньше вероятность альтернатив некоторого класса, тем меньшим должен выбираться уровень значимости соответствующего критерия в описанной выше схеме. Однако, конкретные процедуры, реализующие этот принцип на основе априорной информации того или иного вида, не разработаны, в связи с чем исследователю приходится полагаться на свой опыт и интуицию.

Связь данной тематики с задачей индуктивного построения БЗ заключается в том, что (как показано в диссертации) задача совместного применения статистических критериев при наличии обучающей выборки о возможных альтернативах может рассматриваться как задача классификации и ММЭР является состоятельным для ее решения, т.е. имеет место сходимость по вероятности риска совместного критерия, построенного на основе ММЭР, к риску наилучшего совместного критерия (понятие наилучшего совместного критерия (н.с.к.), являющегося частным случаем наилучшего критерия Большева Л.Н. [5], введено автором [27]) при неограниченном возрастании объема выборки. Другая параллель между этими направлениями состоит в том, что в обоих случаях предложены подходы, основанные на использовании частичной (неполной) информации при принятии решений.

В связи с вышесказанным целями диссертации являлись

1. разработка методов и алгоритмов индуктивного построения БЗ, позволяющих избео/сатъ эффекта переподгонки на основе МСМЭР и учитывающих априорную информацию;

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

В соответствии с данными целями предметом исследований являлись процедуры генерации комбинаций и индуктивные алгоритмы построения БЗ, схемы реализации МСМЭР, методы и алгоритмы нахождения и упорядочения множества наиболее информативных признаков и дискретизации, статистические критерии проверки гипотез и методы назначения априорных распределений. Основными методами исследований являлись вероятностные и статистические методы, в частности методы байесовской и робастной статистики. При сравнении качества алгоритмов дискретизации и алгоритмов поиска и упорядочения множества наиболее информативных признаков использовалась методика эмпирического сравнения соответствующих индуктивных алгоритмов на реальных задачах из коллекции (репозитария) задач Калифорнийского университета [73]. Заметим, что такой подход является общепринятым в области индуктивного обучения (см., например, [50]).

Диссертация состоит из введения, четырех глав, заключения, списка литературы и 4 приложений.

Ввод 2

Рис. 4.3. Блок-схема алгоритма интерактивного построения псевдонаилучшего двустороннего критерия.

Заключение

Основные итоги диссертации состоят в следующем:

1. Разработан подход к индуктивному построению БЗ (реализованный в виде тесно взаимосвязанного семейства алгоритмов), использующих модель представления знаний в виде систем правил с весами. Подход представлен в виде новых схем реализации МСМЭР, процедур генерации комбинаций, методов и процедур предварительной обработки, ориентированных на применение с индуктивным алгоритмом системы КЕХ. Подход основан на единой методологической основе борьбы с переподгонкой посредством использования частичной информации о качестве классификаторов, индуцированных последовательностью минимальных БЗ путем осуществления автоматического и интерактивного контроля и управления процессом поиска оптимального к.р.ф.

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

3. На основе разработанного семейства алгоритмов разработан прототип комплекса программ СТАТКОП для индуктивного построения БЗ, обеспечивающий существенное расширение функциональных возможностей по сравнению с системой КЕХ [39], ориентирование ной на решение аналогичных задач. С его помощью выявлены факторы риска ранней госпитальной кардиальной летальности и построены классификаторы, позволяющие прогнозировать исход операции, а также выявлены взаимосвязи между проективными стратегиями и современным потенциалом сельских домохозяйств Карелии.

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

По мнению автора работа по этой тематике может быть продолжена в следующих направлениях:

1. исследование свойств предложенных схем реализации МСМЭР, разработка и сравнительное исследование качества критериев автоматического управления процессом поиска оптимального к.р.ф., которые могут быть использованы при реализации этих схем.

2. исследование и разработка методов определения уровней значимости совместно применяемых непараметрических статистических критериев на основе ч.а.и.

3. практическая апробация базового алгоритма интерактивного определения уровней значимости двусторонних статистических критериев.

1. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Классификация и снижение размерностей. -М. : Финансы и статистика, 1989. - 607с.

2. Афифи А., Эйзен С. Статистический анализ. Подход с использованием ЭВМ. М. : Мир, 1982. - 488с.

3. Белая Р. В., Морозова Т. В., Чистяков С. П. Проективные стратегии и современный потенциал сельских домохозяйств // Тр. ИПМИ КарНЦ РАН. 2005. - вып. 5. - С. 21-34.

4. Болыпев Л.Н. Избранные труды. Теория вероятностей и математическая статистика. М. : Наука, 1987. - 268с.

5. Бонгард М.М. Проблема узнавания. М. : Наука, 1967. - 320с.

6. Бондаренко В.М., Павлов Ю.Л. Система поиска регрессионных закономерностей "СПОР" / Петрозаводск: Карельский филиал АН СССР, 1991.-41с.

7. Вайнцвайг М.И. Алгоритм обучения распознаванию образов "Кора". Алгоритмы обучения распознаванию образов / под ред. Вапни-ка В.Н. / М. : Советское радио, 1973. - С. 110-116.

8. Вапник В.Н., Лернер А.Я., Червоненкис А.Я. Системы обучения распознаванию образов при помощи обобщенных портретов // Изв. АН СССР. Сер. Техническая кибернетика. 1965. Вып. 1. - С. 72-87.

9. Вапник В.Н., Червоненкис А.Я. О равномерной сходимости частот появления событий к их вероятностям // Теория вероятностей и ее применения. 1965. Т. 10, вып. 2.

10. И. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М. : Наука, 1974. 416с.

11. Вапник В.Н., Глазкова Т.Г., Кащеев В.А., Михальский А.И., Червоненкис А.Я. Алгоритмы и программы восстановления зависимостей.- М. : Наука, 1984. 816с.

12. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке. Методы обработки данных. М. : Мир, 1980. -610с.

13. Загоруйко Н.Г. Эмпирическое предсказание. Новосибирск.: Наука, 1979. - 123с.

14. Загоруйко Н.Г., Елкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск.: Наука, 1985. - 108с.

15. Закс Ш. Теория статистических выводов. М. : Мир, 1974. - 776с.

16. Ивченко Г.И., Медведев Ю.И. Математическая статистика. М. : Высшая школа, 1992. - 304с.

17. Колмогоров А.Н. К вопросу о пригодности найденных статистическим путем формул прогноза // Геофизический журнал. 1933. Т. 3, № 1. - С. 78-82.

18. Колмогоров А.Н. Три подхода к определению понятия количество информации // Проблемы передачи информации. -1965. Т. 1, вып. 1.- С. 3-11.

19. Леман Э. Проверка статистических гипотез. М. : Наука, 1979. -408с.

20. Морозова Т.В., Гурова С.А., Козырева Г.Б. Сельские сообщества Карелии: традиции, современность, перспективы. — Петрозаводск: Изд-во Кар НЦ РАН, 2004. 252 с.

21. Попов Э.В. Экспертные системы. М. : Наука, 1987. - 456с.

22. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии. - М. : Наука, 1988. - 280с.

23. Павлов Ю. Л., Харин В.Н.,Чистяков С. П. Применение статистических методов для оценки точности решений экспертных систем // Тр. Петрозаводского гос. университета, сер. "Прикладная математика и информатика". 1997. - вып. 6. - С. 179-186.

24. Чистяков С.П. Об определении уровней значимости одновременно применяемых статистических критериев // Тр. ИПМИ КарНЦ РАН.- 1999. вып. 1. - С. 55-60.

25. Чистяков С.П. Об автоматизации построения баз знаний экспертных систем // Обозрение прикладной и промышленной математики, т. 8, вып. 1, 2001. С. 375-376.

26. Чистяков С.П. Об использовании априорной информации для определения уровней значимости совместно применяемых статистических критериев // Обозрение прикладной и промышленной математики, Т. 7, 2001. С. 152-153.

27. Чистяков С.П. Применение метода структурной минимизации эмпирического риска при индуктивном построении баз знаний // Тр. ИПМИ КарНЦ РАН. 2002. - Вып. 3. - С. 213-225.

28. Чистяков С.П. Применение кросс-проверки для оптимизации выбора параметров индуктивных алгоритмов построения систем правил // Обозрение прикладной и промышленной математики. 2003. Т. 10, вып. 1. - С. 252.

29. Чистяков С.П. Об одном алгоритме дискретизации непрерывных признаков // Тр. ИПМИ КарНЦ РАН. 2004. Вып. 4. - С. 203-212.

30. Чистяков С.П. О поиске множества наиболее информативных признаков при индуктивном построении баз знаний // Тр. ИПМИ КарНЦ РАН, вып. 5, 2004. С. 128-135.

31. Шкондин А.И. Нечеткие решающие деревья в моделях принятия решений // Тр. ИПМИ КарНЦ РАН, в. 1, 1999. С. 61-64.

32. Akaike Н. Information theory and a extension of the maximum likelihood principle // Second International simpozium on Information Theory, eds. B. N. Petrov and F. Csaki, Akad. Kiado, Budapest, 1973. P. 267-281.

33. Amari S., Murata N., Muller K., Finke M., Yang H.H. Asimptotical statistical theory of Overtraining and Cross-validation // IEEE Transactions on Neural Networks. 1997. Vol. 8, № 5. - P. 985-986.

34. Amari S., Murata N., Muller K., Finke M., Yang H.H. Statistical Theory of Overtraining — is Cross-validation Asimptotical Efficient? // Advances in Neiral Information Processing Systems. 1996. Vol. 8. - P. 176-182.

35. Berger J.O. An Overviev of Robust Bayesian Analisis // Technical Report 93-53C, Department of statistics, Purdue university, 1993. -P. 1-56.

36. Berka P., Ivanek J. Automated Knowledge Acquisition for PROSPECTOR-like Expert Systems // Proceeding ECML'94, Springer, 1994. P. 339-342.

37. Berka P. Diskretization of numerical attributes for Knowledge EXplorer // Technical Report, LIsp-93-03, 1993. P. 1-11.

38. Berka P., Bruha I. Empirical comparisons of various diskretization procedures // Technical Report, LIsp-95-04. 1995. - P. 1-13.

39. Boose J.N. A survey of knowledge acquisition techniques and tools // Knowledge acquisition. 1989. Vol. 1, № 1. - P. 3-37.

40. Breiman L., Friedman J.H., Olshen R.A., Stone C.J. Classification and regression trees // Bellmont, Wadsworth, 1984.

41. Bratko I., Kononenko I. Learning diagnostic rules from incomplete and noisy data /In B. Phelps, ed. Interactions in AI and Statistical Methods. 1986.: London. - P. 142-153.

42. Catlett J. Megainduction: a test flight / Proceedings of the Eigth International Workshop on Machine Learning, Morgan Kauffman, New York, 1991. P. 596-599.

43. Chistjakov S.P. On joint using of statistical tests // Proceeding of Fifth International Petrozavodsk conference on Probability methods in discrete mathematics. VSP, Utrecht, 2004. P. 159-162.

44. Chistjakov S.P. On using of partial prior information for statistical tests construction // Proceeding of the sixth international conference "Computer Data Analysis and Modelling: Robustness and computer intensive methods", Minsk, 2001. P. 104-109.

45. Clark P., Niblett T. The CN2 induction algorithm // Machine Learning. 1989. V. 3, № 4. - P. 261-284.

46. Cooper G. A Bayesian method for the induction of probabalistic networks from data // Machine Learning. 1991. V. 9. - P. 309-347.

47. Dietterich T.G. Exploratory research in Machine Learning // Machine Learning. 1990. V. 5. - P. 5-9.

48. Dietterich T.G. Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms // Neural Computation. 1998. V. 10 № 7. - P. 1-39.

49. Dougherty J., Kohavi R., Sahami M. Supervized and Unsupervized Diskretization of Continuous Features // Machine Learning: Proceedings of the Tvelfth International Conference. San Francisco: Morgan Caufmann Publishers, 1995. - P. 194-202.

50. Duda R.O. , Gashing J.E. Model Design in the Prospector Consultant System for Mineral Exploration. Expert system in the Micro Electronic Age. UK. : Edinburg University Press, 1979. - P. 153-167.

51. Duda R.O., Hart P.E., Nilsson N.J. Subjective Bajesian methods for rule-based inference systems // Technical Note. 1976. V. 134. -P. 1075-1082.

52. Enbutsu I., Baba K., Hara N. Fuzzy rule extraction from a multilayered neural networks // Proc. of IJCNN. 1991. - P. 212-221.

53. Fayyad U.M., Irani K.B. On the Handling of Continues-valued Attributes in Decision Tree Generation // Machine Learning. 1992. V. 8. - P. 87-102.

54. Gallant S.I. Connectionist expert systems // Communications of the ACM. 1988. V. 31. - P. 152-169.

55. Hagan A., Berger J.O. Ranges of posterior probabilities for quasi-unimodal priors with specified quantiles // Journal of American Statistical Association. 1988. V. 83. - P. 503-508.

56. Hahn G.J. More Intelligent Statistical Software and Statistical Expert Systems: Future Directions // The American Statistician. 1985. V. 39, № 1. - P. 1-16.

57. Hajek P. , Combining Functions for Certainty Factors in Consulting Systems // Int. J. Man-Machine Studies. 1985. V. 22. - P. 59-76.

58. Ivanek J. Minimum knowledge base search from categorial data // Workshop on uncertainty processing in expert system. Praha, 1994. -P. 77-86.

59. Jaynes E.T. On the rationale of maximum entropy methods // Proceedings of IEEE. 1982. V. 70. - P. 939-952.

60. John G.H. Cross-validated C4.5: Using Error Estimation for Automatic Parameter Selection // Tech. Report STAN-CS-TN-94-12, Stanford Univ., Computer Science Department, 1994. P. 1-4.

61. Kerber R. Chimerge: Diskretization of numerical attributes // Proceedings of the tenth National Conference on Artificial Intelligence, MIT Press, 1992. P. 123-128.

62. Kira K. , Rendell L. A practical approach to feature selection // Proc. Intern. Conf. on Machine Learning. Aberdeen: Morgan Kaufmann, 1992. - P. 249-256.

63. Kononenko L., Simec E., Robnic-Sikonja M. Overcoming the myopia of inductive algorithms with RELIEFF // Applied Intelligence. 1997. V. 7. - P. 39-55.

64. Kurgan L., Cios K.J. CAIM Discretization Algorithm // IEEE Transactions on Knowledge and Data Engineering. 2004. V. 16, №. 2, P. 145-153.

65. Lehmann E.L. Significance level and power // Annals of mathematical statistics. 1958. V. 29. - P. 1167-1176.

66. Liseo B., Petrella L., Salinetti G. Bayesian robustness: An interactive approach // Bayesian statistics. 1996. V. 5. - P. 661-666.

67. Maass W. Efficient agnostic PAC-learning with simple hypotheses // Proc. of the Seventh Annual ACM Conference on Computional Learning Theory. 1995. - P. 67-75.

68. Michalski R.S. A Theory and methodology of inductive learning // Artificial Intelligence. 1983. V. 20. - P. 111-161.

69. Murphy D.M., Aha D.W. UCI Repositary of Machine Learning Databases / Univ. of California, Dept. of Information and Computer Science, Irvine, CA, 1995. -http://www.ics.uci.edu/ mlearn/MLRepository

70. Pagallo G., Haussler D. Boolean feature discovery in empirical learning // Machine Learning. 1990. V. 4, № 1. - P. 227-243.

71. Pazzani M., Kibler D. The role of prior knowledge in inductive learning // Machine Learning. 1992. V. 9, №1. - P. 54-97.

72. Preshe L. Early Stopping — but when? // Lecture Notes in Computer Science. 1998. V. 1524. - P. 55-69.

73. Quinlan J.R. Induction of decision trees // Machine Learning. 1986. V. 1(1). - P. 81-106.

74. Quinlan J.R. Simplifying decision trees // International Journal of Man-Machine Studies. 1987. V. 27. - P. 221-234.

75. Quinlan J.R., Compton P.J., Horn K.A., Lazarus L. Inductive knowledge acquisition: A case study // Second Australian Conference on Application of Expert Systems, New South Wales Institute of Technology, Sydney, Australia, 1986.

76. Rissanen J. Modeling by shortest data description // Automatica. -1987. V. 14. P. 465-471.

77. Robnik M., Kononenko I. Discretization of continious attributes using ReliefF // Proceedings of ERK-95, Portoroz, 1995. P. 149-152.

78. Schwarz G. Estimation the dimension of a model // The Annals of Statistics, V. 6, P. 461-464.

79. Shaffer C. Overfitting avoidance as bias // Machine Learning. 1993. V. 10. - P. 113-152.

80. Shafter C. When does overfitting decrease prediction accuracy in induced desision trees and rule sets? // Proceedings of the European Working Session on Learning, Porto, Springer-Verlag, 1991. P. 192-205.

81. Shortliffe E.,Buchanan B.G. A model of inexact reasoning in medicine // Mathematical Biosciences. 1975. V. 23. - P. 351-377.

82. Sima J., Neruda R. Neural networks as expert systems // Neural Networks World. 1992. V. 2. - P. 775-784.

83. Stafeev S.V. Learning Bayesian Networks with Latent Variables // Proceeding of the sixth international conference "Computer Data Analysis and Modelling: Robustness and computer intensive methods", Minsk, 2001. P. 238-243.