Оптимизационный подход в задачах математической диагностики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Кокорина Анастасия Владимировна

ОПТИМИЗАЦИОННЫМ ПОДХОД В ЗАДАЧАХ МАТЕМАТИЧЕСКОЙ ДИАГНОСТИКИ

01.01.09-дискретная математика и математическая кибернетика

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

Санкт-Петербург 2004

Работа выполнена на кафедре Математической теории моделирования систем управления факультета Прикладной математики - процессов управления Санкт-Петербургского государственного университета

Научный руководитель:

доктор физико-математических наук, профессор Демьянов Владимир Фёдорович

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

профессор Квитко Александр Николаевич

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

Ведущая организация:

Институт машиноведения Российской Академии Наук

Защита состоится «24» ноября 2004г. в_

часов_минут на

заседании Диссертационного совета К-212.232.07 по защитам диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, 10-я линия В.О., д.33.

С диссертацией можно ознакомиться в научной библиотеке имени A.M. Горького Санкт-Петербургского государственного университета.

Автореферат разослан

2004г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

В. Ф. Горьковой

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

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

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

РОС. НАЦИОНАЛЬНА*}

библиотека I

оУ-ЗДЗ 1

обратили свое внимание на проблемы диагностики. Так, С. Смейл опубликовал статью в журнале "Bulletin of the American Mathematical Society" (vol. 39, N 1, 2002), посвященную математическим основам обучения, где излагается статистический подход к решению задач распознавания и идентификации. Статистический подход оказался эффективным при решении массовых задач, где удаётся собрать достаточно достоверную статистику. В случае отсутствия такой статистики практическая ценность разработанных подходов существенно снижается. Этот факт привел к тому, что 60-ые годы прошлого столетия в разных странах стали активно привлекать так называемые оптимизационные методы. Одними из первых этими вопросами занимались И.М. Гельфанд, Ю.И. Журавлев, Б.Н. Козинец, О.Л. Мангасарян, АА Первозванский, Б.Т. Поляк, А. И. Пропой, Дж.Б. Розен, В.Н. Фомин, ЯЗ. Цыпкин, В А Якубович и другие.

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

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

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

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

Настоящая работа находится в русле оптимизационного подхода (развиваемого сейчас, в частности, в работах Ю.Г. Евтушенко, A.M. Рубинова и их учеников), поэтому мы не будем заниматься статистическими аспектами обработки баз данных.

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

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

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

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

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

Научная новизна.

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

• Предложены новые методы оптимального разделения двух множеств (с помощью гиперплоскости).

• Разработано программное обеспечение (построены алгоритмы и созданы программы) для применения предложенных методов.

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на XIII международной конференции «Проблемы теоретической кибернетики» (г. Казань, 2002); на первой Российско-Французской международной конференции «Модели Долголетия, Старения и Деградации» («Longevity, Aging and Degradation Models») (г. Санкт-Петербург, 2004), на XXXII, ХХХШ, XXXIV и XXXV научных конференциях «Процессы управления и устойчивость» факультета прикладной математики и процессов управления СПбГУ (г. Санкт-Петербург), а также на семинарах кафедры математической теории моделирования систем управления СПбГУ.

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

Связь с научными программами. Работа выполнена при поддержке Российского фонда фундаментальных исследований (Код проекта РФФИ № 03-01-00668).

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

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

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

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

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

В главе 1 описываются алгоритмы ранжирования параметров.

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

Пусть заданы множества и :

Л = {а,е/4е/}, 5 = {6у е Я"|уеУ},

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

плотностей распределения . Наименьшее

значение площади Sk определяет наиболее существенную координату.

Также в параграфе 1.1 показано, что при проведении практических вычислений достаточно заменить подграфики функций и треугольниками с основаниями [£,' +т<т'^] и

, соответственно, и высотами и

И? = \/та" , соответственно, где т = 2.5 или т = 3, в соответствии со значениями функции Лапласа.

В параграфе 1.2 предложен метод идентификации для проведения ранжирования параметров в дискретном случае, когда координаты и

Ь)к принимают только конечное число значений: у,,^ (причем тк

сравнительно невелико). Построим множества:

