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

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

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

ГРИГОРЬЕВА Ксения Владимировна

АППРОКСИМАЦИЯ КРИТЕРИАЛЬНОГО ФУНКЦИОНАЛА В ЗАДАЧАХ МАТЕМАТИЧЕСКОЙ ДИАГНОСТИКИ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

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

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

Научный руководитель: доктор физико-математических наук,

профессор Демьянов Владимир Федорович

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

профессор Демьянович Юрий Казимирович

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

Ведущая организация: Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится « » 2006 г. в К ч. 0О мин. на за-

седании диссертационного совета К-212.232.07 по защитам диссертаций на соискание ученой степени кандидата наук при Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, Средний пр. В.О., Д.41/43, ауд.

С диссертацией можно ознакомиться в научной библиотеке им. А. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

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

2006 г.

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

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

Общая характеристика работы

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

Существуют различные подходы и теории для исследования вышеупомянутых задач: метод машинного обучения (60-е - 80-е годы XX века), метод опорных векторов, кластерный анализ, статистический подход, метод построения ядра, оптимизационные методы, включающие методы линейного дискриминантного анализа (ЛДА), разработанного Р. Фишером, основанного на линейном и квадратичном программировании, дискретные методы.

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

Большой вклад в развитие методов решения задач диагностики, идентификации и распознавания образов внесли многие отечественные и зарубежные ученые: Н.М. Амосов, В.Н. Вапник, И.М. Гельфанд, Б.А. Головкин, Ю.И. Журавлев, Н.Г. Загоруйко, Б.Н. Козинец, А.Н. Колмогоров, A.A. Ляпунов, O.JI. Мангасарян, М.Н. Мурти, Ю.И. Неймарк, A.A.

Первозванский, В.Ю. Урбах, Р. Фишер, В.Н. Фомин, П. Хансен, А.Я.

|

Червоненкис, Б. Шелкопф, В.А. Якубович и другие.

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

негладком анализе и недифференцируемой оптимизации обеспечили новый более мощный и эффективный аппарат, с помощью которого теперь можно построить математическую модель, лучше описывающую рассматриваемую задачу. Использование нелинейных и даже негладких критериев идентификации может улучшить качество идентификации. Вопросами негладкого анализа занимались, в частности, Ф.П. Васильев, В.В. Гороховик, В.Ф. Демьянов, И.И. Еремин, Ю.М. Ермольев, А.Д. Иоффе, Ж.-Б. Ириа-Уррути, Ф. Кларк, С.С. Кутателадзе, В.Н. Малоземов, Л.И. Минченко, Б.Т. Поляк, JI.H. Полякова, Б.Н. Пшеничный, Р.Т. Рокафеллар, A.M. Рубинов, В.М. Тихомиров, В.В. Федоров, Н.З. Шор. Современный уровень развития вычислительной техники позволяет реализовать многие методы и алгоритмы, которые ранее невозможно было использовать.

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

Так как большинство "суррогатных" функционалов - негладкие, то ЛДА должен быть расширен до негладкого дискриминантного анализа (НДА), в рамках которого для решения практической задачи идентификации требуется:

1) построить правило идентификации;

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

3) выбрать соответствующую модель (суррогатный функционал);

4) использовать существующие или создать новые алгоритмы и программное обеспечение, чтобы получить численные результаты.

Постановка задачи. Задача идентификации может быть сформулирована следующим образом. Пусть в пространстве Л" заданы два множества точек А и В:

Л = { а( е Я" | / е / }; / = 1:ЛГ,; В = ей" |уе J }; J = l:N2.

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

Пусть ceA<jB. Введем множество L{y,d)={xeR"\r(x,y,d) = o}, где r(x,y,d)=<x,y>+d, х,у е R",d еЛ1. Множество L(y,d) является гиперплоскостью. При этом на переменную у накладывается ограничение = 1. Тогда r(x, y,d) является (с точностью до знака) расстоянием от точки х до гиперплоскости L[y, d).

Будем использовать следующее правило идентификации: если r(c,y,d)< 0, то считаем, что се А; если r(c,у,d)> 0, то считаем, что с е В.

В случае r(c,y,d) = 0 точка с считается неидентифицируемой с помощью функции r(x,y,d) (см. рис. 1).

Построим разбиение индексных множеств / и J: / = /tu/0u/., J - Jt иУ0 иУ, где

1+ =I+{y,d)={ieI\r(aity,d)>Q}\ Л = J+iy,d)= {У е J\-r{b},y,d)> 0 }; J0=I0(y,d)={ieI\r(a„y,d) = o}-, J0=J0{y,d)={jeJ\-r[bj,y,d)=Q}, /_ = /.(у,d) = {/ 6 /| г (а,,.у,с/)<О }; J -J_(y,d)= {jeJ | -г{bj,у,d)< 0 }.

