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

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

ЗУБОВА Ольга Андреевна

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

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

АВТОРЕФЕРАТ

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

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

□03448438

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

2008

1 6 0КТ 2008

003448438

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

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

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

кандидат физико-математических наук, доцент Виноградова Татьяна Кановна

Санкт-Петербургский Институт информатики и автоматизации Российской Академии Наук (СПИИРАН)

Защита состоится

008 г в часов на заседании совета Д 212 232 59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу 199004, Санкт-Петербург, Средний пр В О , д 41/43, аудитория 513

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

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

Научный руководитель Официальные оппоненты

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

Ученый секретарь диссертационного совета,

доктор физ -мат наук, профессор /¿Ъ - Ногин В Д

/

/

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

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

В области решения указанных задач существует несколько различных подходов статистический подход Р Фишера, получивший развитие в начале 60-х годов прошлого столетия, метод опорных градиентов, предложенный В Вапником, метод машинного обучения, метод обработки данных с помощью линейного программирования, кластерный анализ и другие, а также так называемый «оптимизационный подход», основоположниками которого были И М Гельфанд, Ю И Журавлев, Б Н Козинец, О Л Ман-гасарян, Б Т Поляк, Дж Б Розен, В Н Фомин, В А Якубович и другие В 60-е - 80-е годы XX века наиболее развитыми и популярными инструментами оптимизации были линейное и квадратичное программирование Поэтому до сих пор оптимизационные элементы, которые являются ключевыми во всевозможных методах, основаны или сводятся к линейному

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

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

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

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

1 В диссертационной работе предложены новые методы оптимального разделения двух и трех множеств многомерного пространства Для решения задачи разделения двух множеств в п-мерном пространстве при помощи (п-1)-мерной гиперплоскости вводятся два новых суррогатных оценочных функционала значение одного из них есть

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

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

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

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

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

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

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

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

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

В первой главе излагается новый подход к решению задачи идентификации двух множеств = -[аг | г € /} и В = {Ь-, | € состоящих из конечных наборов точек в многомерном пространстве, выпуклые оболочки которых не являются полностью отделимыми (соА Р| соВ ф 0) Предлагается разделять указанные множества при помощи некоторой (п-1)-мерной гиперплоскости в пространстве К"

и = {жеЕп|г(ж,Г) =о},

где г (х,Т) = (х,1) + й, 1= [(1,1], I е Ж е Кп, й € Е

Пусть с е С = Л1)В в

качестве решения задачи идентификации будем искать РП следующего вида

если г (с, > 0, то считаем, что с € Л, если г (с, Г) < 0, то считаем, что с £ В

В качестве критерия эффективности построенного решения рассматриваются два суррогатных функционала Рг (I) и (Г) значение одного из них есть сумма расстояний от неверно идентифицированных точек до разделяющей гиперплоскости Ь\, а значение другого - половина суммы квадратов данных расстояний

( 0 = тах{°>г {Ьз> ¡) } + XI тах{°. ~г (а«> 0 }.

ад=5

3€.7 г£1

, 2

^(тах{о,г (Ь„/)}) + £](тах{о,-г (а,,Г)}) " Ье.7 г€/

Далее проводится исследование оценочных функционалов (/) и ^ (/) Доказывается, что функционалы (/) и F2(/) являются выпуклыми ква-зидифференцируемыми функциями, удовлетворяющими условиям теоремы о существовании точной штрафной функции, а также вычисляются квазидифференциалы самих функционалов (Г) и ^ (Г) и их штрафных функций Фа(Г) = + |1 - |'/1|| и Фа (Г) = + |1 - ||/|||, где Л > О В результате данного исследования выводятся следующие критерии оптимальности РП в смысле функционалов и ^(Г) для того чтобы РП было оптимальным в смысле функционала ^ (Г), необходимо, чтобы, во-первых, количество неверно идентифицированных точек множества А было равно количеству точек множества В, ошибочно идентифицированных как точки множества А, и, во-вторых, вектор, представляющий собой определенную линейную комбинацию неверно определенных точек с единичными коэффициентами, был параллелен вектору нормали разделяющей гиперплоскости I*, для того чтобы РП было оптимальным в смысле

функционала /), необходимо, чтобы, во-первых, сумма расстояний от неверно идентифицированных точек множества А до разделяющей гиперплоскости была равна сумме расстояний от точек множества В, ошибочно идентифицированных как точки множества А, до этой гиперплоскости, и, во-вторых, вектор, представляющий собой сумму неверно определенных точек с коэффициентами, равными расстояниям от этих точек до гиперплоскости, был параллелен вектору нормали разделяющей гиперплоскости I"

Во второй главе описывается новый подход к решению задачи идентификации множеств А = {а,) г £ I], В — {Ь} \ ] £ ^ и С = {ск \ к £ К}, состоящих из конечных наборов точек в многомерном пространстве, выпуклые оболочки которых не являются полностью отделимыми Предлагается разделять указанные множества при помощи двух параллельных (п-1)-мерных гиперплоскостей в пространстве Е", задаваемых следующими уравнениями