К =К1'еАа,» =У,Л V/-б 1:тя,,

В качестве критерия значимости параметра выберем величину цк ^ . Чем меньше значение , тем более

существенной является к-ая координата.

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

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

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

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

Пусть заданы множества А с Л" и Вс.К" \ /4 = {а, ее/}, 5 = {6;е/Г

Введем следующий функционал:

F(x) = 1ЕАх)-Е»(х)+т(ТЛх) + т(Гв(х)?

где х е R",

Найдём вектор /ей", который доставляет минимум данному функционалу, т.е. решаем задачу min F(x) = F(x)

Возьмём х' в качестве нормали разделяющей гиперплоскости. Отметим, что значение F(x) - это площадь пересечения треугольников

в проекции на вектор х (умноженная на 2т2), х' - это самое информативное направление, так как площадь пересечения минимальна. Разделение множеств проводим гиперплоскостью: L(a) = {х| h(x, а) = 0}, где

Сформулируем правило идентификации. Пусть с = (с,,...,с/1)е А[)В. Отклонение точки с от гиперплоскости L(a) вычисляется по формуле: r(c,L(a)) = ^ (*о(а)>* )

Тогда если г(с, Ь(а)) < 0, то считаем, что се А ; если г(с, Ь(а)) > 0, то считаем, что сеВ ;

если же г(с, Ь(а)) = 0, то точка с является неидентифицируемой (данным идентификационным правилом).

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

В параграфе 2.3 приведены итоги ранжирования нескольких широко известных баз данных, проведенного по методам, предложенным в параграфах 1.1 и 1.2.

Затем была проведена идентификация элементов рассмотренных баз данных. Результаты применения методов оптимального разделения, описанных в параграфе 2.1, представлены в параграфе 2.3. Они свидетельствуют об эффективности предлагаемых нами процедур идентификации.

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

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

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

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

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

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

В параграфе 3.2 представлены рассматриваемые базы.

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

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

Приложение 1 содержит краткое описание баз данных, которые были использованы в численных экспериментах.

Для сравнения в приложении 2 приведены результаты другого алгоритма определения наиболее информативных признаков, полученные A.M. Багировым и др. в Балларатском университете (Австралия).

Тексты программ представлены в приложении Э.

ЗАКЛЮЧЕНИЕ

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

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

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

• Описан метод ранжирования дискретных параметров.

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

• Разработаны алгоритмы и созданы программы для применения предложенных методов ранжирования и идентификации. Проведено тестирование предложенных методов на реальных базах, которое показало работоспособность и эффективность новых методов и алгоритмического программного обеспечения.

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

По теме диссертации опубликованы следующие работы:

1. Кокорина А.В. Об одной задаче математической диагностики // Тезисы докладов XIII международной конференции «Проблемы теоретической кибернетики» (г. Казань, 2002). М.: издательство центра прикладных исследований при механико-математическом факультете МГУ, 2002, с. 90.

2. Кокорина А.В. Ранжирование параметров в задачах обработки данных // Труды XXXIII научной конференции студентов и аспирантов «Процессы управления и устойчивость». СПб: ООП НИИ Химии СПбГУ, 2002, с. 277-281.

3. Кокорина А.В. Ранжирование дискретных параметров в задачах обработки данных // Труды XXXIV научной конференции аспирантов и студентов «Процессы управления и устойчивость». СПб: Издательство СПбГУ, 2003, с. 276-279.

4. Kokorina A.V. Unsupervised and supervised Data Classification Via Nonsmooth and Global Optimization // Top, Volume 11, Number 1. June 2003. - Sociedad de Estadistica e Investigacion Operativa, Madrid, Spain, pp. 86-89.

5. Кокорина А.В., Кузьмичев В.Л. Прогнозирование эффективности лечения желчнокаменной болезни методом оптимального разделения // Труды XXXV научной конференции аспирантов и студентов «Процессы управления и устойчивость». СПб: Издательство СПбГУ, 2004, с. 318321.

6. Kokorina A.V. Ranking the Parameters in Classification Databases. «Longevity, Aging and Degradation Models» (in Reliability, Public Health, Medicine and Biology) // Материалы международной конференции LAD'2004 («Модели Долголетия, Старения и Деградации»), издательство СПбГПУ, 2004. Vol. 2, pp. 191-193.

Подписано к печати 14.10.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 усл. п.л. Тираж 100 экз. Заказ 3371. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

»19585

Список основных обозначений.

Введение.

Глава 1. Ранжирование параметров в задачах обработки данных.

1.1. Случай нормально распределенных параметров.

1.2. Случай дискретных значений.

1.3. Ранжирование произвольных параметров.

Глава 2. Методы разделения множеств и их применение.

2.1. Метод разделения двух множеств гиперплоскостью.

2.2. Результаты ранжирования некоторых баз данных.

2.3. Результаты разделения множеств.

Глава 3. Применение методов ранжирования и разделения множеств гиперплоскостью к решению задачи прогнозирования эффективности лечения желчнокаменной болезни.

3.1. Описание баз данных и постановка задачи.

3.2. Базы данных медицинской академйи по ЖКБ.

3.3. Результаты исследования.

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

В задачах медицинской диагностики оптимизационный подход к решению этой задачи был предпринят в 30-е годы Р. Фишером [59] (который разработал линейный дискриминантный анализ). В настоящее время эти задачи занимают ведущее место в теории обучающих машин, в задачах искусственного интеллекта. Для решения указанных задач существует несколько подходов (чисто статистический подход [4, 5, 7, 19, 21, 32, 33, 71], метод опорных векторов В.Вапника [9, 57, 77], метод машинного обучения [31,44, 45, 68], метод построения ядра [56, 76], метод обработки данных с помощью линейного программирования [51, 61, 66, 67], кластерный анализ [46, 52, 60, 62, 69]). К сожалению, не существует универсального метода, пригодного для решения всех задач распознавания, идентификации и диагностики. Поэтому, несмотря на наличие богатого арсенала средств для решения задач идентификации и множества успешно решенных практических проблем, интерес к этой тематике не ослабевает. Это объясняется многообразием новых постановок, индивидуальностью сложности реальных задач, необходимостью строить всё более усовершенствованные модели, которые адекватно описывали бы указанные реальные задачи. Вот почему в последние годы многие математики, до этого работавшие в других областях, обратили свое внимание на проблемы диагностики. Так, С. Смейл опубликовал статью в журнале "Bulletin of the American

Mathematical Society" (vol. 39, N 1, 2002), посвященную математическим основам обучения, где излагается статистический подход к решению задач распознавания и идентификации. Статистический подход оказался эффективным при решении массовых задач, где удаётся собрать достаточно достоверную статистику [1, 2, 3, 34]. В случае отсутствия такой статистики практическая ценность разработанных подходов существенно снижается. Этот факт привел к тому, что 60-ые годы в разных странах стали активно привлекать так называемые оптимизационные методы. Одними из первых этими вопросами занимались И.М. Гельфанд [11], Ю.И.Журавлев [20], Б.Н. Козинец [24], O.JI. Мангасарян [65], А.А. Первозванский [35], Б.Т. Поляк [37], А.И. Пропой [15], Дж.Б. Розен [73], В.Н. Фомин [44], Я.3. Цыпкин [15, 37], В.А. Якубович [45] и другие.

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

Названные выше задачи и создают направление в теории оптимизации, которое можно назвать математической диагностикой.

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

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

Настоящая работа находится в русле оптимизационного подхода (развиваемого сейчас, в частности, в работах Ю.Г. Евтушенко, A.M. Рубинова и их учеников), поэтому мы не будем заниматься статистическими аспектами обработки баз данных.

Как уже отмечалось, многие из упомянутых задач сводятся к разделению двух или более часто неразделимых множеств. Для этого важно иметь сравнительно простой критерий, с помощью которого можно классифицировать точки. При выбранном идентификаторе (называемом также классификатором, правилом идентификации или решающим правилом) - функционале, по значению которого судят о принадлежности данной точки тому или другому множеству - качество идентификации оценивается "естественным" критерием - количеством ошибочно идентифицированных точек. Поскольку такой критерий обычно описывается существенно разрывной функцией, то приходится этот естественный критерий качества заменять некоторым "суррогатным" функционалом, который может быть изучен методами математического программирования. В основе существующих оптимизационных методов лежат методы линейного и квадратичного программирования [13, 14, 22, 35], которые существовали и были наиболее эффективны во время создания указанных теорий машинного обучения (60-е - 80-е годы XX века). С тех пор методы оптимизации получили дальнейшее развитие, появились негладкий анализ и недифференцируемая оптимизация.

В отличие от изложенных подходов (основанных на линейном и квадратичном программировании), теперь эти задачи молено решать, используя негладкие критерии, которые лучше аппроксимируют "естественные" критерии качества. Применение методов линейного и квадратичного программирования к решению задач математической диагностики привели к созданию так называемого линейного дискриминантного анализа [43]. На повестке дня — создание негладкого дискриминантного анализа, основанного на использовании негладких моделей и применении методов негладкого анализа и недифференцируемой оптимизации [16, 17, 47, 49, 58, 75]. Можно ожидать, что негладкий дискриминантный анализ позволит улучшить качество идентификации и распознавания и расширить арсенал имеющихся средств для решения задач математической диагностики. Поясним задачу идентификации точек множеств. Пусть AaR" и BczR" - некоторые замкнутые ограниченные множества. Требуется указать достаточно простой критерий для различения элементов множеств А и В.

Точка с е A U В считается идентифицированной, если можно указать, что либо с еА\ В, либо с еВ\ А. Если с е А П В, то точка с считается существенно неидентифицируемой.

Вначале предположим, что А и В - выпуклые множества в R". Возможны два случая:

1)АПВ = 0,

