Выбор оптимальной сложности класса логических решающих функций в задачах анализа разнотипных данных тема диссертации и автореферата по ВАК РФ 05.13.17, доктор технических наук Бериков, Владимир Борисович

• Бериков, Владимир Борисович
• доктор технических наук
• 2006

Оглавление диссертации доктор технических наук Бериков, Владимир Борисович

Введение

1. Построение решающих функций в задачах предсказания

1.1. Основные понятия.

1.2. Обзор методов построения решающих функций распознавания

1.3. Качество решающих функций распознавания

1.4. Логические решающие функции.

1.5. Деревья решений

Выводы.

2. Байесовская модель распознавания конечного множества событий

2.1. Распознавание образов по конечному множеству событий

2.2. Задание модели

2.2.1. Основные предположения.

2.2.2. Задание априорного распределения с учетом ожидаемой вероятности ошибки байесовского решающего правила

2.3. Исследование байесовской модели распознавания конечного множества событий.

2.3.1. Ожидаемый риск неправильного распознавания

2.3.2. Дисперсия функции риска для метода обучения

2.4. Байесовская модель для метода минимизации эмпирической ошибки.

2.4.1. Ожидаемая вероятность ошибки

2.4.2. Ожидаемое уклонение.

2.4.3. Дисперсия случайной величины вероятности ошибки

2.4.4. Дисперсия уклонения.

2.5. Выбор оптимальной решающей функции

2.5.1. Байесовские оценки риска неправильного распознавания для решающей функции.

2.5.2. Смещение и дисперсия байесовских оценок.

2.6. Байесовская оценка как критерий качества дерева решений . . 150 Выводы.

3. Алгоритмы построения деревьев решений в задачах анализа разнотипных данных

3.1. Рекурсивный алгоритм построения дерева решений (£К-метод)

3.2. Группировка с использованием деревьев решений.

3.3. Деревья решений и анализ многомерных разнотипных временных рядов.

3.4. Прогнозирование экстремальных событий

Выводы.

4. Реализация и практическое использование разработанных методов 196 4.1. Комплекс программ J1ACTAH-M

4.2. Анализ спектров мутаций в ДНК.

4.3. Анализ данных об археологических находках

4.3.1. Анализ данных о раскопках Маяцкого кургана.

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

4.3.3. Изучение типологических изменений в процессе развития панцирных доспехов средневековых номадов Центральной Азии

4.4. Прогноз экстремальных гидрологических ситуаций.

4.5. Анализ гелиогеофизических факторов среды при пренатальном развитии в вероятностной модели прогноза здоровья человека.

Выводы.

Введение диссертации (часть автореферата) на тему «Выбор оптимальной сложности класса логических решающих функций в задачах анализа разнотипных данных»

Актуальность темы. В настоящее время при автоматизации процессов обработки информации в различных трудноформализуемых областях исследований (генетике, археологии, медицине и т.д.) возникает проблема решения задач анализа данных (Data Mining), характеризующихся следующими особенностями: недостаточностью знаний об изучаемых объектах, что затрудняет формулировку их математических моделей; большим числом разнотипных (количественных или качественных) факторов при сравнительно малом объеме данных; нелинейностью взаимосвязей; наличием пропусков, погрешностей измерения характеристик; необходимостью прогнозирования редких событий, связанных с большими потерями; требованием представления результатов анализа в форме, понятной специалисту прикладной области.

Одними из наиболее перспективных методов решения такого рода задач являются методы, основанные на классе логических решающих функций (ЛРФ). Часто используемая форма представления ЛРФ - дерево решений.

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

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

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

Направление, разработанное В.Н. Вапником и А.Я. Червоненкисом, получило название статистической теории обучения. В рамках этой теории было предложено понятие емкостной характеристики класса решающих функций (определяющей его сложность), найдена взаимосвязь между интервальными оценками качества решающей функции, сложностью класса и объемом обучающей выборки, а также предложен метод упорядоченной минимизации риска и метод опорных векторов. В последующих работах В.Н. Вап-ника, М. Та^гап, С. Ь^об! и др. было достигнуто значительное улучшение оценок путем привлечения информации о методе обучения, выборке и использования более точных способов оценивания. Авторами, наряду со слож-ностными характеристиками, применялись различные неравенства (Маркова, Чернова и др.), описывающие эффект «концентрации» случайной величины вблизи ее математического ожидания. Эти неравенства справедливы для любого распределения, включая наименее «благоприятное». Такая универсальность, с одной стороны, является сильной стороной, но с другой стороны, приводит к тому, что в некоторых случаях (особенно при малом объеме выборки) оценки риска являются сильно завышенными, а выбранные модели - переупрощенными. В терминах теории принятия решений, полученные оценки качества можно назвать минимаксными.

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

