Лингвистические агломеративные алгоритмы определения зон воздействия на лесные массивы разливов нефти

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

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

Блок схема алгоритма экологического зонирования при условии, что количество кластеров совпадает с количеством лингвистических термов предметной области

Рис.4.1.4. Блок схема алгоритма экологического зонирования при условии, что количество кластеров совпадает с количеством лингвистических термов предметной области

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

Для кластеризации лесных участков могут быть использованы различные лингвистические агломеративные алгоритмы. Классические лингвистические агломеративные алгоритмы состоят из следующих шагов:

1. В соответствии с выбранным критерием (например, метрикой Евклида)

рассчитываются расстояния между всеми парами объектов. В табл., содержа-

~ „ г т(т-1)

щей описание m лесных участков, таких расстоянии должно быть: .

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

Для примера рассмотрим пять лесных участков, для описания качества состояния экосистем которых достаточно всего лишь двух интегральных индексов. Данные по участкам представлены в табл.4.2.1.

Таблица 4.2.1. Пример таблицы описания лесных участков с помощью _интегральных индексов_

N/n

//

h

1

1

2

2

1

3

3

2

4

4

2

5

5

4,5

4,5

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

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

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

Полужирной линией на рис.4.2.1 показано расстояние между первым и пятым участками. Всего таких расстояний будет: - ^ — = 10. Их удобно

представить в виде квадратной матрицы:

В матрице Y на главной диагонали приведены расстояния объектов самих с собой, которые равны нулю. Матрица Y симметрична, так как расстояние от I-то объекта до J-ro равно расстоянию от J-ro до 1-то.

2. Осуществить группировку объектов в виде бинарного иерархического дерева.

На этом шаге объекты объединяются в пары по критерию минимального расстояния между ними. Эти пары являются бинарными кластерами. Далее алгоритм объединяет образованные на нижнем уровне пары кластеров в пары более высокого уровня иерархии. Таким образом, формируется бинарное дерево кластеров, которое получило название дендрограммы.

Для лесных участков, представленных на рис.4.2.1, последовательное объединение в бинарные кластеры показано на рис.4.2.2.

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

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

На рис.4.2.2 представлены новые объекты со следующими номерами. Шестой объект - бинарный кластер, объединивший 1-й и 2-й лесные участки. Седьмой объект - бинарный кластер, объединивший 3-й и 4-й лесные участки. Восьмой объект - бинарный кластер, объединивший 6-й и 7-й объекты - кластеры нижнего уровня иерархии.

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

Таблица 4.2.2. Пример таблицы с описанием бинарного дерева кластеров __лесных участков _

Номер

объекта

Первый объект бинарной пары

Второй объект бинарной пары

Расстояние между объектами

6

1

2

1

7

3

4

1

8

6

7

1,414

9

8

5

2,549

Более наглядную картину расположения бинарных кластеров можно получить с помощью дендрограммы. Дендрограмма, соответствующая табл.4.2.2., представлена на рис.4.2.3.

3. Выделить кластеры с помощью дендрограммы. Как следует из рис.4.2.3, первые четыре лесных участка можно объединить в единый класс качества, поскольку расстояние между всеми объектами этого кластера много меньше, чем расстояние от него до пятого участка.

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

Дендрограмма кластеров лесных участков, сгруппированных по интегральным индексам экологического состояния

Рис.4.2.3. Дендрограмма кластеров лесных участков, сгруппированных по интегральным индексам экологического состояния

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

Рассмотрим теперь модернизированный лингвистический агломератив- ный алгоритм учета экологических зон, полученных из анализа "доза- эффект"- зависимостей, который состоит из следующих шагов:

1. Использовать границы зон экологического зонирования, полученные по "доза-эффект" зависимостям.

