Содержание к диссертации
Введение
Глава 1. Задача идентификации. Основы теории 21
1.1. Постановка задачи 21
1.2. Исследование свойств функционала Fu (у) 24
1.3. Вычисление кодифференциала функционала Fle (у) 40
1.4. Исследование свойств функционала F2s (у) 50
Глава 2. Численные методы решения задачи разделения объектов 56
2.1. Введение 56
2.2. Алгоритм метода условного градиента для решения вспомогательной задачи 58
2.3. Метод проектирования для минимизации функционала Fu(y) на Q 64
2.4. Метод проектирования для минимизации функционала F2e (у) на множестве О , 65
2.5. Построение направления наискорейшего спуска смешанным методом проектирования минимизации функционалов Fu (у) и F2c (у) на множестве Q 67
2.6. Применение суррогатных функционалов для минимизации натурального функционала Q(y) на множестве Q 68
Глава 3. Результаты применения метода проектирования на конкретных базах данных 71
3.1 Введение 71
Часть 1. Сравнительный анализ методов проектирования 76
3.2 Прогнозирование эффективности лечения желчнокаменной болезни 76
3.3 База данных Австралийский кредит (Australian credit) 85
3.4 База данных Heart disease (порок сердца) 88
3.5 Висконсинская база данных рака груди 94
3.6 База данных по инфаркту (используемая Дюком В.А.) 103
Часть 2. Методика прогнозирования эффективности лечения
онкологических заболеваний 113
3.7 База данных по онкологии (Мангасарян) 113
Заключение 149
Приложение 151
Литература
- Исследование свойств функционала Fu (у)
- Исследование свойств функционала F2s (у)
- Метод проектирования для минимизации функционала F2e (у) на множестве О
- База данных Австралийский кредит (Australian credit)
Введение к работе
Актуальность темы. Данная работа относится к достаточно разработанному направлению в прикладной математике - математической диагностике (МД), которая занимается проблемами идентификации, возникающими в различных практических областях: это анализ экспериментальных данных, задачи классификации, распознавания образов, задачи медицинской и технической диагностики, задачи назначения и распределения. Многие из этих задач могут быть описаны математическими моделями, в которых необходимо идентифицировать точки двух или более множеств.
Существуют различные подходы и теории для исследования вышеупомянутых задач: метод машинного обучения (60-е - 80-е годы XX века) [38, 60, 62, 64], метод опорных векторов [6, 45, 46, 48, 56-59, 67], кластерный анализ [39, 44, 52, 54, 56, 61, 65], статистический подход [1-5, 21, 23, 29-30, 51, 63, 67], метод построения ядра [47, 66], оптимизационные методы [9,24, 27, 31,41], включающие методы линейного дискриминантного анализа (ЛДА), разработанного Р. Фишером, основанного на линейном и квадратичном программировании [11, 37, 43, 51, 53, 57, 58, 59], дискретные методы [24, 25].
К сожалению, единого подхода или универсального метода, пригодного для всех задач, не существует. Поэтому разработка новых методов для решения конкретных классов задач, остается актуальной.
Большой вклад в развитие методов решения задач диагностики, идентификации и распознавания образов внесли многие отечественные и зарубежные ученые: Н.М. Амосов, В.Н. Вапник, И.М. Гельфанд, Б.А. Головкин, Ю.И. Журавлев, Н.Г. Загоруйко, Б.Н. Козинец, А.Н. Колмогоров, А.А. Ляпунов, О.Л. Мангасарян, М.Н. Мурти, Ю.И. Неймарк, А.А. Первозванский, В.Ю. Урбах, Р. Фишер, В.Н. Фомин, П. Хансен, А.Я. Червоненкис, Б. Шелкопф, В.А. Якубович и другие.
Предлагаемая работа относится к оптимизационному подходу. В последние десятилетия достижения в математическом программировании, негладком анализе и недифференцируемой оптимизации обеспечили новый более мощный и эффективный аппарат, с помощью которого теперь можно построить математическую модель, лучше описывающую рассматриваемую задачу [8, 17, 26, 33, 35]. Использование нелинейных и даже негладких критериев идентификации может улучшить качество идентификации [7, 28, 32, 34, 41, 42, 50, 55, 65]. Вопросами негладкого анализа занимались, в частности, Ф.П. Васильев, В.В. Гороховик, В.Ф. Демьянов, И.И. Еремин, Ю.М. Ермольев, А.Д. Иоффе, Ж.-Б. Ириа-Уррути, Ф. Кларк, С.С. Кутателадзе, В.Н. Малоземов, Л.И. Минченко, Б.Т. Поляк, Л.Н. Полякова, Б.Н. Пшеничный, Р.Т. Рокафеллар, A.M. Рубинов, В.М. Тихомиров, В.В. Федоров, Н.З. Шор. Современный уровень развития вычислительной техники позволяет реализовать многие методы и алгоритмы, которые ранее невозможно было использовать [10, 22,32,42, 50, 55].
Как уже отмечалось, задачи математической диагностики можно свести к исследованию модели, в которой требуется разделить два или более множества, выпуклые оболочки которых, вообще говоря, пересекаются, т.е. возникает задача разделения двух "линейно" неразделимых множеств. Для этого требуется выбрать сравнительно простой критерий (идентификатор), с помощью которого можно классифицировать точки. При выбранном идентификаторе (называемом также классификатором, правилом идентификации, решающим правилом или критериальной функцией), по значению которого судят о принадлежности данной точки тому или другому множеству, качество идентификации оценивается каким-нибудь "естественным" критерием, например, количеством ошибочно идентифицированных точек. К сожалению, этот критерий (будем называть его далее "натуральным" функционалом) является существенно разрывной функцией, поэтому применение классических методов, разработанных для
гладких или непрерывных негладких функций, затруднено. Эта трудность обходится построением достаточно хорошей аппроксимации "натурального" функционала, которую далее будем называть "суррогатным" функционалом. Так как большинство "суррогатных" функционалов - негладкие, то ЛДА должен быть расширен до негладкого дискриминантного анализа (НДА) [28, 41, 49-50, 65], в рамках которого для решения практической задачи идентификации требуется:
построить правило идентификации;
сформулировать для данной задачи естественный критерий (натуральный функционал) (обычно это - количество ошибочно классифицируемых точек). Этот критерий часто не является непрерывным;
выбрать соответствующую модель (суррогатный функционал);
использовать существующие или создать новые алгоритмы и программное обеспечение, чтобы получить численные результаты.
Постановка задачи. Задача идентификации может быть
сформулирована следующим образом. Пусть в пространстве R" заданы два множества точек А и В:
A = {a,eR"\iel}, / = 1:JV,; B = {bj
Положим C = AkjB. Требуется указать достаточно простой критерий для различения элементов множеств А и В, т.е. найти правило (правило идентификации), чтобы идентифицировать точки множества С. Обычно идентификацию осуществляют с помощью некоторых функционалов (в настоящей работе в качестве функционала выбран линейный функционал) следующим образом.
Пусть сеАиВ. Введем множество L(y,d) = \хєR"\r(x,y,d) = o}, где
r(x,y,d)=
|yj| = 1. Тогда r(x, у, d) является (с точностью до знака) расстоянием от точки х до гиперплоскости b(y,d).
Будем использовать следующее правило идентификации: если г {с, у, d) < О, то считаем, что с є А; если г (с, у, d) > 0, то считаем, что с є В.
В случае r(c,y,d)=0 точка с считается неидентифицируемой с помощью
функции r(x,y,d) (см. рис. 1).
Построим разбиение индексных множеств I и J: I = I+uI0uI_,
J = J+uJ0u J_, где
I+=I+(y,d)={ieI\r(at9y,d)>0}; J+ =-/+(М)={./є J\-r(bj,y,d)>0 j; Io=IoM={ieI\r(at,y,d) = 0}; J0=J0(y,d)={jeJ\-r(bj,y,d)=0}, I_=I_{y,d)={ieI\r(ai,y,d)<0}; J_=J_(y,d)=\j eJ\-r{bj,y,d)
Здесь:
I+(y,d) и J+(y,d) — индексные множества, состоящие из номеров точек
множеств А и В, соответственно, которые ошибочно идентифицированы с помощью функции r(x,y,d);
h(y>d) и J0(y,d) — индексные множества, состоящие из номеров точек множеств А и В, соответственно, которые неидентифицируемы с помощью функции r(x,y,d);
I_{y,d) и J_{y,d) — индексные множества, состоящие из номеров точек множеств А я В, соответственно, которые правильно идентифицированы с помощью функции r{x,y,d).
Воспользуемся следующим обозначением: если D - конечное множество некоторого пространства, то \D\ = card D - количество элементов множества D.
Положим б(7> ^0 = К (у> ^0(+ 1^+0^ ^)( ~ количество ошибочно идентифицируемых точек обоих множеств А и В. Тогда множество Q(y,d) = \l+(y,d] + \j+(y,d} + \l0(y,d] + \j0(y,d] - количество неверно
идентифицируемых точек множеств А я В (неверно идентифицируемые точки - это объединение ошибочно идентифицируемых и неидентифицируемых точек).
Определение 1. Будем называть каждую из введенных функций Q(y, d)
и Q{y,d)~ "натуральным" функционалом.
рис. 1
Цель работы состоит в разделении множеств А и В с помощью гиперплоскости L(y, d). Точное разделение, вообще говоря, невозможно. Поэтому можно ставить задачу провести гиперплоскость L(y, d) так, чтобы число неверно идентифицируемых точек было как можно меньше, т.е.' требуется минимизировать функционал Q(y, d) на множестве
Q={(M)||MI=i}c/r'.
Поскольку функционал Q(y, d) разрывен, то применение стандартных методов, разработанных для минимизации непрерывных функций, невозможно. Поэтому будем аппроксимировать "натуральный" функционал Q(y, d) так называемым "суррогатным" функционалом.
В настоящей работе в качестве "суррогатного" функционала используются следующие функционалы:
0,1
0,
^Л:М) = тах
*L(*<0-Z
r(ai,y,d) ^(а„у^)\ +
\at,y,d)\ + E
+ ^тах^
+2
-r[bpy,d) '\r(bpy,d)\ + s
-r(bpy,d)
\r[bpy,d)\ + s
При є-» О, є>0, оба функционала являются аппроксимирующими натуральный функционал Q(y, d), т.е. Fje(y,d)—^Q->Q{y,d) V і є 1:2. Иначе говоря, значения функционалов Fle(y,d) и F2e(y,d) представляют собой (с некоторой точностью) количество точек, для которых выполняются условия г(а,,у,d)>0 и -r[bj,y,d)>0, так как ненулевой вклад в FH(y,d) и
F2e(y,d) дают те точки из множеств А и В, которые неправильно идентифицированы. Оба эти функционала непрерывны, причем Fle(y,d) является субдифференцируемым, a F2z(y,d) - даже непрерывно-дифференцируемым. Задача состоит в том, чтобы минимизировать оба суррогатных функционала, а также натуральный функционал Q(y,d) на множестве Q = {(y,d)\ ||>»||=1}с: J?"+I с помощью построения различных вариантов направлений наискорейшего спуска и сравнить эффективность использования их на практике.
Цель работы. Целью диссертационной работы является изучение свойств функционалов Fle(y,d) и F2e(y,d), разработка численных методов
для минимизации этих функционалов, создание программного обеспечения, проведение экспериментов на конкретных базах данных, сравнение полученных результатов с исследованиями других авторов.
Методы исследований. Построение новых методов идентификации точек множеств осуществляется с помощью современного аппарата математического анализа (классического - гладкого- и негладкого), а также математического программирования, включая методы квазидифференциального исчисления и недифференцируемой оптимизации.
Научная новизна:
В диссертационной работе для оптимального разделения двух множеств с помощью гиперплоскости предложены два новых суррогатных функционала, изучены их свойства.
Построены численные методы для минимизации натурального функционала, в которых используются направления наискорейшего спуска суррогатных функционалов.
Создано программное обеспечение (построены алгоритмы, реализованные в виде программного продукта) для применения предложенных методов.
Проведено тестирование на конкретных базах данных и разработаны рекомендации для практического применения проведенных исследований.
Практическая и теоретическая значимость. Теоретическая значимость работы определяется тем, что в ней предложены новые математические методы и вычислительные алгоритмы для решения задач математической диагностики, которые могут использоваться для решения практических задач.
Связь с научными программами. Работа проводилась в рамках выполнения проекта РФФИ № 03-01-00668.
Публикации. По результатам проведенных исследований опубликовано 4 печатных работы [12-15].
Апробация. Результаты работы докладывались и обсуждались на
семинарах лаборатории биомедицинской информатики Санкт-
Петербургского института информатики и автоматизации РАН, кафедр
математической теории моделирования систем управления факультета
прикладной математики - процессов управления и параллельных алгоритмов
математико-механического факультета Санкт-Петербургского
государственного университета, а также на конференциях:
1. XXXIV научная конференция аспирантов и студентов "Процессы управления и устойчивость" 21-24 апреля 2003 г., место проведения - Санкт-Петербургский государственный университет, СПб;
2. 56-я Международная научно-техническая конференция молодых
ученых: "Актуальные проблемы современного строительства" 28-30 октября
2003 г., место проведения - Санкт-Петербургский государственный
архитектурно-строительный университет, СПб;
Всероссийская научно-техническая конференция "Искусственный интеллект в XXI веке" 27 ноября 2003 г., место проведения - Пенза, Приволжский Дом знаний, 2003;
61-я научная конференция профессоров, преподавателей, научных работников, инженеров и аспирантов Санкт-Петербургского государственного архитектурно-строительного университета 7-9 февраля
2004 г., место проведения - Санкт-Петербургский государственный
архитектурно-строительный университет, СПб;
5. XXXV научная конференция аспирантов и студентов "Процессы
управления и устойчивость" 14-16 апреля 2004 г., место проведения - Санкт-
Петербургский государственный университет, СПб;
6. 63-я научная конференция профессоров, преподавателей,
научных работников, инженеров и аспирантов Санкт-Петербургского
государственного архитектурно-строительного университета 7-9 февраля
2006 г., место проведения - Санкт-Петербургский государственный
архитектурно-строительный университет, СПб;
7. XXXVII международная научная конференция аспирантов и
студентов "Процессы управления и устойчивость" 11-13 апреля 2006 г.,
место проведения - Санкт-Петербургский государственный университет,
СПб.
Структура работы
Диссертационная работа включает в себя введение, список основных обозначений, три главы, в которых содержатся полученные результаты, заключение, приложение и список литературы из 69 наименований. Работа имеет общий объем - 191 страница (включая приложение).
Содержание работы Во Введении объясняется актуальность темы, содержится постановка задачи, формулируются цели и методы исследования, кратко перечисляются основные полученные результаты.
Исследование свойств функционала Fu (у)
Ниже будет показано, что заданный функционал представляет собой субдифференцируемую функцию, для которой выполняются следующие свойства (см. [18], гл.1, 6,14; гл.2, 1): 1. Производная по направлениям1 выражается с помощью субдифференциала2 д/(х) функции f(x) в точке х0 по формуле f(xQ,g) = max(v,g). (1.2.1) 2. Необходимое условие минимума на R" имеет вид ОпЕд/{х), (1.2.2) где Л; - точка минимума f(x) на R". 3. Если 0И д/(х0), то направление ( о) = -ф -. О-2-3) V; lv(x0) где v(x0)= min v, является направлением наискорейшего спуска vedf(xQ) функции f(x) в точке х0.
Пусть на открытом множестве S с R" задана конечная функция fix). Будем говорить, что функция f(x) квазидифференцируема в точке x0eS, если она дифференцируема в точке х0 по любому направлению g є R" и если существуют выпуклые компакты df(x0)cz R" и df(xQ)c: R" такие, что fU.g)-mf( +ag) fM= wjr-g) ЧИ1 , ". о-2-4) aJ-0 a еЭД 0)4 wed/(xoy
Пару множеств Df(xQ) = [Qf(x0),df(x0)] назовем квазидифференциалом (КВД) функции f(x) в точке х0, а множества d.f{xQ\ Э/(лг0) соответственно суб- и супердифференциалом функции f(x) в точке х0. ИЗ формулы (1.2.4) видно что КВД определяется неоднозначно: пара множеств d(xo) = [df(xo) + B,df(x0)-B], где BaR"- произвольный выпуклый компакт, тоже является КВД. Если среди квазидифференциалов функции f(x) в точке х0 есть элемент вида Df(x0) = [df(x0),{On}] = [df(x0),{On}], то функцию будем называть субдифференцируемой в точке JC0. Аналогично, если среди квазидифференциалов функции f(x) в точке х0 есть элемент вида Df(xo)=[{Qnl&(xo)] = [{Qnldf(x0)], то функцию будем называть супердифференцируемой в точке д:0.
Пусть Q с S. Если функция f(x) квазидифференцируема в каждой точке XQ Є Q, ТО она называется квазидифференцируемой на множестве Q (см. [18], гл.2, 1).
Пусть [X, р] - метрическое пространство (т.е. на множестве X задана метрика р)3, QczX - непустое множество этого пространства. Предположим, что на допределен функционал f:X- R\ Требуется найти
Эта задача называется задачей условной минимизации (в случае Q = X задача (1.2.6) называется задачей безусловной минимизации).
Задача, которой посвящена данная работа, представляет собой задачу условной минимизации, которую можно свести к задаче безусловной минимизации. Один из способов состоит в использовании метода точных штрафных функций, а именно при некоторых предположениях, сформулированных ниже, существует такое А, 0, что при любом X X задача минимизации функционала FXtAy) на множестве Q = \yeR"+l\(p{y) = 0\, где ф(у,й?) = .у-1, эквивалентна задаче минимизации функционала ix(y) = Fls(y) + k ($()}) на всем пространстве Rn+\ Ясно, что (р(у) 0 для любого yeR"+1. Воспользуемся следующей теоремой: Теорема 1.2.2. (См. [19], стр.70). Пусть имеет место inf Fu{y) = F -оо и выполнены условия: уеСї 1) существует 0 оо такое, что для любого Х Х0 найдется ух є R"+l такое, что Фи ( ) = inf Фи (у) = Ф;,; yeR" 2) существует 8 О, а О такое, что ф ф. ит р(У+ -г)-ф(50 _а 0 а-Ю а S-[geV \lfcl) для всех у є Q5 \ Q, где Q6 = {у є R"+11 ф(у) 8 }4; 3) функция Fu(y) липшицева на Q5 \Q, то есть для некоторого L оо будет выполняться Flt(yvd)- Flt (у2,d)\ L р(у,,у2) для любых у,, 2 є Я".
Величина ф (у) называется скоростью наискорейшего спуска функции ф(у) в точке у. Тогда существует А, Л,0 такое, что выполняется (p(yx,dx) = 0 для всех Х Х и Fu(yx,dx) = F = mfFle(y), т. е. точка (yx,dx) - решение задачи yeil условной минимизации. Замечание 1.2.1. В случае, если ф(у) - гладкая функция, то Ф ООЧФШ (1-2-7) 2L Из доказательства теоремы 1.2.2 (см. [19], стр.72) имеем, что X = —. а Покажем выполнение условий 2) и 3) (можно показать также выполнение условия 1) теоремы 1.2.2). Для того, чтобы оценить константу Липшица L для функционала F]E(y) t такую, что \FlE(yvd)-Fu(y2,d)\ b\\yi-y2\\ Vylty2eR\ воспользуемся следующими результатами, которые известны из курса математического анализа: Утверждение 1.2.1. Для линейных функций /іСу /гСу)? локально липшицевых с константами Липшица Lj и L2, соответственно, функции f(y) = fi(y)±fi(y\ f(y) = /iW f2(y} /M = 4H; AW O являются локально липшицевыми с константами Липшица 1) для линейной функции f(x,y,d)= x,y +d, x,yeR",deRl константа Липшица = х; 2)для суммы и разности /(у) = f\{y)± fiiy) константа Липшица 3)для произведения f(y)=fi(y)-f2{y), где \fx(y\ Cx,\f2(y\ C2, константа Липшица L = max{L,; L2} (Cx + C2) 4)для отношения f{y) = lM /2(y) 0, IfiWuA, \f2(y] B, \fz{y\ є, константа Липшица L
Исследование свойств функционала F2s (у)
Сформулируем теперь необходимое условие минимума для функционала F2e(y). Лемма 1.4.2. Необходимое условие минимума для функционала F2e(y) на множестве Q имеет вид I Л ъ+Ы-о.г г{а„у1Ж\а, -W 1Л ){г(а„уе,4 в)+еУ jejM){-r(bj,yl,d e)+ef R»: 2 teU + s = 0.
Доказательство, п Как было показано выше, задача минимизации функционала F2s(y) на множестве Q сводится к задаче безусловной минимизации функционала Ф2Х(у) (ПРИ А, А, ) на всем пространстве Rn+1, где ф2х(у)= Ш+ЧМ1-1 Функционал Ф2\(у) является субдифференцируемым, и на множестве Q (при \\у\\ = 1) его субдифференциал равен 3&2Х Ы = VF2e (у) + X - со{Су,0); (- у,0)}. По необходимому условию минимума 0п+1 едФ2Х{у ), где 5 = (У ,ЙҐ)Є Q - точка минимума функционала F2e\y ) на множестве Q.
Точка у = (y ,d)eQ., удовлетворяющая необходимому условию минимума 0И+1 єдФ2Х\у ), называется стационарной точкой функционала Ф2Х на R л+1
Рассмотрим точку у = (у, Й?) Є Q. Для проверки этой точки на стационарность решим задачу нахождения ближайшей точки v(y) от начала координат до субдифференциала дФ2Х(у)- Для этого найдем min -.H2=--v(yF (1-4.5) Имеем 5Ф2,(г) = - Е(у) + Х.[у.З? + (і-уХ-Й]ує[0;і]} = = {у = є + ц. Чцє[- ]}, где ц = А,(2у-1), У = (у,0), j JT1. Решим сначала задачу mini.Fi +i.j2 = IK + \i -jf (1.4.6) цел 2. Для этого найдем производную от функционала (1.4.6) и приравняем ее нулю: следовательно, получим (F2e, у) + JI j j = О, откуда имеем 1УГ""( } Поскольку множество значений у такое, что у є Q, то есть множество значений у - единичная сфера, a F2\ - ограничено, то ограниченным будет и ц =-(F2e,J ), и при достаточно больших X окажется и. є [-X; X], то есть, min- -\Fie+\i-yf= min- F2 e + ц 2. Но тогда задача (1.4.5) 1 2 1 2 эквивалентна задаче min — F2 + ц д/ = — F2 e + u. -3? . Следовательно, цЄ[--Х;Х]2 ІГ2Є ЛІ 2 2Є решение задачи (1.4.6) будет решением задачи (1.4.5), то есть т(у)=К-К,у)-У Если v(y)j = 0„+1, то точка y = (y,d)eQ - стационарная точка функционала F2E(y) на множестве Q, следовательно, при этом имеет место соотношение &)=К-(К У) У- С1-4-7) Если v(p & 0я+1, то найдем направление наискорейшего спуска g(y) функции Ф2Х в точке у: g(y) = /- Это направление будет IwJll использовано в главе 2 для построения численных методов решения задачи. Воспользуемся равенством (1.4.7) для вывода необходимого условия минимума функционала F2s на множестве Q в явном виде. Если у = [у , d )e Q - точка минимума функционала Fl\y ) на множестве Q, то из (1.4.7) следует В настоящей главе рассматривается задача минимизации введенных в главе 1 функционалов Fle(y,d) и F2e{y,d). Задача является задачей минимизации при наличии ограничений, т.е. задачей условной минимизации. В 1.2 было показано, что с помощью теории точных штрафов эта задача сводится к задаче безусловной минимизации функционала Фц О7) = Fu(р) + ф(у) гДе - любое достаточно большое число. Пусть имеется некоторое фиксированное y = (y,d) такое, что у =1. Распишем субдифференциалы дФіХ(у) и дФ2Х(у) для функционалов КМ и .(M):»AG0=2Fj G0 + A.-SPW / = 1:2. Для функционала Fu(y,d) имеем /є/0 І Є J уєУ0 t Є Для функционала F2e(y,d) имеем + X-co{(y, 0),(- 7,0)}. Оба эти субдифференциала имеют вид: /=1 Проверка необходимого условия минимума сводится к проверке условия 0И+1 є2Фд(у), У = 1:2. Если необходимое условие не выполняется в Ґ-\ v(y) точке у, то тогда ищется направление наискорейшего спуска g{y) = - , llvMI где \\v{yj\ - расстояние от 0л+1 до дФ (у), j = 1:2. Поэтому поставим вспомогательную задачу: найти расстояние от и+1 -мерного нуля до субдифференциала дФ}Х{у), у = 1:2, - которую будем решать с помощью метода условного градиента.
Метод проектирования для минимизации функционала F2e (у) на множестве О
Отметим, что сходимость данного метода к стационарной точке следует из сходимости градиентных методов [8,26,33].
Замечание 2.6.2.1. На практике в главе 3 для натурального функционала Q{y) будет использоваться как метод построения направления наискорейшего спуска с помощью суррогатного функционала F2E(y), описанный в данном пункте 2.6, так и метод построения направления наискорейшего спуска с помощью суррогатного функционала F2e(y), изложенный в пункте 1 2.6 для функционала FH(y) . 1. Выбирается произвольно у0 = (у0,d0) є Q = {у є R"+i \ \\y\ -1 = 0}. Пусть уже построено yk=(yk,dk). Находим направления наискорейшего спуска функционалов Фа и Ф2Х в точке ук. Пусть это будут направления vk ! 2. Найдем и vk, соответственно. mingfo + а v,(l))= й(ук + аі 4]\ 3{ук + « П(2))= йЬк + »2 П(2)) 3. Если g(yt +а, (1)) 2(з?А +а2 -vi2)), то положим ум=ук+а к{{).
Если Q{yk+arvk[l)) Q(yk+a2-vk[2)) то положим ум = yk+a2vk{2). Если нахождение обоих направлений vk и v затруднено, то можно использовать только одно из них. В этой главе представлены результаты численных экспериментов, которые были получены при последовательном проведении минимизации натурального функционала Q(y,d) с помощью алгоритмов построения направлений наискорейшего спуска для суррогатных функционалов Fu{y,d) и F2E(y,d). Здесь на примерах исследуемых ранее баз данных рассматриваются следующие варианты решения поставленной задачи разделения объектов: 1) Алгоритм минимизации натурального функционала Q(y,d), в котором используется построение направлений наискорейшего спуска (н. н. с.) четырех типов: a) Н. н. с. строится с помощью суррогатного функционала Fu{y,d) (см. 2.2; 2.3); b) Н. н. с. строится с помощью суррогатного функционала F2e(y,d) (см. 2.3; 1.4); c) Н. н. с. строится с помощью суррогатного функционала F2e(y,d) (см. 2.4); d) Н. н. с. строится одновременно с помощью суррогатных функционалов Fu(y,d) и F2e(y,d) (см. 2.5). 2) Рассмотрим также результаты решения задачи минимизации непосредственно суррогатных функционалов Fle(y,d) и F2E(y,d) по схеме выше описанного построения направлений наискорейшего спуска (1 а) - 1 d)).
Глава состоит из двух частей: 1. Первая часть посвящена исследованию рассматриваемых ранее баз данных, к которым уже применялись различные методы идентификации и имеются численные результаты. Поэтому основной задачей этой части главы является получение численных результатов решения задачи разделения объектов с помощью представленных в данной работе методов, а основные выводы будут строиться на основании сравнения полученных результатов с уже имеющимися по следующим пунктам: процент отделимости (удалось улучшить, ухудшилось либо не изменилось); при каком є получается лучший результат; какое из направлений наискорейшего спуска целесообразно использовать, а также на предмет качества применения суррогатного или натурального функционалов.
2. Вторая часть представлена исследованием онкологической базы данных рака молочной железы (база Мангасаряна) разработанными в данной работе методами и ее практическим применением. В этой части на основании полученных результатов ставится и решается задача определения эффективности прогнозирования лечения онкологических заболеваний.
Замечание 3.1.1. Для отбора наиболее информативных признаков используются результаты ранжирования параметров, полученные А.М.Багировым (Балларатский Университет, Австралия) и А.В.Кокориной (СПбГУ, Россия)1.
Замечание 3.1.2. Программы, реализующие представленные методы решения задачи разделения объектов, были написаны на языке Delphi, вычисления проводились на PC с CPU Intel Celeron 1,70 GHz, 256 MB of RAM.
Замечание 3.1.3. Оптимизация проводится с точностью до 0.001. Для метода условного градиента используется точность 0.1. Для метода деления отрезка пополам используется точность 0.01.
Замечание 3.1.4. Для объемных баз данных (общее число точек более 300-400) оказалось достаточным использовать небольшое количество параметров (3-4). 3.1.1. Обозначения
Результаты расчетов представлены в виде таблиц и рисунков. Для описания результатов в таблицах использованы следующие обозначения: N - номера параметров, используемых при разделении, расположенные в порядке убывания значимости; Р - процент правильно определенных точек, полученный наилучшим для 100% обучающего множества методами Кокориной А.В.; t - время вычисления методами Кокориной А.В. (в секундах); t - время вычисления исследуемыми методами (в секундах); п - количество произведенных итераций при фиксированном оптимальном начальном значении (у, d). Для случаев la), lb), 1с) и Id) (натуральный функционал Q(y,d)), соответственно, введем: Pibeg, p2(1)beg, p2(2)beg} pbes _ начальные значения процента правильно определенных точек, полученные с помощью минимизации функционала Q(y,d) для 100% обучающего множества; P]end, p2(1)cnd, p2(2)end? pend _ конечные значения процента правильно определенных точек, полученные с помощью минимизации функционала Q(y,d) для 100% обучающего множества;
База данных Австралийский кредит (Australian credit)
Эта база была изучена J.R. Quinlan (см. [64]). Назначение этой базы данных - разработать правило для определения риска кредитования. Результаты интерпретировать сложно, потому что атрибуты (признаки) и классы были закодированы, чтобы сохранить конфиденциальность. С базой можно ознакомиться в Internet [68].
База данных Австралийский кредит (Australian credit) состоит из двух классов и 690 наблюдений: 383 из них принадлежат первому классу и 307 -второму. Данные разделяют на два класса по значению 15-ой координаты -либо 1, либо 2. Число рассматриваемых параметров л=14.
Результаты ранжирования Кокориной А.В.: - 14, 8, 10, 9, 5, 7, 6, 4, 3, 2, 13, 12, 11, 1 - параметры расположены в порядке уменьшения информативности. Результаты ранжирования Багирова A.M.: - (8, 9,10); (7, 8, 9,10); (5, 7, 9, 8,10); (3, 5, 7, 8, 9,10,13, 14); (2, 3, 5, 7, 8, 9, 10, 13, 14); (1-14)- параметры сгруппированы по степени важности в норме L1; - (7, 8, 9, 10); (7, 8, 9, 10, 14); (3, 7, 8, 9, 10, 14); (3, 5, 7, 8, 9, 10, 14); (3, 5, 7, 8, 9, 10, 11, 14); (3, 5-11, 13, 14); (1-11, 13, 14); (1-14) - параметры сгруппированы по степени важности в норме L2. Разделение ведется при помощи функционала Q2(1) при е = 0.00001 (на основании выводов предыдущего параграфа), так как база достаточно большая и обработка затруднена из-за длительности времени вычислений. Замечание 3.3.1. При построении гиперплоскости рассматривались все 100% данных.
Эта база данных содержит данные о наличии или отсутствии порока сердца, установленные в результате различных медицинских тестов, проведенных на пациентах. База данных получена из Кливлендского Медицинского Фонда (Cleveland Clinic Foundation); состоит из двух классов и 297 наблюдений (160 из первого класса и 137 из второго). С базой можно ознакомиться в Internet [68].
Множества разделяются по значению 14-ой координаты (0 - здоровые, 1, 2, 3 - больные, с соответствующей степенью заболевания). Число рассматриваемых параметров «=13. Замечание 3.4.1. Строки, в которых отсутствуют значения некоторых параметров, полностью исключаются из рассмотрения. Ранжирование по Кокориной А.В.: - 12, 13, 10, 9, 11, 8, 3, 2, 1, 4, 7, 5, 6 - параметры упорядочены по уменьшению информативности. Ранжирование по Багирову A.M.: - (7, 10, 12); (7, 9, 10, 12); (7, 9, 10, 12, 13); (7, 9, 10, 11, 12, 13); (3, 7, 9, 10, 12, 13); (1, 3, 5, 7, 8, 9, 10, 12, 13) - параметры сгруппированы по степени важности в норме L1, - (9, 10,12); (7, 9, 10, 12); (7, 9, 10,12, 13); (2, 7, 9,10, 12, 13); (2, 3, 7, 8, 9, 10, 11, 12, 13); (2, 3, 6 - 13); (1 - 4, 6 - 13) - параметры сгруппированы по степени важности в норме L2. В данном параграфе поставлены следующие вопросы: 1. Получить результаты исследования базы данных с помощью натурального функционала Q! при є = 0.001 и Q2(1) при 8 = 0.001-0.00001 в трех случаях: по результатам ранжирования Кокориной А.В. и Багирова A.M. в нормах L1 иЬ2. 2. Сравнить результаты между собой и с ранее полученными. 3. Оценить качество получаемого процента отделимости и степень сложности обработки базы данных. Замечание 3.4.2. При построении гиперплоскости рассматривались все 100% данных. Результаты представлены в таблицах 3.4.1 - 3.4.12. Таблицы 3.4.4, 3.4.8, 3.4.12 как наиболее показательные представлены в параграфе, остальные - см. Приложение.
Наилучший результат по результатам ранжирования Кокориной А.В. -84.5% правильно определенных точек - был получен во всех четырех случаях при всех рассмотренных е. Исследовать базу данных удалось не более чем при пяти параметрах, так как метод регистрировал негативное влияние 8-го параметра и требовалось много времени на вычисления. При є = 0.00001 в случае lb) результат получился за более короткое время, чем в остальных случаях.
На рис. 3.4.3 рассматриваются значения 9-го параметра (ось абсцисс) и 10-го (ось ординат) как наиболее значимых. При рассмотрении параметров в норме L2 наилучший результат -84.9% при 8 = 0.0001 и 8 = 0.00001. При 8 = 0.00001 в случае lb) результат получился за более короткое время, чем в остальных случаях. При всех рассмотренных комбинациях параметров результат получался каждый раз лучше уже имеющегося.
Наилучший результат по всем рассмотренным вариантам группирования параметров- 86.5% правильно определенных точек - был получен при рассмотрении параметров базы в норме L1 с помощью натурального функционала Q2(1) при всех 3-х рассмотренных є.
В сравнении с ранее полученными результатами повысить процент отделимости удалось всего лишь на 1-1.5%, что, однако, дает возможность утверждать, что рассматриваемый метод применим на практике, как, впрочем, и натуральный функционал Qi. Данная база создана клинический научный центром Висконсинского Университета. Состоит из двух классов, 569 (212 - данные пациентов со злокачественными опухолями и 357 - данные пациентов с доброкачественными опухолями) наблюдений и 30 параметров (см. [68]).
Ранжирование по Кокориной А.В.: - 28, 23, 24, 8,21, 14, 3, 4, 1, 7, 13, 11,27,26, 6, 29,22,25,2, 18, 30, 5, 17, 9, 16, 20, 19, 12, 15, 10 - параметры расположены в порядке уменьшения информативности. Ранжирование по Багирову A.M.: - 7; (7, 8); (4, 7, 8); (4, 6, 7, 8); (1, 3, 4, 6, 7, 8); (1, 2, 3, 4, 6, 7, 8); (1-8) параметры сгруппированы в порядке уменьшения степени важности. В данном параграфе поставлены следующие вопросы: 1. Получить результаты исследования базы данных в случае 1а) при = 0.001, lb) при 8 = 0.001-0.00001 и 1с) при є = 0.001 по результатам ранжирования Кокориной А.В. и в случае 1а) при є = 0.001 и lb) при є = 0.001 - 0.00001 по результатам ранжирования Багирова A.M. 2. Сравнить результаты между собой и с ранее полученными. 3. Оценить качество получаемого процента отделимости и степень сложности обработки базы данных.
