Содержание к диссертации
Введение
Глава 1. Ранжирование параметров в задачах обработки данных 17
1.1. Случай нормально распределенных параметров 17
1.2. Случай дискретных значений 26
1.3. Ранжирование произвольных параметров 29
Глава 2. Методы разделения множеств и их применение 33
2.1. Метод разделения двух множеств гиперплоскостью 33
2.2. Результаты ранжирования некоторых баз данных 36
2.3. Результаты разделения множеств 49
Глава 3. Применение методов ранжирования и разделения множеств гиперплоскостью к решению задачи прогнозирования эффективности лечения желчнокаменной болезни 67
3.1. Описание баз данных и постановка задачи 67
3.2. Базы данных медицинской академии по ЖКБ 69
3.3. Результаты исследования 72
Заключение 85
Литература 86
Приложение
- Случай дискретных значений
- Результаты ранжирования некоторых баз данных
- Базы данных медицинской академии по ЖКБ
- Результаты исследования
Введение к работе
Актуальность темы. Многие практически важные задачи, например, задачи распознавания образов, классификации, технической и медицинской диагностики, идентификации, обработки экспериментальных данных, спектрального анализа, могут быть описаны математическими моделями, в которых требуется "отделить" два или более множества. Часто указанные множества "неразделимы". Поэтому возникает задача идентификации как можно большего числа точек этих множеств.
В задачах медицинской диагностики оптимизационный подход к решению этой задачи был предпринят в 30-е годы Р. Фишером [59] (который разработал линейный дискриминантный анализ). В настоящее время эти задачи занимают ведущее место в теории обучающих машин, в задачах искусственного интеллекта. Для решения указанных задач существует несколько подходов (чисто статистический подход [4, 5, 7, 19, 21, 32, 33, 71], метод опорных векторов В.Вапника [9, 57, 77], метод машинного обучения [31,44, 45, 68], метод построения ядра [56, 76], метод обработки данных с помощью линейного программирования [51, 61, 66, 67], кластерный анализ [46, 52, 60, 62, 69]). К сожалению, не существует универсального метода, пригодного для решения всех задач распознавания, идентификации и диагностики. Поэтому, несмотря на наличие богатого арсенала средств для решения задач идентификации и множества успешно решенных практических проблем, интерес к этой тематике не ослабевает. Это объясняется многообразием новых постановок, индивидуальностью сложности реальных задач, необходимостью строить всё более усовершенствованные модели, которые адекватно описывали бы указанные реальные задачи. Вот почему в последние годы многие математики, до этого работавшие в других областях, обратили свое внимание на проблемы диагностики. Так, С. Смейл опубликовал статью в журнале "Bulletin of the American
Mathematical Society" (vol. 39, N 1, 2002), посвященную математическим основам обучения, где излагается статистический подход к решению задач распознавания и идентификации. Статистический подход оказался эффективным при решении массовых задач, где удаётся собрать достаточно достоверную статистику [1, 2, 3, 34]. В случае отсутствия такой статистики практическая ценность разработанных подходов существенно снижается. Этот факт привел к тому, что 60-ые годы в разных странах стали активно привлекать так называемые оптимизационные методы. Одними из первых этими вопросами занимались И.М. Гельфанд [11], Ю.И.Журавлев [20], Б.Н. Козинец [24], О.Л. Мангасарян [65], А.А. Первозванский [35], Б.Т. Поляк [37], А.И. Пропой [15], Дж.Б. Розен [73], В.Н. Фомин [44], ЯЗ. Цыпкин [15, 37], В.А. Якубович [45] и другие.
Интерес к оптимизационным методам в последние годы усилился, поскольку, с одной стороны, современный уровень развития вычислительной техники позволяет реализовать многие методы и алгоритмы, которые ранее невозможно было использовать ввиду их громоздкости, с другой стороны, современное состояние теории моделирования позволяет обрабатывать огромные массивы экспериментальных данных в различных областях (в медицине, биологии, химии) с целью выявления новых закономерностей (возникло даже направление, называемое искусственным интеллектом).
Названные выше задачи и создают направление в теории оптимизации, которое можно назвать математической диагностикой.
Упомянутые статистический и оптимизационный подходы к решению задач математической диагностики удачно дополняют друг друга: обработка одних и тех же баз данных с помощью обоих подходов позволяет получить более достоверную информацию и предоставляет лицу, принимающему решение, возможность выбора наиболее рационального решения.
Задачи математической диагностики представляют хороший полигон для проверки эффективности математических моделей, численных методов их исследования, отработки и усовершенствования методик идентификации и самих классификаторов (идентификаторов) и критериев. При этом появляются новые математические задачи и возможность практического использования ранее казавшихся абстрактными математических результатов. Хорошие модели существенно упрощают и улучшают процесс проектирования.
Настоящая работа находится в русле оптимизационного подхода (развиваемого сейчас, в частности, в работах Ю.Г. Евтушенко, A.M. Рубинова и их учеников), поэтому мы не будем заниматься статистическими аспектами обработки баз данных.
Как уже отмечалось, многие из упомянутых задач сводятся к разделению двух или более часто неразделимых множеств. Для этого важно иметь сравнительно простой критерий, с помощью которого можно классифицировать точки. При выбранном идентификаторе (называемом также классификатором, правилом идентификации или решающим правилом) - функционале, по значению которого судят о принадлежности данной точки тому или другому множеству - качество идентификации оценивается "естественным" критерием - количеством ошибочно идентифицированных точек. Поскольку такой критерий обычно описывается существенно разрывной функцией, то приходится этот естественный критерий качества заменять некоторым "суррогатным" функционалом, который может быть изучен методами математического программирования. В основе существующих оптимизационных методов лежат методы линейного и квадратичного программирования [13, 14, 22, 35], которые существовали и были наиболее эффективны во время создания указанных теорий машинного обучения (60-е - 80-е годы XX века). С тех пор методы оптимизации получили дальнейшее развитие, появились негладкий анализ и недифференцируемая оптимизация.
7 В отличие от изложенных подходов (основанных на линейном и квадратичном программировании), теперь эти задачи можно решать, используя негладкие критерии, которые лучше аппроксимируют "естественные" критерии качества. Применение методов линейного и квадратичного программирования к решению задач математической диагностики привели к созданию так называемого линейного дискриминантного анализа [43]. На повестке дня — создание негладкого дискриминантного анализа, основанного на использовании негладких моделей и применении методов негладкого анализа и недифференцируемой оптимизации [16, 17, 47, 49, 58, 75]. Можно ожидать, что негладкий дискриминантный анализ позволит улучшить качество идентификации и распознавания и расширить арсенал имеющихся средств для решения задач математической диагностики.
Поясним задачу идентификации точек множеств.
Пусть AczR" и BczR" - некоторые замкнутые ограниченные множества. Требуется указать достаточно простой критерий для различения элементов множеств А и В.
Точка с є A U В считается идентифицированной, если можно указать, что либо с єА\В, либо с єВ\А. Если с є АПВ, то точка с считается существенно неидентифицируемой.
Вначале предположим, что А и В - выпуклые множества в R". Возможны два случая: 1)АПВ = 0, 2) А[)Вф0.
Случай Л П В = 0 (множества А и В не пересекаются). По теореме отделимости (см. [17, 39]) существуют вектор у є R" и число d є R, такие, что
(x,y) + d>0 VxeA, (1)
(x,y) + d<0 VxeB. (2)
Для того чтобы найти z = [у, d] є Rn+l, удовлетворяющее (1) и (2), достаточно найти
f(A,B)= mm \\а-Ь\\2=\\ а -Ь*\\2.
аєА,ЬєВ
Поскольку АПВ = 0,то f(A,В)>0.
d-Ъ" ,. (а+Ь* Л || Ъ" ||2 -|| a f
Положим v =— —, а = ,v - ...
По необходимому условию минимума (см., например, [17]), пара z*— [у*,d*] удовлетворяет неравенствам:
(x,y) + d*>-\\a-b'\\>0 \/хєА, (3)
(x,y) + d* <--\\а -Ь*\\<0 \/хеВ. (4)
Функция r(x,z*) = (x,y*) + d* может быть использована как критериальная функция.
Пусть известно, что с є A U В. Неравенства (3) и (4) означают, что если r(c,z*) >0,то с є А, если r(c,z*)< 0, то с є В.
Таким образом, в случае, когда множества А и В выпуклые и не пересекаются, точки множеств А и В можно идентифицировать с помощью линейной функции г {с, z ), причем такая идентификация -точная: каждая точка ceAljB идентифицирована правильно. Этот же подход применим и в случае, когда множества А и В не обязательно выпуклые, но их выпуклые оболочки не пересекаются. И в этом случае точная идентификация возможна с помощью линейной критериальной функции, которую можно построить, как описано выше, взяв в качестве множеств выпуклые оболочки множеств А и В.
СлучанАПВф0. В случае, когда соАПсоВ Ф 0 (т.е. когда пересечение выпуклых оболочек множеств А и В непусто), точная идентификация с помощью линейной
9 критериальной функции невозможна. Тем не менее, можно ставить задачу о нахождении линейной критериальной функции, наилучшей в том или
ином смысле. Точнее говоря, пусть задана линейная функция r(c,z*). Будем использовать следующее правило идентификации: для ceA[jB будем считать, что
с є А, если r(c,z*) > О,
с є В, если r(c,z*)<0.
В случае r(c,z*) = Q считаем точку с неидентифицированной. Очевидно, что при таком правиле идентификации часть точек может быть неверно ' идентифицирована. Задача состоит в нахождении такого z*, чтобы количество неверно идентифицированных точек (либо их относительное количество) было как можно меньше. Выбор функционала, который требуется минимизировать, зависит от поставленной задачи.
Критериальную функцию можно выбирать и не обязательно в классе линейных критериальных функций. В методах опорных векторов [53, 54, 56] изучаются различные классы критериальных функций. Все эти методы в конечном итоге сводятся к линейным критериальным функциям (с помощью перехода в расширенное пространство признаков).
Целью диссертационной работы является проведение исследований, направленных на развитие оптимизационных методов для решения задач математической диагностики, а также разработка методик идентификации и построение решающих правил (классификаторов).
Конечным результатом исследований является создание алгоритмического и программного обеспечения для применения предложенных методов к решению соответствующих прикладных задач, а также проверка (тестирование) новых правил идентификации (алгоритмов) на реальных базах данных и сравнение с результатами применения других методов.
Методы исследований. Построение новых методов ранжирования параметров и идентификации точек множеств осуществляется с использованием современного аппарата математического анализа, теории вероятностей и математической статистики, математического программирования, а также различных методов обработки результатов экспериментов.
Научная новизна.
В диссертационной работе предложены новые методы ранжирования параметров (способы выбора наиболее существенных признаков при первоначальной обработке экспериментальных данных). В частности, разработан упрощенный алгоритм ранжирования (в случае, когда параметры подчиняются нормальному закону распределения).
Предложены новые методы оптимального разделения двух множеств (с помощью гиперплоскости).
Разработано программное обеспечение (разработаны алгоритмы и созданы программы) для применения предложенных методов.
Практическая и теоретическая значимость. Теоретическая значимость работы определяется тем, что в ней предложены новые математические методы и вычислительные алгоритмы для решения задач математической диагностики.
Ранжирование параметров дает возможность выбрать наиболее информативные (наиболее существенные) из них и работать в пространстве гораздо меньшей размерности, что позволяет облегчить и ускорить процесс идентификации. Применение предложенных методов идентификации совместно с другими методами статистического и оптимизационного подходов позволит получить более достоверную информацию и существенно повысить эффективность решения практических задач медицинской и . технической диагностики, распознавания образов и идентификации.
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на XIII международной конференции «Проблемы теоретической кибернетики» (г. Казань, 2002); на первой Российско-Французской международной конференции «Модели Долголетия, Старения и Деградации» («Longevity, Aging and Degradation Models») (г. Санкт-Петербург, 2004), на XXXII, XXXIII, XXXIV и XXXV научных конференциях «Процессы управления и устойчивость» факультета прикладной математики и процессов управления СПбГУ (г. Санкт-Петербург), а также на семинарах кафедры математической теории моделирования систем управления СПбГУ.
Эффективность предлагаемых методов ранжирования и идентификации подтверждается сравнением с известными в литературе методами на конкретных базах данных, а также решением задачи прогнозирования эффективности лечения желчнокаменной болезни (на базе данных, предоставленной Военно-медицинской академией им. СМ. Кирова).
Связь с научными программами. Работа выполнена при поддержке Российского фонда фундаментальных исследований (Код проекта РФФИ №03-01-00668).
Публикации. По результатам выполненных исследований опубликовано 6 печатных работ [25] - [28], [63], [64].
Структура работы. Содержание диссертационной работы включает в себя данное введение, список основных обозначений, три главы, содержащие основные результаты работы, заключение, три приложения, список литературы из 78 наименований и имеет общий объём 119 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении рассматривается краткая история вопроса, актуальность темы, приводится сжатое изложение полученных результатов.
В предлагаемой работе изучаются только некоторые вопросы математической диагностики. Так, практические базы экспериментальных
данных являются обычно многомерными и возникает задача разделения множеств точек двух (или более) множеств в многомерных пространствах. Однако опыт решения реальных задач показывает, что достаточно надежную идентификацию можно провести, используя только небольшую часть имеющихся параметров, что может существенно облегчить и ускорить процесс идентификации [12, 18, 19, 29, 30, 40, 41, 48, 53, 69, 78].
В главе 1 описываются алгоритмы ранжирования параметров.
В параграфе 1.1 рассматривается случай, когда значения параметров подчиняются нормальному закону распределения.
Пусть заданы множества AaR" и BaR":
A = {at є^\ієІ},В = {Ь; eR"\jeJ},
где I = l:Nlt J = l:N2, a, =(an,ai2,...,ain), Ъ} =(Ьп,Ь.2,...,Ьр). Предположим, что для каждого к aik и bjk - это значения случайных величин Ак и 5t, подчиняющихся нормальному закону распределения. Вычисляем математические ожидания и дисперсии Ак и Вк, затем строим
функции плотности распределения данных величин - fk и fk,
соответственно. В качестве критерия значимости параметра возьмем площадь пересечения подграфиков плотностей распределения
+00
Sk = \mm\fkA(x\fk{x)\dx. Наименьшее значение площади Sk
—00
определяет наиболее существенную координату.
Также в параграфе 1.1 показано, что при проведении практических
вычислений достаточно заменить подграфики функций fk и fk
треугольниками с основаниями [Ек —так ,Ек +так] и
[Ек -тсгк ,Ек +тсгк , соответственно, и высотами hk =\/тсгк и
hk =\/тсгк , соответственно, где т = 2.5 или т = 3, в соответствии со значениями функции Лапласа.
13 В параграфе 1.2 предложен метод идентификации для проведения ранжирования параметров в дискретном случае, когда координаты ajk и
bjk принимают только конечное число значений: vu,....,vmiJt (причем тк
сравнительно невелико). Построим множества:
^={flftlI'e/,flfft=vlt} Vrel:mk,
Brk={bjk\jeJ,bjk=vJ Уге\:тк.
В качестве критерия значимости параметра выберем величину
4* I \Brk
1 ^ -/V="Z niin
2* гєкть
. Чем меньше значение juk, тем более
существенной является к-ая координата.
В параграфе 1.3 представлен метод ранжирования, основанный на построении идентификационного правила (согласно структуре множеств) и проведении разделения элементов множества (по данному правилу). Критерием значимости будет являться количество (часть) ошибочно определенных точек. Наименьшее значение определит наиболее существенную координату. Данный метод, в частности, можно использовать, когда параметры принимают произвольные значения и закон распределения неизвестен.
В главе 2 идёт речь о некоторых методах разделения множеств и приведены результаты их применения.
В параграфе 2.1 обсуждаются методы разделения двух множеств гиперплоскостью. В частности, предложен новый критерий (функционал) для выбора нормали разделяющей гиперплоскости. Идея основана на выборе самого информативного направления.
Пусть заданы множества A<^Rn и В a R":
А = {а, eR"\ieI} nB = {bJ. eRn\jeJ},
где I = l:Nl9J = l:N2, at ={aa,an,...,ain), bj.= {bn,b.2,...,bjn).
14 Введем следующий функционал:
[ЕА 00 - Ев (х) + таА (х) + тсгв (х)]:
F(x) =
&2А(х) + а2в(х)
где хе R",
N, ш N, /е/
і " -1 т і
Ев(х) = ^-^.(х) = ^-^(Ь;.,х) = (Ев,х):
J\2 /ЄJ I\2 JGJ
<(х) = ^-^-(х)-Е2А(х) = ^(^хУ-(ЕА,хУ,
Nx ш Nx iei
1(х) = ^%(х)-ЕІ(х)=±-^,х)2-(Ев,х)2.
IV2 jeJ I\2 jeJ
Найдём вектор x* є R", который доставляет минимум данному функционалу, т.е. решаем задачу min F(x) = F(x*).
xeR"
Возьмём x" в качестве нормали разделяющей гиперплоскости. Отметим, что.Р(д:) - это площадь пересечения треугольников в проекции
на вектор х (умноженная на 2т2), х* - это самое информативное направление, так как площадь пересечения минимальна. Разделение множеств проводим гиперплоскостью: L(a) = {х \ h{x, а) = 0},
где h(x,а) = (х-х0 (а),х*), х0(a) = аЕА + (і - а)Ев и а є [0,1]. Сформулируем правило идентификации.
Пусть с = (с1,...,сп)є A\JВ. Отклонение точки с от гиперплоскости
(с х*) — (х (ее} X*}
Ь(а) вычисляется по формуле: r(c, Ь(а)) = ——-— —-.
II х* || Тогда если г(с,Ь(аУ) < 0, то считаем, что с є А; если r(c,L(a)) > 0, то считаем, что с є В;
если же r(c, L(a)) = 0, то точка с является неидентифицируемой (данным идентификационным правилом).
Далее проводим минимизацию по а, то есть выбираем а таким образом, чтобы количество ошибочно определенных и неидентифицированных точек было минимальным.
В параграфе 2.3 приведены итоги ранжирования нескольких широко известных баз данных, проведенного по методам, предложенным в параграфах 1.1 и 1.2. Для сравнения в приложении 2 приведены результаты другого алгоритма определения наиболее информативных признаков, полученные A.M. Багировым и др. в Балларатском университете (Австралия).
Затем была проведена идентификация элементов данных баз. Результаты применения методов оптимального разделения, описанных в параграфе 2.1, представлены в параграфе 2.3. Они свидетельствуют об эффективности предлагаемых нами процедур идентификации.
В главе 3 приводятся некоторые результаты применения метода оптимального разделения к решению задачи прогнозирования эффективности лечения желчнокаменной болезни.
В параграфе 3.1 приведено описание баз данных и сформулирована постановка задачи исследования.
Исследование проводилось на материале двух баз данных, предоставленных Кафедрой общей терапии Военно-медицинской академии им. СМ. Кирова. Они были получены с помощью различных методик измерений, что привело к различной степени надежности прогноза эффективности лечения.
Каждая база была представлена двумя группами точек. Первая группа содержала данные анализов пациентов, у которых в результате курса лечения конкремент (камень) полностью растворился. Вторая группа -данные анализов пациентов, у которых произошло только частичное растворение конкремента.
Задача состояла в том, чтобы по результатам первичного обследования дать прогноз эффективности лечения данным лекарственным препаратом.
В параграфе 3.2 представлены рассматриваемые базы.
Результаты исследования приведены в параграфе 3.3.
В заключении приведен краткий обзор проделанных исследований, сформулированы основные результаты диссертационной работы.
В приложении 1 дано краткое описание баз данных, которые были использованы в численных экспериментах.
Тексты программ (написанные на языке Matlab), применяемых в ходе проводимых исследований, представлены в приложении 3.
Случай дискретных значений
Теперь рассмотрим случай, когда координаты aik и bjk принимают только конечное число значений: vlk,....,vmkk (причем тк сравнительно невелико). Чтобы проиллюстрировать идею, предположим, что Nl= N2 = N. Построим множества: Сформулируем следующее правило идентификации с помощью только к-ой координаты. Пусть с = (с,,..., сл) є A[jB. Тогда существует гк(с)е\:тк, такое, 4Tock=vrk(c). ., Если I Агк(сп 1 1 вгк(с)к I то считаем, что с є А; если АГк(с)к \ \ ВГк(с)к , то считаем, что с є В; если АГк(с)к = В {с)к , то считаем, что с не может быть идентифицирована (с помощью рассматриваемого правила идентификации по к-ой координате). Здесь G - количество элементов множества \G\. Согласно такому правилу, число ошибочно определенных точек (по к-ой координате) равно Значение juk = Mk/2N - это часть от общего количества элементов обоих множеств, которая была неправильно определена (согласно нашему правилу идентификации с помощью только А:-ой координаты). Теперь расположим значения juk в возрастающем порядке. Чем меньше значение /лк, тем более существенной является к-ая координата. Предположим, что при некотором к параметр принимает дискретные значения: Количество элементов в обоих множествах одинаковое: N = 13. Математические ожидания элементов множества Ак и элементов множества Вк равны. Также совпадают значения дисперсий. ЕАк = Евк = 2.0769; DAk = DBk = 1.6095. Тем не менее, глядя на диаграмму, легко заметить, что большая часть элементов множества Ак имеют значения 0 и 3, а большая часть элементов множества Вк имеют значения 1 и 2: Используем описанное выше правило идентификации.
Пусть с = (с]5...,сл)є A\JB. Если ск = 0, либо ск = 3, то считаем, что с є А; если ск = 1, либо ск = 2, либо ск = 6, то считаем, что с є В. Согласно такому правилу, число ошибочно определенных точек равно Мк = min(3,0) + min(l,4) + min(l,7) + min(8,l) + min(0,l) = 3. Значение juk = Mk/2N =3/26 = 0.1154, т.е. 3 из 26 определены неверно. Таким образом, если мы будем проводить идентификацию по к-ому параметру (используя данное правило идентификации), мы получаем около 90% правильно определенных от общего числа элементов. Теперь рассмотрим случай, когда координаты aik и bjk принимают только конечное и сравнительно небольшое число значений: vlk,....,v к и N N2. Построим множества: Сформулируем следующее правило идентификации с помощью только к-ой координаты. идентифицирована. (Здесь G \ - количество элементов множества G.) Согласно такому правилу, часть ошибочно определенных (неправильно идентифицированных) точек от общего числа точек обоих множеств (точек, прошедших проверку) есть значения /лк в возрастающем порядке. Чем меньше значение juk, тем более существенной является А:-ая координата. Замечание 1.2.1. Если некоторые параметры распределены по нормальному закону, а другие принимают дискретные значения, то можно вычислять либо Sk, либо 2juk (в зависимости от типа распределения) и упорядочивать полученные значения по возрастанию. Заметим, что Sk также может быть рассмотрена как часть (удвоенная) ошибочно определенных точек. Замечание 1.2.2. Описанные здесь (в параграфе 1.2) и далее в параграфе 1.3 правила координатной идентификации введены только для проведения ранжирования параметров (координат). Правила идентификации точек множеств (А и В) обсуждаются в главе 2. В параграфе 1.1 мы проводили ранжирование в предположении, что известен закон распределения величин. В случаях, когда закон не известен, можно использовать «прямой» метод ранжирования. Предположим, что для каждого к аік и bjk - это значения случайных величин Ак и Вк, закон распределения которых неизвестен. Предположим, что множества А и В конечны (тогда / = 1: N J = 1: N2). Пусть х є Rl. Для каждого параметра к построим множества: если большинство ajk находятся правее большей части элементов Ъ к; если большинство ал находятся левее большей части элементов bjk. А - это неправильно определенные элементы множества А, а В , соответственно, неправильно определенные элементы множества В. Замечание 1.3.1. Если заранее неизвестно, как расположены точки (с какой стороны относительно х расположена большая часть элементов одного из множеств), то рассматриваются оба варианта (и из них выбирается более подходящий). Сформулируем следующее правило идентификации с помощью только к-ок координаты. Пусть с = (clv..,cn)e A\JB. Если ск х, то будем считать, что с є А; если ск х, то считаем, что с є В; если ск = х, то с не может быть идентифицирована (с помощью рассматриваемого правила идентификации). Решаем следующую задачу:
Результаты ранжирования некоторых баз данных
В этом параграфе представлены результаты численных экспериментов. Для описания результатов использованы следующие обозначения: vrk - значение параметра; JVj - количество элементов множества А; N2 - количество элементов множества В; \А_ — - часть множества А, которая состоит из элементов г со значениями vrk; \В — - часть множества В, которая состоит из элементов N2 со значениями vrk; juk - часть ошибочно определенных точек (от общего числа точек обоих множеств). Программы были написаны на языке Matlab, вычисления проводились на PC с CPU INTEL PENTIUM III 533Мгц. Тексты программ приведены в приложении 3. Австралийский кредит (Australian credit) База данных Австралийский кредит состоит из двух классов, 690 наблюдений и 14 параметров, 8 из которых являются категорическими (качественными) (остальные 6 признаков - непрерывными). Замечание 2.2.1. Более подробное описание баз приведено в приложении 1. Ранжирование непрерывных параметров проводилось по методу, описанному в параграфе 1.1. Полученные результаты приведены в таблице 2.2.1. В первом столбце таблицы указаны номера рассматриваемых параметров (к), во втором столбце приведены значения площадей пересечения подграфиков плотностей (Sk). Для сравнения были проведены расчеты в случае аппроксимации подграфиков плотностей треугольниками - значения площадей пересечения треугольников при различных значениях параметра т представлены в четвертом, шестом, восьмом и десятом столбцах. В третьем, пятом, седьмом, девятом и одиннадцатом столбцах проведена нумерация параметров в порядке уменьшения информативности в соответствии со значениями площадей (нумерация в порядке возрастания Sk). Анализируя результаты вычислений, приведенные в таблице 2.2.1, можно сделать вывод, что для рассмотренной базы аппроксимация треугольниками плотностей распределения с параметром т=2.5 даёт относительно точные значения площади пересечения подграфиков плотностей распределения, но при этом она точно сохраняет их последовательность в порядке возрастания. Поэтому для уменьшения времени обработки (ранжирования) данных мы можем применять изложенный выше метод аппроксимации с помощью треугольников.
В результате проведения ранжирования мы получили, что наиболее существенным среди непрерывных параметров (поведение которых можно считать подчиняющимся нормальному закону распределения) является 14-ый параметр ( = 0.1764), а наименее - 13-ый ( = 0.9060). Для ранжирования дискретных параметров был использован метод, описанный в параграфе 1.2. Результаты представлены в таблице 2.2.2. В первом столбце таблицы указаны номера рассматриваемых параметров (к); во втором и в четвертом столбцах приведены значения (yrk), которые принимают параметры первого множества (обозначенного А) и второго множества (обозначенного Л), соответственно; в третьем и в пятом - части множества А и В, соответственно, которые состоят из элементов с данными значениями (см. обозначения в начале данного параграфа). Шестой столбец содержит значения параметра juk - часть ошибочно определенных точек от общего числа точек обоих множеств, согласно предложенному правилу. В последнем столбце проведена нумерация параметров в порядке уменьшения информативности в соответствии со значениями параметра juk (нумерация в порядке возрастания juk ). Как было предложено в замечании 1.2.1, если некоторые параметры распределены по нормальному закону, а другие принимают дискретные значения, то можно вычислять либо Sk, либо 2juk (в зависимости от типа распределения) и распределять в порядке возрастания, поскольку Sk может быть рассмотрена как удвоенная часть ошибочно определенных точек. В таблице 2.2.3 представлены общие итоги - сведены результаты ранжирования непрерывных и дискретных параметров. В первом столбце таблицы 2.2.3 указаны номера рассматриваемых параметров (к); во втором столбце приведены значения площадей пересечения подграфиков плотностей (Sk) для непрерывно распределенных параметров и удвоенное значение параметра juk, если
Базы данных медицинской академии по ЖКБ
Результаты исследования В этом параграфе для описания результатов использованы следующие обозначения: number - номера параметров, используемых при разделении; Р - процент правильно определенных точек; Pi - средний процент (среднее значение процента) правильно определенных точек при проведении идентификации точек контрольного множества; Рг - средний процент (среднее значение процента) правильно определенных точек при проведении идентификации точек обучающего множества; а -оптимальное значение параметра а ; F - минимальное (по х) значение функционала F(x): F = min F(x) = F(x ); X x - нормаль разделяющей гиперплоскости (вектор, минимизирующий F(x)); t - время вычисления (в секундах). ОРГ-1 - оптимальное разделение гиперплоскостью L(a) = {x\h(x,a) = 0}, где а є [ОД], h(x,a) = (x-x0(a),EA-EB), х0(а) = аЕА+(\-а)Ев; ОРГ-2 - оптимальное разделение гиперплоскостью L(a) = {x\h(x,a) = 0}, где а є [ОД], h(x,a) = (x-x0(a),x ), х0(а) = аЕА + (і - а)Ев, х - вектор, минимизирующий F(x). Программы были написаны на языке Matlab, вычисления проводились на PC с CPU Intel Pentium III 533МГц. Тексты программ приведены в приложении 3. Ранжирование параметров проводилось по методу, описанному в параграфе 1.1. Полученные результаты для сокращенной базы приведены в таблице 3.3.1, для полной базы - в таблице 3.3.2. В первом столбце таблицы указаны номера рассматриваемых параметров (к), во втором столбце приведены значения площадей пересечения подграфиков плотностей (Sk). Для сравнения были проведены расчеты в случае аппроксимации подграфиков плотностей треугольниками - значения площадей пересечения треугольников при различных значениях параметра т представлены в четвертом, шестом, восьмом и десятом столбцах. В третьем, пятом, седьмом, девятом и одиннадцатом столбцах проведена нумерация параметров в порядке уменьшения информативности в соответствии со значениями площадей (нумерация в порядке возрастания Sk). В результате ранжирования по полной базе параметры были упорядочены следующим образом (в порядке уменьшения информативности): 2, 1,7, 4, 5, 3, 9, 6, 8. При разделении гиперплоскостью L(a) = {x\h(x,a) = 0}, где h(x,a) = (x- результаты (см. таблицу 3.3.3). При рассмотрении всех параметров по сокращенной базе наилучший результат - 92% правильно определенных точек - был получен при а =0.55-0.68. При рассмотрении двух наиболее существенных параметров (по результатам ранжирования) - 6-го и 8-го получили 96% правильно определенных точек при а = 0.57 - 0.62. При рассмотрении всех параметров по полной базе наилучший результат - 75.76% правильно определенных точек - был получен при а =0,0.01,0.19-0.31.
При рассмотрении двух наиболее существенных параметров (по результатам ранжирования) - 2-го и 1-го получили 80.3% правильно определенных точек при а = 0.09 - 0.13. Сравнивая результаты применения метода десятикратной проверки с результатами, полученными при рассмотрении 100% данных, можем сделать следующие выводы. По сокращенной базе: при идентификации точек обучающего множества (обучающее множество содержит 90% от исходных данных) средний результат существенно не изменился (можно считать несущественными колебания в интервале [-2.2,+0.2] процента в связи с малой размерностью базы); при идентификации точек контрольного множества (10% от исходного) средний результат также не ухудшился (уменьшение на 2% при рассмотрении всех параметров можно считать несущественным в связи с малой размерностью базы), а в ряде случаев незначительно улучшился (на 4%). По полной базе: при идентификации точек обучающего множества средний результат существенно не изменился (ухудшился на 0.2 процента или улучшился меньше, чем на 1.3 процента, что можно объяснить погрешностью вычислений); при идентификации точек контрольного множества средний результат улучшился (на 4-10%), что может свидетельствовать о неоднородности базы (например, о наличии существенно неточных измерений). Замечание 3.3.1. Чтобы дать объективную оценку, сравнивая результаты применения метода десятикратной проверки с результатами, полученными при рассмотрении 100% данных, необходимо учитывать количество точек в базе данных. В частности, для сокращенной базы, содержащей небольшое количество точек, полученную разницу в несколько процентов можно считать несущественной. Затем разделение проводим гиперплоскостью L{a) = {х \ h(x, а) = 0}, вектор, доставляющий минимум F(x). При построении гиперплоскости и проверке сначала рассматриваем все 100% данных. Результаты приведены в таблице 3.3.5. вектор, минимизирующий F(x).
Результаты исследования
Замечание 3.3.1. Чтобы дать объективную оценку, сравнивая результаты применения метода десятикратной проверки с результатами, полученными при рассмотрении 100% данных, необходимо учитывать количество точек в базе данных. В частности, для сокращенной базы, содержащей небольшое количество точек, полученную разницу в несколько процентов можно считать несущественной. Затем разделение проводим гиперплоскостью L{a) = {х \ h(x, а) = 0}, вектор, доставляющий минимум F(x). При построении гиперплоскости и проверке сначала рассматриваем все 100% данных. Результаты приведены в таблице 3.3.5. вектор, минимизирующий F(x). При рассмотрении всех параметров по сокращенной базе наилучший результат - 96% правильно определенных точек - был получен при а = 0.42 - 0.56, 0.59 - 0.65. При рассмотрении двух наиболее существенных параметров (по результатам ранжирования) - 6-го и 8-го получили 96% правильно определенных точек при а = 0.58 - 0.69. Разделение по четырем параметрам - 6, 8, 3, 7 (а также по пяти и шести признакам) дало превосходный результат - 100% правильно определенных точек. При рассмотрении всех параметров по полной базе наилучший результат - 86.36% правильно определенных точек - был получен при а =0.42-0.45. При рассмотрении двух наиболее существенных параметров (по результатам ранжирования) - 2-го и 1-го получили 81.82% правильно определенных точек при а = 0.36. Проиллюстрируем результаты первого и второго методов на двумерном случае (см. рис. 1 и рис. 2). Для сокращенной базы будем рассматривать значения 6-го параметра (ось абсцисс) и 8-го (ось ординат) как наиболее значимых.
Для полной базы будем рассматривать значения 2-го параметра (ось абсцисс) и 1-го (ось ординат). Обозначения на рисунках: звездочки ( )- элементы «излечившегося» множества, обозначим множество А; треугольники ( ) - элементы «неизлечившегося» множества, обозначим множество В; точки (о) - «средние» точки первого и второго множества, соответственно {ЕА = —-2а, и Ев = —-6у); N1 «є/ TV 2 JeJ пунктирная линия - прямая, которая дает наилучшее разделение 1-ым методом (ОРГ-1) в двумерном случае; сплошная линия - прямая, которая дает наилучшее разделение 2-ым методом (ОРГ-2) в двумерном случае. На рисунке 1: пунктирная линия - прямая L = {х h(x) = 0}, где h(x) = (х-х0,ЕА —Eg), х0 = аЕА + (і-а)ЕВ и а = 0.57 - данная прямая дает наилучшее разделение 1-ым методом (ОРГ-1) в двумерном случае (96% правильно определенных данных); сплошная линия - прямая L(a) = {х j h(x, а) = 0}, где h(x, а) = (х- х0 (а), х ), х0 = аЕд + (l - а)Ев и а — 0.58 - данная прямая дает наилучшее разделение 2-ым методом (ОРГ-2) в двумерном случае (96% правильно определенных данных). L(a) = {x h(x, a) = 0}, где h(x, a) = (x-x0 (a), x ), x0 = aEA + (l - a)EB и a = 0.36 - данная прямая дает наилучшее разделение 2-ым методом (ОРГ-2) в двумерном случае (81.82% правильно определенных данных). Сравнивая результаты применения метода десятикратной проверки с результатами, полученными при рассмотрении 100% данных, можем сделать следующие выводы. По сокращенной базе: при идентификации точек обучающего множества (обучающее множество содержит 90% от исходных данных) средний результат существенно не изменился (ухудшился на 0.9 процента или улучшился на 0.1 - 1.8 процента, что можно объяснить погрешностью вычислений); при идентификации точек контрольного множества (10% от исходного) средний результат не ухудшился (уменьшение на 1% при рассмотрении трех параметров можно считать несущественным в связи с малой размерностью базы и можно объяснить погрешностью вычислений), а в ряде случаев улучшился (на 4%). По полной базе: при идентификации точек обучающего множества средний результат существенно не изменился (ухудшился на 0.3 процента или улучшился на 0.5 - 1.2 процента, что можно объяснить погрешностью вычислений); при идентификации точек контрольного множества средний результат незначительно улучшился (на 2-4%). по сокращенной базе данных ВМА по ЖКБ удалось получить (превосходный) результат (100% правильно определенных точек для контрольного множества и 100% для обучающего множества); наилучший результат по полной базе данных ВМА по ЖКБ - 90% правильно определенных точек для контрольного множества и 87.54% для обучающего множества. Замечание 3.3.2. Как и предполагалось, вращение гиперплоскости позволило получить лучшие результаты. Замечание 3.3.3. При рассмотрении 2-3-х наиболее существенных параметров, отобранных предложенным способом, получены значительно более хорошие результаты, что позволяет сократить время предварительной диагностики. Замечание 3.3.4. Результаты, полученные для сокращенной базы, лучше, чем результаты для полной базы. Это объясняется использованием более надежной методики измерения при первичном обследовании пациентов. Именно эту методику следует рекомендовать практикующему врачу.