2) А[)Вф0.

Случай Л П В = 0 (множества А и В не пересекаются). По теореме отделимости (см. [17, 39]) существуют вектор у е R" и число d е R, такие, что x,y) + d> 0 VxeA, (1) x,y) + d< 0 VxeB. (2)

Для того чтобы найти z = [у, d] е Rn+l, удовлетворяющее (1) и (2), достаточно найти f(A,В)= mm || а-Ь\\2=\\ а -Ъ" ||2. аеЛ.оеВ

Поскольку А п в = 0, то ДА,В)> 0.

Положим у* = —--—, d" - II а -Ь*" а -К (ал-Ъ* Л II2

211 а -Ъ" 2

По необходимому условию минимума (см., например, [17]), пара z* =[у*,d*] удовлетворяет неравенствам: x,y) + d* >-\\а -b* ||>0 VxeA, (3) x,y) + d* <--|| a -b* ||<0 \/хеВ. (4)

Функция r(x,z*) = (x,y*) + d* может быть использована как критериальная функция.

Пусть известно, что с е A U В. Неравенства (3) и (4) означают, что если r(c,z*) > 0, то с е А, если r(c,z*) < 0, то с е В.

Таким образом, в случае, когда множества А и В выпуклые и не пересекаются, точки множеств А и В можно идентифицировать с помощью линейной функции r(c,z*), причем такая идентификация -точная: каждая точка ceAljB идентифицирована правильно. Этот же подход применим и в случае, когда множества А и В не обязательно выпуклые, но их выпуклые оболочки не пересекаются. И в этом случае точная идентификация возможна с помощью линейной критериальной функции, которую можно построить, как описано выше, взяв в качестве множеств выпуклые оболочки множеств А и В. Случай

