Задачи динамического программирования и нечеткой кластеризации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Куркина, Мария Викторовна

• Куркина, Мария Викторовна
• кандидат физико-математических наук
• 2005

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Задачи динамического программирования и нечеткой кластеризации»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют у\. Средства X, вложенные в г-ое предприятие, приносят к концу года доход /¿(X) и возвращаются в размере X) < Х\ г = 1,2,., т. По истечении года все оставшиеся средства заново перераспределяются между предприятиями, новых средств не поступает и доход в производство не вкладывается. Требуется найти оптимальный способ распределения имеющихся средств.

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

Ха + хгг + . + хьт = У г-Пронормировав переменные управления = ^ получим, что ь

1ы + 7*2 + . + 7Ьтп = 1, 1ы > 0.

То есть точка = {7^} £ А"1-1 принадлежит (га — 1) - симплексу А171-1. Показатель эффективности данной задачи - это доход за один год

1(^1) + /2(^2) + . + /т(я*т).

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

2 = [/1(^1) + /2(^2) + . +

Уравнение состояния выражает остаток средств yt после ¿-го шага и имеет вид

Уе+1 = ^1(^1) + (Р2Ы2) + . -I- (Рт(х1т).

Пусть Z*(Y,t) - условный оптимальный доход, полученный от распределения средств У между т предприятиями в период с ¿-го года до последнего n-го. Рекуррентные функциональные уравнения Беллмана для этих функций имеют вид:

Z*(yn,п) = тах lfi(xm) + . • + fm(xnm)]

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

Z*(yut) = max \fi(xtl) + . + /m(xtm) + Z*(yt+ut+l)\

Xtl + .+Xtm-yt

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

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

Теорема (Теорема 1.2.1). Пусть функции fi(X) и Wi(X) (функции дохода и возврата средств соответственно), линейные fi{X) = hiX, tpi(X) =

ПХу hi 0, Ti >0, i— 1,2,., 772. Тогда функций условного оптимального дохода Z*(y,k) также будут линейные Z*(y,k) = Н^у, при этом коэффициенты Hk находятся рекуррентно:

Нп = А(0), Нп~1 = А(Нп),

Hi = А(Я2), где функция Х(х) = ^ах [hi + гг-ж] - верхняя огибающая линейных функций.

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

Определение. Коэффициентом эффективности i-ого предприятия назовем решение уравнения х = /ц 4- Г{Х , т. е. число hi р. —--l-n

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

Теорема (Теорема 1.2.3). Для многомерной линейной модели распределения ресурсов справедливы утверждения; таxhi < Hi < maxP^, i i lim Hi = maxPj n—+00 i

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

Теорема (Теорема 1.2.4). Пусть функции fi(X) и <Pi(X) (функции дохода и возврата средств соответственно), линейные fi(X) = h{X, <fii(X) = пХ:

Vi > 0, г = 1,2,., 77i. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) = \Z*(y, к), при Л > то есть н£у, у> 0, I Щу, у< 0. при этом коэффициенты , Нк находятся рекуррентно; н: = х+( о), К-1 =

Н- = л-(0),

- Л-(Я-)

Я+ = А+(Я+), яг = Л-(Я2-), где функции А+(з;) = шах [/¿¿Н-тус], Л (х) = min [hi+rix] - соответ

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

Теорема (Теорема 1.2.5). Пусть функции fi(X) и Pi{X) (функции дохода и возврата средств соответственно), линейные fi{X) — hiX, <£>i(X) = TiX; maxi{rj} > 0 > mirii{ri}. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) — XZ*(y, к), при Л > 0, то есть тах{Л+(Яп+),Л+(Я-)} , = min {Х~(Щ), Л"(Я")}

Я+ = тах {Л+(Я2+), Л+(Я2-)} , tff = min {Х~(Н}), Х~(Щ)} , где функции Х+(х) = тах [Л^ + ^х], X (х) = min [1ц + rix] - соответ

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

Оптимальному решению соответствует дискретная динамическая двумерная система, определяемая отображением траектория которой с начальной точкой гг0 = 0, уо = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке. А+(0)

Я" = Л-(0), х* = шах{Л+(х), Х+(у)} , у*= шт{Л-(х),Л-(у)},

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

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

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

