Введение к работе
Актуальность темы. В современной информатике особое место занимает область, известная как распознавание или классификация наблюдений. В последние три десятилетия методы построения решающих функций распознавания с успехом применяются в научных исследованиях и внедряются в такие трудно формализуемые области, как экология, медицина, социология и др.
За 30-40 лет интенсивного развития теории распознавания было создано достаточно большое количество методов построения решающих функций распознавания (классификации), основанных на различных идеях, гипотезах и принципах, что затрудняет выбор метода для решения конкретной задачи. Возникает необходимость в теоретическом исследовании свойств методов распознавания с точки зрения их качества. Известно, что ограниченность объема выборки является существенным фактором, влияющим на качество распознавания (классификации).
Из теоретических исследований ряда авторов, в том числе автора данной работы, следует, что при ограниченном объеме выборки чем более сложные функции используются для построения решений, чем больше число используемых характеристик (признаков), тем выше вероятность получения "плохого" решения, сильно отличающегося от оптимального (байесовского решения).
Например, может оказаться, что квадратичная решающая
функция будет хуже, чем линейная функция, либо линейная функция, заданная на всем исходном множестве характеристик будет хуже линейной функции, заданной на некотором их подмножестве. На практике часто наблюдается, что добавление новых характеристик ухудшает, а не улучшает качество классификации. Поэтому, при исследовании методов классификации необходимо учитывать сложность решающих функций, объем выборки и сложность распределений (в частности, размерность пространства).
Вопрос о выборе сложности решающей функции при фиксированной сложности распределений (в частности, размерности пространства) в условиях ограниченной выборки для достижения заданного качества классификации и составляет весьма важную проблему статистической устойчивости решающих функций классификации относительно объема выборки.
Проблема статистической устойчивости является одной из важных и сложных в общей проблеме построения решающих функций классификации. Наиболее существенный вклад в решение указанной проблемы внесли работы Вапника В.Н., Чер-воненкиса А.Я. и Раудиса Ш. Однако в работах Раудиса Ш. исследования проводятся при сильных ограничениях на вид распределения (для нормальных распределений). В работе Вапника В.Н. и Червоненкиса А.Я. рассматривается случай произвольных распределений, но предложенный в работе подход к решению данной проблемы направлен на самый сложный вид
распределений. В результате оказалось, что объемы выборки для достижения заданного качества классификации значительно превышают объемы выборки в реальных задачах.
В связи с этим возникает необходимость решения проблемы статистической устойчивости решающих функций классификации в случае произвольных распределений для объемов выборки, существующих в практических задачах. Решение данной проблемы сводится к разработке подхода к исследованию алгоритмов классификации на статистическую устойчивость, который заключается в поиске объемов выборки, достаточных для достижения заданного качества классификации при фиксированной сложности распределений (в частности, размерности пространства). Для этого необходимо получить функциональные зависимости между качеством классификации и сложностью распределений при фиксированных значениях объема выборки.
Основная цель работы. Предложить подход к решению проблемы статистической устойчивости решающих функций классификации, который позволит исследовать существующие методы и разработать новые эффективные методы классификации (распознавания). Получить функциональные зависимости между качеством классификации, сложностью распределений (в частности, размерностью пространства п) и объемом выборки JV; исследовать поведение качества классификации как функции от параметров п и Лг. С помощью имитационного модели-
рования провести апробацию предложенного подхода и разработать новые эффективные алгоритмы в классе логических решающих функций.
Научная новизна исследования. В работе впервые получены функциональные зависимости между качеством классификации (распознавания), сложностью распределений и объемом выборки с учетом и без учета априорной информации о байесовском уровне ошибки в дискретном пространстве характеристик. Зависимости получены для произвольных распределений и для случая независимых характеристик.
Получена оптимальная (с точки зрения минимума функции средних потерь) решающая функция классификации для ограниченных объемов выборки при фиксированной сложности распределений и фиксированном байесовском уровне ошибки в дискретном пространстве характеристик.
Предложен новый подход к исследованию статистической устойчивости решающих функций классификации по отношению к объему выборки, основанный на упорядочивании распределений по сложности и использующий полученные функциональные зависимости. Дано теоретическое обоснование данного подхода. При произвольном распределении для выбора решающей функции минимальной сложности, дающей решение близкое к оптимальному, предложено использовать класс логических решающих функций. Введено понятие универсальности класса функций. Универсальность класса функций позволяет переходить от очень простых ко все более сложным решаю-
гцим функциям и тем самым подбирать функцию подходящей сложности, дающей решение близкое к оптимальному, для любого распределения. Доказано, что класс логических решающих функций является универсальным.
Предложенный подход к исследованию решающих функций классификации на статистическую устойчивость апробирован на классе логических решающих функций. Данный подход явился основой для разработки новых эффективных методов классификации и регрессионного анализа в классе логических решающих функций. Впервые разработан алгоритм многоклассового распознавания для разнотипных переменных (качественных и количественных) в классе логических решающих функций. Также впервые разработаны алгоритмы многооткликовой регрессии для разнотипных переменных и алгоритм регрессионного анализа для структурированных объектов.
На защиту выносятся.
1. Новый подход для исследования статистической устой
чивости решающих функций классификации к объему выборки,
который в отличие от существующих подходов направлен на
произвольный вид распределений и предназначен для работы
с объемами выборки, реально существующими в практических
задачах.
2. Полученные в рамках подхода функциональные зависимо
сти между качеством классификации, объемом выборки и слож
ностью распределений с учетом и без учета априорной инфор-
мации о байесовском уровне ошибки для произвольных распределений и для случая независимых характеристик.
3. Теоретическое обоснование данного подхода, основанное
на введении усредненных стратегий природы упорядоченной
сложности.
-
Разработку методов классификации и регрессионного анализа в классе логических решающих функций, объединенных в компьютерную систему LASTAN, в которой реализован предложенный подход к исследованию алгоритмов на статистическую устойчивость.
-
Результаты исследования поведения качества классификации в зависимости от изменения объема выборки и сложности распределения (в частности, размерности пространства).
-
Результаты апробации предложенного подхода для разработанных алгоритмов в классе логических функций с помощью имитаци'онного моделирования.
Методы исследования. В работе использованы методы теории вероятностей, математической статистики, теории распознавания образов.
Практическая значимость. В работе дан ответ на актуальный для практики вопрос: как проводить исследование решающих функций классификации на статистическую устойчивость относительно объема выборки для произвольных распределений. Полученные в работе функциональные зависимости между качеством классификации, объемом выборки и сложностью
распределений позволяют:
-
при фиксированном объеме выборки определять допустимую сложность распределений (в частности, размерность пространства) для достижения заданного качества классификации:
-
при фиксированной сложности распределений определять необходимый объем выборки для достижения заданного качества классификации;
-
при фиксированных объеме выборки и сложности распределений прогнозировать ожидаемое качество классификации.
Предложенный подход к исследованию алгоритмов на статистическую устойчивость позволил разработать ряд новых алгоритмов классификации и регрессионного анализа, вошедших в программную систему ЛАСТАН, а также позволил более эффективно использовать существующие алгоритмы для решения различных прикладных задач.
Разработанные алгоритмы использовались в Институте терапии СО РАМН (г. Новосибирск) для решения задач поиска маркеров атеросклероза и прогноза выживаемости больных, перенесших инфаркт миокарда; в лаборатории экологической информатики Института химии нефти СО РАН (г. Томск) для решения задач моделирования и прогнозирования состояния окружающей среды; в Институте цитологии и генетики СО РАН (г. Новосибирск) для анализа селекционных признаков злаковых культур; на ПО "Кировский завод" (г. Санкт-Петербург) для решения задач модернизации оборудования цеха выпус-
ка кабин тракторов; в Центральной клинической больнице СО АМН РАН (г. Новосибирск) для определения степени эффективности метода волевой ликвидации глубокого дыхания лечения больных сахарным диабетом; в Институте общей патологии и экологии человека СО РАМН (г. Новосибирск) для определения риска общепатологических синдромов; для исследования качества и надежности выпускаемых изделий (г. Уфа, г. Новосибирск); в Новосибирском медицинском институте для выявления железодефицитных состояний при массовых осмотрах населения", в НИИ Патологии Кровообращения МЗ РСФСР (г. Новосибирск) для определения степени влияния глубины эфирной анестезии при проведении анестезиологического обеспечения кардиохирургических операций на "сухом сердце" и для выделения факторов риска развития дыхательной недостаточности в послеоперационном периоде; для решения задач прикладного материаловедения (г. Москва); в Институте народного хозяйства (г. Алма-Ата) для решения задач из области капитального строительства; в Днепропетровском горном институте для прогнозирования геологи геофизических данных; в Институте химии АН МССР (г. Кишинев) для получения зависимости структурно биологической активности; в Каз ВИРГ (г. Алма-Ата) для решения задач интерпретации геофизических данных; в ИХФ АН СССР (пос. Черноголовка) для изучения активности и селективности платиноидных катализаторов; в НИИ онкологии Томского научного центра для диагностики злокачествен-
ных новообразований; в Ленинградском механическом институте при автоматизированном проектировании элементов технологических процессов обработки класса деталей-тел вращения и т.д. Модификация разработанной программной системы (система СПАРК) передана в Региональный Центр экстремальной медицинской помощи (г. Новосибирск) для анализа и прогнозирования чрезвычайных ситуаций.
Апробация работы. Основные положения работы докладывались и обсуждались на Всесоюзных конференциях "'Машинные методы обнаружения закономерностей" (Новосибирск, 1983 г.), "Математические методы распознавания образов" (2-я - Дили-жан, 1985 г., 5-я - Москва, 1991 г.), "Применение многомерного статистического анализа в экономике и оценке качества продукции" (3-я - Тарту, 1985 г.), "Методы и программное обеспечение обработки информации и прикладного статистического анализа на ЭВМ" (2-я - Минск, 1985 г.), "Условно-корректные задачи математической физики и анализа" (Новосибирск, 1992 г.); на Всесоюзных школах-семинарах "Программно-алгоритмическое обеспечение анализа данных в медико-биологических исследованиях" (Пущино, 1986 г.), "Статистические методы распознавания образов и компьютерной кластеризации" (Киев, 1989 г.), "Непараметрические и робастные методы статистики в кибернетике и информатике" (6-я - Томск, 1987 г., 7-я - Иркутск, 1991 г.), "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа" (4-я - Москва, 1991 г.); на
Всероссийских конференциях "Математические методы распознавания образов" (б-я - Москва, 1993 г., 7-я - Москва, 1995 г.), "Математические проблемы экологии" (1-я Новосибирск, 1992 г., 2-я Новосибирск, 1994 г., 3-я Новосибирск, 1996 г.); на республиканских, конференциях по эпидемиологии (Новосибирск, 1987 г.), "Математическое и программное обеспечение анализа данных" (Минск, 1990 г.), "Компьютерный анализ данных и моделирование" (Минск, 1992 г.); на Советско-финском симпозиуме по распознаванию образов (Тбилиси, 1987 г.); на Международных конференциях ''Компьютерный анализ данных и моделирование" (Минск, 1991 г.), "Математические методы интеллектуализации обработки информации" (Алушта, 1996 г.), "Распознавание образов и обработка информации" (Минск, 1997 г.); на 7-м международном симпозиуме по непараметрическим и робаст-ным .методам в кибернетике (Красноярск, 1995 г.); на 2-м Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 199G г.); на семинарах Института математики СО РАН. Института кибернетики и математики АН ЛитССР (1987 г., 1989 г., 1990 г.), кафедры теоретической кибернетики НГУ.
Публикации. По теме диссертации опубликовано 55 научных работ.
Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения, изложенных на 210 страницах машинописного текста, 28 рисунков, списка литературы
из 108 наименований и приложения.