Оптимизационный подход в задачах математической диагностики

Актуальность темы

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

В задачах медицинской диагностики оптимизационный подход к решению этой задачи был предпринят в 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* <—|| ab* ||<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^AjB будем считать, что с е А, если 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−668).

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

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

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

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

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

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

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

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

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

Заключение

.