Теорема (Теорема 1.2.6). Пусть функции fi{X) и <pi(X), линейные fi(X) = h{X, <Pi(X) — Г{Х; hi > 0, 0 < г* < 1, i = 1,2,. ,га. Тогда функции условного оптимального дохода Z*(y, к) также будут линейные Z*(y, к) = Н^у, при этом коэффициенты Hk находятся рекуррентно; нп = Aq(0),

Нп-1 = Аа(.?/П), #1 = Аа(Я2), функция Аа определена формулой Маоса [hi + TiX], здесь оператор Маха определена формулой:

1 Р г р ' 1

И 3=1 где > Нг2 > Ы3 > . > р = [та] - целая часть та.

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

Кг}, а функцию Аа - верхней а-средней семейства линейных функций.

Определение. Групповым коэффициентом эффективности набора г из р предприятий, где г = {¿1, ¿2,., 1р\, назовем решение уравнения х — - + Ъкх)> 171■ е- ^исло Р Ъ

2^к=1 Пгк

Р —

1 р 1 - -12 к=1т

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

Маха^ < Нх < шах РТ, г т тахРт. п—+оо т

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

Теорема (Теорема 1.3.1). Пусть "ресурс" X = {х-7} €Е ЯР состоит из р компонент, функции "дохода" /{(X) = Кцх3 - линейные, отображения <Р1 : ЕР —» ВР - линейные, <Рг(Х) = {т^х^}3^, здесь по повторяющемуся индексу (вверху и внизу) вычисляется сумма, > 0, г^ > 0, г = 1,2,., т; jJs = 1,2, Тогда функции условного оптимального дохода Z*(Y,k) также будут линейными функционалами Z*{Yyk) = , при этом коэффициенты Zk = £ ЯР находятся рекуррентно: гп = Л(0), = А(£п), . Zx = Л(Я2), где отображение А : BP —> BP имеет компоненты XS(X), определяемые формулами:

XS(X) = max his + r3isXj 4 ' 1 <i<m L ls Ji

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

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

Определение. Вектором ("чистым") эффективности %-ого предприятия назовем решение уравнения xs = hiS + rfsXj , т. е. вектор

Пусть (3 : {1, 2,. ,р} —► {1,2,., т} произвольное отображение конечных множеств. Сопоставим (3 решение Рр системы уравнений xs = /¿3(s)s+ rP(s)sXj' т'е• вектоР

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

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

IMloo = max {1^,1}.

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

IMI = max П^Иоо,

1М1оо<1 будет равна .

1И = д«{ЕИ1

Теорема (Теорема 1.3.3). Пусть нормы линейных операторов строго меньше 1, тогда для многомерной линейной модели распределения ресурсов справедливы утверждения: max hi < i lim Zi = max P/3 > maxFj, n—>oo /? i где неравенство выполняется покомпонентно.

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

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

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

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

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

I I p(h, r)dpdh = 1. J о J о

4. конечны первые моменты + 00 л+оо /*+оо л+оо

Р + ОО Л+ОО Л+ОО Л + ОО / hp(h,r)dpdh < + оо, / / гр(/г,г)фс^ <+оо. 7о Уо Уо Уо

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

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

I p(h, r)dpdh = а.

J Mi

Это те предприятия, которые привлекаются к данному проекту на следующий год. Новых средств не поступает, доход в производство не вкладывается.

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

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

Нп = Аа(0), 1 = \а(Нп), • • • Н\ = Ла(Я2), функция Аа определена формулой

Аа(х) = sup s I [h + rx\p(h, r)dhdr : / p(h, r)dhdr = a > , AC.M lJ A J A J для каждого x множество А С M на котором достигается супремум представляет собой область вида

Мх = {т = (h,r) Е М : h + хг > с} , где константа с зависит от выбора х и определяется из условия p(h,r)dpdh = а. s

Jmx

Замечание. В силу линейности подинтегралъной функции справедливо равенство [И + гх]р(к, г)с£Ыг = (/¿* -I- г*х) / г)(Ик1г, ]а за где точка , г*) - центр тяжести мноэюества А с данной плотностью массы р{К,г). Отсюда следует, что а(х) = [Л 4- гх]р(И, г)йкйг = (/г* 4- г*х)а, Змх где точка дх(Н*,г*) - центр тяжести множества Мх с данной плотностью массы г).

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

Их = {т= (к,г) е М :Н + хг < с} = М\ Мх. Выпуклое множество определенное равенством X назовем запретным уровня а.

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

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

Оа = 0 Мх, х назовем общим уровня а.

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

Пусть £ = £(/1,г) - произвольная функция, А^Аг = Щ. - некоторое разбиение первого квадранта плоскости на два множества, введем обозначения: ¡1\ = I р(Н, r)dhdr, \12= p(h,r)dhdr,

6 = - / t(p,r)p{h,r)dhdr, ¿2 = - / £(р,г>(/г,г)сШг,

Д1УА1 Ач

I = [ £(р, г)р(Н, г)<1Мг, = [ к - е(р, г)]2р(Л, г)йк(1г ил2 и АхиАг

Тогда справедливо равенство ^£>1 + /^¿>2 + - б)2 + ■- Й)2, частный случай общего дисперсионного равенства). Возьмем в качестве множеств А\ = Мх и = ЛГХ, а в качестве функции £ = к + хг, тогда имеем: а, = 1 - а, = Д + ах, £>[£] = £>[/1 + хг],

6 = (Л* + хг*) = -\а(х), 6 = (Л" + хг**) = Н + Х* а 1 — а где точки г), яЦЬ*, г*), д**(Ь**, г**) - центры тяжести множеств Мх,

7УХ при данной плотности р(И,г).

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

D\ 1 = / (/г - h)2p(h, r)dhdr < 00,

Jr2+

D\2 — I (h — h)(r — f)p(h, r)dhdr < 00, D22 = I (r — f)2p(h,r)dhdr < 00,

Я» тогда справедливо равенство a(h + xf) — Aq(x)]'

Ai + 2xA2 + ягДм = + (1 - a)D2 + a(l — q)

Следствие. В условиях теоремы справедливо неравенство a(h + хг) - Aa(x)]2 < a( 1 - a)(Dn + 2xDu + x2D22).

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

Ха(х) < —{h + xf).

OL

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

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

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

• Va Е X : а) = 1 - свойство рефлексивности,

• Va, Ъ £ X : fj,R(a,b) = ßR{by а) - свойство симметричности,

• Va, Ь, с G X : min {ßR(a, b),fj,R(b, с)} < /гя(а, с) - свойство транзитивности.

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

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

• Va е X : />(а, а) = 0,

• Va, b е X : р(а, 6) = р(Ь, а),

• У а, Ь,с € X : р(а, с) < шах {р(а, Ъ),р(Ъ, с)}. Лар?/ (X, р) называют улътраметрическим пространством.

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

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

Нас будет интересовать случай нечеткого отношения эквивалентности Я (или двойственной ультраметрики) на конечном множестве X, содержащем N точек а,г, г = 1,2,., N. Будем отождествлять точки с их номерами, т.е. аг = г. Введем обозначения: = \Ы\ = |И*|| =

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

О < < 1, 0 < рц < 1, (1)

Ни = 1, Ра = 0, (2)

Щ, = Кр = Яр, (3)

Я^оЯ^ = Я^, ЯрбЯр = Яр, (4) где определение композиций о, б числовых матриц дано ниже:

Определение. Мах-тт композицией (соответственно Мъп-тах и Мт-р1ив композицией) матриц Я = Цг^Ц, 5 = \\skjW размеров соответственно пхр и рх т называется матрица Т — ЯоБ (соответственно Т = ЯоБ и Т = Я О Б) размера п х т определяемая соответственно формулами:

Uj = maxjfe=if.>p{min(rifc,Sfcj)}, i — 1,. ,n, j = 1,. ,m, = minfc=1).)P{max(rifc,s^)}, г = 1,. ,n, j = 1,. ,m, iy = minfc=iv.)P {rifc + skj}, t = l,.,n,j = l,.,m.

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

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

Rn R12

К = ,

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

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

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

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

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

Определение. Разделяющим сходством двух различных точек i, j мно-otcecmea X (соответсвенно разделяющим несходством) называются величины: san R{i,j) = rrmxsn(F), saáR(i,j) = minsd(P), где P произвольный путь соединяющий i и j. Если i — j, то sanR(i,j) = 1, sadñ(¿, j) = 0.

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

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

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

Теорема (Теорема 3.2.2). Обозначим через G' = (Х,Е') наименьший остов графа G = (Х,Е), тогда справедливы равенства: sa,nR(i,j) = sn<3'(P'), i sadñ(z,j) = sdG,(P'), где Р' единственный путь (без самоналожения) лежащий в остове G' — (Х,Е') и соединяющий вершины i и j.

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

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

Определим понятие локальной нечеткой близости двух линейных элементов Л(аг1, ух- <рх)> В(х2,7/2", ^2), где (а^, у{) - координаты точек, направление перпендикулярное полю градиенту в данных точках, по формуле где Я/(Л, В) истинное, если каждая из точек по отношению к другой лежит между ветвями гиперболы с вертикальной полуосью 7~о и горизонтальной полусью Го/. Таким образом / - тангенс половины угла раствора гиперболы (угла между асимптотами). На рисунке 1 пункта 4.2.1 показаны две таких линейных элементы и соответствующие им гиперболы. Параметр г о характеризует толщину линии, параметр / константу Липшицевости линии. Величина <1(А, В) - расстояние между точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками.

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

Каждая линейный элемент изображается эллипсом, размер и форма которого управляется функцией /(А¿) = С^^ (матрица С^^ - в стандартной форме), что соответсвует наиболее грубой кластеризации.

Я(А,В) = ехр

Нёг1). ес™ Я/(Л,В) = 1, если В/(А, В) = О,

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Куркина, Мария Викторовна, 2005 год

1. Беллман Р. Динамическое программирование. М.: Изд-во ИЛ, 1960.

2. Беллман Р., Дрейфус О. Прикладные задачи динамического программирования. М.: Наука, 1965. 457с.

3. Арис Р. Дискретное динамическое программирование. М.: Мир, 1969. 168с.

4. Вентцель Е.С. Исследование операций. М.: Наука, 1972.

5. Вагнер Г. Основы исследования операций М.: Мир, 1973.

6. Оскорбин Н.М., Суханов В.А. Исследование операций и теотия игр в элементарном изложении. Барнаул: Изд-во АГУ, 1987. 62 с.

7. Исследование операций: Т.1: Пер. с англ./ Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981.

8. Кремер Н.Ш., Путко Б.А., Тришин И.М. Исследование операций в экономике. ЮНИТИ, 1997.

9. Sutherland, W.R.S.; Wolkowicz, Н.; Zeidan, V. An explicit linear solution for the quadratic dynamic programming problem. J. Optimization Theory Appl. 58, No.2, 319-330 (1988).

10. Черноусько Ф.Л. Динамическое программирование. Соровский образовательный журнал. №2, 1998.

11. Карымов В.Р., Славская М.В. Многомерная линейная модель распределения ресурсов// Математическое образование на Алтае: Труды региональной научно-методической конференции. Барнаул: Изд-во АлГТУ,2001. С.33-36. '

12. Славская М.В. Многомерная линейная модель распределения ресурсов с ограничениями. Вестник БГПУ, №1, Барнаул 2001г. С. 41-44.

13. Славская М.В. Бесконечномерный аналог многомерной линейной модели распределения ресурсов с ограничениями. Тр. рубцовского индустр. инст. Вып.9, Рубцовск, 2001, 8с.

14. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК2002, Барнаул 2002г. 1с.

15. Славская М.В. Линейная модель распределения ресурсов с равномерным распределением параметров. Вестник БГПУ, №2, 2002. 6с.

16. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК-2002, Барнаул, 2002г.

17. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК-2002, Барнаул 2002г. 1с.

18. Славская М.В. Геометрический подход к решению одной задачи динамического программирования. Конференция-школа по геометрии и анализу-2002 посвященная памяти А.Д.Александрова, Новосибирск, 920 сентября 2002г. 1с.

19. Славская М.В. Динамическая линейная модель ресурсов с равномерным распределением параметров. Проблемы теоретической и прикладной математики. Труды 34-й региональной молодежной конференции. Екатеринбург: УрО РАН, УДК 517 ISBN 5-7691-1373-1 2003г. 6с.

20. Славская М.В. Непрерывная модель распределения ресурсов. Вестник БГПУ, №3, 2003. 6с.

21. Куркина М.В. Выпуклая динамическая система связанная с линейной задачей распределения ресурсов. Международная конференция-школа по геометрии и анализу-2004, Новосибирск, 23 авг.- 4 сент. 2004г. 1с.

22. Куркина М.В. Динамическая система связанная с линейной задачей распределения ресурсов. Вестник БГПУ, №3, 2004. бс.

23. Куркина М.В. Многомерная линейная модель распределения ресурсов с непрерывным временем. Конференция МОНО 2004, Барнаул, 2004г.

24. Куркина М.В., Славский В.В. Применение пакета "Scientific Workplace" для организации самостоятельной работы студентов и тестирования их знаний. Тезисы докладов краевой конференции МАК-2001, Барнаул 2004г. 2с.

25. Куркина М.В. Динамическая система связанная с линейной задачей распределения ресурсов. Доклады Академии Наук, Т. 401, №3, 2005. Зс.

26. Кристофидес Н. Теория графов. Алгоритмический подход. Москва:, Мир, 1978.

27. Zadeh L.A. Fuzzy sets. Information and Control, vol. 8, 1965, pp. 338-353.

28. Александр Леоненков. Нечеткое моделирование в среде MATLAB и fuzzyTECH. Санкт-Петербург:, БХВ-Петербург, 2003.

29. Yu LI, Jonathan LI, Haibin DONG, Xiangqian GAO. A fuzzy relation based algorithm for segmenting color aerial images of urban environment

30. Thomas J. Smith. Constructing ultrametric and additive trees based on Li norm. Journal of classification 18: 185-207(2001).

31. Farach M., Kannan S., and Warnow T. A robust model for finding optimal evolutionary trees, Algorithmica 13:155-179, 1995.

32. Hazewinkel M. Classification in Mathematics, Discrete Metric Spaces, and Approximation by Trees. // Report AM-R9505, CWI Amsterdam. The Netherlands.

33. Куратовский К., Мостовский А. Теория множеств. Москва:, Мир, 1979.

34. Цифровая обработка изображений в информационных системах. Учебник. Новосибирск:, НГТУ, 2002.

35. Введение в контурный анализ. Приложение к обработке изображений и сигналов. Под редакцией Я.А. Фурмана. -М. Наука, 2003.

36. Добеши И. Десять лекций по вейвлетам. -Москва-Ижевск., РХД, 2001.

37. J. Podani, P. Csontos and J. Tam6s. Additive trees in the analysis of community data. Community ecology 1: xxx-xxx, Akadftmiai Kiady, Budapest (2000).

38. Makarenkov, Vladimir. Comparison of Four Methods for Inferring Additive Trees from Incomplete Dissimilarity Matrices.

39. B.Leclerc, Minimum spanning trees for tree metrics: abridgements and adjustments, J. Classification 12 (1995) 207-241.

40. Wu, Bang Ye; Chao, Kun-Mao; Tang, Chuan Yi Approximation and exact algorithms for constructing minimum ultrametric trees from distance matrices. J. Comb. Optim. 3, No.2-3, 199-211 (1999).

41. Buneman, P. A Note on the Metric Properties of Trees, Journal of Combinatorial Theory (B), 17, 48-50. (1974)

42. Smolensky, V.A. A method for linear recording of graphs, USSR Comput. Math. Phys. 2 (1969) 396-397.

43. Агекян Т.А. Теория вероятностей для астрономов и физиков. М.: Наука, 1974. С.264

44. Nicholas Jardine, Robin Sibson, Mathematical taxonomy, Wiley, 1971.

45. Bruno M. Carvalho, C. Joe Gau, Gabor T. Herman and T. Yung Kong. Algorithms for Fuzzy Segmentation. // Pattern Analysis & Applications (1999)2:73-81.

46. Herman GT. Geometry of Digital Spaces. Boston, MA: Birkhauser, 1998

47. D. Bryant and V. Moulton. A polynomial time algorithm for constructing the refined buneman tree. Applied Mathematics Letters, 12:51-56, 1999.

48. V. Moulton and M. Steel. Retractions of finite distance functions onto tree metrics. Discrete Applied Math., 1998.

49. Farris J.S. A probability model for inferring evolutionary trees. Systematic Zoology, 22:250-256, 1973.

50. Konstantinos Georgatos. On Indistinguishability and Prototypes. L. J. of the IGPL, Vol. 11 No. 5, pp. 531-545, 2003.