г (хЛ) = 0, г (х,[2) = 0, где г (х,1г) = (х,1) + ¿г,

I = [«*,,/], ¡£ Кп+1, 1,х £ К", <1г £ Е, ||/|| = 1,г = 1 2

Для того, чтобы идентифицировать каждую точку у € У ^ Ливи^ рассматривается РП следующего вида

если г (у, 1\) < 0, то считаем, что у £ А,

если г (у, Г]) > 0, г (у,/2) < 0, то считаем, что у £ В,

если г (г/, Гг) > 0, то считаем, что у £ С

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

гб/ з€]

+ ^тах|о,-г (ск,Т2)},

к£К

£(тах{о,г (аг,Г1>})2 + ]Г(тах{о,-г (с*,/~"2)})2

гЕ1 кек

]>](тах{о,г (ЬГМ) ,-г

зез

Далее проводится исследование оценочных функционалов Р\ (Г) и ^(0 Доказывается, что функционалы и Р2(0 являются выпуклыми ква-зидифференцируемыми фикциями, удовлетворяющими условиям теоремы о существовании точной штрафной функции, а также вычисляются квазидифференциалы самих функционалов и и их штрафных функций Фх(Г) = Ъ{1) + |1 - ||2||| и ф2([) = Р2(Г) + |1 - ||/|||, где А > О В результате данного исследования выводятся следующие критерии оптимальности РП в смысле функционалов (/) и ( 0 для того чтобы РП было оптимальным в смысле функционала необходимо, чтобы,

во-первых, количество неверно идентифицированных точек множества А

было равно количеству точек множества В, ошибочно идентифицированных как точки множества А, а количество неверно идентифицированных точек множества С было равно количеству точек множества В, ошибочно идентифицированных как точки множества С, и, во-вторых, вектор, представляющий собой определенную линейную комбинацию неверно определенных точек с единичными коэффициентами, был параллелен вектору нормали разделяющей гиперплоскости I*, для того чтобы РП было оптимальным в смысле функционала )> необходимо, чтобы, во-первых, сумма расстояний от неверно определенных точек множества А до первой разделяющей гиперплоскости была равна сумме расстояний от точек множества В, ошибочно идентифицированных как точки множества А, до этой гиперплоскости, а сумма расстояний от неверно определенных точек множеств С до второй гиперплоскости была равна сумме расстояний от точек множества В, ошибочно идентифицированных как точки множества С, до этой гиперплоскости, и, во-вторых, вектор, представляющий собой сумму неверно идентифицированных точек с коэффициентами, равными расстояниям от этих точек до гиперплоскостей, был параллелен вектору нормали разделяющей гиперплоскости I**

Третья глава посвящена численным методам идентификации двух и трех множеств, принадлежащих многомерному пространству, при разработке которых использовались результаты, полученные в главах 2 и 3, а также теория точных штрафных функций и метод проекции градиента Для задачи идентификации точек двух множеств Л и В £ К" на ос-

новании критерия оптимальности РП в смысле функционала Р2 (/), выведенного в главе 1, строится алгоритм оптимального разделения множеств при помощи гиперплоскости из пространства Суть алгоритма заг-

ключается в построении такого набора параметров РП = [й*,^,^], при котором выполняется необходимое условие минимума штрафной функции Фг^, а именно субдифференциал штрафной функции Фг(/) содержит точку {0п+1} (начало координат в пространстве Кп+1) На каждом шаге алгоритма в качестве направления спуска выбирается направление, противоположное вектору минимального элемента субдифференциала функции Ф2 (Т) При этом производится проектирование данного направления на целевое множество П = = [й, /] 11 € К", ||1|| = М € м} С Кп+1 Величина шага в выбранном направлении вычисляется исходя из условия минимальности функции Фг(^) В конце главы доказывается сходимость предложенного алгоритма

Для задачи идентификации точек трех множеств Л, Б и С € К" на основании критерия оптимальности РП в смысле функционала Р^ (/), выведенного в главе 2, строится алгоритм оптимального разделения множеств при помощи двух параллельных гиперплоскостей из пространства М"-1 Суть алгоритма заключается в построении такого набора параметров РП I" = [(/",с?",при котором выполняется необходимого условия минимума штрафной функции Фг^, а именно субдифференциал штрафной функции содержит точку {0п+2} (начало координат в пространстве тп+2) Общая схема алгоритма аналогична алгоритму идентификации

двух множеств, приведенному выше В конце главы также доказывается сходимость предложенного алгоритма

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

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

Приложение содержит описание и тексты программ в среде MATLАВ

Основные результаты, выносимые на защиту На защиту выносятся новые методы оптимального разделения двух и трех множеств многомерного пространства, предложенные в диссертационной работе

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

сходимость данного алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

г

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

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

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

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

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

Подписано в печать «12» сентября 2008 г Формат 60x84/16 Бумага офсетная Печать офсетная Уел печ л 1 Тираж 100 экз Заказ №456

Типография «Восстания -1» 191036, Санкт-Петербург, Восстания, 1

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

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Задача идентификации двух множеств в многомерном пространстве

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

§2. Идентификация двух множеств с помощью разделяющей гиперплоскости

§3. Исследование оценочного функционала Fl{l).

§4. Исследование оценочного функционала Г).

Глава 2. Задача идентификации трех множеств в многомерном пространстве

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

§2. Идентификация трех множеств с помощью двух параллельных разделяющих гиперплоскостей.

§3. Исследование оценочного функционала Fl(l).

§4. Исследование оценочного функционала (I).

Глава 3. Методы идентификации двух и трех множеств в многомерном пространстве.

§1. Алгоритм решения задачи идентификации двух множеств.

§2. Алгоритм решения задачи идентификации трех множеств.

Глава 4. Применение методов идентификации множеств к решению задач прогнозирования эффективности лечения РМЖ.

§1. Описание базы данных РМЖ (Мангасарян) и постановка задачи

§2. Содержание и результаты проведенных исследований.

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 заданы два конечных множества точек А и В:

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

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

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)dÜ min ||а — Ь||2 = ||а* — 6*||2. а€Л, b€B

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

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

Zi

Г (с, Г) = (cj*) + if < -h\a*-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={bj\jeJ=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 — A\JB\JC, рассмотрим РП следующего вида: если г (у, 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-00276).

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.

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

2. Барабаш Ю.Л., Барский Б.В., Зиновьев В.Т. и др. Вопросы статистической теории распознавания. М.: Советское радио, 1967.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17. Демьянов В.Ф. Условия экстремума и вариационное исчисление. М.: Высшая Школа, 2005. 335 с.

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

19. Демьянов В.Ф., Демьянова В.В., Кокорина A.B., Моисеенко В.М. Прогнозирование эффективности химиотерапии при лечении онкологических заболеваний // Вестник Санкт- Петербургского университета. Серия 10, вып. 3, 2006, с. 30-36.

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

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

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

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

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

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

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

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

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

29. Зубова O.A. Математическое моделирование самообучающихся систем// В кн. А.Ф. Зубова <Математические методы моделирования промышленных процессов и технологий>. СПб: Изд-во НИИ Химии СПбГУ, 2005. С. 336-342.

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

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

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

33. Зубова O.A. Применение квазидифференциального исчисления к решению задач идентификации. СПб: Изд-во НИИ Химии СПбГУ, 2005, с. 18

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

66. DeCoste D. and Scholkopf B. Training invariant support vector machines. Machine Learning 46, 2002, pp. 161-190.

67. Demyanov V.F. Mathematical diagnostics via nonsmooth analysis. Optimisation Methods and Software. 2005. Vol 20, No 2-3. pp. 197-218.

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

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

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

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

72. Kokorina A.V. Unsupervised and supervised Data Classification Via Nonsmooth and Global Optimization. Top, Volume 11, Number 1. June 2003. Sociedad de Estadística e Investigación Operativa, Madrid, Spain, pp. 86-89.

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

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

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

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

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

78. Moor A. Breast-Cancer Therapy — Looking Back to the Future New England Journal of Medicine. 2007. Vol 375, No 15. pp. 1547-1549.

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

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

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

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

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

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

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

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

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