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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ , . , А п ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

Ко О Л

? ^ НОЯ На правах рукописи

Старцева Наталья Геннадьевна

СТАТИСТИЧЕСКАЯ УСТОЙЧИВОСТЬ РЕШАЮЩИХ ФУНКЦИЙ В ЗАДАЧАХ КЛАССИФИКАЦИИ

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

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

Новосибирск 1997

Ново-

Официальные оппоненты: доктор физико-математических наук, профессор Ю. Н. Григорьев,

доктор физико-математических наук, прфессор Ю. А. Воронин

доктор технических наук, прфессор В. В. Губарев

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

У/ ***

Защита состоится 1997 г. в час. на заседании Специализиро-

ванного совета Д 002.10.02 при Вычислительном центре СО РАН по адресу: 630090, Новосибирск-90, проспект академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (пр.академика Лаврентьева, 6).

Автореферат разослан -1997 г.

Ученый секретарь Специализированного совета к.т.н.

Г. И. Забинякс

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

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

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

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

Например, может оказаться, что квадратичная решающая

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся.

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

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

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

3. Теоретическое обоснование данного подхода, основанное на введении усредненных стратегий природы упорядоченной сложности.

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

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

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

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

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

распределений позволяют:

1) при фиксированном объеме выборки определять допустимую сложность распределений (в частности, размерность пространства) для достижения заданного качества классификации:

2) при фиксированной сложности распределений определять необходимый объем выборки для достижения заданного качества классификации;

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

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

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

ка кабин тракторов; в Центральной клинической больнице СО АМН РАН (г. Новосибирск) для определения степени эффективности метода волевой ликвидации глубокого дыхания лечения больных сахарным диабетом; в Институте общей патологии и экологии человека СО РАМН (г. Новосибирск) для определения риска общепатологических синдромов; для исследования качества и надежности выпускаемых изделий (г. Уфа, г. Новосибирск); в Новосибирском медицинском институте для выявления железодефицитных состояний при массовых осмотрах населения; в НИИ Патологии Кровообращения МЗ РСФСР (г. Новосибирск) для определения степени влияния глубины эфирной анестезии при проведении анестезиологического обеспечения кардиохирургических операций на "сухом сердце" и для выделения факторов риска развития дыхательной недостаточности в послеоперационном периоде; для решения задач прикладного материаловедения (г. Москва); в Институте народного хозяйства (г. Алма-Ата) для решения задач из области капитального строительства; в Днепропетровском горном институте для прогнозирования геолого геофизических данных; в Институте химии АН МС'С'Р (г. Кишинев) для получения зависимости структурно биологической активности; в Каз ВИРГ (г. Алма-Ата) для решения задач интерпретации геофизических данных; в ИХФ АН СССР (пос. Черноголовка) для изучения активности и селективности платиноидных катализаторов; в НИИ онкологии Томского научного центра для диагностики злокачсствен-

ных новообразований; в Ленинградском механическом институте при автоматизированном проектировании элементов технологических процессов обработки класса деталей-тел вращения и т.д. Модификация разработанной программной системы (система СПАРК) передана в Региональный Центр экстремальной медицинской помощи (г. Новосибирск) для анализа и прогнозирования чрезвычайных ситуаций.

Апробация работы. Основные положения работы докладывались и обсуждались на Всесоюзных конференциях "'Машинные методы обнаружения закономерностей" (Новосибирск, 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-м Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996 г.); на семинарах Института математики СО РАН. Института кибернетики и математики АН ЛитССР (1987 г., 1989 г., 1990 г.), кафедры теоретической кибернетики НГУ.

Публикации. По теме диссертации опубликовано 55 научных работ.

Структура и объем работы. Диссертационная работа состоит из введения, шести глав, заключения, изложенных на 210 страницах машинописного текста, 28 рисунков, списка литературы

из 108 наименований и приложения.

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

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

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

