Задачи динамического программирования и нечеткой кластеризации Куркина Мария Викторовна

Содержание к диссертации

Введение

1 Многомерная линейная модель динамического распределения ресурсов 24

1.1 Принцип Беллмана динамического программирования . 24

1.1.1 Многошаговый процесс управления 24

1.1.2 Задача оптимального управления 26

1.1.3 Элементарный подход 27

1.1.4 Метод динамического программирования 28

1.1.5 Задача распределения ресурсов 33

1.2 Многомерная линейная модель распределения ресурсов 34

1.2.1 Линейная модель распределения ресурсов с положительными коэффициентами 34

1.2.2 Линейная модель распределения ресурсов с произвольными коэффициентами 37

1.2.3 Линейная модель с ограничениями 47

1.3 Обобщенная многомерная линейная модель распределения ресурсов 52

2 Бесконечномерная линейная модель распределения ресурсов с ограничениями 60

2.1 Бесконечномерная линейная модель распределения 60

2.2 Линейная модель распределения ресурсов с равномерным и независимым распределением параметров 69

2.3 Линейная модель распределения ресурсов с равномерным распределением параметров в круге 74

2.4 Многомерная линейная модель распределения ресурсов с непрерывным временем 77

3 Нечеткая кластеризация 79

3.1 Нечеткое отношение эквивалентности, ультраметрика. Стандартная форма ультраметрической матрицы 79

3.2 Транзитивное замыкание нечеткого толерантного отношения . 89

3.3 Иерархическое кластеробразование 95

3.4 Аддитивные метрики. Конструкция Бунемана 97

3.5 Соотношение между аддитивной метрикой и ультраметрикой 102

3.6 Евклидово расстояние между нечеткими толерантными отношениями 107

3.7 Липшицево расстояние между нечеткими толерантными отношениями 114

4 Выделение контурных линий изображения методами нечеткой кластеризации 117

4.1 Диагональные детали (второго порядка) 119

4.2 Детали первого порядка 121

4.2.1 Нечеткая кластеризация аномальных точек поля градиента 121

4.2.2 Другие локальные нечеткие отношения для аномальных точек 123

А Приложение 125

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

Введение к работе

Задачи оптимизации и классификации играют в приложениях важную роль и со временем актульность этих задач только возрастает. Метод динамического программирования - широко известный и мощный математический метод оптимизации применяемый в самых разных областях современной прикладной математики. Впервые данный термин был введен в конце 50-х годов американским математиком Р. Беллманом в его известных монографиях [1, 2], в этих работах на основе рассмотрения функциональных уравнений были заложены математические основы ДП. В работах Р. Арис, Е.С. Вент-цель, Г. Вагнер, Н.М. Оскорбин, Дж. Моудера, Н.Ш. Кремер [3, 4, 5, 6, 7, 8], даны многочисленные примеры применения ДП.

При вычислительной реализация метода динамического программирования возникают трудности. Эти трудности Р. Беллман назвал "проклятием размерности". Они связаны с необходимостью хранения в процессе счета большого числа табулированных функций многих переменных. Одним из способов преодоления этих трудностей является выделение классов задач, которые допускают построение аналитических решений, или хотя бы аналитическое исследование. Примером такого подхода служит работа Sutherland, W.R.S.; Wolkowicz, Н.; Zeidan, V. [9]. В диссертации выделен класс задач, который можно условно назвать линейной моделью распределения ресурсов и проведено аналитическое исследование этих задач.

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

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

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

Основные задачи работы включают.

1. Установление связи между многомерной линейной моделью распределения ресурсов и дискретной одномерной динамической системой;

2. Изучение многомерной линейной модели распределения ресурсов с ограничениями и соответствующей динамической системы;

3. Исследование обобщенной линейной модели распределения многомерных ресурсов и соответствующей ей динамической системы;

4. Построение интегральной линейной модели распределения ресурсов с ограничениями;

5. Оптимизация транзитивного замыкания нечеткого отношения эквивалентности.

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении представлен обзор литературы по теории динамического программирования, приводятся основные результаты работы.

Первая глава диссертации посвящена элементарному введению в теорию динамического программирования, формулировке задачи динамического распределения ресурсов в наиболее простой экономической интерпретации [4].

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют у\. Средства X, вложенные в г-ое предприятие, приносят к концу года доход fi(X) и возвращаются в размере ц>і(Х) < X;

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

Процесс распределения ресурсов рассматривается как n-шаговый, в котором номер шага соответствует номеру года. Управляемая система в данном случае это т предприятий с вложенными в них средствами. Система характеризуется (р = 1) одним параметром состояния уи t = 1,2, ...,п -количеством средств, которые следует перераспределить в начале t-vo года. Переменных управления на каждом шаге т (s = га), хц - количество средств, выделенных соответственно г-ому предприятию, г = 1,... ,т. Так как средства ежегодно перераспределяются полностью, то

Xtl + X_t2 + ... + Xtm = Vt-

Пронормировав переменные управления 7ti = тг¹ получим, что

yt 7il + 7« + — + Itm = 1, Iti > 0.

То есть точка j_t = {jti} Є A^m_1 принадлежит (га — 1) - симплексу Л^т-1. Показатель эффективности данной задачи - это доход за один год

/l(z*l) + /2(^2) + ... + fm{Xtm)-

Критерий оптимальности - доход полученный от га предприятий в течении п лет равен

п Z = XI lfl(^xtl) + /2(^2) + ... + fm(Xtm)]-

t=l Уравнение состояния выражает остаток средств y_t после t-ro шага и имеет

2/M-l = + ^2(^2) + ... +

