Методы негладкого анализа в задачах идентификации и диагностики

1.

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

.

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

В области решения указанных задач существует несколько различных подходов: статистический подход, получивший развитие в начале 60-х годов прошлого столетия [1, 2, 3, 4, 5, 6, 20, 21, 46, 47, 74, 86, 92], метод опорных градиентов, предложенный В. Вапником [9, 92], метод машинного обучения [44, 57, 58, 82], метод построения ядра [70, 91], метод обработки данных с помощью линейного программирования [64, 76, 80, 81], кластерный анализ [57, 63, 73, 75, 81]. Все перечисленные методы обладают своими преимуществами и недостатками в каждом отдельном случае. Так, статистический метод эффективен для решения массовых задач при наличии обширной статистики [1, 2, 3, 47]. Если подобная статистика отсутствует, то достоверность решения, полученного с помощью данного метода, существенно снижается. В связи с этим обстоятельством наряду со статистическим подходом, начал развиваться так называемый «оптимизационный подход» [72]. Одними из первых, кто занимался данным вопросом, были И. М. Гельфанд [11], Ю. И. Журавлев [22], Б. Н. Козинец [37], О. Л. Мангасарян [79], А. А. Первозванский [48], Б. Т. Поляк [50], А. И. Пропой [15], Дж.Б. Розен [88], В. Н. Фомин [57], Я. З. Цыпкин [15, 50], В. А. Якубович [58] и другие.

В 60-е — 80-е годы XX века наиболее развитыми и популярными инструментами оптимизации были линейное и квадратичное программирование [13, 14, 35, 48], поэтому до сих пор оптимизационные элементы, которые являются ключевыми во всевозможных методах, основаны или сводятся к линейному или квадратичному программированию. Такой подход называют линейным дискриминантным анализом (ЛДА) [56]. Тем не менее, в последние десятилетия прогресс в математическом программировании и компьютерных науках, возникновение и развитие негладкого анализа и недифференцируемой оптимизации дали новые усовершенствованные и усложненные инструменты. Теперь, используя эти инструменты, стало возможным создавать математические модели, обеспечивающие более высокое качество идентификации. Кроме того, современная вычислительная техника позволяет обрабатывать огромные массивы экспериментальных данных в различных областях (в медицине, биологии, химии). Для обозначения перечисленных задач был введен термин «Математическая диагностика», определяющий, таким образом, целое направление в теории оптимизации.

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

Ваясно понимать, что упомянутые ранее статистический подход и нестатистические подходы, основанные на методах математического программирования, не являются взаимоисключающими. Так, например, известно, что статистический и оптимизационный методы удачно дополняют друг друга и позволяют производить более подробный анализ существующих баз экспериментальных данных. Настоящая работа находится в русле оптимизационного подхода к решению задач идентификации и диагностики, который в настоящее время развивается, в частности, в работах Ю. Г. Евтушенко, A.M. Рубинова и их последователей [61, 62, 63, 90, 72].

Как было отмечено ранее, многие задачи математической диагностики сводятся к отделению двух или более множеств, принадлежащих многомерному пространству. Для этого необходимо сформулировать определенное правило (называемое также классификатором, правилом идентификации или решающим правилом), согласно которому точки многомерного пространства будут отнесены к тому или иному множеству. Одной из основных проблем, возникающих при идентификации, является оценка эффективности построенного решающего правила (РП), т. е. возникает необходимость построить некоторый критерий, при помощи которого можно было бы сравнивать различные РП между собой, выбирая лучшее из них. В качестве подобного критерия обычно используют так называемые «натуральные функционалы», определяющие количество неверно идентифицированных точек. В этом случае, чем меньше значение функционала, тем лучше рассматриваемое РП. Поскольку использование натуральных функционалов сопряжено с различного рода трудностями, связанными с их существенной разрывностью, то вводят так называемые «суррогатные функционалы», аппроксимирующие натуральные функционалы. Использование нелинейных и даже негладких суррогатных функционалов может повысить качество идентификации. Гладкие суррогатные функционалы, в свою очередь, представляют больший практический интерес, так как они могут послужить основой для создания алгоритмов построения РП [24, 26, 28, 33]. Программная реализация таких алгоритмов, в конечном итоге, позволит создать программное обеспечение, при помощи которого можно будет решать задачи идентификации в каждом отдельном случае.

2. Постановка задачи.

2.1 Постановка задачи идентификации точек двух множеств в многомерном пространстве.

Пусть в пространстве М71 заданы два конечных множества точек, А и В:

Задача идентификации заключается в построении решающего правила (РП) — определенного закона, по которому каждая точка пространства М&trade-, принадлежащая объединению множеств, А и В, классифицируется как точка, принадлежащая одному из этих множеств.

Рассмотрим два возможных варианта расположения точек множеств, А и В в пространстве:

1. В случае, если множества, А и В или их выпуклые оболочки (когда множества не являются выпуклыми) не пересекаются, они могут быть идентифицированы при помощи линейной функции. Это следует из Теоремы отделимости [18, 52], согласно которой существует вектор I <5 К. п и число (I 6 К., такие, что выполняются следующие неравенства:

А = аг | г е / = 1: М, ^ е м} в = {ь,-1 з е 3 = 1: N2, N2 е м} ж, I) + й > 0 для любых х € А, (х, I) + (I < 0 для любых х е В.

1) (2).

Введем новые обозначения:

1 = &-1], 1е Мп+1, г (х, 1} = (х, I) + ±.

Тогда, в силу (1) — (2), для любой точки с? С = A[JB РП может быть выражено следующим образом: если г (с, Г) > 0, то считаем, что с е А, (3) если г (с, I) < 0, то считаем, что с € В. (4).

Для того, чтобы найти вектор I, определяющий РП (3) — (4), достаточно найти расстояние между множествами, А и В, а именно найти.

Q (AB)dU min ||а — Ь||2 = ||а* — 6*||2. а€Л, b€B.

Так как, А f| В = 0, то д (А, В) > 0. Положим г= ащ-Ь* ||6Ц2−11аЦ2 а* — &*||' 2||а* — 6*||.

Согласно необходимому условию минимума выполняются следующие неравенства: г (с, Г) = (cj*) + d*>ha*-b'r\ > 0 Vc е А, (5).

Zi.

Г (с, Г) = (cj*) + if < -ha*-b*\ < 0 Усе В. (6) j.

Таким образом, множества, А и В могут быть точно разделены при помощи (п-1)-мерной гиперплоскости, задаваемой уравнением г (с, Г)= 0. (7).

2. В случае, если множества, А и В имеют общие точки, т. е. соА f) соВ ф 0, полное отделение этих множеств с помощью какой-либо (п-1)-мерной гиперплоскости является невозможным. Рассмотрим РП следующего вида: если г (с, Т) > 0, то считаем, что с G А, (8) если г (с, I) < 0, то считаем, что с? В.

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

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

2.2 Постановка задачи идентификации точек трех множеств в многомерном пространстве.

Пусть в пространстве Rn заданы три конечных множества точек А, В и.

С:

А= [щ | г е 1= 1: Nh М € n}, B={bjjeJ=l:N2, N2e n}, (9).

С — keK~l-. TVs, N3e N} .

Рассмотрим задачу разделения множеств (9) при помощи двух параллельных гиперплоскостей, задаваемых уравнениями г (х, h) = 0 и г (ж, 12) = 0, где г (ж, k) = (х, I) + df,.

Ti = [di, l) — Те Rn+1, l, x? WLn, di e R, \l\ = M = 1: 2. def.

Для того, чтобы идентифицировать каждую точку у 6 Y — AJBJC, рассмотрим РП следующего вида: если г (у, li) < 0, то считаем, что у € А, если г (у, 1) > 0, г (г/, 12) < 0, то считаем, что у? В, (10) если г (у, 12) > 0, то считаем, что у € С.

Классификация точек при помощи РП (10), очевидно, буде иметь некоторую неточность. В связи с этим возникает проблема нахождения наилучшей, в том или ином смысле, пары разделяющих гиперплоскостей, а точнее, оптимального набора параметров I — [d, d2, l] G Rn+2, который однозначно их определяет. Исходя из того, какое РП принято считать более эффективным, строится оценочный функционал, который следует минимизировать с целью нахождения оптимального РП.

3. Цель работы.

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

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

4. Методы исследований.

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

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

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

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

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

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

• Разработано программное обеспечение, реализующее предложенные методы идентификации.

• Проведено тестирование указанного программного обеспечения на базе данных Wisconsin Prognostic Breast Cancer Chemotherapy Database (база данных пациентов с раком молочной железы, сокращенно РМЖ), а также сравнение полученных данных с известными статистическими медицинскими показателями эффективности применения метода дополнительной химиотерапии при лечении РМЖ.

6. Практическая и теоретическая значимость.

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

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

7. Апробация работы.

