Введение к работе
Актуальность темы. В настоящее время при автоматизации процессов обработки информации в различных трудноформализуемых областях исследований (генетике, археологии, медицине и т д.) возникает проблема решения задач анализа данных (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 фундаментальных исследований Президиума РАН.
Цели и задачи работы. Разработка теории и методов решения задач распознавания с использованием класса ЛРФ и позволяющих при выборе оптимальной сложности класса учитывать эмпирические данные и экспертные знания. Разработка методов анализа разнотипных данных (распознавания образов, регрессионного анализа, кластер-анализа, анализа разнотипных временных рядов) в классе ЛРФ. Методы должны позволять решать задачи, характеризующиеся сложными многомодальными распределениями. Цель достигается путем решения следующих задач.
Нахождение модели, позволяющей как можно более полно учесть особенности класса ЛРФ и удобной для теоретического исследования.
Разработка способов формализации экспертных знаний о задаче распознавания.
Получение, с учетом экспертных знаний и специфики метода обучения, зависимостей между оценками риска и объемом обучающей выборки, сложностью класса ЛРФ.
Теоретическое исследование полученных оценок; нахождение оптимальной сложности класса, минимизирующей оценку риска.
Разработка и исследование методов построения ЛРФ в задаче распознавания, основанных на полученных оценках риска.
Создание эффективных методов и алгоритмов анализа данных в классе ЛРФ.
Создание программного обеспечения, реализующего разработанные алгоритмы, применение его для решения прикладных задач в различных областях исследований.
Научная новизна. В диссертационной работе получены следующие новые результаты, которые выносятся на защиту.
Предложен подход к разработке и исследованию методов построения ЛРФ, в основе которого лежит идея применения байесовской модели распознавания конечного множества событий.
Введен новый вид этой модели, позволяющий учитывать экспертные знания о классе распределений (знания, выраженные в априорных предпочтениях на множестве событий, оценках априорных вероятностей образов) и классе решающих функций (знания, отраженные в специфике метода обучения).
В рамках байесовской модели предложен способ формализации экспертных знаний о задаче распознавания, выражающий ожидаемую степень «пересечения» образов.
Найдены и исследованы зависимости между точечными и интервальными оценками риска и объемом обучающей выборки, сложностью класса решающих функций в байесовской модели, которые позволяют находить оптимальную сложность класса.
Предложены критерии качества логических решающих функций, основанные на полученных оценках.
Разработан рекурсивный метод («!ЕЯ-метод») построения дерева решений, позволяющий решать следующие виды задач анализа разнотипных данных, распознавание образов, регрессионный анализ, кластер-анализ, анализ многомерных временных рядов. На основе ЭЯ-метода разработан алгоритм построения леса решений в задачах распознавания и регрессионного анализа.
Разработан метод прогнозирования экстремальных событий с использованием класса ЛРФ.
Разработан комплекс программ, реализующих предложенные методы и алгоритмы анализа, с помощью которого решен ряд актуальных прикладных задач.
Методы исследования. В работе использованы методы теории распознавания образов, теории вероятностей, математической статистики, комбинаторного анализа, теории статистических решений, статистическое моделирование, экспериментальные исследования на тестовых и прикладных задачах.
Практическая значимость. Разработанные методы, алгоритмы и программное обеспечение дают возможность решать широкий круг задач анализа разнотипных данных (распознавания образов, регрессионного анализа, кластер-анализа, анализа временных рядов, прогнозирования экстремальных событий) в различных прикладных областях исследований Результаты работы использовались в таких областях, как-
генетика (в Институте цитологии и генетики СО РАН для анализа спектров мутаций ДНК);
археология (в Краеведческом музее г. Новосибирска для классификации древних наконечников стрел; Институте археологии и этнографии СО РАН для анализа антропологических находок эпохи неолита и анализа данных о
средневековых вооружениях);
медицина (в Международном научно-исследовательском институте космической антропоэкологии для анализа влияния факторов среды на показатели здоровья в экстремальных условиях; НИИ терапии СО РАМН для поиска маркеров атеросклероза);
гидрология (в Новосибирском филиале Института водных и экологических проблем СО РАН для прогнозирования экстремальных гидрологических ситуаций)
Программная система ЛАСТАН-М, реализующая основные разработанные методы и алгоритмы, доступна через официальный сайт Института математики СО РАН ( nscru/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