Провести такой учет позволяет байесовская теория обучения. В основе этого направления лежит идея использования априорных знаний о решаемой задаче, позволяющих, в частности, сопоставить каждому возможному распределению («стратегии», «состоянию» природы) некоторый вес. Этот вес отражает интуитивную уверенность эксперта в том, что неизвестное истинное распределение совпадает с рассматриваемым. В первых работах в данном направлении находились байесовские оценки параметров моделей распознавания. Рядом авторов (G. Hughes, Г.С. Лбов и Н.Г. Старце-ва и др.) рассматривалась байесовская модель распознавания для дискретных переменных в случае, когда на множестве стратегий природы задано равномерное априорное распределение. Другими авторами (W. Buntine и др.) предлагалось задавать априорное распределение на классе решающих функций, с целью нахождения решающей функции, максимизирующей апостериорную вероятность. Однако в указанном направлении до сих пор остаются актуальными такие вопросы, как задание априорного распределения, отражающего экспертные знания о решаемой задаче, учет специфики метода обучения, повышение надежности и точности оценок. Поэтому решение этих вопросов и использование полученных результатов в задачах анализа данных является актуальным.

При построении ЛРФ, наряду с выбором их оптимальной сложности (числа логических высказываний или листьев решающего дерева), актуальна также проблема создания эффективных методов и алгоритмов поиска оптимальной функции для решения задач анализа разнотипных данных (распознавания образов, регрессионного анализа, кластер-анализа, анализа многомерных временных рядов), поскольку существующие методы не позволяют достичь наилучшего качества в случае сложной структуры данных например, когда наблюдения подчиняются многомодальному распределению с «шахматной» структурой).

Связь с крупными научными программами, темами. Результаты диссертационных исследований использованы при выполнении в Институте математики СО РАН следующих научно-исследовательских работ (с указанием номера госрегистрации в случае его присвоения): г/б НИР 01.200.1 18611, индекс научного направления 2.2.4.; г/б НИР 01960002688, индекс научного направления 1.1.11.6; г/б НИР 01960002702, индекс научного направления 1.1.З.; г/б НИР 1.1.8. (приоритетное направление 2 - Прикладная математика; программа 2.5 - Проблемы теоретической кибернетики, дискретного анализа, исследования операций и искусственного интеллекта); грантов РФФИ 93-01-00466-а, 95-01-00930-а, 98-01-00673-а , 01-01-00839-а, 04-01-00858-а, 04-06-80248-а, 05-01-14045-д, 99-04-49535-а, грантов «Интеграционные программы СО РАН»: проекты «Компьютерная система анализа погребальных памятников эпохи неолита и ранней бронзы», «Анализ и моделирование экстремальных гидрологических явлений» программы 13 фундаментальных исследований Президиума РАН.

Цели и задачи работы. Разработка теории и методов решения задач распознавания с использованием класса ЛРФ и позволяющих при выборе оптимальной сложности класса учитывать эмпирические данные и экспертные знания. Разработка методов анализа разнотипных данных (распознавания образов, регрессионного анализа, кластер-анализа, анализа разнотипных временных рядов) в классе ЛРФ. Методы должны позволять решать задачи, характеризующиеся сложными многомодальными распределениями. Цель достигается путем решения следующих задач.

- Нахождение модели, позволяющей как можно более полно учесть особенности класса ЛРФ и удобной для теоретического исследования.

- Разработка способов формализации экспертных знаний о задаче распознавания.

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

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

- Разработка и исследование методов построения ЛРФ в задаче распознавания, основанных на полученных оценках риска.

- Создание эффективных методов и алгоритмов анализа данных в классе ЛРФ.

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

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

- Предложен подход к разработке и исследованию методов построения ЛРФ, в основе которого лежит идея применения байесовской модели распознавания конечного множества событий.

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

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

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

- Предложены критерии качества логических решающих функций, основанные на полученных оценках.

- Разработан рекурсивный метод («Ш-метод») построения дерева решений, позволяющий решать следующие виды задач анализа разнотипных данных: распознавание образов, регрессионный анализ, кластер-анализ, анализ многомерных временных рядов. На основе Ш-метода разработан алгоритм построения леса решений в задачах распознавания и регрессионного анализа.

- Разработан метод прогнозирования экстремальных событий с использованием класса ЛРФ.

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

Методы исследования. В работе использованы методы теории распознавания образов, теории вероятностей, математической статистики, комбинаторного анализа, теории статистических решений, статистическое моделирование, экспериментальные исследования на тестовых и прикладных задачах.

Практическая значимость. Разработанные методы, алгоритмы и программное обеспечение дают возможность решать широкий круг задач анализа разнотипных данных (распознавания образов, регрессионного анализа, кластер-анализа, анализа временных рядов, прогнозирования экстремальных событий) в различных прикладных областях исследований. Результаты работы использовались в таких областях, как:

- генетика (в Институте цитологии и генетики СО РАН для анализа спектров мутаций ДНК);

- археология (в Краеведческом музее г. Новосибирска для классификации древних наконечников стрел; Институте археологии и этнографии СО РАН для анализа антропологических находок эпохи неолита и анализа данных о средневековых вооружениях);

- медицина (в Международном научно-исследовательском институте космической антропоэкологии для анализа влияния факторов среды на показатели здоровья в экстремальных условиях; НИИ терапии СО РАМН для поиска маркеров атеросклероза);

- гидрология (в Новосибирском филиале Института водных и экологических проблем СО РАН для прогнозирования экстремальных гидрологических ситуаций).

