Процессы управления и устойчивость
жүктеу/скачать 30,48 Mb. Pdf көрінісі
|
|
ных критериев оптимумы будут различны. В работе [1] изучались аналоги функционала (1), которые явля- ются гладкими. Нами же рассматриваются функционалы (2) и (3), которые по сути являются негладкими [2, 3]. Рассмотрим следующий пример. 1 Работа выполнена при финансовой поддержке РФФИ (проект № 03-01-00668) 189 Пример 1. Пусть m = 4, n = 2. Для молекулы задана матрица δ расстояний между атомами x k , k = 1, 4, δ = 0 10 5 3 10 0 3 5 5 3 0 4 3 5 4 0 ,
т.е. δ ij = x i − x
j — расстояние от i-го до j-го атома. Требует- ся найти структуру молекулы, т.е. координаты атомов x k , k = 1, 4, в некотором смысле наилучшим образом соответствующую имеющим- ся данным. Не умаляя общности, зафиксируем x 1 в начале координат. В нашем случае минимум функции F 1 достигается в точке x ∗ = (0, 0, 4, 8889, 0, 3249, 4, 1523, 3, 0057, 0, 3728, 2, 7518). Если в качестве минимизируемой функции выбрать суммарную невязку (2) и найти минимум этой функции, то окажется, что F 2 достигает наименьшего значения при x ∗∗ =(0, 0, 7, 2341, 3, 9243, 5, 0389, 1, 1899, 2, 1952, 2, 7343). Если же выбрать функцию наименьшего уклонения F 3 и найти
минимум по этому критерию, то минимум достигается при x ∗∗∗
= (0, 0, 9, 2283, 1, 5351, 4, 7992, 2, 7343, 3, 1172, 1, 9044). Сравним значения невязок в точках минимума функционалов (2) и (3):
δ 2 = 0 8, 23 5, 17 3, 5 8, 23
0 3, 5
5, 17 5, 17
3, 5 0 3, 23 3, 5 5, 17 3, 23 0
, δ
3 = 0 9, 3
5, 52 3, 65 9, 3
0 4, 58 6, 12 5, 52 4, 58 0 1, 87 3, 65 6, 12 1, 87 0 . Видим, что у функционалов различные оптимумы и поэтому вы- бор конкретной функции (см. (1)–(3)) в качестве критерия зависит от характера задачи. 2. Случай “точного” разрешения. В этом пункте приведены результаты решения исходной задачи в случае ее “точной” разре- шимости. Сформулировано необходимое и достаточное условие по- строения симплекса по заданным ребрам, а также получена явная формула, позволяющая строить молекулу по заданным ребрам. 190
Заметим следующий геометрический факт, что если заданы рас- стояния от некоторой точки до вершин симплекса, то координаты этой точки определяются однозначно. Далее, ответим на следующий вопрос: при каких условиях воз- можно построение симплекса с заданными ребрами δ ij при 1 ≤ i < j ≤ n + 1. В R n симплекс состоит из n + 1 вершин. Обозначим, через x ij — j-ю координату точки i. Утверждение 1. Симплекс с ребрами δ ij при 1 ≤ i < j ≤ n + 1 в R n существует с точностью до преобразования (сдвига, переме- щения, поворота вокруг оси) тогда и только тогда, когда x 2 i,i−1 > 0,
i = 2, n + 1, где
x 1 = (0, . . . , 0), x 2 = (δ 12 , 0, . . . , 0), x 3
δ 2 13 + δ 2 12 − δ 2 23 2δ 12 , δ 2 13 − x 2 31 , 0, . . . , 0 , x 4 = δ 2 14 + δ
2 12 − δ 2 24 2δ 12 , δ 2 14 + δ 2 13 − δ 2 34 − 2x 41 x 31 2x 32 , δ 2 14 − x 2 41 − x 2 42 , 0, . . . 0 , Координаты точки x k , при 4 < k ≤ n + 1, соответственно: x k1 = δ 2 1k + δ 2 12 − δ 2 2k 2δ 12 , x kj = δ 2 1k + δ 2 1,j+1 − δ 2 j+1,k − 2 j−1
i=1 x ki x j+1,i
2x j+1,j
, j = 2, k − 2, x k,k−1 = δ 2 1k − k−2 i=1 x 2 ki , x kj = 0, j = k, n. 191
3. Решение задачи. Предположим, что существует точное ре- шение исходной задачи. Пусть из данного набора {δ ij }
но построить хотя бы один симплекс. Не умаляя общности, допустим, что этот
симплекс образуется ребрами {δ
} при
1 ≤ i < j ≤ n + 1, т.е. для них справедливо условие (1). Применяя утверждение 1, определим x 1 ,. . . , x n+1 — вершины симплекса. Ниже приведены формулы, позволяющие аналитически находить координаты оставшихся точек x k , k = n + 2, m: x k1 = δ 2 1k + δ 2 12 − δ 2 2k 2δ 12 , x kj = δ 2 1k + δ 2 1,j+1 − δ 2 j+1,k − 2 j−1
i=1 x ki x j+1,i
2x j+1,j
, j = 2, n. Литература 1. Le Thi H.A., Pham Dinh T. Large-scale molecular optimization from distance matrices by a d.c. optimization approach // SIAM J. Optim. 2003. Vol. 14, № 1. P. 77–114. 2. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. 368 с. 3. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимиза- ция. М.: Наука, 1981. 384 с. 192
3. Математические модели медико- биологических систем Григорьева К.В. Санкт-Петербургский государственный университет Прогнозирование эффективности применения химиотерапии при лечении онкологических заболеваний 1 Рекомендовано к публикации профессором Демьяновым В.Ф. Рассмотрим следующую задачу идентификации из области мате- матической диагностики. Пусть в пространстве R n заданы два мно- жества точек A и B A = { a
i ∈ R
n |i ∈ I } , I = 1, N 1 ; B = { b j ∈ R
n |j ∈ J } , J = 1, N 2 .
L (y, d) = { x ∈ R n | r (x, y, d) = 0 } , где r (x, y, d) = x, y + d, y ∈ R n , d ∈ R 1 , таким образом, чтобы максимально возможное количество точек из множеств A и B были бы правильно идентифицированы с помощью следующего критерия. Пусть c ∈ A ∪ B. Если r (c, y, d) < 0, то считаем, что c ∈ A, если r (c, y, d) ≥ 0, то c ∈ B. При этом на переменную y накладывается ограничение y = 1. Тогда r (c, y, d) является (с точностью до знака) расстоянием от точки c до гиперплоскости L (y, d). В [1, 2] введены два функционала с параметром ε, использо- вание которых дает разделяющие гиперплоскости. Качество раз- деления оценивается так называемым натуральным функционалом ˜ Q (¯ y) = |I + (¯ y)| + |J + (¯ y)| + |I 0 (¯ y)| + |J 0 (¯ y)|, где I + (¯ y) = { i ∈ I|r (a i , y, d) > 0 } ; J + (¯ y) = { j ∈ J| − r (b j , y, d) > 0 } ; I 0
y) = { i ∈ I|r (a i , y, d) = 0 } ; J 0 (¯ y) = { j ∈ J| − r (b j , y, d) = 0 } . Значение функционала ˜ Q (¯
y) представляет собой количество неверно идентифицируемых точек множеств A и B. Поставим следующую задачу: дать прогноз эффективности при- менения химиотерапии при лечении онкологических заболеваний на примере онкологической базы данных [3]. Суть исследования сводится к следующему. Имеется две груп- пы онкологических пациентов, в одной из которых (140 пациентов) 1 Работа выполнена при финансовой поддержке РФФИ, проект № 03-01-00668 193 проводилась химиотерапия, а в другой (113 пациентов) – нет. Каж- дая из этих групп делится еще на две группы, обозначаемые так: A − множество пациентов из группы, которые прожили больше 60- ти месяцев после операции, и B − множество пациентов из группы, которые прожили меньше 60-ти месяцев после операции. Для решения задачи идентификации использовались четыре раз- личных алгоритма, которые давали различные разделяющие гипер- плоскости (из-за наличия локальных минимумов) при различных значениях ε. Кроме того, задача решалась для трех наборов наи- более информативных параметров базы данных, полученных в ре- зультате ранжирования по методу Кокориной А.В. [4]: (33, 35), (30, 33, 35), (30, 33, 34, 35), где 30 − максимальная гладкость; 33 − мак- симальная выпуклость; 34 − максимальная симметричность; 35 − максимальная фрактальность. Вначале рассмотрим множество из 140 пациентов, которым была проведена химиотерапия. Разделим множества A и B с помощью ги- перплоскости рассмотренными методами и получим 18 гиперплоско- стей L (y s , d
s ), s = 1, 18. Наибольший процент отделимости – 72,86%. Аналогично проведем разделение подобных множеств A и B для на- бора пациентов в 113 человек, не проходивших химиотерапию, и то- же получим 18 гиперплоскостей L (y s , d s ), s = 19, 36. Практически во всех случаях были получены разные гиперплоскости и достаточ- но хороший процент отделимости – 73,45%. Затем решим обратную задачу: применим гиперплоскости, полу- ченные для 140 пациентов, к множеству из 113 пациентов, и, на- оборот, гиперплоскости, полученные для 113 пациентов, применим к группе в 140 человек. В результате получим для каждого из 253 пациентов 36 значений линейных функций r (c i , y s , d
s ), s = 1, 36; i = 1, 253. Теперь применим для каждого из 253 пациентов критерий иден- тификации, сформулированный ранее, и тогда получим для каждой из гиперплоскостей L (y s , d
s ), s = 1, 36, два множества A − s
+ s : A − s = {a i ∈ A, b j ∈ B | r (a i , y
s , d
s ) < 0; r (b j , y
s , d
s ) < 0} ;
B + s = {a i ∈ A, b j ∈ B | r (a i , y
s , d
s ) > 0; r (b j , y
s , d
s ) > 0} .
Введем обозначения для каждой из 36 гиперплоскостей L (y s , d s ), s = 1, 36: ˜ A − s = {a
i ∈ A | r (a i , y
s , d
s ) < 0} ; ˜ A +
= {a i ∈ A | r (a i , y
s , d
s ) > 0} .
Как и в [5], найдем k A − s = ˜
A − s |A − s | − долю пациентов из множе- 194
ства A − s , которые “правильно” идентифицированы (в случае, если па- циент c
i получил знак “−” функции r (c i , y
s , d
s ), s = 1, 36; i = 1, 253), и ¯ k
+ s = ˜ A + s |B + s | − долю пациентов из множества B + s , которые “неправильно” идентифицированы (в случае, если пациент c i полу-
чил знак “+” функции r (c i , y s , d
s ), s = 1, 36; i = 1, 253), в расчете на то, что именно они обеспечивают пациенту вероятность попадания в группу A – “успешные”. Для простоты, введем обозначение k s
= k A − s , r (c i , y s , d
s ) < 0;
¯ k B + s , r (c i , y s , d
s ) > 0;
где k s i – вероятность благоприятного прогноза с помощью s-гипер- плоскости для i-го пациента. Проиллюстрируем сказанное на примере одной из s-гиперплоско- стей для группы из 140 пациентов, для которых проводилась хи- миотерапия. Множество A содержит 61 точку, из них неверно опре- деленных − 14 (+) и верно определенных − 47 (−). Множество B содержит 79 точек, из них верно определенных – 53 (+) и неверно определенных − 26 (−). В группе из 73 пациентов “правильно” идентифицировано 47 па- циентов, что составляет k A −
= 47/(47 + 26) = 0, 64 − это вероят- ность того, что химиотерапия будет успешной для пациента, по- павшего в множество A − s , i = 1, 140. А в группе из 67 пациентов “правильно” идентифицировано 53 пациентов, что составляет k B +
= 53/(53 + 14) = 0, 79 − это вероятность “неудачи” для пациента, по- павшего в множество B + s , и, соответственно, вероятность “успеха” для него в этом случае (или, иными словами, вероятность попада- ния в группу A − “успешные”) будет k s i = ¯ k B + s = 1 − k B + s = 0, 21, i = 1, 140. На основании полученного материала предлагается давать реко- мендации следующим образом. Для каждого пациента имеем 36 ги- перплоскостей, s = 1, 36. Первая группа из 18 гиперплоскостей дает прогноз того, что будет, если пациенту будет сделана химиотерапия: если пациент (для любой s-гиперплоскости, s = 1, 18) получил знак “−”, то это означает, что он был правильно идентифицирован s-гиперплоско- стью с благоприятным прогнозом в случае, если ему будет сделана химиотерапия. Причем, благоприятный прогноз в этом случае со- ставляет вероятность k s i
A − s . Если пациент был ошибочно иден- тифицирован с помощью s-гиперплоскости, s = 1, 18, т.е. получил 195
знак “+”, то это означает, что прогноз для этого пациента в слу- чае, если ему будет сделана химиотерапия, неутешительный, и веро- ятность этого прогноза k B + s . Соответственно, вероятность прогноза, что химиотерапия даст положительный результат в этом случае бу- дет k
s i = ¯ k B + s . Вторая группа из 18 гиперплоскостей дает прогноз того, что будет, если пациенту не будет сделана химиотерапия: если па- циент (для любой s-гиперплоскости, s = 19, 36) получил знак “−”, то это означает, что он был правильно идентифицирован s-гиперплоскостью с благоприятным прогнозом в случае, если ему не будет сделана химиотерапия. Причем, благоприятный прогноз в этом случае составляет вероятность k s i
A − s . Если пациент был ошибочно идентифицирован с помощью s-гиперплоскости, s = 19, 36, т.е. получил знак ”+”, то это означает, что прогноз для этого пациен- та в случае, если ему не будет сделана химиотерапия, неутешитель- ный, и вероятность этого прогноза k B + s . Соответственно, вероятность прогноза, что отсутствие химиотерапии даст положительный резуль- тат в этом случае будет k s i
k B + s . Теперь для каждой группы из 18 знаков выбираем доминиру- ющий знак и тогда каждый пациент имеет два знака вида “−/−”, “+/+”, “−/+”, “+/−”: • “−/−” – пациент, которому можно предсказать положительный результат, если ему будет сделана химиотерапия, и положи- тельный результат, если ему не будет сделана химиотерапия; • “+/+” – пациент, которому можно предсказать отрицательный результат в обоих случаях; • “−/+”– пациент, которому можно предсказать положительный результат, если ему будет сделана химиотерапия, и отрицатель- ный результат, если ему не будет сделана химиотерапия; • “+/−” – пациент, которому можно предсказать отрицательный результат, если ему будет сделана химиотерапия, и положи- тельный результат, если ему не будет сделана химиотерапия. Будем определять вероятность благоприятного прогноза k chemo i
образом: берется среднее значение вероятностей благоприятного для i-го пациента прогноза k s i
L (y s , d s ), s = 1, 18, i = 1, 253 (при этом гиперплоскости берут- ся различные). Вероятность благоприятного прогноза k nochemo
i для
i-го пациента в случае отсутствия химиотерапии будет вычисляться, 196
соответственно, как среднее значение вероятностей благоприятного для i-го пациента прогноза k s i
L (y s , d s ), s = 19, 36, i = 1, 253 (гиперплоскости берутся различные). Несколько другой подход описан в [6]. В зависимости от того, какая из вероятностей k chemo i
nochemo i больше, тот вариант будем считать предпочтительнее. Литература 1. Григорьева К.В. Метод проектирования в одной задаче иденти- фикации // Процессы управления и устойчивость: Труды 34-й научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова. – СПб.: Изд-во СПбГУ, 2004. С. 268– 271.
2. Григорьева К.В. Суррогатные функционалы в математической диагностике // 63-я научная конференция Санкт-Петербургского государственного архитектурно-строительного университета. 7–9 февраля 2006 г., СПбГАСУ. 3. "WPBCC: Wisconsin Prognostic Breast Cancer Chemotherapy Data- base". Computer Science Dept., University of Wisconsin, Madison, 1999. 4. Кокорина А.В. Ранжирование параметров в задаче обработки данных. // Процессы управления и устойчивость: Труды 34-й на- учной конференции аспирантов и студентов / Под ред. В.Н. Стар- кова. – СПб.: Изд-во СПбГУ, 2002. С. 277–281. 5. Демьянова В.В. Метод главного эксперта в задачах идентифи- кации // Устойчивость и процессы управления: Труды междун. конф., посвященной 75-летию со дня рождения В.И. Зубова. Рос- сия, СПб, 29 июня – 1 июля 2005 г. / Под ред. Д.А. Овсянникова, Л.А. Петросяна. – СПб.: СПбГУ, НИИ ВМ и ПУ, ООО ВВМ, 2005. Т. 2. С. 815–822. 6. Семко А.Н., Яковлев Я.В. Метод экспертных оценок в задачах математической диагностики // Устойчивость и процессы управ- ления: Труды междун. конф., посвященной 75-летию со дня рож- дения В.И. Зубова. Россия, СПб, 29 июня – 1 июля 2005 г. / Под ред. Д.А. Овсянникова, Л.А. Петросяна. – СПб.: СПбГУ, НИИ ВМ и ПУ, ООО ВВМ, 2005. Т. 2. С. 927–930. 197
Демьянова В.В. Санкт-Петербургский государственный университет Задача прогнозирования Рекомендовано к публикации профессором Токиным И.Б. 1. Введение. Рассматривается задача прогнозирования эффек- тивности применения нескольких методик обучения, тренировки или лечения (для определенности будем говорить о методиках обучения, например, языкам). Предполагается, что для каждой методики из- вестны результаты ее применения, т.е. известен идентификатор, или решающее правило (РП), с помощью которого для любого ученика можно (с некоторой известной точностью) сказать, будет ли данная методика эффективна в отношении его или нет, т.е. в какую группу он попадает: в группу "обучаемых" учащихся (для которых обуче- ние окажется успешным) или в группу "необучаемых". В работах [1, 2] был описан "метод главного эксперта"(МГЭ), в котором из нескольких решающих правил строилось новое РП, жүктеу/скачать 30,48 Mb. Достарыңызбен бөлісу:
|