Для модельной "доза-эффект" зависимости, представленной в табл.4.2.1, можно выделить пять зон экологического зонирования со следующими диапазонами по дозе: {0 -г- 0,25; 0,25 -г- 0,32; 0,32 -г- 0,55; 0,55 -г- 0,75; 0,75 -г- 1}. Эти граничные точки с помощью таблицы "доза-эффект" зависимостей, можно преобразовать в граничные точки по эффекту. Граничные точки по эффекту представляют собой граничные величины интегральных индексов. В случае отсутствия в табл, соответствующих измерений можно воспользоваться интерполяцией.

Таблица 4.2.3. Коэффициенты рассогласования объектов _ дендрограммы рис.4.2.3__

Номер

объектов

Средняя длина связи

Стандартное отклонение длин связей

Количество связей, использованных для расчета

Коэффициент

рассогласования

0,2)

1

0

1

0

(3,4)

1

0

1

0

(6,7)

1,138

0,239

3

1,155

(8.5)

1,982

0,803

2

0,707

2. В конфигурационном пространстве интегральных индексов рассчитать матрицу расстояний R между соседними экологическими зонами. Каждая строка матрицы R соответствует двум соседним зонам и включает три расстояния, показанные на рис.4.2.4.

Схема расстояний между границами двух соседних экологических зон

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

Количество строк в матрице равно: N - 2, где N - количество экологических зон, полученных в результате анализа "доза-эффект" зависимостей.

3. Рассчитать минимальное и максимальное расстояния между соседними зонами:

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

  • 4. Построить дендрограмму.
  • 5. Провести на дендрограмме два сечения на уровнях: rmin и rmax. В результате в качестве кластеров выделяются только те узлы, которые попадают в интервал: (rmjn, rmax). При этом используется матрица объектов, пример которой представлен в табл.4.2.3.

Блок-схема агломеративного алгоритма кластеризации с учетом притяжения кластеров к особым точкам "доза-эффект" зависимостей приведена на рис.4.2.5.

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

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

где С - новая точка деления зоны на две части.

Соответствующий терм лингвистического словаря также должен быть разделен на два новых терма: TL и TR. Блок-схема алгоритма разделения терма на две части представлена на рис.4.2.7. На этом рис. Ктах - обозначает максимальное количество термов, которые необходимо разделить на две части.

Tl и Tr - новые дополнительные термы, которые должны получить имена соответствующих дополнительных экологических зон. Для обеспечения автоматического функционирования алгоритма можно использовать два автоматических модификатора имен термов экологического зонирования: {Ближняя} и {Дальняя}. Так, например, действие модификаторов на терм {Импактная зона} порождает два дополнительных терма: {Ближняя импактная зона} и {Дальняя импактная зона}. Имеется в виду расстояние от места разлива нефти.

Обозначим начальный лингвистический терм через - L, а конечный терм через - R. Также обозначим введенные модификаторы следующим образом: В - {Ближняя} и D = {Дальняя}. Тогда в случае деления начального терма его левая часть останется с именем - L, а правая получит имя В u L. В случае деления конечного терма его правая часть останется с именем - R, а левая получит имя DuR. Любой промежуточный терм при делении на две части порождает термы с именами: {D и Т, В и Т}.

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

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

Области, принадлежащие двум центроидам А и В, попавшим в одну экологическую зону

Рис.4.2.6. Области, принадлежащие двум центроидам А и В, попавшим в одну экологическую зону

Блок-схема алгоритма деления лингвистического терма экологического зонирования на две части

Рис.4.2.7. Блок-схема алгоритма деления лингвистического терма экологического зонирования на две части:

V - словарь лингвистических термов

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

На ряду с лингвистическими агломеративными алгоритмами в задачах кластеризации часто применяют субтрактивные алгоритмы. Рассмотрим работу субтрактивных алгоритмов на примере алгоритма, реализованного в инструментальном пакете MatLab.

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

Потенциал объекта, принадлежащего данному кластеру, рассчитывается по следующей формуле:

где Pj - потенциал j-й точки, - p-я координата k-й точки, г(р) - радиус кластера вдоль р-й координаты. Центром кластера становится точка с наибольшим значением Pj. После этого алгоритм переходит к следующей итерации.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >