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

РГв Од

иоЗи55Э13

Бериков Владимир Борисович

г'Г

л"

ВЫБОР ОПТИМАЛЬНОЙ СЛОЖНОСТИ КЛАССА ЛОГИЧЕСКИХ РЕШАЮЩИХ ФУНКЦИЙ В ЗАДАЧАХ АНАЛИЗА РАЗНОТИПНЫХ ДАННЫХ

05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Новосибирск - 2007

003055919

Работа выполнена в Институте математики им. С Л. Соболева СО РАН (Новосибирск).

Научный консультант:

доктор технических наук, профессор Лбов Геннадий Сергеевич

Официальные оппоненты:

доктор технических наук,

профессор Котюков Владислав Игоревич,

доктор технических наук, профессор Павлов Виктор Николаевич,

доктор физико-математических наук, профессор Попков Владимир Константинович.

Ведущая организация Вычислительный Центр РАН (Москва).

Защита состоится 23 мая 2007 г. в 14.00 на заседании диссертационного совета Д 212.173.06 при ГОУ ВПО «Новосибирский государственный технический университет» по адресу 630092, г. Новосибирск, проспект Карла Маркса, 20.

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

Автореферат разослан Г^- 2007 г.

Ученый секретарь М & - Чубич В М.

диссертационного совета (КХл^

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

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

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

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

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

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

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

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

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

Провести такой учет позволяет байесовская теория обучения. В основе этого направления лежит идея использования априорных знаний о решаемой задаче, позволяющих, в частности, сопоставить каждому возможному распределению («стратегии», «состоянию» природы) некоторый вес. Этот вес отражает интуитивную уверенность эксперта в том, что неизвестное истинное распределение совпадает с рассматриваемым. В первых работах в данном направлении находились байесовские оценки параметров моделей распознавания. Рядом авторов (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 фундаментальных исследований Президиума РАН.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

средневековых вооружениях);

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

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

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

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

Апробация работы. Основные положения работы докладывались и обсуждались на- Всесоюзной конференции «Статистические методы распознавания образов и компьютерной кластеризации», Киев, 1989 г.; Международных конференциях «Компьютерный анализ данных и моделирование», Минск, 1992, 2001, 2004 гг.; Всероссийских конференциях «Математические проблемы экологии», Новосибирск, 1992,1994 гг.; Всероссийских конференциях «Математические методы распознавания образов», Москва, 1999, 2003, 2005 гг.; Международной конференции "Second International Conference on Bioinforma-tics 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", r. Лейпциг, Германия, 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 является вводной. В ней даются основные понятия теории распознавания образов, делается обзор методов распознавания. Рассматриваются способы определения качества метода. Вводится класс логических решающих функций (деревьев решений).

В параграфе 1.1 даются основные понятия теории распознавания образов

Пусть определена генеральная совокупность Г объектов, которые входят в круг интересов исследователя. Предположим, что каждый объект можно описать набором переменных Х\,... ,Xj,...,Хп. Множество всевозможных значений, которые может принимать Xj, обозначим через Dj.

Набор X = (Xi,...,Xn) может содержать как количественные, так и качественные переменные. Множество всевозможных значений, которые может принимать X, обозначим Dx = D\ х ■ ■ ■ х Dn.

Для произвольного объекта а € Г набор наблюдений его характеристик -это набор Х(а) = х = (х\,... ,Xj,..., хп), где xj — Х3{а) обозначает значение характеристики Х3 для объекта а.

Дополнительно к набору X определена целевая (предсказываемая) переменная У. Множество значений У обозначим через Dy. Будем полагать, что переменные X, У - случайные. Предположим, что на множестве Dz = Dx х Dy задана вероятностная мера p(Z) (закон распределения величины Z=(X,Y)).

Если переменная У - качественная, то задачу предсказания ее значения по произвольному набору значений X назовем задачей распознавания образов. Если переменная У -количественная, то задачу предсказания назовем задачей регрессионного анализа.

Отображение / : Dx —* Dy называется решающей функцией. Пусть Ф° -множество всевозможных решающих функций. Обычно вводится некоторое ограничение на класс решающих функций, т. е. / € Ф, Ф С Ф°.

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

д. Будем называть функцию потерь индикаторной, если Ь^ = 0 и Ь1Л — 1 при г ф д, г, я = 1,..., К.

Если перейти на язык теории игр, то можно считать, что природа играет против нас стратегией в = р(х, у) из множества Л, а мы играем стратегией / из Ф. Тогда паре (в, /) сопоставляются ожидаемые потери (риск) при прогнозировании произвольного наблюдения

Щ(в) = Е = / £/(«),„<*?(*)• (1)

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

Оптимальной байесовской решающей функцией назовем такую решающую функцию /в £ Ф°, для которой выполняется Д/в(0) = шЭту

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

Будем полагать, что выборка V = где хМ = Х(а^), уМ =

г = 1,..., N формируется в результате случайного независимого отбора некоторых представителей а^ совокупности Г. Число N называют объемом, обучающей выборки.

Будем называть методом построения решающих функций (методом обучения) некоторую процедуру которая на основе обучающей выборки у и ограничений на класс стратегий природы Л или (и) на класс решающих функций Ф строит решающую функцию /. Метод /х можно рассматривать как функцию, задающую отображение множества всевозможных выборок V во множество решающих функций Ф: / = [¿(у). Будем полагать, что при построении решающих функций метод ц использует некоторый критерий оптимальности функции / на заданной выборке. В идеале требуется по обучающей выборке найти такую решающую функцию, для которой риск минимален. Взамен неизвестного риска может быть использована найденная некоторым способом по выборке оценка Как правило, критерий совпадает с оценкой риска. Например, оценка эмпирического риска основана на замене оператора математического ожидания в (1) усреднением по обучающей выл _ л n борке: Я» (у) = Я/(«), где Д/(г;) = ^ £ ^/(аМ)^«-

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

Существуют два подхода к построению решающих функций: а) функция строится на основе ограничений на класс распределений; б) функция строится на основе ограничений на класс решающих функций. Оба варианта

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

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

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

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

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

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

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

При исследовании качества решающих функций важную роль играют понятия сложности класса решающих функций и класса распределений. Под сложностью Мф класса решающих функций Ф можно понимать, например, число параметров дискриминантной функции; емкостную характеристику класса; максимально допустимое число листьев дерева решений и т.д. Под сложностью М\ класса распределений Л можно понимать число параметров функции распределения; степень гладкости плотности и т.д.

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

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

Ниже рассматриваются некоторые известные в литературе способы определения качества метода.

a) Ожидаемый по выборкам риск. Риск для метода /х построения решающей функции по случайной выборке V обозначим как Я^(у){9). Для метода д можно определить качество распознавания как математическое ожидание риска ЕгДе усреднение проводится по всевозможным выборкам идг заданного объема N1 полученным в соответствии со стратегией природы 9. В некоторых задачах можно вычислить асимптотический ожидаемый риск Яи}оо(0) = Ига ЕД„/у \(в). Степенью адекватности метода

' iv—>оо ^ '

к стратегии природы 9 назовем величину 7Д0) = Я^оо(9) — Rfв(9), где Я/в(9) — риск для оптимальной (байесовской) решающей функции. Величину = — Я^оо(9) назовем эффектом ограниченности выборки для метода уи. Тогда математическое ожидание риска, очевидно, будет представлено выражением

Е-й>„)(0) = ДЛ(0) + Ъ(в) + М9,Ю.

Таким образом, качество распознавания зависит от информативности исходной системы переменных Я/в{9) (которая не зависит от метода), от соответствия тц(9) выбранной математической модели распознавания действительному распределению, и от эффекта, связанного с ограниченным объемом выборки *Сц(9,Ы).

b) Верхняя доверительная граница риска по выборкам. Пусть задана вероятность г] и выполняется Р <е)>г] Тогда качество метода при объеме выборки N определяется величиной е = ем(9, М$, ЛГ, 77) (верхней доверительной границей риска): чем меньше е, тем выше обобщающая способность; величина 77 выражает надежность метода.

Основная проблема при использовании вышеописанных показателей качества заключается в том, что стратегия природы 9 неизвестна. Для оценивания риска применяются различные неравенства (Маркова, Чернова и др.), описывающие эффект «концентрации» случайной величины вблизи ее математического ожидания. Эти неравенства справедливы для любых стратегий, включая наименее благоприятную

c) Ожидаемый риск по стратегиям природы и выборкам. Вместо привлечения гипотезы о наименее благоприятной стратегии природы можно использовать (в соответствии с байесовским подходом) усреднение по всем 9 & А и выборкам у^. При этом стратегия выступает в качестве случайного вектора © параметров модели распределения с некоторой заданной плотностью р(9). Таким образом, качество распознавания для метода ц выражается величиной

<1) Верхняя граница риска по стратегиям природы и выборкам.

Для случайного риска (как функции случайной стратегии © и слу-

чайной выборки У^у) потребуем, чтобы с вероятностью не меньше заданной величины г] выполнялось Р (6>) <е)>г/- Здесь е = еДМд, Мф, ./V, 77)

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

Проводимое в данной работе исследование опирается на способы с) и с!) определения качества. Требуется получить зависимости между качеством метода и рассматриваемыми показателями сложности с учетом объема выборки и априорной информации (знаний экспертов).

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

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

Логическую решающую функцию можно представить в виде набора высказываний вида «Если х е Е^, то у = У(тЬ, где У^ е Оу, ...,

- разбиение пространства е^ = е[ш) х • • ■ х е{™], е^т) С и3, е™ есть интервал в случае количественной переменной Х3, либо произвольное подмножество значений в случае номинальной или булевой Х}, т = 1,2,. ., М, ¿ = 1,2,....п.

Описывается предложенный Г.С. Лбовым и Н.Г. Старцевой способ упорядочения распределений по сложности с помощью класса логических решающих функций.

В параграфе 1.5 описывается удобная форма представления логической решающей функции - дерево решений. В дереве решений (не обязательно дихотомическом) каждой внутренней вершине (узлу) соответствует некоторая характеристика а ветвям, выходящим из данной вершины соответствует истинность определенного высказывания вида € '», где г = 1,... ,1,1 >