Пусть Z*(Y,t) - условный оптимальный доход, полученный от распределения средств Y между га предприятиями в период с t-ro года до последнего

n-го. Рекуррентные функциональные уравнения Беллмана для этих функций имеют вид:

Я*(Уп, ^п) = ^тах _ [fl(^xnl) + - - - + fm(Xnm)}

- последнее уравнение Беллмана (при t = п), и

Z\y_ut) = max \fi(x_tl) + ... + f_m(x_tm) + Z*(y_t+Ut + 1)]

Xn + ...+Xtm-yt

- уравнения Беллмана при t = n — 1,...,1, здесь y_t+i = <-p\{xti) + ^2(^2) +
... + _m(xtm). Как видно из этих уравнений, даже для функций /г, <>j про
стого вида, рассчитывать на получение явного решения затруднительно.
Большинство известных явных решений для двумерной задачи приведено
в [1, 2, 3, 4].

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

Теорема (Теорема 1.2.1). Пусть функции fi{X) и ifi{X) (функции дохода и возврата средств соответственно), линейные fi{X) = hiX, = ГіХу hi > О, г і > 0, г = 1, 2,... ,77г. Тогда функции условного оптимального дохода Z*(y,k) также будут линейные Z*(y,k) — Н^у, при этом коэффициенты Hk находятся рекуррентно:

Н_п = А(0),

#i = А(Я₂),

где функция Х(х) = max [hi + rix] - верхняя огибающая линейных функций.

Оптимальному решению соответствует дискретная динамическая одномерная система, определяемая отображением

х* = \(х)_у

траектория которой с начальной точкой хо = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке (см. рис. 2 пункта 1.2.1).

Определение. Коэффициентом эффективности 1-ого предприятия назовем решение уравнения х = hj_-\- Г{Х , т. е. число

р. — 1

1-Г;

Справедливо утверждение

Теорема (Теорема 1.2.3). Для многомерной линейной модели распределения ресурсов справедливы утверждения;

m&xhi < Hi < maxPf,

і і

lim Н\ = maxPj

п—+оо і

Далее условия hi > 0 и г і > 0 в теореме 1.2.1 последовательно ослабляются в серии теорем.

Теорема (Теорема 1.2.4). Пусть функции fi(X) и 0, і = 1, 2,... ,т. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) = XZ*(y, к), при X > 0, то есть