Рассматривается статистическая постановка задачи классификации. Будем считать, что и> = 1, являются простыми выборками из п-мерных генеральных совокупностей соответственно с распределениями Для дискретного пространства £) характеристик (признаков) Х\,...,Х„ распределение описывается в параметрами р",..., р^; Р? — ^ определяющими вероятности возможных значений п - мерной случайной величины. Параметрические векторы Ри = (Рп---,^) не известны. Следует принять решение, к какому из распределений Р\,...,Рк относится выборка х — ..., хп) объема один, х £ И.

Пусть Б — П;=1 В,, О} - множество значений характеристики X,, = г,-, в = П"=1 гу

В дальнейшем элементы множества И (значения п - мерной случайной величины) будем обозначать через х1.

Пусть qul - априорная вероятность принадлежности х к распределению Р^.

Определение 1.1. Под стратегией природы с будем понимать следующий набор с = \qjpi '■ и! — 1 г = 1,...,«}, в — сложность

стратегии природы или сложность распределения Р^.

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

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

В задачах классификации Рш неизвестны. Для выбора стратегии статистика используется информация об этих распределениях, содержащаяся в выборках. Пусть N — ^'^Лц и к=2. При фиксированной выборке качество решающего правила /, т.е. потери при правиле /, построенном по выборке, определяются

вероятностью ошибочной классификации (функцией риска)

= £ £ ЧхР\,

х'е/У х'ео1

где ЕГ = {х'' : 7(х') = ал г = 1,..., а, }, И = Б1 и £>2.

Пусть Ф - некоторый класс решающих функций.

Определение 1.4. Алгоритмом построения решающей функции классификации (алгоритмом распознавания) будем называть некоторое отображение (}, которое каждой выборке ставит в соот-

ветствие решающее правило / 6 Ф, т.е. <3(2а>) — /•

Обобщенно, под стратегией статистика будем понимать алгоритм распознавания (}. Качество алгоритма Ц при фиксированных стратегии природы с и объеме выборки N будем определять математическим ожиданием вероятности ошибки

Е2„Р(о1с,7,м) = р{0/с,7,гк)р(гк/с),

к,}

где Р(^д,/с) - условная вероятность появления выборки Математическое ожидание ЕгкР{о)с,/, .У) — есть средние потери при стратегии статистика ф и стратегии природы с при фиксированном объеме выборки Лг.

Во второй главе получены функциональные зависимости между качеством классификации (средними потерями), объемом выборки N и сложностью распределений в в дискретном пространстве характеристик. Зависимости получены для произвольных распределений и для случая независимых характеристик. Исследовано поведение качества классификации в зависимости от объема выборки Л', размерности пространства п и числа значений характеристики Л";.

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

При фиксированной априорной вероятности <71 = 1 — Ч\) вектор с= (РхтРо) полностью определяет вероятностную структуру задачи (стратегию природы). Можно построить оптимальную

(байесовскую) решающую функцию /о с вероятностью ошибки

s

Р(о/с, /о) = min {<11р},Я2р]}-¿=1