В случае, когда co^Dcoi? Ф 0 (т.е. когда пересечение выпуклых оболочек множеств А и В непусто), точная идентификация с помощью линейной критериальной функции невозможна. Тем не менее, можно ставить задачу о нахождении линейной критериальной функции, наилучшей в том или ином смысле. Точнее говоря, пусть задана линейная функция r(c,z*). Будем использовать следующее правило идентификации: для c^A\jB будем считать, что с е А, если r(c,z*) > О, с е В, если r(c,z*) < 0. В случае г (с, z*) = 0 считаем точку с неидентифицированной. Очевидно, что при таком правиле идентификации часть точек может быть неверно ' идентифицирована. Задача состоит в нахождении такого z*, чтобы количество неверно идентифицированных точек (либо их относительное количество) было как можно меньше. Выбор функционала, который требуется минимизировать, зависит от поставленной задачи.

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

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

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

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

Научная новизна.

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

• Предложены новые методы оптимального разделения двух множеств (с помощью гиперплоскости).

• Разработано программное обеспечение (разработаны алгоритмы и созданы программы) для применения предложенных методов.

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на XIII международной конференции «Проблемы теоретической кибернетики» (г.Казань, 2002); на первой Российско-Французской международной конференции «Модели Долголетия, Старения и Деградации» («Longevity, Aging and Degradation Models») (г. Санкт-Петербург, 2004), на XXXII, XXXIII, XXXIV и XXXV научных конференциях «Процессы управления и устойчивость» факультета прикладной математики и процессов управления СПбГУ (г. Санкт-Петербург), а также на семинарах кафедры математической теории моделирования систем управления СПбГУ.

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