Z*(y,k) = H±(y)^{ ^кУ'

[Нїу, у<0.

при этом коэффициенты Н, Н_к находятся рекуррентно;

Я+ = Л⁺(0), Я" = А-(0),

HU = А⁺(Я_П⁺), Н-__г = Л-(Я-)

НІ = А+(Я₂⁺), ЯГ = Л-(Я₂"),

где функции \⁺{х) = max [Л» Н- г«гг], Л~(аг) = min [hi+rix] - соответ-

ственно верхняя и нишсняя огибающая линейных функций.

Теорема (Теорема 1.2.5). Пусть функции fi(X) и (fi{X) (функции дохода и возврата средств соответственно), линейные fi(X) — hiX, ipi(X) = ГіХ; тахг{гі} > 0 > тіщ{гї\. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) = \Z*(y, к), при А > 0, то есть

[ніу, у>0, [Нїу, у<0. при этом коэффициенты Н, Н^ находятся рекуррентно;

^{я+ = л+(о), я- = л-(о),}

HU = тах{А⁺(Я+), А⁺(Я~)} , Н'__г = min {А-(Я+), А~(Я-)}

НІ = max {А⁺(Я₂⁺), А⁺(Я₂-)} , tff = min {\~(Н}), \~{Щ)} ,

где функции Х⁺(х) = max {[ь + пх], Х~(х) = min \hi+rix\ - соответ-

1<г<гп ^{J Ч} ' 1<г<т^{1 J}

ственно верхняя и нижняя огибающая линейных функций.

Оптимальному решению соответствует дискретная динамическая двумерная система, определяемая отображением

х* = max{A⁺(x), Х⁺(у)},

у*= min {А" (х), А" (г/)}, траектория которой с начальной точкой xq = 0, т/о = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке.

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

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют о- Средства X, вложенные в г-ое предприятие, приносят к концу года доход fi(X) и возвращаются в размере фі(Х) < X] г = 1,2,...,?тг. По истечении года все оставшиеся средства заново перераспределяются поровну между определенным, фиксированным процентом а% предприятий (например а = 25%), которые имеет смысл финансово поддержать и привлечь к данному проекту. Новых средств не поступает, доход в производство не вкладывается.

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

Теорема (Теорема 1.2.6). Пусть функции fi{X) и О, 0 < г, < 1, і = 1,2,... ,га. Тогда функции условного оптимального дохода Z*(y, к) также будут линейные Z*(y, k) = Н^у, при этом коэффициенты Hk находятся рекуррентно;

Н_п = \*(0),

Hn-i — A_a(i/_n),

Яі = Аа(Я₂),

функция Х_а определена формулой

А_а(#) = Мах^а [hi + гіх] ,

здесъ оператор Мах^а определена формулой:

Max" {Ы} = - У>_я

где h_h > h_i2 >h_h> ...> h_im, p = [ma] - целая часть та.

Величину Мах^а {hi} назовем верхним а-средним для числового семейства

{Ы}, а функцию Л_а - верхней а-средней семейства линейных функций.

Определение. Групповым коэффициентом эффективности набора г из р предприятий, где г = {іі,І2, 7^р}> назовем решение уравнения х — - Y?k=\ (kk + ^rik^x)> ^m- ^e- ^исло

-^^p h-p = - ^F

¹ - Hk=\ ^rik

Теорема (Теорема 1.2.8). Для многомерной линейной модели распределения ресурсов с ограничением справедливы утверждения:

Max^ahi < Hi < max Р_Т,

і т

lim/Уі = maxP_T.

n—+oo ^т

Далее рассматривается обобщенная линейная модель распределения ресурса произвольной конечной размерности. Справедлива

Теорема (Теорема 1.3.1). Пусть "ресурс" X — {х-⁷} Є ЯР состоит из р компонент, функции "дохода" fi(X) = hijX³ - линейные, отобраэюения ifi : R^p —» R^p - линейные, Ц>і(Х) = {TijX³}^s_sZ^p, здесь по повторяющемуся индексу (вверху и внизу) вычисляется сумма, hij > 0, г\' > 0, і = 1,2,..., т; j,s = 1,2, ...,р. Тогда функции условного оптимального дохода Z*(Y,k) также будут линейными функционалами Z*{Y_yk) = Zkjy³, при этом коэффициенты Zk = {zkj} Є R^p находятся рекуррентно:

Z_n = Л(0), Zn-г = A(Z_n), - Z_x = A(Z₂),

где отображение А : В? —> В? имеет компоненты \_S(X), определяемые формулами:

X_S(X) = max hi_S + r{_sXj
^v ' \<ї<т L ^{ls J}J

- выпуклые вниз функции (верхние огибающие линейных функций).

Замечание. Нахождение плана оптимального распределения ресурсов сводится к вычислению траектории {Zk} динамической системы, определяемой отображением A : R+ —> ЯР₊ с начальной точкой Zq = 0 в начале координат.

Определение. Вектором ("чистым") эффективности г-ого предприятия назовем решение уравнения x_s = hi_s + r³_isXj , т. е. вектор

Рі = (Е- <рі)-%.

Пусть (3 : {1, 2,... ,р} — {1,2,..., т} произвольное отображение конечных мнооюеств. Сопоставим (3 решение Рр системы уравнений x_s = hpr_s\_s+ ri,^_sXj_; т.е. вектор

Рр = (Е - ^lhp,

где <рр - "смесь" линейных операторов ері, г = 1,2, . ..,га, т.е. каждая строка матрицы оператора (рр есть строка с тем же номеров одной из матриц ірі, г = 1,2,..., т. Вектор Рр назовем вектором эффективности (3 "смеси" предприятий. Всего таких векторов будетр^т. Если отображение (3 постоянное, то получаем "чистый" вектор эффективности.

Введем в пространстве В? норму по формуле

ЦхЦоо = max {\хА}. j=i,...,p

Соответствующая норма линейного оператора <р : ЯР —* ЯР, <р(х) = {r-Xj}

определяемая формулой

INIoo

будет равна .

IMI = .^та^х ^У)Иі

Теорема (Теорема 1.3.3). Пусть нормы линейных операторов {ty?i}i строго меньше 1, тогда для многомерной линейной модели распределения ресурсов справедливы утверждения:

—+ —*

max hi < Z\,

—» —* —»

lim Z\ = maxP/з > maxPj,

n—>oo (3 і

где неравенство выполняется покомпонентно.

Вторая глава - "Бесконечномерная линейная модель распределения ресурсов с ограничениями" посвящена исследованию математической модели бесконечномерной (интегральной) задачи распределения ресурсов.

В случае очень большего числа линейных предприятий (порядка 10000) естественно перейти от конечного набора коэффициентов hi, г і к вероятностному распределению пар чисел {h, г}. Будем считать, что задана функция совместной плотности распределения этих величин p(h, г) обладающая свойствами:

6. p(h, г) > 0 при h > 0 и г > 0, равная нулю в противном случае;

7. функция p(h,r) > 0 непрерывна при h > 0 и г > 0;

8. выполняется равенство

л+оо л+оо

і I p(h,r)dpdh = 1. Jo ./о

4. конечны первые моменты

»+оо Л+ОО /»+00 /«+00

л+оо л+оо л+оо л+оо

/ / hp(h, r)dpdh < +оо, / / rp(h, г)dpdh < +оо.
Jo Jo Jo Jo

Введем обозначение M = [0, +оо) х [0, +оо) - множество (фазовое пространство) всех параметров предприятий. Доля предприятий, параметры которых лежат в прямоугольнике ЛМ = [/г, h -Ь Ah] х [г, г + Лг], равна

_/

Л+Д/i лг+Аг / p(h,r)dpdh ~p(h,r)/\p/\h

Рассмотрим следующую математическую модель деятельности М предприятий в течение п лет. Начальные средства составляют о- Средства X, вложенные в множество dM предприятий, приносят к концу года доход f(dM, X) = X hp(h, r)dpdh и возвращаются в размере = X rp(h, r)dpdh. По истечении года все оставшиеся средства заново перераспределяются равномерно на каждый раз определяемом множестве Мі предприятий, доля которых составляет фиксированным процент а% (например а = 25%),

/ p(h, r)dpdh = а.

Это те предприятия, которые привлекаются к данному проекту на следующий год. Новых средств не поступает, доход в производство не вкладывается. Требуется найти оптимальный способ отбора множеств {М;}, і = 1,..., п тех предприятий, между которыми будет происходить распределение имеющихся средств. Процесс выбора рассматриваем как n-шаговый, в котором номер шага соответствует номеру года. Справедлива

Теорема (Теорема 2.1.1). В условиях задачи функции условного оптимального дохода Z*(y,k) будут линейные Z*(y,k) = Н^у, при этом коэффициенты Hk находятся рекуррентно:

Н_п = А_а(0), Я„_і = Аа (//„), — Н\ = \_а(Н2),

функция Л_а определена формулой

А_а(х) = sup < / [h + rx]p(h, r)dhdr : I p(h, r)dhdr = a > ,

AcM U A J A J

для каждого x множество А С M на котором достигается супремум представляет собой область вида

М_х = {т = (h,r) Є М : h + хг > с} ,

где константа с зависит от выбора х и определяется из условия

/

J м-

p(h,r)dpdh — а.

Замечание. В силу линейности подинтегралъной функции справедливо равенство

I [h + rx]p(h, r)dhdr = (h* + r*x) / p(h, r)dhdr,
J A J A

где точка q(h*, r*) - центр тяжести мноэюества А с данной плотностью массы p{h,r). Отсюда следует, что

^а(х) = [h + rx]p(h, r)dhdr = (h* 4- r*x)a, Jm_x

где точка q_x(h*,r*) - центр тяжести мноэюества М_х с данной плотностью массы p(h, г).

Определение. Положим

N_x = {т = (h,r) Є М : h + xr < с} = М \ М_х. Выпуклое множество определенное равенством

F_a = f]N_X}

назовем запретным уровня а.

При любом выборе выборе начальных средств х и любом количестве этапов перераспределения средств множество F_a не участвует в этом перераспределении.

Определение. Выпуклое множество определенное равенством

G_a = f)M_x,

назовем общим уровня а.

При любом выборе выборе начальных средств х и любом количестве этапов перераспределения средств множество G_a участвует в каждом перераспределении.

Пусть = (h,r) - произвольная функция, A1UA2 = Щ. - некоторое раз-

-17-
биеиие первого квадранта плоскости на два множества, введем обозначения:
/xi = / p(h,r)dhdr, //2=/ p(h,r)dhdr,

Сі = - / {p,r)p{h,r)dhdr, Ь = - / ,{p,r)p(h,r)dhdr,

Di = - [ [fi - «eb, г)]²р(Я, r)d№, D₂ = - f [6 - (p, r)]²^(/i, r)rfWr,

f = / f(p, г)р(Л, r)^r, Z?[fl =/ [f - Є(Р, г)]²р(/г, r)cMr

7ЛіиЛ₂ JAiUA₂

Тогда справедливо равенство

(частный случай общего дисперсионного равенства). Возьмем в качестве множеств А\ = М_х и А₂ = ЛГ_Х, а в качестве функции = /г, + яг, тогда имеем:

А«і = а, Д42 = 1 — а,

= Л + ax, >[] = D[h -f xr\,

Й = (Л* + xr*) = -\_а(х), 6 = (h** + zr**) = ^fc + ^gf-M^)

а 1-а

где точки go(^> ^), Ql{h*, г*), q**(h**, г**) - центры тяжести множеств R+, М_Ху

N_x при данной плотности p(h,r).

Теорема (Теорема 2.1.2). Пусть конечны все центральные вторые моменты

D\\ = / {h - h)²p(h, r)dhdr < со, Jr²₊

Dn — I (h — h)(r — f)p(h, r)dhdr < oo,

JR\

D22 = I (r — f)²p(h,r)dhdr < 00, JfR

тогда справедливо равенство

[a(h + xf) — A_Q(x)]'

a(l — a)

D_n + 2^ + s^zD₂₂ = aDi + (1- a)>₂ +

Следствие. В условиях теоремы справедливо неравенство

[a(h + xf) - \_a(x)f < ос{1 - a)(D_n + 22: + 2:²).

Теорема (Теорема 2.1.3). Пусть конечны первые моменты, тогда справедливо неравенство

А_а(:г) < — (h + xf). а

В главе 2, также подробно изучен случай независимого равномерного распределения {/г, г} и равномерного распределения {h, г} в круге.

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

При практическом разбиении на кластеры в теории нечеткого моделирования [27, 28, 29] используют понятие нечеткого множества и нечеткого отношения эквивалентности. Нечеткое отношение эквивалентности R (нечеткое подмножество X х X) определяется своей функцией принадлежности fi^R : X х X —> [О,1] обладающей свойствами:

Va Є X : LL^R(a, a) = 1 - свойство рефлексивности,

Va, Ъ Є X : fi^R(a,b) = /і^л(6, a) - свойство симметричности,

Va, 6, с Є X : min {/j,^R(a, b),/j,^R(b, с)} < /г^я(а, с) - свойство транзитивности.

Нечеткое отношение назовем нечетким толерантным отношением, если выполнены лишь свойства рефлексивности и симметричности.

Определение. Ультраметрикой на множестве X называют функцию /?(a, Ь) удовлетворяющую аксиомам:

Va Є X : />(а, а) = 0,

Va, Ь Є X : р(а, 6) = р(Ъ, а),

Va, b, с Є X : p(a, с) < max {p(a, b),p(b, c)}. Пару (X,p) называют улътраметрическим пространством.

Функция /і^й(а, b) определяет нечеткое отношение эквивалентности на множестве X в том и только в том случае когда функция p^R(a, 6) = 1 — ji^R(a, b) - ультраметрика на X. Будем называть эту ультраметрику двойственной к нечеткому отношению эквивалентности.

Любое свойство нечеткого отношения эквивалентности имеет аналог в терминах ультраметрики, верно и обратное. Ультраметрические пространства обладают рядом замечательных свойств, например, они изометрично вкладываются в сферу гильбертового пространства (см. В.Н.Берестовский [34]), имеются многочисленные приложения этого понятия, как в самой математике (р-адический анализ), так и в других естественных науках (в биологии [38]).

Нас будет интересовать случай нечеткого отношения эквивалентности R (или двойственной ультраметрики) на конечном множестве X, содержащем N точек а,{, г = 1,2,..., N. Будем отождествлять точки с их номерами, т.е. di = і. Введем обозначения:

Ъ = \Ы\ = \Ш = \\1*^л(<н,ъ)\1

Квадратные матрицы R^, R_p размера N х N обладают свойствами:

О < fiij < 1, 0 < Pij < 1, (1)

У-іі = 1, Ра = 0, (2)

R-и⁼ R/ii R_p⁼ Rpi (з)

RpoRp = Д„, R_poR_p = R_p, (4)

где определение композиций 6, б числовых матриц дано ниже:

Определение. Мах-тгп композицией (соответственно Мгп-тах и Мгп-plus композицией) матриц R — ||г^[|, S = \\skj\\ размеров соответственно пхр и рх т называется матрица Т — RoS (соответственно Т = RoS и Т = RQ S) размера п х m определяемая соответственно формулами:

Uj = тахы,..._)Р {mm(r_ifc, s_kj)}, і = 1,...,n, j = 1,...,m,

Uj = min_fc=i_v.._)P {max(r_ifc, s_kj)}, і = 1,...,n, j = 1,...,rn,

tij = min_fc=i,...,_p {r_ik + s_kj}_} t = l,...,n,j = l,...,m.

Определение. Если выполнены лишь свойства (1) - (3), то матрицы R^ и R_p будем называть матрицами сходства (соответсвенно несходства) для данного нечеткого толерантного отношения.

Определение. Пусть R = И_р ультраметрическая матрица, т.е. удовлетворяет условиям (1)-(4). Стандартная или каноническая форма матриц такого типа определяется рекуррентно:

Rn R12
К = ,

R-21 R-22

где Rn, R-22 квадратные матрицы меньшей размерности в стандартной форме, а у матриц R12 = R₂i все элементы имеет одинаковую величину равную D = max. Rij, где D - диаметр ультраметрического пространства.

Теорема (Теорема 3.1.2). Пусть матрица R удовлетворяет условиям (1)-(4), тогда ее элементы принимают не более чем N — 1 различных положительных значений, и путем перенумерации точек щ X матрицу можно привести к стандартной форме (рис. 1 пункта 3.1).

При построении кластеризации основной операцией служит транзитивное замыкание нечеткого толерантного отношения.

Пусть R нечеткое толерантное отношение определенное на множестве X и Р = {hi, Ii2,..., h_k} последовательность точек в X такая, что hi = г и h_k = j. Будем называть Р путем соединяющим точки i,j Є X.

Определение. Шагом сходства (соответственно шагом несходства) вдоль пути Р называются величины:

^sn(^p) = ^.13-1.^.}

Определение. Разделяющим сходством двух различных точек i, j мно-оісества X (соответсвенно разделяющим несходством) называются величины:

san^R(i,j) = maxsn(F),

sad^R(i,j) = minsd(P),

где P произвольный путь соединяющий г и j. Если і — j, то sair^z, j) — 1, sad^R(iJ) = 0.

Теорема (Теорема 3.2.1). Для произвольного нечеткого толерантного отношения R функции san.^R(i,j) и sad (i,j) на мнооісестве X х X определяют, нечеткое отношение эквивалентности и двойственную ультра-метрику.

Определение. Остовом графа G = (V, Е) называется его подграф G' = (V.E') с тем эюе множеством вершин, являющийся деревом. Наименьшим остовом (SST) графа G = (V, Е) называют остов, у которого сумма весов ребер наименьшая.

Нечеткому толерантному отношению R на множестве X сопоставим полный неориентированный граф G = (V, Е), где V = X, Е - множество всех неупорядоченных пар точек из X, с весовой функцией ребра {а^, а^} равной величине несходства точек рц — p^R(a,i,aj).

Теорема (Теорема 3.2.2). Обозначим через G' = (Х,Е^Г) наименьший остов графа G = (Х,Е), тогда справедливы равенства:

sa,n^R(i,j) = sn_G'(P'),

і sad*(z,j) = sd_G,(P'),

где Р' единственный путь (без самоналоэюения) лежащий в остове G' = (X, Е') и соединяющий вершины і и j.

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

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

В современной теории цифровой обработки изображений уделяется большое внимание разработкам методов выделения контуров [35, 36]. В последний годы методы нечеткой сегментации изображения интенсивно разрабатываются [46], [47].

Определим понятие локальной нечеткой близости двух линейных элементов А(хі, уі; В(х2,2/2", <Р2), где (х;, уі) - координаты точек, cfi направление перпендикулярное полю градиенту в данных точках, по формуле

0, если R_f (А, В) = 0,

^(-^Г¹)' если ^/(^,5) = 1,

где Rf (А, В) истинное, если каждая из точек по отношению к другой лежит между ветвями гиперболы с вертикальной полуосью го и горизонтальной полусью Го/. Таким образом / - тангенс половины угла раствора гиперболы (угла между асимптотами). На рисунке 1 пункта 4.2.1 показаны две таких линейных элементы и соответствующие им гиперболы. Параметр vq характеризует толщину линии, параметр / константу Липшицевости линии. Величина d(A, В) - расстояние между точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками.

Нечеткое отношение эквивалентности Q_{j, полученное транзитивным замыканием данного локального отношения эквивалентности Qij, можно использовать для более наглядной визуализации данных (рис. 2 пункта 4.2.1).

Каждая линейный элемент изображается эллипсом, размер и форма которого управляется функцией f(Ai) = Q_iN (матрица Q_fj- - в стандартной форме), что соответсвует наиболее грубой кластеризации.

Визуальное сравнение рисунков указывает большую содержательность последнего.

В приложении даны программные модули в системе Matlab использованные в четвертой главе.

Линейная модель распределения ресурсов с положительными коэффициентами

. Наибольшую сложность представляет обратная процедура, включающая максимизацию функций по s-мерному векторному аргументу X. Здесь нужно, согласно (6), выполнить п процедур максимизации функций от s переменных. Это, вообще говоря, значительно более простая задача, чем максимизация одной функции по sn переменным, что требуется при элементарном подходе.

Однако есть одно серьезное осложнение. Дело в том, что обратная процедура предусматривает построение функций Z (Y,t) и Vt(Y), зависящих от р-мерного вектора Y. Даже простое табулирование и хранение функций р переменных представляют большие трудности. Если, к примеру, составлять таблицы, придавая каждой переменной 100 значений, то для хранения таблицы одной функции р переменных понадобится 100р ячеек памяти. Всего же обратная процедура, в которой участвуют функции Z (Y,t) и vt(Y), потребует п100р -Ь nsl00p ячеек.

Отсюда понятно, что вычислительная реализация метода динамического программирования сталкивается с большими трудностями. Эти трудности Р. Беллман назвал "проклятием размерности".

Одним из способов преодоления этих трудностей является выделение таких классов задач, которые допускают построение аналитических решений или могут быть исследованы аналитически. Некоторые обобщения Остановимся сначала на таких обобщениях постановки задачи (1)-(4), которые требуют лишь небольших и очевидных модификаций метода динамического программирования. 1. Ограничения, наложенные на управляющие воздействия, могут зависеть от текущего состояния системы и времени. В этом случае вместо (1.1.1) имеем условие где U(Y(t),t) - множество в 5-мерном пространстве, зависящее от р-мерного вектора У и от времени t. 2. Соотношение (1.1.2), определяющее переход системы из одного состоя ния в другое, может явно зависеть от времени, нестационарные процес сы. В этом случае вместо (2) имеем где F(Yt X, t) - заданная функция своих аргументов. 3. Критерий оптимальности (1.1.4) также может содержать слагаемые, яв но зависящие от времени, то есть иметь видСоответствующие очевидные изменения следует внести и в другие соотношения. Метод динамического программирования используется для исследования и решения задач оптимального управления процессами в условиях неопределенности. Здесь имеются в виду два различных типа проблем. Если неопределенные факторы (внешние воздействия, возмущения, шумы) имеют случайную природу, то для описания процессов управления используется аппарат теории вероятности и случайных процессов. Если же неопределенные факторы связаны с активным противодействием противника или необходимо обеспечить гарантированный результат (застраховаться от наихудших возможных реализаций неконтролируемых возмущений), то применяется аппарат теории игр. Отдельно следует сказать о задачах оптимального управления с непрерывным временем, описываемым дифференциальными уравнениями. В этом случае метод динамического программирования приводит к нелинейному дифференциальному уравнению в частных производных первого порядка. Теория решений этого уравнения, иногда называемого уравнением Гамиль-тона-Якоби-Беллмана-Айзекса, активно разрабатывается в последние годы. Приведем формулировку динамической задачи распределения ресурсов в наиболее простой экономической интерпретации [4]. Планируется деятельность т предприятий в течение п лет. Начальные средства составляют у\. Средства X, вложенные в г-ое предприятие, приносят к концу года доход fi(X) и возвращаются в размере fi(X) X; і — 1,2,..., т. По истечении года все оставшиеся средства заново перераспределяются между предприятиями, новых средств не поступает и доход в производство не вкладывается. Требуется найти оптимальный способ распределения имеющихся средств.

Процесс распределения ресурсов рассматривается как n-шаговый, в котором номер шага соответствует номеру года. Управляемая система в данном случае это т предприятий с вложенными в них средствами. Система характеризуется (р = 1) одним параметром состояния yt, t = 1,2,..., п — количеством средств, которые следует перераспределить в начале -го года. Переменных управления на каждом шаге га (s = га), хц - количество средств, выделенных соответственно г-ому предприятию, г = 1,... ,т. Так как средства ежегодно перераспределяются полностью,

Линейная модель распределения ресурсов с равномерным и независимым распределением параметров

Доказательство. Для вершин г j обозначим через P\ij\ = {/її, /іг, , hk} цепочку соединяющую вершины і и j в графе G на которой достигается минимум

Такие цепочки будем называть экстремальными. В силу предыдущей теоремы можно считать, что экстремальные цепочки лежат в остове SST. Тогда число звеньев в экстремальной цепочки всегда будет (N — 1). Из определения композиции следует где минимум берется по всем цепочкам длины к — 1, соединяющим точки і = si, j — Sfc. Так как рц = 0, то можно считать, что в формуле (3.2.3) цепочки длины (к — 1). Обозначим, через m(i,j) длину минимальной экстремальной цепочке соединяющей вершины і и j. Пусть г = Замечание 3.2.2. Данная теорема дает универсальный способ построения нечеткой кластеризации. Сначала строится нечеткое толерантное отношение, т.е. без свойства транзитивности, а затем строится его транзитивное замыкание. Аналогично можно найти "метрическое" замыкание для данной матрицы несходства. Теорема 3.2.4 (Теорема о "метрическое" замыкании). Пусть квадратная матрица R удовлетворяет условиям 3.1.3-3.1.5, тогда существует такое 1 г N, что Rr+1 = Rr и матрица Q = Rr задает метрическое замыкание R, где степень матрицы вычисляется с помощью композиции 0 (3.1.7). Доказательство. Для вершин і j обозначим через Р = {h\, /i2, hk} цепочку соединяющую вершины і и j в графе G на которой достигается минимум (3.1.12) Такие цепочки будем называть минимальными, число звеньев в минимальной цепочки всегда будет (N — 1), так как в противном случае цепочка содержит цикл, который можно выкинуть из цепочки. Из определения композиции 0 следует где минимум берется по всем цепочкам длины к — 1, соединяющим точки г = Si, j — Sfc. Так как рц = О, то можно считать, что в формуле (3.2.12) участвуют все цепочки длины (к — 1). Обозначим, через m(i,j) число ребер минимальной цепочке соединяющей вершины г и j. Пусть г Для представления данных в информационных системах, в справочниках, . при реализации алгоритмов поиска и в других приложениях часто используются корневые деревья, то есть деревья с выделенной вершиной, именуемой корнем. Пусть на множестве X задано нечеткое толерантное отношение R, пару (X, pR) будем называть пространством несходства. Определение 3.3.1 ([32]). Деревом классификации для пространства несходства (X, pR) называют корневое дерево G = (V,E), вместе с отображением ip : X — V в множество вершин G. Для стандартного дерева классификации X, множество значений отображения ip совпадает с множеством листьев G. Замечание 3.3.1. Для нестандартного дерева классификации X не требуется, чтобы множество значений отображения р совпадало с множеством листьев G. Часто предполагают, что отображение (р инъективно, но это не обязательно имеет место, особенно когда расстояние pR обращается в нуль для различных точек X.

Дерево классификации имеет однородную глубину, если число шагов (ребер) от корня до листа всегда одно и тоже.

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

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

Соотношение между аддитивной метрикой и ультраметрикой

В современной теории цифровой обработки изображений уделяется большое внимание разработкам методов выделения контуров [35, 36]. В данной главе предложен метод выявление контуров аномального поведения геофизических данных на основе нечеткой кластеризации изолированных точек аномального поведения данных при различных уровнях вейвлет разложения изображения. В последний годы методы нечеткой сегментации изображения интенсивно разрабатываются [46], [47],

Исследовались данные геофизической съемки одного участка в ХМ АО. Данные были представлены в двух файлах: "Amp.dat", "Koog.dat", содержащих координаты места и значения измеряемых величин. В первом файле 73935 точек, во втором 77884 точек. Далее для краткости эти величины обозначены, как "Amp", "Koog".

На этапе предварительной обработки величины Amp и Koog были приведены к одному масштабу и равномерному распределению на отрезке [0,1]. Для дальнейшей комплексной одновременной обработки Amp и Koog потребовались их значения на одной равномерной решетке, для этого была использована интерполяция их значений на один прямоугольный участок. Была использована процедура griddata из MatLab, эта процедура основана на триангуляции Делоне и позволяет проводить экстраполяцию на выпуклую оболочку данных. Была взята линейная интерполяция с числом узлов 1024 х 1024, этот выбор обусловлен стремлением максимально полно использовать имевшиеся данные, выбор линейной интерполяции (процедура griddata позволяет использовать кубическою) обусловлен стремлением произвести локальное усреднение данных.

В результате получены две переменные SZ1, SZ2 заданные в узлах квадрата 1024 х 1024. На рисунках изображены линии уровня 0.5 (медианы) функций SZ1 и SZ2. Из рисунков видно, что функции имеют сильно фрактальный характер, обусловленный не столько "помехами" , сколько самой природой этих данных. В этих условиях обычные градиентные методы выделения [35] контуров могут не дать желаемых результатов.

В силу фрактального характера переменных, на следующем этапе использовалось вейвлет разложение переменных SZ1, SZ2. Нахождение точек аномального поведения величин при вейвлет анализе сводится к исследованию коэффициентов деталей на разных уровнях вейвлет разложения. Так как разные уровни имеют нулевую корреляцию (ортогональны), то информацию поступающую с разных уровней, можно рассматривать как взаимно дополняющую друг друга. Число узлов 1024 = 210 и использование Хаар вейвлета позволило устранить "краевые" эффекты.

Кратко опишем суть вейвлет анализа (или метода масштабирования) на примере разложения изображения с помощью вейвлета Хаара. Вейвлет анализ изображения это многошаговый процесс на каждом шаге которого размеры "пикселов" масштабируется (увеличиваются). При этом часть информации об изображении теряется, чтобы эти потери нейтрализовать вводят так называемые "детали", которые берутся из высокочастотной области спектра изображения таким образом, чтобы каждый шаг масштабирования можно было обратить и однозначно восстановить исходное изображение по его "огрубленному" образу и сопутствующему набору деталей. Проиллюстрируем этот метод на вейвлете Хаара и прямоугольной сетке 2П х 2П. В результате слияния четырех пикселов {ац, аіг, а2Ь а22І получается один пиксел сА, и детали сН, cV, cD Пиксел сА состоит из четырех и яркость его принимается равной среднему значению (в процедуре DWT2 используется деление на два, чтобы сделать эту процедуру унитарной, сохраняющей Li норму). В результате теряется часть информации в размере 3 чисел на один укрепненный пиксел. Эта информация "уходит" в "детали" cH,cV,cD- горизонтальную, вертикальную и диагональную. Нетрудно видеть, что величины сА, сН, сУ, cD ортогональны т.е. раскоррелированы. В результате одного шага вейвлет разложения получим четыре изображения; усредненное и три содержащих детали (в каждом 512 х 512 узлов). Замечание 4.1.1. Два изображения (горизонтальные и вертикальные детали) содержат информацию о градиенте функции яркости (для вейвлета Хаара). Это компоненты градиента в данном масштабе, или соответствующие частные производные 1 порядка функции яркости. Диагональные детали представляют собой величины вида т.е. равны D — f х Jb v 4 1-dxdy и соответствуют в данном масштабе смешанной производной функции от двух переменных. Рассматриваемые по абсолютной величине они представляют собой вариацию функции от двух переменных и поэтому являются характеристиками 2 порядка Брались абсолютные значения этих деталей. Исходя из уровня значимости а = 0.02 на каждом уровне разложения выделялись наибольшие значения, остальные отбрасывались (так как была поставлена задача нахождения аномальных точек).

Другие локальные нечеткие отношения для аномальных точек

Исходя из гипотез о геологических процессах данного региона естественно было ожидать, что аномальные точки будут расположены вблизи геологических разломов, т.е вдоль слабо регулярных кривых на которых данные величины хотя и непрерывны, но теряют регулярность, аналогично функциям на плоскости вида /(я, у) = \ах + by + с\ или f(x, у) = у/х2 + у2. Направление градиента функции в этих точек ожидалось перпендикулярным линиям разломов или неопределенным.

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

Пусть заданы две точки с направлением А(х\, у\\ р{) и В(х2, уг\ f2), здесь Х{, у І - координаты точек, ірі - углы направлений с осью ОХ (О (fi 7г). Определение 4.2.1. Введем понятие локальной нечеткой близости двух точек направления А(хі,уі;срі), В(х2,У2 , Р2) по формуле где R/(A, В) истинное, если каждая из точек по отношению к другой лежит между ветвями гиперболы с вертикальной полуосью г о и горизонтальной полусью Го/. Таким образом f - тангенс половины угла раствора гиперболы (угла между асимптотами). На рисунке 1 показаны две такие точки направления и соответствующие им гиперболы. Параметр г$ характеризует толщину линии, параметр f константу Липшицевости линии. Величина d(A, В) - расстояние между точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками. Чем ближе величина Q{A, В) к единице, тем больше оснований считать эти точки направления принадлежащими одной кривой. Если имеются N точек, то в результате получаем симметричную матрицу локального нечеткого толерантного отношения Q = Q(Aj, -Aj) jJ=I,...,JV, на диагонали которой стоят единицы. Данное отношение рефлексивно, симметрично, и вообще говоря не транзитивное. где Е - единичная матрица, С - включение для нечетких подмножеств (т.е. функция принадлежности одного множества меньше функции принадлежности другого множества), о - операция нечеткой композиции двух отношений (max — min композиция). Применив операцию транзитивного замыкания локального нечеткого отношения Q получим нечеткое отношение эквивалентности Q. Нечеткое отношение эквивалентности можно использовать для более наглядной визуализации данных рис. 2. Каждая точка направления изображается эллипсом размер и форма которого управляется функцией f(Ai) — QiiV, что соответ-свует наиболее грубой кластеризации. Замечание 4.2.1. Визуальное сравнение рисунков 1 и 2 указывает боль где параметр г о характеризует радиус влияния. Величина d(A, В) - расстояние меэюду точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками. Замечание 4.2.2. С точки зрения общей топологии локальное отношение связности есть нечеткий аналог понятия топологической связности. Определение 4.2.3. Введем понятие локальной нечеткой линейной связности двух точек А{х\)уі), В(х2,У2) по формуле где Rf(A,B) истинное, если в "лунке" между точками {А, В) содержится по крайне мере одна из исследуемых точек С отличная от (А, В). На рисунке показаны две такие точки и соответствующая им "лунка". Параметр го характеризует радиус влияния, параметр (3 константу Липшице-вости линии. Величина d(A, В) - расстояние меэюду точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками. Замечание 4.2.3. С точки зрения общей топологии локальное отношение линейной связности есть нечеткий аналог понятия линейной связности. Приложение А Исходные данные для каждой величины представлены в виде текстовых файлов, в каждой строке первые два числа указывают абсолютные координаты точки, последующие числа это компоненты величины. Промежуточные данные представлены в виде массивов (матриц), соответствующих точкам исследуемого участка. Размеры матриц в зависимости от уровня разложения 64 х 64, 128 х 128, 256 х 256, 512 х 512, 1024 х 1024, к каждой такой матрице прилагается координатная сетка (координатная система) абсолютных координат элементов матрицы. Координатная сетка указывается левым нижним углом, размерами, и углом наклона. Используются также промежуточные данные в виде sparse разреженных матриц. Выходные данные (особые точки и значения величин) имеют структуру исходных данных для удобства их сравнения и накопления.

Похожие диссертации на Задачи динамического программирования и нечеткой кластеризации

Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизацииМельникова Елена Анатольевна

Метод динамических приоритетов и таблиц, его использование при решении многокритериальных трудно формализуемых задач целочисленного программирования в условиях ограниченных ресурсовВеденина Светлана Григорьевна

Модели и методы коррекции задач возможностного программирования и программный комплекс их поддержки Сорокин Сергей Владимирович

Применение мелкозернистого локально-параллельного программирования при решении задач математической физики методом сетокЗаручевская Галина Васильевна

Математическое моделирование распределения ресурсов в задаче сетевого планирования средствами стохастического динамического программированияДокучаев, Александр Владимирович

Оценка качества кластеризации в задачах интеллектуального анализа данныхСивоголовко Елена Владимировна

Решение задач кластеризации на основе хаотической нейронной сетиЖукова Софья Витальевна

Методы кластеризации в задачах оценки технического состояния зданий и сооружений в условиях неопределённостиКоняева Елена Ивановна

Определение и визуализация структуры взаимосвязей объектов статистической системы на основе задачи N тел и нечеткой кластеризацииЛившиц Владимир Леонидович

Семантическое программирование задач спектрального метода теории управленияГаланина, Елена Николаевна