Программная система JIACTAH-M, реализующая основные разработанные методы и алгоритмы, доступна через официальный сайт Института математики СО РАН (http://www.math.nsc.ru/AP/datamine/decisiontree.htm).

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

Апробация работы. Основные положения работы докладывались и обсуждались на: Всесоюзной конференции «Статистические методы распознавания образов и компьютерной кластеризации», Киев, 1989 г.; Международных конференциях «Компьютерный анализ данных и моделирование», Минск, 1992, 2001, 2004 гг.; Всероссийских конференциях «Математические проблемы экологии», Новосибирск, 1992, 1994 гг.; Всероссийских конференциях «Математические методы распознавания образов», Москва, 1999, 2003, 2005 гг.; Международной конференции "Second International Conference on Bioinformatics of Genome Regulation and Structure (BGRS-2000)", г. Новосибирск, 2000 г.; Международной конференции «Интеллектуализация обработки информации», г. Алушта, 2000, 2002, 2004 гг.; Международной конференции "Pattern recognition and information processing", Минск, 2003 г.; 3-й Международной конференции "Machine Learning and Data Mining in Pattern Recognition" г. Лейпциг, Германия, 2003 г.; Международном семинаре "6-th Open German-Russian Workshop on Pattern Recognition and Image Understanding" , Алтай, 2003 г.; Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании», г. Алма-Ата, 2004 г., 11-й Международной конференции "Knowledge-Dialog-Solution", г. Варна, Болгария, 2005 г.; на семинаре лаборатории анализа данных ИМ СО РАН, семинаре «Теория вероятностей и математическая статистика» ИМ СО РАН, семинаре отдела теоретической кибернетики ИМ СО РАН, семинаре «Теория статистических решений» кафедры теоретической кибернетики НГУ, семинаре кафедры прикладной математики НГТУ.

Публикации. По теме диссертации опубликовано 58 работ, в том числе: 1 монография в издательстве Института математики СО РАН; 10 статей в журналах, входящих в перечень, рекомендованный ВАК России; 4 статьи в рецензируемых зарубежных журналах издательств Elsevier Science, Oxford University Press, Springer-Verlag; 5 статей в журналах, выходящих в издательствах институтов Академий Наук Болгарии, Украины, Казахстана; 5 статей в сборниках научных трудов; 33 статьи в сборниках трудов Международных и Всероссийских конференций. В списке публикаций автореферата приведено 30 работ автора, отражающих основное содержание диссертации.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 168 наименований, приложения. Работа изложена на 260 страницах основного текста, включая 43 рисунка и 7 таблиц.

Заключение диссертации по теме «Теоретические основы информатики», Бериков, Владимир Борисович

Основные выводы и результаты работы:

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

2. Известные виды критериев качества ЛРФ теоретически обосновываются в рамках различных подходов к анализу прогнозирующей способности. При исследовании прогнозирующей способности методов обучения распознаванию, для того чтобы получить оценки, независимые от распределения, в основном используется либо подход Вапника-Червоненкиса (минимаксный), либо байесовский подход. В диссертационной работе выбран байесовский подход, так как он позволяет учитывать экспертные знания о задаче. Однако в байесовской теории обучения существует ряд актуальных проблем: задание априорного распределения, выражающего экспертные знания; учет специфики метода обучения; повышение надежности и точности оценок качества.

3. Существующие алгоритмы построения решающих деревьев не позволяют находить сложные закономерности в данных (например, в случае «шахматной» структуры данных); либо требуют для этого полный перебор вариантов.

4. В диссертационной работе введен новый вид байесовской модели распознавания конечного множества событий, позволяющий при разработке и исследовании методов построения ЛРФ учитывать экспертные знания о классе распределений (знания, выраженные в априорных предпочтениях на множестве событий, оценках априорных вероятностей образов) и классе решающих функций (знания, отраженные в специфике метода обучения) [20, 23].

5. Для байесовской модели предложен способ формализации экспертных знаний о задаче распознавания, выражающих ожидаемую степень «пересечения» образов [21, 23, 22].

6. Для произвольного метода обучения найдены выражения, позволяющие в рамках байесовской модели находить точечную (ожидаемый риск) и интервальную оценку риска (верхнюю границу риска по стратегиям природы и выборкам) [20, 23]. Эти выражения позволяют находить оптимальную сложность класса решающих функций в зависимости от объема обучающей выборки и знаний эксперта.

7. Для байесовской модели исследована прогнозирующая способность метода минимизации эмпирической ошибки [12, 16, 18]. Получены выражения для математического ожидания и дисперсии (по стратегиям природы и выборкам) величины вероятности ошибки. Найдены также аналогичные выражения для уклонения между вероятностью ошибки данного метода и вероятностью ошибки оптимальной байесовской решающей функции.

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

9. Предложено использовать полученные выше оценки в качестве критерия при построении деревьев решений в задаче распознавания [19, 20, 23].

10. Предложен рекурсивный алгоритм (*Н-метод) [3, 6] построения дерева решений в задачах распознавания и регрессионного анализа, который позволяет обнаруживать более сложные закономерности в анализируемых данных, чем существующие алгоритмы, основанные на деревьях решений. В проведенных экспериментах *И-метод чаще давал значимо меньшую ошибку, чем ряд классических методов распознавания и других методов, использующих деревья решений (либо, при незначительной разнице в ошибке, получал гораздо более простые решения). Существуют примеры задач, которые не смог решить никакой другой алгоритм, кроме рекурсивного.

11. На основе рекурсивного алгоритма разработан алгоритм построения леса решений [1].

12. Алгоритм группировки объектов, созданный на основе переборной схемы *Н-метода, позволяет решать задачу автоматической классификации при наличии разнотипных переменных [24]. Алгоритм позволяет выявлять закономерности, описывающие группы (кластеры).

13. В отличие от существующих методов анализа временных рядов, разработанный алгоритм построения дерева решений на основе 9^-метода [5] позволяет обрабатывать многомерные разнотипные ряды и обнаруживать в них логические закономерности.

14. Разработанный алгоритм прогнозирования экстремальных событий [29] позволяет анализировать несбалансированные таблицы данных, которые содержат редкие события, сопряженные с большими потерями. Методика прогнозирования основана на построении дерева событий с помощью разработанных в диссертации алгоритмов, использующих решающие деревья.

15. На основе методов и алгоритмов, описанных в диссертационной работе, создан комплекс программ ЛАСТАН-М [1, 20], позволяющий решать задачи анализа разнотипной информации (распознавание образов, регрессионный анализ, группировка объектов, анализ многомерных временных рядов).

16. Разработанные методы были применены для: анализа спектров мутаций в ДНК [6, И, 9], анализа антропологических находок эпохи неолита [25], прогнозирования экстремальных гидрологических ситуаций [27], анализа влияния факторов среды на показатели здоровья в экстремальных условиях [13], построения модели прогноза здоровья человека [7], нахождения маркеров атеросклероза (х/д работа с НИИ терапии СО РАМН), анализа качества жизни и здоровья населения в индексах функции дожития (х/д работа с ИКЭМ СО РАМН) и др.

17. Вышесказанное позволяет заключить, что в диссертации разработан новый подход к разработке и исследованию методов построения ЛРФ. Подход основан на применении модели распознавания конечного множества событий и нахождении байесовских точечных и интервальных оценок риска. В отличие от других подходов, предложенный обладает рядом преимуществ: учитывает экспертные знания, не требует постулирования модели распределения, позволяет проводить теоретические исследования при любых объемах выборки, принимает во внимание специфику метода обучения.

Заключение

Список литературы диссертационного исследования доктор технических наук Бериков, Владимир Борисович, 2006 год

1. Основные публикации автора:

2. Лбов Г.С., Бериков В.Б. Устойчивость решающих функций в задачах распознавания образов и анализа разнотипной информации. Новосибирск: Изд-во Ин-та математики, 2005. - 218 с.

3. Бериков В.Б., Лбов Г.С. Рекурсивные алгоритмы решения задач дис-криминантного и регрессионного анализа // В кн. «Машинное моделирование и планирование эксперимента». Новосибирск, НЭТИ. 1991. С. 48-52.

4. Berikov V.B. On the convergence of logical decision functions to optimal decision functions // Pattern Recognition and Image Analysis, Vol. 5, N 1, 1995. P. 1-6. О сходимости логических решающих функций к оптимальным решающим функциям.

5. Lbov G.S., Berikov V.B. Recognition of a Dynamic Object and Prediction of Quantitative Characteristics in the Class of Logical Functions // Pattern

6. Recognition and Image Analysis, Vol. 7, N 4, 1997. P. 407-413. Распознавание динамического объекта и прогнозирование количественных характеристик в классе логических решающих функций.

7. Berikov V.B., Rogozin I.В. Regression trees for analysis of mutational spectra in nucleotide sequences // Bioinformatics, Vol. 15, 1999. P. 553-562. Деревья регрессии для анализа спектров мутаций в нуклеотидных последовательностях.

8. Казначеев В.П., Лбов Г.С., Бериков В.Б. и др. Гелиофизические факторы среды при перинатальном развитии в вероятностной модели прогноза здоровья человека // Вестник МНИИКА, №6, 1999. С. 37-43.

9. Бериков В.Б. Об устойчивости алгоритмов распознавания в дискретной постановке // Искусственный интеллект, №2, 2000. С. 5-8.

10. Рогозин И.Б., Бериков В.Б. Васюнина Е.А., Синицина О.Е. Исследование влияния особенностей первичной структуры ДНК на возникновение мутаций, индуцированных алкилирующими агентами // Генетика, Т. 37, №6, 2001. С. 854-861.

11. Berikov, V.B. An approach to the evaluation of the performance of a discrete classifier // Pattern Recognition Letters, Vol. 23 (1-3), 2002. P. 227-233. Подход к оцениванию качества дискретного классификатора.

12. Berikov, V.B. A priori estimates of recognition quality for discrete features // Pattern Recognition and Image Analysis, Vol. 12, N 3, 2002. P. 235-242. Априорные оценки качества распознавания для дискретных признаков.

13. Бериков В.Б. Методика статистического исследования для анализа пси-щ хофизиологических резервов организма человека // Вестник МНИИ1. КА, №9, 2002. С. 122-132.

14. В.Б.Бериков, А.Г. Литвиненко. Оценка надежности классификации в дискретной задаче распознавания // Искусственный интеллект, №2, 2002. С. 39-45.

15. Berikov V.B., Litvinenko A.G. The influence of prior knowledge on the expected performance of a classifier // Pattern Recognition Letters, Vol. 24, N 15, 2003. P. 2537-2548. Влияние априорных знаний на ожидаемое качество классификатора.

16. Бериков В.Б. Априорные оценки качества распознавания при ограниченном объеме обучающей выборки // Журн. вычисл. математики и мат. физики, Т. 43, №9, 2003. С. 1448-1456.

17. Бериков В.Б. Некоторые свойства оценки вероятности ошибки в дис-Щ кретной задаче распознавания // Сибирский журнал индустриальнойматематики, Т. 7, №3(19), 2004. С. 44-56.

18. Бериков В.Б., Литвиненко А.Г. Выбор оптимальной сложности решающей функции в дискретной задаче распознавания // Искусственный интеллект, №2, 2004. С. 17-21.

19. В.Б.Бериков, Г.С.Лбов. Байесовские оценки качества распознавания по конечному множеству событий // Доклады РАН, Т. 402, №1, 2005. С. 1-4.

20. Бериков В.Б. Байесовские критерии качества деревьев решений // Математический журнал Института математики МОН РК. Т. 5, №4(18), 2005. С. 44-51.

21. Berikov V.B. Bayes estimates for recognition quality on a finite set of events // Pattern Recognition and Image Analysis. V. 16, N 3, 2006. P. 329-343. Байесовские оценки качества распознавания на конечном множестве событий.

22. Бериков В.Б. Байесовский принцип учета априорной информации в задачах распознавания // Сб. трудов 6-й Международной конференции «Распознавание образов и анализ изображений» (РОАИ'2002). Великий Новгород, 2002. С. 61-65.

23. Berikov V.B. Evaluation of classifier performance in descrete pattern récognition problem // Proc. of the 7th Korea-Russia International Symposium "KORUS". Ulsan, 2003. P. 201-205. Оценивание качества классификатора в дискретной задаче распознавания.

24. Бериков В.Б., Лбов Г.С. О прогнозирующей способности методов распознавания // Докл. Всероссийской конференции «Математические методы распознавания образов» ММРО-12. Москва, 2005. С. 29-32.

25. Список цитируемой литературы

26. Айвазян С.А., Енюков Е.С., Мешалкин И.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика, 1988. 450 с.

27. Айзерман М.А., Браверман. Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. 383 с.

28. Андерсон Т. Введение в многомерный статистический анализ: Пер. с англ. М.: Физматгиз, 1963. 500 с.

29. Аркадьев А.Г., Браверман Э.М. Обучение машины классификации объектов. М.: Наука, 1971. - 172 с.

30. Беркинблит М.Б. Нейронные сети. М.: МИРОС, 1993. - 156 с.

31. Бокс Д., Дженкинс Г. Анализ временных рядов: прогноз и управление. М.: Мир, 1974. Вып. 1 406 е.; вып. 2 - 197 с.

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

33. Боровков A.A. О задаче распознавания образов // Теория вероятностей и ее применение, 1971. Т.16. №1. С. 132-136.

34. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983. 464с.

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

36. Васильев В.И. Распознающие системы. Киев: Наук, думка, 1969. 292 с.

37. Васильев В.И. Проблема обучения распознаванию образов. Принципы, алгоритмы, реализация. Киев: Высш. школа, 1989. 64 с.

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

39. Вапник В.Н., Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 449 с.

40. Воронин Ю.А. Теория классификации и ее приложение. Новосибирск: Наука, 1982. 194 с.

41. Воронцов, К. В. Комбинаторные оценки качества обучения по прецедентам // Доклады РАН, Т.394, №2. 2004. С. 175-178.

42. Гладун В.П. Эвристический поиск в сложных средах. Киев: Наук, думка, 1977. 166 с.

43. Горелик A.JI., Скрипкин В.А. Методы распознавания. М.: Высш. школа, 1977. 222 с.

44. Гуров С.И. Оценка надежности классифицирующих алгоритмов. Учебное пособие. М.: Изд-во МГУ, 2002. 3 п.л.

45. Деев А.Д. Асимптотические разложения распределений статистик дис-криминантного анализа // Статистические методы классификации. М.: Изд-во МГУ, 1972. Вып. 31. С. 12-23.

46. Дискант В.А. Алгоритмы построения правил классификации в структурно аналитических моделях распознавания // Математические методы анализа динамических систем. Харьков: изд-во ХАИ, 1983. Вып. 7. С. 124-127.

47. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений // Дискрет, анализ. Новосибирск, 1966. Вып. 7. С. 3-15.

48. Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // Журн. вычисл. математики и мат. физики. 1982, Т.22, №4. С. 963-974.

49. Донской В.И., Башта А.И. Дискретные модели принятия решений при неполной информации. Симферополь: Таврия, 1992. - 166 с.

50. Дорофеюк A.A. Алгоритмы обучения машины распознаванию образов без учителя, основанные на методе потенциальных функций. Автоматика и телемеханика. 1966, №10. С. 78-88.

51. Дуда P.O., Харт П.Е. Распознавание образов и анализ сцен. М.: Мир, 1976. -559 с.

52. ДюковаЕ.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. Учебное пособие. М.: Прометей, 2003. 29 с.

53. Журавлев Ю.И., Никифоров B.B. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. №3. С. 1-12.

54. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: Изд-во ФАН УзССР, 1974. -119 с.

55. Журавлев Ю.И. Непараметрические задачи распознавания // Кибернетика. 1976. №6. С. 93-103.

56. Журавлев Ю.И. Избранные научные труды. М.: Магистр, 1999. 420 с.

57. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972. 206 с.

58. Загоруйко Н.Г. Искусственный интеллект и эмпирическое предсказание. Новосибирск: Изд-во НГУ, 1975. 82 с.

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

60. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999. 270 с.

61. Загоруйко Н.Г., Елкина В.Н., Емельянов C.B., Лбов Г.С. Пакет прикладных программ ОТЭКС. М.: Финансы и статистика, 1986.

62. Закревский А.Д., Торопов И.Р. Обучение распознаванию образов в булевом пространстве // Самообучающиеся автоматические системы. М: Наука, 1966. С.6-16.

63. Ивахненко А.Г. Самообучающиеся системы распознавания и автоматического регулирования. Киев: Техника, 1969. 392 с.

64. Кендэл М. Временные ряды. М.: Финансы и Статистика, 1981. 199 с.

65. Кокрен У. Методы выборочного обследования. М.:Статистика, 1976. -400 с.

66. Котюков В.И. Многофакторные кусочно-линейные модели. М.: Финансы и статистика, 1984. 216 с.

67. Котюков В.И. Распознавание образов в булевом пространстве // Вычислительные системы. 1971. Вып.44. С. 23-34.

68. Л.С.Кучмент, А.Н.Гельфанд. Динамико-стохастические модели формирования речного стока. М.: Наука. 1993.

69. Лапко А.В. Непараметрические методы классификации и их применение. Новосибирск: Наука, 1993. 152 с.

70. Лбов Г. С. Выбор эффективной системы зависимых признаков // Вычислительные системы. 1965. Вып. 19. С. 21-34.

71. Лбов Г. С. О представительности выборки при выборе эффективной системы признаков // Вычислительные системы. 1966. Вып. 22. С. 3952.

72. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, 1981. 160 с.

73. Лбов Г. С., Котюков В. И., Манохин А. Н. Об одном алгоритме распознавания в пространстве разнотипных признаков // Вычислительные системы. Новосибирск, 1973. Вып. 55. С. 97-107.

74. Лбов Г.С., Старцева Н.Г. Сравнение алгоритмов распознавания с помощью программной системы Полигон. Вычислительные системы. 1990. Вып. 134. С. 56-66.

75. Лбов Г. С., Старцева Н. Г. Сложность распределений в задачах классификации // Докл. РАН. 1994. Т. 338, №5. С. 592-594.

76. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск: Изд-во Ин-та математики, 1999. 212 с.

77. Леман Э. Теория точечного оценивания. М.: Наука, 1991. 448 с.

78. Мазуров В.Д. Комитеты систем неравенств и задача распознавания. Кибернетика. 1971. №3. С. 140-146.

79. Манохин А.Н. Методы распознавания образов, основанные на логических решающих функциях // Вычислительные системы. 1976. Вып. 67. С.42-53.

80. Манохин А.Н. О свойствах инвариантности и состоятельности алгоритмов распознавания, основанных на логических решающих функциях // Вычислительные системы. 1980. Вып. 83. С. 42-52.

81. Надарая Э.Я. Об оценке регрессии // Теория вероятн. и ее применения. 1964. №9. С. 157-159.

82. Нильсон Н. Обучающиеся машины. М: Мир, 1967. 180 с.

83. Пфанцагль И. Теория измерений. М.: Мир, 1976. 248 с.

84. Растригин Л.А., Эренштейн Р.Х. Принятие решений коллективом решающих правил в задачах распознавания образов. Автоматика и телемеханика. 1975. №9. С. 133-144.

85. Раудис Ш. Ограниченность выборки в задачах классификации // Статистические проблемы управления. Вильнюс, 1976. Вып. 18. С. 1-185.

86. Раудис Ш. Влияние объема выборки на качество классификации (обзор) // Статистические проблемы управления. Вильнюс, 1984. Вып. 66. С. 9-42.

87. Розенблатт Ф. Принципы нейродинамики. Перцептрон и теория механизмов мозга. М.: Мир, 1965. 480 с.

88. Старцева Н.Г. LRP Логическое распознающее правило (Описание программы. Решение модельных и прикладных задач) // Вычислительные системы. 1985. Вып. 111. С. 11-22.

89. Старцева Н.Г. О статистической устойчивости в задачах классификации // Докл. РАН. 1992. Т. 325, №5. С. 441-444.

90. Суппес П., Зинес Дж. Основы теории измерений // Психологические измерения. М.: 1967. С. 9-110.

91. Тарасенко Ф.П. Непараметрическая статистика. Томск: Изд-во Томск. гоС. ун-та, 1976. - 292 с.

92. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 3. М.: Физматлит, 1960. 728 с.

93. Фу К.С. Последовательные методы в распознавании образов и обучении машин. М.: Наука, 1971. 255 с.

94. Фукунага К. Введение в статистическую теорию распознавания образов. М.: Наука, 1979. -367 с.

95. Хант Э. Искусственный интеллект М.: Мир, 1978.

96. Хант Э., Марин Дж., Стоун Ф. Моделирование процесса формирования понятий на вычислительной машине. М.: Мир, 1970. 301 с.

97. Харин Ю.С. Робастность процедур дискриминантного анализа (обзор) // Заводская лаборатория. 1990. Т. 56, №10. С. 69-72.

98. Ченцов H.H. Оценка неизвестной плотности по наблюдениям // Докл. АН СССР. 1962. Т. 147, №1. С. 45-48.

99. Шурыгин A.M. Прикладная стохастика: робастность, оценивание, прогноз. М.: Финансы и статистика, 2000. 224 с.

100. Akaike Н. A new look at the statistical model identification // IEEE Trans. Autom. Control. 1974. V.19, N 6. P. 716-723.

101. Alon N., Ben-David S., Cesa-Bianchi N, Haussler D. Scale-sensitive dimensions, uniform convergence, and learnability //J. ACM, N 44. 1997. P. 615-631.

102. Andras A., Kegl B., Linder T., Lugosi G. Data-dependent margin-based generalization bounds for classification //J. Mach. Learn. Research. 2002. N 3. P. 73-98.

103. Bartlett P.L. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network // IEEE Trans. Inform. Theory. 1998. N 44. P. 525-536.

104. Berger J. An overview of robust Bayesian Analisis // Tech. rep. 93-53C, Department of Statistics, Purdue University, 1993.

105. Boucheron S., Lugosi G., Massart P. A sharp concentration inequality with applications // Random Structures and Algorithms. 2000. N 16, P. 277-292.

106. Bousquet O., Elisseeff A. Algorithmic Stability and Generalization Performance // Adv. Neural Inform. Process. Systems. 2001. N 13, P. 196202.

107. Breiman L., Friedman J., Olshen R., Stone C. Classification and Regression Trees. Belmont, CA: Wadsworth Int. Group, 1984.

108. Breiman L. Bagging predictors // Mach. Learn. 1996. V. 24. P. 123-140.

109. Buhlmann H. Mathematical Methods in Risk Theory. Berlin: Springer-Verl., 1996.- 324 p.

110. Buntine W., Weigend A. Bayesian back propagation // Complex systems.1991. N 5. P.603-643.

111. W. Buntine. Learning classification trees // Statistics and Computing.1992. V. 2. P. 63-73.

112. Burges C. A Tutorial on Support Vector Machines for Pattern Recognition 11 Data Mining and Knowledge Discovery, Vol.2, N 2. 1998. P. 121-167.

113. Carnevali P., Coletti L., Patarnello S. Image Processing by Simulated Annealing // IBM J. Research and Developement, V. 29, N 6. 1985. P. 569-579.

114. Chandrasekaran, B. Independence of measurements and the mean recognition accuracy // IEEE Trans. Inform. Theory. 1971. V. 17. P. 452-456.

115. Cover T. M. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition // IEEE Transactions on Electronic Computers. 1965. N 14. P. 326-334.

116. Cover T.M., Hart P.E. Nearest neighbour pattern classification.- IEEE Trans. Inform. Theory. 1967. V. 13. P. 21-27.

117. Cramer, H. On the Mathematical Theory of Risk. Skandia Jubilee Volume. Stockholm. 1930. P. 7-84.

118. Duin R. The mean recognition performance for independent distributions. IEEE Trans. Inform. Theory. 1978. V. 24. P. 394-395.

119. Duin, R. The Combining Classifier: To Train Or Not To Train? // Proc. 16 Internat. Conf. on Pattern Recognition. Quebec, 2002. V. 2. P. 765-770.

120. Embrechts P, Klueppelberg, C, Mikosch, T. Modelling Extremal Events for Insurance and Finance. Berlin: Springer-Verl., 1997. 648 p.

121. Esposito, F., Malerba, D., Semerato, G. A comparative analysis of methods for pruning decision trees // IEEE Trans. Pattern Anal. Mach. Intell. 1997. V.19, N 5. P. 476-491.

122. Fowler, R.G. and Schaaper R.M. The role of-the mutT gene of Escherichia coli in maintaining replication fidelity // FEMS Microbiol. Rev., N 21.1997. P. 43-54.

123. Geman S., Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images // IEEE Trans. Pattern Anal. Mach. Intell. 1984. N 6. P. 721-741.

124. Glazko G.V., Milanesi L.,Rogozin I.B. The subclass approach for mutational spectrum analysis: application of the SEM algorithm //J. Theor. Biol. 1998. V. 192. P. 475-487.

125. Godwin H.J. On Generalizations of Tchebychef's Inequality //J. Amer. Stat. Ass. 1955. V. 50(271). P. 923-945.

126. Gould H. W. Combinatorial Identities, a Standardized Set of Tables Listing 500 Binomial Coefficient Summations. Morgantown: West Wirg. Univ. Press, 1972.

127. Grunwald P. D.,Vitanyi P. M. B. Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers. //J. Logic, Language, and Information. 2003. V. 12(4). P. 497-529.

128. Hand D. J. Construction and Assessment of Classification Rules. Chichester, England: John Wiley & Sons, 1997. 232 p.

129. Hanich W. Design and optimization of a hierarchical clasifier //J. New Generat. Comput. Syst. 1990. N 2. P. 159-173.

130. Haussler D. Probably approximately correct learning // Proc. 8 Nation. Conf. on Artificial Intelligence. Boston, MA: Morgan Kaufmann, 1990. P. 1101-1108.

131. D.Haussler, M.Kearns, and R.Schapire. Bounds on sample complexity of Bayesian learning using information theory and the VC dimension // Mach. Learn. 1994. N 14. P. 84-114.

132. Heckerman D., Geiger D., Chickering D. Learning Bayesian networks: The combination of knowledge and statistical data // Machine Learning, V. 20, N 3. 1995. P. 197-243.

133. Ho T.K., Hull J.J., Srihari S.N. Decision combination in multiple classifier systems 11 IEEE Trans. Pattern Anal. Mach.e Intell. 1994. V. 16, N 1. P. 66-75.

134. Hughes G.F. On the mean accuracy of statistical pattern recognizers // IEEE Trans. Inform. Theory. 1968. V. 14, N 1. P. 55-63.

135. Hyafil 1., Rivest R. Constructing Optimal Binary Decision Trees is NP-complete // Inf. Proc. Letters. V. 5, 1976. P. 15-17.

136. Jain A.K., Duin R.P.W., Mao J. Statistical Pattern Recognition: a Review // IEEE Trans. Pattern Anal. Mach. Intell. 2000. V. 22(1). P. 4-37.

137. Kearns M.J., Ron D. Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation // Proc 10 Annual Conf. on Computational Learning Theory. Nashville, 1997. P. 152-162.

138. Kolmogorov A. N. Three approaches to the quantitative definitions of information, Prob. Inf. Transm. 1965. 1(1), P. 1-7.

139. Loh W.Y., Vanichsetakul N. Tree-structured classification via generalized discriminant analysis (with discussion) // Journal of the American Statistical Association. 1988. Vol. 83, P. 715-728.

140. Lugosi G. Improved Upper Bounds for Probabilities of Uniform Deviations // Statist. Probab. Lett. 1995. N 25. P. 71-77.

141. McAllester D.A. Some pac-bayesian theorems // Proc. 11 Annual Conference on Computational Learning Theory. Madison, 1998. P. 230-234.

142. Meisel W.S., Michalopoulos D.A. A partitioning algorithm with application in pattern classification and the optimization of decision trees // IEEE Trans. Comput. 1973. N 22. P. 93-103.

143. Michalski R. S. Variable-valued logic: system VL1 // Proc. Symp. Multiple Valued Logic. Morgentown, 1974. P. 323-346.

144. Morgan J.N., Sonquist J.A.: Problems in the analysis of survey data, and a proposal // American Statistical Association Journal. 1963. pp. 415-434.

145. Nedel'ko V.M. On the accuracy of Vapnik-Chervonenkis risk estimations in discrete case // Proc. 7 Internat. Conf. Pattern Recognition Information Processing. Minsk, 2003. V. 2. P. 75-79.

146. Niblett T., Bratko I. Learning decision rules in noisy domains // Developments in Expert Systems: Proc. / Expert Systems 86 Conf., Brighton, 15-18 Dec. 1986. Cambridge: Univ. Press, 1986.

147. Opper M., Haussler D. Generalization performance of Bayes optimal classification algorithm for learning a perceptron // Physical Review Lett. 1991. V. 66, N 20. P. 2677-2680.

148. Parzen E. An estimation of a probability density function and mode. Ann. Math. Statist. 1962. N33. P. 1065-1076.

149. Quinlan J. R. C4.5: Programs forMachine Learning. San Francisco: Morgan Kaufmann, 1993.

150. Raudys S. Statistical and Neural Classifiers: An integrated approach to design. London: Springer-Verl., 2001.

151. Rissanen J. Minimum-description-length principle // Ann. Statist. 1985. V. 6. P. 461-464.

152. Rosenblatt M. Remarks on some nonparametric estimates of a density function // Ann. Math. Statist. 1956. N 27. P.642-669.

153. Safavian S.R., Landgrebe D. A Survey of Decision Tree Classifier Methodology // IEEE Trans. Systems, Man, and Cybernetics. 1991. Vol. 21, No. 3. P. 660-674.

154. Scheffer T. Predicting the Generalization Performance of Cross Validatory Model Selection Criteria // Proc. 17 Internat. Conf. on Machine Learning. San Francisco: Morgan Kaufmann, 2000. P. 831-838.

155. Scott C., Nowak R. Dyadic classification trees via structural risk minimization // Neural Information Processing Systems NIPS 2002, Dec. 9-14, Vancouver, Canada, 2002.

156. Sethi I., Sarvarayudu. Hierarchical classifier design using mutual information IEEE Trans. Pattern Anal, and Mach. Intell. 1982. N. 4. P. 441-445.

157. Shawe-Taylor J., Bartlett P.L., Williamson R.C., Anthony M. Structural risk minimization over data-dependent hierarchies // IEEE Trans. Inform. Theory. 1998. N 44. P. 1926-1940.

158. Shawe-Taylor J., Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge: Univ. Press, 2003.

159. Talagrand M. Sharper Bounds for Gaussian and Empirical Processes // Ann. Probab. 1994. V. 22, N 1. P.28-76.

160. Valiant L.G. A Theory of the Learnable // Communications of the Association for Computing Machinery. 1984. V. 17(11). P. 1134-1142.

161. Vapnik V., Levin E. and Le Cun Y. Measuring the VC-Dimension of a Learning Machine // Neural Comput. 1994. V. 6, N 5, P. 851-876.

162. Vapnik V.N. An Overview of Statistical Learning Theory // IEEE Trans. Neural Networks. 1999. V. 10, N 5. P. 988-999.

163. Wallace C. S. and Boulton D. M. An information measure for classification // Comput. J. 1968. N 11. P. 185-195.