Связь с научными программами. Работа выполнена при поддержке Российского фонда фундаментальных исследований (Код проекта РФФИ №03-01-00668).

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ [25] - [28], [63], [64].

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

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

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

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

• Описан метод ранжирования дискретных параметров.

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

• Разработаны алгоритмы и созданы программы для применения предложенных методов ранжирования и идентификации. Проведено тестирование предложенных методов на реальных базах, которое показало работоспособность и эффективность новых методов и алгоритмического программного обеспечения.

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

86

Заключение

1. Бейли Н. Статистические методы в биологии. Пер. с англ.; под ред. В.В. Налимова. -М.: Иностранная литература, 1962.

2. Бешелев С.Д., Гурвич Ф.Г. Математико-статистические методы экспертных оценок. -М.: Статистика, 1980.

3. Вальд А. Последовательный анализ. Пер. с англ.; под ред. В.А. Севастьянова. М.: Наука, 1960.

4. Вальд А. Статистические решающие функции. Позиционные игры. Под ред. Н.Н. Воробьева и Н.Н Врублевской. М.: Наука, 1967, с. 300-522.

5. Ван дер Варден Б.Л. Математическая статистика. Пер. с немецкого; под ред. Н.В. Смирнова. М.: Иностранная литература, 1960.

6. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). -М.: Наука, 1974.

7. Генкин А.А. Новая информационная технология анализа медицинских данных (программный комплекс ОМИС). СПб.: Политехника, 1999.

8. Головкин Б. А. Машинное распознавание и линейное программирование. М.: Советское радио, 1972.

9. Гублер E.B. Вычислительные методы анализа и распознавания патологических процессов. JL: Медицина, 1978.

10. Девятериков И. П., Пропой А.И., Цыпкин Я.З. О рекуррентных алгоритмах обучения распознавания образов // Автоматика и телемеханика, № 1,1967.

11. Демьянов В.Ф. Идентификация точек двух выпуклых множеств // Вестник Санкт- Петербургского университета. Серия 1, вып. 3 (N 17), 2001, с. 14-20.

12. Демьянов В.Ф., Васильев Л. В. Недифференцируемая оптимизация. -М.: Наука, 1981.

13. Дубров A.M. Обработка статистических данных методом главных компонент. -М.: Статистика, 1978.