2 - число ветвей, выходящих из данной вершины, причем набор ..., Е® есть разбиение Иу Каждому тп-му листу дерева приписывается решение (номер соответствующего класса) у(т), т = 1,2,... М, где М - число листьев дерева.

Цепочке ветвей дерева, ведущих из корневой вершины в т-й лист, можно сопоставить логическое утверждение вида — «Если € Е^1^ И хл €

Л .72

Е^ И ■ ■ • И хлп € Е^'1т\ то У — у(т)», где дт - длина данной цепочки.

32 ■>Чт Здт

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

цирование.

Описывается алгоритм последовательного ветвления для построения дерева решений. Рассматриваются методы построения набора деревьев (решающего леса), описываются алгоритмы построения деревьев, основанные на редуцировании. Проводится критический обзор наиболее известных программно-алгоритмических разработок для построения деревьев решений (ЛРП, AID, ID3, С4 5, CART, IND и др.).

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

В параграфе 2.1 описывается задача распознавания конечного множества событий, возникающая при разбиении пространства переменных на некоторое конечное число подобластей. Если ввести новую переменную, значениям которой соответствуют данные подобласти, то получим случай распознавания по значениям одной дискретной неупорядоченной переменной (заметим, что в работе [26] автором предлагалась также байесовская модель распознавания по переменной с упорядоченными значениями, однако ее исследование проводилось только методом статистического моделирования).

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

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

Для удобства записи, будем использовать следующие соглашения. Выражение обозначает произведение х.. (х + п — 1), где п - натуральное число. Оператор ^ (а также П) означает, что суммирование (умножение) j _ з

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

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

дискретные случайные переменные: входную переменную X с множеством неупорядоченных значений Dx = {ci,..., см}, где cj - j-e значение (ячейка) и выходную переменную Y с множеством неупорядоченных значений Dy — {w^,... , гдеи;^> -i-e значение, называемоег-м образом (клас-

сом), К >2 - число образов. Далее, для удобства, закодируем значения переменной X через номера ячеек, а образы - через соответствующие им номера. Пусть р^ - вероятность совместного события «X = j, Y = г», при этом

выполняется р^ > 0, — I7 J = 1,...,М, i — 1 ,...,К. Обозначим

ÍJ

9 = (0Ь.. ,в3,.. ,вм), где Bj = (pfKpfK ■■■,P{f))- Обозначим априорную

вероятность г-го образа через pW. Очевидно, что EjP^ = 1> Ejí^ ~ Р^

Для решения задачи распознавания требуется найти решающую функцию f : Dx —■► Dy. Пусть имеется некоторый класс Ф решающих функций распознавания. Величину М будем называть сложностью класса Каждой решающей функции / из Ф можно сопоставить ожидаемые потери (риск) при распознавании произвольного наблюдения

М К 3=1 t=l

Если бы вектор в был известен, можно было бы построить оптимальную байесовскую решающую функцию /в, для которой риск минимален: /g(j) — I : К ,t) к ..

Е Pj ЬЦ = min Е Pj LP,ú где p = 1,. ,K,j = í,...,M.

В прикладных задачах распознавания вектор в обычно неизвестен. Решающая функция выбирается из Ф с помощью некоторого заданного метода ¡л на основе случайной выборки наблюдений над X и У (обучающей (О

выборки). Пусть п '- число наблюдений г-го образа, соответствующих j-й ячейке; = N. Обозначим вектор частот через s ~ (si,..., sj, . , sm),

где Sj = ... Оценкой эмпирического риска для решающей

функции / называют величину Rf(s) = -ttE-^/OV/1^"

N gj

Метод минимизации эмпирического риска состоит в следующем, поставить в соответствие j'-й ячейке такой номер образа г, что Е = min

i J ' Р

1

Пусть S - случайный вектор частот Этот вектор подчиняется полиномиальному распределению. Рассмотрим семейство полиномиальных моделей распределения вектора частот с множеством параметров Л = {6} Это семейство (класс распределений) будем также называть множеством стратегий

природы. Под сложностью класса понимается величина М. Используем байесовский подход: предположим, что на Л определена случайная величина 0 = ■ ■ ■ >РмЬ с некоторым известным априорным распределением

piß) при в € Л. В этом случае риск является функцией Rf(Q), зависящей от случайного вектора параметров модели.

Будем полагать, что параметр О подчиняется распределению Дирихле: р(в) = \ ГКр^)^ \ гДе > 0 - некоторые заданные вещественные Z г,3

числа, выражающие априорные знания о распределении в, i — 1,..., К, j = 1,... М, Z - нормализующая константа. Обозначим d = . ■ ■, d^'}.

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

При d^ = 1 получим случай равномерного априорного распределения, использование которого оправдано при наличии априорной неопределенности относительно стратегии природы. Выбор распределения Дирихле объясняется тем, что оно удобно для выражения априорных знаний о распределении на

jW