Основные результаты работы докладывались и обсуждались на XXXVI, XXXVII и XXXIX международных научных конференциях аспирантов и студентов <Процессы управления и устойчивость> факультета Прикладной математики и процессов управления (г. Санкт-Петербург, 2005, 2006, 2008), Международной математической конференции <Еругинские чтения — ХХ> (г. Могилев, 2005), Международной математической конференции <Математические методы в технике и технологиях> (г. Воронеж, 2006), а также на семинарах кафедры математической теории моделирования систем управления СПбГУ.

8. Связь с научными программами.

Работа частично проводилась в рамках выполнения проекта Российского фонда фундаментальных исследований (код проекта РФФИ № 06−01−276).

9. Публикации.

По результатам проведенных исследований опубликовано двенадцать печатных работ, в том числе 2 из списка ВАК. Перечень работ приведен в Заключении на стр.77).

10. Структура работы.

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

Заключение

.

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

Одним из основных результатов работы является создание новых алгоритмов построения оптимального (в указанном смысле) РП и математического программного обеспечения, реализующего данные алгоритмы. Решение задачи идентификации двух п — мерных множеств строится при помощи (п-1) -мерной гиперплоскости, трех п — мерных множеств — при помощи двух параллельных (п-1) — мерных гиперплоскостей. С целью оценки эффективности построенных решений вводятся два новых суррогатных оценочных функционала: значение одного из них есть сумма расстояний от неверно идентифицированных точек до разделяющей гиперплоскости, а значение другогополовина суммы квадратов этих расстояний. Кроме того, конечным результатом исследований стало проведение численных экспериментов на базе данных Wisconsin Prognostic Breast Cancer Chemotherapy Database (база данных пациентов с РМЖ), а также сравнение полученных данных с известными статистическими медицинскими показателями эффективности применения метода дополнительной химиотерапии при лечении РМЖ.

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

ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ.

Публикации в изданиях, рекомендуемых ВАК.

1. Зубова О. А. Математические модели систем управления// Научнотехнические ведомости СПбГПУ. СПб.: Изд-во СПбГПУ, Т. 1, № 6, 2006. С. 7−9.

2. Зубова O.A. Идентификация нескольких множеств в многомерном пространстве// Вестник СПбГУ. СПб.: Изд-во СПбГУ, Сер. 10, вып. 4, 2007. С. 17−22.

Публикации в других изданиях.

3. Зубова O.A. Задача наблюдательного обучения// Процессы управления и устойчивость: Труды XXXV научной конференции аспирантов и студентов — СПб.: Изд-во СПбГУ, 2004. С. 312−317.

4. Зубова O.A. Один алгоритм решения задачи идентификации// Процессы управления и устойчивость: Труды XXXVI межвузовской научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, В. Н. Старкова, — СПб.: Изд-во СПбГУ, 2005. С. 41−46.

5. Зубова O.A. О задаче идентификации точек многомерного пространства// Тезисы докладов международной математической конференции <Еругипские чтения — ХХ>, Могилев, 2005, с. 119−120.

6. Зубова O.A. О проблеме сглаживания в задачах математической диагностики// Тезисы докладов международной конференции <Процессы управления и устойчивость>- СПб.: Изд-во СПбГУ, 2005. С. 1665.

7. Зубова O.A. Задача идентификации нескольких множеств// Процессы управления и устойчивость: Труды XXXVII международной научной конференции аспирантов и студентов / Под ред. A.B. Платонова, Н. В. Смирнова.- СПб.: Изд-во СПбГУ, 2006. С. 34−38.

8. Зубова O.A. К проблеме сглаживания в задачах математической диагностики// Сборник трудов XIX международной математической конференции <Математические методы в технике и технологиях>.- Воронеж: Изд-во ВГТА, Т.1, 2006. С. 28.

9. Зубова O.A. Решение задачи идентификации// Труды средневолжского математического общества — Саранск, Т.1, № 2, 2006. С. 230−232.

10. Зубова O.A. Определение функционала// Труды Института системного анализа РАН. Динамика неоднородных систем / Под ред. Ю.С. Попкова-М.: Изд-во КомКнига, Вып. 10(2), 2006. С. 199−202.

И. Зубова O.A. Применение методов негладкого анализа в задачах математической диагностики// Процессы управления и устойчивость: Труды 39-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2008. С. 29−32.

12. Зубова O.A. Проблемы диагностики// Труды конгресса-2008 <Фундаментальные проблемы естествознания и техники>. — СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2008. С. 739.