Здесь:

I^{y,d) и J^(y,d) — индексные множества, состоящие из номеров точек множеств А и В, соответственно, которые ошибочно идентифицированы с помощью функции r(x,y,d)-,

I0(y,d) и J^{y,d) — индексные множества, состоящие из номеров точек множеств А и В, соответственно, которые неидентифицируемы с помощью функции r{x,y,d);

I_(y,d) и J_(y,d) — индексные множества, состоящие из номеров точек множеств А к В, соответственно, которые правильно идентифицированы с помощью функции г(x,y,d}.

Воспользуемся следующим обозначением: если D — конечное множество некоторого пространства, то |Z)| = card D - количество элементов множества D.

Положим = + - количество ошибочно

идентифицируемых точек обоих множеств А и В. Тогда множество + + + - количество неверно

идентифицируемых точек множеств А к В (неверно идентифицируемые точки - это объединение ошибочно идентифицируемых и неидентифицируемых точек).

Определение 1. Будем называть каждую из введенных функций с1) и 0{у,<£)~ "натуральным" функционалом.

рис. I

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

п = {Ы)1ЫН !}<=*"'-

Поскольку функционал 0(у, с1) разрывен, то применение стандартных методов, разработанных для минимизации непрерывных функций, невозможно. Поэтому будем аппроксимировать "натуральный" функционал 0(у, сГ) так называемым "суррогатным" функционалом.

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