множестве стратегии природы величины а^ задают априорные предпочтения на множестве ячеек и аналогичны числу попаданий в ячейки наблюдений различных образов Это распределение сопряжено с рассматриваемым полиномиальным распределением вектора частот. Кроме того, оно дает возможность задать неравномерное распределение на множестве стратегий природы, зависящее от степени «пересечения» между образами.

В параграфе 2.2.2 предлагается способ такого задания. На практике, в задачах распознавания всегда можно предполагать, что переменные, описывающие наблюдаемые объекты, задаются не случайно, но обладают некоторой информативностью. Поэтому позволительно считать, что вероятность ошибки оптимального байесовского решающего правила не слишком велика (например, не более 0.1 - 0 15). Оценка этой вероятности выражает мнение эксперта о степени «пересечения» между образами. Задание параметров распределения Дирихле позволяет учитывать такую априорную информацию. Для простоты, рассматривается случай двух образов и индикаторной функции потерь

Пусть все параметры Дирихле совпадают и равны некоторой величине d. Таким образом, считаем, что не имеется априорной информации о предпочтении одних ячеек перед другими, при этом априорное распределение на множестве стратегий природы не обязательно равномерное (d ф 1). Найдем ожидаемую вероятность ошибки ЕPjB(ß), где усреднение проводится по всем

случайным векторам 0 с плотностью распределения р(в) — ГКр?)^1-

z г,3

Утверждение 1. Пусть К = 2, d^ = d, (г = 1,2, j = 1,..., М), где d > 0 -некоторый параметр. Тогда при сформулированных выше предположениях

выполняется ЕP/B(Q) = h,b{d+ 1 ,d), где Ix{p,q) - бета функция распределения с параметрами х, р, q.

EPfB(&)

Рис. 1. Зависимость между параметром д. и ожидаемой вероятностью ошибки байесовской решающей функции

На рис 1 показан график зависимости ЕРув(9) от величины ¿. Параметр с? может служить для задания неравномерного априорного распределения на классе стратегий природы Л: при уменьшении этого параметра плотность априорного распределения меняется так, что образы в среднем более разделены. Например, если предположить, что ожидаемая по стратегиям вероятность ошибки байесовской решающей функции не превосходит 0.15, то параметр й не должен превышать значения 0.38.

В параграфе 2.3 проводится исследование байесовской модели распознавания конечного множества событий для произвольного метода обучения [20, 23, 26, 30]. Заметим, что в методе обучения при принятии решения может учитываться не только эмпирическая ошибка. Например, если есть экспертные знания о предпочтении какого-либо образа, решение может приниматься в его пользу несмотря на увеличение ошибки.

В разделе 2.3.1 найдено математическое ожидание функции риска, где усреднение проводится по всевозможным значениям параметров из множества Л и всевозможным обучающим выборкам заданного объема И: Утверждение 2. Пусть / = - решающая функция, полученная по выборке в с помощью некоторого детерминированного метода /л, такого, что решение для ячейки принимается по набору частот, у = 1,..., М. Тогда математическое ожидание ЕЛ^^©) функции риска равно

т(Р)т А_1_у. г(гч + р-

1=1

хП Пф + п^ЬюМ?*»?)'

I 5=1

где В — й-, = = N — > оператор означает,

ы у У и 0 ,

что суммирование ведется по всем наборам .. ,птаким, что

Е/п'0 < лг.

Назовем функцию = М, К, <3) ожидаемым риском для метода ¡л

в зависимости от объема обучающей выборки N, сложности класса М, числа образов /Г и вектора параметров <1.

Следствие 1. Оптимальным методом, который минимизирует ожидаемый риск, будет являться следующий метод' поставить в соответствие ¿-Я. ячейке такой номер образа г, что

£ Ь^ + п?) = £ + п«), з = 1,..., М

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

В параграфе приводятся выражения для ожидаемого риска, а также условия оптимальности метода при различных предположениях о функции потерь и априорном распределении. Так, в случае, когда функция потерь является индикаторной функцией, а априорное распределение является равномерным, доказывается, что оптимальным методом, который минимизирует ожидаемую вероятность ошибки классификации будет метод минимизации эмпирической ошибки Обозначим данный метод через ц* ■ Этот метод является оптимальным и в случае, когда все параметры Дирихле совпадают между собой Известно также, что метод теоретически обосновывается исходя из оценки риска, полученной методом максимального правдоподобия.

Далее в разделе 2.3.2 в рамках байесовской модели рассматривается зависимость ожидаемой вероятности ошибки от сложности класса решающих функций при К = 2. Пусть сформирована последовательность классов возрастающей сложности М = 1,2,..., Мщах■ При увеличении сложности класса естественно предположить, что ожидаемая вероятность ошибки ЕРув(В) оптимальной байесовской решающей функции (выражающая степень пересечения образов) также будет меняться. При М = 1 эта величина максимальна, поскольку в этом случае оптимальное байесовское решение основано лишь на априорных вероятностях, а при дальнейшем увеличении М величина

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

При этом при малых значениях М усложнение модели (переход от М к М + 1) должно вызывать заметное уменьшение ЕР/В(6), а при больших значениях М эффект такого же усложнения менее выражен. Для каждого М обозначим ожидаемую оптимальную вероятность ошибки через ЕРв(М), соответствующее значение параметра Дирихле через ¿м Выбор конкретных значений «¿1, <¿2, - ■ ,<^мтах (или соответствующих величин ЕРв{ 1), ЕРв(2), ..., ЕРв(Мтах)) должен проводиться на основе экспертных знаний.

Можно предложить, например, следующий способ. Задается модель зависимости ЕРв{М) от М (степенная или экспоненциальная), а также крайние значения ЕРв{ 1), ЕРв{Мтах). Затем в соответствии с утверждением 1 находятся значения с1\, ¿2, ■.., <1мтлх- Наконец, с использованием утверждения 2 вычисляется набор ожидаемых вероятностей ошибки исследуемого метода ¡л для различных значений М.

V

0,43 0,41 0,39 0,37 0,35 0,33 0,31 0,29

0,27 ; ;

0,25 4-—1-1—I—!—1-.-1---1-.-1-1-1-1-1-1-1-1-1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 М

Рис 2 Ожидаемая вероятность ошибки в зависимости от сложности класса при разных объемах обучающей выборки N. Модель ЕРВ(М) = (ЕРВ{1) - ЕРв(Мтах))е-°-75(-'1'-1) + ЕРв(Мпшх), М = 2,3, .., М^г - 1, Мтах = 20, ЕРВ(1) =0 4, ЕРв{Мггш:г) = 0 25

Приведен пример (рис. 2), из которого видно, что между крайними значениями М существует оптимальное значение, зависящее от объема выборки, для которого ожидаемая вероятность ошибки минимальна.

Дисперсия функции риска, наряду с ее ожидаемым значением, является важным показателем, характеризующим качество метода построения решающей функции. Так, при сравнении различных методов, метод с меньшей дисперсией может считаться лучшим (при прочих равных условиях) Утверждение 6. Пусть выполняются условия, сформулированные в утверждении 2. Тогда дисперсия функции риска для метода ц равна

УагН^ ^(Эх+д!- (ЯцУ, где Г(Р)Ю. 1 1

Г( N + п 4-Ъ)

Г(ЛТ + £> + 2) ^ ^ Г(Д - й3 - П{Г(4'))Г(Й<1'')}

I

Я,г

о V 1 1

Г(ЛГ + О + 2) Г(£> - Пг(^)}

I 3

ПГ(4г)+гг(;)) „у г 3 3 Т{п3+р-й3)

4- гг„С)! п.,!

д,г-

П П7' • V

I

х (¿<«>+п<«> )(4г>+ПМ)+х;^)2^+п^ )(49)++1)

где п^ = N — — оператор означает, что суммирование

II

ведется по всем наборам = (п^,..., п^), st = (т^,..., гс^) таким,

что £><г) + £пг(г) ^ ЛГ-г ^ I

Найденные выражения для математического ожидания и дисперсии функции риска можно использовать для нахождения толерантного интервала для случайного риска. В большинстве приложений важно знать лишь верхнюю границу интервала, поэтому рассмотрим неравенство € [0,е]) >

г], где е имеет смысл допустимой верхней границы риска, а 77 - показатель надежности. Для нахождения оценок можно воспользоваться различными обобщениями неравенств Чебышевского типа.

Так, из неравенства Кантелли (это неравенство используется для нахождения верхних границ у неотрицательных случайных величин) следует, что е ~ Яц + ^УагЛцу/г}/(1 — г}), где величина г) должна быть выбрана такой, чтобы выполнялось условие УагД^/(УагД,, + (Д/г)2) < 77 < 1.

В параграфе 2.4 исследуется байесовская модель для метода минимизации эмпирической ошибки, двух образов и равномерного априорного распре-

деления на множестве стратегий природы [12, 17, 18, 16]. С помощью комбинаторных преобразований можно получить более простое выражение для математического ожидания и дисперсии из утверждений 2, 6 для рассматриваемого метода [18]:

Утверждение 7. Пусть К = 2, ¿^ = 1 (I = 1,2, з = 1,2,..., М). Тогда ожидаемая вероятность неправильного распознавания для метода минимизации эмпирической ошибки /¿* равна

о 8М2 + ЪМЫ + ЛГ2 — 4М — N

= + 2М — 1){И + 2М) * ^ М>'

где ОДМ) = = £

,,. Го, если к четно г. , ,

7(/с) = < ' , Кроме того, справедлива следующая оцен-

' [1, если к нечетно. е г ^

ка:

м < < М(2М-1)(ЛГ+1)

4(ЛГ+2М-1)(ЛГ+2М) — Ь 4(Л^2М-1)(Я+2М)(2ЛГ+2М-1)'

Отсюда можно найти асимптотически точные выражения для верхней

и нижней оценки ожидаемой вероятности ошибки. При больших М или ./V

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

т, 8М2 + 5МЛГ + ./V2 - 5М - ТУ Р,.(ДГ,М) « М) =-4(Дг + 2М_1)(2)-•

Кроме того, выполняются следующие свойства:

М)->0,25 при N-+00; РД.(ЛГ, М)->0,5 при М -> оо Рассмотрим уклонение ожидаемой вероятности ошибки для метода минимизации эмпирического риска от минимального уровня ¿(6, <?) = Р^»(5)(0) — Рв(©). Обозначим ожидаемое уклонение через = Е£(в,5) = Рм> — ЕРд. Данная величина показывает, насколько имеющийся объем обучающей выборки позволяет приблизиться к «идеальному» качеству распознавания. Утверждение 8. Пусть выполняются условия утверждения 7. Тогда для метода минимизации эмпирического риска справедливо

Г /Д. М{И + 4М — 3) ,.ЛГ

М) = 4(* + Ш-1)(ЛГ + Ш) - ^

где -ф{Ы,М) = 0(Ы,М) - А^+2м-1)(ы+2М)' пРтем - неотрица-

тельная бесконечно малая относительно каждого аргумента функция.

Из утверждения 8 очевидно, что при любом фиксированном М величина ¿^(ЛГ, М) -> 0 при N —> ос.

Следствие 6. Пусть е € (0; 0,25) - заданная величина. Тогда если сложность М класса решающих функций меньше, чем

_ ЩИ + 3 - N - 8е + ^/(N - З)2 + 16е(2]У2 + Ш - 3) + 64е2 ~ 8(1-4е)

или если число наблюдений в обучающей выборке больше, чем

„ _ М + 4е - 16еМ + УМ2 + 16е2 + 32еМ2 - 40еМ

8е

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

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

Далее рассматривается дисперсия случайной величины вероятности ошибки для метода минимизации эмпирической ошибки. Обозначим (5) =

Е ЩР1^ - к)1, /?) = £ ^(ЛГ - к)1у(Я ~ к), где ¡,N,0- некото-к=О А-О

рые натуральные числа. Доказывается, что справедливы рекуррентные соотношения: ОД/?) = Ж?,^,/?) - С^Н - 1,0 + 1); = £>;(ЛГ,/?) = ЛГА-!(#■,/?) — 1?(-х(N — 1,/3 + 1), а также справедлива оценка

+1).

Утверждение 9. Пусть выполняются условия утверждения 7. Тогда дисперсия величины Р^. (5) (О) равна УагР^- = VI + Уг — (Р^*)2; г<^е

И = + 1а,(fi.fi) - SDiiN.fi)) + |л'(С2 (ЛГ./З)-

= + 2ОС74(ЛГ,/?0 + 150С3(М,<3') + 520С2(^,/?')+

+ 824^1(^/3') + С?0(АГ,/?') - 1501(^)3') - бОА^/ЗО},

, _ М(2М—1)17У! у _ Л л// _ М(М-\){2М-\)т „ _ „

л ~ (2ЛГ-3)!(ЛГ+2М)" л ~ ДЧ-2М+1' л — (2М-5)!(ЛЧ-2М+1)" ^ ~

0' = 2М- 5.

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

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

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

Согласно байесовской методологии, функция риска Д/(Э) при фиксированной выборке является случайной функцией, зависящей от случайного вектора ©.

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

функции / равно ЩЩ(е)\з) = —ЕЕ^)^"?' + ^

Назовем величину Е(Ду(0)|з) байесовской оценкой риска, соответствующей решающей функции /. Обозначим эту величину как Д/,в. Как известно из теории оценивания, апостериорное математическое ожидание является оптимальной байесовской оценкой, минимизирующей байесовский риск при квадратичной функции потерь. В работе приводятся выражения для байесовских оценок риска для решающей функции, а также условия ее оптимальности при предположениях о том, что функция потерь является индикаторной и/или априорное распределение является равномерным. Утверждение 15. Пусть априорное распределение на множестве стратегий природы является равномерным, функция потерь - индикаторной. Выберем из множества Ф произвольную решающую функцию / и определим по заданной выборке в € 5 число п неправильно распознанных объектов. Тогда характеристическая функция случайной величины вероятности

00 0,1 А

ошибки равна <р(Ь) = Н(п + (К-1)М,М + КМ-,И), гдеН(а,с;у) = £ ——

- гипергеометрическая функция Куммера, 1 - мнимая единица.

Отсюда следует, что 1-й абсолютный момент оценки вероятности ошибки

/ /, . <р®(0) {п + (К-1)М)а) для решающей функции / равен Е(Р}(&)\з) = —^ = —+ '

где - 1-я производная I = 1,2, ■ ■ ■.

Следствие 9. Байесовская оценка вероятности ошибочной классификации для равномерного априорного распределения, индикаторной функции потерь равна

= п + (К — 1)М Лв N + КМ '

Рассмотрим апостериорную дисперсию функции риска. Утверждение 16. Пусть / - произвольная решающая функция, выбранная из множества решающих функций Ф, и задана выборка з € 5. Тогда апостериорная дисперсия функции риска равна

УагЛ/1в =---иЬЬ),^? + п?) -

з,ч

(Д/,*)2

N + 0 + 1'

Для нахождения толерантного интервала для риека можно воспользоваться неравенством Кантелли.

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