14. Елисеева И.И., Руковишников В.О. Группировка, корреляция, распознавание образов. -М.: Статистика, 1977.

15. Карманов В.Г. Математическое программирование. -М.: Наука, 1975.

16. Кендалл М., Стюарт А. Статистические выводы и связи. Пер. с англ.; под ред. А.Н. Колмогорова и Ю.В. Прохорова. М.: Наука, 1973.

17. Козинец Б.Н. Рекуррентный алгоритм разделения двух множеств. В сб. под ред. В.Н. Вапника «Алгоритмы обучения распознавания образов». М.: Советское радио, 1973.

18. Кокорина А.В. Ранжирование дискретных параметров в задачах обработки данных // Труды XXXIV научной конференции аспирантов и студентов «Процессы управления и устойчивость». СПб: Издательство СПбГУ, 2003, с. 276-279.

19. Кокорина А.В. Ранжирование параметров в задачах обработки данных // Труды XXXIII научной конференции студентов и аспирантов «Процессы управления и устойчивость». СПб: ООП НИИ Химии СПбГУ, 2002, с. 277-281.

20. Колкот Э. Проверка значимости. Пер. с англ. М.: Статистика, 1978.

21. Кулъбак С. Теория информации и статистика. Пер. с англ.; под. ред. А.Н. Колмогорова. М.: Наука, 1967.

22. Литваков Б.М. О сходимости рекуррентных алгоритмов обучения распознаванию образов // Автоматика и телемеханика, № 1, 1968.

23. Логинов В.К, Хургин Я.И. Общий подход к проблеме распознавания образов. Сб. тр. МИНХ и ГП, вып. 62. М.: Недра, 1966.

24. Мале та Ю.С., Тарасов В.В. Математические методы статистического анализа в биологии и медицине. Вып. 1, вып. 2. М.: Издательство МГУ, 1982.

25. Неймарк Ю.И., Баталова З.С. и др. Распознавание образов и медицинская диагностика. М.: Наука, 1972.

26. Первозванский А.А. Распознавание абстрактных образов, как задача линейного программирования // Известия АН СССР, Техническая кибернетика, № 4,1965.

27. Петрова Н.В. Разделение двух дискретных одномерных множеств методом изоляции // Труды XXXV научной конференции аспирантов и студентов «Процессы управления и устойчивость». СПб: Издательство СПбГУ, 2004, с. 328-330.

28. Поляк Б.Т., Цыпкип Я.З. Псевдоградиентные алгоритмы адаптации и обучения // Автоматика и телемеханика, № 1, 1973.

29. Приставко В.Т., Ярвельяп А.В. Методы разделяющей гиперплоскости в медико-биологических задачах // Труды XXXV научной конференции аспирантов и студентов «Процессы управления и устойчивость». СПб: Издательство СПбГУ, 2004, с. 331-333.

30. Рокафеллар Р. Выпуклый анализ. -М.: Мир, 1973.

31. Славин М.Б. Методы системного анализа в медицинских исследованиях. -М.: Медицина, 1989.

32. Тинтиер Г. Введение в эконометрию. Пер. с англ. М.: Статистика, 1965.

33. Уилкс С. Математическая статистика. М.: Наука, 1967.

34. Урбах В.Ю. Дискриминантный анализ: основные идеи и приложения. Сб. Статистические методы классификации, вып. 1. МГУ, 1969.

35. Фомин В.Н. Математическая теория обучаемых опознающих систем. -М.: Издательство ЛГУ, 1976.

36. Якубович В.А. Некоторые общие теоретические принципы построения обучаемых опознающих систем. Сб. Вычислительная техника и вопросы программирования. ЛГУ, 1965.

37. AnderbergM.R. Cluster Analysis for Applications. Academic Press, 1973.

38. Babu G.P. andMurty M.N. A near optimal initial seed value selection in the k-means algorithm using a genetic algorithm. Pattern Recognition Letters 14,1993, pp. 763-769.