»k r({a"y't £1 [ \r{al,y,d]^ +1

+ У maX'jo.T-T-TT

jtj [ \r{bj,y,d^

+ e

max-j 0,

r(a„y,d)

+ 2

jSJ

max-^ 0,

-r{bJty,d) r{bpy,d

+ £

При е->0, е>0, оба функционала являются аппроксимирующими натуральный функционал 0(у, с/), т.е. Рл(у,Л)—V I е 1:2.

Иначе говоря, значения функционалов FH{y,d) и Flt(y,d) представляют собой (с некоторой точностью) количество точек, для которых выполняются условия r(any,d)> 0 и -r[bjyy,d)> 0, так как ненулевой вклад в Fu(y,d) и

Fu(y,d) дают те точки из множеств А и В, которые неправильно идентифицированы. Оба эти функционала непрерывны, причем FH(y,d) является субдифференцируемым, a Fu (у, d) — даже непрерывно-дифференцируемым. Задача состоит в том, чтобы минимизировать оба суррогатных функционала, а также натуральный функционал Q{y,d) на множестве fl = {(y,i/)| ||><||= l}c: Ял+| с помощью построения различных вариантов направлений наискорейшего спуска и сравнить эффективность использования их на практике.

Цель работы. Целью диссертационной работы является изучение свойств функционалов Fuiy,d) и Fu{y,d), разработка численных методов для минимизации этих функционалов, создание программного обеспечения, проведение экспериментов на конкретных базах данных, сравнение полученных результатов с исследованиями других авторов.

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

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

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

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

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

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

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

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

Апробация. Результаты работы докладывались и обсуждались на семинарах лаборатории биомедицинской информатики Санкт-Петербургского института информатики и автоматизации РАН, кафедр математической теории моделирования систем управления факультета прикладной математики — процессов управления и параллельных алгоритмов математико-механического факультета Санкт-Петербургского

государственного университета, а также на конференциях:

1. XXXIV научная конференция аспирантов и студентов "Процессы управления и устойчивость" 21-24 апреля 2003 г., место проведения - Санкт-Петербургский государственный университет, СПб;

2. 56-я Международная научно-техническая конференция молодых ученых: "Актуальные проблемы современного строительства" 28-30 октября 2003 г., место проведения - Санкт-Петербургский государственный архитектурно-строительный университет, СПб;

3. Всероссийская научно-техническая конференция "Искусственный интеллект в XXI веке" 27 ноября 2003 г., место проведения - Пенза, Приволжский Дом знаний, 2003;

4. 61-я научная конференция профессоров, преподавателей, научных работников, инженеров и аспирантов Санкт-Петербургского государственного архитектурно-строительного университета 7-9 февраля 2004 г., место проведения - Санкт-Петербургский государственный архитектурно-строительный университет, СПб;

5. XXXV научная конференция аспирантов и студентов "Процессы управления и устойчивость" 14-16 апреля 2004 г., место проведения - Санкт-Петербургский государственный университет, СПб;

6. 63-я научная конференция профессоров, преподавателей, научных работников, инженеров и аспирантов Санкт-Петербургского государственного архитектурно-строительного университета 7-9 февраля 2006 г., место проведения - Санкт-Петербургский государственный архитектурно-строительный университет, СПб;

7. XXXVII международная научная конференция аспирантов и студентов "Процессы управления и устойчивость" 11-13 апреля 2006 г., место проведения — Санкт-Петербургский государственный университет, СПб.

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

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

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

Глава I посвящена изложению основ теории, используемой для исследования свойств рассматриваемых в данной работе функционалов. В § 1.1 приводится постановка задачи, в §§ 1.2 - 1.4 проводится исследование свойств функционалов, предлагается методика решения задачи. Результаты формулируются в виде лемм и утверждений.

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

Сформулируем основные результаты, полученные в главе 1.

В §§ 1.2 - 1.3 (лемма 1.2.1, утверждение 1.2.2, лемма 1.3.2) устанавливается, что функционал F[t(y,d) является

1) субдифференцируемым и его субдифференциал имеет вид

ш. (r(a„y,d) + б У {- r^b^y.dj+sf

1Е/„ l Е J j*J, l Е

2) липшицевым и его константа Липшица

ici L £ J (ei [ E J

где

A, = max|/f|; A, = max|/,]; В, = пмх(|/,| + e) Bj= max(/y| + e); f, = f(.ai,y,d)=<al,y>+d, at,y e R",d e R1; fj=f{bJ,y,d)=<bJ,y>+d, bj,y e R" ,d e /?';

3) непрерывно гиподифференцируемым и его гиподифференциал

-тах^О.^А.О

V I Ф2<

' , ф|,'1ф|.1 | Ф» Ч>2, Ф2, Ф2<

- тах-(

ф2< Ф2, ф2,

М.0. ,0

ФгЛ )

■Л^а, » 2

Ф* Ф21

-тах<{ 0,-^,0,,, О Ч>2/

У?; ) Чу!^,,,! ,

+ - тах<! 0,-^- кОл,О

I V»,

VI

Чу1Уц I | К Ч>2,

I У»)

где

ф„ =г(апу,Л); фг,=|г(а,,.М)|+е; ¡ = 1:Ы,;

Основной результат, полученный в § 1.4 (лемма 1.4.1) для функционала состоит в том, что функционал Р2с(у,с1) является непрерывно-дифференцируемым и его градиент равен

то- г' (л -л ■УСу , у г{ь1,у,а\ь)У\)

Задача минимизации функционалов Р1с(у,с/) и которой

посвящена данная работа, представляет собой задачу условной минимизации, которую можно свести к задаче безусловной минимизации. Один из способов состоит в использовании метода точных штрафных функций, заключающегося в том, что при некоторых предположениях, которые формулируются в пункте 2 § 1.2, существует такое X' > 0, что при любом Х>Х' задача минимизации функционала на множестве

Г2 = И"*' |ф(у,^)=|||,)'|| -1| = о} эквивалентна задаче минимизации

функционала Ф(у, й?) = Р)Т_(}',с1) + X - ф(_у,(¡) (/ = 1:2) на всем пространстве Я"*'. Используя установленные свойства функционалов /г1си Ри{у,Ы), в главе 1 обосновывается такой переход к эквивалентной задаче минимизации функционалов ФдСу.^). у = 1:2, на всем пространстве (теорема 1.2.2), а затем устанавливается субдифференцируемость функционалов Фд(у,г/), / =1:2, на множестве С2 (из лемм 1.2.1 и 1.2.3). При этом субдифференциал имеет, соответственно, вид

, . - Е/ ¿И у +

М = VF1.G',rf) + X ■ со{(у,0); (- у,0)}.

Для того, чтобы точка являлась точкой минимума

функционала ФА на Л"+|, необходимо выполнение условия е2Фд(р*), у' = 1:2. Точка у', удовлетворяющая необходимому условию минимума 0„„, е5Фд(у*) (/ = 1:2), называется /'«/-стационарной точкой функционала Фд на Л"*1. Из необходимого условия минимума и из вышеприведенных формул для субдифференциалов функционалов Фд вытекает необходимое условие минимума для функционала на

множестве О (лемма 1.2.4) в виде:

„ е-а. V-" ъ-Ь. Я": 0 еУ--;—^-Г-Ут—7-;-+

где р е [- X, X],

а для функционала ^(у,^) на множестве О (лемма 1.4.2) в виде:

/Г: £ ^./.¿'Ь КУ/^'К +~./ = 0п.

где р = X].

2-е

В случае, если Ia,J0=G (следствие 1.2.1), из необходимого условия минимума для функционала Ри{у,с1) следует, что в Л1 суммы квадратов обратных расстояний (с точностью до е) ошибочно определенных точек множеств А и В совпадают, а в Я", что вектор

е • а, ж-, £ • Ь

— — У —,- ' .-параллелен вектору у

££(г{а„у ,с*') + е)2 ££ (- г (б,,/ )+ г?

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

1) Релаксационный метод проектирования, построенный для суррогатных функционалов Ри{у,с1) и

2) Сходящийся к стационарной точке метод проектирования, построенный для суррогатного функционала

3) Смешанный метод проектирования, построенный с использованием обоих суррогатных функционалов Ри(у,с1) и Ги{у,с1).

Эти методы положены в основу решения задачи минимизации натурального функционала на множестве С2={(у,£/)| || _у||= 1}с Л"*' и

заключаются в следующем:

1) Для релаксационного метода, построенного для суррогатных функционалов Ри{у,Ы) и

1. Выберем произвольно уа =(уа,с!0)е П = {р е |||у|- 1| = о}. Пусть уже найдено у1 = (Ук>^к). Построим ЙФЛ0>*), у=1:2, и найдем с помощью метода условного градиента (см. § 2.2) решение задачи

Ш1П ,4м2 =4IV,

«8®иСА)2 2

где V, »„6*", ей'

2. Если |у4|2=0, то выполнено необходимое условие минимума функции Ф х на К"*', точка у1 является стационарной, и процесс

прекращается. Если |уа|2>0, то направление g^=~^iгí]¡ является

1К1!

направлением наискорейшего спуска функционала Ф Найдем

Ш1П О

а20

¿-"'".г \ = £

>2

VIIУ-а-П. II Н-У-а-П,

*2

Ну-а, -у,,]

3. Положим Ук+\= Уь ~ ак и отметим, что

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

2) Для сходящегося к стационарной точке метода, построенного для суррогатного функционала

1. Выберем произвольно у0 = = {_ре ||у|- 1| = Пусть уже найдено ук = {ук,<Лк). Построим ^^(Ук) и решим задачу

+ + где У,=(у.,0), Ук*Я"л (см. §

2.4). Необходимое условие минимума выполняется в точке

Ц* У*)-

2. Если + = то выполнено необходимое условие минимума функционала Ри на О, точка ук является стационарной, и процесс прекращается. В противном случае найдем

.У + а-Я*, с1 + 1

гшп£?

где Я, gk=(gt^,gl2)\ ёкг еД1.

3. Положим Ук*\~Ук+ак" ёк- Отметим, что

Отметим, что сходимость данного метода к стационарной точке следует из сходимости градиентных методов.

3) Для смешанного метода проектирования, построенного с использованием обоих суррогатных функционалов и Ри{у,с1):

1. В ыбирается произвольно у0 = (у0, с/0) е О = {у е Я 1 -1| = о} Пусть уже построено ук = (ук,с1к}. Находим направления наискорейшего спуска функционалов Ф,х и Фп в точке ук. Пусть это будут направления у^ и у^ .соответственно.

2. Найдем

гшпб^ + а• у«)= ё(ук + а, -V«) тт&{ук + а • Г<2))= + а2 • у<2>)

3. Если +a/-v,(l>)<2(y<+«2' pf2))' то положим yktl -ук +а, Если + «I • vA(l))s Q{pt + а2' то положим ykti-ук + ce2vj;2\ Если

нахождение обоих направлений v^ и v,'2' затруднено, то можно использовать только одно из них.

На основании всех проведенных теоретических исследований построено программное обеспечение решения задачи минимизации. Программы были написаны на языке Delphi, вычисления проводились на PC с CPU Intel Celeron 1,70 GHz, 256 MB of RAM.

Глава 3 состоит из двух частей. Основой первой части главы 3 являются результаты численных экспериментов, которые были получены при последовательном проведении минимизации суррогатных функционалов Fuiy'd) и !72i{y,d) и натурального функционала Q{y,d) на множестве П = {(у, d) | || у ||= 1} с: Л"+1 на примере шести баз данных:

1. Желчно-каменная болезнь (сокращенная и полная базы) - база предоставлена Кафедрой общей терапии Военно-медицинской академии им. С.М. Кирова (§ 3.2);

2. Австралийский кредит (§ 3.3);

3. Heart Disease (§ 3.4);

. 4. Висконсинская база данных рака молочной железы (§ 3.5);

5. База данных по инфаркту (§ 3.6);

6. База данных по онкологии (§ 3.7).

Для отбора наиболее информативных признаков используются результаты ранжирования параметров, полученные А.М.Багировым (Балларатский Университет, Австралия) и А.В.Кокориной (СПбГУ, Россия).

Проведенные эксперименты показали, что функционалы Fu(y,d) и F^(y,d) могут эффективно использоваться в качестве суррогатных

функционалов. В силу

многоэкстремальности этих функционалов их

применение рекомендуется для уточнения точки минимума (полученной с

помощью других суррогатных функционалов, например, методом опорных векторов).

Вторая часть главы 3 представлена исследованием онкологической базы данных О.Л. Мангасаряна разработанными в данной работе методами. В этой части на основании полученных результатов была поставлена и решена задача определения эффективности прогнозирования лечения химиотерапией онкологических заболеваний (§ 3.7).

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

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

1. Введены два новых суррогатных функционала, установлена субдифференцируемость функционала Ри{у,с1) и гладкость функционала

РиМ-

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

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

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

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

Публикации по теме диссертации

1. Григорьева К.В. Метод проектирования в одной задаче идентификации. Процессы управления и устойчивость. Труды XXXIV научной конференции аспирантов и студентов. — СПб: Изд-во С.-Петерб. Ун-та, 2003, с.268-271.

2. Григорьева К.В. Задача идентификации точек двух конечных множеств. Сборник материалов Всероссийской научно-технической конференции "Искусственный интеллект в XXI веке". Пенза, Приволжский Дом знаний, 2003, стр.74-77.

3. Григорьева К.В. Метод проектирования в одной задаче идентификации. Актуальные проблемы современного строительства. 56-я Международная научно-техническая конференция молодых ученых. Сборник докладов. СПб, С.-Петерб. Гос. Архитектурно-Строительный Университет, 2004, с.48-50.

4. Григорьева К.В. Идентификация множеств с помощью негладкой модели. Процессы управления и устойчивость. Труды XXXV научной конференции аспирантов и студентов. - СПб: Изд-во С.-Петерб. Ун-та, 2004, с.294-296.

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 04.05.06 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л. 1. Тираж 100 экз., Заказ № 313/с 198504, СПб, Ст. Петергоф, ул. Ульяновская, д. 3, тел. 428-43-00.

Оглавление.

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

Введение.

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

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

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

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

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

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

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

Апробация.11

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

Содержание работы.13'

Основные результаты, выносимые на защиту.20

Заключение

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

Исследование предложенных в данной работе баз данных показало, что существенной разницы в процентах отделимости не получилось (на примерах ЖКБ и HD в процентном отношении улучшение наблюдалось не более, чем на 3%), что свидетельствует о работоспособности алгоритмов минимизации функционалов Qi и Q2(1) при любом достаточно малом 8.

Сравнивая работу функционалов Qb Qi(I), Q/2) при е = 0.001 для Висконсинской базы данных, сформированной из параметров по результатам ранжирования Кокориной А.В., можно констатировать, что при одной комбинации параметров дает лучший результат один алгоритм, при другой -другой. В некоторых случаях получились одинаковые результаты. Поэтому, однозначно утверждать, что какой-либо из функционалов и методов построения наискорейшего спуска предпочтительнее другого, невозможно.

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

Использование напрямую суррогатных функционалов (базы данных -инфаркт) позволило наблюдать следующие моменты:

1. Отрицательное влияние точек, попавших на гиперплоскость.

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

На примере базы данных РМЖ задача диагностирования пациентов была расширена до задачи прогнозирования эффективности применения лечения и на основании построенной методики была построена следующая оценка эффективности прогнозирования лечения онкологии химиотерапией: 70.49% - успех для множества А - "успешные" из 140 пациентов в случае проведения химиотерапии; и 73.42% - успех для множества В -"неуспешные" из 140 пациентов в случае отсутствия химиотерапии.

На основании полученных результатов исследования сформулируем основные результаты диссертационной работы:

1. Введены два новых суррогатных функционала, изучены их свойства, установлена субдифференцируемость функционала Fle(y,d) и гладкость функционала F2e(y,d).

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

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

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

1. Амосов Н.М., Зайцев Н.Г., Мельников А.А. и др. Медицинская информационная система. - Киев: Наукова думка, 1971.

2. Бейли Н. Математика в биологии и медицине: Пер. с англ. М.: Мир, 1970.

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

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

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

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

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

8. Васильев Ф.П., Численные методы решения экстремальных задач, М., "Наука", 1980.

9. Гельфанд И.М., Пятецкий-Шапиро И.И., Федоров Ю.Г. Отыскание структуры кристаллов с помощью метода нелокального поиска // ДАН СССР, т. 152, № 5,1963, с. 1045-1048.

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

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

12. Григорьева К.В. Метод проектирования в одной задаче идентификации. Процессы управления и устойчивость. Труды XXXIV научной конференции аспирантов и студентов. СПб: Изд-во С.-Петерб. Ун-та, 2003, с.268-271.

13. Григорьева К.В. Задача идентификации точек двух конечных множеств. Сборник материалов Всероссийской научно-технической конференции "Искусственный интеллект в XXI веке". Пенза, Приволжский Дом знаний, 2003, стр.74-77.

14. Григорьева К.В. Метод проектирования в одной задаче идентификации. Актуальные проблемы современного строительства. 56-я Международная научно-техническая конференция молодых ученых. Сборник докладов. СПб, СПбГАСУ, 2004, с.48-50.

15. Григорьева К.В. Идентификация множеств с помощью негладкой модели. Процессы управления и устойчивость. Труды XXXV научной конференции аспирантов и студентов. СПб: Изд-во С.-Петерб. Ун-та, 2004, с.294-296.

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

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

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

19. Демьянов В.Ф. Условия экстремума и вариационные задачи. СПб.: НИИ Химии СПбГУ, 2000, 136 с.

20. Демьянов В.Ф. Рубинов A.M. Основы негладкого анализа и квазидифференциальное исчисление.-М.: Наука, 1990.-432 с.

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

22. Дюк В.А. Методология поиска логических закономерностей в предметной области с нечеткой системологией. Автореферат диссертации насоискание ученой степени д.т.н. СПб, СПбГУ, 2005.

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

24. Журавлев Ю.И., Дмитриев А.Н., Кренделев Ф.Н. О математических принципах классификации предметов и явлений. Дискретный анализ. Сб. трудов ИМ СО АН СССР. Новосибирск, № 7,1966.

25. Загоруйко Н.Г. Методы распознавания и их применения. М.: Советское радио, 1972.

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

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

28. Кокорина А.В. Оптимизационный подход в задачах математической диагностики. Диссертация на соискание ученой степени к.ф.-м.н. СПб, СПбГУ, 2004.

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

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

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

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

33. Поляк Б.Т. Методы оптимизации. М.: Наука, 1981. - 384 с.

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

35. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975. - 320 с.

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

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

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

39. Anderberg M.R. Cluster Analysis for Applications. Academic Press, 1973.

40. Babu G.P. and Murty 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.

41. Bagirov A.M., Rubinov A.M. and Yearwood J. A global optimization approach to classification. Optimization and Engineering 3, 2002, pp. 129155.

42. Bennett K.P. and Mangasarian O.L. Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods and Software 1, 1992, pp. 23-34.

43. 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.

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

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

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

47. De Coste D. and Scholkopf B. Training invariant support vector machines. Machine Learning 46,2002, pp. 161-190.

48. V.F. Demyanov. Mathematical diagnostics via nonsmooth analysis. OMS, vol. 20, № 2-3,2005, pp.197-218.

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

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

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

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

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

54. Lee, Y.-J. and Mangasarian, O.L. SSVM: a smooth support vector machine for classification. Computational Optimization and Applications, 2001,20(1). 5-22.

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

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

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

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

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

60. 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.

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

62. Quinlan J.R. Programs for Machine Learning. Morgan Kaufmann, San Mateo, 1993.

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

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