где фа,с&) = н(а, а = п + (К - 1 )М, с = N + КМ, Ь* - граница Чернова. Приближенное значение вычисляется численным путем. Приведены примеры, из которых видно, что использование метода Чернова дает более точные результаты

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

где рМ - заданная априорная вероятность г-го образа, г = 1,..., К, причем £гр(г) = 1. Обозначим множество всех векторов в, удовлетворяющих данным ограничениям, через Лр.

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

Будем полагать, что случайная величина © подчиняется распределению

Дирихле- р(в) = ГКр/л')^'-7 ~~ гДе > ® ~ некоторые заданные вещественные числа, I = 1,..., К, у = 1,... М, Zv - нормализующая константа. Утверждение 18. Пусть / - произвольная решающая функция, выбранная из множества решающих функций Ф, и задана выборка я £ 5. Тогда апостериорное математическое ожидание функции риска для решающей функции / при условии заданных априорных вероятностей р = {р^,... равно величине

е = -(]п фа,с(П-Ч1-г1)Ъ

1

з,я

где — Х^п^ - число наблюдений q-гo образа.

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

Следствие 12. Байесовская оценка вероятности ошибочной классификации для равномерного априорного распределения, известных априорных вероятностей образов равна

"/«-ХУ" Хм ■ (4)

где ММ

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

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

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

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

Найденная байесовская оценка риска (2), как и любая другая оценка, является лишь приближенным показателем качества решающей функции. Поэтому возникает вопрос, насколько точна данная оценка, каковы ее статистические свойства и т.д. В разделе 2.5.2 полагается, что в - фиксированный, но неизвестный вектор, а выборка 5 является случайной. Пусть задана некоторая решающая функция /. В этом случае байесовская оценка риска является приближением к неизвестному (также фиксированному) риску. В разделе рассмотрено смещение байесовской оценки Е^Д^ — Н/(в) и найдены выражения для смещения и дисперсии байесовской оценки риска.

Байесовские оценки качества могут использоваться на этапе обучения как критерий оптимальности логической решающей функции. В параграфе 2.6 описывается применение полученных результатов для построения решающих деревьев [19, 28]. Оценки оптимальной сложности класса могут применяться при этом для задания ограничений на максимальное число листьев. Рассмотрим задачу нахождения оптимального дерева в задаче распознавания. Можно предложить два способа применения байесовской модели.

1. Образуем исходное разбиение пространства переменных на некоторое достаточно большое число подобластей. Каждая область является декарто-

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

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

Рассмотрим уклонение ¿/(в, 5) = Н/^ — -Й/(В) между оценкой и действительным риском для решающего дерева / (как стратегия природы, так и выборка случайны). Для любого е > 0 справедливо Р(| ¿/(в, 5")| > е) < Е Й(в,5)

——7,-, причем правая часть неравенства сходится к нулю при увеличении

6

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

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

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

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

В параграфе 3.1 описывается рекурсивный алгоритм («Э^-метод») построения дерева решений в задачах распознавания образов и регрессионного анализа [2, 3].

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

Таким образом, возникает необходимость в разработке метода, который позволял бы решать задачи, характеризующиеся следующими особенностями:

- многомодальность совместного распределения величин X, У;

- сложная нелинейная зависимость между X и У .

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

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

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

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

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

Критерий качества дерева записывается в следующем виде: Q = n/N + PM/N (для задачи распознавания образов) или Q — voc/vq + /ЗМ/N (для задачи регрессионного анализа), где /? - некоторый заданный параметр, М -число листьев дерева, п - ошибка на обучении, voc и vo - остаточная и исходная дисперсии соответственно. Регуляризующий параметр /3 в критерии качества подбирается экспериментально. На основе результатов, полученных в параграфе 2.5, рекомендуется при достаточно большом объеме выборки в случае задачи распознавания задавать этот параметр равным К — 1 (где К -число образов). Результаты решения большого числа прикладных и тестовых задач свидетельствуют о правильности этой рекомендации. Если предположить, что на множестве стратегий природы задано неравномерное априорное распределение, обеспечивающее с помощью параметра dм ожидаемую вероятность ошибки байесовского решающего правила (см. раздел 2.3.2, стр. 27), то параметр ¡3 рекомендуется задавать равным величине йм-

В параграфе описываются результаты статистического моделирования для исследования ОЯ-метода и сравнения его с некоторыми другими методами: использующими линейные дискриминантные функции, квадратичные дис-криминантные функции, основанными на непараметрических оценках плотности, и алгоритмами, использующими деревья решений (DW, ЛРП, GLRP, See5, CART)

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

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

Описан и исследован на тестовых задачах алгоритм построения леса решений на основе iH-метода.

В параграфе 3.2 описан алгоритм построения дерева решений на основе iH-метода для задачи группировки объектов [24]. С помощью рекурсивного алгоритма ищется дерево разбиения пространства переменных, оптимальное с точки зрения критерия качества группировки. Под критерием качества понимается величина Q — q + I3K, где q - суммарный относительный объем таксонов, /3 > 0 - некоторый заданный параметр, К - число групп, совпадающее с числом листьев дерева. При минимизации этого критерия, с одной

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

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

В параграфе 3.3 рассматривается задача анализа многомерных разнотипных временных рядов с использованием деревьев решений [5]

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

В параграфе 3.4 предлагается метод прогнозирования экстремальных событий с помощью построения дерева событий на основе анализа многомерного разнотипного временного ряда [29].

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

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

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

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

В параграфе 4.1 описывается комплекс программ ЛАСТАН-М для по-

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

В параграфе 4 2 описано применение разработанного комплекса программ в задаче анализа спектров мутаций в ДНК [6, 9,11]. Приведены некоторые из полученных результатов. Проблема анализа мутационных спектров является весьма актуальной в биоинформатике из-за важности выяснения механизмов мутагенеза и большого количества мутационных спектров, накопленных к настоящему времени. Лишь для некоторых из спектров имеется информация о закономерностях контекстного окружения горячих точек мутаций. Использование результатов диссертационной работы позволило провести детальный анализ этих спектров и найти контекстные закономерности.

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

В параграфе 4.4 приводятся результаты решения задачи прогнозирования экстремальных гидрологических ситуаций [27]. Разработанный алгоритм построения дерева событий был использован для прогнозирования экстремальных событий (маловодий) на реке Обь (г. Барнаул, Колпашево) по наблюдениям за 1922 - 2000 гг. В качестве исходных данных для прогнозирования использовались среднемесячные данные по температуре, осадкам, расходу воды. Были обнаружены закономерности, характерные для возникновения маловодий.

В параграфе 4.5 описывается применение разработанных методов для решения задачи анализа гелиогеофизических факторов среды при пренаталь-ном развитии в вероятностной модели прогноза здоровья человека [7]. Были выявлены закономерности между показателями солнечной активности, напряженности магнитного поля Земли на различных сроках пренатального развития и уровнями риска патологических синдромов на момент исследования

Кроме того, разработанные методы были использованы для анализа вли-

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

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

Приложение содержит документы о внедрении результатов диссертации

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Lbov G S., Berikov V.B. Recursive Method of Formation of the Recognition Decision Rule in the Class of Logical Functions // Pattern Recognition and Image Analysis, Vol. 3, N 4,1993. P. 428-431. [Рекурсивный метод построения решающего правила распознавания в классе логических решающих функций]

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

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

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

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

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

10. 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. [Подход к оцениванию качества дискретного классификатора]

11. Malyarchuk В , Rogozin I, Berikov V.B., Derenko M Analysis of phylogene-tically reconstructed mutational spectra in human mitochondrial DNA control region // Human Genetics, N 111, 2002. P. 46-53. [ Анализ филогенетически реконструированного спектра мутаций в управляющем участке ми-тохондриальной ДНК человека]

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

13. Бериков В.Б. Методика статистического исследования для анализа психофизиологических резервов организма человека // Вестник МНИИКА, №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. V. В Berikov, G. S. Lbov, and A. G Litvinenko. Discrete Recognition Problem with a Randomized Decision Function // Pattern Recognition and Image Analysis, Vol. 14, Ж 2, 2004, P. 211-221. [Дискретная проблема распознавания с рандомизированной решающей функцией]

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

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

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

21. Berikov V. Recognition on Finite Set of Events Bayesian Analysis of Generalization Ability and Classification Tree Pruning // Int. J. Information Theories & Applications. V.13, N.3, 2005. P. 285-290. [Распознавание на конечном множестве событий, байесовский анализ обобщающей способности и усечение дерева классификации]

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

23 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. [Байесовские оценки качества распознавания на конечном множестве событий]

24. Бериков В.Б , Вишневская Е.А , Лбов Г.С. Статистическое моделирование для исследования одного метода автоматической группировки // Сб. научных статей V Международной конференции «Компьютерный анализ данных и моделирование», Часть З'А-К. Минск, 1998. С. 54-59.

25. Деревянко Е. И., Лбов Г. С., Рыбина Е.А., Бериков В.Б. Компьютерная система анализа погребальных памятников эпохи неолита и ранней бронзы // В кн.: Интеграционные программы фундаментальных исследований СО РАН. Новосибирск, Издательство СО РАН, 1998. С. 135-143.

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

27. Лбов Г. С , Бериков В.В., Герасимов М.К. Прогнозирование экстремальных гидрологических ситуаций на основе анализа многомерных временных рядов // Труды Международной научной конференции «Экстремальные гидрологические события' теория, моделирование, прогнозирование». Москва, 2003. С. 26-30.

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

29. Бериков В.Б. Построение дерева причин на основе анализа многомерного временного ряда // Вычислительные технологии. Том 9. Вестник КазНУ им. аль-Фараби. Серия математика, механика, информатика. №3 (42) (совм. вып. по материалам Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании»). Алмата, 2004. С. 305-310.

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

Подписано в печать 02.03 2007 Формат 60 х 84/16 Объем 2 п.л.

Тираж 100 экз. Заказ № '¿,3 / Отпечатано с оригинал-макета в типографии НГТУ 630092, г. Новосибирск, пр. К.Маркса, 20.

Введение

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

Заключение

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.