39. Bagirov A.M., Rubinov A.M. and Yearwood J. A heuristic algorithm for feature selection based on optimization techniques. In: Sarker R., Abbas H.and Newton C.S. (eds.), Heuristic and Optimization for Knowledge Discovery. Idea Publishing Group. 2000.

40. Bagirov A.M., Rubinov A.M. and Yearwood J. A global optimization approach to classification. Optimization and Engineering 3, 2002, pp. 129-155.

41. Bhuyan N.J., Raghavan V.V. and Venkatesh K.E. Genetic algorithms for clustering with an ordered representation. Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp. 408-415.

42. Bradley P.S. and Mangasarian O.L. Feature selection via concave minimization and support vector machines. Machine Learning Proceedings of the Fifteenth International Conference (ICML'98), San Francisco, California. Morgan Kaufmann, 1998, pp. 82-90.

43. Bradley P.S. and Mangasarian O.L. Massive data discrimination via linear support vector machines. Optimization Methods and Software 13, 2000, pp. 1-10.

44. Chen C. and Mangasarian O.L. Hybrid misclassification minimization. Mathematical Programming Technical Report 95-05, University of Wisconsin, 1995.

45. Cristianini N. and Shawe-Taylor J. An Introduction to Support Vector Machines and other kernel based methods. Cambridge University Press, 2000.

46. DeCoste D. andScholkopfB. Training invariant support vector machines. Machine Learning 46, 2002, pp. 161-190.

47. Fisher R.A. Contributions to Mathematical Statistics. New-York, 1952.

48. Hansen P. and Jaumard B. Cluster analysis and mathematical programming. Mathematical Programming 79, 1997, pp. 191-215.

49. Highleyman W.H. Linear decision functions with applications to pattern recognition. Proc. IRE, № 6, 1962.

50. Jain A.K., Murty M.N. and Flynn P.J. Data clustering: a review. ACM Computing Surveys 31, 1999, pp. 264-323.

51. Kokorina A.V. Unsupervised and supervised Data Classification Via Nonsmooth and Global Optimization. Top, Volume 11, Number 1. June 2003. Sociedad de Estadistica e Investigacion Operativa, Madrid, Spain, pp. 86-89.

52. Mangasarian O.L. Linear and nonlinear separation of patterns by linear programming. Operations Research, vol. 13, 1965, pp. 444-452.

53. Mangasarian O.L. Misclassification minimization. Journal of Global Optimization 5, 1994, pp. 309-323.

54. Mangasarian O.L. Mathematical programming in data mining. Data Mining and Knowledge Discovery 1, 1997, pp. 183-201.

55. Michie D., Spiegelhalter D.J. and Taylor C.C. Machine Learning, Neural and Statistical Classification. Ellis Horwood Series in Artificial Intelligence, 1994.

56. Mirkin B. Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996.

57. Murphy P.M. and Aha D. W. UCI repository of machine learning databases. Technical report, Department of Information and Computer science, University of California, Irvine, 1992. www.ics.uci.edu/mlearn/MLRepositorv.html.

58. Nagy G. State of the art in pattern recognition. Proceedings of the IEEE 56, 1968, pp. 836-862.

59. Quinlan J.R. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, 1993.

60. Rosen J.B. Pattern separation by convex programming. Journal of Mathematical Analysis and Applications, vol. 10, 1965, pp. 123-134.

61. Rosenblatt F. The perseptron, a probability model for information storage and organization in the brain. Psychol. Rev., 65, 1958.

62. Rubinov A.M., Soukhoroukova N. V. and Yearwood J. Clustering for studying structure and quality of datasets, Research Report 01/24, University of Ballarat, 2001.

63. Scholkopf B. and Smola A. Learning with Kernels. The MIT Press, 2002.

64. Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, 2000.

65. Ward J. Hierarchical grouping to optimize and objective function. Journal of the American Statistical Association 58, 1983, pp. 236-244.