Пусть стратегия с определяется случайным образом при выборе ее из некоторой генеральной совокупности Bs, которой соответствует плотность р(с), где Bs = {с = (pf, : Yliftt =

О <Pt < 1; w = 1,2}.

Байесовский риск (средние потери при стратегии статистика /о и рандомизированной стратегии природы фиксированной сложности s) будет

R0= [ Р(о/с, fa)p(c)dc.

Jb,

Пусть р(с) - равномерное распределение и q\ < Q2- В этом случае получено, что

Пусть стратегия природы с неизвестна. Решающее правило / строится по выборке Zдг. Средние потери при алгоритме Q и рандомизированной стратегии природы

R = EcEzyP(f, 8, N) = T [ P(o/cJ, ZN)P(ZN/c)p(c)dc.

Zv ^

Средние потери Jî - двойное математическое ожидание вероятности ошибки по всевозможным стратегиям фиксированной сложности s и по всевозможным выборкам Zn фиксированного об-ъема X.

Пусть /,-, т,- - числа встречаемости значения х' соответственно в первом и во втором классе для выборки Если априорные вероятности заданы, то Ыи = qlllN - ожидаемое число объектов класса и>.

Теорема 2.1. Средние потери Л в случае отсутствия информации

о виде распределений определяются следующей формулой

2

(ЛГ2 + я - 1)!(ЛГ,+*-1)!

Л А (М2 - т, + * - 2)1(М1 - ^ + 8 - 2)!

* ЕЕ--9 <™ь'ь^У2),

где

^(гтцЛь^Ь^) =

я1 е £>2

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

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

При фиксированной априорной^ вероятности <71 вектор с = (С//,..., С/Г"1,..., и1,...,итп"-\ У,1,...,;^-1,-, к1,-КГ""1) полностью определяет вероятностную структуру задачи (стратегию природы), где и*^ - есть вероятности появления значения tj переменной X] для первого и второго класса соответственно.

Et, Uj1 = 1. Еt,V¡' = 1. Если x¡ = tj, то С? = Ub и Vf = V,?', где х = (a;i,...,xn), j = 1, ...,n.

Пусть стратегия природы с — (Р\, P¿) определяется случайным образом при выборе ее из некоторой генеральной совокупности Bs, которой соответствует плотность р(с). Имеем Bs = {с =

Vi,...,v„r"_1) /^uj' = = i, о < v) < i,

0< <1, j = 1,.-,n}.

Пусть p(c) - равномерная плотность распределения. Показано, что средние потери при байесовском решающем правиле равны

< = «П (»V - !)2 Г - /' "»'"fox п П V}1}*

j=l •'u j=l j=l

i=i

Если стратегия природы с неизвестна, то средние потери равны

R11 = EcEZnP(J,s,N) = £ /" P(o/ZN,c)P(ZN/c)p(c)dc,

где P(o/c, 7, ZN) = q2 П"=1 Vp + 91 Е*е№ П"=1 U? - вероятность ошибки для некоторой выборочной решающей функции /, гг = {*//(*) = cj}.

Теорема 2.2. Средние потери

R"

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

R« WП [(>■;-^ rí7 X

где

_ " гп/ + 1 „ " Iх/ + 1

reo1 j'=i ; i€D2i=1 7

" числа встречаемости значения Xj соответственно в 1-м и

во 2-м классе.

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

В третьем параграфе проведены исследования асимптотических свойств функции средних потерь для оптимальных (в смысле минимума средних потерь) выборочных решающих функций /g с учетом и без учета независимости характеристик. ПуСТЬ Г\ = ... = гп = г.

Утверждение 2.6 Если q\ = r/2, Nun фиксированы, то при г —» ос имеем R = EcEzNP(/о, s, N) —> 0,5.

Утверждение 2.7. Если q\ = q-2, N и г фиксированы, то при п —» оо имеем R = EcEzNP(f0, s,N) —» 0,5.

Теорема 2.3. Для того, чтобы средние потери

R = EcEZnP{J0,s,N) -^0,25

при s —► оо и jV —► оо, (qi = g2)> достаточно выполнения условия N(s) = o(s).

Утверждение 2.10. Если г фиксировано, то прип —» оо и Лг —> ос «AtecAt R" = EcEz„P(f0, s, N) -> 0.

В четвертом параграфе продемонстрированы эффекты ограниченности выборки для дискретного пространства характери-

стик с учетом и без учета независимости. Качество распознавания рассматривается как функции от объема выборки N и сложности распределений s, q\ = q2. Средние потери в случае произвольных распределений вычислены для решающего правила, использующего оценки максимального правдоподобия, а в случае независимых характеристик - для оптимального (в смысле минимума средних потерь RH) решающего правила.

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

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

На практике априорные вероятности неизвестны, поэтому стратегию природы зададим следующим образом: с =

= 1,2. где pf = q^pf. В дальнейшем волну будем опускать. Не теряя общности, предположим, что сложность s четна.

Зафиксируем Рц. Множество стратегий Вв = {с = :

Е,-(Р,?+Р?) = 1, Ех'е^РКЕх'е^Р* =-Ро, 0<рГ< 1,^ = 1, 2}. Пусть

на В3 при фиксированном значении байесовского уровня ошибки Р0 задано равномерное распределение р(с).

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

Р(о/с, 7,^)= ]Грг2 +

г'еЯ1 г'бО2

где I?1 = {х' : 1{ > т,}, Х>2 = И/И1, - числа встречаемости

значения ¿с' для первого и второго классов соответственно. Если Ро = 0, то средние потери

Ф-1)

Ро 2(ЛГ + в)(ЛГ + а-1)' Теорема 3.1. Для того, чтобы средние потери

Ир0=о = ЕсЕг„Р(7,ЛГ, Ро = 0) - о

при .5 —» сю и N оо достаточно выполнения условия = о(в).

Положим для краткости а1 = N2 — Ш1 + « — 2 — г, = + к, а\ =-. N1 - 1Х + ггц + 1 + ] + г, В{ = В(тх + ; + - Л + г + в - 1).

= Ь+к+1, й\ = + В\ = £(тгМ+ 1).

Пусть

9\{т\, ¡¡,N1, N-2, Ро) = <

> т1

Теорема 3.2. Средние потери Рр0 в случае фиксированного байесовского уровня ошибки Ро > О определяются следующей формулой = ЕСЕ2„Р(7, 8, лг, Р0) = §(Е1Е2„Р(1, 3, ЛГ, Р0) + Е2сЕ2„Р(], в, К Ро)),

где

А' N2 N^=N-N2

*

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

Теорема 3.3. Если Ро = 0, то решающее правило, использующее оценки максимального правдоподобия, является оптимальной стратегией статистика, ■ обеспечивающей минимум средних потерь В.р0.

Положим для краткости а1 = А^ — 2 —и, а2 = ^—¡¿+в—2—1/;

Ъ\ = и+к, Ь\ = 1{+к+1, Ь\ = = т{+к; = Nl-li+m¡+\+j+v,

(1\ = Ы^-и + ггц-Ы + и, 11\ = N2-1711 + ^+3 + 1', (Р2 = М2-ггц + и + + В\ = B(ml+j + 2,N1-ll + v + s-l), В\ = В{11 + з + 2,Ы2~т1 + и+з-1), В\ = В(т1+] + 1,М1-11+1У+8-1), В| = Р^^^-Ы^г-т^г/Ч-в-!).

ПуСТЬ S^(rij, m;, Po) =

»-2 ( s~2\ 2

Uh,mi,P0) = Y'[ \(-lYTSi(lumi,PQ), a, = 1,2. \ " ) t=1 Теорема 3.4. Для x' £ D решающее правило

-т, ,4 f М1г,т{,Р0) > /2(/,-,"г«,-Ро) f{%) = 4

[2, Ми,т{,Р0) <М1{,тгц,Р0)

является оптимальной стратегией статистика, обеспечивающей минимум средних потерь Rp0 при любом фиксированном Pq > 0.

В пятом параграфе продемонстрированы эффекты ограниченности выборки при заданном байесовском уровне ошибки.

Увеличение размерности пространства п влечет за собой ухудшение качества классификации при любых фиксированных значениях Pq. Чем больше Pq, тем большие значения объема выборки N требуются для получения заданного качества классификации. Показано, что с увеличением N разница между средним риском Rpa и байесовским уровнем ошибки Pq при малых тг не столь велика, как это наблюдается при больших п.

Отметим, что даже при больших объемах выборки (JV = 1000) при n = 10nr = 2(s = 1024) несмотря на то, что байесовский уровень ошибки нулевой, средние потери заметно от него отличаются, _RPo=o = 0,127. Это объясняется следующим: при объемах выборки сравнимых по величине со сложностью стратегии вероятность того, что некоторые значения случайной величины

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

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

И* =ЕраЕсЕ2„Р(7,8,Ы).

Положим для краткости щ = N2 — т\ — к, щ = пц + /1 — г + ] + 2, uз-N^-l■[ + s-l,щ = m^-i + j + Nl+l,u5 = ml + N1-i + j + t2 + 2. Пусть ф^тиЬ, N¡,N3) =

Е"=о ЕЙГ' Е£о Еп+='о Е«'=1 () )Ф*(™и/1, М,ЛЬ), к > т Е^ЕЙГ1 Е"=оЕп=оЕги2=о ^у.Ы.ЬЛ.т к < гщ,

где

*В{1 + к+1,а-1)В{и2,и3у ' (-) ,

И5 + 11 I

функция ф2(гп,1,11, N1, N2) отличается от функции ф\(гп1, к, ^,N2) только заменой знака ">" на знак ">", а знака "<" на знак "<".

Теорема 3.5. Средние потери В* в случае отсутствия информации о виде распределений определяются следующей формулой

В* = Щ + Щ, где

N N^N-N1

щ = ф -1)2 Е Е £

¡МЛ^-ЬЖ^-гту.'

л2=0 1711=0 /1=0

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

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

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

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

Например, пусть отсутствует какая-либо априорная информа-

ция о распределении или о байесовском уровне ошибки, г = 2, п = 4. Необходимо определить минимально допустимое значение объема выборки М* для того, чтобы средние потери отличались от оптимального значения средних потерь на величину меньшую 0,1. Если предположить, что дх = 92, и воспользоваться зависимостью, полученной в теореме 2.1, то получим М* = 30, а если воспользоваться зависимостью, полученной в теореме 3.5, то получим Лг* = 18.

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

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

Пусть - подмножество всевозможных стратегий природы сложности з. Каждому множеству Ьа при фиксированном байесовском уровне ошибки Ро необходимо поставить в соответствие такую стратегию природы со, чтобы средние потери Др„ при

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

Определение 4.1 Под усредненной стратегией природы с0 при фиксированных сложности в и байесовском уровне ошибки Ро понимается стратегия природы, для которой вероятности появления г—го значения определяются как

1 2 1 ~ Ро 1 2 Ра Рп-1 = Рк = —~—; Р% = Ра-1 = —■

Вычислены средние потери Рг„ = ЕгкР{о/со, /, Лг) для усредненной стратегии природы при фиксированных Ро, в, N и

решающего правила , использующего оценки максимального

1 Лч - 1\ ,Ч

правдоподобия: если Ро = 0, то Рг„ = - ( --1 ; если Ро > О, то

Рго = Е^Р(о/с0,У, М) + Е^Р(о/с0,7, IV), где

N и, N,=N-N2 . . . = - > > > ———-гттттт-гт,

( , 1 ^ т1 31{ти1иРа) = <

[ (1 -Р0)/в, 11 < ть

, г. ч [ ^ > ТО1

52(^1, «1, Ро) =< ,

\ (1 - Ро)/э, 1г < ТЩ.

В 4, 5 и 6 параграфах показано, что средними потерями для усредненной стратегии можно оценивать средние потери для

рандомизированной стратегии Rp0 и найдены объемы выборки N* при заданном £ > О, начиная с которых данная оценка справедлива.

Теорема 4.1. Если s фиксировано и Р0 = 0, то для любого е > О существует такое N*, что при всех N > N*

\EZnP{o/C0,7, N) - EcEZnP{7, в, N, Po)I < е.

Теорема 4.2. Если s фиксировано и Pq = 0, то для существования предела

lim \EeEZsP(f, s, N, Po) - Ez„P(o/cü, f,N)\ = 0

достаточно выполнения условия N(s) = o(s).

Теорема 4.3. Для любого е > 0 и фиксированных s,Pq существует такое N*, что при всех N > N*

\EZNP(o/c0J,N)-Pa\<£.

Теорема 4.4. При фиксированных сложности s и Pq для любого е > 0 существует такое №, что при всех N > №

\EcEz„P(7,s,N,P0) - Ez„P(o/cqJ,N)I <

Таким образом, начиная с некоторого N > №, средний риск Rpa можно оценивать с помощью средних потерь для усредненной стратегии природы R^ и определять значения N, для которых подобная оценка справедлива. Например, если е = 0,05,

Ро = 0,05, то при сложности в = 2 получаем № = 5; при сложности в = 4 получаем № = 10.

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

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

Определение 5.2. Класс решающих функций Ф назовем универсальным, если

1) класс Ф образует последовательность подклассов Ф1 С ... С Фэ = Ф и каждому подмножеству Фд/ С Ф ставится в соответствие некоторая сложность /х(Фм) такая, что /¡(Ф^ < ... < м(Ф9) = ц(Ф), где 9 < оо;

2) для любых стратегии сие > 0 найдется такой номер М* (М* 6 {1,...,д}), что для некоторой / £ Ф.^. выполняется

P(O/f,c)-P0(c)<£.

Каждому классу Фд/ поставим в соответствие подмножество стратегий природы Lf С L¡¡ следующим образом

If = {с : В/ € ФM, P(o/f,c) - Ро(с) < е}.

Назовем n{Lf) - относительой сложностью подмножества Lf. Относительную сложность подмножества L^f будем определять равенством n(L^) = м).

Определение 5.3 Под сложностью класса логических решающих функций Фм понимается число подобластей разбиения пространства D, соответствующих логической решающей функции / € Фм, т.е. fi(Фм) = М.

Для класса логических решающих функций p{Lf) = M. Если ' с 6 Ls, то для получения решения близкого к оптимальному (байесовскому) достаточно выбрать решающую функцию сложности M < s.

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

Теорема 5.1. При фиксированном типе предиката класс логических решающих функций Фд/ является универсальным.

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

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

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

Алгоритм Ы1Р строит решающее правило в виде дихотомического дерева. Ы1Р явился первым алгоритмом в классе логических функций, предназначенным для многоклассового распознавания (к > 2). Алгоритм СЬИР явился первым алгоритмом, использующим группу деревьев для случая к > 2.

В четвертом параграфе проведено экспериментальное исследование алгоритма Ы1Р с использованием усредненных стратегий природы. Для алгоритма Ы1Р при заданных параметрах N и М получены оценки среднего риска Яра на множестве усредненных стратегий, заданных с помощью имитационного моделирования. Для различных значений Ро характерно, что при малых значениях сложности (в = 2; 4) с увеличением объема выборки от 40 до 100 ДНр0 (оценка отклонения среднего риска Яр0 от /о) значительно не изменяется, близка к нулю. Рассмотренный эффект легко объясняется тем, что при сложности 5 = 4 для алгоритма Ы1Р объем выборки 40 является достаточным для получения качественной классификации.

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

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

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

Совместно со Лбовым Г.С. и Бериковым В.Б. была разработана компьютерная система ЛАСТАН (Логический Анализ Статистических Наблюдений), предназначенная для решения задач распознавания, регрессионного и кластерного анализа с использованием класса логических решающих функций. В системе предусмотрена возможность варьировать параметр сложности решающей функции M в зависимости от имеющего объема выборки N и числа признаков п. Приведены примеры использования системы ЛАСТАН для решения практических задач из области медицинской диагностики, биологии и т.д. (имеется более двадцати актов о внедрении). Система ЛАСТАН реализована на языке TURBO PASCAL 5.5 и работает под управлением MS DOS.

Система ЛАСТАН предназначена также для решения задач регрессионного анализа. В пятом параграфе описан новый ал-

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

случая независимых характеристик.

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

4. Исследовано поведение качества классификации (средних потерь) в зависимости от изменения объема выборки N, размерности пространства п, числа значений г каждой характеристики, байесовского уровня ошибки Ро для произвольных распределений и для случая независимых характеристик. Показано, что с увеличением байесовского уровня ошибки отклонение среднего риска от Ро увеличивается для любых фиксированных Лг, п и г. Исследованы асимптотические свойства функции средних потерь. Получены предельные значения средних потерь.

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

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

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

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

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

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

1. Лбов Г.С, Старцева Н.Г. Алгоритм многоклассового распознавания, основанный на логических решающих функциях// Вычислительные системы. Новосибирск. 1986, вып.111. С.3-10.

2. Лбов Г.С, Старцева Н.Г. Классификация и принципы сравнения алгоритмов построения решающих правил распознавания// Статистический анализ и обработка экспериментальных данных. Новосибирск, 1988. С.14-23.

3. Лбов Г.С, Старцева Н.Г. Логические решающие правила и их использование в технико- экономическом анализе производства// Заводская лаборатория. М., 1988. С.72-75.

4. Лбов Г.С, Старцева Н.Г. Пять процедур распознавания по группе деревьев// Тр.VI Всесоюз. школы-семинар "Непараметрические и робастные методы статистики в кибернетике". Томск, 1987. 4.2. С.265-273.

5. Лбов Г.С, Старцева Н.Г. Об одном понятии сложности стратегии природы в распознавании образов// Вычислительные системы. Новосибирск. 1986, вып.117. С.91-102.

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

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

8. Старцева Н.Г. Влияние сложности распределений на качество классификации для независимых переменных// Докл. РАН. 1997, Т^Ж. С. ЧЫ ' <¡12,.

9. Старцева Н.Г. Зависимость классификации от сложности распределений// Труды Межд. конф. "Компьютерный анализ данных и моделирование". Минск, 1995. Т.2. С.255-259.

10. Старцева Н.Г. Зависимость математического ожидания

вероятности ошибки распознавания от объема выборки// Труды 5 Всесоюз. конф."Математические методы распознавания образов". Киев, 1991. С. 107-108.

11. Старцева Н.Г. LRP-логическое решающее правило// Вычислительные системы. Новосибирск. 1986, вып.111. С.11-22.

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

13. Старцева Н.Г. Решение задачи многооткликовой регрессии для разнотипных признаков в классе логических решающих правил// Вычисл.системы. Новосибирск. 1990, вып.134. С.67-84.

14. Старцева Н.Г. Сравнение алгоритмов распознавания на стратегиях природы различной сложности// Методы и средства статистического анализа. Новосибирск, 1988. С.67-71.

15. Старцева Н.Г. Средние потери в задачах классификации// Труды 4 Международной конфер. "Pattern Recognition and information processing". Минск, 1997, C.21-26.

16. Старцева Н.Г. Статистическая устойчивость решающих функций классификации// Известия Вузов. Физика. 1995, N.9. С.74-78.

17. Старцева Н.Г. Сходимость математического ожидания верятности ошибки к усредненной стратегии. //Докл. РАН, 1995. Том 341. N.5. С.235-240.

18. Старцева Н.Г., Людвина Н.А. Регрессионный анализ для структурированного объекта// Докл. РАН. 1996, Т.346. N.5.

C.600-603

19. Lbov G.S., Starceva N.G. About statistical robustness of decision functions in pattern recognition problems // Pattern Recognition and Image Analysis, 1994. Vol 4. No.3. P.97-106.

20. Lbov G.S., Starceva N.G. LASTAN-A system for Logical Analysis of Statistical Observation functions in pattern recognition problems // Pattern Recognition and Image Analysis, 1992. Vol 2. No.l. P.57-61.

21. Lbov G.S., Starceva N.G. Logical-and-probability models at ecology// Conditionally well posed problems of Mathematical Physics and Analysis VSP/TVP. Notherlands, 1992. P.46-51.

22. Starceva N.G. Influance of volume of sample and complexity distribution on quality of classification // Pattern Recognition and Image Analysis, 1992. Vol 2. No.3. P.265-270.

23. Starceva N.G. Convergence of mathematical expectation of error probability for averaged strategy // Pattern Recognition and Image Analysis, 1994. Vol 4. No.2. P.110-115.

24. Starceva N.G., Ludvina N.A. Recognition of quantitative variable for structural objects// Pattern Recognition and Image Analysis, 1996. Vol 6. No.3. P.487-490.

25. Starceva N.G. Influence of distribution complexity on classification quality for independent variables// Pattern Recognition and Image Analysis, 1997. Vol 7. No.3. P. Z6~c .

26. Starceva N.G. The effects of the limited in discrete space// Pattern Recognition and Image Analysis, 1997. Vol 7. No.2. P.241-249.